[라이트 머신러닝] Session 9. 결정 트리 학습

 이번 세션에서는 모델의 결정 과정을 설명할 때 아주 중요한 결정 트리(decision tree) 분류기라는 모델을 소개해드리도록 하겠습니다.

1. 결정트리란?

결정 트리는 어떤 질문에 대한 결정을 통해서 데이터를 분해하는 모델이라고 할 수 있습니다. 그림 1에서 예를 들어볼까요?

그림 1. 결정트리 예시

 결정 트리는 훈련 데이터의 특성을 기반으로 샘플의 클래스 레이블을 추정할 수 있는 질문을 학습합니다. 예시는 범주형 변수를 사용했지만 동일한 개념은 붓꽃 데이터셋 같은 실수형 특성에서도 적용됩니다. 예를 들어 "꽃잎의 길이가 3cm보다 긴가요?"라는 예/아니오 질문을 할 수 있습니다.

 결정 알고리즘을 사용하면 트리의 루트, 그러니까 트리의 기원이 되는 부분부터 시작해서 정보 이득(Information Gain, IG)가 최대가 되는 특성으로 데이터를 나눕니다. 반복을 통해서 리프 노드가 순수해질 때까지 모든 자식 노드에서 이 분할 작업을 반복합니다. 그러나 실제로 이렇게 하면 깊은 트리가 만들어져서 오버피팅이 될 확률이 높은데, 이것을 방지하기 위해서 가지치기(pruning)합니다.

 위 단락에서 정보 이득이 나왔죠? 우리는 최대한 샘플에서 정보가 풍부한 특성으로 노드를 나누는 것이 분류에 적합합니다. 이때 노드를 나누기 위해 트리 알고리즘으로 최적화할 목적함수를 정의해야하는데, 이 목적 함수는 각 분할에서 정보 이득을 최대화합니다. 정보 이득은 아래 식과 같습니다.

그림 2. 정보이득

 이 식에서 f는 분할에 사용할 특성, 즉 질문입니다. Dp와 Dj는 부모와 j번째 자식 노드의 데이터이고, I는 불순도(impurity)입니다. Np는 부모 노드에 있는 전체 샘플 개수입니다. 각각의 샘플이 질문을 만나기 전의 상태를 의미합니다. Nj는 j번째 자식 노드의 샘플 개수입니다. 정보 이득은 단순히 부모 노드의 불순도와 자식 노드의 불순도 합의 차이입니다. 자식 노드의 불순도가 낮을수록 정보 이득이 커집니다. 사이킷런을 포함한 대부분의 라이브러리는 이진 결정 트리를 사용하므로 부모노드는 두 개의 자식 노드로 나뉘어집니다.

그림 3. 정보이득 - 결정 트리

 이진 결정 트리에 중요한 역할을 하는 불순도 지표(분할 조건)은 대표적으로 지니 불순도(Gini impurity), 엔트로피(entropy, IH), 분류 오차(classification error, IE)입니다. 샘플이 있는 모든 클래스 p(i|t)!=0에 대한 엔트로피의 정의는 그림 4와 같습니다.

그림 4. 샘플이 있는 모든 클래스에 대한 엔트로피 정의

 여기서 p(i|t)는 특정 노드 t에서 클래서 i에 속한 샘플 비율입니다. 한 노드의 모든 샘플이 같은 클래스이면 엔트로피는 0이 됩니다. 클래스 분포가 균등할 때 엔트로피가 최대가 되겠죠. 예를 들어, i=1일 때 p가 1이거나 i=0이고 p=1이면 엔트로피는 0이고, i=1일 때 p가 0.5와 i=0일 때 p가 0.5로 균등하면 엔트로피는 1이 됩니다. 엔트로피는 물리에서 불규칙함을 뜻한다는 것은 들어보셨겠죠? 편하게 비슷한 개념으로 이해하시면 됩니다.

 지니 불순도는 이름에서 알 수 있듯이 잘못 분류될 확률을 최소화하기 위한 일종의 기준입니다. 엔트로피와 비슷하게 지니 불순도는 클래스가 완벽하게 균등하게 섞여있을 때 최대가 됩니다.

그림 5. 지니 불순도

 예를 들어 이진 클래스 환경, 즉 c가 2일 때는 I가 0.5가 됩니다. 실제로 지니 불순도와 엔트로피는 모두 매우 비슷한 결과가 나오지만, 불순도 조건을 바꾸어서 트리를 평가하는 것보다는 가지치기의 수준을 바꾸는 편이 낫다고 합니다.

 마지막 불순도 지표는 분류 오차입니다. 가지치기는 좋은 기준이나 결정 트리를 구성하는 데는 노드의 클래스 확률 변화에 둔감하기 때문에 권장하지 않습니다.

