결정 트리

결정트리는 분류와 회귀 작업, 다중출력 작업이 가능한 머신러닝 알고리즘이다.

붓꽃 데이터셋으로 결정트리의 훈련, 시각화, 예측 방법에 대해 알아볼 것이다.

결정 트리 학습과 시각화

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

iris = load_iris()
X = iris.data[:, 2:] # 꽃잎 길이와 너비
y = iris.target

tree_clf = DecisionTreeClassifier(max_depth=2, random_state=42)
tree_clf.fit(X, y)

DecisionTreeClassifier(ccp_alpha=0.0, class_weight=None, criterion='gini',
                       max_depth=2, max_features=None, max_leaf_nodes=None,
                       min_impurity_decrease=0.0, min_impurity_split=None,
                       min_samples_leaf=1, min_samples_split=2,
                       min_weight_fraction_leaf=0.0, presort='deprecated',
                       random_state=42, splitter='best')

Decision TreeClassifier를 훈련시키는 코드이다.

  
from graphviz import Source
from sklearn.tree import export_graphviz

export_graphviz(
        tree_clf,
        out_file=os.path.join(IMAGES_PATH, "iris_tree.dot"),
        feature_names=iris.feature_names[2:],
        class_names=iris.target_names,
        rounded=True,
        filled=True
    )

Source.from_file(os.path.join(IMAGES_PATH, "iris_tree.dot"))

export_graphviz함수를 사용해서 아래와 같이 결정 트리를 시각화 할 수 있다

예측하기

시각화한 결정 트리를 보며 결정트리가 예측하는 순서를 살펴보자

루트 노드에서는 꽃잎의 길이가 2.45cm보다 짧은지 검사한다.
1. 참일 경우 추가적인 자식노드가 없기때문에 검사를 종료한다. 품종은 Setosa일 것이다.
2. 거짓일 경우 오른쪽 노드로 이동한다. (꽃잎의 길이가 2.45cm 보다 긴 경우)
다음 노드에서는 꽃잎의 너비가 1.75cm보다 작은지 확인한다.
1. 참일 경우 꽃잎은 Versicolor일 것이다.
2. 거짓일 경우 Virginica일 것이다.

노드에서 sample속성은 훈련 샘플이 적용된 수를 나타낸다.
노드의 value속성은 노드에서 각 클래스의 훈련 샘플의 수를 나타낸다.
노드의 gini속성은 불순도를 측정한다.

결정트리의 결정 경계

  
from matplotlib.colors import ListedColormap

def plot_decision_boundary(clf, X, y, axes=[0, 7.5, 0, 3], iris=True, legend=False, plot_training=True):
    x1s = np.linspace(axes[0], axes[1], 100)
    x2s = np.linspace(axes[2], axes[3], 100)
    x1, x2 = np.meshgrid(x1s, x2s)
    X_new = np.c_[x1.ravel(), x2.ravel()]
    y_pred = clf.predict(X_new).reshape(x1.shape)
    custom_cmap = ListedColormap(['#fafab0','#9898ff','#a0faa0'])
    plt.contourf(x1, x2, y_pred, alpha=0.3, cmap=custom_cmap)
    if not iris:
        custom_cmap2 = ListedColormap(['#7d7d58','#4c4c7f','#507d50'])
        plt.contour(x1, x2, y_pred, cmap=custom_cmap2, alpha=0.8)
    if plot_training:
        plt.plot(X[:, 0][y==0], X[:, 1][y==0], "yo", label="Iris setosa")
        plt.plot(X[:, 0][y==1], X[:, 1][y==1], "bs", label="Iris versicolor")
        plt.plot(X[:, 0][y==2], X[:, 1][y==2], "g^", label="Iris virginica")
        plt.axis(axes)
    if iris:
        plt.xlabel("Petal length", fontsize=14)
        plt.ylabel("Petal width", fontsize=14)
    else:
        plt.xlabel(r"$x_1$", fontsize=18)
        plt.ylabel(r"$x_2$", fontsize=18, rotation=0)
    if legend:
        plt.legend(loc="lower right", fontsize=14)

