Decision Tree

1. 서론

최근, Light Gradient Boosting 을 써보다가, 이 모델이 정확히 뭔지를 이해하고 싶어졌다.
그래도 최소한 내가 쓰는 모델이 어떤 방식으로 동작하는지는 알고있어야하지 않을까 싶어서...
이전에, xgboost 도 혼자 공부하다가 포기했었는데, 이번에 light gbm 까지 리뷰하는 김에 다 공부해봐야겠다.

대충 공부? 리뷰? 해보려는 것들은 다음 순으로 할 예정이다.

• Decision Tree
• Ensemble 개념 (Bagging, Boosting)
• Bagging
  • Random Forest
• Boosting
  • Adaptive Boosting
  • Gradient Boosting
    • Light GBM
    • XG boost

보면, 모두 Tree 모델 기반으로 고도화 시킨 모델들이다.
그리고 그 첫 번째 시작은 Decision Tree 로, 기초부터 다시 이해하려고 한다.
최대한 직관적으로, 그리고 키워드 단위로 '리뷰' 해보려고 한다.

이 글은 StatQuest with Josh Starmer 의 StatQuest: Decision Trees 영상을 보고 정리한 글이다.
모든 사진과 설명에 대한 출처는 여기에 있다.

2. Decision Tree

2.1. 개념

영상에 나오듯, 예를 직접 보여주며 정리하겠다.
먼저 다음을 보자.

왼쪽의 테이블은, 우리가 가진 데이터다.
행 하나 하나가 환자 한 명의 진단 데이터인데, 'Chest Pain', 'Good Blood Circulation', 'Blocked Arteries' 의 유무(Yes / No) 를 가지고, 'Heart Desease' 를 예측하려고 한다.
이 때, 일반적으로 예측에 쓰이는 데이터 열들을 Feature 라고 하고, 예측하고자 하는 열을 Target 이라고 한다.

Decision Tree 는 
데이터의 Feature 들을 스무고개 처럼 하나씩 질문하여,
최종적으로 Target 을 예측하는 방법이다.

예를 들어, Chest Pain 이 있는가? 있다면, Good Blood Circulation 는 있는가? 그리고 Blocked Arteries는 있는가? 다 있다면 최종적으로, Heart Desease도 있다! 라고 예측하는 식이다.
Feature 들을 순차적으로 물어보고, 그에 따라 분기를 나누는 것(Yes 또는 No)이 특징이다. 이 모양이 마치 Tree 같다고 하여, 이름도 Decsion Tree 인 것이다.
한편, 이런 모델은 누군가에게 설명하기도 쉽다. 질문을 따라가고, 답을 하나씩 얻다보면, Tree 의 끝, 즉 Leaf 에 도달하게 되고, 여기서 최종적인 답을 얻을 수 있기 때문이다. 그저, 질문만 잘 따라가면 된다.

근데, 스무고개도 그렇지만, 늘 '질문'을 잘 해야한다.
즉, 어떤 Feature 순서로 먼저 질문할지에 선택함에 따라 최종예측이 달라진다.
예를 들어, 환자의 Chest Pain 을 물어보고 다음에 Good Blood Circulation 를 물어보는 것과
Good Blood Circulation 을 물어보고 Chest Pain 을 그 다음에 물어보는 것이 예측이 달라진다.
우리는 예측 모델을 만드는 것이므로, 잘 예측하는 것이 중요하고, 따라서, 물어볼 Feature 의 순서가 주 이슈가 된다.

그렇다면 물어볼 Feature의 순서는 어떻게 '잘' 정하는가?
다시 말하면, 어떤 방식으로 Decision Tree 를 만드는가?

2.2. Decision Tree 만드는 법 (Feature 순서 정하기)

한마디로 말해, Gini impurity 라는 것을 사용한다.

Gini impurity 는 다음의 예를 보면 대충 어떻게 계산되는지 알 수 있을 것이다.
먼저, Leaf Node의 Gini impurity는 다음과 같이 계산한다.

Leaf Node 의 Gini impurity = 1 - (yes 의 확률)^2 - (no 의 확률)^2

예를 들어, Chest Pain 으로 환자들을 Yes, No 로 분류하고, 분류된 환자들을 Heart Disease 로 또 최종 분류한다고 해보자.
그리고 그 결과가 다음과 같다고 하자.

그럼, Chest Pain 이라는 Feature 는 Heart Disease 의 유무를 판가름하는데 중요한 질문이었을까?
이를 수치화해서 표현해주는 것이 Gini impurity 이다.
먼저 왼쪽의 Leaf Node의 Gini impurity 를 계산하면 다음과 같다.

오른쪽의 Leaf Node의 Gini impurity 를 계산하면 다음과 같다.

