의사결정 나무(Decision Tree)

의사결정 나무(Decision Tree) 는 특정 타겟 변수(target variable)에 의해 여러가지 성질의 데이터를 보다 유사한 성질의 소그룹으로 분류하거나 예측하는 것이다. 의사결정 나무는 이상치나 편향된 분포에 민감하지 않으며, 결측치 또한 하나의 노드로 구분이 가능하다는 장점이 있다.

의사결정 나무는 각각의 마디(node) 로 구성되어 있으며 다음과 같이 구분된다. 

- 뿌리마디(root node): 의사결정 나무가 시작되는 마디로 전체 데이터로 구성되어 있다.

- 자식마디(child node): 한가지 마디에서 2개 이상의 마디로 구분된 마디 

- 부모마디(parent node): 자식마디의 상위 마디

- 잎 또는 끝마디(leaf or terminal node): 각각의 줄기의 최종에 위치한 마디로 잎(leaf) 또는 끝마디(terminal node) 라고 하며, 끝마디의 개수만큼 규칙에 생성된 것

- 중간마디(internal node): 의사결정 나무의 중간에 있는 마디로 끝마디가 아닌 것

- 가지(branch): 하나의 뿌리마디에서 끝마디까지 연결된 마디들이며 가지를 이루는 마디의 개수를 깊이(depth) 라 한다.

이렇게 구성되는 의사결정 나무(Decision Tree) 는 뿌리마디(root node) 에서 시작하여 끝마디(leaf) 까지 자식마디(child mode) 로 구성되며 각각의 노드를 구성하기 위한 분리기준(Split Criterion)을 설정하게 된다.

의사결정 나무의 분리기준(Split Criterion) 은 하나의 부모마디로부터 자식마디들이 형성될 때, 생성된 노드에 속하는 자료의 순수도(purity) 가 가장 크게 증가하도록 재귀적으로 진행된다. 이 때 범주형 목표변수(Categorical Target Variable) 에 사용되는 분리기준은 Gini, Entropy, Information gain ratio Chi-square test 등이 있으며, 숫자형 목표변수(Numeric Target Variable) 에 사용되는 불리기준은 Reduction in variance 와 F-test 등이 있다. 

	Discrete target variable	Continuous target variable
CHAID(multi split)	Chi-square statistic	ANOVA F-statistic
CART(binary split)	Gini index	variance reduction
C 4.5	Entrophy index	n/a

1. CHAID(Chi-squared Automatic Interaction Detection) 알고리즘은 카이제곱 검정(Chi-square test: 범주형 목표변수에 적용) 또는 F 검정(F-test: 연속형 목표변수에 적용) 등을 이용하여 분리를 수행하는 알고리즘이다. 카이제곱 검정은 관측도수(Oj )와 기대도수(Ej)의 차이의 제곱합을 사용하는 피어슨(Pearson) 카이제곱 통계량을 사용한다.

 

이렇게 산출된 통계량을 사용하며, 관측도수와 기대도수의 차이가 커질 수록 순수도(Purity) 는 높아지고, 좋은 분리(Split) 가 됐다고 할 수 있다. 즉, 카이제곱 통계량이 가장 큰 예측변수를 사용하여 자식마디를 형성한다. 

2. CART(classification and Regression Trees) 알고리즘은 지니지수(Gini index: 범주형 목표변수에 적용) 또는 분산의 감소량(variance reduction: 연속형 목표변수에 적용) 등을 이용하여 분리를 수행하는 알고리즘이다. 지니점수(Gini Score) 는 0 에서 1 사이의 숫자로 나타낼 수 있으며, 1인 경우는 완벽한 순수(Purity)의 노드를 나타낸다. 

