decision_tree

의사 결정 나무

의사결정나무(decision tree)는 여러 가지 규칙을 순차적으로 적용하면서 독립변수 공간을 분할하는 분류 모형이다. 판별적 확률모형이긴 하지만 분류해야 하는 class가 multi든 binary든, 혹은 문제 자체가 classification이든 regression이든 모두 적용할 수 있는 만능 모형이다. 분류와 회귀분석 모두에 사용될 수 있다는 점에서 CART(Classification And Regression Tree)라고도 한다.

의사 결정 나무를 이용한 분류

의사결정나무를 이용해 분류를 할 때는 다음과 같은 방식을 따른다.

1. 여러가지 독립변수 중 하나의 독립변수를 선택하고, 그 독립변수에 대한 기준값을 정한다. 이를 분류 규칙이라고 하고, 최적의 분류 규칙을 찾는 방법은 추후 설명한다.

2. 전체 학습데이터 집합(부모노드)을 선택한 독립변수 값이 기준값보다 작은 데이터와 큰 데이터의 두 그룹(자식노드 1, 2)으로 나눈다.

3. 각각의 자식노드에 대해 또 새롭게 독립변수와 기준값을 선택해 1~2의 단계를 반복하여 하위 자식노드를 만들어나간다. 자식노드에 한 가지 클래스의 데이터만 남게 된다면 그 노드는 거기서 중단한다.

   그런데 현실적으로 한 클래스의 데이터 수가 0이 아니더라도 두 클래스 데이터 비율이 10:1 정도라면 계산의 편의를 위해 그정도에서 멈출 수 있다.

   또한 학습용 데이터가 너무 작아서 마지막노드의 클래스의 비율이 2:1 과 같이 너무 작게 나오면 신뢰도가 떨어지기 때문에 그 전에 중단해준다.

이렇게 자식노드 나누기를 계속하다보면 노드가 계속 뻗어나가는 나무와 같은 형태로 표현된다. 이 나무가 의사결정 나무가 된다.

의사결정 나무에 전체 트레이닝 데이터를 모두 적용해 보면 각 데이터는 갈라지는 두 노드 중 하나의 노드로 계속해서 흘러내려가게 된다. 그렇게 해서 각 노드는 특정 데이터 집합을 갖게 되는데, 각 노드에 속한 데이터들의 클래스 비율을 해당 노드의 조건부 확률분포 $P(Y=k\mid X)_{\text{node}}$ 라고 정의한다.

$$P(Y = k|X)_{node} \approx \frac{N_{\text{node},k}}{N_{\text{node}}}$$

이 의사결정나무를 이용해 테스트 데이터의 클래스를 예측할 때는 가장 상위의 노드에 데이터를 집어넣어 나무의 노드를 따라 흘러내려가게 만들고 맨 마지막에 도달하는 노드의 조건부 확률분포를 이용해 클래스를 예측한다.

그렇다면 첫 번째 단계에서 분류규칙을 정하는 기준은 무엇일까? 이 때 조건부 엔트로피 개념이 사용되는데, 모든 독립변수와 가능한 기준값들에 대해 부모노드와 자식노드 간의 엔트로피를 계산한 후 어떤 조합에서 가장 엔트로피가 낮아지는지를 본다. 즉, 자식노드의 엔트로피가 부모노드의 엔트로피에 비해 얼마나 낮아졌는가가 기준이 된다. 이러한 기준을 정량화한 것을 정보획득량(information gain)이라고 한다.

정보 획득량

정보 획득량(information gain)이란, $X$ 라는 조건에 의해 확률변수 $Y$의 엔트로피가 얼마나 감소했는지를 타나내는 값이다. $Y$의 엔트로피에서$ X$에 대한 $Y$의 조건부엔트로피를 뺀 값으로 정의된다. IG값이 큰 조건, 즉 분류규칙을 선택한다.

$$IG[Y,X] = H[Y] - H[Y|X]$$

H[Y] : 부모노드의 엔트로피

H[Y|X] : 두 자식노드의 조건부 엔트로피의 평균값 . 낮으면 낮을수록 좋다

예를 들어 하나의 데이터셋에 A, B 두 가지의 다른 분류 규칙을 적용하여 다음처럼 서로 다른 의사결정나무가 만들어졌다고 가정하자.

A와 B의 부모노드에 들어간 데이터는 같지만, 자식노드에서는 데이터가 다르게 나뉘어 들어갔다.

• A의 왼쪽 자식노드 - Y=0인 데이터가 30개, Y=1인 데이터가 10개
• A의 오른쪽 자식노드 - Y=0인 데이터가 10개, Y=1인 데이터가 30개
• B의 왼쪽 자식노드 - Y=0인 데이터가 20개, Y=1인 데이터가 40개
• B의 오른쪽 자식노드 - Y=0인 데이터가 20개, Y=1인 데이터가 0개

