Decision Trees

 

결정 트리

 

결정 트리는 분류와 회귀 문제에 널리 사용하는 모델입니다.

 

기본적으로 결정 트리는 결정에 다다르기 위해 예/아니오 질문을 이어 나가면서 학습합니다. 

 

트리의 노드는 질문이나 정답을 담은 네모 상자입니다 (특히 마지막 노드는 리프(leaf)라고 합니다).

 

에지(edge)는 질문의 답과 다음 질문을 연결합니다. 

 

모델을 직접 만든느 대신 지도 학습 방식으로 데이터로부터 학습할 수 있습니다. 

 

연속된 질문들은 결정 트리로 나타납니다. 

 

그림1

 

 

최상의 분할을 결정하는 방법 (분류)

 

그리디(Greedy) 접근 : 더 순수한 클래스 분포를 가진 노드를 선호하는 것 

 

그림2

 

노드 불순도를 측정하는 방법

 

$GINI(t) = 1 - \sum_{j}[p(j\mid t)]^{2}$

 

$Entropy(t) = -\sum_{j} p(j \mid t) log p (j \mid t)$

 

$Error(t) = 1 - max P(i \mid t)$

 

 

최상의 분기를 결정하는 방법 (분류)

 

1. 분기 전에 측정한 불순도 (P)를 계산합니다. 

 

2. 분기 후에 측정한 불순도 (M)을 계산합니다.

 

각 자녀 노드에서 불순도 측정을 계산합니다. 

 

M은 자녀의 가중된 불순도입니다.

 

3. 가장 높은 gain을 얻은 변수를 선택합니다.

 

Gain = P - M 

 

그림3

 

	Parent
C1	7
C2	5
Gini = 0.486

 

Gini(Parent) = 1 - (7/12)^2 - (5/12)^2

 

	N1	N2
C1	5	2
C2	1	4
Gini = 0.361

 

Gini(N1) = 1 - (5/6)^2 - (1/6)^2 = 0.278

 

Gini(N2) = 1 - (2/6)^2 - (4/6)^2 = 0.444

 

Weighted Gini of N1 N2 = 6/12 * 0.278 + 6/12 * 0.444 = 0.361

 

Gain = 0.486 - 0.361 = 0.125

 

 

결정 트리 만들기

 

2차원 데이터셋을 분류하는 결정트리를 만들어보겠습니다. 

 

이 데이터셋은 각 클래스에 데이터 포인트가 75개씩 있고 반달 두개가 포개진 듯한 모양을 하고 있습니다.

 

이 데이터셋을 two_moons라고 하겠습니다. 

 

그림4

 

트리를 만들 때 알고리즘은 가능한 모든 테스트에서 타깃값에 대해 가장 많은 정보를 가진 것을 고릅니다. 

 

그림5

 

이 두 영역에서 가장 좋은 테스트를 찾는 과정을 반복해서 모델을 더 정확하게 만들 수 있습니다. 

 

가장 많은 정보를 담을 수 있도록 x[0] 값을 기준으로 왼쪽과 오른쪽 영역으로 나누고 있습니다. 

 

그림6

 

데이터를 분할하는 것은 각 분할된 영역이 (결정 트리의 리프) 한 개의 타깃값 (하나의 클래스나 하나의 회귀 분석 결과)을 가질 때까지 반복됩니다. 

 

타깃 하나로만 이뤄진 리프 노드를 순수 노드(pure node)라고 합니다. 

 

그림7

 

 

결정 트리 예측

 

새로운 데이터 포인트에 대한 예측은 주어진 데이터 포인트가 특성을 분할한 영역들 중 어디에 놓이는지를 확인하면 됩니다. 

 

분류 문제의 경우 영역의 타깃값 중 다수 (순수 노드라면 하나)인 것을 예측 결과로 합니다. 

 

회귀 문제의 경우 새로운 데이터 포인트에 해당되는 리프 노드를 찾습니다. 찾은 리프 노드의 훈련 데이터 평균값이 이 데이터 포인트의 출력이 됩니다. 

 

 

결정 트리의 복잡도 제어하기

 

일반적으로 트리 만들기를 모든 리프 노드가 순수 노드가 될 때까지 진행하면 모델이 매우 복잡해지고 훈련 데이터에 과대적합됩니다.

 

순수 노드로 이루어진 트리는 훈련 세트에 100% 정확하게 맞는다는 의미입니다. 

 

 

과대적합을 막는 두 가지 전략

 

사전 가지치기 : 트리 생성을 일찍 중단하는 전략 

 

