어렵고 복잡한 모델이 아닌 기본 트리모델이 성능이 더 좋은 경우가 있다. 

또 인기있는 부스팅 모델인 Light GBM, XG boost은 Tree모델을 고도화한 것이고,

나 또한 프로젝트에서 사용했던 모델이기에 다시 한 번 정확히 이해해보고자 StatQuest: Decision Trees를 보고 정리해봤다.

 

* 이 글은 StatQuest: Decision Trees를 보고 정리한 내용입니다. * 

 

0. Decision Tree

Decision Tree는 분류 규칙을 통해 데이터를 분류, 회귀하는 지도 학습 모델 중 하나이다.

한 번의 분기 때마다 변수 영역을 두 개로 구분하며, 질문이나 정답은 노드(Node)라고 불린다.

맨 처음 분류 기준을 Root Node,

중간 분류 기준을 Intermediate Node,

맨 마지막 노드를 Terminal Node 혹은 Leaf Node라고 한다.

 

결정 트리의 기본 아이디어는 Leaf Node가 가장 섞이지 않은 상태로 완전히 분류되는 것, 즉 복잡성(entropy)이 낮도록 만드는 것이다.

 

StatQuest: Decision Trees 에서는 Yes/No 데이터, 숫자 데이터 및 순위 데이터의 세 가지 데이터 유형에 대한 Decision Tree를 구축하는 방법을 보여준다.

 

1. 예시 (Classfication - Yes/No)

 행 하나하나가 환자 한 명의 진단 데이터인데, '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. Decision Tree 만드는 법 (Feature 순서 정하기)

리프 노드 중 어느 것도 100% "예" 또는 100% "아니오"가 아니기 때문에 모두 "impure" 한 것으로 간주된다.

루트 노드를 결정하려면 어떤 분리가 가장 좋은지 알고 싶다. 

즉, "impurity"를 측정하고 비교할 방법이 필요하다. → Gini Index 사용 

 

Leaf Node의 Gini impurity는 다음과 같이 계산한다.

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

Gini impurity (GI) = 1 — P(Yes)² — P(No)²

 

예를 들어, 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로 더 작으므로

  • 다음에 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 이 완성된다.

 

 

3. Regression의 경우는 어떻게 할까? (Numeric Data)

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

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

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

1. 환자의 Weight 를 오름차순으로 정렬한다.

2. 환자와 그 다음 환자 Weight 사이의 평균 가중치를 구한다.
   각 평균 가중치에 대한 Impurity를 계산한다.

3. '이 값보다 큰가?' 가 일종의 질문(feature) 가 된다. 이 질문을 통해 Gini Impurity 를 구할 수있다.

4. 역시 가장 작은 Gini Impurity 순서대로 Tree 를 만든다.

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

 

 

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

205는 GI가 가장 낮다. 따라서 이것은 가중치와 흉통/동맥 차단을 비교하는 데 사용하는 컷오프 및 Impurity 값이다.

 

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

 

4. Ranked data

Ranked data는 numeric data와 유사하지만, 가능한 모든 순위에 대한 impurity scores를 계산한다.

* 파란색, 빨간색 또는 녹색에 대한 불순물 점수는 모든 사람을 포함하므로 계산할 필요가 없다.

 

 

5. 한계

  1. 만약 샘플의 사이즈가 크면 효율성 및 가독성이 떨어진다.
  2. 과적합으로 알고리즘 성능이 떨어질 수 있다.
    • 이를 극복하기 위해서 트리의 크기를 사전에 제한하는 튜닝이 필요하다.
  3. 한 번에 하나의 변수만을 고려하므로 변수간 상호작용을 파악하기가 어렵다.
  4. 결정트리는 Hill Climbing 방식 및 Greedy 방식을 사용하고 있다.
    • 일반적인 Greedy 방식의 알고리즘이 그렇듯이 이 방식은 최적의 해를 보장하지는 못한다.
  5. 약간의 차이에 따라 (레코드의 개수의 약간의 차이) 트리의 모양이 많이 달라질 수 있다.
    • 두 변수가 비슷한 수준의 정보력을 갖는다고 했을 때, 약간의 차이에 의해 다른 변수가 선택되면 이후의 트리 구성이 크게 달라질 수 있다.
  6. 이 같은 문제를 극복하기 위해 등장한 모델이 바로 Random forest이다.
    • 같은 데이터에 대해 의사결정 나무를 여러 개 만들어 그 결과를 종합해 예측 성능을 높이는 기법이다.

 

 

마치며

지난 면접에서 Gini impurity, impurity에 대해 물어본 적이 있는데 제대로 답을 하지 못한 적이 있다. 사실 아직도 잘 이해가 안 되는 부분이 있어서, 다음엔 impurity에 대해 정리해보고자 한다.

 

 

 

 

티스토리툴바