결정트리(의사결정나무, Decision Trees)

yuns_u·2021년 8월 17일

Decision Tree = 한 번에 하나의 설명변수를 사용하여 예측 가능한 규칙들의 집합을 생성하는 알고리즘

🌲 결정트리

데이터를 분석하여 이들 사이에 존재하는 패턴을 예측 가능한 규칙들의 조합으로 나타내며, 그 모양이 ‘나무’와 같다

root node: 뿌리마디
decision node(intermediate node): 중간마디
terminal node: 끝마디

초기지점은 root node이고 분기가 거듭될수록 그에 해당하는 데이터의 개수는 줄어든다. 각 terminal node에 속하는 데이터의 개수를 합하면 root node의 데이터수와 일치합니다. 즉, terminal node 간에는 교집합이 없다.

한편 terminal node의 개수는 분리된 집합의 개수이다. 예컨대 위 그림처럼 terminal node가 5개라면 전체 데이터가 3개의 부분집합으로 나눠진 셈이다.

결정트리는 분류(classification)과 회귀(regression)에 모두 적용 가능하다. 범주형이나 연속형 수치 자료 모두 예측할 수 있다는 것이다.
결정트리는 데이터를 분할해 가면서 범주를 예측한다.

[분류]
새로운 데이터가 특정 terminal node에 속한다는 정보를 확인한 뒤, 해당 terminal node에서 가장 빈도가 높은 범주에 새로운 데이터를 분류하게 된다. 날씨가 맑고 습도가 70 미만일 때 운동경기가 열린다고 한다면 날씨가 맑고 습도가 90인 경우 운동경기가 열리지 않을 것이라고 예측하는 것이다.

이처럼 분류 과정은 새로운 데이터가 특정 말단 노드에 속한다는 정보를 확인한 뒤 말단노드의 빈도가 가장 높은 범주로 데이터를 분류하는 것이다.

[회귀]
회귀의 경우 해당 terminal node의 종속변수(y)의 평균을 예측값으로 반환하게 되는데, 이 때 예측값의 종류는 terminal node의 개수와 일치하게 된다. 만약 terminal node가 3개라면 새로운 데이터가 몇 개가 들어온다고 해도 결정트리는 3가지의 답만을 출력하게 된다. 인구가 80억명이지만 MBTI는 16가지로 분류되기 때문에 20명의 MBTI를 구한다고해도 16가지의 답들 중에서 나올 것이고, 80억명의 MBTI를 구한다고해도 16가지의 답들 중에서 나올 것이다.

데이터를 분할한다는 것

결정트리를 학습하는 것은 노드를 어떻게 분할하는가에 대한 문제이다.
노드를 분할하는 기준이 불순도를 작게 만드는, 즉 데이터를 잘 구분하는 feature가 기준점이 될 수 있다. 분할에 사용할 특성이나 분할지점(값)은 타겟변수를 가장 잘 구별해 주는(불순도의 감소가 최대가 되는, 정보획득이 가장 큰)것을 선택한다.

노드 분할 방법에 따라 다른 모양의 트리구조가 만들어지게 될 것이다. 결정트리의 비용함수를 정의하고 그것을 최소화하도록 분할하는 것이 트리모델 학습 알고리즘이다. 트리모델의 학습 알고리즘으로 분순도를 측정하는 gini impurtiy와 entropy 등이 있다.

🌲 정보획득

결정트리는 구분 뒤 각 영역의 순도(homogeneity)가 증가, 불순도(impurity) 혹은 불확실성(uncertainty)이 최대한 감소하도록 하는 방향으로 학습을 진행한다.

정보획득(information gain): 불순도가 줄어드는 것을 정보이론에서는 정보획득이라고 한다. 특정한 특성을 사용해 분할했을 때 엔트로피의 감소량이라고 할 수 있다.

$IG(T,a)=\mathrm {H} {(T)}-\mathrm {H} {(T|a)}$
= 분할 전 노드 불순도 - 분할 후 자식노드 들의 불순도

🌲 불순도/불확실성

