A Step By Step C4.5 Decision Tree Example
결정 트리는 데이터 과학 분야에서 여전히 뜨거운 주제이다. 여기서 ID3가 가장 일반적인 전통적 의사 결정 트리(decison tree) 알고리즘이지만 ID3는 병목현상이 있다. 속성들은 범주형 값(nominal values)이어야 하고 데이터셋에는 손실 데이터가 없어야 한다. 그리고 알고리즘이 오버피팅(overfitting)되는 경향이 있다. 여기서 ID3의 창시자인 Ross Quinlan이 이러한 병목현상을 일부 개선하여 C4.5라는 새로운 알고리즘을 만들었다. 이제 알고리즘은 연속적인 데이터를 포함하는 좀 더 일반화된 모델을 만들 수 있고 손실 데이터를 다룰 수 있다. 게다가 Weka (위키백과 : 웨카는 자바로 개발된 기계 학습 소프트웨어 제품군으로, 뉴질랜드 와이카토 대학교에서 개발되었다. GNU 일반 공중 사용 허가서로 허가된 자유 소프트웨어이다.) 같은 몇몇 리소스가 이 알고리즘을 J48로 명명했다. 실제로 이것은 C4.5 릴리즈 8의 재구현을 나타낸다.
Groot appears in Guardians of Galaxy and Avengers Infinity War
C4.5 in Python
이 글에서는 C4.5 알고리즘에 대해 더 자세히 설명하고 단계적으로 문제를 해결해 본다. 여기에서 C4.5 알고리즘의 파이썬 구현을 찾을 수 있다.
Objective
결정 규칙(decision rule)은 엔트로피(entropy)와 각 특성의 정보 이익 비율 쌍(information gain ratio pair)로 결정된다. 결정 트리의 각 레벨에서 최대 이익 비율(gain ratio)를 갖는 특성이 결정 규칙이 된다.
Data set
아래 데이터셋으로 결정 테이블(decision table)을 만들 것이다. 이 데이터셋은 이전 14일동안 외부에서 테니스 경기를 하기 위한 의사결정 요소(decision making factor)에 대한 정보이다. 데이터셋은 ID3에서 사용한 것과 유사하지만 차이점은 온도(Temperature)와 습도(Humidity) 컬럼이 범주형 대신 연속적인 값을 갖는다는 것이다.
| Day | Outlook | Temp. | Humidity | Wind | Decision |
|---|---|---|---|---|---|
| 1 | Sunny | 85 | 85 | Weak | No |
| 2 | Sunny | 80 | 90 | Strong | No |
| 3 | Overcast | 83 | 78 | Weak | Yes |
| 4 | Rain | 70 | 96 | Weak | Yes |
| 5 | Rain | 68 | 80 | Weak | Yes |
| 6 | Rain | 65 | 70 | Strong | No |
| 7 | Overcast | 64 | 65 | Strong | Yes |
| 8 | Sunny | 72 | 95 | Weak | No |
| 9 | Sunny | 69 | 70 | Weak | Yes |
| 10 | Rain | 75 | 80 | Weak | Yes |
| 11 | Sunny | 75 | 70 | Strong | Yes |
| 12 | Overcast | 72 | 90 | Strong | Yes |
| 13 | Overcast | 81 | 75 | Weak | Yes |
| 14 | Rain | 71 | 80 | Strong | No |
ID3 예제에서 했던 것을 할 것이다. 우선, 전체 엔트로피(global entropy)를 계산한다. 'Yes'결정 9개와 'No' 결정 5개로 총 14개의 옵져베이션(Observation, Data points (rows) in the dataset.) 이 있다.
$Entropy(Decision) = \sum_{i=1}^n-p_i \cdot \log_2p_i$
$= -p(Yes) \cdot \log_2p(Yes) - p(No) \cdot \log_2p(No)$
$= -(9 \div 14) \cdot \log_2(9 \div 14) - (5 \div 14) \cdot \log_2(5 \div 14) = 0.940$
ID3 알고리즘에서 각 특성에 대한 이익(gain)을 계산했다. 여기서는 이익대신 이익 비율(gain ratio)를 계산한다.
$Gain(S, A) = Entropy(S) - \sum[p(S|A) \cdot Entropy(S|A)]$
$GainRatio(A) = Gain(A) \div SplitInfo(A)$
$SplitInfo(A) = -\sum(\frac{|D_j|}{|D|} \times \log_2\frac{|D_j|}{|D|})$
$Gain(S, A) = Entropy(S) - \sum[p(S|A) \cdot Entropy(S|A)]$
$GainRatio(A) = Gain(A) \div SplitInfo(A)$
$SplitInfo(A) = -\sum(\frac{|D_j|}{|D|} \times \log_2\frac{|D_j|}{|D|})$
바람 속성(Wind Attribute)
바름은 범주 속성으로 약함(weak)와 강함(Strong) 값을 갖을 수 있다.
$Gain(Decision, Wind) = Entropy(Decision) - \sum(p(Decision|Wind) \cdot Entropy(Decision|Wind))$
$Gain(Decision, Wind) = Entropy(Decision)$
$-[p(Decision|Wind=Weak) \cdot Entropy(Decision|Wind=Weak)]$
$-[p(Decision|Wind=Strong) \cdot Entory(Decision|Wind=Strong)]$
8개의 약한 바람이 있고 그중 2개는 'No', 6개는 'Yes'이다.
$Entropy(Decision|Wind=Weak) = -p(No) \cdot \log_2p(No) - p(Yes) \cdot \log_2p(Yes)$
$=-(2 \div 8) \cdot \log_2(2 \div 8) - (6 \div 8) \cdot \log_2(6 \div 8) = 0.811$$Entropy(Decision|Wind=Strong) = -(3 \div 6) \cdot \log_2(3 \div 6) - (3 \div 6) \cdot \log_2(3 \div 6) = 1$
$Gain(Decision, Wind) = 0.940 - (8 \div 14) \cdot (0.8411) - (6 \div 14) \cdot (1) = 0.940 - 0.463 - 0.428 = 0.049$
약한 바람이 8번, 강한 바람이 6번 있다.
$SplitInfo(Decision, Wind) = -(8 \div 14) \cdot \log_2(8 \div 14) - (6 \div 14) \cdot \log_2(6 \div 14) = 0.461 + 0.524 = 0.985$
$GainRatio(Decision, Wind) = Gain(Decision, Wind) \div SplitInfo(Decision, Wind)$
$=0.049 \div 0.985 = 0.049$
전망 속성(Outlook Attribute)
전망은 범주형 속성으로 맑음(sunny), 흐림(overcast), 비(rain)값이 가능하다.
$Gain(Decision, Outlook) = Entropy(Decision) - \sum(p(Decision|Outlook) \cdot Entropy(Decision|Outlook))$
$Gain(Decision, Outlook) = Entropy(Decision)$
$-p(Decision|Outlook) \cdot Entropy(Decision|Outlook=Sunny)$
$-p(Decision|Outlook) \cdot Entropy(Decision|Outlook=Overcast)$
$-p(Decision|Outlook) \cdot Entropy(Decision|Outlook=Rain)$
맑음의 경우 3개의 'No'와 2개의 'Yes'로 총 5개가 있다.
흐림의 경우 4개 모두 'Yes'이다.
비의 경우 2개의 'No'와 3개의 'Yes'로 총 5개가 있다.
$Entropy(Decision|Outlook=Sunny) = -p(No) \cdot \log_2p(No) - p(Yes) \cdot \log_2p(Yes)$
$= -(3 \div 5) \cdot \log_2(3 \div 5) - (2 \div 5) \cdot \log_2(2 \div 5) = 0.441 + 0.528 = 0.970$
$Entropy(Decision|Outlook=Overcast) = -(0 \div 4) \cdot \log_2(0 \div 4) - (4 \div 4) \cdot \log_2(4 \div 4) = 0$
$Entropy(Decision|Outlook=Rain) = -(2 \div 5) \cdot \log_2(2 \div 5) - (3 \div 5) \cdot \log_2(3 \div 5) = 0.970$
$Gain(Decision, Outlook) = 0.940 - (5 \div 14) \cdot (0.970) - (4 \div 14) \cdot (0) - (5 \div 14) \cdot (0.970) = 0.246$
$SplitInfo(Decision, Outlook) = -(5 \div 14) \cdot \log_2(5 \div 14) - (4 \div 14) \cdot \log_2(4 \div 14) - (5 \div 14) \cdot \log_2(5 \div 14) = 1.577$
$GainRatio(Decision, Outlook) = Gain(Decision, Outlook) \div SplitInfo(Decision, Outlook) = 0.246 \div 1.577 = 0.155$
습도 속성(Humidity Attribute)
습도는 연속적 속성으로 연속적인 값을 범주형으로 변환해야 한다. C4.5는 임계치 값(threshold)으로 이진 분류를 수행한다. 임계치는 해당 속성에 대해 최대 이익을 제공하는 값이어야 한다. 이제 습도 속성을 살펴보자. 우선, 습도값을 오름차순으로 정렬한다.
| Day | Humidity | Decision |
|---|---|---|
| 7 | 65 | Yes |
| 6 | 70 | No |
| 9 | 70 | Yes |
| 11 | 70 | Yes |
| 13 | 75 | Yes |
| 3 | 78 | Yes |
| 5 | 80 | Yes |
| 10 | 80 | Yes |
| 14 | 80 | No |
| 1 | 85 | No |
| 2 | 90 | No |
| 12 | 90 | Yes |
| 8 | 95 | No |
| 4 | 96 | Yes |
이제 모든 습도값을 반복하여 데이터셋을 현재 값보다 작거나 같은 인스턴스와 현재 값보다 큰 인스턴스 두 부분으로 분리한다. 매 단계에서 이익과 이익비율을 계산한다. 이익을 최대화하는 값이 임계치가 된다.
습도에 대한 임계치로써 65를 점검해 보자.
$Entropy(Decision|Humidity<=65) = -p(No) \cdot \log_2p(No) - p(Yes) \cdot \log_2p(Yes)$
$= -(0 \div 1) \cdot \log_2(0 \div 1) - (1 \div 1) \cdot \log_2(1 \div 1) = 0$
$Entropy(Decision|Humidity>65) = -(5 \div 13) \cdot \log_2(5 \div 13) - (8 \div 13) \cdot \log_2(8 \div 13) = 0.530 + 0.431 = 0.961$
$Gain(Decision, Humidity <> 65) = 0.940 - (1 \div 14) \cdot 0 - (13 \div 14) \cdot (0.941) = 0.048$
*위의 상태는 65보다 작거나 같고 65보다 큰 것에 대한 결정트리의 분가가 무엇인지를 나타낸다. 이것은 습도가 65와 같지 않다는 것을 나타내느 것은 아니다!
$SplitInfo(Decision, Humidity<>65) = -(1 \div 14) \cdot \log_2(1 \div 14) - (13 \div 14) \cdot \log_2(13 \div 14) = 0.371$
$GainRatio(Decision, Humidity<>65) = 0.126$
이번에는 임계치 70으로 확인해보자.
$Entropy(Decision|Humidity<=70) = -(1 \div 4) \cdot \log_2(1 \div 4) - (3 \div 4) \cdot \log_2(3 \div 4) = 0.811$
$Entropy(Decision|Humidity=>70) = -(4 \div 10) \cdot \log_2(4 \div 10) - (6 \div 10) \cdot \log_2(6 \div 10) = 0.970$
$Gain(Decision|Humidity<>70) = -(4 \div 14) \cdot (0.811) - (10 \div 14) \cdot (0.970) = 0.940 - 0.231 - 0.692 = 0.014$
$SplitInfo(Decision|Humidity<>70) = -(4 \div 14) \cdot \log_2(4 \div 14) - (10 \div 14) \cdot \log_2(10 \div 14) = 0.863$
$GainRatio(Decision|Humidity<>70) = 0.016$
임계치 75로 확인해 보자.
$Entropy(Decision|Humidity<=75) = -(1 \div 5) \cdot \log_2(1 \div 5) - (4 \div 5) \cdot \log_2(4 \div 5) = 0.721$
$Entropy(Decision|Humidity=>75) = -(4 \div 9) \cdot \log_2(4 \div 9) - (5 \div 9) \cdot \log_2(5 \div 9) = 0.991$
$Gain(Decision|Humidity<>75) = -(5 \div 14) \cdot (0.721) - (9 \div 14) \cdot (0.991) = 0.940 - 0.2575 - 0.637 = 0.045$
$SplitInfo(Decision|Humidity<>70) = -(5 \div 14) \cdot \log_2(5 \div 14) - (9 \div 14) \cdot \log_2(9 \div 14) = 0.940$
$GainRatio(Decision|Humidity<>70) = 0.047$
이런식으로 이익(gain)이 최대인 값을 찾는다.
Gain(Decision, Humidity <> 78) =0.090, GainRatio(Decision, Humidity <> 78) =0.090
Gain(Decision, Humidity <> 80) = 0.101, GainRatio(Decision, Humidity <> 80) = 0.107
Gain(Decision, Humidity <> 85) = 0.024, GainRatio(Decision, Humidity <> 85) = 0.027
Gain(Decision, Humidity <> 90) = 0.010, GainRatio(Decision, Humidity <> 90) = 0.016
Gain(Decision, Humidity <> 95) = 0.048, GainRatio(Decision, Humidity <> 95) = 0.128
여기서 임계치 96은 습도가 96보다 클 수 없기 때문에 제외하였다.
보이는 것처럼 습도에 대해 임계치가 80일 때 이익이 최대이다. 이것은 결정트리내 분기를 생성하기 위해 다른 범주형 속성과 습도 80에 비교해야 한다는 것을 의미한다.
온도 특성 역시 연속적이다. 모든 분할 가능한 지점에서 온도에 이진 분류를 적용해보면 이익과 이익비율 모두에 대해 최고인 결정 규칙은 다음과 같다.
- Gain(Decision, Temperature <> 83) = 0.113, GainRatio(Decision, Temperature<> 83) = 0.305
계산한 이익과 이익비율을 정리해보자. 전망 속성은 최대 이익과 이익비율 모두를 제공한다. 이는 결정트리의 루트에 전망 결정을 놓아야 한다는 의미이다.
| Attribute | Gain | GainRatio |
|---|---|---|
| Wind | 0.049 | 0.049 |
| Outlook | 0.246 | 0.155 |
| Humidity<>80 | 0.101 | 0.107 |
| Temperature<>83 | 0.113 | 0.305 |
만약 이익 지표(metric)를 사용한다면 전망이 가장 높은 이익값을 갖기 때문에 루트노드(root node)가 된다. 반대로 이익비율 지표를 사용하면 온도가 가장 높은 이익비율을 갖기 때문에 루트노드가 된다. 여기서는 ID3와 유사한 이익을 사용한다. 별도로 이익 비율로 C4.5 결정트리도 만들어 보길 바란다.
이후에는 ID3와 유사한 단계를 적용하여 결정 트리를 만든다. 전망이 루트 노드가 된다.
이제 다른 전망 형태에 대한 결정을 살펴보자.
Outlook = Sunny
80보다 큰 값과 80보다 작거나 같은 값으로 습도를 나눴다. 놀랍게도 전망이 맑을 때 80보다 습도가 높다면 결정은 'No'이다. 비슷하게 맑음 전망에서 80보다 작거나 같은 습도라면 결정은 'Yes'이다.
| day | Outlook | Temp. | Hum.>80 | Wind | Decision |
|---|---|---|---|---|---|
| 1 | Sunny | 85 | Yes | Weak | No |
| 2 | Sunny | 80 | Yes | Strong | No |
| 8 | Sunny | 72 | Yes | Weak | No |
| 9 | Sunny | 69 | No | Weak | Yes |
| 11 | Sunny | 75 | No | Strong | Yes |
Outlook = Overcast
전망이 흐리다면, 온도, 습도, 바람은 상관없다. 결정은 항상 'Yes'이다.
| day | Outlook | Temp. | Hum.>80 | Wind | Decision |
|---|---|---|---|---|---|
| 3 | Overcast | 83 | No | Weak | Yes |
| 7 | Overcast | 64 | No | Strong | Yes |
| 12 | Overcast | 72 | Yes | Strong | Yes |
| 13 | Overcast | 81 | No | Weak | Yes |
Outlook = Rain
아래에서 보이는 것 처럼 바람이 약하면 결정은 'Yes'이고 강하면 'No'이다.
| day | Outlook | Temp. | Hum.>80 | Wind | Decision |
|---|---|---|---|---|---|
| 4 | Rain | 70 | Yes | Weak | Yes |
| 5 | Rain | 68 | No | Weak | Yes |
| 6 | Rain | 65 | No | Strong | No |
| 10 | Rain | 75 | No | Weak | Yes |
| 14 | Rain | 71 | No | Strong | No |
최종적인 결정 테이블의 형태는 다음과 같다.
C4.5로 생성한 결정 트리