max_depth : 트리의 최대 깊이를 제한합니다. 

 

min_sample_leaf : 노드가 분할하기 위한 포인트의 최소 개수를 지정합니다. 

 

max_leaf_nodes : 리프의 최대 개수를 제한합니다.

 

사후 가지치기 : 데이터 포인트가 적은 노드를 삭제하거나 병합하는 전략이니다. 

 

 

유방암 예시 - DecisionTreeClassifier

 

from sklearn.datasets import load_breast_cancer
cancer = load_breast_cancer()

 

유방암 데이터셋을 이용하겠습니다.

 

 

from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(
    cancer.data, cancer.target, stratify=cancer.target, random_state=42)

 

훈련 세트와 테스트 세트로 나눕니다.

 

 

from sklearn.tree import DecisionTreeClassifier
clf = DecisionTreeClassifier(random_state=0)
clf.fit(X_train, y_train)

 

기본값 설정으로 완전한 트리(모든 리프 노드가 순수 노드가 될 때까지 생성한 트리) 모델을 만듭니다.

 

rnadom_state 옵션을 고정해 만들어진 트리를 같은 조건으로 비교합니다. 

 

 

from sklearn.metrics import accuracy_score
y_train_hat = clf.predict(X_train)
print('train accuracy :', accuracy_score(y_train, y_train_hat))
y_test_hat = clf.predict(X_test)
print('tests accuracy :', accuracy_score(y_test, y_test_hat))

그림8

 

모든 리프 노드가 순수 노드이므로 정확도는 100%입닏.

 

트리는 훈련 데이터의 모든 레이블을 완벽하게 기억할 만큼 충분히 깊게 만들어졌습니다.

 

테스트 세트의 정확도는 이전에 본 선형 모델에서의 정확도인 95%보다 조금 낮습니다. 

 

 

training_accuracy = []
test_accuracy = []

m_settings = [1, 2, 5, 10, 20]
for m in m_settings:
    #bulid the model
    clf = DecisionTreeClassifier(min_samples_leaf=m, random_state=0)
    clf.fit(X_train, y_train)
    
    # accuracy on the training set
    y_train_hat = clf.predict(X_train)
    training_accuracy.append(accuracy_score(y_train, y_train_hat))
    
    # accuracy on the test set
    y_test_hat = clf.predict(X_test)
    test_accuracy.append(accuracy_score(y_test, y_test_hat))

 

min_samples_leaf 옵션을 조정하여 훈련 세트와 테스트 세트의 성능을 비교하였습니다.

 

 

min_data = pd.DataFrame({'min_samples_leaf' : m_settings,
                        'training accuracy' : training_accuracy,
                        'test accuracy' : test_accuracy})
min_data

그림8

 

min_samples_leaf를 제한하면 과대적합이 줄어듭니다. 이는 훈련 세트의 정확도를 떨어뜨리지만 테스트 세트의 성능은 개선시킵니다. 

 

 

training_accuracy = []
test_accuracy = []

m_settings = [2, 3, 5, 7, 10]
for m in m_settings:
    #bulid the model
    clf = DecisionTreeClassifier(max_depth=m, random_state=0)
    clf.fit(X_train, y_train)
    
    # accuracy on the training set
    y_train_hat = clf.predict(X_train)
    training_accuracy.append(accuracy_score(y_train, y_train_hat))
    
    # accuracy on the test set
    y_test_hat = clf.predict(X_test)
    test_accuracy.append(accuracy_score(y_test, y_test_hat))

 

이번에는 max_depth 옵션을 조정하여 훈련 세트와 테스트 세트의 성능을 비교했습니다.

 

 

max_data = pd.DataFrame({'max_depth' : m_settings,
                        'training accuracy' : training_accuracy,
                        'test accuracy' : test_accuracy})
max_data

그림9

 

트리 깊이를 제한하면 과대적합이 줄어듭니다. 훈련 세트의 정확도를 떨어뜨리지만 테스트 세트의 성능은 개선시킵니다. 

 

 

결정 트리 시각화

 

트리를 시각화하면 알고리즘의 예측이 어떻게 이뤄지는지 잘 이해할 수 있으며 비전문가에게 머신러닝 알고리즘을 설명하기에 좋습니다.

 

그림10

 

 

트리의 특성 중요도

 

전체 트리를 살펴보는 것은 어려울 수 있으니, 대신 트리가 어떻게 작동하는지 요약하는 속성들을 사용할 수 있습니다.

 

가장 널리 사용되는 속성은 트리를 만드는 결정에 각 특성이 얼마나 중요한지를 평가하는 특성 중요도입니다. 

 

