[Data Science] Decision Tree - GINI index와 CART 알고리즘

GINI Index on Node

Formula

어떤 attribute에 의하여 클래스 개수에 대한 tuple을 얻을 것이다. 이 tuple을 이용하여 각 클래스 별 비율 $p_i$를 구할 수 있다. $n$개의 클래스에 대하여 지니계수는 다음과 같이 정의한다.

\[ Gini= 1-\sum_{i=1}^{n} p_i^2 \]

 

Node Impurity의 최대와 최소

node impurity가 가장 클 때는 $C$개의 클래스 집합에서, 해당 노드가 모든 클래스들이 모두 같은 비율로 나누어지면 $p_i = 1/C$이므로 $Gini_{max} = 1-1/C$이다.

Node impurity가 가장 작을 때는 해당 노드가 하나의 클래스로만 나눠진 경우이다. 이 경우 하나의 $p_i=1$이고 나머지는 $p_j=0(j \neq i)$이므로 $Gini_{min}=0$이다.

 

GINI Index를 사용하는 알고리즘

CART, SLIQ, SPRINT 등의 알고리즘은 node impurity를 GINI index 기반으로 split한다.

CART는 Classification And Regression Tree로 가장 기본적이면서 분류와 회귀 모두 적용 가능하기에 자주 사용되는 알고리즘이다.

Examples for Computing GINI

클래스의 개수가 2인 이진분류에서 어떤 노드의 상태가 다음과 같다고 하자.

$\{C1: 0, C2: 6 \}$인 경우, $p_1=0, p_2=1$이므로 $Gini= 1-(0^2 + 1^2) = 0$이다.

$\{C1: 1, C2: 5 \}$인 경우, $p_1=1/6, p_2=5/6$이므로 $Gini= 1-((1/6)^2 + (5/6)^2) = 0.278$이다.

$\{C1: 2, C2: 4 \}$인 경우, $p_1=2/6, p_2=4/6$이므로 $Gini= 1-((2/6)^2 + (4/6)^2) = 0.444$이다.

당연히 Worst Case인 경우는 위에서 살펴 보았듯이 $1-(1/2)=0.5$이다.

 

GINI Index on Partition

노드가 $k$개의 partition(children)으로 나누어질 때, GINI Index는 각 노드들의 GINI계수의 가중평균으로 계산한다.

\[ Gini_{partition} = \sum_{i=1}^{k} \cfrac{N_i}{N_p}Gini(i) \]

이때 $N_p$은 parent node의 데이터 수, $N_i$는 $i$번째 child node의 데이터 수이다.

 

Case 1. Binary Attributes

Parent 가 $\{C1:6, C2:6\}$이라 하자.

$B$가 binary attribute여서 yes/no 2개의 partition으로 나뉜다. 이때 yes와 no로 분류된 노드를 각각 $N1, N2$라 하자.

그리고 그 결과가 다음과 같이 $N1 =\{C1: 5, C2: 2 \}, N2 = \{C1:1, C2:4\}$

Binary-way split

각 노드별로 지니 계수를 구하고 가중평균을 구해보자.

$Gini(N1) = 1-\{(5/7)^2 + (2/7)^2 \} = 0.408$

$Gini(N2) = 1-\{(1/5)^2 + (4/5)^2 \} = 0.320$

따라서 $Gini(child) = (7/12)(0.408) + (5/12)(0.320) = 0.371$ 이다. (분모의 12는 Parent Node의 6+6에서 온 것이다)

 

Case 2. Categorical Attributes

Multi-way split, Two-way split

첫번째 그림의 경우만 계산해보자.

$Gini(Family) = 1 - ((1/5)^2 + (4/5)^2) = 0.312$

$Gini(Sports) = 1 - ((1/3)^2 + (2/3)^2) = 0.444$

$Gini(Luxury) = 1 - ((1/2)^2 + (1/2)^2) = 0.500$

따라서

$Gini(child) = (5/10)(0.32) + (3/10)(0.44) + (2/10)(0.50)=0.393$ 이다.

 

Case 3. Continuous Attributes

Continuous의 경우 조금 복잡하다. 이전 포스팅에서도 보았듯이, 가능한 모든 경우에서 노드 불순도를 계산하고 최적의 값을 찾아야 하기 때문이다.

어떤 특정 값 $v$에 대하여 $\{ A: A<v \}$, $\{A: A \ge v \}$ 이렇게 2개의 partition으로 나눌 수 있다.

즉 attribute를 정렬한 후 선형탐색을 통해 최적의 GINI Index를 계산한다.

 

더 효율적인 계산을 위해 label(여기서 Cheat)마다 Yes/No의 개수를 하나씩만 업데이트 해주는 방법을 이용하여 efficiency를 향상시킬 수 있다. 맨 왼쪽 LHS, RHS가 각각 [(0, 0), (3, 7)]로 시작한다. 처음 만나는 label이 No이므로 해당 label의 개수를 1개씩 증감시켜주면 [(0, 1), (3, 6)]이 된다. 이런식으로 선형탐색을 통해 yes/no 개수를 1씩 업데이트 해주면 되므로 일일히 전제 DB를 스캔하여 개수를 구하지 않아도 된다.

Compute GINI Index on Continuous Attributes

CART Algorithm

Pseudo code

1. 각 attribute마다 best split을 찾는다.
   1. Gini index가 가장 많이 감소하는 경우가 best split point가 된다.
2. 각 node 마다 best split을 찾는다.
   1. step1에서 찾은 best split에 대하여, gini index가 가장 작은 것을 고른다.
3. step2에서 찾은 node로 split한다.