A Step by Step ID3 Decision Tree Example

원본 링크

A Step by Step ID3 Decision Tree Example

결정 트리(Decison Tree)알고리즘은 원시 데이터(raw data)를 트리를 만드는 결정 기반 규칙으로 변형시킨다. 여기서 ID3은 가장 일반적인 결정트리 알고리즘 중 하나이다. 우선 이것은 1986년에 소개되었고 Iterative Dichotomiser(반복적으로 둘로 나누다)의 머리글자이다.

Sandra Bullock, Premonition (2007)

우선 둘로 나누기는 두개의 완전히 반대인 것으로 나눈다는 것이다. 그래서

• 알고리즘은 반복적으로 가장 지배적인 속성과 나머지가 트리를 만드는 두 그룹으로 속성을 나눈다.
• 그리고 각 속성에 대한 엔트로피(entropy)와 정보 이익(information gain)을 계산한다. 이런 방법으로 가장 지배적인 속성을 찾을 수 있다.
• 그리고 나서 가장 지배적인 하나를 결정 노드(decision node)로 트리에 집어 넣는다.
• 그 후 엔트로피와 이익 점수는 다른 속성사이에서 다시 계산된다.
• 따라서 다음 가장 지배적인 속성이 찾을 수 있다.

마지막으로 이 절차를 해당 가지에 대한 결정에 도달할 때 까지 계속한다. 이렇기 때문에 Iterative Dichotomiser라고 불린다.

ID3 in Python

이 글에서는 ID3 알고리즘에 대해 깊이 설명하고 단계별로 문제를 해결해 본다.
여기에서 ID3를 파이썬으로 구현한 소스를 볼 수 있다.

Objective

결정 규칙(Decision rule)은 엔트로피(entropy)와 정보 이익(information gain) 쌍의 특성에 기초하여 찾는다.

Data set

데이터셋으로 아래 표는 이전 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

ID3 알고리즘을 아래와 같이 요약할 수 있다.

• $Entropy(S) = \sum-p_i \cdot \log_2p_i$

• $Gain(S, A) = Entropy(S) - \sum[p(S|A) \cdot Entropy(S|A)]$

Entropy

우선 엔트로피를 계산해야 한다. 결정 컬럼(decison column)은 14가지 예로 구성되고 2개의 레이블 - 'yes', 'no'를 포함한다. 여기서 9가지는 'yes'이고 5가지는 'no'이다.

• $Entropy(Decison) = -p(Yes) \cdot \log_2p(Yes) - p(No) \cdot \log_2p(No)$

• $Entropy(Decison) = -(9 \div 14) \cdot \log_2(9 \div 14) - (5 \div 14) \cdot \log_2(5 \div 14) = 0.940$

이제, 결정을 위한 가장 지배적인 인자를 찾아야 한다.

결정에 있어 바람(Wind) 인자

• $Gain(Decision, Wind) = Entropy(Decision) - \sum[p(Decision|Wind) \cdot(Decision|Wind)]$

바람 속성은 Weak와 Strong 두가지 레이블을 갖는다. 이를 수식에 반영한다.

• $Gain(Decison, Wind) = Entropy(Decision)$
  $- [p(Decision|Wind=Weak) \cdot Entropy(Decision|Wind=Weak)]$
  $- [p(Decision|Wind=Strong) \cdot Entropy(Decision|Wind=Strong)]$

이제는 (Decision|Wind=Weak)와 (Decision|Wind=Strong)을 계산해야 한다.

결정에 있어 약한(Weak) 바람 인자

Day	Outlook	Temp.	Humidity	Wind	Decision
1	Sunny	Hot	High	Weak	No
3	Overcast	Hot	High	Weak	Yes
4	Rain	Mild	High	Weak	Yes
5	Rain	Cool	Normal	Weak	Yes
8	Sunny	Mild	High	Weak	No
9	Sunny	Cool	Normal	Weak	Yes
10	Rain	Mild	Normal	Weak	Yes
14	Rain	Mild	High	Strong	No

약한 바람에 대해서는 8개가 있다. 2개의 결정은 'No'이고 나머지 6개는 'Yes'이다.

• $Entropy(Decision|Wind=Weak) = -p(No) \cdot \log_2p(No) - p(Yes) \cdot \log_2p(Yes)$

• $Entropy(Decision|Wind=Weak) = -(2 \div 8) \cdot \log_2(2 \div 8) - (6 \div 8) \cdot \log_2(6 \div 8)$

>만약 분류에 대한 인스턴수가 0이고 전체 인스턴스 수가 n이라면 $-(0 \div n) \cdot \log_2(0 \div n)$을 계산해야만 한다. 여기서 $\log(0)$는 $- \infin$이므로 $0 \times \infin$을 계산할 수 없다. 이것은 결정 트리 어플리케이션에서 자주 나타나는 특수한 경우이다. 비록 컴파일러가 이러한 연산을 할 수 없더라도 우리는 미적분으로 계산할 수 있다. 만약 이러한 수식을 계산하는 방법이 궁금하다면 여기를 참고하자.

