Decision Tree + C4.5알고리즘

Decision Tree + C4.5알고리즘

c4.5 특징

1. 수치형 자료를 처리한다.

2. 불완전한 데이터를 처리한다.

3; 가지치기로 과적합을 해결한다.

GainRatio < 참고1, 참고2>

Information Gain의 문제점은 많은 측정값을 가진 속성으로 편향된다는 것이다. ID_CODE와 Outlook의 Information Gain을 구해보자.

Gain(Outlook) = E(Play) - E(Play, OutLook) = 0.94 - 0.69

Gain(ID_CODE) = E(Play) - E(Play, ID_CODE) = 0.94 - 0

ID_CODE	Outlook	Play?
1	sunny	No
2	sunny	No
3	overcast	Yes
4	rain	Yes
5	rain	Yes
6	rain	No
7	overcast	Yes
8	sunny	No
9	sunny	Yes
10	rain	Yes
11	sunny	Yes
12	overcast	Yes
13	overcast	Yes
14	rain	No

Gain Ratio는 Gain을 split info로 나누어준다. 수식을 보자.

SplitInfo에 대한 설명은 번역하기 애매해서 원문 그대로 적겠다.

The split information value represents the potential information generated by splitting the training data set D into v partitions, corresponding to v outcomes on attribute A.

Gain(A)는 이전 글에서 Gain을 구하는 방법과 똑같다. (예 : E(Play) - (Play, OutLook))

Gain(OutLook) = 0.25

SplitInfo는 Sunny 항목 5개, Overcast 4개,  Rain 5개로,

GainRatio(OutLook) = 0.1585, GainRatio(ID_CODE) = 0.25이다.  Gain(Outlook) = 0.25, Gain(ID_CODE) =0.97보다 GainRatio가 더 변별력(?) 있다. 하지만 GainRatio(ID_CODE)가 가장 높은 수치이다. 이런 경우 직접 속성을 제거해야한다...ㅠㅠ;;

수치형 자료의 엔트로피 계산 

Humidity	Play?
85	No
90	No
78	Yes
96	Yes
80	Yes
70	No
65	Yes
95	No
70	Yes
80	Yes
70	Yes
90	Yes
75	Yes
80	No

속성을 정렬(Sort)한다.  

Humidity = {65, 70, 75, 78, 80, 85, 90, 95}

각각 수치별로 Gain을 구한다.

		Humidity
		X<=65	X>65
PLAY	YES	1	8
	NO	0	5

 

이런식으로 모두 구하면 

80을 기준으로 나누는게 가장 큰 Entropy를 가지므로,  Gain(T, Humidity)는 0.102가 된다.

불완전한 데이터 처리 < 참고 >

Outlook	Play?
sunny	No
?	No
?	Yes
rain	Yes
rain	Yes
rain	No
overcast	Yes
?	No
?	Yes
?	Yes
?	Yes
overcast	Yes
overcast	Yes
rain	No

엔트로피 계산은 누락값을 제외하고 계산한다.

Gain은 속성의 누락값을 제외한 비율로 가중된다.

SplitInfo는 누락값을 하나의 항목으로 생각하고 계산하면 된다.

가지치기 ( pessimistic pruning ) < 참고 >

pessimistic pruning은 통계적 보정방법을 사용하며 에러를 측정하기위해 Validation set과 test set을 필요로하지 않는다. 

상위 신뢰한계를 사용하여 오류를 추정한다.

z-score부분은 나중에 보충해야겠다.ㅠㅠ

그림으로 이해하자.