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

이 글은 세바스찬 라쉬카의 머신러닝 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이 되도록 정규화한 것입니다.

결정 트리와 불순도에 대한 궁금증”에 대한 1개의 생각

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중

This site uses Akismet to reduce spam. Learn how your comment data is processed.