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

이 글은 세바스찬 라쉬카의 머신러닝 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.).

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

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

f 는 분할에 사용되는 특성이고 D_p와 D_j는 각각 부모 노드와 j 번째 자식 노드의 데이터셋입니다. I 는 불순도 지표입니다. N 은 샘플의 전체 개수이고 N_j 은 j 번째 자식 노드의 샘플 개수입니다. 이제 분류에서 가장 널리 사용되는 (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}(I_G)와 엔트로피^Entropy(I_H)와 분류 오차^{Classification Error}(I_E)입니다. 엔트로피의 정의부터 살펴보죠. 다음과 같습니다.

$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개의 샘플을 가진 부모 노드의 데이터셋 D_p 를 각각 두 개의 데이터셋 D_left 와 D_right 로 나누었습니다. 분류 오차를 분할 기준으로 사용했을 때 정보 이득은 A 와 B 의 경우 모두 같습니다(IG_E = 0.25):

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

$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$

$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$

$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$

$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$

$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$

$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개의 생각

KT PARK 2018-03-25 (11:37 pm)

깊이 있는 설명 감사합니다. 도움이 되었습니다.

좋아요Liked by 1명

응답 ↓

답글 남기기 응답 취소

여기에 댓글을 입력하세요...

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

이메일 (필수) (주소는 공개되지 않습니다)

이름 (필수)

웹사이트

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

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

취소

%s에 연결하는 중

	박해선 (Hands-On Machine Learning with…)
	박형근 (Hands-On Machine Learning with…)
	박해선 (Hands-On Machine Learning with…)
	강정윤 (Hands-On Machine Learning with…)
	박해선 (Hands-On Machine Learning with…)
	강정윤 (Hands-On Machine Learning with…)
	Mustafa Ileri (Hinton’s Neural Networks…)
	박해선 (머신 러닝 교과서 3판)
	김신 (머신 러닝 교과서 3판)
	박해선 ([Deep Learning with Python] 2판…)
	딥러닝부시기 ([Deep Learning with Python] 2판…)
	박해선 (SciPy Korea 2023)
	parksamjong (SciPy Korea 2023)
	박해선 (어떤 책을 봐야 하나요?)
	siwonsong (어떤 책을 봐야 하나요?)

텐서 플로우 블로그 (Tensor ≈ Blog)

머신러닝(Machine Learning), 딥러닝(Deep Learning) 그리고 텐서(Tensor) 또 파이썬(Python)

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

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