그림 6. 분류 오차

이제 이해하기 쉬운 예시를 들어볼까요? 여러분께 두 개의 분할 시나리오를 드리도록 하겠습니다.

그림 7. 분할 시나리오

 부모노드에서 위에 말한대로 데이터셋 Dp로 시작합니다. 클래스 1이 40개, 클래스 2가 40의 샘플을 갖고 있네요. 이것을 두 개의 데이터 셋 Dleft와 Dright로 나눕니다. 분류 오차를 분할 기준으로 했을 때 정보 이득은 시나리오 A와 B가 같습니다.(IG = 0.25)

 그럼 이번에는 지니 불순도로 나누어볼까요? 이 경우에는 시나리오 A(IG = 0.125)보다 시나리오 B(IG = 0.16)이 더 순수하기 때문에 값이 높습니다.

 비슷하게 엔트로피의 기준도 시나리오 A(IG=0.19)보다 시나리오 B(IG = 0.31)을 더 선호합니다

 

 앞서 나온 세 개의 불순도 기준을 비교하기 위해 클래스 1의 확률 범위인 0부터 1 사이의 불순도 인덱스를 그려보도록 하겠습니다. 지니 불순도가 엔트로피와 분류 오차의 중간임을 관찰하기 위해 스케일이 조정된 entropy/2를 추가하였습니다. 아래 코드를 실행해볼까요?

import matplotlib.pyplot as plt
import numpy as np


def gini(p):
    return p * (1 - p) + (1 - p) * (1 - (1 - p))


def entropy(p):
    return - p * np.log2(p) - (1 - p) * np.log2((1 - p))


def error(p):
    return 1 - np.max([p, 1 - p])

x = np.arange(0.0, 1.0, 0.01)

ent = [entropy(p) if p != 0 else None for p in x]
sc_ent = [e * 0.5 if e else None for e in ent]
err = [error(i) for i in x]

fig = plt.figure()
ax = plt.subplot(111)
for i, lab, ls, c, in zip([ent, sc_ent, gini(x), err], 
                          ['Entropy', 'Entropy (scaled)', 
                           'Gini Impurity', 'Misclassification Error'],
                          ['-', '-', '--', '-.'],
                          ['black', 'lightgray', 'red', 'green', 'cyan']):
    line = ax.plot(x, i, label=lab, linestyle=ls, lw=2, color=c)
    
ax.legend(loc='upper center', bbox_to_anchor=(0.5, 1.15),
          ncol=5, fancybox=True, shadow=False)

ax.axhline(y=0.5, linewidth=1, color='k', linestyle='--')
ax.axhline(y=1.0, linewidth=1, color='k', linestyle='--')
plt.ylim([0, 1.1])
plt.xlabel('p(i=1)')
plt.ylabel('Impurity Index')
plt.show()

그림 8. 불순도 지표 비교

 그림 8에서 확인할 수 있다시피 지니 불순도는 스케일이 1/2로 조정된 entropy와 거의 일치합니다. 이렇게 불순도 지표 세 가지, 분류 오차, 엔트로피, 지니 불순도를 알아보았습니다. 이제 결정 트리를 만들어볼까요?

 

2. 결정 트리 만들기

 결정 트리는 특성공간을 사각형으로 나누기 때문에 복잡한 결정 경계를 만드는 것이 가능합니다. 다만 위에서 언급한 것과 같이 트리가 너무 커지고 깊어지면 경계가 너무 복잡해지고 오버피팅되기 쉽기 때문에 주의하는 것이 좋습니다. 아래 코드는 사이킷런과 지니 불순도 조건으로 최대 깊이가 4인 결정 트리를 훈련합니다.

from sklearn.tree import DecisionTreeClassifier

tree = DecisionTreeClassifier(criterion='gini', 
                              max_depth=4, 
                              random_state=1)
tree.fit(X_train, y_train)

X_combined = np.vstack((X_train, X_test))
y_combined = np.hstack((y_train, y_test))
plot_decision_regions(X_combined, y_combined, 
                      classifier=tree, test_idx=range(105, 150))

plt.xlabel('petal length [cm]')
plt.ylabel('petal width [cm]')
plt.legend(loc='upper left')
plt.tight_layout()
plt.show()

그림 9. 결정 트리가 학습한 결정 경계

 사이킷런은 훈련 이후에 결정 트리를 .dot 파일로 추출할 수 있습니다. GraphViz 프로그램을 사용하여 시각화할 수 있는데, 이 프로그램은 여기에서 다운 받을 수 있습니다. 무료입니다! 

 GraphViz 이외에도 파이썬 라이브러리인 pydotplus를 사용할 수 있습니다. 이 경우에는 pip 패키지 관리자를 통해서 설치할 수 있습니다. 아나콘다의 경우에는 둘째 줄을 참고하세요.

