[ML] 의사결정 나무(Decision Tree) C4.5 알고리즘

이전에 업로드에서 의사결정 나무의 가장 기초적인 알고리즘인 ID3 알고리즘에 대해서 정리하였다.

이번에 소개할 C4.5 알고리즘은 ID3 알고리즘과 동일하게 엔트로피로 불순도를 계산하며 연속형 변수의 피처도 처리할 수 있도록 발전시킨 알고리즘이다.

-목차-

1. C4.5 알고리즘

    1.1 Information Gain Ratio

    1.2 연속형 변수의 사용

 

1. C4.5 알고리즘

C4.5 알고리즘이 ID3알고리즘에 비해 개선된 점은 아래와 같이 요약할 수 있다.

• 정교한 불순도 지표 (Information gain ratio) 활용
• 범주형 변수뿐 아니라 연속형 변수를 사용 가능

 

1.1 Information Gain Ratio

앞서 ID3 알고리즘에서 설명했듯, 엔트로피 \(H(t)\)가 작을수록, \(t\)의 순도는 높다고 했었으니, 순도가 높을수록, \(IG(Y,X)\)는 커진다. 이를 통해 분기를 시작할 노드를 선택할 수 있다. 다만, 각 노드마다 단 하나의 샘플을 갖는 경우를 생각해보면, 순도가 무조건 최고값을 가지게 되는 것을 알 수 있는데, 이러한 이유로 정보 이득은 일반화 성능이 매우 저조하다. 때문에 이득율(Gain ration)라는 것을 사용하는데, 수식은 아래와 같다.

 

\[Information\,Gain\,Ratio = GR = \frac{IG}{IV} \]

 

여기서 \(IG\) 는 ID3 알고리즘에서의 Information Gain을 의미하며 \(IV\)는 Intrinsic Value를 의미한다. 정보 이득을 어떤 속성의 내재 값(Intrinsic value)로 나눠줌으로써, 일종의 정규화를 건 것으로 이해하면 된다.

특정 지표로 분기했을 때 생성되는 가지의 수를 \(N\)이라고 하고, \(i\)번째 가지에 해당하는 확률을 \(p_{i}\)라고할 때, Intrinsic Value는 아래와 같다.

 

\[IV = -\sum_{i}^{N}p_i\log p_i\]

 

이해를 돕기 위해 아래 그림을 보자.

Windy 지표에 대한 Information Gain Ratio를 계산해보면, 첫 번째 경우는 0.5739라는 값을 얻을 수 있다.

하지만 아래와 같은 경우는 어떠한가?

 

동일한 방법으로 With whom에 대한 \(GR\)을 계산하면 0.2182라는 값을 얻을수 있다.

두 번째 예시는 대부분의 가지가 하나의 샘플만을 가지기 때문에 \(IG\)가 매우 높은 상태이다. 하지만 너무 세분화되어 있기 때문에 좋은 모델이라고 할 수 없다. \(GR\)을 분기 지표로 사용하게 되면 이렇게 가지가 세분화되는 경우에 \(IV\)라는 페널티가 주어 지기 때문에 \(IG\)를 분기 지표로 사용하는 ID3 알고리즘보다 더 좋은 모델을 생성할 수 있다. 

 

1.2 연속형 변수의 사용

C4.5 알고리즘에서의 두번째 개선점은 범주형 변수 (discrete variables)뿐 아니라 연속형 변수 (continuous variables)를 입력값으로 넣을 수 있다는 점입니다.

아래 테이블과 같은 데이터가 있다고 가정해보자. Temperature 변수는 연속형 변수이다.

 

Temperature	Play
36	No
35	No
22	Yes
24	Yes
20	Yes
35	No
31	Yes
30	No
29	Yes
28	Yes
25	Yes
26	Yes
29	Yes
27	No

 

간단하게 생각해보면 특정 threshold 초과/이하의 값으로 나누면 된다. 먼저 데이터를 변수값에 따라 정렬합니다. 그 후 Threshold를 모든 breakpoints로 설정하면서 분기에 따른 불순도를 계산합니다. 이후 불순도를 최소화하는 지표를 선택하는 것처럼, 불순도를 최소화하는 threshold를 사용한다.

그러면 여기서 breakpoints는 어떻게 정하게 될까? 여기에는 아래 그림과 같이 크게 세 가지 방법이 있다.

 

 

1. 값이 바뀌는 모든 지점을 breakpoints 로 설정
2. Output 클래스가 바뀔 때만 breakpoints로 설정
3. Q1, Median, Q3 값을 breakpoints로 설정

이 중 방법 1을 예시로 Information Gain을 계산해보면 Temperature 지표의 경우, 33도를 기준으로 분기하였을 때 가장 많은 \(IG\)을 얻을 수 있으므로 최적 threshold는 33도라는 것을 알 수 있다.

 

\[IG(Play, Temperature(33)) = 0.4009\]

 

---

참고 자료

https://tyami.github.io/machine%20learning/decision-tree-3-c4_5/

https://junklee.tistory.com/104