Decision Tree (의사결정나무)

Note: 이번 내용은 Jaeyoon Han님의 자료를 저희 스터디원이 진행 한 발표내용을 중심으로 추가적인 discussion을 정리했습니다. 의사결정나무의 개념과 추가적인 내용 및 파이썬 코드에 관한 부분은 아래의 링크를 참고하시기 바랍니다. 개인적으로 이해한 내용으로 작성한 자료니 틀린 부분이나 모르는 부분은 댓글로 남겨주시기 바랍니다!!!

 

의사결정나무는 마치 스무고개를 하듯이 Rules에 의해서 Predictors로 Target을 예측하는 모델입니다.

 

출처: Jaeyoon Han님의 2017 machine learning study 자료

위의 내용에서 Play Golf라는 목적값을 예측하기 위해서 날씨(Outlook), Temp(온도) ,습도(Humidity), 바람(windy)의 4가지 요소를 나누는 것입니다. 오른쪽 그림에서 예를 들면 Outlook이 Sunny이고 Windy가 True인 경우에는 Play Golf가 No를 3명 가지는 것을 볼 수 있습니다. 이처럼 내가 가지고 있는 독립변수들을 Rules에 기반하여 목적변수 Y를 예측하는 방법을 의사결정나무라고 합니다. 

 

위의 예시는 입력값과 출력값이 카테고리인 경우이고 수치형인 경우에는 아래와 같이 Box의 형태로 나눌 수 있습니다. 

출처: Kichun Lee, Ph.D. Hanyang University, Seoul, Korea

수치형인 경우에는 특정 경계선보다 크냐 작냐에 의해서 의사결정을 진행하고, 특정 경계선을 선정하는 방법은 아래에서 자세히 보겠습니다. 

 

 

출처: Jaeyoon Han님의 2017 machine learning study 자료

다시 첫번쨰 그림으로 돌아와서 의사결정나무에서 사용하는 용어를 살펴보도록 하겠습니다.  의사결정나무에서 맨위에 있는 사각형을 뿌리 노드(root node)라고 하고, 노드와 노드를 잇는 선을 가지(branch)라고 합니다. 그리고 가지가 밑으로 더 이상 생성되지 않는 노드를 잎사귀 노드(leaf node) 혹은 말단 노드(terminal node)라고 합니다. 이 노드에는 최종 의사결정에 대한 정보가 담겨있습니다. 마지막으로 뿌리 노드와 말단노드를 제외한 모든 노드를 중간 노드(internal node)라 부르고 뿌리 노드부터 말단 노드까지의 노드 수를 깊이(depth)라고 합니다.

 

의사결정나무는 말단 노드에 존재하는 의사결정 결과를 보다 순수(pure)하게 만드는 모델입니다. 다만 그 결과를 만들기까지 어떤 변수를 이용해서 나눌 것이며, 어떤 기준을 두는가가 모델의 중요한 이슈가 되는겁니다. 이러한 기준으로는 어떻게 노드를 나눌 것인지, 여러 형태의 데이터를 다룰 수 있는지, 과적합을 어떻게 방지할 지 등등 여러개가 있고 주로 사용하는 알고리즘은 아래와 같습니다.

 

출처: Jaeyoon Han님의 2017 machine learning study 자료

 

• ID3 (Iterative Dichotomizer 3)
  
• CART (Classification and Regression Tree)
• C4.5
• C5
• CHAID

출처: http://blog.naver.com/trashx/60099037740 각 알고리즘 별 내용도 나와있음.

참고1: https://stackoverflow.com/questions/9979461/different-decision-tree-algorithms-with-comparison-of-complexity-or-performance

참고2: https://www.quora.com/Do-different-decision-tree-algorithms-offer-significant-differences-in-performance

 

각 알고리즘의 차이는 저도 정확하게 이해하지 못해서 위의 참고자료를 통해서 각자 이해하도록하고 이번자료에서는 가장 많이 쓰이는 CART 모형에 대해서만 살펴보도록 하겠습니다. 

 

CART (Classification and Regression Tree)​

이진분류를 사용하여 discrete target variable(Classification Tree)와 continuous target variable(Regression Tree)를 예측하는것을 의미합니다. 

 

출처: Jaeyoon Han님의 2017 machine learning study 자료