정리하면, 두 Leaf Node 의 Gini Impurity 는 다음과 같다.

최종적으로, 이 Feature 의 Gini Impuritiy 를 계산해야 하는데, 이는 다음과 같이 계산한다.

해당 Feature 의 Gini Impurity = Yes Node(왼쪽) 의 Gini Impurity + No Node(오른쪽) 의 Gini Impurity

이 때, 두 Leaf Node 의 데이터 개수가 다름을 고려하여, weight average 를 곱해주어야 하는데,
구구절절 말하는 거보다, 식으로 그냥 빨리 이해하는게 나을 듯 싶다.

전체 데이터 144+159 를 해당 데이터 144와 159에 각각 나눠준 weight 값을 곱해주는 것을 볼 수 있다.
아무튼, 이렇게 해서 얻게된 Chest Pain 의 Gini Impurity 값은 0.364 이다.

이런식으로, 모든 Feature 들의 Gini Impurity 값을 구해보면 다음과 같다.

이 중, Good Blood Circulation 이 0.360으로 제일 낮은 Gini Impurity 값을 갖는 것을 알 수 있다.
따라서, 다음과 같이 이를 맨 처음 물어보는 Feature 로 둔다.

그리고, 이제 다음에 Chest Pain 을 물어볼지, 아니면 Blocked Arteries 를 물어볼지 결정해야 한다.
이 역시 지금 한 과정을 그대로 적용한다.
즉, Feature 의 Gini Impurity 를 계산하여, 작은 Gini Impurity 값을 갖는 Feature 를 다음 Node 의 질문 Feature 로 두면 된다.

Blocked Arteries 가 0.29 로 더 작으므로,

1. 다음에 Good Blood Circulation 을 가졌는가?
   • (Yes 인 경우) Blocked Arteries 을 가졌는가? 

순으로 Decision Tree 가 만들어진다.
그리고 최종적으로 다음과 같이 Chest Pain 의 유무를 물어보며, 한 쪽의 Leaft Node 까지 도달하게 된다.

한 쪽은 완성되었다.
아직 채워지지 않은 Node 중 하나를 보자.

이 경우, Chest Pain 으로 물어보는 것(분기를 나누는 것) 의 Gini Impurity (0.29) 보다, 안 물어보는 것이 Gini Impurity (0.2) 로 더 낮기 때문에, 안 나누는게 낫다고 본다. 따라서 저 자체가 Leaf Node 가 된다.

정확히는 다음의 규칙을 따라서 만든다.

1. 아직 질문하지 않은 Feature 의 Gini Impurity Score를 계산한다.
2. Feature 의 Gini Impurity Score 보다 Leaf Node 그 자체의 Gini Impurity Score 가 더 낮다면, 분기를 만들지 않고, 현재 Node 가 Leaf Node가 된다.
3. 2의 경우가 아니라면, Gini Impurity Score가 가장 낮은 Feature 로 분기를 나눈다.
4. Tree 가 완성될 때 까지 2,3 을 모든 Leaf Node 에 반복한다.

이러한 과정을 모든 Leaf Node 를 따라가며 모든 과정을 거치게 되면 다음과 같은 Tree Model 이 완성된다.

 

2.3. Regression 의 경우는 어떻게 할까?

지금까지는 Yes/No, 즉 Numeric Data 가 아닌 Binary Data 을 사용했다. 즉 Classfication 문제였다고 볼 수 있다.
그렇다면, Numeric Data 를 사용하여 Regression 문제일 경우는 어떻게 할까?

예를 들어, 환자의 weight 로 heart disease 를 예측해야 한다고 해보자.

이럴 때는 다음과 같이 진행한다.

1. 환자의 Weight 를 오름차순으로 정렬한다.
2. 환자와 그 다음 환자 Weight 사이의 평균 값을 구한다. 만약 10명 있다면 9개의 평균값을 구할 수 있다.
3. '이 값보다 큰가?' 가 일종의 질문(feature) 가 된다. 이 질문을 통해 Gini Impurity 를 구할 수있다.
4. 역시 가장 작은 Gini Impurity 순서대로 Tree 를 만든다.

1. 155와 180 사이 평균은 167.5 다. 이 값보다 큰지 작은지 물어본뒤, 해당 질문의 Gini Impurity 를 구한다.

2. 이런 식으로 구한, 각 질문들 중, Gini Impurity 가 가장 작은 질문을 먼저 질문하도록 Tree 를 만든다.

이렇게 최종적으로 다 만들고 나면, Yes or No 식의 질문이 아닌, < 159, < 200 등 부등식의 질문으로 Tree 의 Node 들을 채울 것이다.

3. 핵심 키워드

• Tree
• Gini Impurity (Leaf and Feature)