# 그래프 그리기
plt.figure(figsize=(8, 4))
plot_decision_boundary(tree_clf, X, y)
plt.plot([2.45, 2.45], [0, 3], "k-", linewidth=2)
plt.plot([2.45, 7.5], [1.75, 1.75], "k--", linewidth=2)
plt.plot([4.95, 4.95], [0, 1.75], "k:", linewidth=2)
plt.plot([4.85, 4.85], [1.75, 3], "k:", linewidth=2)
plt.text(1.40, 1.0, "Depth=0", fontsize=15)
plt.text(3.2, 1.80, "Depth=1", fontsize=13)
plt.text(4.05, 0.5, "(Depth=2)", fontsize=11)

save_fig("decision_tree_decision_boundaries_plot")
plt.show()

굵은 선은 루트 노드의 결정 경계를 나타낸다.(꽃잎 길이: 2.45cm)
결정 경계 왼쪽은 Setosa만 존재하기때문에 나눌 수 없다.
결정 경계 오른쪽은 꽃잎의 넓이로 경계가 나눠진다.
결정트리의 max_depth를 2로 설정했으므로 더이상 나눠지지 않는다.
점선은 max_depth를 3으로 설정했을 경우 추가로 경계가 만들어진다.

클래스 확률 추정

결정트리는 샘플에 대해 리프 노드를 탐색하고 해당 리프 노드의 클래스 k의 훈련 샘플의 비율을 반환한다. 결정트리는 하나의 샘플이 특정 클래스 k에 속할 확률을 추정할 수 있다.

  
tree_clf.predict_proba([[5, 1.5]])
'''
array([[0.        , 0.90740741, 0.09259259]])
'''
tree_clf.predict([[5, 1.5]])
'''
array([1])
'''

위 코드는 길이가 5cm이고 너비가 1.5cm인 꽃잎에 대한 추정이다.
리프 노드는 깊이 2에서 왼쪽 노드이며 이에 해당하는 확률을 반환한다.
Setosa는 0%, Versicolor는 90.7%, Virginica는 9.3%로 나온다.
하나의 클래스를 예측한다고 하면 가장 높은 클래스인 Versicolor를 반환할 것이며 실제로 예측한 값도 동일하다.

CART 훈련 알고리즘

\[J(k_t, t_k) = ({m_{left}} / {m}) * G_{left} + ({m_{right}} / m) * G_{right}\]

CART(Classification and Regression Tree)알고리즘의 비용함수이다.
$G_{left/right}$는 왼쪽/오른쪽 서브셋의 불순도이다.
$m_{left/right}$는 왼쪽/오른쪽 서브셋의 샘플수이다.
CART알고리즘은 greedy algorithm으로 루트 노드에서 최적의 분할을 찾는다.
분할하면서 최대 깊이가 되면 중지하거나 불순도를 줄이는 분할을 찾을 수 없을 경우 종료한다.
greedy algorithm의 특징으로 인해 항상 최적의 솔루션을 보장하진 않는다.

계산 복잡도

결정트리는 균형 이진트리로 볼 수 있다.
결정트리를 탐색하기 위해 $O(log_2(m))$개의 노드를 탐색해야 한다.
각 노드에서 특성값 하나만 확인하기 때문에 시간복잡도는 특성 수와는 무관하게 $O(log_2(m))$로 동일하다.
사이킷런에서 presort=True를 지정하면 데이터를 미리 정렬해서 훈련 속도를 높일 수 있다.
훈련 세트가 클 경우 presort를 하게되면 속도가 느려질 수 있다.

지니 불순도 또는 엔트로피

결정트리에서는 기본적으로 지니 불순도가 사용되지만 criterion속성을 "entropy"로 지정하면 엔트로피 불순도를 사용할 수 있다.

\[H_i = -\Sigma_{k=1}^{n} p_{i,k}log_2(P_{i,k})\]

정보이론(information theory)에서 엔트로피 식은 위와 같다.
지니 불순도와 엔트로피 불순도는 비슷한 트리를 생성하고, 지니 불순도가 연산 속도가 빠르다.
지니 불순도는 가장 빈도가 높은 클래스를 한쪽 가지로 고립시키는 경향이 있지만, 엔트로피는 균형을 이루는 트리를 생성한다.

규제 매개변수

결정 트리는 훈련 데이터에 대한 제약 사항이 없기 때문에 제한을 두지 않으면 트리가 훈련 데이터에 최대한 맞추려고 하면서 과대적합이 되기 쉽다.

비파라미터 모델

훈련되기 전에 파라미터 수가 결정되지 않고 훈련을 진행하는 결정트리를 비파라미터 모델이라고 한다.
모델 구조가 데이터에 맞춰져 고정되지 않고 자유로운것이 특징이다.