pip3 install pydotplus

conda install pydotplus

 

요 다음 코드는 로컬 디렉터리에 png형태의 결정 트리 이미지를 보여줍니다. out_file을 none으로 설정하면 tree.dot 파일을 만들지 않고 dot 데이터를 dot_data 변수에 전해줍니다. filled, rounded, class_names, feature_names는 선택사항입니다.

from pydotplus import graph_from_dot_data
from sklearn.tree import export_graphviz

dot_data = export_graphviz(tree,
                           filled=True, 
                           rounded=True,
                           class_names=['Setosa', 
                                        'Versicolor',
                                        'Virginica'],
                           feature_names=['petal length', 
                                          'petal width'],
                           out_file=None) 
graph = graph_from_dot_data(dot_data) 
graph.write_png('tree.png')

그림 10. 붓꽃 데이터셋 결정 트리

 그림 10을 보면 결정 트리가 선택한 분할을 쉽게 분석할 수 있습니다. 처음 루트 노드에서 105개의 샘플로 시작하고, 그 다음에 꽃잎 너비 기준을 사용해 0.75를 기준으로 35개와 70개 샘플로 나눕니다. 첫 분할로 왼쪽 자식 노드는 Iris-setasa클래스의 샘플만을 갖게 되었습니다! 그 다음 오른쪽에서 분할이 일어나서 Iris-versicolor와 Iris-verginica 클래스의 샘플을 구분합니다.

 

3. 랜덤 포레스트로 여러 개의 결정 트리 연결

 랜덤 포레스트(random forest)는 결정 트리의 앙상블(ensemble)로 생각하면 쉽습니다. 랜덤 포레스트는 여러 개의 결정 트리를 평균 내는 것입니다. 각각의 트리는 분산이 너무 높은 문제가 있지만 앙상블하면 견고한 모델을 만들어서 일반화 성능을 높이고 오버피팅의 위험을 줄일 수 있습니다. 랜덤 포레스트 알고리즘은 다음 4단계로 요약됩니다.

1. n개의 랜덤한 부트스트랩(bootstrap)샘플을 뽑습니다. (중복허용하며 랜덤하게 n개 샘플 선택)
2. 부트스트랩 샘플에서 결정 트리를 학습합니다. 그리고 각 노드에 대해서 아래와 같이 적용합니다
   1. 중복을 허용하지 않고 랜덤하게 d개의 특성을 선택합니다.
   2. 정보 이득과 같은 목적 함수를 기준으로 최선의 분할을 만드는 특성을 이용해 노드를 분할합니다.
3. 단계 1과 2를 k번 반복합니다.
4. 각 트리의 예측을 모아서 다수결 투표(majority voting)로 클래스 레이블을 할당합니다.

 단계 2에서 훈련할 때 조금 다른 점은 각 노드에서 최선의 분할을 찾기 위해 모든 특성을 평가하는 게 아니라 랜덤하게 선택된 일부 특성만 평가합니다. 

 랜덤 포레스트는 결정 트리처럼 해석이 쉬운 것은 아니지만 하이퍼 파라미터 튜닝에 시간을 많이 투자하지 않아도 됩니다. 즉 앙상블 모델이 개별 결정 트리가 만드는 잡음이 거의 없이 안정되어있어 가지치기를 할 필요가 없습니다. 실전에서 신경써야할 것은 단계 3 뿐입니다. 트리 개수가 많을수록 계산 비용이 증가하고 그만큼 분류기의 성능이 좋아집니다.

 부트스트랩 샘플 크기가 작아지면 개별 트리의 다양성이 증가하고, 따라서 랜덤 포레스트의 무작위성이 증가하고 오버피팅 영향이 줄어듭니다. 하지만 보통 부트스트랩 샘플이 작을수록 성능이 줄어듭니다. 훈련 성능과 테스트 성능 사이의 격차가 작아지기 때문이죠. 반대로 부트스트랩 크기가 증가하면 오버피팅될 가능성이 높아집니다. 부트 스트랩과 개별 결정 트리가 서로 비슷해지기 때문이죠.

 사이킷런의 RandomForestClassifier을 포함한 대부분의 라이브러리에서는 부트스트랩 샘플 크기를 원본 훈련 세트의 샘플 개수와 같게 합니다. 이렇게 하면 균형잡힌 트레이드 오프를 얻을 수 있기 때문이죠. 분할할 때 사용할 특성 개수 d는 전체 특성 개수보다 작게 합니다. 여러 라이브러리에서 사용하는 적당한 기본값은 d = m^(1/2)입니다.

