ML_Decision Tree

📌 결정 트리 (Decision Tree)

📍 결정 트리

결정 트리는 예/아니오로 답할 수 있는 어떤 질문들이 있고, 그 질문들의 답을 따라가면서 데이터를 분류하는 알고리즘이다.

예를 들어 교통사고가 났을 때, 운전자의 생존 여부를 예측하고 싶다고 하자. 그러면 결정 트리는 다음과 같을 수 있다.

질문들에 답을 해가면서 한 단계식 내려갈 수 있고, 위에서부터 질문들에 계속 답을 하며 내려가다가 보라색 박스들에 도착을 하면 해당 분류 값을 리턴한다.

또한 결정 트리는 한 속성을 딱 한 번만 사용해야 되는 건 아니다. 예를 들어 '주행 속도'라는 속성이 있다고 할 때 아래처럼

속도가 100을 넘었는지, 60을 넘었는지 안 넘었는지 등등 하나의 속성으로 여러 개의 질문을 만들 수도 있다.

이처럼 하나의 시작 지점에서 퍼져나가는 모습이 마치 나무와 비슷하고, 한 단계 내려갈 때마다 왼쪽으로 갈지 오른쪽으로 갈지 선택하는 알고리즘이기 때문에 이름이 결정 트리인 것이다.

결정 트리 관련 용어는 아래와 같다.

일단 박스 하나하나를 '노드'라고 하는데, 가장 위에 있는 질문 노드는 나무의 뿌리라고 해서 root 노드라고 한다. 그리고 트리의 가장 끝에 있는 노드들은 leaf 노드라고 한다. leaf 노드는 항상 사망/생존과 같은 특정 예측값을 갖고 있고, 나머지 노드들은 예/아니오로 답할 수 있는 질문을 갖고 있다.

📍 지니 불순도(Gini Impurity)

선형 회귀 알고리즘의 목적이 학습 데이터를 가장 잘 나타낼 수 있는 일차식을 찾는 거였다면, 결정 트리의 목적은 학습 데이터를 직접 분류해보면서, 데이터들을 가장 잘 분류할 수 있는 노드(기준)들을 찾아내는 것이다. 즉, 결론적으론 최적의 트리 구조를 찾는 것이다.

최적의 트리 구조를 찾기 위해선 어떤 위치에 무슨 노드들이 있어야 좋고 나쁜지 즉, 좋고 나쁨의 판단 기준이 있어야 하는데 선형 회귀에서는 이걸 손실 함수를 통해서 했다면 결정 트리에서는 이걸 지니 불순도, 영어로는 Gini Impurity를 통해서 한다. (앤트로피(Entropy)로도 할 수 있다.)

지니 불순도는 데이터 셋 안에 서로 데이터들이 얼마나 섞여있는지를 나타낸다. 수식으로 나타내면 다음과 같다. ($C$는 클래스의 개수를 의미함.)

예를 들어 독감 데이터 셋 100개에서 독감인 데이터는 70개, 일반 감기인 데이터는 30개라고 하자. 그렇다면 지니 불순도는

가 될 것이다.

데이터 셋에서 독감인 데이터만 100개라면 데이터들이 섞여있지 않은 것이니 지니 불순도는 0이다. 지니 불순도가 낮다는 것은 데이터들이 하나의 분류에 집중돼있다는 것을 의미한다.
반대로 데이터가 정확하게 50개씩 반반 섞여있다면 지니 불순도는 0.5가 될 것이다. 이진 분류 기준으로 섞여있는 데이터 비율이 50:50일 때 지니 불순도는 최대가 된다.

정리하자면 지니 불순도가 작을수록 데이터 셋이 순수하고, 클수록 데이터 셋이 불순하다.

📍 결정 트리 노드 정하기

그러면 이제 지니 불순도를 이용해서 결정 트리의 노드를 정해보자.

일단 다음과 같은 독감 환자 데이터 셋이 있다고 가정하자.

데이터 셋은 보이는 것처럼 고열, 기침, 몸살이 있는지 없는지를 속성으로, 환자가 독감인지 아닌지를 목표 변수로 갖는다.
그리고 학습 데이터를 직접 한 번 분류해보면서 결정 트리를 만들어보고, 이 결정 트리를 써서 몸 상태로 독감이 있는지 없는지를 예측하려고 한다.

