의사결정 트리(Decision Tree) - C4.5 알고리즘

https://levelup.gitconnected.com/c4-5-decision-tree-explained-from-bottom-up-67468c1619a7

C4.5 Decision Tree. Explained from bottom up

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

의사결정 나무 (Decision Tree) C4.5 알고리즘 설명

 

ID3의 몇 가지 단점을 보완한 알고리즘 - 대표적으로 "범주형 속성 뿐만 아니라 수치형 속성도 사용 가능"

ID3와 마찬가지로 entropy와 information gain을 활용하여 노드를 분할한다.

2023.08.24 - [AI,머신러닝,데이터] - 의사결정 트리 (Decision Tree) > 트리 노드 분할 > 정보 이득 (Information Gain)

의사결정 트리 (Decision Tree)

하지만, ID3와 다르게 information gain에 보정값을 적용한 information gain ratio를 사용한다.

 

Information Gain Ratio를 통한 노드 분할

Information gain을 사용하게 되면 피쳐의 범주가 많을수록 entropy가 감소하는 경향이 있는데, 이는 과적합(overfitting)을 유발

Information gain ratio는 information gain 값을 split information(intrinsic information)으로 나눠줌으로써 이를 완화함

 

Split information 식은 다음과 같다.

$ Split Information = -\sum\limits_{i}^{N}p_i log_2 p_i $

범주 수가 적을수록 split information 값이 작아지므로, 더 적은 범주의 피쳐가 선호된다.

(범주가 하나 뿐이라면 split information은 0이 됨)

 

 

위 Outlook 예제 데이터를 식에 대입하면 split information은 1.577이 나온다.

$ Split Information(Outlook) = -\cfrac{5}{14}\times log_2\cfrac{5}{14} - \cfrac{4}{14}\times log_2 \cfrac{4}{14} - \cfrac{5}{14}\times log_2\cfrac{5}{14} = 1.577 $

 

수치형 속성 처리 방식

수치형 속성은 특정 분할지점(breakpoint)을 기준으로 초과/이하의 그룹으로 나눈다.

Breakpoints를 정하는 방법은 1. 값이 바뀌는 모든 지점을 지정, 또는, 2. class가 바뀌는 지점만 지정하는 방식이 있는데, 예를 들면 아래와 같다.

방법 1을 사용하여 모든 breakpoints의 information gain을 계산해보면 아래와 같다. $temperature=33$일 때 가장 큰 information gain이 나오며, 즉, temperature 속성은 33을 기준으로 나누는 것이 최적이다.

 

(추가 자료)

https://tomaszgolan.github.io/introduction_to_machine_learning/markdown/introduction_to_machine_learning_02_dt/introduction_to_machine_learning_02_dt/#c45-algorithm

Decision Trees - Introduction to Machine Learning