[6] 의사결정나무의 정보이득과 불순도

의사결정나무는 일정 기준을 통해 클래스를 분류해나가는 모양이 나무와 같다고 해서 붙여진 이름이다. 

 

의사결정나무

 

의사결정나무의 분류 기준은 정보 이득(information gain)이다. 정보 이득은 불순도를 토대로 결정지을 수 있다. 이름에서도 알 수 있듯이 불순도는 해당 노드(node)에 얼마나 다양한 클래스가 섞여있는지에 대한 지표이다.

 

\( IG(D_p,f) = I(D_p) - \sum_{j=1}^{m}\frac{N_j}{N_p}I(D_j)  \)

정보 이득

 

f : 분할에 사용할 특성

\(D_p\)와 \(D_j\) : 부모와 j번째 자식 노드의 데이터셋

I : 불순도 지표

\(N_p\) : 부모 노드에 있는 샘플 개수

\(N_j\) : j번째 자식 노드에 있는 샘플 개수

 

간단하게 설명하자면 자식 노드들의 불순도 합과 부모 노드와의 차이로 정보 이득이 결정된다고 할 수 있다. 자식 노드의 불순도가 낮을수록 정보 이득은 커진다.

 

의사결정나무에 자주 사용되는 불순도 지표는 '엔트로피', '지니 불순도', '분류 오차'이다.

 

엔트로피

 

\( I_H(t) = -\sum_{i=1}^{c}P(i|t)log_2P(i|t) \)

엔트로피

P(i|t) : 특정 노드 t에서 클래스 i에 속한 샘플 비율

 

클래스 분포가 균등하면 엔트로피는 최대가 된다. 예를 들어 이진 클래스인 경우 P(i=1|t) = 1 또는 P(i=0|t) = 0이면 엔트로피는 0이 된다. 반대로 P(i=1|t) = 0.5와 P(i=0|t) = 0.5처럼 균등하게 분포되어 있으면 엔트로피는 1이 된다. 엔트로피 조건을 트리의 상호 의존 정보를 최대화하는 것으로 이해할 수 있다.

 

 

지니 불순도

\( I_G(t) = \sum_{i=1}^{c}P(i|t)(1-P(i|t)) = 1 - \sum_{i=1}^{c}(P(i|t))^2  \)

지니 불순도

 

지니 불순도는 잘못 분류될 확률을 최소화하기 위한 기준으로 이해할 수 있다. 엔트로피와 마찬가지로 클래스가 완벽하게 섞여있을 때 최대가 된다. P(i=1|t) = 0.5와 P(i=0|t) = 0.5일 때 지니 불순도는 0.5의 값을 가진다. 

 

 

분류 오차

\( I_E = 1 - max(p(i|t)) \)

분류 오차

 

분류 오차는 가지치기에는 좋은 기준으로 사용될 수 있지만 클래스 확률 변화에 덜 민감하다는 단점 때문에 결정 트리를 구성하는 데에는 잘 사용되지 않는다. 

 

 

 

 

불순도 지표에 따른 이진 분류 시나리오

\( IG(D_p,f) = I(D_p) - \sum_{j=1}^{m}\frac{N_j}{N_p}I(D_j)  \)

정보이득

 

\( IG(D_p,f) = I(D_p) -\frac{N_{left}}{N_pI(D_{left})} -\frac{N_{right}}{N_p}I(D_{right}) \)

이진 분류에서의 정보이득

 

 

엔트로피를 사용했을 때의 정보이득

\( I_H(t) = -\sum_{i=1}^{c}P(i|t)log_2P(i|t) \)

엔트로피

 

 

$$ I_H(Dp) = -(0.5log_2(0.5) + 0.5log_2(0.5)) = 1$$ 

$$ A : I_H(D_{left}) = -(\frac{3}{4}log_2(\frac{3}{4}) + \frac{1}{4}log_2(\frac{1}{4}))= 0.81   $$

$$ A : I_H(D_{right}) = -(\frac{1}{4}log_2(\frac{1}{4}) + \frac{3}{4}log_2(\frac{3}{4}))= 0.81   $$

