はじめてのパターン認識 第11章 決定木

はじめてのパターン認識 第11章の決定木についてまとめた。
決定木とは
決定木とは、if ... then ... else
のような単純な識別規則を組み合わせて
分類・回帰をおこなうノンパラメトリックな手法である。
以下の説明はCARTを前提とする。
特徴
- 学習した木を可視化することができる。
- 質的変数も量的変数も扱うことができる。
- ノード数を増やすと過学習しやすいのでノード数の調整が必須。
- 訓練データにfitしやすく、高バリアンスである。
木の分割
: クラス : ノード に属するサンプルの数 : クラス に属するサンプルの数 : ノード に属するサンプルのうちクラス に属する数 : サンプルがノード に属する確率 : クラス の事前確率 : クラス のサンプルがノード に属する確率
ノード
となる。
不純度(impurity)
ノード
: 子ノード(左) : 子ノード(右) : サンプル が に属する確率 : サンプル が に属する確率
とすると、
ノード
と定義すると、
のとき、
すなわちどのクラスの事後確率も一様に等しいとき最大になる。- ある
について となり、 のときは 、
すなわちただ1つのクラスに定まるとき最小になる。 に関して対称な関数である。
という性質をもつ。
誤り率
ノード
交差エントロピー
ジニ係数
ジニ係数とは、 あるノードから取り出したサンプルを取り出し
そのサンプルが
それ以外のクラスであるときを0とするベルヌーイ試行を考えたとき、
取り出したサンプルのクラスが異なる確率である。
取り出したサンプルのクラスが異なる確率が大きい
(1のクラスと0のクラスがほぼ同程度存在する)
ということを示している。
また、
ジニ係数はすべてのクラスに関する分散の和でもある。
なお、ジニ係数はもともとは経済学において
所得分配の不均衡の度合いを示す指標である。
木の剪定 (pruning)
木が大きくなるとバイアスは小さくなるものの汎化性能が下がる、
木が小さいとバイアスが大きくなり再代入誤り率が大きくなる
というトレードオフの調整のために、
誤り率と木の複雑さで決まる許容範囲まで木を剪定する。
: 終端ノード : 終端ノードに属するサンプルのうち、事後確率を最大にしないクラスのサンプル数 : 1つの終端ノードがあることによる複雑さのコスト
とすると、木全体の誤り率と複雑さのコスト
目的は木のコスト
続きは後日追記予定。
ちなみにscikit-learnでは木のpruningはサポートされていない。
そのため、max_depth
やmax_leaf_node
の値を
汎化性能を見ながら調整する必要がある。
実践
irisデータセットをsklearn.tree.DecisionTreeClassifier
で分類、
bostonデータセットをsklearn.tree.DecisionTreeClassifier
で回帰させる。
分類木
import os
import sys
sys.path.append(os.path.abspath('{}/../../'.format(os.getcwd())))
from sklearn.datasets import load_iris
from sklearn.cross_validation import train_test_split
from sklearn.metrics import accuracy_score
from IPython.display import Image
import swsk
# http://pythondatascience.plavox.info/scikit-learn/scikit-learn%E3%81%A7%E6%B1%BA%E5%AE%9A%E6%9C%A8%E5%88%86%E6%9E%90/
# http://sucrose.hatenablog.com/entry/2013/05/25/133021
# load dataset
iris = load_iris()
print(iris.target_names)
print(iris.feature_names)
# split dataset into training and test subsets
tr_x, te_x, tr_y, te_y = train_test_split(iris.data, iris.target, test_size=0.4)
print(tr_x.shape, tr_y.shape)
print(te_x.shape, te_y.shape)
# learn
clf = swsk.tree.DTClassifier(tr_x, tr_y, {'max_depth': 3})
# accuracy
pred_tr_y = clf.predict(tr_x)
pred_te_y = clf.predict(te_x)
print('accuracy against tr data: {}'.format(round(accuracy_score(tr_y, pred_tr_y), 5)))
print('accuracy against te data: {}'.format(round(accuracy_score(te_y, pred_te_y), 5)))
# show tree
graph = clf.graph(iris)
Image(graph.create_png())
['setosa' 'versicolor' 'virginica']
['sepal length (cm)', 'sepal width (cm)', 'petal length (cm)', 'petal width (cm)']
(90, 4) (90,)
(60, 4) (60,)
accuracy against tr data: 0.98889
accuracy against te data: 0.96667
ジニ係数が小さくなるようにノードを分割している。
なお、criterion='entropy'
とすれば不純度を交差エントロピーに変更できる。
回帰木
import os
import sys
sys.path.append(os.path.abspath('{}/../../'.format(os.getcwd())))
from sklearn.datasets import load_boston
from sklearn.cross_validation import train_test_split
from sklearn.metrics import mean_squared_error
from IPython.display import Image
import swsk
# load dataset
boston = load_boston()
print(boston.feature_names)
# split dataset into training and test subsets
tr_x, te_x, tr_y, te_y = train_test_split(boston.data, boston.target, test_size=0.4)
print(tr_x.shape, tr_y.shape)
print(te_x.shape, te_y.shape)
# learn
clf = swsk.tree.DTRegressor(tr_x, tr_y, {'max_depth': 3})
# accuracy
pred_tr_y = clf.predict(tr_x)
pred_te_y = clf.predict(te_x)
print('mse against tr data: {}'.format(round(mean_squared_error(tr_y, pred_tr_y), 5)))
print('mse accuracy against te data: {}'.format(round(mean_squared_error(te_y, pred_te_y), 5)))
# show tree
graph = clf.graph(boston)
Image(graph.create_png())
['CRIM' 'ZN' 'INDUS' 'CHAS' 'NOX' 'RM' 'AGE' 'DIS' 'RAD' 'TAX' 'PTRATIO'
'B' 'LSTAT']
(303, 13) (303,)
(203, 13) (203,)
mse against tr data: 11.95696
mse accuracy against te data: 30.75719
回帰木では、不純度にmean squared errorが使用されている。
章末問題
11.1
決定木Aの
決定木Bの
(1)
決定木Aの誤り率は
決定木Bの誤り率は
よって、どちらの木も誤り率は同じである。
(2)
決定木Aの総コスト
決定木Bの総コスト
よって、決定木Bの方が総コストが低い。
(3)
決定木Aの総コスト
決定木Bの総コスト
よって、決定木Bの方が総コストが低い。