from sklearn.ensemble import RandomForestClassifier

forest = RandomForestClassifier(criterion='gini',
                                n_estimators=25, 
                                random_state=1,
                                n_jobs=2)
forest.fit(X_train, y_train)

plot_decision_regions(X_combined, y_combined, 
                      classifier=forest, test_idx=range(105, 150))

plt.xlabel('petal length [cm]')
plt.ylabel('petal width [cm]')
plt.legend(loc='upper left')
plt.tight_layout()
plt.show()

그림 11. 랜덤 포레스트의 결정 경계

 위 코드의 n_estimators 매개변수로 25개 트리를 사용하여 훈련했고, 지니 불순도를 사용했습니다.

 

3. k-최근접 이웃: 게으른 학습 알고리즘

 이번 세션의 마지막 지도학습 알고리즘은 k-최근접 이웃(K-Nearest Neighbor, KNN)입니다. 이 알고리즘은 이전의 알고리즘들과는 아주 다른데, KNN이 게으른 학습기(lazy learner)라고 불리는 데서 쉽게 유추할 수 있습니다. 이 알고리즘은 훈련 데이터에서 판별 함수를 학습하는 게 아니라 훈련 데이터셋을 메모리에 저장합니다.

 KNN을 요약하자면 아래와 같습니다.

1. 숫자 k와 거리 측정 기준을 선택합니다.
2. 분류하려는 샘플에서 k개의 최근접 이웃을 찾습니다.
3. 다수결 투표를 통해 클래스 레이블을 할당합니다.

그림 12. k-최근접 이웃과 다수결 투표

 그림 12를 통해서 우리는 물음표로 표시된 포인트가 동그라미 안 다섯 개의 다수결 투표를 기반으로 삼각형 클래스 레이블에 할당될 것이라는 것을 보여줍니다. 

 이러한 메모리 기반의 분류기는 수집된 새로운 데이터에 즉시 적응할 수 있는 것이 장점입니다. 단점은 새로운 샘플을 분류하는 계산이 상당히 복잡하다는 점이죠. 데이터의 차원이 적고 알고리즘이 효율적인 구조가 아니라면 계산의 복잡도는 샘플 개수에 선형적으로 증가할 겁니다. 또 훈련 단계가 없으니 훈련 샘플을 버릴 수 없어서 저장공간에 문제가 있을 수 있죠.

 아래 코드를 통해서 유클리디안(euclidean)거리 측정 방식을 사용한 KNN모델을 확인해보겠습니다.

from sklearn.neighbors import KNeighborsClassifier

knn = KNeighborsClassifier(n_neighbors=5, 
                           p=2, 
                           metric='minkowski')
knn.fit(X_train_std, y_train)

plot_decision_regions(X_combined_std, y_combined, 
                      classifier=knn, test_idx=range(105, 150))

plt.xlabel('petal length [standardized]')
plt.ylabel('petal width [standardized]')
plt.legend(loc='upper left')
plt.tight_layout()
plt.show()

그림 13. k-최근접 이웃 모델의 결정경계

 적절한 k를 선택하는 것이 오버피팅과 언더피팅 사이의 균형을 잡을 수 있습니다. 당연히 데이터의 특성에 알맞는 거리 측정 지표를 선택해야하죠. 붓꽃 데이터처럼 실수 값을 가진 경우에는 유클리디안 거리를 사용합니다. 유클리디안은 표준화해야한다는 것이 중요합니다. 위 코드에서 minkowski 거리는 유클리디안과 맨해튼 거리를 일반화한 것으로, 아래 그림 14와 같습니다.

그림 14. minkowski

 매개변수 p=2로 지정하면 유클리디안이, p-1로 지정하면 맨해튼 거리가 됩니다. 사이킷런에는 다른 거리 측정 기준이 많으니 요기를 참고하세요.

 

---

분량 조절에 실패했습니다! 죄송합니다ㅠㅠ 어쩐지 글을 쓸 때마다 점점 세션이 길어지는 것 같은 기분이네요. 이번 세션에서틑 결정 트리, 앙상블이라는 개념과 k-최근접 이웃 모델에 대해서 간단하게 알아보았습니다. 세 가지의 불순도 지표에 대해서도 알아보았습니다. 지니 불순도, 엔트로피, 그리고 분류 오차였죠. 이번 세션에서는 방금 언급된 키워드들만 제대로 아셔도 충분하실 겁니다. 문장이 매끄럽지 않은 부분은 후에 검수하면서 수정하도록 하겠습니다. 그럼 저는 다음 세션에서 데이터 전처리에 대한 내용을 들고 오도록 하겠습니다!