다운로드
작성자: admin 작성일시: 2016-10-21 15:07:35 조회수: 8184 다운로드: 419
카테고리: 머신 러닝 태그목록:

의사 결정 나무

의사 결정 나무(decision tree)는 여러 가지 규칙을 순차적으로 적용하면서 독립 변수 공간을 분할하는 분류 모형이다. 분류(classification)와 회귀 분석(regression)에 모두 사용될 수 있기 때문에 CART(Classification And Regression Tree)라고도 한다.

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

의사 결정 나무를 이용한 분류법은 다음과 같다.

  1. 여러가지 독립 변수 중 하나의 독립 변수를 선택하고 그 독립 변수에 대한 기준값(threshold)을 정한다. 이를 분류 규칙이라고 한다. 최적의 분류 규칙을 찾는 방법은 이후에 자세히 설명한다.
  2. 전체 학습 데이터 집합(부모 노드)을 해당 독립 변수의 값이 기준값보다 작은 데이터 그룹(자식 노드 1)과 해당 독립 변수의 값이 기준값보다 큰 데이터 그룹(자식 노드 2)으로 나눈다.
  3. 각각의 자식 노드에 대해 1~2의 단계를 반복하여 하위의 자식 노드를 만든다. 단, 자식 노드에 한가지 클래스의 데이터만 존재한다면 더 이상 자식 노드를 나누지 않고 중지한다.

이렇게 자식 노드 나누기를 연속적으로 적용하면 노드가 계속 증가하는 나무(tree)와 같은 형태로 표현할 수 있다.

의사 결정 나무를 사용한 분류 예측

의사 결정 나무에 전체 트레이닝 데이터를 모두 적용해 보면 각 데이터는 특정한 노드를 타고 내려가게 된다. 각 노드는 그 노드를 선택한 데이터 집합을 가진다. 이 때 노드에 속한 데이터의 클래스의 비율을 구하여 이를 그 노드의 조건부 확률 분포 $P(Y=k|X)_{\text{node}}$라고 정의한다.

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

테스트 데이터 $X_{\text{test}}$의 클래스를 예측할 때는 가장 상위의 노드부터 분류 규칙을 차례대로 적용하여 마지막에 도달하는 노드의 조건부 확률 분포를 이용하여 클래스를 예측한다.

$$ \hat{Y} = \text{arg}\max_k P(Y=k|X_{\text{test}})_{\text{last node}} $$

분류 규칙을 정하는 방법

분류 규칙을 정하는 방법은 부모 노드와 자식 노드 간의 엔트로피를 가장 낮게 만드는 최상의 독립 변수와 기준값을 찾는 것이다. 이러한 기준을 정량화한 것이 정보 획득량(information gain)이다. 기본적으로 모든 독립 변수와 모든 가능한 기준값에 대해 정보 획득량을 구하여 가장 정보 획득량이 큰 독립 변수와 기준값을 선택한다.

정보 획득량

정보 획득량(information gain)는 $X$라는 조건에 의해 확률 변수 $Y$의 엔트로피가 얼마나 감소하였는가를 나타내는 값이다. 다음처럼 $Y$의 엔트로피에서 $X$에 대한 $Y$의 조건부 엔트로피를 뺀 값으로 정의된다.

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

예를 들어 A, B 두 가지의 다른 분류 규칙을 적용했더니 다음 처럼 서로 다르게 데이터가 나뉘어 졌다고 가정하자.

그림 18.4.1 : 분류 결과 예시

A 방법과 B 방법 모두 노드 분리 전에는 Y=0 인 데이터의 수와 Y=1 인 데이터의 수가 모두 40개였다.

A 방법으로 노드를 분리하면 다음과 같은 두 개의 자식 노드가 생긴다.

  • 자식 노드 A1은 Y=0 인 데이터가 30개, Y=1 인 데이터가 10개
  • 자식 노드 A2은 Y=0 인 데이터가 10개, Y=1 인 데이터가 30개

B 방법으로 노드를 분리하면 다음과 같은 두 개의 자식 노드가 생긴다.

  • 자식 노드 B1은 Y=0 인 데이터가 20개, Y=1 인 데이터가 40개
  • 자식 노드 B2은 Y=0 인 데이터가 20개, Y=1 인 데이터가 0개

우선 부모 노드의 엔트로피를 계산하면 다음과 같다.

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

A 방법에 대해 IG를 계산하면 다음과 같다.

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

B 방법에 대해 IG를 계산하면 다음과 같다.

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

따라서 B 방법이 더 나은 방법임을 알 수 있다.

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

Scikit-Learn에서 의사 결정 나무는 DecisionTreeClassifier 클래스로 구현되어있다. 여기에서는 붓꽃 분류 문제를 예를 들어 의사 결정 나무를 설명한다. 이 예제에서는 독립변수 공간을 공간상에 표시하기 위해 꽃의 길이와 폭만을 독립변수로 사용하였다.

In [1]:
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)

다음은 의사 결정 나무를 시각화하기 위한 코드이다. draw_decision_tree 함수는 의사 결정 나무의 의사 결정 과정의 세부적인 내역을 다이어그램으로 보여주고 plot_decision_regions 함수는 이러한 의사 결정에 의해 데이터의 영역이 어떻게 나뉘어졌는지를 시각화하여 보여준다.

In [2]:
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
In [3]:
draw_decision_tree(tree1)
Out:
In [4]:
plot_decision_regions(X, y, tree1, "Depth 1")
plt.show()
In [5]:
from sklearn.metrics import confusion_matrix

confusion_matrix(y, tree1.predict(X))
Out:
array([[50,  0,  0],
       [ 0, 50,  0],
       [ 0, 50,  0]])
In [6]:
tree2 = DecisionTreeClassifier(
    criterion='entropy', max_depth=2, random_state=0).fit(X, y)
In [7]:
draw_decision_tree(tree2)
Out:
In [8]:
plot_decision_regions(X, y, tree2, "Depth 2")
plt.show()
In [9]:
confusion_matrix(y, tree2.predict(X))
Out:
array([[50,  0,  0],
       [ 0, 49,  1],
       [ 0,  5, 45]])
In [10]:
tree3 = DecisionTreeClassifier(
    criterion='entropy', max_depth=3, random_state=0).fit(X, y)
In [11]:
draw_decision_tree(tree3)
Out:
In [12]:
plot_decision_regions(X, y, tree3, "Depth 3")
plt.show()
In [13]:
confusion_matrix(y, tree3.predict(X))
Out:
array([[50,  0,  0],
       [ 0, 47,  3],
       [ 0,  1, 49]])
In [14]:
tree4 = DecisionTreeClassifier(
    criterion='entropy', max_depth=4, random_state=0).fit(X, y)
In [15]:
draw_decision_tree(tree4)
Out:
In [16]:
plot_decision_regions(X, y, tree4, "Depth 4")
plt.show()
In [17]:
confusion_matrix(y, tree4.predict(X))
Out:
array([[50,  0,  0],
       [ 0, 49,  1],
       [ 0,  1, 49]])
In [18]:
tree5 = DecisionTreeClassifier(
    criterion='entropy', max_depth=5, random_state=0).fit(X, y)
In [19]:
draw_decision_tree(tree5)
Out:
In [20]:
plot_decision_regions(X, y, tree5, "Depth 5")
plt.show()