$$ A : IG_H = 1 - \frac{4}{8}0.81 - \frac{4}{8}0.81 = 0.19 $$

$$ B : I_H(D_{left}) = -(\frac{2}{6}log_2(\frac{2}{6}) + \frac{4}{6}log_2(\frac{4}{6}))= 0.92   $$

$$ B : I_H(D_{right}) = 0   $$

$$ B : IG_H = 1 - \frac{6}{8}0.92 - \frac{2}{8}0 = 0.31 $$

 

 

시나리오 A(\(IG_H = 0.19\))보다 시나리오 B(\(IG_H = 0.31\))의 정보이득이 더 높은 것을 알 수 있다. 따라서 엔트로피 기준도에서는 B를 선호한다는 것을 알 수 있다. 

 

 

지니 불순도를 사용했을 때의 정보이득

\( I_G(t) = \sum_{i=1}^{c}P(i|t)(1-P(i|t)) = 1 - \sum_{i=1}^{c}(P(i|t))^2  \)

지니 불순도

 

$$ I_G(D_p) = 1 - (0.5^2 + 0.5^2) = 0.5 $$

$$ A : I_G(D_{left}) = 1 - ((\frac{3}{4})^2 + (\frac{1}{4})^2) = 0.375 $$

$$ A : I_G(D_{right}) = 1 - ((\frac{1}{4})^2 + (\frac{3}{4})^2) = 0.375 $$

$$ A : IG_G = 0.5-\frac{4}{8}0.375 - \frac{4}{8}0.375 = 0.125 $$

$$ B : I_G(D_{left}) = 1 - ((\frac{2}{6})^2 + (\frac{4}{6})^2) = \frac{4}{9} $$

$$ B : I_G(D_{right}) = 0 $$

$$ B : IG_G = 0.5-\frac{6}{8}\frac{4}{9}- 0 = 0.16xx $$

 

 

시나리오 A(\(IG_G = 0.125\))보다 시나리오 B(\(IG_G = 0.16xx\))의 정보이득이 더 높은 것을 알 수 있다. 따라서 지니 불순도 또한 B를 선호한다는 것을 알 수 있다. 

 

 

분류 오차를 사용했을 때의 정보이득

\( I_E = 1 - max(p(i|t)) \)

분류오차

 

$$ I_E(D_p) = 1 - 0.5 = 0.5 $$

$$ A : I_E(D_{left}) = 1 - \frac{3}{4} = 0.25 $$

$$ A : I_E(D_{right}) = 1 - \frac{3}{4} = 0.25 $$

$$ A : IG_E = 0.5-\frac{4}{8}0.25 - \frac{4}{8}0.25 = 0.25 $$

$$ B : I_E(D_{left}) = 1 - \frac{4}{6} = \frac{1}{3} $$

$$ B : I_E(D_{right}) = 1 - \frac{2}{2} = 0 $$

$$ B : IG_E = 0.5-\frac{6}{8}\frac{1}{3} - \frac{2}{8}0 = 0.25 $$

 

 

분류오차를 사용할 때는 시나리오 A(\(IG_E = 0.25\))와 시나리오 B(\(IG_E = 0.25\))의 정보이득이 같다.

 

 

 

불순도 기준 비교

 

실제로는 지니 불순도와 엔트로피 모두 비슷한 결과가 나온다. 엔트로피에 0.5를 곱한 '엔트로피 (scaled)'를 보면 지니 불순도와 매우 유사함을 알 수 있다. 불순도 조건을 바꾸어 트리를 평가하는 것보단 가지치기 수준을 바꾸면서 하이퍼파라미터튜닝을 진행하는 것이 더 좋다.

 

 

해당 불순도 지표에 따라 정보이득이 결정되기 때문에 이는 분할 조건이 된다고 할 수 있다. 이러한 분할 조건 때문에 의사결정나무는 리프노드가 순수해질 때까지 모든 자식노드에서 이 분할 작업을 반복해준다. 하지만 트리의 최대 깊이를 제한하지 않는다면 과대적합이 될 가능성이 높기 때문에 가지치기의 작업을 진행해준다.