最近、複数の識別器*を組み合わせて全体で認識性能を上げる方法が考えられている。
*今回は識別器として決定木を使用。
決定木は偏りが小さく分散が大きいという性質を持っており、組み合わせる事で分散を小さくできる。
本章では、決定木を下記の3つの手法によって組み合わせてみる。
・バギング
・アダブースト←パス
・ランダムフォレスト

決定木

単純なルールを組み合わせて複雑な識別境界を得る方法に決定木がある。
図のようなデータ分布があった場合、●と○のクラスを識別するための識別規則は非線形になる
この図の場合、x1のa,d,e x2のb,cより大きいか小さいかを見れば●と○を識別できる。

このように、ある特徴軸の値としきい値の大小関係を判断する過程は図11.2に示すような決定木で表現できる

決定木はノード（丸、四角）とリンク（線）によって表現される

根ノード：木の始まり:1
終端ノード,葉ノード：木の終わり：6,7,8,9,10,11
内部ノート：根でも葉でもないノード：2,3,4,5

決定木の構成手法

学習データから決定木を構成する方法はボトムアップ的な手法とトップダウン的な手法がある

ボトムアップ的な手法は、ある一つの学習データを正しく識別できる特徴を探して特殊な識別規則をつくり、特徴に対する制約を緩めながら、他の学習データも正しく識別できるよう規則を一般化していく

トップダウン的な手法は、根ノードですべての学習データをできるだけ誤りの少ない様にクラス分けできる特徴軸を探して、特徴空間を2分する規則を求め、その後さらに2分して、2分して、というのを繰り返していく
この手法を分割統治法といい、現在の主流

トップダウン的に決定木を学習データから構成するには、次の要素を考える必要がある
・各ノードにおける特徴軸としきい値の選択
・終端ノードの決定（一つのノードに複数クラスがあってよいのか、木の剪定をどこまでおこなうか)
・終端ノードに対する多数決によるクラスの割り当て

決定木の学習方式にはCART,ID3,C4.5などがある
*今回はCARTで実施する

決定木では、各領域に特定のクラスを割り当てて、入力データのクラス分類を行う。
クラスを$C_i(i=1,2,,,K)$とした時、終端ノードtが表すクラスの事後確率を下記の様に計算する。

クラスラベル付きの学習データ集合を

{(x_i, t_i)}(i=1,2,,,N)

クラスjに属する学習データ数を$N_j$とすれば、クラスjの事前確率は

p(c_j)=N_j/N

特徴空間は、ノードを経るごとに分割されていく。
あるノードtの領域に属する学習データ数を$N(t)$とする。$N(t)$個のデータのうち、j番目のクラスに属するデータを$N_j(t)$で表す。

\sum_{j=1}^kN_j(t) = N(t)

クラスjの学習データがノードtに属する確率
$$p(t|C_j) = \frac{N_j(t)}{N_j}$$

それらの同時確率
$$p(C_j,t)=P(C_j)p(t|C_j)=\frac{N_j}{N}\frac{N_j(t)}{N_j}=\frac{N_j(t)}{N}$$

ノードtの周辺確率
$$p(t) =\sum_{j=1}^{k}p(C_j,t)=\sum_{j=1}^{K}\frac{N_j(t)}{N}=\frac{N(t)}{N}$$

tにおけるクラスjの事後確率
$$P(C_j|t)=\frac{p(C_j,t)}{p(t)}=\frac{N_j(t)}{N(t)}$$

tにおいてクラス識別を行う場合、事後確率が最大になるクラスを選べば良い
$$識別クラス=argmaxP(C_j|t)$$

ノード分割規則

各ノードにおけるd次元特徴空間の最適な分割は、特徴軸ごとに可能な考えうる分割を不純度とよばれる評価関数で評価し、選択する。
あるノードtの分割規則を構成するときには、これらすべての候補点を不純度で評価する。

ノードtで分割規則を作る時、不純度の減り方が一番大きな分割を選べば良い

