決定木とランダムフォレスト 和田　俊和

T1, T2, T3, T4 の値 クラス分類器 (classifier) 出力 （目標属性に一致させる） 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 1 0 0 1 1 0 1 0 1 0 0 1 0 0 1 0 1 1 0 0 1 1 1 0 1 0 1 1 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 T1, T2, T3, T4 の値 クラス分類器 (classifier) 出力 （目標属性に一致させる）

分類ルール テスト If T1=1 Then If T3=1 If T4=1 Then 目標属性＝1 Else 目標属性＝0 Else T1 T2 T3 T4 目標属性 (Objective) 1 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 1 0 0 1 1 0 1 0 1 0 0 1 0 0 1 0 1 1 0 0 1 1 1 0 1 0 1 1 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0

決定木(decision tree) If T1=1 Then If T3=1 If T4=1 Then 目標属性＝1 Else 目標属性＝0 Else 目標属性＝0 T1 1 T3 T4 1 1 T4 1 1 1 ルールによる表現 木構造表現

テストの順番を変えると異なる決定木が得られる T1 T2 T3 T4 目標属性 1 1 1 1 1 1 1 1 0 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 0 1 0 1 1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 1 0 0 0 1 0 0 1 0 1 0 0 T2 1 T1 T4 1 1 T3 T4 T3 1 1 1 T4 1 1 T1 1 1 1 1

用語 属性(attribute) テスト属性（test attributes） レコード(record) 目標属性(Objective attribute) T1　　T2　　T3　　T4 　Ao 1　　　1　　　1　　　1 　1 1 　　1　　　1　　　0 　0 : レコード(record) レコード t の属性 A の値を t[A] と表記 目標値　　目標属性の値の１つ．　　例えば 1 目標属性 Ao、目標値が 1 のとき、 　t[Ao]= 1 となる t を　正(positive) 　t[Ao]≠1となる t を　負(negative)

決定木の最小化

決定木のコスト 決定木の評価 根ノードから葉ノード x に至るテストの数 cost(x) 　決定木のコスト ＝ S {cost(x) | x は葉ノード} 　決定木のコストは小さい 　ほうが望ましい T1 T3 T4 1 2 3 3 12

コストの比較 T2 T1 T4 T3 1 T1 T3 T4 1 3+3+2+2+2=12 4+4+3+3+3+3+4+4+2=30

近似的解法 Greedy Algorithm エントロピー

近似的解法 貪欲(greedy)アルゴリズム 　「最も良さそうな」テストを選択し、 　レコード集合を分割 　分割したレコード集合に 　同じ戦略を繰り返し適用する 　一度選択したテストは変更しない 　「最も良さそうな」　の基準を工夫

最初にT2ではなくT1を選ぶべき T1 T3 T4 1 3+3+2+2+2=12 4+4+3+3+3+3+4+4+2=30 T2 T1 T4 T1 T3 T4 1 3+3+2+2+2=12 4+4+3+3+3+3+4+4+2=30

T2 ではなく T1 を選択する評価基準は？ #P : 正レコードの数 #N: 負レコードの数 T1 1 #P = 3 #N = 5 T1 T2 T3 T4 目標属性 1 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 1 0 0 1 1 0 1 0 1 0 0 1 0 0 1 0 1 1 0 0 1 1 1 0 1 0 1 1 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 #P : 正レコードの数 #N: 負レコードの数 T1 1 #P = 3 #N = 5 #P = 5 #N = 3 T2 1 #P = 4 #N = 4 #P = 4 #N = 4

テスト選択のための評価値を定める y #P+#N = n #P = m (x, y+Δ) (x -Δ, y) (x, y) test 1 (m, m) (n, m) (x, y+Δ) (x -Δ, y) (x, y) test 1 (x, y) (x +Δ, y) #P+#N = x #P = y #P+#N = n-x #P = m-y (x, y-Δ) x (n-m, 0) 　test を選択すると (x, y) が定まる．評価関数を φ(x, y) とおく 　評価基準 φ(x, y) が満たしてほしい条件 φ(x, y) は m/n = y/x のとき最小 φ(x, y) ≦ φ(x, y+Δ), φ(x, y) ≦ φ (x -Δ, y) if m/n < y/x φ(x, y) ≦ φ(x, y-Δ), φ(x, y) ≦ φ (x +Δ, y) if m/n > y/x Δ> 0

