예시를 통해 이해하는 decision tree가 생성되는 원리

현재 딥러닝이 분류문제의 기본 상식으로 알려져있지만 이전에 고전적인 머신러닝에서는 decision tree를 이용하여 분류문제를 해결했습니다.

 

decision tree는 주어진 dataset을 class별로 구별해나가는 하나의 tree를 생성하는 모형인데요.

 

어떤 식으로 구별해나가는지 그 원리를 예를 들어 설명하겠습니다.

 

주어진 dataset은 여러개의 feature를 가지고 있겠죠? 예를 들면 다음과 같은 dataset을 생각해봅시다.

 

그림1. 예시 dataset

현재 D1~D14까지 data를 outlook, temperature, humidity, wind라는 feature를 이용하여 target 변수인 play tennis의 yes or no 여부를 구분해야합니다.

 

현재 구분하기 전에 yes는 9개 있고 no는 5개 있습니다.

 

이 때 불확실한 상태인 entropy는 얼마일까요?

 

$$- \frac{9}{14} log _{2} \frac{9}{14} - \frac{5}{14} log _{2} \frac{5}{14} =0.94$$

 

여기서 decision tree model은 선택의 순간, 즉 decision을 하는 순간 information gain을 최대로 하는 feature를 선택하여 분류를 진행합니다.

 

순간 순간 information gain이 최대가 되는 feature를 선택하는 일종의 greedy algorithm을 수행하여 학습을 합니다.

 

예를 들어 wind라는 feature를 이용해서 구분한다고 생각해봅시다.

 

wind는 strong과 weak 2가지 값을 가집니다. wind=strong인 경우 yes는 3개 no는 3개가 있고

 

wind=weak인 경우는 yes가 6개 있고 no가 2개 있다는 것을 알 수 있습니다.

 

그림2. wind를 이용해 decision을 하는 과정

 

전체 데이터를 strong이냐 weak냐로 구분할 때 위에서 전체 데이터중 strong의 비율과 weak의 비율을 가중치로 하여 entropy의 합을 계산했다는 것을 기억할 것입니다.

 

strong의 비율은 $\frac{6}{14}$이고 weak의 비율은 $\frac{8}{14}$입니다.

 

그리고 strong영역에서 entropy와 weak영역의 entropy를 구해서 가중합을 구해보면

 

$$\frac{6}{14} (- \frac{1}{2} log _{2} \frac{1}{2} - \frac{1}{2} log _{2} \frac{1}{2} )+ \frac{8}{14} (- \frac{3}{4} log _{2} \frac{3}{4} - \frac{1}{4} log _{2} \frac{1}{4} )= \frac{6}{14} + \frac{8}{14}  \times 0.811=0.892$$

 

wind를 이용해서 구분을 하면 entropy가 0.940에서 0.892로 떨어져서 0.048의 information gain을 얻은 것입니다.

 

이런 식으로 모든 feature에 대해 information gain을 계산해보고 최대가 되는 feature를 이용해서 먼저 1단계 구분을 시작합니다.

 

outlook, humidity, tempearture를 이용해서 information gain을 계산하면 0.246, 0.151, 0.029가 나온다고 합니다.

 

그래서 첫 번째 단계에서는 가장 information gain이 높은 outlook을 이용해서 잎을 구성하는 것입니다.

 

outlook같은 경우는 sunny, rain, overcast 3가지 경우가 있는데요.

 

3가지 경우도 똑같은 방식으로 entropy를 계산할 수 있습니다.

 

전체 데이터에서 sunny, rain, overcast인 비율은 각각 $\frac{5}{14}$ , $\frac{5}{14}$, $\frac{4}{14}$

 

sunny에서 yes는 2, no는 3이고 rain은 yes는 3 no는 2 overcast는 yes가 4이고

 

각각 entropy를 계산할 수 있으니까 가중합을 이용하면 전체 entropy를 계산할 수 있습니다.

 

그림3. decision tree 1단계가 형성된 모습

 

outlook 잎이 형성된 모습이 그림3과 같습니다. 3가지 분기점으로 구분된 모습을 확인할 수 있는데요.

 

주목할 부분은 overcast로 분기된 부분은 모든 data가 yes이므로 더 이상 구분할 필요가 없습니다.

 

직관적으로도 yes와 no로 구분해야하는데 no가 없으니까 더 이상 구분할 필요가 없구요

 

수학적으로도 entropy가 0으로 완전하게 확실한 상태이고 더 이상 information gain을 할 수 없는 상태입니다.

 

그러면 이제 decision tree는 sunny 부분과 rain 부분에서 구분을 위해 information gain이 가장 큰 feature를 선택하는 위와 같은 과정을 반복하여 진행합니다.

 

이렇게 반복해서 구분을 진행한다고 하여 이런 방법을 재귀적 분할이라고 부릅니다.(recursive partitioning)

 

참고로 outlook을 또 선택할 수 있느냐? 어차피 sunny 부분에 모인 데이터들은 outlook=sunny니까 또 선택할 이유가 없습니다.

 

그림4. 학습이 끝난 decision tree

 

여기서 만약 새로운 data로 D15가 들어왔다고 합시다.

 

D15는 feature로 outlook=sunny, temperature = hot, humidity = normal, wind= strong을 가진다고 합니다.

 

학습한 decision tree에 의하면 D15의 play tennis 예측 label은 무엇일까요? 아주 쉽게 yes라는 것을 예상할 수 있습니다.

 

그림5. 학습된 decision tree에서 prediction 과정

 

 

참고

 

Decision tree(의사결정나무) 원리 (tistory.com)

Decision tree(의사결정나무) 원리