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

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

決定木とは

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

特徴

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

木の分割

$C_{i} (i = 1, \dots, K)$ : クラス
$N (t) (t = 1, \dots, T)$ : ノード $t$ に属するサンプルの数
$N_{j}$ : クラス $j$ に属するサンプルの数
$N_{j} (t)$ : ノード $t$ に属するサンプルのうちクラス $j$ に属する数
$p (t) = \frac{N (t)}{N}$ : サンプルがノード $t$ に属する確率
$P (C_{j}) = \frac{N_{j}}{N}$ : クラス $j$ の事前確率
$p (t | C_{j}) = \frac{N_{j} (t)}{N_{j}}$ : クラス $j$ のサンプルがノード $t$ に属する確率

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

\begin{aligned} P (C_{j} | t) & = \frac{p (t | C_{j}) P (C_{j})}{p (t)} \\ = p (t | C_{j}) P (C_{j}) p (t)^{- 1} \\ = \frac{N_{j} (t)}{N_{j}} \frac{N_{j}}{N} \frac{N}{N (t)} \\ = \frac{N_{j} (t)}{N (t)} \end{aligned}

となる。

不純度(impurity)

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

$t_{L}$ : 子ノード(左)
$t_{R}$ : 子ノード(右)
$p_{L}$ : サンプル $x$ が $t_{L}$ に属する確率
$p_{R}$ : サンプル $x$ が $t_{R}$ に属する確率

とすると、

Δ I (s, t) = I (t) - (p_{L} I (t_{L}) + p_{R} I (t_{R}))

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

I (t) = ϕ (P (C_{1} | t), \dots, P (C_{K} | t))

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

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

という性質をもつ。

誤り率

I (t) = 1 - max_{i} P (C_{i} | t)

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

交差エントロピー

I (t) = - \sum_{i = 1}^{K} P (C_{i} | t) \ln P (C_{i} | t)

ジニ係数

\begin{aligned} I (t) & = \sum_{i = 1}^{K} \sum_{j \neq i} P (C_{i} | t) P (C_{j} | t) \\ = \sum_{i = 1}^{K} P (C_{i} | t) (1 - P (C_{i} | t)) \\ = 1 - \sum_{i = 1}^{K} P (C_{i} | t)^{2} \end{aligned}

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

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

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

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

木の剪定 (pruning)

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

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

とすると、木全体の誤り率と複雑さのコスト $R_{α} (T)$ は

\begin{aligned} R_{α} (T) & = \sum_{t \in \tilde{T}} R (t) + α | \tilde{T} | \\ = \sum_{t \in \tilde{T}} \frac{M (t)}{N} + α | \tilde{T} | \end{aligned}

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

続きは後日追記予定。

ちなみにscikit-learnでは木のpruningはサポートされていない。
そのため、max_depthやmax_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の $(C_{1}, C_{2}) = (50, 150)$ のノードを $t_{A, L}$ , $(150, 50)$ のノードを $t_{A, R}$ 、
決定木Bの $(C_{1}, C_{2}) = (100, 200)$ のノードを $t_{B, L}$ , $(100, 0)$ のノードを $t_{B, R}$ とする。

$P (C_{1} | t_{A, L}) = \frac{50}{200} = \frac{1}{4}, P (C_{2} | t_{A, L}) = \frac{150}{200} = \frac{3}{4}$
$P (C_{1} | t_{A, R}) = \frac{150}{200} = \frac{3}{4}, P (C_{2} | t_{A, R}) = \frac{50}{200} = \frac{1}{4}$
$P (C_{1} | t_{B, L}) = \frac{100}{300} = \frac{1}{3}, P (C_{2} | t_{B, L}) = \frac{200}{300} = \frac{2}{3}$
$P (C_{1} | t_{B, R}) = \frac{100}{100} = 1, P (C_{2} | t_{B, R}) = \frac{0}{100} = 0$

(1)

決定木Aの誤り率は $\frac{50}{400} + \frac{50}{400} = \frac{1}{4}$
決定木Bの誤り率は $\frac{100}{400} + \frac{0}{400} = \frac{1}{4}$

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

(2)

決定木Aの総コスト $R_{A} (T)$ は

\begin{aligned} R_{A} (T) & = \sum_{t \in {t_{A, L}, t_{A, R}}} R (t) + α | \tilde{T} | \\ = - \sum_{t \in {t_{A, L}, t_{A, R}}} \sum_{i = 1}^{2} P (C_{i} | t) \ln P (C_{i} | t) + α | \tilde{T} | \\ = - 2 (\frac{1}{4} \ln \frac{1}{4} + \frac{3}{4} \ln \frac{3}{4}) + 2 α \\ = 0.562335 \dots \times 2 + 2 α \\ = 1.125 + 2 α \end{aligned}

決定木Bの総コスト $R_{B} (T)$ は

\begin{aligned} R_{B} (T) & = \sum_{t \in {t_{B, L}, t_{B, R}}} R (t) + α | \tilde{T} | \\ = - \sum_{t \in {t_{B, L}, t_{B, R}}} \sum_{i = 1}^{2} P (C_{i} | t) \ln P (C_{i} | t) + α | \tilde{T} | \\ = - (\frac{1}{3} \ln \frac{1}{3} + \frac{2}{3} \ln \frac{2}{3} + \ln 1) + 2 α \\ = 0.6365 \dots + 2 α \end{aligned}

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

(3)