$$不純度の減少量=ΔZ(s,t)=Z(t)-(p_LZ(t_L)+p_RZ(t_R))$$

あやめデータの例

木の剪定アルゴリズム

木を構成した学習データに対する再代入誤り率を定義する。
終端ノードにおける誤り数M(t)は終端ノードに属する学習データのうち事後確率を最大にしないクラスの学習データ数である。
このノードの誤り率は
$$R(t) = \frac{M(t)}{N}(t∈T')$$
Nは総学習データ数

木全体での再代入誤り率の推定値は
$$R(T)=\sum_{t∈T'}R(t)$$

木の複雑さを終端ノードの数で評価することにする
木Tのノード数を|T|で表現すれば
終端ノード数は|T'|と表現できる

一つの終端ノードがあることによる複雑さをコストαで表せば
$$R_α(t) = R(t) + α$$
これは、一つの終端ノードにおける誤り率と複雑さのコストを和となる

木全体では
$$R_α(T)=\sum_{t∈T'}R_α(t)=R(T) + α|T'|$$

目的は木のコストRα(T)を最小にすることにあるが
|~T|が大きくなれば誤り率R(T)は減少し、逆に終端ノードの数が減れば誤り率は大きくなる
係数αはこれら２つの要素の間のバランスをとる正則化パラメータの役割を果たしている

αを小さく設定すると大きな木になり
αを大きく設定すると小さな木になる

任意のノードtにおける再代入誤り率は、識別クラスが式(11.4)の最大事後確率で決まるので
$$r(t) = 1 -maxP(C_i|t)$$

式(11.12)で定義したR(t)は、式(11.2)で定義したノードtに学習データが属する確率p(t)を用いれば
$$R(t)$ = r(t)p(t)$$

と書くことができる

これは、ノードtが終端ノードであれば、全体の誤りに対するtの寄与とかんがえられる

任意のノードtを根ノードとする分枝をTtで表す
Rα(Tt) < Rα(t)であれば、tを終端ノードと考えたときの誤りと複雑さのコストより
tの分枝がもつコストの方が小さいのでTtをそのままにしておいた方が全体のコストは小さくなる
しかし、正則化パラメータαを次第に大きくしていけば両者は等しくなり、その時のαは
$$α = \frac{R(t)-R(T_t)}{|T'_t|-1}$$

すなわち、ノードtを終端ノードにしてもコストは変わらないので
$Tt$を剪定してしまってよいことになる

そこで、αをtの関数とみなして
$$g(t) = \frac{R(t)-R(T_t)}{|T'_t|-1}$$

これをノードtのリンクの強さに関する尺度と考える

木の剪定は、すべての非終端ノードについてg(t)を計算し
$$g(t)=\frac{R(t)-R(T_t)}{|T'_t|-1}$$

最小値を取るすべてのノードを終端ノードとし、その子孫を削除して木を剪定する
剪定された木にたいして同じ手続きを繰り返し、根ノードのみになるまで剪定する

アヤメのデータで実践

図aではノード7が最小なので、7の子孫を剪定して良い
図bではノード4が最小なので、4の子孫を剪定して良い
図cではノード1が最小なので、1の子孫を剪定して良い

すると根ノードのみになってしまった、どこかで止める必要があった。
止める所を探すには、ホールド・アウト法や交差確認法を用いて誤り率が小さくなるKの値を求める
そして、誤りの最小値とその点の標準偏差を加えた値を超えたところのサイズの木を最適とする事が経験的に提案されている
(1標準偏差ルール)

バギング

複数の識別器を組み合わせる方法に、バギングがある
学習データのブートストラップサンプルを用いて複数の識別器を学習させ、新しい入力データのクラスはそれらの識別器の多数決で決めるという方法である
決定木は、学習データの少しの変化で識別器の性能が大きく変わってしまう不安定な識別器だが、図11.6の様に複数の決定木からの結果の多数決を取ることで安定したものにできる