의사 결정 나무 Decision Tree

분석의 목적과 자료구조에 따라서 적절한 '분리기준' + 정지규칙/가지치기를 통하여 의사결정나무를 얻는다. 모형에서 분리의 기준은 부모마디에 비해 자식마디에서 순수도(=목표변수의 특정 범주에 개체들이 포함되어 있는 정도)가 증가하는 정도를 수치화한 것이 된다. = 부모 마디에서 자식 마디로 갈수록 순수도는 증가한다. 상위의 노드로부터 하위의 노드로, 나무 구조를 형성하는 매 단계마다 분류 기준의 선택값과 분류 변수가 중요하다. 선형성, 정규성, 등분산성 등의 수학적 가정이 불필요한 비모수적 모형이다.

 

[출처] 위키피디아 (https://en.wikipedia.org/wiki/Decision_tree_pruning)

 

맨 위의 마디를 뿌리마디(Root node)라 하며, 이는 분류 또는 예측 대상이 되는 모든 자료 집단을 포함한다. 상위의 마디는 하위의 마디로 분리된다. 이때 상위 마디를 부모마디(Parent node)라고 하고, 하위마디를 자식마디(Child node)라고 하며 더 이상 분기되지 않는 마디를 최종 마디(Terminal node)라고 부른다.

 

나무를 만들 때 분리 기준과 함께 정지 규칙을 꼭 세우고,
과대적합 시에는 가지치기Prunning해줄 것

의사결정 나무가 성장하는 과정 중 정지 규칙을 적용하지 않으면 모든 터미널 노드의 순도가 100%(불순도 0)인 상태가 되는데 이를 Full Tree라고 한다. Full Tree까지 성장하면 분기가 너무 많아져 과대적합(overfitting)이 발생할 수 있다. 분기가 너무 많으면(과대적합 상태) 현실문제에 적응할 수 없는 규칙이 나오게 된다. 이러한 과대적합 문제를 해결하기 위해 가지치기(Prunning)를 해준다. 과대 적합 상태에서는, 가지치기를 통하여 제시되는 규칙들의 타당성을 검토해 타당성이 없는 규칙을 제거함으로써 과적합을 방지하고 적합한 수준에서 터미널 노드를 결합해준다. 

 

장점과 단점 

장점	1. 구조가 단순하여 해석이 용이    2. 유용한 입력변수의 파악과 예측변수 간의 상호작용 및 비선형성을 고려하여 분석이 가능    3. 수학적 가정이 불필요한 비모수적 모형    4.계산 비용이 낮아 대규모 데이터셋에서도 비교적 빠르게 연산 가능    5. 수치형/범주형 변수를 모두 사용할 수 있다.
단점	1. 분류 기준값의 경계선 부근에서는 자료값에 대해서는 오차가 크다.   2. 로지스틱회귀와 같이 각 예측변수의 효과를 파악하기 어렵다.   3. 새로운 자료에 대한 예측이 불안정할 수 있다.

 

알고리즘 별 분리, 정지 기준변수 선택법

알고리즘	이산형 목표변수 (분류나무)	연속형 목표변수 (회귀나무)
CART (Classification And Regression Tree)	지니지수	분산 감소량
C5.0	엔트로피 지수
CHAID (Chi-squared Automatic Interaction Detection)	카이제곱 통계량의 p-value	(ANOVA F-통계량) -( p-value)

의사결정나무를 위한 알고리즘은 CHAID, CART, ID2, C5.0, C4.5가 있으며 하향식 접근 방법(Top-down)을 이용한다.

 

 

출처 : ADsP 이론서, EduAtoZ - Programming YouTube, 위키피디아