評価値:エントロピーゲイン 正レコードの割合 p = #P / (#P + #N) 負レコードの割合 1-p = #N / (#P+#N) エントロピー ent(p) = - p log2 p - (1-p) log2 (1-p) レコード数　 n 正レコードの割合　 p0 = m / n 1 n1 = x p1 = y / x n2 = n - x p2 = (m - y) / (n - x) Entropy Gain Ent(x, y) = ent(p0) - (n1/n) ent(p1) - (n2 /n) ent(p2)

T1を選んだときのエントロピーゲイン #P = 8 #N = 8 ent(8/16) = 2 (- (1/2) log2(1/2)) = 1 #P = 3 #N = 5 #P = 5 #N = 3 ent(3/8) = - (3/8)log2(3/8) - (5/8)log2(5/8) = 0.95444 ent(5/8) = ent(3/8) Entropy Gain = ent(8/16) - (8/16)ent(3/8) - (8/16)ent(5/8) = 1 - 0.95444 = 0.04556

T2を選んだときのエントロピーゲイン #P = 8 #N = 8 ent(8/16) = 1 T2 1 #P = 4 #N = 4 #P = 4 #N = 4 #P = 4 #N = 4 ent(4/8) = 1 ent(4/8) = 1 Entropy Gain = ent(8/16) - (8/16)ent(4/8) - (8/16)ent(4/8) = 0

決定木とは？

決定木の定義 data point

分岐ノード

各ノードにおけるサンプル

各ノードにおけるh(v,θj)の学習 評価には，エントロピーゲインが主に用いられる

エントロピーゲイン

完全な最適化を行うことは不可能 全パラメータ空間T内でエントロピーゲインIを最大化するパラメータθ*を求めるのは時間がかかりすぎて不可能． ランダムにサンプルしたパラメータTjについて，それぞれエントロピーゲインを評価する．（サンプルデータを流す）

葉っぱで計算される内容 vを与えて，葉に到達したときそれがクラスｃに属するか，あるいは出力値ｙに関連づけられているかの確率に関連づけられている．

学習データからランダムにサンプリングしたデータで複数の木を作る． トレーニング集合Sから，ランダムにサンプル集合Skを求め，それぞれについて決定木を求める．（集合間の重なりは許容する） t番目の木についてベクトルvを与えて求められる事後確率pt(c|v)を元にして，T個の木から下記のように確率を統合する．（通常は平均を使う）

学習データからランダムにサンプリングしたデータで複数の木を作る．

学習の終了条件 1. あらかじめ定めた深さに達した場合 2. ノードに割り当てられた学習データの個数が一定値以下になったとき 3. 分割によるエントロピーゲインが一定値以下になったとき

画像への応用

点対応付けの際の学習データの生成（Lepetit 2006）

Feature Harvesting for Tracking-by-Detection

kinect からの身体部位推定shoutton 2011 open NIに組み込まれている． 人間の身体を３１個の部位に分割 入力：デプスマップ 出力：部位ラベル 奥行きの差を特徴として用いる．

学習データ モーションキャプチャと距離データペアを取得

身体部位推定結果

特徴抽出

Semantic Texton Forest Shotton 2008

Bag of Semantic textons

結果

回帰計算の例 Hough Forest Gall et al. 2009

Hough Forest Gall et al. 2009

Hough Forestによる投票結果

演習問題 左の表のようなテスト-目標属性間の関係があるとき，エントロピーゲインに基づいて決定木を求めなさい T1 T2 T3 T4 目標属性 1 0 1 1　　　1 1 1 1 1　　　1 1 1 1 0　　　0 1 0 1 0　　　0 1 1 0 1　　　0 1 0 0 1　　　0 0 1 0 1　　　1 0 0 1 1　　　1 0 1 0 1 　　 1 0 0 0 1　　　1 0 0 1 0　　　0 0 1 0 0　　　0 左の表のようなテスト-目標属性間の関係があるとき，エントロピーゲインに基づいて決定木を求めなさい