[Data Mining] Decision Tree

아래의 설명에는 별 이상이 없을 것이다. 그런데 숫자 계산에는 다소 오류가 있을 수 있으니 너무 숫자에 신경쓰시면서 보시지 않아도 된다.

Decision Tree를 공부해보자. 그런데 설명하기 전에 하나만 말하고 가자. 음... 이거는 구현은 안 하려고 한다. 핑계를 좀 대자면, 복잡하기도 하고 적어도 원리는 이해를 했으니 복습을 하겠다는 가장 근본적인 취지는 지켰다는 점도 있고, 그리고 나머지 복습에 논문준비에 할 것이 태산같이 쌓였다는 점도 있다. 게다가 지금까지 포스팅한 것을 보면 구현한 부분은 그냥 마지막에 잠깐 보여주시 식으로만 되어있는데.. 그닥 있을지 없을지 모르는 독자들에게는 도움이 안 될 것 같다는 핑계를 주절주절...

이제 핑계는 그만 나불거리고, decision tree를 공부해보자. decision tree를 공부하기 위해서 우선 알아야 할 개념은 entropy이다. 우선 이미지로 알아보자. entropy가 높은 경우와 낮은 경우이다.

왼쪽이 entropy가 높은 경우, 오른쪽이 entropy가 낮은 경우이다. entropy가 높다는 말은 그만큼 data가 지저분하다는 뜻이다. 반대로 entropy가 낮다는 말은 data가 간단하다는 것이다.

왼쪽에 entropy가 높은 messy data에는 1부터 3까지의 숫자가 골고루 있다. 반면에 오른쪽에 entropy가 낮은 neat data에는 1만 있다. 그렇다면 entropy는 어떻게 구하는지 공식을 통해 알아보자. 아래의 식과 같다.

확률이 나온다. 각 값이 나타날 확률과 그 확률의 로그값을 곱해서 모두 합하여 -1을 곱하는 식이다. 위의 공식으로 messy data와 neat data의 entropy를 구해보면 아래와 같다.

여기서 뭔가 이상하다고 생각하는 사람이 있을 수도 있다. "내가 알기로는 엔트로피는 0과 1 사이인데?" 그렇다. possible value가 2개일 경우 즉 엔트로피 공식이 아래와 같이 simplify되는 경우에는 0과 1 사이이다. 그런데 possible value가 3개 이상일 경우에는 entropy가 1 이상일 수 있다.

아무튼 위에 messy data와 neat data의 entropy값을 보면, messy data는 1.5774062828523452가 된다. 이 data를 이제 간단하게 나눠보자. 즉, 이 값을 쪼개서 entropy를 낮춰보자는 말이다.

1로 쪼개진 그룹의 엔트로피는 당연히 0

2로 쪼개진 그룹의 엔트로피도 당연히 0

3로 쪼개진 그룹의 엔트로피도 당연히 0 이다.

1, 2, 3은 각각 4/14, 5/14, 5/14비율로 쪼개졌으니까 

세 entropy의 weighted average을 구하면 0이 된다. 1.5774062828523452라는 entropy가 어떤 기준에 따라 1, 2, 3으로 나누었더니 entropy(weighted average entropy)가 0으로 뚝 떨어졌다는 것이다. 그러면 우리는 "아 그 기준에 따라서 우리가 data를 나누면 뭔가 정보를 많이 얻겠구나?"라고 이해할 수 있다. 이것을 우리가 전문용어로 Information Gain이라고 한다.

nominal value들에 대해서는 위와 같이 entropy를 구해서 Information Gain을 구할 수 있다. 그럼 numeric data들에 대해서는 어떻게 구할까? 같은 방법으로 구할 수 있다.

entropy for x2를 구한 방법은 아래와 같다. 예를 들어 값이 x2값이 65일때는 x2<=65인 경우의 확률과 x2>65인 경우의 확률을 구해서 entropy를 구하는 것이다.

참고로 x2전체에 대한 entropy는 0.9402859587이므로 이 값에서 각 x2에 대한 entropy를 빼면 아래와 같은 결과가 나온다.

