의사 결정 나무(Decision Tree)는 여러 가지 규칙(rule)을 순차적으로 적용하면서 독립 변수 공간을 분할하는 분류 모형이다. 분류(classification)와 회귀 분석(regression)에 모두 사용될 수 있으며 CART(Classification And Regression Tree Analysis) 모형이라고도 불리운다. 여기에서는 분류를 위한 의사 결정 모형을 살펴보자
의사 결정 나무에서는 규칙(rule)을 기반으로 독립 변수 공간을 영역(region)으로 분할하고 분할된 각각의 영역에 대해 다시 새로운 규칙을 적용하여 독립 변수 공간을 $M$개의 영역 $\mathbf{R}_m$으로 세분화 한다. 따라서 다음과 같은 조건부 확률을 가지는 확률 기반
$$ p(y \mid x) = \sum_{m=1}^M \mathrm{I}(x \in \mathbf{R}_m) $$여기에서 $\mathrm{I}(x \in \mathbf{R}_m)$ 은 $x$ 가 $\mathbf{R}_m$ 에 속하면 1 이고 아니면 0 인 값을 가진다.
영역 분할 규칙은 일반적으로 특정한 독립 변수(feature)의 값이
이렇게 규칙을 적용하는 위치를 노드(node)라고 하며 규칙을 연속적으로 적용하면 노드가 계속 증가하는 나무(tree)와 같은 형태로 표현할 수 있다.
In [1]:
import pydot
import StringIO
from IPython.core.display import Image
def drawtree(command):
graph = pydot.graph_from_dot_data(command)
image = graph.create_png()
image_buf = StringIO.StringIO()
image_buf.write(image)
return Image(image_buf.getvalue())
In [2]:
command = """
digraph Tree {
node [shape=box, fontname="NanumGothic", fontsize=9];
edge [labeldistance=2, fontname="NanumGothic", fontsize=9];
0 [label="해야할 일이 있는가"];
1 [label="집에 있는다."];
0 -> 1 [labelangle=45, headlabel="네"];
2 [label="날씨가 어떤가"];
0 -> 2 [labelangle=-45, headlabel="아니오"];
3 [label="해변으로 놀러간다"];
2 -> 3 [labelangle=45, headlabel="맑음"];
4 [label="친구들이 바쁜가"];
2 -> 4 [labelangle=-45, headlabel="비"];
5 [label="집에 있는다"];
4 -> 5 [labelangle=45, headlabel="네"];
6 [label="같이 영화 보러 간다"];
4 -> 6 [labelangle=-45, headlabel="아니오"];
}
"""
drawtree(command)
Out[2]:
의사 결정 나무의 장점은 분류 과정이 사람이 쉽게 이해할 수 있는 직관적 규칙을 가진다는 점이다. 이 장점을 활용하기 위해서는 의사 결정 규칙을 시각화를 통해 표현해야 한다. 의사 결정 나무를 시각화하려면 GraphViz 프로그램과 pydot 파이썬 패키지를 사용한다.
노드에서 규칙이 적용되어 영역이 분할되면 각 영역 $R_m$에 속하는 표본 데이터 집합 $\{x_m, y_m\}$ 이 결정된다. 만약 하나의 영역에 속하는 모든 표본 데이터가 같은 클래스 값을 가진다면 더이상 영역을 분할할 필요가 없으므로 규칙 적용이 종료되고 하위 노드가 생성되지 않는다. 가장 극단적인 경우는 최종 영역이 하나의 표본 데이터만을 가지는 경우이다.
In [1]:
from sklearn.tree import export_graphviz
def draw_decision_tree(classifier):
dot_buf = StringIO.StringIO()
export_graphviz(classifier, out_file=dot_buf, feature_names=iris.feature_names)
graph = pydot.graph_from_dot_data(dot_buf.getvalue())
#getvalue는 넣은 값을 다시 불러들일 때
image = graph.create_png()
#png 포맷 형태로 랜더링을 한다.
image_buf = StringIO.StringIO()
#메모리 상에 파일이 있다.
image_buf.write(image)
#이미지는 ipython의 코어의 디스플레이의 이미지를 임포트 했다.
return Image(image_buf.getvalue())
def plot_decision_regions(X, y, classifier, title):
resolution=0.01
#점과 점 사이를 연결해주는 것?
markers = ('s', '^', 'o', '^', 'v')
#클래스가 많이 필요하지는 않지만 일단 써 놓은 것
colors = ('red', 'blue', 'lightgreen', 'gray', 'cyan')
cmap = mpl.colors.ListedColormap(colors[:len(np.unique(y))])
#칼라맵을 그대로 쓰기 위해서 만들어 놓은 것
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 = classifier.predict(np.array([xx1.ravel(), xx2.ravel()]).T)
Z = Z.reshape(xx1.shape)
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('petal length [cm]')
plt.ylabel('petal width [cm]')
plt.legend(loc='upper left')
plt.title(title)
plt.show()
In [4]:
from sklearn.datasets import load_iris
from sklearn.cross_validation import train_test_split
iris = load_iris()
X = iris.data[:, [2, 3]]
y = iris.target
In [5]:
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import confusion_matrix
In [6]:
tree1 = DecisionTreeClassifier(criterion='entropy', max_depth=1, random_state=0).fit(X, y) #max_depth는 줄기 최대값
plot_decision_regions(X, y, tree1, "Depth 1")
In [7]:
draw_decision_tree(tree1)
Out[7]:
In [8]:
confusion_matrix(y, tree1.predict(X))
Out[8]:
In [9]:
tree2 = DecisionTreeClassifier(criterion='entropy', max_depth=2, random_state=0).fit(X, y)
In [10]:
plot_decision_regions(X, y, tree2, "Depth 2")
In [13]:
draw_decision_tree(tree2) # <=1.75는 thresholds값
Out[13]:
In [14]:
confusion_matrix(y, tree2.predict(X))
Out[14]:
In [15]:
tree3 = DecisionTreeClassifier(criterion='entropy', max_depth=3, random_state=0).fit(X, y)
In [16]:
plot_decision_regions(X, y, tree3, "Depth 3")
In [17]:
draw_decision_tree(tree3)
# 그 아래는 X축을 기준으로 나누었다.
Out[17]:
In [18]:
confusion_matrix(y, tree3.predict(X))
Out[18]:
In [19]:
tree4 = DecisionTreeClassifier(criterion='entropy', max_depth=4, random_state=0).fit(X, y)
In [20]:
plot_decision_regions(X, y, tree4, "Depth 4")
In [21]:
draw_decision_tree(tree4)
# 1번 더 했다. 그 밑에는 다시 또 sepal width 기준으로 갈랐더니 또 다른 새로운 영역이 생겼다.
Out[21]:
In [22]:
confusion_matrix(y, tree4.predict(X))
Out[22]:
In [23]:
tree5 = DecisionTreeClassifier(criterion='entropy', max_depth=5, random_state=0).fit(X, y)
In [24]:
plot_decision_regions(X, y, tree5, "Depth 5")
In [25]:
draw_decision_tree(tree5)
Out[25]:
In [26]:
confusion_matrix(y, tree5.predict(X))
Out[26]:
노드를 생성하는 것은 독립 변수 $X$의 값에 따라 데이터를 분리하는 작업이다.
올바른 노드 생성 즉, 데이터 분리는 데이터를 분리함으로써 각 노드 안에 있는 데이터의 동질성(purity)이 높아지거나 전체 확률 분포의 엔트로피가 낮아져야 한다. 이러한 기준을 정량화한 것이 information gain 또는 impurity function 이다.
의사 결정 나무에서는 이러한 Information Gain 값이나 impurity function 이 가장 많이 향상되는 독립 변수 $X$ 와 기준값(threshold)를 다양한 시도를 통해 찾아낸다.
IG(information gain)는 데이터 분리에 의해 확률 변수의 엔트로피가 얼마나 감소하였는가를 나타내는 값이다.
$$ IG[Y,X] = H[Y] - H[Y|X] $$예를 들어 다음과 같은 두가지 경우를 생각하자.
A 방법과 B 방법 모두 노드 분리 전에는 Y=0 인 데이터의 수와 Y=1 인 데이터의 수가 모두 40개였다.
A 방법으로 노드를 분리하면 다음과 같은 두 개의 자식 노드가 생긴다.
B 방법으로 노드를 분리하면 다음과 같은 두 개의 자식 노드가 생긴다.
우선 부모 노드의 엔트로피를 계산하면 다음과 같다.
$$ H[D] = -\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[A1] = -\dfrac{3}{4}\log_2\left(\dfrac{3}{4}\right) -\dfrac{1}{4}\log_2\left(\dfrac{1}{4}\right) = 0.81 $$$$ H[A2] = -\dfrac{1}{4}\log_2\left(\dfrac{1}{4}\right) -\dfrac{3}{4}\log_2\left(\dfrac{3}{4}\right) = 0.81 $$$$ IG = H[D] - \dfrac{1}{2} H[A1] - \dfrac{1}{2} H[A2] = 0.19 $$B 방법에 대해 IG를 계산하면 다음과 같다.
$$ H[B1] = -\dfrac{1}{3}\log_2\left(\dfrac{1}{3}\right) - \dfrac{2}{3}\log_2\left(\dfrac{2}{3}\right) = 0.92 $$$$ H[B2] = 0 $$$$ IG = H[D] - \dfrac{3}{4} H[B1] - \dfrac{1}{4} H[B2] = 0.31 $$따라서 B 방법이 더 나은 방법임을 알 수 있다.
In [2]:
n_classes = 3
plot_colors = "bry"
plot_step = 0.02
plt.figure(figsize=(10,7))
for pairidx, pair in enumerate([[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]):
X = iris.data[:, pair]
y = iris.target
idx = np.arange(X.shape[0])
np.random.seed(13)
np.random.shuffle(idx)
X = X[idx]
y = y[idx]
mean = X.mean(axis=0)
std = X.std(axis=0)
X = (X - mean) / std
clf = DecisionTreeClassifier().fit(X, y)
plt.subplot(2, 3, pairidx + 1)
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, plot_step),
np.arange(y_min, y_max, plot_step))
Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)
cs = plt.contourf(xx, yy, Z, cmap=plt.cm.Paired)
plt.xlabel(iris.feature_names[pair[0]])
plt.ylabel(iris.feature_names[pair[1]])
plt.axis("tight")
for i, color in zip(range(n_classes), plot_colors):
idx = np.where(y == i)
plt.scatter(X[idx, 0], X[idx, 1], c=color, label=iris.target_names[i], cmap=plt.cm.Paired)
plt.axis("tight")
plt.tight_layout()
plt.show()
In [3]:
df = pd.read_csv('http://dato.com/files/titanic.csv', index_col=0)
df.head()
# Pclass는 특등실~ Name은 피쳐에 넣으면 안 된다. 넣으면 오버피팅이 된다. SibSp는 형제가 같이 탑승했느냐
# parch는 가족수. fare는 Pclass랑 거의 비슷하니까 다중공선성이 일어날 수 있다.
# 그래서 상식적으로 넣을 만한 것은 몇 등실, 나이, 성별만
Out[3]:
In [4]:
feature_names = ["Pclass", "Age", "Sex"]
dfX = df[feature_names]
dfy = df["Survived"]
dfX.tail()
Out[4]:
In [5]:
dfX.ix[:,"Age"].fillna(int(dfX["Age"].mean()), inplace=True)
dfX.tail() #imputaion 과정
Out[5]:
In [6]:
from sklearn.preprocessing import LabelEncoder
dfX.ix[:,"Sex"] = LabelEncoder().fit_transform(dfX["Sex"])
dfX.tail()
Out[6]:
In [7]:
from sklearn.preprocessing import OneHotEncoder
dfX2 = pd.DataFrame(OneHotEncoder().fit_transform(dfX["Pclass"].as_matrix()[:,np.newaxis]).toarray(),
columns=['first_class', 'second_class', 'third_class'], index=dfX.index)
dfX = pd.concat([dfX, dfX2], axis=1)
del(dfX["Pclass"])
dfX.tail()
Out[7]:
In [8]:
from sklearn.cross_validation import train_test_split
X_train, X_test, y_train, y_test = train_test_split(dfX, dfy, test_size=0.25, random_state=1)
In [9]:
from sklearn.tree import DecisionTreeClassifier
model = DecisionTreeClassifier(criterion='entropy', max_depth=3, min_samples_leaf=5).fit(X_train, y_train)
In [10]:
command_buf = StringIO.StringIO()
export_graphviz(model, out_file=command_buf, feature_names=['age','sex','1st_class','2nd_class','3rd_class'])
graph = pydot.graph_from_dot_data(command_buf.getvalue())
image = graph.create_png()
image_buf = StringIO.StringIO()
image_buf.write(image)
Image(image_buf.getvalue())
In [12]:
from sklearn.metrics import classification_report, confusion_matrix
In [13]:
confusion_matrix(y_train, model.predict(X_train))
Out[13]:
In [14]:
confusion_matrix(y_test, model.predict(X_test))
Out[14]:
In [15]:
print(classification_report(y_train, model.predict(X_train)))
In [16]:
print(classification_report(y_test, model.predict(X_test)))
In [17]:
from sklearn.datasets import fetch_20newsgroups
categories = [
'talk.religion.misc',
'comp.graphics',
'sci.space',
]
news = fetch_20newsgroups(subset='train', categories=categories, shuffle=True, random_state=1)
news_test = fetch_20newsgroups(subset='test', categories=categories, shuffle=True, random_state=2)
In [19]:
len(news.data), len(news_test.data)
Out[19]:
In [20]:
set(news.target), set(news_test.target)
Out[20]:
In [21]:
from sklearn.feature_extraction.text import TfidfVectorizer
vect = TfidfVectorizer(stop_words="english")
X = vect.fit_transform(news.data)
y = news.target
In [22]:
from sklearn.tree import DecisionTreeClassifier
model = DecisionTreeClassifier(criterion='entropy').fit(X,y)
In [23]:
X_test = vect.transform(news_test.data)
y_test = news_test.target
from sklearn.metrics import classification_report, confusion_matrix
print(classification_report(y_test, model.predict(X_test)))
In [24]:
print(classification_report(y, model.predict(X)))
In [25]:
import pydot, StringIO
from sklearn.tree import export_graphviz
from IPython.core.display import Image
def draw_decision_tree(classifier):
dot_buf = StringIO.StringIO()
export_graphviz(classifier, out_file=dot_buf, feature_names=[x.encode("utf-8") for x in list (vect.vocabulary_)])
graph = pydot.graph_from_dot_data(dot_buf.getvalue())
image = graph.create_png()
image_buf = StringIO.StringIO()
image_buf.write(image)
return Image(image_buf.getvalue())
In [26]:
draw_decision_tree(model)
In [27]:
news.target_names
Out[27]:
In [28]:
df = pd.DataFrame({"x":news.data, "y":news.target})
df.tail()
Out[28]:
In [29]:
df[df.x.str.contains("inclination*")]
Out[29]:
In [30]:
print(df.x[113])