가령, 부모마디에서 흰색과 검은색으로 구분된 20개의 구슬을 선택함에 있어, 자식마디에서 흰색 9개와 검은색 1개의 왼쪽 노드와 흰색 1개와 검은색 9개의 오른쪽 노드로 선택되었다고 하자. 이럴 경우, 부모마디의 지니점수는 (10/20)^2+(10/20)^2=0.5 이다. 자식마디 왼쪽노드의 지니점수는 (9/10)^2 + (1/10)^2=0.82이며 오른쪽 노드의 점수는 (1/10)^2 + (9/10)^2=0.82이다. 따라서, 10/20*0.82 + 10/20*0.82=0.82 이다. 

지니지수(Gini Index) 는 각 마디에서의 불순도(impurity) 또는 다양도(diversity) 를 측정하는 것으로 다양도 지수(Diversity Index) 로 사용되기도 한다. 다양도 지수는

와 같이 표현될 수 있다. 여기에서 c 는 목표변수의 범주의 수를 나타내며 P(j) 는 j 범주에 분류될 확률이다. n 은 마디에 포함되어 있는 관찰치의 수이며 는 목표변수의 j 번째 범주에 속하는 관찰치의 수이다.

3. C 4.5 알고리즘의 엔트로피지수(Entropy index) 는 다항분포에서 우도비 검정통계량을 사용하는 것으로, 이 지수가 가장 작은 예측변수와 그 때의 최적분리에 의해 마디를 생성한다. 즉, 부모마디(parent node) 의 엔트로피(Entropy) 에서 자식마디(child node) 의 엔트로피(Entropy) 를 차감하여 산출한다. 엔트로피(Entropy) 는 각 마디(node) 의 목표변수의 범주별 비율에 로그(log) 를 취하고, 각 비율을 곱한 값들을 합하여 산출한다. 단, 일반적으로 음의 값을 갖게 되므로 -1을 곱하여 양수로 나타나게 된다.

가령, 부모마디에서 흰색과 검은색으로 구분된 20개의 구슬을 선택함에 있어, 자식마디에서 흰색 9개와 검은색 1개의 왼쪽 노드와 흰색 1개와 검은색 9개의 오른쪽 노드로 선택되었다고 하자. 이럴 경우, 부모마디의 엔트로피는 -[0.5 * log2(0.5) + 0.5 * log2(0.5)]=1 이다. 자식마디 왼쪽노드의 엔트로피는 -[0.9 * log2(0.9) + 0.1 * log2(0.1)]=0.47 이며 오른쪽 노드의 엔트로피는 -[0.1 * log2(0.1) + 0.9 * log2(0.9)]=0.47 이다. 따라서, Entropy Reduction 은 1-(0.5*0.47 + 0.5*0.47)=0.53 이다.

다른 예로, 부모마디에서 흰색과 검은색으로 구분된 20개의 구슬을 선택함에 있어, 자식마디에서 흰색 0개와 검은색 6개의 왼쪽 노드와 흰색 10개와 검은색 4개의 오른쪽 노드로 선택되었다고 하자. 

우선 지니점수의 경우, 부모마디의 지니점수는 (10/20)^2+(10/20)^2=0.5 이다. 자식마디 왼쪽노드의 지니점수는 (0/6)^2 + (6/6)^2=1 이며 오른쪽 노드의 점수는 (10/14)^2 + (4/14)^2=0.59 이다. 따라서, 6/20*1 + 14/20*0.59=0.71

엔트로피의 경우, 부모마디의 엔트로피는 -[0.5 * log2(0.5) + 0.5 * log2(0.5)]=1 이다. 자식마디 왼쪽노드의 엔트로피는 -[0 * log2(0) + 1 * log2(1)]=0 이며 오른쪽 노드의 엔트로피는 -[10/14 * log2(10/14) + 4/10 * log2(4/10)]=0.86 이다. 따라서, Entropy Reduction 은 1-(6/20*0 + 14/20*0.86)=0.40 이다.

첫 번째 구분과 두 번째 구분된 예제를 통해서 알 수 있듯이 첫 번째가 지니점수 및 엔트로피가 높게 산출되었다. 즉, 분류기준에 있어 첫 번째 구분이 순수도(purity)가 높게 잘 구분되었다고 할 수 있는 것이다.