일단 결정 트리를 만들 때 처음에는 root 노드를 정해야 한다. root 노드가 될 수 있는 것은 무엇이 있을까?

• Case 1) 분류 노드를 바로 만든다.
  질문 노드를 만들지 않고 바로 분류 노드를 만들 수 있다. 예를 들어 처음부터 그냥 모든 데이터는 독감이다(or 일반 감기다)라고 할 수 있다.

• Case 2) 질문 노드를 만든다
  “고열이 있나요?”, “기침이 있나요?”, “몸살이 있나요?” 이 세 질문 중 하나를 노드로 만들어 분류해볼 수 있다.

이 선택지들 중 어떤 걸 골라야 될까? 결정 트리를 만들 때는 항상 현재 상황에서 가장 “좋은” 노드를 골라야 한다. 이때 “좋다/안 좋다”의 기준은 위에서 배운 지니 불순도를 활용한다.

일단 분류 노드를 바로 만드는 경우에 대해서 살펴보자.

💡Case 1) 분류 노드를 바로 만든다

root 노드를 분류 노드로 만든다고 가정하자.
일단 학습에 사용하는 데이터 수는 90개인데, root 노드는 가장 위에 있는 노드니까 모든 데이터가 거쳐야 되는 노드이므로 이 90개를 모두 사용한다.

학습 데이터는 아래와 같이 독감인 사람이 50명, 아닌 사람이 40명이 있다.

분류 노드를 했을 때 최대한 많은 데이터를 맞게 분류해야 좋은 것이다. 그 말은 여기 있는 모든 데이터 90개를 하나의 분류(독감 or 일반 감기)로 예측을 했을 때, 최대한 많이 맞아야 된다는 것이다.

일단 분류 노드를 만들 때는 항상 데이터 셋에서 가장 많은 분류로 만든다. 지금 같은 경우는 독감 데이터가 일반 감기 데이터보다 많기 때문에 독감 노드를 분류 노드로 고른다.

그럼 이 독감 노드는 정확히 얼마나 좋은 걸까?

좋은 독감 노드는 최대한 많은 학습 데이터를 맞출 수 있어야 하는데, 그러려면 이 데이터 셋 안에 처음부터 독감 데이터가 많아야한다. 다르게 표현하면 불순도가 낮은, 순수한 데이터 셋이어야 한다.

근데 독감 노드를 분류 노드로 설정했을 때 불순도를 계산해보면 0.494로 꽤 높은 편이다.

데이터가 불순할 때 처음부터 분류 노드로 만들면 성능이 별로 안 좋다는 것을 확인할 수 있다. 육안으로 봐도 전체 데이터 90개 중에 50개는 맞고 40개는 틀려버리는 셈이다.

따라서 분류 노드를 root 노드로 할 때는 데이터가 처음부터 잘 분류되어 있을 때 효과적이다.

💡Case 2) 질문 노드를 만든다

여러 질문 노드 중 “고열이 있나요?”로 노드로 만드는 경우를 생각해보자. 결정 트리에서 좋은 질문은 데이터를 잘 나누는 질문이다.

만약 “고열이 있나요?”로 데이터를 나눴을 때, 정확하게 독감과 일반 감기를 분류했다면 이 질문 노드는 데이터를 엄청 잘 나누는 좋은 노드이다. 그림으로 보면 아래와 같다.

근데 만약 아래 그림처럼 나뉜 데이터에 다시 독감과 일반 감기가 많이 섞여 있다면 그 질문 노드는 데이터를 잘 분류하지 못하는 것이므로 좋지 않은 노드이다.

정리하자면 좋은 질문 노드는 섞여있는 데이터를 잘 나눠서 점점 더 분류하기 쉽게 만들어 주고, 또 나뉜 데이터 셋들의 지니 불순도가 낮을수록 좋은 질문 노드이다.

그러면 질문 노드의 성능을 수치적으로 평가해보자.
먼저 “고열이 있나요?”로 데이터를 나눴을 때, 다음과 같이 분류가 되었다고 가정하자.