이 값은 0과 1 사이의 숫자로, 각 특성에 대해 0은 전혀 사용되지 않았다는 뜻이고 1은 완벽하게 타깃 클래스를 예측했다는 뜻입니다.

 

특성 중요도의 전체 합은 1입니다. 

 

 

clf.feature_importances_

그림11

 

 

def plot_feature_importances_cancer(model):
    n_features = cancer.data.shape[1]
    plt.barh(np.arange(n_features), clf.feature_importances_, align='center')
    plt.yticks(np.arange(n_features), cancer.feature_names)
    plt.xlabel("Feature importance")
    plt.ylabel("Feature")
    plt.ylim(-1, n_features)

plot_feature_importances_cancer(tree)

그림12

 

시각화했습니다. 

 

 

컴퓨터 메모리 가격 동향 예시 - DecisionTreeRegressor

 

import os
ram_prices = pd.read_csv(os.path.join(mglearn.datasets.DATA_PATH, "ram_price.csv"))

plt.semilogy(ram_prices.date, ram_prices.price)
plt.xlabel("Year")
plt.ylabel("Price in $/Mbyte"

from sklearn.tree import DecisionTreeRegressor
# use historical data to forecast prices after the year 2000
data_train = ram_prices[ram_prices.date < 2000]
data_test = ram_prices[ram_prices.date >= 2000]

# predict prices based on date
X_train = data_train.date[:, np.newaxis]
# we use a log-transform to get a simpler relationship of data to target
y_train = np.log(data_train.price)

tree = DecisionTreeRegressor(max_depth=3).fit(X_train, y_train)
linear_reg = LinearRegression().fit(X_train, y_train)

# predict on all data
X_all = ram_prices.date[:, np.newaxis]

pred_tree = tree.predict(X_all)
pred_lr = linear_reg.predict(X_all)

# undo log-transform
price_tree = np.exp(pred_tree)
price_lr = np.exp(pred_lr)

plt.semilogy(data_train.date, data_train.price, label="Training data")
plt.semilogy(data_test.date, data_test.price, label="Test data")
plt.semilogy(ram_prices.date, price_tree, label="Tree prediction")
plt.semilogy(ram_prices.date, price_lr, label="Linear prediction")
plt.legend()

그림13

 

 

결정 트리 결론

 

결정 트리의 주요 하이퍼파라미터

 

결정 트리에서 모델 복잡도를 조절하는 매개변수는 트리가 완전히 만들어지기 전에 멈추게 하는 사전 가지치기 매개변수입니다.

 

max_depth, max_leaf_nodes 또는 min_samples_leaf 중 하나만 지정해도 과대적합을 막는 데 충분합니다.

 

일반적으로 평가 데이터셋에서 가장 높은 성능을 가진 것을 선택합니다.

 

 

장점

 

이진 특성과 연속적인 특성이 혼합되어 있을 때도 잘 작동합니다. (one-hot encoding이 필요하지 않습니다)

 

데이터의 스케일에 구애받지 않습니다. (data scaling이 필요하지 않습니다)

 

만들어진 모델을 쉽게 시각화할 수 있어서 비전문가도 이해하기 쉽습니다. 

 

 

단점

 

사전 가지치기를 사용함에도 불구하고 과대적합이되는 경향이 있어 일반화 성능이 좋지 않습니다. 

 

앙상블 방법을 단일 결정 트리의 대안으로 흔히 사용합니다. 

 

입력 변수 사이의 interactions를 고려하지 않습니다.

 

 

결정 트리의 앙상블

 

결정 트리의 주요 단점은 훈련 데이터에 과대적합되는 경향이 있다는 것입니다.

 

앙상블은 이 문제를 다루는 하나의 방법입니다.

 

앙상블은 여러 머신러닝 모델을 연결하여 더 강력한 모델을 만드는 기법입니다. 

 

그림14

 

 

랜덤 포레스트

 

랜덤 포레스트는 결정 트리의 앙상블입니다. 기본적으로 조금씩 다른 여러 결정 트리의 묶음입니다.

 

랜덤 포레스트의 아이디어는 각 트리는 비교적 예측을 잘 할 수 있지만 데이터의 일부에 과대적합하는 경향을 가진다는 데 기초합니다.

 

잘 작동하되 서로 다른 방향으로 과대적합된 트리를 많이 만들면 그 결과를 평균냄으로써 과대적합된 양을 줄일 수 있습니다.

 

랜덤 포레스트는 이름에서 알 수 있듯이 트리들이 달라지도록 트리 생성 시 무작위성을 주입합니다. 

 

 

랜덤 포레스트 구축

 

랜덤 포레스트에서 트리를 랜덤하게 만드는 방법은 두 가지입니다.

 

1. 트리를 만들 때 사용하는 데이터 포인트를 무작위로 선택하는 방법

 

bootstrap : 랜덤 포레스트의 트리가 조금씩 다른 데이터셋을 이용해 만들어지도록합니다. 

 

2. 분할 테스트에서 특성을 무작위로 선택하는 방법

 

max_features : 각 노드에서 전체 특성을 대상으로 최선의 테스트를 찾는것이 아니고 알고리즘이 각 노드에서 후보 특성을 무작위로 선택한 후 이 후보들 중에서 최선의 테스트를 찾습니다.

 

각 노드는 다른 후보 특성들을 사용하여 테스트를 만듭니다.

 

max_feature 값을 크게 하면 랜덤 포레스트의 트리들은 매우 비슷해지고 가장 두드러진 특성을 이용해 데이터에 잘 맞춰질 것입니다.

 

max_feature 값을 낮추면 랜덤 포레스트 트리들은 많이 달라지고 각 트리는 데이터에 맞추기 위해 깊이가 깊어지게 됩니다.

 

일반적으로, p features를 가진 분류 문제에서 $\sqrt{p}$ (rounded down) featrues가 각 분할에 사용됩니다.

 

회귀 문제의 경우 p/3 (rounded down)이 기본값입니다. 

 

실제 문제에서 가장 최상의 값을 결정하는 건 문제에 달려있습니다. 

 

그림15

 

예측을 할 때는 먼저 알고리즘이 모델에 있는 모든 트리의 예측을 만듭니다. 

 

회귀의 경우 이 예측들을 평균하여 최종 예측을 만듭니다. 

 

분류의 경우 약한 투표 전략을 사용합니다. 각 알고리즘이 가능성 있는 출력 레이블의 확률을 제공함으로써 간접적인 예측을 합니다.

 

트리들이 예측한 확률을 평균내어 가장 높은 확률을 가진 클래스가 예측값이 됩니다.

 

 

유방암 예시 - RandomForestClassifier

 

from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.ensemble import RandomForestClassifier
from sklearn.metrics import accuracy_score

cancer = load_breast_cancer()
X_train, X_test, y_train, y_test = train_test_split(
cancer.data, cancer.target, stratify=cancer.target, random_state = 42)

training_accuracy = []
test_accuracy = []

n_settings = [1, 2, 5, 10, 20, 50, 100]
for n in n_settings:
    #bulid the model
    clf = RandomForestClassifier(n_estimators=n, random_state=0)
    clf.fit(X_train, y_train)
    
    # accuracy on the training set
    y_train_hat = clf.predict(X_train)
    training_accuracy.append(accuracy_score(y_train, y_train_hat))
    
    # accuracy on the test set
    y_test_hat = clf.predict(X_test)
    test_accuracy.append(accuracy_score(y_test, y_test_hat))

n_data = pd.DataFrame({'n_estimators' : n_settings,
                        'training accuracy' : training_accuracy,
                        'test accuracy' : test_accuracy})
n_data

그림16

 

랜덤 포레스트는 아무런 매개변수 튜닝 없이도 높은 정확도를 내고 있습니다. 

 

 

랜덤 포레스트 결론

 

랜덤 포레스트의 주요 하이퍼파라미터 

 

n_estimators : 클수록 좋습니다. 

 

bootstrap : 부트스트랩 샘플을 사용할지를 결정합니다.

 

max_features : 일반적으로 기본값을 쓰는 것이 좋은 방법입니다. 분류는 sqrt(n_features)이고 회귀는 n_features입니다.

 

추가적으로 결정 트리의 하이퍼파라미터를 추가하면 가끔 성능이 향상되기도 합니다.

 

 

장점 

 

성능이 매우 뛰어나고 매개변수 튜닝을 많이 하지 않아도 잘 작동합니다.

 

 

단점

 

모든 트리를 상세하게 분석하기가 어렵습니다.

 

션형 모델보다 많은 메모리를 사용하며 훈련과 예측이 느립니다. 

 

그러나 멀티 코어 프로세서일 떄는 n_jobs 매개변수를 이용하여 사용할 코어 수를 지정할 수 있습니다. 사용하는 CPU 코어 개수에 비례해서 속도도 빨라집니다. 

 

 

파이썬 라이브러리를 활용한 머신러닝 책과 성균관대학교 강석호 교수님 수업 내용을 바탕으로 요약 작성되었습니다.