파라미터 모델

정의된 파라미터 수를 가지므로 모델 구조의 자유도가 제한되고 과대적합될 확률을 줄여준다.

DecisionTreeClassifier의 규제 매개변수

  
tree_clf_tweaked = DecisionTreeClassifier(max_depth=2, random_state=40) # max_depth 제한 
tree_clf_tweaked.fit(X, y)

DecisionTreeClassifier의 규제 매개변수로 max_depth를 2로 제한해서 훈련 시켜보았다.
트리의 depth가 2로 제한되면서 트리의 깊이가 2개까지 나온다.

  
from sklearn.datasets import make_moons
Xm, ym = make_moons(n_samples=100, noise=0.25, random_state=53)

deep_tree_clf1 = DecisionTreeClassifier(random_state=42)
deep_tree_clf2 = DecisionTreeClassifier(min_samples_leaf=4, random_state=42) # leaf 수 제한
deep_tree_clf1.fit(Xm, ym)
deep_tree_clf2.fit(Xm, ym)

fig, axes = plt.subplots(ncols=2, figsize=(10, 4), sharey=True)
plt.sca(axes[0])
plot_decision_boundary(deep_tree_clf1, Xm, ym, axes=[-1.5, 2.4, -1, 1.5], iris=False)
plt.title("No restrictions", fontsize=16)
plt.sca(axes[1])
plot_decision_boundary(deep_tree_clf2, Xm, ym, axes=[-1.5, 2.4, -1, 1.5], iris=False)
plt.title("min_samples_leaf = {}".format(deep_tree_clf2.min_samples_leaf), fontsize=14)
plt.ylabel("")

save_fig("min_samples_leaf_plot")
plt.show()

mean_sample_leaf의 값을 4로 제한하게 되면서 규제가 없는 경우에 비해 과대적합되지 않고 일반화가 잘 된 결과를 볼 수 있다.

Pruning

Pruning은 제한 없이 결정 트리를 훈련시키고 불필요한 노드를 가지치기하는 알고리즘이다.

결정트리의 과대적합을 해결하기위한 방법이다.

Pruning 방법

속성을 제한한다.
1. 트리의 깊이, leaf node의 최대 갯수, 노드가 분할하는 최대 갯수를 제한한다.
min_sample_split파라미터를 조정한다.
1. 하나의 노드에 들어있는 최소 데이터 수를 지정한다.

Pruning은 과대적합을 방지하지만, 정확도가 떨어질 가능성이 있어 파라미터 설정을 잘 해줘야 한다.
여러개의 결정트리를 학습하는 앙상블 기법으로 Random Forest가 있으며, 하나의 결정트리보다 뛰어난 성능을 보인다.

회귀

DecisionTreeRegressor를 이용해서 회귀 트리를 생성할 수 있다.

  
from sklearn.tree import DecisionTreeRegressor

tree_reg = DecisionTreeRegressor(max_depth=2, random_state=42)
tree_reg.fit(X, y)

위 코드는 max_depth를 2로 지정한 회귀 트리이다.
결정트리와 다른점은 각 노드에서 클래스를 예측하지 않고 값을 예측한다는 것이다.
$x_1$이 0.6인 값을 예측해보면 트리에서 value가 0.111인 리프 노드에 도달하게된다.
위 그림은 max_depth가 2, 3인 경우 모델의 예측을 나타낸 것이다.

위 그림은 규제 파라미터가 없는 경우와 min_sample_leaf파라미터를 10으로 지정해준 경우이다.
규제가 없는 모델의 훈련은 예상대로 과대적합된 모습을 보인다.
규제 파라미터를 적용한 모델은 과대적합되지 않고 잘 학습된 모습을 보인다.

불안정성

결정트리는 계단 모양의 결정경계를 만들어 낸다.
결정트리는 같은 데이터 셋이지만 데이터 셋의 회전에 민감하다.
위 그림처럼 데이터 셋이 45도 회전된 경우 계단 모양으로 분류되어 일반화가 되지 않는 모습을 보인다.
사이킷런의 훈련 알고리즘은 확률적이기 때문에 random seed를 지정하지 않으면 같은 데이터 셋에서도 다른 결과를 얻을 수 있다.

결정트리 (Hands-On Machine Learning Part1)