결정에 있어 강한(Strong) 바람 인자

Day	Outlook	Temp.	Humidity	Wind	Decision
2	Sunny	Hot	High	Strong	No
6	Rain	Cool	Normal	Strong	No
7	Overcast	Cool	Normal	Strong	Yes
11	Sunny	Mild	Normal	Strong	Yes
12	Overcast	Mild	High	Strong	Yes
14	Rain	Mild	High	Strong	No

여기에는 강한 바람에 대한 것이 6개 있다. 결정은 두개의 동일한 부분으로 나누어 진다.

• $Entropy(Decision|Wind=Strong) = -p(No) \cdot \log_2p(No) - p(Yes) \cdot \log_2(Yes)$
• $Entropy(Decision|Wind+Strong) = -(3 \div 6) \cdot \log_2p(3 \div 6) - (3 \div 6) \cdot \log_2(3 \div 6) = 1$

이제 Gain(Decision, Wind)식으로 돌아가보자.

• $Gain(Decision, Wind) = Entropy(Decision)$
  $- [p(Decision|Wind=Weak) \cdot Entorpy(Decision|Wind=Weak)]$
  $- [p(Decision|Wind=Strong) \cdot Entorpy(Decision|Wind=Strong)]$
  $= 0.940 - [(8 \div 14) \cdot 0.811] - [(6 \div 14) \cdot 1] = 0.048$

바람(wind) 컬럼에 대한 계산이 끝났다. 이제 결정에 가장 지배적인 요소를 찾기 위해 다른 컬럼에 동일한 계산을 적용한다.

결정에 있어 다른 인자들

다른 컬럼에 유사한 계산을 적용한다.

• $Gain(Decison, Outlook) = 0.246$
• $Gain(Decision, Temperature) = 0.029$
• $Gain(Decision, Humidity) = 0.151$

보이는 바와 같이 결정에서 전망(outlook) 인자가 가장 높은 점수이다. 따라서 전망 결정이 트리의 루트 노드(root node)가 된다.

트리의 루트 결정

이제 전망 속성의 커스텀 서브셋에 대한 데이터셋을 테스트해야 한다.

결정에서 흐림 전망(Overcast Outlook)

기본적으로 결정은 전망이 흐림이라면 항상 'Yes'이다.

Day	Outlook	Temp.	Humidity	Wind	Decision
3	Overcast	Hot	High	Weak	Yes
7	Overcast	Cool	Normal	Strong	Yes
12	Overcast	Mild	High	Strong	Yes
13	Overcast	Hot	Normal	Weak	Yes

결정에서 맑음 전망(Sunny 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

여기서는 맑음 전망이 5개가 있다. 결정은 'No'가 $3 \div 5$, 'Yes'가 $2 \div 5$의 확률이다.

• $Gain(Outlook=Sunny|Temperature) = 0.570$
• $Gain(Outlook=Sunny|Humidity) = 0.970$
• $Gain(Outlook=Sunny|Wind) = 0.019$

이제 습도가 맑음 전망일 때 가장 높은 점수이기 때문에 결정이 된다.

여기서 결정은 습도가 높을때(High) 항상 'No'가 된다.

Day	Outlook	Temp.	Humidity	Wind	Decision
1	Sunny	Hot	High	Weak	No
2	Sunny	Hot	High	Strong	No
8	Sunny	Mild	High	Weak	No

반대로, 습도가 보통이면 결정은 항상 'Yes'이다.

Day	Outlook	Temp.	Humidity	Wind	Decision
9	Sunny	Cool	Normal	Weak	Yes
11	Sunny	Mild	Normal	Strong	Yes

이것은 맑음 전망일 때 습도를 확인해하고 결정해야한다는 것을 나타낸다.

결정에서 비 전망(Rain Outlook)

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

• $Gain(Outlook=Rain|Tempreature) = 0.01997309402197489$
• $Gain(Outlook=Rain|Humidity) = 0.01997309402197489$
• $Gain(Outlook=Rain|Wind) = 0.9709505944546686$

여기서는 비 전망일때 바람이 가장 높은 점수이다. 따라서 비 전망일때 두번째 레벨에서 비 속성을 확인해야 한다.

바람이 약하고 비 전망일 꼉우 결정은 항상 'Yes'인 것으로 나타난다.

Day	Outlook	Temp.	Humidity	Wind	Decision
4	Rain	Mild	High	Weak	Yes
5	Rain	Cool	Normal	Weak	Yes
10	Rain	Mild	Normal	Weak	Yes

게다가 바람이 강하고 비 전망이면 결정은 항상 'no'이다.

Day	Outlook	Temp.	Humidity	Wind	Decision
6	Rain	Cool	Normal	Strong	No
14	Rain	Mild	High	Strong	No

이렇게 결정 트리 생성이 끝났다. 아래와 같이 결정을 위한 규칙을 사용할 수 있다.

결정 트리 최종 버전