태그 보관물: 결정트리

결정 트리와 불순도에 대한 궁금증

이 글은 세바스찬 라쉬카의 머신러닝 FAQ 글(Why are implementations of decision tree algorithms usually binary and what are the advantages of the different impurity metrics?)을 번역한 것입니다.

결정 트리 알고리즘은 왜 이진 트리로 구현되어 있을까요? 각 불순도 지표들의 장점은 무엇인가요?

현실적인 이유로(조합의 폭발적인 증가combinatorial explosion) 대부분의 라이브러리들은 결정 트리를 이진 트리로 구현합니다. 좋은 점은 이진 트리가 NP-완전 문제NP-complete라는 것입니다(Hyafil, Laurent, and Ronald L. Rivest. “Constructing optimal binary decision trees is NP-complete.” Information Processing Letters 5.1 (1976): 15-17.).

(CARTClassification And Regression Tree 알고리즘의) 목적 함수는 각 분할에서 정보 이득information gain(IG)을 최대화하는 것입니다:

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

는 분할에 사용되는 특성이고 D와 D는 각각 부모 노드와 번째 자식 노드의 데이터셋입니다. 는 불순도 지표입니다. N 은 샘플의 전체 개수이고 Njj 번째 자식 노드의 샘플 개수입니다. 이제 분류에서 가장 널리 사용되는 (CART 알고리즘의) 분할 기준을 살펴 보겠습니다. 간단하게 이진 분할로 식을 표현하지만 당연히 다중 분할로 일반화될 수 있습니다. 이진 분할에 대한 IG 는 다음과 같이 계산합니다:

IG(D_p, a) = I(D_p) - \dfrac{N_{left}}{N}I(D_{left}) - \dfrac{N_{right}}{N}I(D_{right})

이진 결정 트리에서 가장 널리 사용되는 불순도 지표 또는 분할 기준은 지니 불순도Gini impurity(IG)와 엔트로피Entropy(IH)와 분류 오차Classification Error(IE)입니다. 엔트로피의 정의부터 살펴보죠. 다음과 같습니다.

I_H(t) = - \sum_{i=1}^c p(i|t)\,log_2\,p(i|t)

클래스에 샘플이 하나라도 있다면

p(i|t) \ne 0

이고 p(i|t) 는 특정 노드 t 에서 클래스 c 에 속한 샘플의 비율입니다. 그러므로 한 노드의 샘플이 모두 동일한 클래스에 속한다면 엔트로피는 0입니다. 클래스 별로 균등하게 분포되어 있다면 당연하게 엔트로피는 최대가 됩니다. 지니 불순도는 잘 못 분류될 확률을 최소화시키려는 기준으로 생각할 수 있습니다.

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

엔트로피와 비슷하게 지니 불순도는 클래스가 균일하게 섞여 있을 때 최대가 됩니다. 그러나 실제로 지니 불순도와 엔트로피는 매우 비슷한 결과를 만들며 불순도 기준을 사용하여 트리를 평가하는데 시간을 들이는 것보다 가지치기pruning 방식을 바꿔보는 것이 더 낫습니다. 또 다른 불순도 지표는 분류 오차입니다.

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

가지치기에는 좋은 지표지만 노드의 클래스 확률 변화에 덜 민감하기 때문에 결정 트리를 구성하는데는 적합하지 않습니다.

overview-plot

분류 오차가 클래스 확률 변화에 왜 덜 민감한지 보기 위해 다음 그림에서 두 개의 분할 사례를 살펴 보겠습니다.

split

클래스 1에 40개의 샘플, 클래스 2에 40개의 샘플을 가진 부모 노드의 데이터셋 Dp 를 각각 두 개의 데이터셋 Dleft 와 Dright 로 나누었습니다. 분류 오차를 분할 기준으로 사용했을 때 정보 이득은 AB 의 경우 모두 같습니다(IGE = 0.25):

I_E(D_p) = 1 - \text{max}(0.5 + 0.5) = 0.5

A:

I_E(D_{left}) = 1 - \text{max}(0.75, 0.25) = 0.25

I_E(D_{right}) = 1 - \text{max}(0.25, 0.75) = 0.25

