의사결정나무 정의
- 나무 모양으로 나타내어 전체 자료를 몇 개의 소집단으로 분류하거나 예측을 수행하는 기법
- 상위노드로부터 하위노드로 트리구조를 형성
- 매 단계마다 분류 변수와 분류 기준값의 선택 중요
- 상위노드에서 분류된 각각의 하위노드는 노드 내 동질성이 커지고, 노드 간에는 이질성이 커지는 방향으로 분류 변수와 기준값 선택
- 모델의 크기는 과대적합(또는 과소적합)되지 않도록 적절히 조절
- 예) 시장조사, 광고조사, 품질관리, 타겟 고객 분류, 고객 신용분류, 행동 예측 등
의사결정나무 구성
- 뿌리 마디(Root Node, 뿌리 노드)
- 나무가 시작되는 마디
- 부모가 없는 마디로 대상이 되는 모든 자료집합 포함
- 중간 마디(Internal Node)
- 뿌리 마디에서 나온 각 나무줄기 중간에 있는 마디
- 끝 마디(Terminal Node, 잎 노드)
- 각 나무줄기의 끝에 있는 마디
- 자식이 없는 마디
- 자식 마디(Child Node)
- 하나의 마디로부터 분리된 2개 이상의 마디
- 부모 마디(Parent Node)
- 자식 마디의 상위 마디
- 가지(Branch)
- 하나의 마디로부터 끝 마디까지 연결된 마디들
- 깊이(Depth)
- 가장 긴 가지의 크기(마디의 개수)
의사결정나무 종류
분류나무
- 이산형(범주형) 목표변수에 따른 빈도 기반 분리에 사용
- 이산형 목표변수 : 목표변수 범주에 속하는 빈도(frequency) 기반 입력 데이터가 분류되는 클래스
- 상위 노드에서 가지 분할을 진행할 때 분리 기준
- 카이제곱 통제량의 p-value : ((실제도수-기대도수)^2/기대도수) 의 합
- 지니 지수(Gini Index) : 특정 집합에서 한 항목을 뽑아 무작위로 라벨 추정 시 틀릴 확률
- 엔트로피 지수(Entropy Index) : 무질서 정도에 대한 측도
- 분리 기준을 선택할 때에는 불순도를 통해 자식 노드가 현재 노드에 비해 불순도가 감소되도록 설정
- 분리 기준 : 어떤 입력변수를 입력하여 분리하는 것이 의사결정 나무 모델의 목표에 가장 잘 부합하는지에 대한 기준
- 불순도 : 서로 다른 데이터가 섞여 있는 정도
- 정보 획득(Information Gain) : 불순도 차이
회귀나무
- 연속형(수치형) 목표변수에 따른 평균/표준편차 기반 분리에 사용
- 연속형 목표변수 : 목표변수 평균/표준편차 기반 예측된 결과로 특정 의미 지니는 실수값 출력
- 상위 노드에서 가지분할을 진행 할 때 분리 기준
- 분산분석 F-통계량의 p-값(p-value of F-Statistic) : 등분산성을 검정하여 p-값이 커지면 등분산성이 있음을 뜻하므로 낮은 이질성, 즉 순수도가 높아짐
- 분산의 감소량(Variance Reduction) : 분산의 감소량이 최대화가 될수록 낮은 이질성, 순수도가 높아지는 방향으로 가지분할 진행
의사결정나무 분석 과정
- 변수 선택
- 목표변수와 관련된 설명(독립) 변수들을 선택
- 의사결정나무 형성
- 분석목적에 따른 적절한 분리기준과 정지규칙, 평가기준 등으로 의사결정나무 생성
- 정지규칙 : 더 이상 분리가 일어나지 않고 현재의 마디가 끝 마디가 되도록 하는 여러 규칙
- 가지치기
- 부적절한 나뭇가지 제거
- 오버피팅을 막고 일반화 성능을 높임
- 모형 평가 및 예측
- 이익(gain), 위험(risk), 비용(cost) 등을 고려
- 모델을 평가하며 분류 및 예측 수행
- 정보 획득(Information Gain)
- 순도가 증가하고 불확실성이 감소하는 것
- 현재 노드의 불순도와 자식노드의 불순도 차이를 의미
- 재귀적 분기(Recursive Partitioning) 학습
- 분기 전보다 분기 후 각 영역의 정보 획득량이 높아지도록 입력 변수 영역 구분
- 사전에 설정한 기준을 만족할 때까지 분기를 반복하는 학습
- 모든 잎(끝마디)의 엔트로피가 0이 될 때까지 반복하는데 새로운 데이터가 제대로 분류되지 못하는 현상을 방지하기 위해 일정 단계에서 중지하거나 분기를 재조정하는 가지치기 단계로 이동
- 가지치기
- 평가용 데이터 활용
- 부적절한 추론규칙을 가지고 있거나 불필요한 또는 분류오류를 크게 할 위험 있는 마디 제거
- 에러감소 가지치기(Reduced Error Pruning)
- 분할/결합 전과 후의 오류를 비교
- 오류가 더 이상 줄어들지 않을 때까지 반복하는 방법
- 룰 포스트 가지치기(Rule Post Pruning)
- 나무구조를 뿌리 노드부터 잎 노드까지 경로의 형태로 변환
- 정확도가 낮은 순서대로 제거하는 방법
- 분기가 너무 많을 경우 학습데이터가 과적합되어 더 복잡한 트리 생성 가능성 존재
- 사전 가지치기와 사후 가지치기를 이용하여 과적합 방지
- 타당성 평가
- 이익, 비용, 위험 등을 고려하여 모형을 평가하는 단계
- 이익 도표, 위험 도표, 교차 타당성(교차 검증)으로 의사결정나무 평가
- 해석 및 예측
- 의사결정나무 최종 모델에 대한 해석으로 분류 및 예측 모델을 결정
- 의사결정나무를 이용하여 인공지능을 학습시키는 포스팅
2022.05.09 - [Programming/Machine Learning (Python)] - 인공지능 머신러닝 - Decision Tree 모델
의사결정나무 대표적 알고리즘
CART(Classification and Regression Trees)
- 일반적으로 활용되는 의사결정나무 알고리즘
- 불순도 측도로 범주형 또는 이산형일 경우 지니 지수 활용
- 불순도 측도로 연속형인 경우 분산의 감소량을 이용한 이진분리 활용
C4.5 / C5.0
- 범주형/이산형 목표변수에만 활용
- 불순도 측도로 범주형 또는 이산형의 경우에만 엔트로피 지수 활용
- 범주의 수만큼 분리가 일어나는데 각 마디에서 다지분리(multiple split) 가능
CHAID(Chi-squared Automatic Interaction Detection)
- 범주형/이산형 목표변수와 연속형 목표변수에 활용
- 불순도 측도로 범주형 또는 이산형일 경우 카이제곱 통계량 활용
- 불순도 측도로 연속형일 경우 ANOVA F-통계량 활용
- 가지치기를 하지 않고 적당한 크기에서 성장을 중지
- 분리변수의 범주마다 마디를 형성하는 다지분리(multiple split) 가능
랜덤 포레스트(Random Forest)
- 부트스트래핑과 배깅을 이용하여 숲을 형성하게하는 것
- 부트스트래핑 기반 샘플링을 활용한 의사결정나무 생성
- 부트스트래핑(BootStrapping)
- 단순 복원 임의추출법(랜덤 샘플링)
- 크기가 동일한 여러 개의 표본자료를 생성
- 전체 관측값들 중 일부를 뽑아 통계값을 측정하는 과정을 여러 번 반복하는 것
- 부트스트래핑(BootStrapping)
- 이후 배깅 기반 나무들을 모아 앙상블 학습
- 배깅(Bagging, Bootstrap Aggregating)
- 여러 부트스트랩 자료를 생성하여 학습하는 모델링
- 분류기를 생성한 후 그 결과를 앙상블 하는 방법
- 추출한 각 샘플별 모델링 학습 뒤 결과들을 집계, 최종 결과를 만들어내는 방식
- 범주형 데이터 : 다수결 투표 방식
- 연속형 데이터 : 평균으로 결과 집계
- 앙상블 학습(Ensemble Learning)
- 여러 모델을 학습시켜 결합하는 방식의 학습방법
- 일반화 성능을 향상시켜 과적합 해결
- 부스팅(Boosting)
- 가중치 활용하여 약분류기를 강분류기로 만드는 방법
- 순차적으로 분류 모델들이 틀린 곳에 집중하여 새로운 분류 규칙을 생성하는 기법
- 이전 분류기의 학습 결과를 토대로 다음 분류기의 학습 데이터의 샘플 가중치를 조정해 학습 진행
- 잘 맞춘 약분류기 : 가중치를 더함
- 잘못 평가한 약분류기 : 가중치를 뺌
- 누적된 약분류기 가중치를 합산하여 최종 학습 모델링
- 배깅(Bagging, Bootstrap Aggregating)
의사결정나무 장단점
- 장점
- 연속형, 범주형 변수 모두 적용
- 변수 비교가 가능하며 규칙에 대해 이해하기가 쉬움
- 데이터로부터 규칙을 도출하는 데에 유용
- 활용 분야 : DB 마케팅, CRM, 시장조사, 기업 부도/환율 예측 등
- 단점
- 트리구조가 복잡할 시 예측/해석력 저하
- 데이터 변형에 민감
참고