우선 A와 B의 공통된 부모 노드의 엔트로피를 계산하면 다음과 같다.

$$H[Y] = -\frac{1}{2}\log_2\left(\frac{1}{2}\right) - \frac{1}{2}\log_2\left(\frac{1}{2}\right) = \frac{1}{2}+\frac{1}{2}=1$$

그런 후 A와 B 각각의 IG를 계산해본다.

​ 1) A의 정보획득량

$$H[Y\mid X=X_1] = -\frac{3}{4}\log_2\left(\frac{3}{4}\right) -\frac{1}{4}\log_2\left(\frac{1}{4}\right) = 0.81 \\ H[Y\mid X=X_2] = -\frac{1}{4}\log_2\left(\frac{1}{4}\right) -\frac{3}{4}\log_2\left(\frac{3}{4}\right) = 0.81 \\$$ $$H[Y\mid X]= \frac{1}{2}H[Y\mid X=X_1] + \frac{1}{2}H[Y\mid X=X_2] = 0.81$$ $$IG = H[Y] - H[Y\mid X] = 0.19$$

​ 2) B의 정보획득량

$$H[Y\mid X=X_1] = -\frac{1}{3}\log_2\left(\frac{1}{3}\right) -\frac{2}{3}\log_2\left(\frac{2}{3}\right) = 0.92 \\ H[Y\mid X=X_2] = 0$$ $$H[Y\mid X]= \frac{3}{4}H[Y\mid X=X_1] + \frac{1}{4}H[Y\mid X=X_2] = 0.69$$ $$IG = H[Y] - H[Y\mid X] = 0.31$$

따라서 B가 더 나은 분류규칙임을 알 수 있다.

처음에 독립변수와 임계점을 선정하는 방법은 다음과 같다.

독립변수들 중 맨 첫 번째 변수를 우선 선택하고, 임계점은 처음 두 데이터의 해당 독립변수에 대한 값들의 중간값으로 설정해 IG값을 계산한다. 그 후 두번째와 세번째 데이터의 중간값으로 임계점을 재설정하고 IG값을 또 계산한다. 이 과정을 데이터 끝까지 반복해나가고, 모든 독립변수에 대해 전 과정을 또 반복한다.

여기서 끝이 아니라, 그렇게 해서 나눠진 자식노드에서 위 과정을 반복해나간다.

사실 현실적으로는 위처럼 전 데이터에 대해 하지는 않고 임계점을 특정 기준에 따라 선택해서 일부만 계산한다. 일단은 그냥 위와 같은 방식으로 일일히 IG값을 비교해 분류규칙을 선택한다고 생각하면 된다.

Scikit-Learn의 의사 결정 나무 클래스

scikit-learn이 제공하는 DecisionTreeClassifier 클래스로 붓꽃 분류 문제를 풀어보도록 하자.

여기서는 편의상 꽃의 길이와 폭만을 독립변수로 사용한다.

from sklearn.datasets import load_iris

iris = load_iris()
X = iris.data[:, [2, 3]]
y = iris.target

from sklearn.tree import DecisionTreeClassifier

tree1 = DecisionTreeClassifier(criterion='entropy', max_depth=1, random_state=0).fit(X, y) #max_depth는 의사결정나무의 높이, 즉 자식노드를 몇 단계까지 만들 것인지를 의미한다.

다음은 의사결정나무를 시각화하기 위한 코드이다.

draw_decision_tree 함수는 의사결정나무가 의사결정을 하는 과정을 다이어그램으로 보여주고,

plot_decision_regions 함수는 이러한 의사결정에 의해 데이터의 영역이 어떻게 나눠졌는지를 보여준다.

import io
import pydot
from IPython.core.display import Image
from sklearn.tree import export_graphviz


def draw_decision_tree(model):
    dot_buf = io.StringIO()
    export_graphviz(model, out_file=dot_buf,
                    feature_names=iris.feature_names[2:])
    graph = pydot.graph_from_dot_data(dot_buf.getvalue())[0]
    image = graph.create_png()
    return Image(image)


def plot_decision_regions(X, y, model, title):
    resolution = 0.01
    markers = ('s', '^', 'o')
    colors = ('red', 'blue', 'lightgreen')
    cmap = mpl.colors.ListedColormap(colors)

    x1_min, x1_max = X[:, 0].min() - 1, X[:, 0].max() + 1
    x2_min, x2_max = X[:, 1].min() - 1, X[:, 1].max() + 1
    xx1, xx2 = np.meshgrid(np.arange(x1_min, x1_max, resolution),
                           np.arange(x2_min, x2_max, resolution))
    Z = model.predict(
        np.array([xx1.ravel(), xx2.ravel()]).T).reshape(xx1.shape)

    plt.contour(xx1, xx2, Z, cmap=mpl.colors.ListedColormap(['k']))
    plt.contourf(xx1, xx2, Z, alpha=0.4, cmap=cmap)
    plt.xlim(xx1.min(), xx1.max())
    plt.ylim(xx2.min(), xx2.max())

    for idx, cl in enumerate(np.unique(y)):
        plt.scatter(x=X[y == cl, 0], y=X[y == cl, 1], alpha=0.8,
                    c=[cmap(idx)], marker=markers[idx], s=80, label=cl)

    plt.xlabel(iris.feature_names[2])
    plt.ylabel(iris.feature_names[3])
    plt.legend(loc='upper left')
    plt.title(title)

    return Z