불순도를 계산하는 3가지 지표는 아래와 같다. 이 중 많이 쓰이는 지표는 엔트로피와 지니 불순도로, 엔트로피는 더 안정적이고 지니 불순도는 더 빠른 계산이 가능하다는 장점이 있으며 가장 보편적으로 쓰이는 지표는 엔트로피이다.

엔트로피(entropy)

$\mathrm {H} (T)=\operatorname {I} _{E}\left(p_{1},p_{2},...,p_{J}\right)=-\sum _{i=1}^{J}{p_{i}\log _{2}p_{i}}$

J 개의 레코드가 속하는 T 영역에 대한 엔트로피는 위와 같이 설명할 수 있다.
$p_i$ 는 T 영역에 속하는 데이터 가운데 i 범주에 속하는 데이터의 비율

지니 불순도(gini impurity, gini index)

${I}_{G}(p)=\sum _{i=1}^{J}p_{i}(1-p_{i})=1-\sum _{i=1}^{J}{p_{i}}^{2}$

오분류오차(misclassification error)

불순도를 측정할 수 있긴 하나 나머지 두 지표와 달리 미분이 불가능한 점 때문에 자주 쓰이지는 않는다.

파이썬으로 구현하기

sklearn.tree.DecisionTreeClassifier

파이프라인을 사용하면 파이프라인 코드에서 분류기만 바꾸어 주면 된다.
결정트리에서는 StandardScaler는 도움이 되지 않기 때문에 제외하고 학습하는 것이 효율적이다.

from sklearn.tree import DecisionTreeClassifier

pipe = make_pipeline(
    OneHotEncoder(use_cat_names=True),  
    SimpleImputer(), 
    DecisionTreeClassifier(random_state=1, criterion='entropy')
)

pipe.fit(X_train, y_train)
print('훈련 정확도: ', pipe.score(X_train, y_train))
print('검증 정확도: ', pipe.score(X_val, y_val))

결정트리 시각화

결정트리가 너무 크면 한 눈에 보기 어렵기 때문에 max_depth를 3으로 한정시켰다.

# graphviz 설치방법: conda install -c conda-forge python-graphviz
import graphviz
from sklearn.tree import export_graphviz

model_dt = pipe.named_steps['decisiontreeclassifier']
enc = pipe.named_steps['onehotencoder']
encoded_columns = enc.transform(X_val).columns

dot_data = export_graphviz(model_dt
                          , max_depth=3
                          , feature_names=encoded_columns
                          , class_names=['no', 'yes']
                          , filled=True
                          , proportion=True)


display(graphviz.Source(dot_data))

과적합 해결하기

복잡한 트리는 과적합 가능성을 높이기 때문에 복잡도를 낮추어 일반화를 유도할 수 있다. 복잡한 트리일수록 특정한 값을 선정하기 때문에 과적합을 일으킬 확률이 높다고 할 수 있다.

아래는 결정트리에서 과적합을 해결하는 데에 많이 쓰이는 방법들이다.

min_samples_split
min_samples_leaf
max_depth

min_samples_leaf를 사용하하면 말단 노드(external node)에 최소한 존재해야 하는 샘플들의 수를 정해줄 수 있다.

pipe = make_pipeline(
    OneHotEncoder(use_cat_names=True), 
    SimpleImputer(), 
    DecisionTreeClassifier(min_samples_leaf=10, random_state=2)
)

pipe.fit(X_train, y_train)

Feature Importance

선형모델에서는 특성과 타겟의 관계를 확인하기 위해 회귀 계수(coefficients)를 살펴보았다. 하지만 결정트리에서는 특성과 타겟의 관계를 확인하기 위해 특성중요도를 확인할 수 있습니다.

회귀계수와 달리 특성중요도는 항상 양수값을 가진다. 이 값을 통해 특성이 얼마나 일찍 그리고 자주 분기에 사용되는지 결정됩니다.

model_dt = pipe.named_steps['decisiontreeclassifier']

importances = pd.Series(model_dt.feature_importances_, encoded_columns)
plt.figure(figsize=(10,30))
importances.sort_values().plot.barh();