[3] Predicting Forest Cover with Decision Trees

[3] Predicting Forest Cover with Decision Trees

 

Decision Trees

 

 

위의 그림은 우유가 상했는지 , 상하지 않았는지 판단하는 의사결정 방법이다. 의사결정 방법의 구조와 트리와 닮아있기 때문에 의사결정 트리 , Decision Trees라고 한다. 트리의 구조를 가지고 있기 때문에 구조를 살펴보면 Leaf와 Node , Edge 같은 요소들을 가지고 있는 것을 확인할 수 있다.

 

Decision Trees에서의 주목할 점은 Leaf에는 무엇이 들어갈지 모두 정해져 있다는 것이다. Leaf node 안의 내용이 중요한 것이 아니라 우유가 상했는지 상하지 않았는지를 판단하는 기준이 중요하다는 것을 의미한다. Feature와 lable을 보고 가장 잘 분류할 수 있는 기준이 node에 들어가게 될 것이다. 그런 의미에서 Root node는 가장 처음으로 경우를 나누는 기준이다. 그렇기에 Root node는 분류에 있어서 가장 중요한 조건이고 기준이 될 것이다. 예를 들어 위쪽 우유가 상했는지 상하지 않았는지 판단하는 Decision Tree에서는 유통기한이 지났는지 지나지 않았는지를 1순위 기준으로 두고 있다. Root node의 기준이 유통기한 이므로 우유가 상하였는지 상하지 않았는지 판단하는 기준에서는 유통기한이 가장 중요하다는 Insight를 얻을 수 있다는 것이다.

 

 

 

다음은 애완동물에 관한 표이다. 로봇은 위의 데이터를 학습할 것이고 최종적으로는 이 애완동물이 Good pet인지 Bad pet인지 구분하는 것이 목표이다.

 

 

 

 

만약 다음과 같은 기준으로 나누었다면 어떻게 나뉘게 될까. 

 

 

 

결과는 다음과 같이 나온다. 올바르게 구분되지 않아 보인다. 여기에 다른 node를 추가하여 살펴보자.

 

 

 

위의 Decision Tree를 통한 결과는 다음과 같다.

 

 

 

파란색 동그라미는 위의 Decision Tree가 Yes라고 판단한 경우이다. 살펴본 결과 9마리의 애완동물 중 7마리를 정확하게 구분했다. 그렇다면 나머지 2마리 역시 올바르게 구분하기 위해 Decision Tree에 node를 하나 더 추가하고 완벽하게 구분하는 것이 좋은 Decision Tree일까. 그렇지 않다는 것이다. machine learning의 관점에서 Training data에 초점을 맞추는 것은 좋지 않다. Training data가 아닌 Test data에 초점을 맞추는 것이 옳다. 즉 Training data에 대해 과하게 초점을 맞추다 보면 Overfitting이 발생할 수 있다.

 

물론 앞선 경우처럼 너무 Under 하게 만드는 것도 좋진 않다. 당연한 이야기이지만 Training data에 대한 정확도도 어느 정도 나와주어야 한다. 앞선 이야기들은 같은 정확도의 모델이 2개 있고 , 두 모델 간의 차이가 node 개수라면 당연하게도 node 수가 적은 모델이 더 좋다는 것을 의미한다. Decision Tree가 심플하다는 것은 Decision rule의 수가 적다는 것을 의미하고 또 이는 tree의 depth와 tree의 양옆 폭이 작다는 것을 의미한다.

 

 

 

골프 치기 좋은 날인지 , 좋지 않은 날인지 판단하는 데이터다. 너무 덥고 , 바람 불고 , 습하면 골프 치기 좋지 않다고 판단할 수 있다.

 

 

 

위의 Decision Tree는 모든 조건을 총망라해 만든 Decision Tree이다. 이런 경우가 Training data에 치우친 경우이다. 이런 식으로 만들어진 Decision Tree는 새로운 데이터에 대해 잘 구분하지 못한다는 것이다. no와 yes 2개로 분류하는 경우인데도 이렇게 복잡하다면 새로운 데이터가 들어왔을 때 잘 구분한다는 보장이 없다. 따라서 Decision Tree를 만들 때에는 최대한 심플한 tree를 만드는 것이 목표다.

 

심플한 tree를 만들 때 node에서 가장 선호하는 Feature는 가장 경우를 pure 하게 구분할 수 있는 Feature이다. 예를 들어 Windy가 yes인 경우 모두 골프 치기 좋지 않은 날이 나오고 , no인 경우에는 모든 경우가 골프 치기 좋은 날이 나왔다면 Windy Feature가 가장 pure 하게 구분할 수 있는 Feature라는 것이다.

 

이러한 Feature들을 구하기 위해서는 Feature들끼리 수치적으로 비교할 수 있어야 한다. 수치 측정의 경우는 크게 두가지인데, 모든 예시가 같은 class로 분류되었다면 좋은 것이고 , 고루 분포되어있다면 나쁜 것이다. 예를 들어 어떤 Feature로 만들어진 node를 통해 구분한 결과가 50대 50이라면 그냥 반반 확률로 찍는 것과 다름이 없다는 것이고 이는 좋은 조건이 아니라는 것이다. 결국 수치적으로 비교가 가능해야 하고 이때 사용되는 것이 Entropy이다.

 

 

 

 