draw_decision_tree(tree1)

생성된 의사결정나무를 보면 독립변수로는 Petal width가 선택되었고, 임계점으로는 0.8이 설정되었다. 이 때 부모노드의 IG값을 구하면 다음과 같다.

$$H[Y] = 1.585\\ H[Y|X]= \frac{1}{3} \times 0 + \frac{2}{3} \times 1 = 0.667\\ IG = 1.585 - 0.667 = 0.918$$

이 의사결정나무에 의해 나눠진 데이터의 영역을 확인해본다.

plot_decision_regions(X, y, tree1, "Depth 1")
plt.show()

클래스 1과 2의 영역이 나눠지지 않았으므로 의사결정나무의 max_depth인수를 2로 설정해 데이터 분류를 한 번 더 실시한다.

tree2 = DecisionTreeClassifier(
    criterion='entropy', max_depth=2, random_state=0).fit(X, y)
draw_decision_tree(tree2)

이번에도 petalwidth가 독립변수로 선택됐는데 기준값은 1.75로 바뀌었다.

맨 아래 단계의 왼쪽 자식노드에는 클래스2인 데이터가 훨씬 많고 오른쪽 자식노드에는 클래스3인 데이터가 훨씬 많게 나누어졌므로 이 정도면 꽤 분류가 잘 될 수 있는 모델이다.

plot_decision_regions(X, y, tree2, "Depth 2")
plt.show()

여기서 한단계 더 해주면, 맨 아래 자식노드드에 엔트로피가 커진 것들이 있긴 하지만 데이터수가 각각 6, 3으로 매우 작고, 그 외 자식노드들은 데이터가 많고 엔트로피가 확 낮아졌기 때문에 결과적으로 평균 엔트로피는 낮아진다.

tree3 = DecisionTreeClassifier(criterion='entropy', max_depth=3,
                               random_state=0)
draw_decision_tree(tree3)

plot_decision_regions(X, y, tree3, "Depth 3")
plt.show()

위 단계에서 맨 오른쪽 노드를 보면 클래스 2에 해당하는 초록색 구간도 4.85를 기준으로 각각 2개와 43개의 데이터로 나눠졌는데 그래프에서 나타나지 않는다. 왜 그럴까?

어차피 나눠진 두 자식노드에서 모두 3번째 클래스인 데이터가 더 많게 나왔으므로 사실 마지막 그 단계는 큰 의미가 없는 작업이라서 경계가 표시되지 않는다. 그 위 노드에서 1:45로 나눠졌을 때 멈췄어도 된다.

여기서 두 단계를 더 해주면 마지막에는 아래와 같이 나눠진다.

tree5 = DecisionTreeClassifier(
    criterion='entropy', max_depth=5, random_state=0).fit(X, y)
draw_decision_tree(tree5)

plot_decision_regions(X, y, tree5, "Depth 5")
plt.show()

이 결과에 대해 confusion matrix를 보면 아래와 같다.

confusion_matrix(y, tree5.predict(X))

회귀 나무

예측값 $\hat{y}$ 을 다음처럼 각 영역마다 고정된 값을 사용하고, 특징을 구분하는 기준값으로 IG값이 아닌 오차 제곱합을 사용하면 회귀분석에서도 의사결정나무를 쓸 수 있다.

이러한 모형을 회귀 나무(regression tree) 라고 한다.

$$\hat{y} = \begin{cases} y_1 & \;\; \text{if} x \geq x_{\text{threshold}}\\ y_2 & \;\; \text{if} x < x_{\text{threshold}} \end{cases}$$

from sklearn.tree import DecisionTreeRegressor

rng = np.random.RandomState(1)
X = np.sort(5 * rng.rand(80, 1), axis=0)
y = np.sin(X).ravel()
y[::5] += 3 * (0.5 - rng.rand(16))

regtree = DecisionTreeRegressor(max_depth=3)
regtree.fit(X, y)

X_test = np.arange(0.0, 5.0, 0.01)[:, np.newaxis]
y_hat = regtree.predict(X_test)

# Plot the results
plt.figure()
plt.scatter(X, y, s=20, edgecolor="black", c="darkorange", label="데이터")
plt.plot(X_test, y_hat, color="cornflowerblue", linewidth=2, label="예측")
plt.xlabel("x")
plt.ylabel(r"$y$ & $\hat{y}$")
plt.title("회귀 나무")
plt.legend()
plt.show()