A Step by Step CHAID Decision Tree Example
CHAID는 가장 오래된 결정 트리 알고리즘 중 하나로 1980년 Gordon V. Kass에 의해 알려졌고 CART는 1984년에 ID3는 1986년 그리고 C4.5는 1993년에 발표되었다. CHAID는 CHi-square Automatic Interaction Detection(카이제곱 자동 상호작용 감지)의 머리글자 이다. 여기서 카이제곱(chi-square)은 특성의 중요도를 찾기 위한 지표(metric)이다. 높은 값일수록 더 높은 통계적 중요성을 갖는다. 다른 것과 유사하게 CHAID는 분류 문제에 대한 결정 트리를 구성한다. 이는 범주형 목표 변수(target variable)를 갖는 데이터셋을 사용한다는 의미이다.
Living trees in the Lord of the Rings (2001)
CHAID in Python
이글에서는 CHAID 알고리즘에 대해 깊게 알아보고 단계별로 문데를 해결해 본다. 여기에 CHAID 알고리즘을 파이썬으로 구현한 것을 찾을 수 있다.
CHAID in chefboost for python
Objective
특성의 카이제곱값으로 결정 규칙을 찾는다.
수식(Formula)
CHAID는 가장 지배적인 특성을 찾기위해 카이제곱(chi-square) 테스트를 사용하지만 ID3는 정보 이익(information gain)을 C4.5는 이익 비율(gain ration), CART는 GINI Index를 사용한다. 카이제곱 테스트는 [Karl Pearson]https://en.wikipedia.org/wiki/Karl_Pearson)에 의해 발전되었다. 그는 또한 상관관계(correlation)의 창시자이다. 오늘날 대부분의 컴퓨터 라이브러리(예를 들면, Pandas)는 기본적으로 상관관계에 Pearson 지표를 사용한다.
카이제곱의 수식은 쉽다.
$\sqrt{\frac{(y - y')^2}{y'}}$
- y : 실제값
- y' : 예측값
Data set
아래 데이터셋으로 결정 규칙을 구성한다. 결정(Decision) 컬럼은 몇가지 특성을 기초로 찾기를 바라는 목표(target)이다.
아무튼, 여기서는 날(day) 컬럼이 단순히 라인 번호이기 때문에 무시한다.
| Day | Outlook | Temp. | Humidity | Wind | Decision |
|---|---|---|---|---|---|
| 1 | Sunny | Hot | High | Weak | No |
| 2 | Sunny | Hot | High | Strong | No |
| 3 | Overcast | Hot | High | Weak | Yes |
| 4 | Rain | Mild | High | Weak | Yes |
| 5 | Rain | Cool | Normal | Weak | Yes |
| 6 | Rain | Cool | Normal | Strong | No |
| 7 | Overcast | Cool | Normal | Strong | Yes |
| 8 | Sunny | Mild | High | Weak | No |
| 9 | Sunny | Cool | Normal | Weak | Yes |
| 10 | Rain | Mild | Normal | Weak | Yes |
| 11 | Sunny | Mild | Normal | Strong | Yes |
| 12 | Overcast | Mild | High | Strong | Yes |
| 13 | Overcast | Hot | Normal | Weak | Yes |
| 14 | Rain | Mild | High | Strong | No |
이 데이터셋에서 가장 지배적인 특성을 찾아야 한다.
전망 특성(Outlook feature)
전망 특성은 맑음(sunny), 흐림(overcast), 비(rain)의 3가지 분류(class)를 갖고 'Yes'와 'No' 2가지 결정(decision)이 있다. 우선 각 분류에 대한 'Yes'와 'No' 결정의 수를 정리한다.
| Yes | No | Total | Expected | Chi-square Yes | Chi-square No | |
|---|---|---|---|---|---|---|
| Sunny | 2 | 3 | 5 | 2.5 | 0.316 | 0.316 |
| Overcast | 4 | 0 | 4 | 2 | 1.414 | 1.414 |
| Rain | 3 | 2 | 5 | 2.5 | 0.316 | 0.316 |
Total 컬럼은 각 열(row)에서 Yes와 No 결정의 합이다. Expected 값은 결정이 Yes와 No의 2가지 분류가 있기 때문에 total 컬럼의 절반이다. 이 테이블로 카이제곱 값을 구하는 것은 쉽다.
예를 들어 맑음 전망에 대한 Yes의 카이제곱은 다음과 같다.
$\sqrt{(2 - 2.5)^2 \div 2.5} = 0.316$
여기서 실제값은 2, 예측값은 2.5이다.
전망의 카이제곱값은 카이제곱 Yes와 카이제곱 No 컬럼의 합이다.
$0.316 + 0.316 + 1.414 + 1.414 + 0.316 + 0.316 = 4.092$
이제 다른 특성에 대한 카이제곱값도 알아보자. 최대 카이제곱 값을 갖는 특성이 결정 지점(decision point)가 된다.
온도 특성(Temperature feature)
온도 특성은 더움(hot), 포근함(Mild), 추움(Cool)의 3가지 분류가 있다. 다음은 이들 분류에 대한 카이제곱 값을 정리한 것이다.
| Yes | No | Total | Expected | Chi-square Yes | Chi-square No | |
|---|---|---|---|---|---|---|
| Hot | 2 | 2 | 4 | 2 | 0 | 0 |
| Mild | 4 | 2 | 6 | 3 | 0.577 | 0.577 |
| Cool | 3 | 1 | 4 | 2 | 0.707 | 0.707 |
온도 특성에 대한 카이제곱 값은 다음과 같다.
$0 + 0 + 0.577 + 0.577 + 0.707 + 0.707 = 2.569$
이 값은 전망의 카이제곱 값보다 작다. 이는 카이제곱 테스트로 전망 특성이 온도 특성보다 더 중요하다는 것을 의미한다.
습도 특성(Humidity feature)
습도는 높음(High), 보통(Normal)의 2가지 분류가 있다.
| Yes | No | Total | Expected | Chi-square Yes | Chi-square No | |
|---|---|---|---|---|---|---|
| High | 3 | 4 | 7 | 3.5 | 0.267 | 0.267 |
| Normal | 6 | 1 | 7 | 3.5 | 1.336 | 1.336 |
온도 특성의 카이제곱 값
$0.267 + 0.267 + 1.336 + 1.336 = 3.207$
이 값도 전망의 카이제곱값보다 작다.
바람 특성(Wind feature)
바람 특성은 약함(Weak), 강함(Strong)의 2가지 분류이다.
| Yes | No | Total | Expected | Chi-square Yes | Chi-square No | |
|---|---|---|---|---|---|---|
| Weak | 6 | 2 | 8 | 4 | 1 | 1 |
| Strong | 3 | 3 | 6 | 3 | 0 | 0 |
바람 특성의 카이제곱 테스트 값은 2이다. (원문에서는 weak|Yes의 개수가 하나 적어 다른 값으로 계산되었다.)
여기까지 모든 특성애 대한 카이제곱 값을 구했다.
| Feature | Chi-square value |
|---|---|
| Outlook | 4.092 |
| Temperature | 2.569 |
| Humidity | 3.207 |
| Wind | 2 |
보이는 것과 같이 전망 특성이 가장 높은 카이제곱 값을 갖으므로 가장 중요한 특성이 된다. 따라서 전망 특성을 루트 노드로 놓는다.
CHAID 트리의 초기 형태
위 그림에서 전망 분류로 원시데이터를 나눴다. 예를 들면, 흐림(overcast) 분기는 하위 데이터셋에 'Yes' 결정만을 갖는다. 이것은 CHAID 트리가 흐림일 경우 'Yes'를 반환한다는 의미이다.
맑음과 비 분기 모두는 Yes와 Ne를 갖는다. 이 하위 데이터셋에 카이제곱 테스를 적용한다.
Outlook = Sunny 분기(branch)
이 분기에는 5개의 데이터(instance)가 있다. 이제 가장 지배적인 특성을 찾아보자. 여기서는 전망(outlook) 컬럼은 모두 동일하기 때문에 무시한다. 즉, 온도, 습도 그리고 바람 중에서 가장 중요한 특성을 찾는다.
| Day | Outlook | Temp. | Humidity | Wind | Decision |
|---|---|---|---|---|---|
| 1 | Sunny | Hot | High | Weak | No |
| 2 | Sunny | Hot | High | Strong | No |
| 8 | Sunny | Mild | High | Weak | No |
| 9 | Sunny | Cool | Normal | Weak | Yes |
| 11 | Sunny | Mild | Normal | Strong | Yes |
맑음 전망에서 온도 특성
| Yes | No | Total | Expected | Chi-square Yes | Chi-square No | |
|---|---|---|---|---|---|---|
| Hot | 0 | 2 | 2 | 1 | 1 | 1 |
| Mild | 1 | 1 | 2 | 1 | 0 | 0 |
| Cool | 1 | 0 | 1 | 0.5 | 0.707 | 0.707 |
$\text{Chi-square value(Outlook=Sunny|Temperature)} = 1 + 1 + 0 + 0 + 0.707 + 0.707 = 3.414$
맑음 전망에서 습도 특성
| Yes | No | Total | Expected | Chi-square Yes | Chi-square No | |
|---|---|---|---|---|---|---|
| High | 0 | 3 | 3 | 1.5 | 1.225 | 1.225 |
| Normal | 2 | 0 | 2 | 1 | 1 | 1 |
$\text{Chi-square value(Outlook=Sunny|Humidity)} = 1.225 + 1.225 + 1 + 1 = 4.449$
맑음 전망에서 바람 특성
| Yes | No | Total | Expected | Chi-square Yes | Chi-square No | |
|---|---|---|---|---|---|---|
| Weak | 1 | 2 | 3 | 1.5 | 0.408 | 0.408 |
| Strong | 1 | 1 | 2 | 1 | 0 | 0 |
$\text{Chi-square value(Outlook=Sunny|Wind)} = 0.408 + 0.408 + 0 + 0 = 0.816$
맑음 전망에 대한 카이제곱 값을 정리하면 다음표와 같다.
| Feature | Chi-square value |
|---|---|
| Temperature | 3.414 |
| Humidity | 4.449 |
| Wind | 0.816 |
맑음 전망에서는 습도가 가장 지배적인 특성으로 결정 규칙으로 트리에 넣는다.
CHAID 트리의 두번째 단계
위 그림과 같이 맑음 전망에 대한 양쪽 습도 분기는 하나의 결정만을 갖는다. CHAID 트리는 맑고 습도가 높으면 No를 맑고 보통 습도면 Yes를 반환한다.
Outlook = Rain 분기(branch)
비 전망 분기는 여전히 Yes와 No 결정을 모두 가지고 있다. 정확한 결정을 찾기 위해 이 분기에 카이제곱 테스트를 적용해야 한다.
| Day | Outlook | Temp. | Humidity | Wind | Decision |
|---|---|---|---|---|---|
| 4 | Rain | Mild | High | Weak | Yes |
| 5 | Rain | Cool | Normal | Weak | Yes |
| 6 | Rain | Cool | Normal | Strong | No |
| 10 | Rain | Mild | Normal | Weak | Yes |
| 14 | Rain | Mild | High | Strong | No |
비 전망에서 온도 특성
이 특성은 아래와 같이 2가지 분류이다. (** 원래 온도는 Hot, Mild, Cool 3가지 분류지만, 비 전망에서는 Mild와 Cool 데이터만이 나타나고 있다.)
| Yes | No | Total | Expected | Chi-square Yes | Chi-square No | |
|---|---|---|---|---|---|---|
| Mild | 2 | 1 | 3 | 1.5 | 0.408 | 0.408 |
| Cool | 1 | 1 | 2 | 1 | 0 | 0 |
$\text{Chi-square value(Outlook=Rain|Temperature)} = 0.408 + 0.408 + 0 + 0 = 0.816$
비 전망에서 습도 특성
이 특성은 아래와 같이 2가지 분류이다.
| Yes | No | Total | Expected | Chi-square Yes | Chi-square No | |
|---|---|---|---|---|---|---|
| High | 1 | 1 | 2 | 1 | 0 | 0 |
| Normal | 2 | 1 | 3 | 1.5 | 0.408 | 0.408 |
$\text{Chi-square value(Outlook=Rain|Humidity)} = 0 + 0 + 0.408 + 0.408 = 0.816$
비 전망에서 바람 특성
이 특성은 아래와 같이 2가지 분류이다.
| Yes | No | Total | Expected | Chi-square Yes | Chi-square No | |
|---|---|---|---|---|---|---|
| Weak | 3 | 0 | 3 | 1.5 | 1.225 | 1.225 |
| Strong | 0 | 2 | 2 | 1 | 1 | 1 |
$\text{Chi-square value(Outlook=Rain|Wind)} = 1.225 + 1.225 + 1 + 1 = 4.449$
비 전망에 대한 카이제곱 값을 정리해 보자.
| Feature | Chi-square value |
|---|---|
| Temperature | 0.816 |
| Humidity | 0.816 |
| Wind | 4.449 |
바람 특성이 비 전망 분기에서의 승자이다.
CHAID 트리의 세번째 단계
위와 같이 모든 분기는 하나의 결정을 갖는 하위 데이터셋으로 구성된다. 따라서 아래와 같이 CHAID 트리를 구성할 수 있다.
CHAID 트리의 최종 형태