고열이 있는 사람들로 분류된 데이터셋 50명 중에서 독감인 사람은 40명, 일반 감기인 사람은 10명이다. 지니 불순도를 계산해보면 0.32가 나온다.

고열이 없는 사람들로 분류된 데이터셋 40명 중에서 독감인 사람은 10명, 일반 감기인 사람은 30명이다. 지니 불순도를 계산해보면 0.375가 나온다.

각각 지니 불순도를 계산했으므로 이걸 평균내어 계산하면 “고열이 있나요?”라는 질문 노드의 성능을 수치화 할 수 있다.

평균을 낼 때 각 지니 불순도에 해당 데이터의 크기만큼을 가중치로 준 뒤 이들을 모두 더하고, 그걸 전체 데이터 셋으로 나누면 된다.
이렇게 해서 계산한 “고열이 있나요?” 질문으로 나눠진 데이터 셋들의 평균 지니 불순도는 약 0.344가 된다. 즉, 이 질문이 얼마나 데이터를 잘 나누는지를 수치를 나타내면 0.344라는 것이다. 이 평균 지니 불순도는 낮을 수록 좋고, 높을 수록 좋지 않다.
이 과정을 하나의 그림 안에 담으면 아래와 같다.

💡노드 정하기

위에서는 분류 노드를 사용했을 때와 질문 노드를 사용했을 때의 지니 불순도를 측정했었다. 이제 root 노드를 고르기 위해서는 이 모든 경우들 중에서 지니 불순도가 가장 낮게 나오는 노드를 선택해주면 된다.
일단 위에서는 “고열이 있나요?” 질문 노드에 대한 지니 불순도만 계산해주었는데 나머지 질문들에 대한 지니 불순도도 계산하고 모든 경우들을 함께 보면 아래와 같다.

여기서 지니 불순도가 가장 낮은 것은 “몸살이 있나요?” 질문이다. 따라서 이걸 root 노드로 골라주면 된다.

각 경우 별로 지니 불순도가 낮다는 것의 의미를 정리해보면:

• 분류 노드의 불순도가 가장 작으면 이미 데이터가 잘 나눠져 있기 때문에 있는 그대로 분류해도 된다는 뜻이고,

• 질문 노드의 불순도가 가장 작으면 질문을 통해서 지금 있는 데이터 셋보다 불순도를 더 낮출 수 있다는 뜻이다.

📍 결정 트리 완성하기

이제 나머지 노드들도 위에서 봤던 방법들 그대로 적용해가면 된다. 위에서 root 노드를 “몸살이 있나요?”로 했으니 그 다음 상황은 다음과 같다.

위에 보이다시피 몸살이 있냐는 질문에 '예'라고 답하고 난 후 다시 노드를 정할 때는 학습 데이터가 몸살이 있는 데이터들로 만 구성되어 있다. 바뀐 이 데이터들로 다시 이전에 했던 지니 불순도 비교 과정을 거치면 된다.

만약 몸살이 있는 60명의 사람들 중에 독감인 사람은 50명, 일반 감기인 사람은 10명이라고 하자. 그리고 독감인 사람이 더 많으니 몸살이 있는 데이터는 모두 독감이 있다고 분류해보자. 즉, 독감을 분류 노드로 해보자.
이 때의 지니 불순도를 계산해보면 0.278이 나온다.

다음은 고열이 있는지를 이용해서 나눴을 때와, 기침이 있는지를 이용해서 나눴을 때의 불순도를 계산해보자. 순서대로 0.270, 0.3이 나온다.

비교해봤을 때, '고열이 있나요?'를 질문 노드로 사용했을 때가 가장 지니 불순도가 낮다. 그러니 이 질문을 노드로 만들어주면 되는 것이다. 이제 결정 트리는 다음과 같을 것이다.

방금했던 이 과정을 트리의 맨 끝에 있는 leaf 노드들이 모두 분류 노드가 될 때까지 반복해 주면 결정 트리를 만들 수 있다.

💡결정 트리 깊이

트리가 몇 층까지 내려가는지를 트리의 깊이라고 표현하는데, '깊이 3 이상 내려가지 마라!' 이렇게 정해줄 수도 있다.

