결정 트리(decision tree)는 의사 결정 규칙과 그 결과들을 트리 구조로 도식화한 의사 결정 지원 도구의 일종이다. - 위키백과 (결정 트리)
결정 트리 학습법(decision tree learning)은 어떤 항목에 대한 관측값과 목표값을 연결시켜주는 예측 모델로서 결정 트리를 사용한다. 이는 통계학과 데이터 마이닝, 기계 학습에서 사용하는 예측 모델링 방법 중 하나이다. 트리 모델 중 목표 변수가 유한한 수의 값을 가지는 것을 분류 트리라 한다. 이 트리 구조에서 잎(리프 노드)은 클래스 라벨을 나타내고 가지는 클래스 라벨과 관련있는 특징들의 논리곱을 나타낸다. 결정 트리 중 목표 변수가 연속하는 값, 일반적으로 실수를 가지는 것은 회귀 트리라 한다. - 위키백과 (결정 트리 학습법)
결정 트리는 스무고개 같은 것으로 생각하면 간단하다. 어떠한 대상(표본의 특성)에 대하여 첫 질문(뿌리 노드)을 시작으로 여러 질문들(중간 노드, internal node)을 거쳐 마지막 질문(말단 노드, terminal node, leaf)을 끝으로 최종 답(타겟 예측 값)을 낸다.
다만 스무고개는 질문 횟수 20번으로 규칙이 정해져 있지만, 결정 트리는 사용자가 설정하기에 따라 20번보다 더 많을 수도, 적을 수도 있다. 여기서 이 질문 횟수를 결정 트리의 깊이(depth)라고 한다.
이름이 트리(Tree)인 이유는 말 그대로 나무처럼 생겨서 그렇다. 아래와 같이 생겼다.
출처 : 결정 트리 학습법 - 위키백과
위 예시에서 맨 위 '남자인가?'가 결정 트리의 시작점인 뿌리 노드(root node)이다. 빨강('사망')과 초록('생존')색에 아래로 더 이어진 것이 없는 것들은 말단 노드(external node, terminal node, leaf)라고 한다. 그리고 뿌리 노드와 말단 노드 사이에 있는 노드가 중간 노드(internal node)이다. 노드와 노드 사이를 연결하는 선들은 엣지(edge)라고 한다.
결정 트리 학습 알고리즘
선형 모델에서는 MSE, MAE 등을 비용 함수(Cost function)로 하여 이를 최소화한 모델을 만드는 것이 목적이었다. 결정 트리에서도 비용 함수 역할을 하는 것이 있는데, 바로 지니 불순도(Gini impurity)와 엔트로피(Entropy)이다.
지니 불순도
'불순도'라는 이름 그대로 불순물이 얼마나 섞여 있는지를 나타낸다. 여기서 불순물과 불순물이 아닌 것의 기준은 그곳에 무엇이 더 많이 있는가이다. 즉, 더 많은 것이 주인이고 적은 쪽이 불순물이다.
지니 불순도를 계산하는 식은 다음과 같다.
지니불순도(Gini Impurity or Gini Index): $$I_G(p)=\sum_{i=1}^{J} p_i(1-p_i)=1-\sum _{i=1}^{J}{p_i}^2$$ 여기서 p는 주인이 차지한 영역의 비율(달리 말하면 확률)이다.
만약 불순물이 최대, 즉 반반 치킨처럼 반반이라면 지니 불순도는 0.5이다. 반대로 모든 것이 같은, 즉 순수한 후라이드 또는 양념 치킨이라면 지니 불순도는 0이다.
조금 더 구체적인 예를 들어보겠다. 결정 트리의 어느 노드에 와서 보니 빨간 휴지가 50개, 파란 휴지가 30개라고 한다. 이때 이 노드에서의 지니 불순도는 $$1 - ( (\frac{50}{50+30})^2 + (\frac{30}{50+30})^2 ) = 0.46875$$ 이다.
엔트로피
엔트로피도 지니 불순도처럼 높으면 불순물이 많고 낮으면 적은 것이다.
지니 불순도와의 차이점으로 엔트로피는 최대 1(반반), 최소 0(순수)이다.
정보 획득(Information Gain) : 결정 트리에서 어떤 특성을 사용해 분할을 했을 때 엔트로피가 감소하는 양을 뜻한다. 예시는 아래와 같다.
자식 노드의 가중 평균 엔트로피 = $\frac{17}{30}*0.787 + \frac{13}{30}*0.391 = 0.615$ ∴ IG = 부모 엔트로피 - 자식 노드의 가중 평균 엔트로피 = 0.996 - 0.615 = 0.38
특성 중요도
선형 모델에서는 각 특성별로 타겟에 얼마나 영향을 주는지를 회귀 계수(Coefficient)로 표현하였다. 결정 트리에도 이와 비슷한 역할로 특성 중요도(Feature importance)가 있다.
이름 그대로 타겟 값을 구하는 과정에서 각 특성이 얼마나 중요한지를 나타낸 것으로, 구체적으로는 해당 특성이 얼마나 일찍 그리고 자주 트리의 분기에 사용되는지 결정한다.
회귀 계수와 다른 점으로 특성 중요도는 항상 양수값이다.
결정 트리의 특징
결정 트리는 회귀 문제와 분류 문제 모두에 대하여 사용 가능하다.
결정 트리는 분류 과정을 직관적으로 확인이 가능하다.
선형 모델과 달리 비선형, 비단조$^*$$^1$, 특성 상호 작용$^*$$^2$ 특징을 가진 데이터 분석이 가능하다.
결정 트리는 위와 같은 장점들이 있다. 그러나 훈련 데이터의 일반화가 제대로 되지 않으면 너무 복잡한 결정 트리가 되는 문제가 있는데, 한 마디로 과적합(Overfitting) 문제가 있다.
결정 트리 과적합 문제
scikit-learn의 DecisionTreeClassifier 또는 DecisionTreeRegressor를 이용하면 결정 트리 모델을 만들 수 있다. 이 둘에는 결정 트리의 과적합을 줄일 수 있는 파라미터들로 다음과 같은 것들이 있다.
max_depth : 결정 트리의 최대 깊이를 제한한다. 만약 제한을 하지 않을 경우 트리는 모든 말단 노드가 순수(불순도가 0)해질 때가지 분기를 만들 것이고, 이는 과적합 문제를 발생시킬 수 있다.
min_samples_split : 노드가 분할하기 위해서 필요한 최소한의 표본 데이터 수를 설정한다. 이를 통해 아주 적은 데이터만 있어도 노드가 분할하는 것을 막아 과적합을 줄일 수 있다. 만약 설정하지 않으면 작은 분기가 많이 만들어져 과적합 문제가 발생할 수도 있다.
min_samples_leaf : 말단 노드가 되기 위해서 필요한 최소한의 표본 데이터 수를 설정한다. 설정한 숫자보다 적은 데이터 수를 가진 노드가 생성되는 것을 막아 과적합 문제를 줄인다. 이를 설정하지 않으면 아주 적은 데이터로도 말단 노드가 생성되어 과적합 문제가 생길 수 있다.
결정 트리는 어떻게 하는거지?
위에서 언급한 scikit-learn의 DecisionTreeClassifier를 통해서 결정 트리를 만들어보겠다.
1) 데이터 불러오기 및 전처리
import pandas as pd
from sklearn.model_selection import train_test_split
target = 'vacc_h1n1_f'
train = pd.merge(pd.read_csv('https://ds-lecture-data.s3.ap-northeast-2.amazonaws.com/vacc_flu/train.csv'),
pd.read_csv('https://ds-lecture-data.s3.ap-northeast-2.amazonaws.com/vacc_flu/train_labels.csv')[target], left_index=True, right_index=True)
test = pd.read_csv('https://ds-lecture-data.s3.ap-northeast-2.amazonaws.com/vacc_flu/test.csv')
sample_submission = pd.read_csv('https://ds-lecture-data.s3.ap-northeast-2.amazonaws.com/vacc_flu/submission.csv')
import numpy as np
def engineer(df):
"""특성을 엔지니어링 하는 함수입니다."""
# 높은 카디널리티를 가지는 특성을 제거
selected_cols = df.select_dtypes(include=['number', 'object'])
labels = selected_cols.nunique() # 특성별 카디널리티 리스트
selected_features = labels[labels <= 30].index.tolist() # 카디널리티가 30보다 작은 특성만 선택합니다.
df = df[selected_features]
# 새로운 특성 생성
behaviorals = [col for col in df.columns if 'behavioral' in col]
df['behaviorals'] = df[behaviorals].sum(axis=1)
dels = [col for col in df.columns if ('employment' in col or 'seas' in col)]
df.drop(columns=dels, inplace=True)
return df
train = engineer(train)
val = engineer(val)
test = engineer(test)
∴ 결정 트리의 훈련 정확도는 99가 넘는데 검증 정확도는 타겟의 다수 범주(0) 비율과 거의 똑같다. 즉, 과적합 상태이다.
3) 과적합 해결하기
# max_depth 설정을 통해 과적합 줄이기
pipe = make_pipeline(
OneHotEncoder(use_cat_names=True),
SimpleImputer(),
DecisionTreeClassifier(max_depth=6, random_state=2)
)
pipe.fit(X_train, y_train)
print('훈련 정확도', pipe.score(X_train, y_train))
print('검증 정확도', pipe.score(X_val, y_val))
훈련 정확도 0.8283367434688491 검증 정확도 0.8269481674771676
# min_samples_leaf 설정을 통해 과적합 줄이기
pipe = make_pipeline(
OneHotEncoder(use_cat_names=True),
SimpleImputer(),
DecisionTreeClassifier(min_samples_leaf=10, random_state=2)
)
pipe.fit(X_train, y_train)
print('훈련 정확도', pipe.score(X_train, y_train))
print('검증 정확도', pipe.score(X_val, y_val))
훈련 정확도 0.8577528689618361 검증 정확도 0.8029889692800379
∴ 과적합을 줄이기 위한 파라미터를 넣지 않았을 때와 비교하면 훈련 정확도는 낮아졌지만 검증 정확도는 높아졌다. 이전보다 과적합이 줄어들었다. 위 예시에는 담지 않았지만, min_samples_split 또한 비슷한 결과를 얻을 수 있다.
4) 특성 중요도 구하기
# 특성 중요도가 높은 순서대로 그래프에 표시하기
model_dt = pipe.named_steps['decisiontreeclassifier']
enc = pipe.named_steps['onehotencoder']
encoded_columns = enc.transform(X_val).columns
# DecisionTreeClassifier의 feature_importances_ 속성을 통해 특성 중요도를 알 수 있음
importances = pd.Series(model_dt.feature_importances_, encoded_columns)
plt.figure(figsize=(10,30))
importances.sort_values().plot.barh();
지면 관계상 일부 생략
*1 비단조(non-monotonic)란?
'단조(monotonic)'라는 말의 뜻을 알면 비단조는 바로 알 수 있다. 보통 일상 생활에서 '단조(單調)롭다'라는 말에서의 '단조'와 같은 '단조(單調)'이다.
수학적인 의미의 '단조'는 간단하게 말하면 계속해서 증가 혹은 감소하는 상태를 말한다. 중간에 올라가다가 내려가거나, 내려가다가 올라가지 않고 그냥 꾸준히 계속해서 상승 또는 하강하는 것이다.
*2 특성 상호 작용? 특성 상호 작용이란 특성 둘 이상이 만나면 타겟에 각자가 갖고 있던 영향만 끼치는 것이 아니라 여기에 추가적인 영향이 생기는 것으로 이해할 수 있다. 선형 회귀 모델의 경우 이러한 특성 상호 작용이 있으면 모델 성능이 떨어질 수 있으나, 결정 트리는 그렇지 않다. 구체적인 예시를 보겠다.
# 선형 회귀 모델
from sklearn.linear_model import LinearRegression
linear = LinearRegression()
linear.fit(X_house, y_house)
print('R2: ', linear.score(X_house, y_house))
print('Intercept: ', linear.intercept_[0])
print('Coefficients')
pd.DataFrame(columns=cols[:2], data=linear.coef_)
R2: 1.0 Intercept: 150000.0 Coefficients
location
size
0
50000.0
100000.0
# 회귀 트리 모델
import graphviz
## jupyterlab 사용시: jupyter labextension install @jupyter-widgets/jupyterlab-manager
from ipywidgets import interact
from sklearn.tree import DecisionTreeRegressor, export_graphviz
# 트리구조 그리는 함수
def show_tree(tree, colnames):
dot = export_graphviz(tree, feature_names=colnames, filled=True, rounded=True)
return graphviz.Source(dot)
from sklearn.tree import DecisionTreeRegressor
tree = DecisionTreeRegressor(criterion="mae")
tree.fit(X_house, y_house)
print('R2', tree.score(X_house, y_house))
show_tree(tree, colnames=X_house.columns)
R2 1.0
good and big 인 경우 +100,000 규칙 추가(특성상호작용)
y_house.loc[0, 'price'] = 400000
y_house
price
0
400000
1
200000
2
250000
3
150000
# 선형 회귀 모델
# 특성 상호 작용이 있는 경우 $R^2$ 점수가 떨어짐(성능 감소)
linear = LinearRegression()
linear.fit(X_house, y_house)
print('R2: ', linear.score(X_house, y_house))
print('Intercept: ', linear.intercept_[0])
print('Coefficients')
pd.DataFrame(columns=cols[:2], data=linear.coef_)
# 회귀 트리 모델
# 특성 상호 작용이 있어도 트리 모델의 성능은 그대로임
tree = DecisionTreeRegressor(criterion="mae")
tree.fit(X_house, y_house)
print('R2', tree.score(X_house, y_house))
show_tree(tree, colnames=X_house.columns)