위의 왼쪽과 같은 문제가 주어졌을 때, 오른쪽으로 트리를 만들기 위해서 가장 먼저 해야하는 것은 Outlook, Temp, Humidity, Windy라는 4가지 변수가 주어졌을 때 어떤 변수로 트리를 분류(의사결정)해야 하는 점 입니다. 결론부터 말하면 불순도(impurity) 혹은 불확실성(uncertainty)를 감소하는 방향으로 학습을 진행합니다. 그리고 같은 표현으로 정보획득(information gain)이라고 합니다. 

 

불순도/불확실성에 대해 계산하는 부분은 다음의 링크에 자세히 설명되어있으니 참고 하시기 바랍니다. https://ratsgo.github.io/machine%20learning/2017/03/26/tree/ 

 

위에서 불순도를 계산하는 방법을 안다는 가정하에서 위의 문제를 풀어보도록 하겠습니다. 

 

E(S) = E([9+,5-]) = (-9/14 log2 9/14) + (-5/14 log2 5/14) = 0.94

Next we will need to calculate the information gain G(S,A) for each attribute A where A is taken from the set 

{Outlook, Temperature, Humidity, Wind}.

 

1) Outlook

• G(S,Outlook) = E(S) – [5/14 * E(Outlook=sunny) + 4/14 * E(Outlook = overcast) + 5/14 * E(Outlook=rain)]
• G(S,Outlook) = E([9+,5-]) – [5/14*E(2+,3-) + 4/14*E([4+,0-]) + 5/14*E([3+,2-])]
• G(S,Outlook) = 0.94 – [5/14*0.971 + 4/14*0.0 + 5/14*0.971] = 0.246 

G(S,Outlook) = 0.246  <------ 제일 큼!!!

2) Temperature

• G(S,Temperature) = 0.94 – [4/14*E(Temperature=hot) +   6/14*E(Temperature=mild) +   4/14*E(Temperature=cool)]
• G(S,Temperature) = 0.94 – [4/14*E([2+,2-]) +     6/14*E([4+,2-]) + 4/14*E([3+,1-])]
• G(S,Temperature) = 0.94 – [4/14 + 6/14*0.918 + 4/14*0.811] 
• G(S,Temperature) = 0.029

 

3) Humidity

• G(S,Humidity) = 0.94 – [7/14*E(Humidity=high) + 7/14*E(Humidity=normal)]
• G(S,Humidity = 0.94 – [7/14*E([3+,4-]) + 7/14*E([6+,1-])]
• G(S,Humidity = 0.94 – [7/14*0.985 + 7/14*0.592]
• G(S,Humidity) = 0.1515

4) Wind

• G(S,Wind) = 0.94 – [8/14*0.811 + 6/14*1.00]
• G(S,Wind) = 0.048

첫번째 과정으로 4가지 변수에 대해 Gain Information을 계산하고 가장 큰 값은 Outlook 변수를 선택합니다. 

이제 위와 같은 과정을 반복해서 불순도가 0이 아닌 Sunny, Rainy에 대해서 같은 작업을 반복하면 위와 같은 결과를 얻을 수 있습니다. 의사결정 나무의 장단점은 아래와 같습니다. 

 

의사결정 나무의 장점과 단점 

1. 장점

사용하고,이해하기 쉽다. 규칙들을 생성하고 해석하기 매우 쉽다. 변수 선택과 축소가 자동적이다.

통계적인 가정이 필요하지 않다.  결측치를 다루지 않아도 된다.

 

2. 단점

수평 또는 수직 분할로 잘 포착되지 않은 구조의 데이터가있는 곳에서는 성능이 좋지 않을 수 있습니다.

프로세스가 한 번에 하나의 변수를 처리하기 때문에 변수 간의 상호 작용을 캡처 할 수 없습니다.

출처: Kichun Lee, Ph.D. Hanyang University, Seoul, Korea 

 

Random Forests 

의사결정 나무를 개선한 모델이 Random Forests입니다. Random Forests는 의사결정나무의 단점 중 하나인 

오버피팅 문제를 극복하기 위해 Bootstrapping(bagging)을 통해 만든 의사결정숲입니다. 숲이라고 표현한 것은 tree1과 같이 여러개의 의사결정나무가 모여서 하나의 모델을 만들기 때문입니다. 

 

 

출처: Kichun Lee, Ph.D. Hanyang University, Seoul, Korea 

 

Random Forest의 장점과 단점 

1. 장점

의사결정나무보다 높은 예측력. 일반화가 되어 과적합 가능성이 낮음

 

2. 단점

블랙박스 모델(모델의 설명력이 떨어짐)