이럴 땐 그냥 특정 깊이까지 내려오면 더 이상 지니 불순도를 비교하지 않고 분류 노드를 만든 뒤에 끝내면 된다.
예를 들어 고열이 있는 데이터 셋에서 독감인 사람이 더 많다면 독감 노드로 끝내면 되고, 고열이 없는 데이터 셋에서 일반 감기가 더 많다면 그곳은 일반 감기 노드로 끝내면 된다.

💡속성이 숫자형일 때 질문 노드

지금까지 본 속성들은 모두 참 거짓으로 바탕한 불린형 데이터였다. 그렇기 때문에 그냥 “고열이 있나요?” 이렇게 할 수 있는 질문이 하나밖에 없었다.

하지만 아래 표에서 데이터가 가장 왼쪽 체온 속성처럼 숫자형으로 있는 경우에는 만들 수 있는 질문이 엄청 많다.

예를 들어 체온이 “37.1도를 넘나요?”, 체온이 “37.2도를 넘나요?”, 체온이 “37.3도를 넘나요?” 이렇게 끝도 없이 질문이 많을 수 있다.

이렇게 하나의 속성에서 만들 수 있는 수많은 질문들 중에 하나를 고르는 방법은 무엇인지 알아보자.

가장 먼저는 체온 데이터를 정렬시킨다. 그럼 체온이 낮은 거부터 높은 순서대로 데이터가 정렬된다. 그 다음에는 연속된 체온 데이터끼리 평균을 계산한다. 그리고 계산된 이 평균 체온들을 이용해서 질문들을 하나씩 만들어본다.

그 후 이 질문들에 대해서 지니 불순도를 계산한다. 그러니까 그 평균 체온을 기준으로 삼았을 때 데이터가 얼마나 잘 분류됐는지를 전부다 계산해 주는 것이다.

그렇게 해서 이 중에서 가장 지니 불순도가 낮은 질문이 있을 텐데, 예를 들어서 체온이 37.5를 기준으로 나눴을 때가 가장 지니 불순도가 낮다고 하자. 그럼 체온 속성 관련 질문 노드를 만들 때 대표로 “체온이 37.5가 넘나요?”를 사용하면 된다.

그럼 이제 노드를 선택할 때는 “37.5가 넘나요?”, “몸살이 있나요?”, “기침이 있나요?” 이 세 질문 노드들과 분류 노드들 중 가장 지니 불순도가 낮은 거를 선택하면 된다.

주의할 점은 다음 노드를 만들 때 만들어 놓은 “37.5가 넘나요?”라는 대표 질문 노드를 재사용하는 건 아니다. 매번 노드를 만들 때마다 위에서 했던 거처럼 해당 노드까지 오는 학습 데이터에 대해서 가장 좋은 체온 질문을 또다시 찾아내야 한다.

📍 속성 중요도

결정 트리의 장점은 다음과 같다.

• 직관적이다.
• 해석하기 쉽다.

여기서 해석한다는 것은 머신러닝에서 예측을 하는 데 있어서 어떤 속성들이 좀 더 중요하게 사용됐고, 어떤 것들이 좀 덜 중요하게 사용됐는지... 이런 걸 알아낸다는 것이다.

그럼 그 속성들의 중요도를 계산하는 방법에 대해서 알아보자.

속성들의 중요도를 계산하기 위해서는 우선 각 노드 하나하나의 중요도를 계산해야 한다. 노드 중요도 (Node Importance) $NI$는 다음과 같이 계산한다.

$n$은 중요도를 계산하려는 노드까지 오는 학습 데이터의 수이고, $GI$는 이 노드까지 오는 데이터 셋의 불순도, 그리고 $m$은 전체 학습 데이터의 수이다.
먼저 계산하려는 노드까지 오는 학습 데이터 수 $n$이랑 불순도 $GI$를 곱한 후, 총 데이터 수 $m$으로 나눠준다.
그리고 중요도를 계산하려는 노드의 왼쪽 자식 노드, 오른쪽 자식 노드에서도 똑같이 계산을 한다. 그리고 중요도를 계산하려는 노드의 계산 값에서 나머지 두 노드의 계산 값을 빼면 된다.

예시는 다음과 같다.
전체에 학습 데이터는 90개고, root 노드의 중요도를 계산한다고 해보자.

