Notice
Recent Posts
Recent Comments
Link
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
Archives
Today
Total
관리 메뉴

이지훈님의 블로그

Decision Tree + C4.5알고리즘 본문

ML

Decision Tree + C4.5알고리즘

개발자입니다. 2017. 7. 3. 21:27

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부분은 나중에 보충해야겠다.ㅠㅠ

그림으로 이해하자.
















'ML' 카테고리의 다른 글

Naive Bayesian Classification (python code)  (0) 2017.07.18
Logistic Regression  (0) 2017.07.10
Decision Tree + ID3알고리즘  (0) 2017.07.01
Linear Regression  (0) 2017.04.20
Linear Classifier  (0) 2016.07.13
Comments