Entropy는 무질서도를 의미하고 이와 유사한 개념으로는 복잡도가 있다. 만약 복잡도가 0이라면 복잡하지 않은 상태 , 즉 하나의 class로만 이루어진 상태라는 것이다. 만약 5:5 상황으로 나누어져 있다면 Entropy가 가장 큰 , 복잡도가 가장 큰 상황이 되는 것이다. 6:4 나  4:6이나 Entropy의 관점으로는 같은 상황이므로 binary classification의 경우 5:5가 가장 큰 Entropy를 가질 것이다. 따라서 수치적으로 비교가 가능해졌으므로 가장 Entropy가 작은 node를 택하면 pure 하게 결정을 내릴 수 있다는 것이다.

 

Entropy의 식에서의 N은 가지고 있는 Portion 수 , Class의 수가 될 것이다. pi는 각 class가 가지고 있는 비율을 의미한다. 따라서 binary classification의 경우 다음과 같이 식이 나오게 될 것이다. binary classification이기 때문에 p+ = 1 - p-이고 따라서 식이 다음과 같이 나오게 된다.

 

 

 

 

따라서 p+에 따른 Entropy는 다음과 같다.

 

 

골프 치기 좋은 날씨인지 판단하는 Decision Tree의 Entropy를 확인하면 다음과 같다. Sunny의 경우 no가 2개 , yes가 3개이기 때문에 1에 가까운 값이 나오는 것을 볼 수 있다.

 

 

 

위의 Entropy값들은 모두 Outlook에 대한 값들이다. 이 3개의 Entropy를 합칠 때에는 단순하게 더하거나 곱하면 안 된다. 최종적으로 Entropy값들을 합칠 때에는 비율을 적용하여야 한다. 즉 Sunny는 전체 14개의 경우중 5번 등장하였으므로 앞에 5/14를 곱하여 더하게 된다. 즉 Entropy값들에 가중치를 적용하는 방식으로 Entropy를 합칠 수 있다.

 

 

 

이와 관련된 개념으로는 information gain이 있다. information gain이란 , original set인 S가 가지고 있는 Entropy와 비교하여 얼마나 차이가 큰지를 확인하는 것이다. 즉 S의 전체 Entropy와 계산한 Feature에 대한 Entropy의 차이를 본다는 것이다. 차이가 크다는 것은 최대한 많은 information을 얻었다는 것이고 , 이는 average Entropy가 작다는 결론이 나오게 된다. 따라서 information gain을 최대화한다는 것은 Entropy를 최소화한다는 것과 같다고 볼 수 있다.

 

 

 

 

아래의 예시에서는 왼쪽의 경우가 information gain이 크므로 왼쪽이 더 좋을 것이다.

 

 

 

 

위의 과정을 거쳐 Root node는 Outlook으로 구하였다. 이후 다음으로 구분하는 node는 무엇일지 구하는 방법은 Outlook을 구해낸 것처럼 다시 한번 information gain이나 Entropy를 사용하면 된다.

 

 

 

 

 

위의 과정을 반복해 구해낸 최종적인 Decision Tree다. 앞서 처음에 살펴본 Decision Tree와 달리 비교적 심플한 것을 볼 수 있다. 앞서 본 복잡한 Decision Tree와 위의 Decision Tree 모두 Training data에 대해 완벽하게 구분해내고 있다. 이런 경우 Overfitting을 막기 위해서 좀 더 심플한 Decision Tree를 선택하는 것이 좋고 , 따라서 위의 Decision Tree가 더 좋다고 볼 수 있다. 

 

 

Random Forest

Random Forest는 Random Decision Forest라고도 한다. 이는 Decision Tree의 Ensemble모드이다. Ensemble (앙상블) 이란 , 단순한 모델을 결합하여 보다 나은 모델을 만드는 것을 이야기한다. 뉴럴 구조의 딥러닝의 단점 중 하나는 설명하기 어렵다는 점이 있었다. 결과를 보니 잘 돌아가긴 하는데 왜 그런지 비전문가들에게 설명하기 어렵다는 것이다. 그에 반해 Decision Tree는 보는 것만으로도 직관적으로 어떤 것이 중요하고 어떤 과정으로 분류가 되는지 알 수 있다. Random Forest는 이러한 결과의 신뢰도에 대한 부분도 확인할 수 있다.

 

Random Forest는 Decision Tree를 여러 개 만들어 사용하고 평균을 내는 것이다. 예를 들어 5개의 Decision Tree를 사용해 분류한 결과가 3개는 A , 2개는 B라고 분류했다면 3:2로 A가 우세하기 때문에 A라고 판단하고 분류하는 것이다. 모두 같은 값으로 분류하면 신뢰도가 높은 결과일 것이고 , 3:2처럼 아슬아슬하게 분류가 되었다면 신뢰도가 낮은 결과일 것이다. 또한 빅데이터 시대에 데이터를 parallel 하게 병렬적으로 처리할 수 있다는 점은 큰 장점이다. Random Forest 역시 parallel 하게 사용할 수 있어 경우에 따라 유용하게 사용할 수 있는 데이터 분석 방법들 중 하나다.