x2가 80일 경우 가장 Information Gain이 높다. 자 이 원리를 이용해서 우리는 Decision Tree를 만들어 보려고 한다. 어떻게 만들까? 우선 이전 포스팅에서 사용했던 weather data를 다시 이용해보자.

이것을 가지고 우리는 아래와 같은 Tree를 만들려고 한다.

제일 위에 보면 outlook으로 data가 나뉜다. 어떻게 outlook으로 data를 나눈다는 것을 결정할까? 이 때 Information Gain을 이용한다. 지금 우리는 Outlook, Temperature, Humidity, Windy 네 개의 attribute을 가지고 있다. 이것들의 Information Gain을 구해서 가장 높은 값을 구하는 것이다. 이유는 바로 Information Gain이 높은 값으로 쪼개야 data가 가장 less messy해지기 때문이다. 아래와 같이 구하면 된다.

(단, Entropy(p) = p*log(1/p) + (1-p)*log(1/(1-p)))

참고로 위의 Minimum Entropy(Tempuerature)과 Minimum Entropy(Humidity)는 아래와 같이 구했다.

Outlook, Humidity, Temperature, Windy의 Entropy를 구해서 Parent Entropy에서 빼서 가장 큰 attribute을 택한다.

Outlook이 가장 크다. 따라서 data를 Outlook으로 쪼갰을 때 가장 data가 certain해진다는 것이다.

그 다음에 해야 할 일은 똑같다. 각각의 나누어진 것에 대해서 또 똑같이 Information Gain을 구한다. Outlook은 overcast, sunny, rainy 값을 가질 수 있기 때문에 각 값으로 쪼갠 후 각각의 Entropy를 다시 구하면 된다.

Outlook이 overcast인 경우에는 이미 "yes" 값 밖에 없다. entropy는 0일 것이고, 충분히 certain한 값이기 때문에 더 이상 Tree를 쪼개지 않는다.

Outlook이 Sunny일 경우에는 75로 쪼개진다. (과정 생략)

Outlook이 Rainy일 경우에는 Windy로 쪼개진다. (과정 생략)

방법은 같기 때문에 생략한다. (솔직히 일일이 하나하나 하기에는 작업이 많이 간다.)

자 이제 마지막 leaf node들을 보면 모든 값이 no나 yes를 갖게 된다. 그러니까 이제 Tree를 그만 쪼갠다. 트리를 쪼갤지 말지 결정하는 기준으로는 아래의 세 가지 기준이 있다.

1. 모든 data가 같은 Class를 가질 경우

2. 모든 data의 attribute이 같을 경우

3. data가 하나 밖에 없을 경우

너무 당연한 거라 딱히 추가적인 설명은 없어도 될 거라고 생각한다. 자 Decision Tree를 만드는 방법은 이와 같다. 

그런데 문제가 있다. weather data의 경우에는 크기가 작기 때문에 위의 Tree와 같이 깔끔하게 나누어지는데, data set이 커지면 트리도 같이 커질 확률이 높다. 왜냐하면 Decision Tree는 위의 세 가지 조건이 만족할 때까지 Tree를 계속 쪼갤 것이기 때문이다. 이렇게 해서 만들어진 Tree는 너무너무너무너무 training data에 잘 맞아 떨어져서 test data에는 잘 맞지 않게 된다. 즉, 너무 자세하게 만들어진 Tree라는 것이다. 이러한 현상을 Overfitting이라고 한다. Train set에 너무 Overfit하여 test set에는 좋지 않다는 것이다. 

그렇다면 우리는 어떻게 해야될까? Pruning이 필요하다. 즉, 가지치기다. 중간에 가지를 잘라버려야 된다는 것이다. 어떻게 자르는지는 나도 안 배웠으니... 이거는 조금 이후로 미루고 다음 포스팅은 Support Vector Machine이다. 어마무시한 수학이 나올 예정인데, 나도 다는 모르므로 최대한 원리만 설명하되 수학도 설명을 많이 하도록 노력은 하겠다. 아무튼 다음 포스팅에서 다시 이야기하자.

p.s. 음... 3년간 포스팅을 해오면서 포스팅하는데 entropy가 가장 높은 날이었다. 정말 힘드네...