이걸 이용해서 root 노드(주황색 박스)의 중요도를 계산해 보면 아래와 같다.

노드 중요도는 정확히 무엇을 수치화 한 것일까? 노드 중요도를 계산하는 식을 다시 보면 아래와 같았다.

중요도를 계산하려는 노드의 불순도에서 그 노드 아래 노드들(왼쪽, 오른쪽)의 불순도를 뺀 거고, 각 항에 해당 노드들까지 가는 데이터의 비율을 맞춰준 거다.

생각해보면 이건 한 노드에서 데이터를 두 개로 나눴을 때, 데이터 수에 비례해서 불순도가 얼마나 줄어들었는지를 계산하는 것이다.

즉, 특정 노드가 얼마나 중요한 노드인지를 판단할 때, 이 노드 전후로 불순도가 얼마나 낮아졌는지를 보는 것이다. 따라서 $NI$는 높을 수록 좋다.

불순도가 낮아질수록 나눠지는 데이터 셋들에서 점점 독감 또는 일반 감기 데이터 중 하나의 비율이 많아지는데, 이는 나눠지는 데이터 셋들에 대해서 점점 더 알아간다, 또는 "더 많은 정보를 얻는다"라고 해서 이 수치를 정보 증가량, 영어로는 Information Gain (IG)라고도 부른다. (개념적 유사)

정리하면

• $NI$ = 분할 전 지니 - 분할 후 가중 평균 지니
• $IG$ = 분할 전 엔트로피 - 분할 후 가중 평균 엔트로피

이제 노드 중요도에 대해서 배웠으니 결정 트리의 모든 노드들에 대해서 노드 중요도를 계산한다.

이걸 써서 특정 속성이 얼마나 중요한지를 계산할 수 있다. 계산하는 방법은 아래와 같다.

고열이 얼마나 중요한지 알고 싶다고 하자. 고열 질문을 갖는 모든 노드의 중요도를 더하고 트리 안에 모든 노드의 중요도의 합으로 나눠준다.

기침이 얼만큼 중요한지 알고 싶으면, 기침 질문을 갖는 모든 노드의 중요도를 더하고 트리 안에 모든 노드의 중요도 합으로 나눠준다.

몸살이 얼마나 중요한지 알고 싶으면 몸살 노드들의 중요도를 더해서 모든 노드의 중요도 합으로 나누면 된다.

쉽게 생각하면, 모든 노드가 데이터를 양 갈래로 나누면서 나누는 데이터 셋들의 지니 불순도를 낮추는데, 전체적으로 낮춰진 불순도(모든 노드 중요도 합)에서 특정 속성 하나(~질문 노드 중요도 합)가 낮춘 불순도가 얼마나 되는지를 계산한 것이다.

특정 속성을 질문으로 갖는 노드들의 중요도들을 평균낸 거랑 비슷한데, 그렇기 때문에 이렇게 최종적으로 구한 값을 속성의 평균 지니 감소 (Mean Gini decrease)라고 부르기도 한다.

각 속성의 평균 지니 감소를 이용하면, 특정 속성이 결정 트리 안에서 평균적으로 얼마나 불순도를 낮췄는지를 계산할 수 있고, 이게 있으면 결정 트리 안에서 그 속성이 얼마나 중요한지를 판단할 수 있는 것이다.

결정 트리 실습 코드는 아래와 같다.

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier

import matplotlib.pyplot as plt
import numpy as np
import pandas as pd

# 데이터 준비
iris_data = load_iris()

X =pd.DataFrame(iris_data.data, columns=iris_data.feature_names)
y = pd.DataFrame(iris_data.target, columns=['Class'])

# 결정 트리 사용
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=5)

model = DecisionTreeClassifier(max_depth=4) # 결정 트리의 최대 깊이 설정
model.fit(X_train, y_train)

model.predict(X_test)
model.score(X_test, y_test) # 성능 평가 -> 결과: 0.9

# 속성 중요도 보기
importances = model.feature_importances_
indices_sorted = np.argsort(importances)

plt.figure()
plt.title("Feature Importances")
plt.bar(range(len(importances)), importances[indices_sorted])
plt.xticks(range(len(importances)), X.columns[indices_sorted], rotation=90)
plt.show()

결과:

---

출처: 코드잇