** 내부 동작을 이해하기 Deep Learning 알고리즘에 비해 동작 방식이 명확하게 보이니 재미를 느껴 몇가지 더 찾아서 다뤄보려고 한다. **
A Step by Step CART Decision Tree Example
알고리즘의 결정을 사람이 명확하게 읽고 이해할 수 있다면 알고리즘은 투명해 질 수 있다. 비록 딥러닝(Deep Learning)이 요즘 머신러닝(Machine Learning)의 수퍼스타일지라도 이것은 불투명한 알고리즘이기 때문에 우리는 알로리즘이 결정한 이유를 알 수 없다. 여기서 투명하게 결정되는 것을 알 수 있는 결정트리(Decision Tree) 알고르즘이 여전히 그 인기를 유지하고 있다. ID3(결정트리의 한 종류)는 정보 습득(information gain)을 사용하지만 C4.5(결정트리의 한 종류)는 분할에 대한 이익 비율(gain ratio)을 사용한다. 여기서 CART는 알고리즘을 구축하는 대체 결정트리이다. CART는 분류(classification)과 회귀(Regression) 작업 모두를 다룰 수 있다. 이 알고리즘은 분류 작업에 대한 결정 포인트를 만들기 위해 지니 인덱스(jini index)라는 새로운 지표(metric)를 사용한다. 여기서는 설계에서부터 직접 CART 결정트리 예제를 차례로 다룰 것이다.
Wizard of Oz (1939)
CART in Python
이 글에서는 CART 알고리즘에 대해 자세히 설명하고 단계별로 문제를 해결해 본다. 다른 한편으로는 단순히 CART 알고리즘을 실행하고 이것의 수학적 배경은 관심없을 수 있다.
여기에서 CART 알고리즘을 파이썬으루 구현한 것을 찾을 수 있다. 단지 몇줄만으로 CART 결정트리를 구축할 수 잇다. 이 패키지는 ID3, C4.5, CHAID, Regression Trees같은 가장 일반적인 결정트리 알고리즘을 지원한다. 또한 Random forest 같은 배깅(bagging) 방법과 gradient boosting, adaboost같은 부스팅(boosting) 방법도 지원한다.
Link
Objective
결정 규칙은 GINI index 값에 의해 나타난다.
Link
Data set
ID3에서와 동일한 데이터셋에서 진행한다. 전망(Outlook), 온도(Temperature), 습도(Humidity)와 바람(Wind) 요소에 기초한 골프 경기 결정에 대한 14가지 예가 있다.
| 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 |
Gini index
지니인덱스(gini index)는 CART에서 분류작업을 위한 지표로 각 분류(class)의 확률을 제곱하여 합산한 것으로 아래와 같은 수식으로 표현할 수 있다.
$Gini = 1 - \sum_{i=1}^n(P_i)^2$
- $n$ : 분류 수 (number of classes)
- $P_i$ : 확률 (Probability)
전망(Outlook)
전망은 범주형 특성으로 맑음(sunny), 흐림(overcast), 비(rain)이 될 수 있다. 이 전망 특성에 따라 최종 결정(decision)을 정리하면 아래와 같다.
| Outlook | Yes | No | 개수(number of instnaces) |
|---|---|---|---|
| Sunny | 2 | 3 | 5 |
| Overcast | 4 | 0 | 4 |
| Rain | 3 | 2 | 5 |
$Gini(Outlook=Sunny) = 1 - {(2 \div 5)^2 + (3 \div 5)^2} = 1-0.16-0.36 = 0.48$
$Gini(Outlook=Overcast) = 1 - {(4 \div 4)^2 + (0 \div 4)^2} = 0$
$Gini(Outlook=Rain) = 1-{(3 \div 5)^2 + (2 \div 5)^2}=1-0.36-0.16 = 0.48$
이제 전망 특성에 대한 가중치가 적용된 gini index의 합을 계산한다.
$Gini(Outlook) = (5 \div 14) \times 0.48 + (4 \div 14) \times 0 + (5 \div 14) \times 0.48 = 0.171 + 0 + 0.171 = 0.342$
온도(Temperature)
비슷하게 온도 역시 범주형 특성이고 3가지 값 - 추움(Cool), 더움(Hot), 포근함(Mild) -을 가질 수 있다. 온도 특성에 대한 결정을 요약하면 아래와 같다.
| Temperature | Yes | No | 개수(number of instnaces) |
|---|---|---|---|
| Hot | 2 | 2 | 4 |
| Cool | 3 | 1 | 4 |
| Mild | 4 | 2 | 6 |
$Gini(Temp=Hot) = 1 - {(2 \div 4)^2 + (2 \div 4)^2} = 0.5$
$Gini(Temp=Cool) = 1 - {(3 \div 4)^2 + (1 \div 4)^2} = 0.375$
$Gini(Temp=Mild) = 1 - {(4 \div 6)^2 + (2 \div 6)^2} = 0.445$
온도 특성에 대해 가중치가 적용된 gini index 합을 계산한다.
$Gini(Temp) = (4 \div 4) \times 0.5 + (4 \div 14) \times 0.375 + (6 \div 14) \times 0.445 = 0.439$
습도(Humidity)
습도는 이진 분류 특성으로 높음(high)와 보통(normal)이 될 수 있다.
| Humidity | Yes | No | 개수(number of instnaces) |
|---|---|---|---|
| High | 3 | 4 | 7 |
| Normal | 6 | 1 | 7 |
$Gini(Humidity=High)=1 - {(3 \div 7)^2 + (3 \div 4)^2} = 0.489$
$Gini(Humidity=Normal) = 1 - {(6 \div 7)^2 + (1 \div 7)^2} = 0.244$
가중치가 적용된 gini index합
$Gini(Humidity) = (7 \div 14) \times 0.489 + (7 \div 14) \times 0.244 = 0.367$
바람(Wind)
바람 또한 습도와 비슷하게 이진 분류 특성으로 약함(weak)와 강함(strong)이 될 수 있다.
| Wind | Yes | No | 개수(number of instnaces) |
|---|---|---|---|
| Weak | 6 | 2 | 8 |
| Strong | 3 | 3 | 6 |
$Gini(Wind=Weak) = 1 - {(6 \div 8)^2 + (2 \div 8)^2} = 0.375$
$Gini(Wind=Strong) = 1 = {(3 \div 6)^2 + (3 \div 6)^2} = 0.5$
$Gini(Wind) = (8 \div 14) \times 0.375 + (6 \div 14) \times 0.5 = 0.428$
Time to decide
각 특성에 대한 gini index를 계산했고 전망(outlook)의 비용(cost)가 가장 낮기 때문에 승자(winner)가 된다.
| Feature | Gini index |
|---|---|
| Outlook | 0.342 |
| Temperature | 0.439 |
| Humidity | 0.367 |
| Wind | 0.428 |
트리의 맨 꼭대기에 전망 결정(decison)을 놓는다.
첫번째 결정은 전망 특성이 될 것이다.
흐림(overcast) 리프(leaf)의 하위(sub) 데이터셋은 'yes' 결정으로만 되어 있다. 이것은 흐림 리프는 끝이라는 것을 나타낸다.
트리는 흐림 전망 리프에서 끝난다
다음 단계에서 하위 데이터셋에 같은 방식을 적용한다.
맑음 전망을 가진 데이터셋에서 온도, 습도, 바람 특성 각각에 대한 gini index를 알아야 한다.
| Day | Outlook | Temp. | Humidity | Wind | Decison |
|---|---|---|---|---|---|
| 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 |
맑음 전망에 대한 온도 Gini
| Temperature | Yes | No | 개수(number of instnaces) |
|---|---|---|---|
| Hot | 0 | 2 | 2 |
| Cool | 1 | 0 | 1 |
| Mild | 1 | 1 | 2 |
$Gini(Outlook=Sunny and Temp.=Hot) = 1 - {(1 \div 2)^2 + (2 \div 2)^2} = 0$
$Gini(Outlook=Sunny and Temp.=Cool) = 1 - {(1 \div 1)^2 + (0 \div 1)^2} = 0$
$Gini(Outlook=Sunny and Temp.=Mild) = 1 - {(1 \div 2)^2 + (1 \div 2)^2} = 0.5$
$Gini(Outlook=Sunny and Temp) = (2 \div 5) \times 0 + (1 \div 5) \times 0 + (2 \div 5) \times 0.5 = 0.2$
맑음 전망에 대한 습도 Gini
| Humidity | Yes | No | 개수(number of instnaces) |
|---|---|---|---|
| High | 0 | 3 | 3 |
| Normal | 2 | 0 | 2 |
$Gini(Outlook=Sunny and Humidity=High) = 1 - {(0 \div 3)^2 + (3 \div 3)^2} = 0$
$Gini(Outlook=Sunny and Humidity=Normal) = 1 - {(2 \div 2)^2 + (0 \div 2)^2} = 0$
$Gini(Outlook=Sunny and Humidity) = (3 \div 5) \times 0 + (2 \div 5) \times 0 = 0$
맑음 전망에 대한 바람 Gini
| Wind | Yes | No | 개수(number of instnaces) |
|---|---|---|---|
| Weak | 1 | 2 | 3 |
| Strong | 1 | 1 | 2 |
$Gini(Outlook=Sunny and Wind=Weak) = 1 - {(1 \div 3)^2 + (2 \div 3)^2} = 0.266$
$Gini(Outlook=Sunny and Wind=Strong) = 1 - {(1 \div 2)^2 + (1 \div 2)^2} = 0.2$
$Gini(Outlook=Sunny and Humidity) = (3 \div 5) \times 0.266 + (2 \div 5) \times 0.2 = 0.466$
맑음 전망에 대한 결정
전망이 맑은 경우에 대한 gini index 점수를 계산했다. 여기서 승자는 가장 낮은 값을 갖는 습도이다.
| Feature | Gini index |
|---|---|
| Temperature | 0.2 |
| Humidity | 0 |
| Wind | 0.466 |
맑음 전망의 확장으로 습도를 놓는다.
높거나 보통인 습도에 대한 하위 데이터셋
보이는 것처럼 결정은 항상 높은 습도와 맑음 전망에 대해서는 'no'이다. 반대로 보통 습도와 맑음 전망에서는 항상 'yes'로 가지(branch)가 끝난다.
높거나 보통 습도에 대한 결정
이제 비 전망에 대해서 진행해 보자.
Rain outlook
| Day | Outlook | Temp. | Humidity | Wind | Decison |
|---|---|---|---|---|---|
| 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 |
비 전망일때 온도, 습도, 바람 특성에 대한 gini index 점수를 계산한다.
비 전망에 대한 온도 Gini
| Temperature | Yes | No | 개수(number of instnaces) |
|---|---|---|---|
| Cool | 1 | 1 | 2 |
| Mild | 2 | 1 | 3 |
$Gini(Outlook=Rain and Temp.=Cool) = 1 - {(1 \div 2)^2 + (1 \div 2)^2} = 0.5$
$Gini(Outlook=Rain and Temp.=Mild) = 1 - {(2 \div 3)^2 + (1 \div 3)^2} = 0.444$
$Gini(Outlook=Rain and Temp.) = (2 \div 5) \times 0.5 + (3 \div 5) \times 0.444 = 0.466$
비 전망에 대한 습도 Gini
| Humidity | Yes | No | 개수(number of instnaces) |
|---|---|---|---|
| High | 1 | 1 | 2 |
| Normal | 2 | 1 | 3 |
$Gini(Outlook=Rain and Humidity=High) = 1 - {(1 \div 2)^2 + (1 \div 2)^2} = 0.5$
$Gini(Outlook=Rain and Humidity=Normal) = 1 - {(2 \div 3)^2 + (1 \div 3)^2} = 0.444$
$Gini(Outlook=Rain and Humidity) = (2 \div 5) \times 0.5 + (3 \div 5) \times 0.444 = 0.466$
비 전망에 대한 바람 Gini
| Wind | Yes | No | 개수(number of instnaces) |
|---|---|---|---|
| Weak | 3 | 0 | 3 |
| Strong | 0 | 2 | 2 |
$Gini(Outlook=Rain and Wind=Weak) = 1 - {(3 \div 3)^2 + (0 \div 3)^2} = 0$
$Gini(Outlook=Rain and Wind=Strong) = 1 - {(0 \div 2)^2 + (2 \div 2)^2} = 0$
$Gini(Outlook=Rain and Wind) = (3 \div 5) \times 0 + (2 \div 5) \times 0 = 0$
비 전망에 대한 결정
비 전망에서는 바람 특성이 최소값이므로 승자이다.
| Feature | Gini index |
|---|---|
| Temperature | 0.466 |
| Humidity | 0.466 |
| Wind | 0 |
비 전망 가지에 바람 특성을 놓고 새로운 하위 데이터셋을 관찰한다.
비 전망에서 약하거나 강한 바람의 하위 데이터셋
보이는 것과 같이 바람이 약할때는 항상 'yes'이고 강할때는 'no'이다. 따라서 가지가 끝난다.
CART 알고리즘에 의해 만드러진 결정 트리의 최종 형태
특성 중요도(Feature Importance)
결정 트리는 알고리즘을 자연스럽게 설명 가능하고 해석 가능하다. 게다가 모델이 어떻게 동작하는지 이해하는 것은 물론 특성 중요도 값을 찾을 수 있다.
Link