의사결정 트리 (Decision Tree)

https://www.ibm.com/topics/decision-trees

What is a Decision Tree | IBM

 

트리 노드 분할

Decision tree 노드 분할 시 최적의 피쳐를 고르는 대표적인 방법으로는 정보 이득(information gain)과 지니 불순도(Gini impurity)가 있다.

 

정보 이득 (Information Gain)

정보 이득은 보통 노드 분할 전후의 엔트로피 차이를 뜻하지만, 엔트로피 대신 지니 불순도나 평균 제곱 오차(mean squared error) 등을 사용할 때에도 쓰일 수 있는 용어이다.

정보 이득은 정보학에서의 엔트로피(Entropy)로 구한다.

Entropy는 필요 정보량의 기댓값을 뜻한다.

2023.08.16 - [AI,머신러닝,데이터/용어] - 정보량, 엔트로피

정보량, 엔트로피

 

Entropy를 구하는 식은 다음과 같다.

$ Entropy(S) = - \sum\limits_{c\in C}p(c)log_2p(c) $

S는 엔트로피를 계산할 데이터셋
c는 데이터셋 S에 포함된 클래스
p(c)는 데이터셋 S에서 클래스 c의 비율

 

Information gain은 노드를 분할하기 전후의 Entropy 차이이다. Entropy는 0~1 사이의 값을 가지는데, Entropy가 작을수록 잘 분류된 상태이므로, 이 값이 낮아지는 방향으로 노드를 분할해야 한다. 즉, Information gain이 가장 높게 나오는 피쳐가 분할을 위한 최적의 피쳐이다. Information gain을 구하는 식은 다음과 같다.

$ Information Gain(S, a) = Entropy(S) - \sum\limits_{v\in values(a)}\cfrac{\left|S_v\right|}{\left|S\right|}Entropy(S_v) $

$a$는 특정 클래스 label
$Entropy(S)$는 데이터셋 S의 entropy
$\cfrac{\left|S_v\right|}{\left|S\right|}$는 데이터셋 S에서 $S_v$의 비율
$Entropy(S_v)$는 데이터셋 $S_v$의 entropy

 

위 데이터는 날씨 속성에 따른 테니스 플레이 여부인데, entropy는 0.94이다. 플레이 여부 Yes는 14개 중 9개, No는 5개이므로, 다음과 같이 entropy 공식에 대입하여 구할 수 있다.

$ Entropy(Tennis) = - \cfrac{9}{14}log_2\cfrac{9}{14} - \cfrac{5}{14}log_2\cfrac{5}{14} = 0.94 $

Humidity 속성의 information gain은 다음과 같이 계산할 수 있다.

$ Information Gain(Tennis, Humidity) = 0.94 - \cfrac{7}{14}*0.985 - \cfrac{7}{14}*0.592 = 0.151 $

- Humidity가 High인 날은 14일 중 7일, 이 데이터의 entropy는 0.985

- Humidity가 Normal인 날은 14일 중 7일, 이 데이터의 entropy는 0.592

 

다른 속성에 대해서도 모두 information gain을 계산하여 가장 높은 값이 나오는 속성으로 트리를 분할하면 되는데, 위 데이터에서는 outlook이 가장 높은 information gain이 나온다.

 

지니 불순도 (Gini Impurity)

Gini impurity는 데이터셋에 다른 데이터가 섞여 있는 정도이다.

클래스가 두 개인 경우 0~0.5 값을 가지며, 모든 데이터가 같은 클래스이면 0, 두 클래스의 데이터 수가 같으면 0.5의 값을 가진다.

2023.08.18 - [AI,머신러닝,데이터/용어] - 지니 불순도 (Gini Impurity)

지니 불순도 (Gini Impurity)

Gini impurity를 구하는 식은 다음과 같다.

$ Gini(D) = 1 - \sum\limits_{i=1}^kp_i^2 $

 

모든 피쳐의 범주(또는, 수치 분할지점들)에 대해 Gini impurity를 계산해서, 이 값이 가장 작은 피쳐를 사용해 노드를 분할한다.

만약 피쳐 A를 기준으로 데이터셋 $D$를 $D_1, D_2$ 로 나눴고, 각각의 크기가 $n_1, n_2$일 때, Gini impurity는 다음과 같이 데이터셋 크기에 비례해서 합산한다.

$ Gini_A(D) = \cfrac{n_1}{n}Gini(D_1) + \cfrac{n_2}{n}Gini(D_2) $

 

Decision Tree 알고리즘 종류

ID3

Entropy와 information gain으로 노드를 나누는 방식 사용

범주형 속성만 사용 가능 (수치형 불가)

자세한 내용은 논문(https://hunch.net/~coms-4771/quinlan.pdf )에서 확인 가능한데, 위 정보 이득 설명이 이 내용을 바탕으로 함

다음 순서로 알고리즘이 동작 (https://ai-times.tistory.com/161)

1. 전체 데이터를 포함하는 루트 노드 생성
2. 만약 샘플들이 모두 같은 클래스라면, 노드는 잎이 되고, 해당 클래스로 레이블을 부여한다.
3. 그렇지 않으면 정보이득이 높은(즉, 데이터를 가장 잘 구분할 수 있는) 속성을 선택한다.
   (이때 정보이득은 엔트로피의 변화를 가지고 계산한다.)
4. 선택된 속성으로 가지(Branch)를 뻗어 하위 노드들을 생성한다.
   (각 하위 노드들은 가지의 조건을 만족하는 레코드들이다.)
5. 각 노드에 대해여 2단계로 이동한다.

 

C4.5

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

Information gain 대신 information gain ratio를 사용하여 노드를 분할함

 

2023.08.24 - [AI,머신러닝,데이터] - 의사결정 트리(Decision Tree) - C4.5 알고리즘

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

 

C5.0

https://www.rulequest.com/see5-comparison.html

Is C5.0 Better Than C4.5?

C4.5보다 더 빠르게, 더 작은 트리를 생성하는 알고리즘

 

CART

"Classification And Regression Trees" 약자

Gini impurity를 사용하여 노드 분할

이진 트리(binary tree) 생성

수치형 속성 지원 (regression)

 

2023.08.24 - [분류 전체보기] - 의사결정 트리(Decision Tree) - CART 알고리즘

의사결정 트리(Decision Tree) - CART 알고리즘