의사결정나무(Decision Tree)

[Site Map]  [인공지능목차]

 

연관토픽

1. [상위] 데이터 마이닝(Data Mining)

 

개념

• 의사결정규칙 과정을 나무 구조로 단계별 도표화하여 분류 또는 예측을 수행하는 통계 분석 기법
• 정량적 분리기준에 따라 분할(split)와 가지치기(pruning)을 통해 대상이 되는 집단을 몇 개의 소집단으로 구분하는 분류 및 예측 기법
• 각 데이터들이 가진 속성들로부터 분할 기준 속성을 판별하고, 분할 기준 속성에 따라 트리 형태로 모델링하는 분류 예측 모델
• 관찰된 데이터로부터 분할기준 속성을 판별하고, 분할기준 속성에 따라 최대 purity를 달성하며, 트리 형태로 모델링한 분류/예측기법
• 의사결정나무는 분류(Classification)와 회귀(Regression) 모두 가능

 

 

 

의사결정나무 목적

• 새로운 데이터에 대한 분류(Classification)하거나, 해당 범주의 값을 예측(Prediction)
• 데이터로부터 tree 구조의 일반화된 지식을 추출

 

 

 

의사결정나무 형성과정

단계	설명
의사결정나무 분할/성장	분석의 목적과 자료구조에 따라서 적절한 분리기준(split criterion)과 정지규칙(stopping rule)을 지정하여 의사결정나무를 얻음
가지치기(pruning)	오류율을 크게 할 위험이 높거나 부적절한 규칙을 가지고 있는 가지를 제거
타당성 평가	이익도표(gain chart)나 위험도표(risk chart) 또는 검증용 데이터(test data)에 의한 교차 타당성 등을 이용하여 의사결정나무 평가
해석 및 예측	의사결정나무를 해석하고 예측모형 설정

 

 

 

의사결정나무 개념도

 

 

 

의사결정나무 기법의 처리절차

처리절차	핵심요소	설명
기준설정	분리기준(split criterion), 정지규칙 지정	분석 목적과 자료구조에 따라 적절히 분리
Recursie Partitioning	지니계수, 엔트로피 계산	지니계수, 엔트로피 계산을 통한 purity check을 수행하며, 반복적인 partitioning 수행
가지치기	부적절 규칙의 가지 제거	하위 속성에 대한 가지치기 수행 분류오류 위험이 높거나 부적절한 규칙의 가지 제거
타당성 평가	Cross Validation	이익도표, 위험도표, validation set 이용한 평가
해석 및 예측	모형 결정	의사결정 나무의 해석, 분류, 예측 모형 설정

• Split 수가 증가할수록 training set의 에러율은 감소하지만, validation set은 특정 지점부터 에러율이 증가하므로, 해당 지점에서 split 수를 결정해야 함

 

 

 

의사결정나무 사용 알고리즘

알고리즘	설명	분류나무	회귀나무
CART[각주:1]	데이터 누락이나 필드 수가 많은 경우 다중 분리 대비 정확도는 떨어짐 이지 분리라 분류가 간단하여 해석 편함	O	O
CHAID[각주:2]	비이분형 트리로 광범위한 트리 작성 복잡한 모형 생성으로 과적합 문제가 적고 정확도가 높음	O	O
C5.0	데이터 누락이나 필드 수가 많은 경우 정확도가 높은 알고리즘이나 과접학	O	X

 

 

 

의사결정나무 분리기준(splitting criterion)

(1) 이산형 목표변수

기준값	분리기준
카이제곱 통계량 p 값	p값이 가장 작은 예측변수와 그 때의 최적분리에 의해 자식마디를 형성
지니 지수	지니 지수를 감소시켜주는 예측변수와 그 때의 최적분리에 의해서 자식마디를 형성
엔트로피 지수	엔트로피 지수가 가장 작은 예측변수와 이 때의 최적분리에 의해 자식마디를 형성

 

(2) 연속형 목표변수

기준값	분리기준
분산분석에서 F통계량	p 값이 가장 작은 예측변수와 그 때의 최적분리에 의해서 자식마디를 형성
분산의 감소량	분산의 감소량을 최대화하는 기준의 최적분리에 의해 자식마디를 형성

 

 

 

의사결정나무 알고리즘별 분리기준

알고리즘	분류나무 (반응변수 : 범주형)	회귀나무 (반응변수 : 수치형)
CART	지니지수[각주:3] (이분형 분류)	분산의 감소량
CHAID	카이제곱 통계량의 p-값 (다중 분류)	분산분석 F 통계량의 p-값
C5.0	엔트로피지수 (다중 분류)

 

 

 

의사결정나무 용어

 

 

 

의사결정나무 분석 수행절차

단계	설명
1	분석 목적과 데이터 형태에 따라 적절한 분리기준[각주:4]과 정지규칙[각주:5] 지정
2	의미 없는 분할이 계속되지 않도록 가지치기[각주:6]

 

 

 

의사결정나무의 장단점

장단점	설명
장점	이상치(outlier) 자체를 하나의 경우로 분류하기 때문에 이상치에 안정적임 반응변수는 수치자료와 범주자료에 상관없이 모두 분석 가능 나무 구조로 단계별로 표현되어 모형을 쉽게 이해할 수 있고 해석이 용이함 화이트 박스(white box) 모형이며, 어떤 설명 변수가 가장 중요한지 시각적으로 파악이 쉬움
단점	설명 변수가 수치형인 경우 비연속적인 값으로 취급하여 예측 오류가 클 가능성이 있음 나무구조가 복잡할수록 예측력이 저하되고 해석 또한 어렵고, 최적 결정트리를 보장 못함 정확한 모형을 만들기 위해서는 설명변수의 범주별 개체수가 어느 정도 확보되어야 함 과적합(overfitting) : 훈련 데이터를 제대로 일반화하기 못할 경우 너무 복잡한 결정 트리를 만들 수 있으며, 약간의 데이터 변화에 트리의 모양이 전혀 달라짐

 

 

 

합격답안

1. [답안] 의사결정트리의 지니지수, 엔트로피(1교시)

 

 

 

 

 

 

1. CART : Classification And Regression Tree [본문으로]
2. CHAID : CHi-squared Automatic Interaction Detection [본문으로]
3. 지니지수 : 불순도를 측정하는 지수 [본문으로]
4. 분리기준 : 설명 변수를 이용하여 반응변수의 분포를 분류할 때 사용되는 기준(반응 변수의 형태에 따라 다름) [본문으로]
5. 정지규칙 : 더 이상 분리가 일어나지 않고, 현재의 마디가 끝 마디가 되도록 지정하는 규칙 [본문으로]
6. 가지치기 : 불필요한 가지를 잘라내는 작업. 지나치게 많은 가지를 가지는 의사결정나무는 새로운 데이터를 적용할 때 과적합이 발생하므로 적절하지 않은 마디를 제거하여 적당한 크기의 나무 구조를 최종 모형으로 선택하는 것이 바람직함 [본문으로]