의사결정나무(decision tree)의 생성 원리

데이터가 무작위로 섞여있는 상태를 생각해봅시다.

 

그림1. 데이터가 무작위 섞여있는 상태

 

이럴 때 우리는 무작위로 선을 그어 빨간색 데이터와 파란색 데이터를 구분하고자 합니다.

 

어떻게 그어야 가장 잘 분류를 했다고 말할 수 있을까요?

 

그러니까 빨간색과 파란색을 어떤 선을 그어서 구분을 해야 가장 잘 구분을 했다고 말할 수 있을까요?

 

직관적으로 한쪽 영역에는 순수하게 파란색만 존재하고 다른쪽 영역에는 순수하게 빨간색만 존재해야겠죠?

 

무작위로 섞여있는 불순물한 상태(impurity)에서 순수한 데이터들만 존재하도록 (purity) 영역을 구분하는 것이 데이터를 잘 분류한 것입니다.

 

다른 말로는 불확실하게 데이터가 섞여있는 상태에서 누구라도 확실하게 빨간색과 파란색을 알아볼 수 있도록 만드는 작업이 분류라는 것입니다.

 

decision tree는 이러한 원리에 기반하여 만들어졌습니다.

 

decision tree가 데이터에게 질문하는 기준은 불순한 현재 상태에서(불확실한 현재 상태에서) 순수한 정도를 최대로 증가시키는 방향(확실한 정도를 높이는 방향)입니다.

 

불확실하다, 확실하다 이런 정도를 어떻게 나타낼까요? entropy를 이용합니다.

 

그림1의 U라는 공간의 entropy는 얼마일까요?

 

로그의 밑을 2로 가정하고 전체 데이터 수는 10개이고 빨간색 데이터는 6개, 파란색 데이터는 4개이므로

 

빨간색 데이터를 뽑을 확률 $P('red')= \frac{3}{5}$

 

파란색 데이터를 뽑을 확률 $P('blue')= \frac{2}{5}$

 

이고 U라는 공간의 entropy는 그 정의에 의하여

 

$$H(U)=- \frac{3}{5} log _{2} \frac{3}{5} - \frac{2}{5} log _{2} \frac{2}{5} =0.972$$

 

0.972 정도의 불확실한 정도를 가집니다.

 

그림2. 데이터를 두가지 영역으로 구분

 

제가 이제 U 공간에 선을 하나 그어서 A,B로 구분했다고 합시다.

 

이럴 때 이 U 공간의 불확실한 정도인 entropy는 얼마일까요?

 

영역이 A와 B로 구분된 경우의 entropy는 다음과 같이 계산됩니다.

 

$$H(U)=P(A)H(A)+P(B)H(B)$$

 

여기서 $P(A)$는 전체 데이터에 대해 A,B로 분할 후 A에 속하는 데이터의 비율이고 $P(B)$는 전체 데이터에 대해 A,B로 분할 후 B에 속하는 데이터의 비율입니다.

 

편의상 정확히 절반으로 구분했다고 합시다. 그러니까 $P(A)=P(B)=\frac{1}{2}$입니다.

 

이번에는 조금 다른 부분이 A영역은 $P('red')= \frac{1}{2}$이고 $P('blue')= \frac{1}{2}$이며

 

B영역은 $P('red')= \frac{3}{4}$이고 $P('blue')= \frac{1}{4}$입니다.

 

$$\frac{1}{2} (- \frac{1}{2} log _{2} \frac{1}{2} - \frac{1}{2} log _{2} \frac{1}{2} )+ \frac{1}{2} (- \frac{3}{4} log _{2} \frac{3}{4} - \frac{1}{4} log _{2} \frac{1}{4} )=0.9075$$

 

구분하기 전 0.972에서 0.9075로 entropy가 조금 감소했습니다.

 

이것이 무슨 의미를 가질까요? 저는 U를 분할 시켰더니 0.972정도의 불순도에서 0.9075로 불순도를 감소시켰습니다.

 

혹은 불확실한 정도를 0.9075로 감소시킨 것입니다.

 

불순도의 반대는 순도이므로 순도를 조금 증가시킨 것입니다.

 

다른 말로는 information을 0.0645를 얻어서 0.972나 불확실한 정도에서 0.9075로 낮춘 것입니다.

 

이것을 information gain이라고 부릅니다. 구분하기 전에 entropy에서 구분하고 나서 entropy의 차이를 뜻합니다.

 

 

내가 0.0645정도의 정보를 획득하면서 분류를 함으로써 현재 공간의 0.972 정도의 불확실한 상태에서 0.9075로 낮춘 것입니다.

 

정보를 얻었으니까 더욱 확실한 상태로 바꿀 수 있겠죠?