はじめてのパターン認識 第11章の決定木についてまとめた。

決定木とは

決定木とは、if ... then ... elseのような単純な識別規則を組み合わせて
分類・回帰をおこなうノンパラメトリックな手法である。
以下の説明はCARTを前提とする。

特徴

  • 学習した木を可視化することができる。
  • 質的変数も量的変数も扱うことができる。
  • ノード数を増やすと過学習しやすいのでノード数の調整が必須。
  • 訓練データにfitしやすく、高バリアンスである。

木の分割

  • Ci(i=1,,K): クラス
  • N(t)(t=1,,T): ノードtに属するサンプルの数
  • Nj: クラスjに属するサンプルの数
  • Nj(t): ノードtに属するサンプルのうちクラスjに属する数
  • p(t)=N(t)N: サンプルがノードtに属する確率
  • P(Cj)=NjN: クラスjの事前確率
  • p(t|Cj)=Nj(t)Nj: クラスjのサンプルがノードtに属する確率

ノードtにおけるクラスjの事後確率P(Cj|t)は、ベイズの公式より

P(Cj|t)=p(t|Cj)P(Cj)p(t)=p(t|Cj)P(Cj)p(t)1=Nj(t)NjNjNNN(t)=Nj(t)N(t)

となる。

不純度(impurity)

ノードtで分割規則を作るときは不純度の減り方が最も大きな分割を選ぶ。

  • tL: 子ノード(左)
  • tR: 子ノード(右)
  • pL: サンプルxtLに属する確率
  • pR: サンプルxtRに属する確率

とすると、

ΔI(s,t)=I(t)(pLI(tL)+pRI(tR))

ノードtの不純度I(t)

I(t)=ϕ(P(C1|t),,P(CK|t))

と定義すると、ϕ()は、

  • P(Ci|t)=1K(i=1,,K)のとき、
    すなわちどのクラスの事後確率も一様に等しいとき最大になる。
  • あるiについてP(Ci|t)=1となり、jiのときはP(Cj|t)=0
    すなわちただ1つのクラスに定まるとき最小になる。
  • P(Ci|t)(i=1,,K)に関して対称な関数である。

という性質をもつ。

誤り率

I(t)=1maxiP(Ci|t)

ノードtにおいて事後確率P(Cj|t)が最大となるクラスを選ぶ。

交差エントロピー

I(t)=i=1KP(Ci|t)lnP(Ci|t)

ジニ係数

I(t)=i=1KjiP(Ci|t)P(Cj|t)=i=1KP(Ci|t)(1P(Ci|t))=1i=1KP(Ci|t)2

ジニ係数とは、 あるノードから取り出したサンプルを取り出し
そのサンプルがi番目のクラスであるときを1、
それ以外のクラスであるときを0とするベルヌーイ試行を考えたとき、
取り出したサンプルのクラスが異なる確率である。

取り出したサンプルのクラスが異なる確率が大きい
=そのノードに属するサンプルのクラスの偏りが小さい
(1のクラスと0のクラスがほぼ同程度存在する)
=不純度が大きい
ということを示している。

また、P(Ci|t)(1P(Ci|t))はこのベルヌーイ試行の分散なので、
ジニ係数はすべてのクラスに関する分散の和でもある。

なお、ジニ係数はもともとは経済学において
所得分配の不均衡の度合いを示す指標である。

木の剪定 (pruning)

木が大きくなるとバイアスは小さくなるものの汎化性能が下がる、
木が小さいとバイアスが大きくなり再代入誤り率が大きくなる
というトレードオフの調整のために、
誤り率と木の複雑さで決まる許容範囲まで木を剪定する。

  • tT~: 終端ノード
  • M(t): 終端ノードに属するサンプルのうち、事後確率を最大にしないクラスのサンプル数
  • α: 1つの終端ノードがあることによる複雑さのコスト

とすると、木全体の誤り率と複雑さのコストRα(T)

Rα(T)=tT~R(t)+α|T~|=tT~M(t)N+α|T~|

目的は木のコストRα(T)を最小にすることであるが、
αは誤り率と複雑さのバランスをとる正則化パラメータの役割を果たす。

続きは後日追記予定。

ちなみにscikit-learnでは木のpruningはサポートされていない。
そのため、max_depthmax_leaf_nodeの値を
汎化性能を見ながら調整する必要がある。

実践

irisデータセットをsklearn.tree.DecisionTreeClassifierで分類、
bostonデータセットをsklearn.tree.DecisionTreeClassifierで回帰させる。

使用したコードはこちら
また、notebookはこちら

分類木

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

png

ジニ係数が小さくなるようにノードを分割している。
なお、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

png

回帰木では、不純度にmean squared errorが使用されている。

章末問題

11.1

決定木Aの(C1,C2)=(50,150)のノードをtA,L, (150,50)のノードをtA,R
決定木Bの(C1,C2)=(100,200)のノードをtB,L, (100,0)のノードをtB,Rとする。

  • P(C1|tA,L)=50200=14,P(C2|tA,L)=150200=34
  • P(C1|tA,R)=150200=34,P(C2|tA,R)=50200=14

  • P(C1|tB,L)=100300=13,P(C2|tB,L)=200300=23
  • P(C1|tB,R)=100100=1,P(C2|tB,R)=0100=0

(1)

決定木Aの誤り率は50400+50400=14
決定木Bの誤り率は100400+0400=14

よって、どちらの木も誤り率は同じである。

(2)

決定木Aの総コストRA(T)

RA(T)=t{tA,L,tA,R}R(t)+α|T~|=t{tA,L,tA,R}i=12P(Ci|t)lnP(Ci|t)+α|T~|=2(14ln14+34ln34)+2α=0.562335×2+2α=1.125+2α

決定木Bの総コストRB(T)

RB(T)=t{tB,L,tB,R}R(t)+α|T~|=t{tB,L,tB,R}i=12P(Ci|t)lnP(Ci|t)+α|T~|=(13ln13+23ln23+ln1)+2α=0.6365+2α

よって、決定木Bの方が総コストが低い。

(3)

決定木Aの総コストRA(T)

RA(T)=t{tA,L,tA,R}R(t)+α|T~|=t{tA,L,tA,R}i=12P(Ci|t)(1P(Ci|t))+α|T~|=2(14×34+34×14)+2α=34+2α

決定木Bの総コストRB(T)

RB(T)=t{tB,L,tB,R}R(t)+α|T~|=t{tB,L,tB,R}i=12P(Ci|t)(1P(Ci|t))+α|T~|=2(13×23+1×0)+2α=49+2α

よって、決定木Bの方が総コストが低い。

参考文献・サイト