의사결정트리(Decision Tree) 분류트리, Gini, Entropy 쉽게 이해하기

 결정 트리 학습법(decision tree learning)은 머신러닝 학습 방법 중, 결과 데이터(output variable)로 학습시키는 지도 학습(supervised learning)에 해당된다. Output variable값이 연속적인 값일 경우(월급, 몸무게, 넓이 등) 회귀(regression)를 사용하며, output variable이 카테고리에 해당한다면(성별, 국적, 직급 등) 분류(classification)를 사용한다. 여기서는 분류 트리 (Classification tree)를 설명하고자 한다.

 

 

분류 트리 개념

 분류트리는 분기로 나눈 구역의 most commonly occurring class (가장 많이 발생한 class) 비율이 높도록 하여 error rate을 낮추는 것을 목표로 한다. 회귀 트리는 구역의 평균값과 실제 데이터들 간의 차이인 RSS를 줄이는 반면, 분류 트리에서는 해당 구역에서 most commonly occurring class에 속하지 못한 class의 비율을 줄인다.

 

 

Classification error rate

 Most commonly occurring class에 속하지 못한 class의 비율을 나타내는 classification error rate는 다음과 같이 계산할 수 있다.

 

$E = 1-max_k(\hat{p}_{mk})$

 

 $\hat{p}_{mk}$는 m번째 구역의 k번째 class의 비율을 나타낸다. 하지만 트리가 자라는 것에 충분히 민감하지 않아 아래 소개될 Gini impurity와 Entropy 두 가지 수식이 error rate 계산에 있어 더 선호된다.

 

 

Gini impurity

Impurity라는 의미처럼 class가 덜 분류되어 덜 순수한 정도를 수치화하며, 수식은 다음과 같다.

 

$G=\sum^K_{k=1}\hat{p}_{mk}(1-\hat{p}_{mk})$

 

Class 가 2개 있는 경우를 예를 들어보자. $\hat{p}_{m1}$가 1이고, $\hat{p}_{m2}$가 0이여서 완벽히 분리된 경우 $G$는 0으로 계산된다. $\hat{p}_{m1}$가 1/2이고, $\hat{p}_{m2}$가 1/2이어서 반반 섞여 있는 경우, $G$는 0.5로 계산되어 값이 커지는 것을 알 수 있다.

 

 

Entropy

 엔트로피는 gini impurity와 유사한 결과를 나타내며, 수식은 다음과 같다.

 

$D=-\sum^K_{k=1}\hat{p}_{mk}log\hat{p}_{mk}$

 

 분류 트리를 생성할 때는 gini impurity 혹은 entropy가 분기를 나누는 데에는 더 적합하여 주로 사용된다. 반면, 트리를 pruning 하는 작업에서는 정확도를 높이기 위해 classification error rate가 더 선호된다.

 

 아래는 다양한 트리 사이즈를 사용하였을 때의 error rate과 Heart data에 대해 만든 분류 트리 예제이다. 간혹 분기로 나누어도 둘다 동일한 class인 leaf가 형성되는 경우가 있는데, 한쪽 leaf가 보다 정확히 class를 나눈 경우 이런 현상이 발생할 수 있다.