Decision Tree + ID3알고리즘

Decision Tree(결정트리) 

어떤 항목에 대한 관측값과 목표값을 연결시켜주는 예측 모델로써 결정 트리를 사용한다. 

장점 

1. 결과를 해석하고 이해하기 쉽다.간략한 설명만으로 결정 트리를 이해하는 것이 가능하다.

2. 자료를 가공할 필요가 거의 없다.다른 기법들의 경우 자료를 정규화하거나 임의의 변수를 생성하거나 값이 없는 변수를 제거해야 하는 경우가 있다.

3. 수치 자료와 범주 자료 모두에 적용할 수 있다.

4. 대규모 데이터 세트도 잘 동작한다.

한계 

1. 휴리스틱 기법을 기반하기 때문에 최적 결정트리라고 보장할 수 없다.

2. 너무 복잡한 결정트리를 만들 수 있다.

3. 약간의 차이에 따라 (레코드의 개수의 약간의 차이) 트리의 모양이 많이 달라질 수 있다. 두 변수가 비슷한 수준의 정보력을 갖는다고 했을 때, 약간의 차이에 의해 다른 변수가 선택되면 이 후의 트리 구성이 크게 달라질 수 있다.

알고리즘 : ID3, C4.5, CART 등이 있다.

ID3알고리즘 (범주형 자료만 분류 가능)

1. 루트노드 생성

2. 현재 트리에서 모든 단말노드에 대해서 아래를 반복한다.

A. 해당 노드의 샘플들이 같은 클래스이면, 해당 노드는 단말노드가 되고, 해당 클래스로 레이블을 부여

B. 더 이상 사용할 수 있는 속성이 없으면 수행 종료

C. Information Gain이 높은 속성을 선택해서 노드를 분할

Entropy (평균 정보량)  

출력값을 나타내기 위해 필요한 평균 비트 수

확률분포에 대한 기대값

공이 8개가 있다. 

여기서 어떤 하나의 공을 뽑을 확률은 1/8이고,  이 때 정보량은 3(bit)이다. 어떤 공인지 찾기 위해 3번의 질문이 필요하다는 의미이다. 

문제를  바꿔서, 빨간공이 3개,  파란공이 5개 있을 경우의 엔트로피를 계산해보자.

이 때의 엔트로피는 약 0.953이다. 정보량에 해당 공을 뽑을 확률을 한 번 더 곱해줘야 한다. 

즉 가중평균으로 엔트로피를 구한다.

엔트로피 참고자료 : http://www.aistudy.com/control/information_theory.htm

Information Gain

원래의 엔트로피와 세부 클래스로 분할된 후의 엔트로피의 차이이다.

information Gain이 클수록 분류하기 좋다는 것을 의미

ID3알고리즘은 Information Gain를 사용하여 노드를 결정한다.

직접 Information Gain을 계산해보자. Outlook, Temp, Humidity, Windy 등을 보고 언제 테니스를 치는지에 대해 분류하는 예제이다.

Outlook	Temperature	Humidity	Windy	Play?
sunny	hot	high	FALSE	No
sunny	hot	high	TRUE	No
overcast	hot	high	FALSE	Yes
rain	mild	high	FALSE	Yes
rain	cool	normal	FALSE	Yes
rain	cool	normal	TRUE	No
overcast	cool	normal	TRUE	Yes
sunny	mild	high	FALSE	No
sunny	cool	normal	FALSE	Yes
rain	mild	normal	FALSE	Yes
sunny	mild	normal	TRUE	Yes
overcast	mild	high	TRUE	Yes
overcast	hot	normal	FALSE	Yes
rain	mild	high	TRUE	No

Play의 엔트로피 계산

E(Play, Outlook)

		Play
		Yes	No	Total
Outlook	sunny	3	2	5
	overcast	4	0	4
	rain	3	2	5

E(Play,Temperature )

		Play
		Yes	No	Total
Temp..	hot	2	2	4
	mild	4	2	6
	cool	3	1	4

E(Play, Humidity)

		Play
		Yes	No	Total
Humidity	high	3	4	7
	normal	6	1	7

E(Play, Windy)

		Play
		Yes	No	Total
Windy	TRUE	3	3	6
	FALSE	6	2	8

이제 Information Gain을 구해보자.

Infomation Gain이 가장 큰 것은 Outlook이다. Outlook으로  분류하자.

이제 Sunny에서 분류를 하자.

Outlook	Temperature	Humidity	Windy	Play?
sunny	hot	high	FALSE	No
sunny	hot	high	TRUE	No
sunny	mild	high	FALSE	No
sunny	cool	normal	FALSE	Yes
sunny	mild	normal	TRUE	Yes

Humidity를 선택할 경우 Information Gain이 가장크다. Humidity를 가지로 선택한다.

이제 트리는 다음과 같은 모양을 가지게 된다.

Humidity에 속하는 클래스들은 모드 같은 레코드를 가지므로 Humidity에서 더 이상 가지를 만들지 않는다.

Outlook	Temperature	Humidity	Windy	Play?
sunny	hot	high	FALSE	No
sunny	hot	high	TRUE	No
sunny	mild	high	FALSE	No

Outlook	Temperature	Humidity	Windy	Play?
sunny	cool	normal	FALSE	Yes
sunny	mild	normal	TRUE	Yes

이제 Outlook에서 Overcast를 선택했을 때를 보자. 이 경우도 Play가 모두 Yes로 같은 class를 가지므로 넘어간다.

Outlook	Temperature	Humidity	Windy	Play?
overcast	hot	high	FALSE	Yes
overcast	cool	normal	TRUE	Yes
overcast	mild	high	TRUE	Yes
overcast	hot	normal	FALSE	Yes

트리에 가능한 가지는 Temperature, Windy 두 속성이 남았다.

Outlook	Temperature	Windy	Play?
rain	mild	FALSE	Yes
rain	cool	FALSE	Yes
rain	cool	TRUE	No
rain	mild	FALSE	Yes
rain	mild	TRUE	No

Rainy를 선택했을 때, Windy가 가지가 된다. 그리고 Windy의 속성에 따라 Play가 모두 같은 class를 가지므로 더 이상 가지를 만들지 않는다.

더 뻗어나갈 가지가 없으므로 트리는 아래 그림으로 완성된다.