IG_E = 0.5 - \dfrac{40}{80}\times0.25-\dfrac{40}{80}\times0.25 = 0.25

B:

I_E(D_{left}) = 1 - \text{max}(\dfrac{20}{60},\dfrac{40}{60}) = \dfrac{1}{3}

I_E(D_{right}) = 1 - \text{max}(1, 0) = 0

IG_E = 0.5 - \dfrac{60}{80}\times\dfrac{1}{3}-\dfrac{20}{80}\times0 = 0.25

하지만 지니 불순도 기준의 IG는 A(0.125) 보다 B(0.1666) 가 더 순수하기 때문에 높습니다.

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

A:

I_G(D_{left}) = 1 - \left( \left(\dfrac{3}{4}\right)^2 + \left(\dfrac{1}{4}\right)^2 \right) = \dfrac{3}{8} = 0.375

I_G(D_{right}) = 1 - \left( \left(\dfrac{1}{4}\right)^2 + \left(\dfrac{3}{4}\right)^2 \right) = \dfrac{3}{8} = 0.375

IG_G = 0.5 - \dfrac{40}{80}\times0.375 - \dfrac{40}{80}\times0.375 = 0.125

B:

I_G(D_{left}) = 1 - \left( \left(\dfrac{2}{6}\right)^2 + \left(\dfrac{4}{6}\right)^2 \right) = \dfrac{4}{9}

I_G(D_{right}) = 1 - \left( \left(\dfrac{2}{2}\right)^2 + \left(\dfrac{0}{2}\right)^2 \right) = 1 - 1 = 0

IG_G = 0.5 - \dfrac{60}{80}\times\dfrac{4}{9} - \dfrac{40}{80}\times0 = 0.1666

비슷하게 엔트로피 기준은 A(0.19) 보다 B(0.31)를 선호합니다.

I_H(D_p) = - (0.5\,log_2\,(0.5) + 0.5\,log_2(0.5)) = 1

A:

I_H(D_{left}) = - \left( \dfrac{3}{4}\,log_2\left(\dfrac{3}{4}\right) + \dfrac{1}{4}\,log_2\left(\dfrac{1}{4}\right) \right) = 0.81

I_H(D_{right}) = - \left( \dfrac{1}{4}\,log_2\left(\dfrac{1}{4}\right) + \dfrac{3}{4}\,log_2\left(\dfrac{3}{4}\right) \right) = 0.81

IG_H = 1 - \dfrac{40}{80}\times0.81 - \dfrac{40}{80}\times0.81 = 0.19

B:

I_H(D_{left}) = - \left( \dfrac{2}{6}\,log_2\left(\dfrac{2}{6}\right) + \dfrac{4}{6}\,log_2\left(\dfrac{4}{6}\right) \right) = 0.92

I_H(D_{right}) = - \left( \dfrac{2}{2}\,log_2\left(\dfrac{2}{2}\right) + \dfrac{0}{2}\,log_2\left(\dfrac{0}{2}\right) \right) = 0

IG_G = 1 - \dfrac{60}{80}\times0.92 - \dfrac{40}{80}\times0 = 0.31

지니 불순도와 엔트로피에 대해 덧붙이자면 위에 언급한 것처럼 만들어진 트리는 실제 매우 비슷합니다. 지니 불순도의 장점은 로그를 계산할 필요가 없어서 구현 성능이 조금 더 낫다는 것입니다.

옮긴이: 위 그림을 보면 엔트로피보다 지니 불순도 방식이 불순도 값을 줄이기 위해 더 클래스 확률을 낮추어야 함을 알 수 있습니다. 즉 엔트로피 방식이 조금 더 균형잡힌 트리를 만들 가능성이 높습니다. scikit-learn의 DecisionTreeClassifier와 DecisionTreeRegressor 및 이들을 사용하는 랜덤 포레스트와 그래디언트 부스팅에서 특성 중요도 속성은(feature_importances_) 트리가 분할에 사용한 특성별로 발생되는 모든 정보 이득을 더하고 전체 특성 중요도의 합이 1이 되도록 정규화한 것입니다.