決定木とランダマイズドアルゴリズム

2008/5/29
機械学習勉強会
決定木と
ランダマイズドアルゴリズム
田部井靖生
東大・新領域・
情報生命・浅井研・D2
1
なぜ、この内容にしたのか？
• ランダマイズドアルゴリズムの回だから。
• 周囲の人が、決定木(Random Forest)を解析
に使っていて、性能が良いと言っていたから
(実用的)。
• 機械学習の人達の間では、決定木が次に流
行ると言われているから。
- フィーチャーの解釈のしやすさが注目されて
いる
2
発表手順
• 決定木(導入)
• ランダマイズドアルゴリズムを用いて決定木
を学習する手法
• Itemset lattice上から決定木を学習する手法
• Random Forest(時間があれば)
3
決定木とは
テスト
T1
T2
T3 T4
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
1
1
0
1
0
1
1
0
1
1
0
0
1
0
1
1
1
1
1
0
0
0
0
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
1
1
1
1
1
0
0
0
label
1
1
1
0
0
0
0
0
1
1
1
1
1
0
0
0
T1
レコード
0
1
T3
1
T4
T4
0
1
0
0
1
0
0
1
1
0
• 木の根ノードから葉ノードまでに
記述されているテストを繰り返し
実行することで、データを分類す
る木。
4
決定木
T1
T2
T3 T4
1
1
1
1
0
0
0
0
1
1
0
0
1
0
1
0
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
1
1
0
0
1
1
1
1
0
1
1
1
1
1
0
1
1
1
1
1
0
0
0
label
1
0
0
0
1
1
1
0
1
1
1
1
0
0
0
0
T2
1
0
T1
T4
1
0
T3
T4
1
0
1
T4
0
1
1
0
T3
0
0 1
0
0
T1
1
1
0
1
0
1
0
0
1
• テストの選択の順番により決
定木の大きさも変化する
5
決定木の評価法
•
根ノードから葉ノードxに至るテ
ストの数 cost(x)
• 決定木のコスト
=Σ {cost(x)|xは葉ノード}
• 決定木のコストは小さい方が
望ましい(オッカムの剃刀)
• オーバーフィッティングしにくい
• コストが最小な決定木をもとめ
ることは、NP困難
T1
0
1
T3
1
T4
T4
0
1
0
0
1
0
２
２
２
0
1
1
0
３
３
12
6
近似解をもとめる手法
Greedy Algorithm
• ある基準において、
最もよさそうなテスト
を選択し、レコードを
分割
• 分割したレコード集
合に同じ戦略を繰り
返す。
7
レコード分割する基準の例
(Entropy Gain)
T1
T2
T3 T4
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
1
1
0
1
0
1
1
0
1
1
0
0
1
0
1
1
1
1
1
0
0
0
0
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
1
1
1
1
1
0
0
0
label
1
1
1
0
0
0
0
0
1
1
1
1
1
0
0
0
• #P:正レコードの数
• #N:負レコードの数
T1
1
T2(T3)
0
#P=3
#N=5
#P=5
#N=3
1
#P=4
#N=4
0
#P=4
#N=4
T4
1
#P=8
#N=3
0
#P=0
#N=5
8
レコード分割する基準の例
(Entropy Gain)
• 正レコードの割合 p = #P/(#P+#N)
• 負レコードの割合 1-p
• エントロピー ent(p) = -plog2p-(1-p)log2(1-p)
レコード数
n
正レコードの割合 p0=m/n
ent(p0)
ent(p)
1
n1=x
p1=y/x
ent(p1)
0
1
n2=n-x
p2=(m-y)/(n-x)
ent(p2)
・Entropy Gain
Ent(x,y) = ent(p0) – (n1/n)ent(p1)-(n2/n)ent(p2)
分割前のエントロピー
分割後のエントロピー
p
1/2
1
9
その他の基準
• Entropy Gain
- ent(p) = -plog2p-(1-p)log2(1-p)
- C4.5/C5
• Gini index
- g(p) = 1-(P2+(1-P)2)=2P(1-P)
- ID3
 misclassification impurity
- i(p) = 1- max(p, 1-p)
1
0.5
p
1/2
1
10
Greedy Algorithmにより決定木を作
ることの問題点
• Greedy Algorithmにより作られた木は、訓
練データに対しては正答率が高い。
• 一方、作られた決定木は、巨大になる傾
向がある(Overfitting)。
• テストデータに対しては、正答率は必ず
しも高くない。
11
Overfittingの回避法の例
• Pre-pruning
- 決定木を構成中にEntropy
Gainが小さい木は生成しない。
• Post-pruning
- 決定木を構成後にEntropy
Gainが小さい木のノードを除
く。
• そのほかにも、データの性質
に依存したpruning法が存在す
る。
12
ここからが、新しい内容
• Anytime Learning of Decision Tree, JMLR
8(2007) 891-933
13
基本的なアイディア
• Entropy Gainは現在のテスト集
合における、レコードの最適な
分割を求めているので、局所解
に陥りやすい。
• しかし、ナイーブにノードを作
る際に子孫のノードのEntropy
Gainを考慮に入れたのでは時間
がかかる。
• 現在のノードにおける、レコー
ドの最適な分割をサンプリング
により求めたテストを用いて、
部分木が最小となる子ノードを
求める。
14
サンプリングによるテスト選択
• Entropy Gainが0のテストが存在するときは、そ
れを選択(1)。
• Entropy Gainに比例した確率でテストを選ぶ(2)。
Entropy Gain を計算
A:テスト
E:レコード
(1)
(2)
15
最小部分木を構成するテストの選
択
• 現在のノードにおける、
a
最適な子ノードを選択
するために、Entropy
Gainに比例した確率で、
テストを選択する指標
をつかい部分木を計算
する。
• 上記をr回繰り返したの
ち、最小の部分木を構
成するテストを選択す r個の部分木
この中から大きさ最小の部分木を
る。
ひとつ選択する。
16
アルゴリズム
テストを一つ選択
テストの値viを一つ選択
テストの値viのみをもつレコードを集める
17項であげた指標を使い
集めたレコードに対して、部分木をr個
つくり大きさが最小の部分木を選択
テストaに対する見積もられた部分木の大きさは、
すべてのテストの値に対応する部分木の和
17
実験結果(ID3との比較)
• ID3・・・指標として、Entropy Gainを用いた手法
• LSID3のr=5とする。
18
実験結果(ID3-kとの比較)
• ID3・・・指標として、Entropy Gainを用いて、k(=2)個
下の子を見たときの最適なレコードの分割を求める。
19
実験結果(Pruningとの組み合わせ)
• 学習後の枝狩りと組み合わせることによ
り、overfittingがしにくくなり、ノイズに
強くなる。
20
Mining Optimal Decision Trees from Itemset
Lattices, KDD 2007
• Itemset lattice上からDecision Treeを求める
手法を提案した論文
• Randomized Algorithmとは、関係ない。
21
変換前
A
1
1
1
1
1
1
1
1
B
0
0
1
1
0
1
0
1
C
1
1
1
1
1
0
0
0
label
1
1
1
0
0
0
0
0
A
B
C
label
A
A
A
A
A
A
A
A
￢B
￢B
B
B
B
B
￢B
B
C
C
C
C
￢C
￢C
￢C
￢C
変換後
1
1
1
0
0
0
0
0
データ表現
• バイナリーのデータが与えられ
たら各レコードをitemset表現
へと変換する
T j  {i | Bij  1}  {i | Bij  0}
- Bijは変換前のデータの要素
 データ中に含まれない要素を￢
をつけて入れることが重要

ノードをitemset、エッジを
subset関係としたlatticeを決め
ることができる。
22
問題設定
• itemset lattice:子は親にitemを一つ加えてできるノード
• Itemset latticeが与えられたら、エラー率を最小化し、
大きさ最小の決定木を求める。
23
探索における基本的なアイディア
• Itemset latticeを再帰的にトラバースし、itemset Iを含
むtransaction t(I)からすべてのitem iに対して、子供の
itemset I∪{i}とI∪{￢i}を根とする大きさとエラー率が最
小の決定木を求める。
I
I∪{i}
• itemsetを含むtransactionの
labelが１種類になったらストッ
I∪{￢i}
プ
• Minimum support による探査木
の枝狩り(itemsetを含む
transactionの非単調性を利用)
24
アルゴリズム
label cを持つ一つのノードからなる木を返す
Itemset Iを含むtransactionが一つのlabelのみからならば、リター
子のitemsetがmin_supを
満たすならば、木を下る
求めた子のitemset I ∪{i}に対する決定木の集合をCとする
子の集合Cの中で、
大きさが最小かつエラー率最小
のみを採用する。
求めた決定木を返す。
25
アルゴリズムの説明(30～33行目)
A
￢A
B ￢B
C
￢C
• Aと￢A, Bと￢B,
Cと￢Cのそれぞれの
部分木の中からエ
ラー率最小かつ大き
さ最小の部分木のペ
アーを一つ選ぶ
26
頻度計算の工夫
• アルゴリズムで最も時間のかかる箇所は、
line20, 23, 32におけるitemset を含むtransaction
の計算
• 解決策
- ナイーブにitemset Iに対して、それを含む
transactionを計算
- Frequent Itemset Minerを利用
はじめにitemset minerを走らせて、その後、作
られたlattice上で、決定木を作る
27
実験結果(時間)
• MiningのPruningの有効性を検証するために、オリジナル
の実装と比較
• オリジナルよりも高速
28
実験結果(精度)
• unpruned ・・・訓練データにおけるエラー率を
最小化するように学習
• pruned・・・テストデータの期待エラー率を最小
化するように学習
ex(T ) 
 e( I )  x( freq ( I ),..., freq ( I ))
I leaves (T )
1
n
訓練データにおけるエラー率ペナルティー項
• ペナルティー項は、葉のcost (C4.5)。
29
実験結果
30
実験結果(精度)
• unpruned, prunedともJ48よりも精度が良
い。
• J48をpruningすると、大きさは1.75倍小さ
くなり、DL8では、1.5倍小さくなる。
• Pruning後は、DL8の方がJ48よりも1.5倍
大きい。
• Pruning後の、DL8の方がJ48よりも精度が
よいので、小さい決定木が必ずしも良い
わけではない。
31
Random Forests
• 時間があれば、やります。
• Random Forests, Machine Learning, 45, 5-32,
2001
32
Random Forests
データ
データ１
決定木１
データ2
決定木2
データ3
決定木3
データN
決定木N
Boostrapにより、
N個のデータを
生成する
・各データから、
決定木のノードを
作る際、ランダム
サンプリングした
テストの中から
最適なテストを選ぶ。
・変数の数の平方根
・予測は、多数決で
行う。
33
Random Forestの特徴
• Bootstrapにより分割されたデータを用いて、学
習を行うので、データのラベルの分布の偏りに
強い。
• ランダムサンプリングされた、テストの中から、
最適なテストを選ぶので、高次元データも学習
しやすい。
• 遺伝子発現データ解析などで、有効性が示され
ている。
• 実装も豊富(Rのrandom forest packageなど)
34
まとめ
• Decision Treeとランダマイドアルゴリズム(サン
プリング)を使って、効率的に決定木を構築する
手法について解説しました。
• Randomized Algorithmはどういうときにつかう
のか？
- Featureの次元が高いとき、サンプリングした
Featureのサブセットに対して学習を行う。
- 訓練データのラベルの分布に偏りがあるとき、
訓練データをサンプリングにより、分割して、
それぞれのデータに対して、個別の分類器を作
成する(Bootstrap)。
35
補足
36
Q&A
Q:最小の決定木を求めることのNP困難性は、
どの問題に対応付けることにより証明す
るのか？
A:Exact cover by 3-setsと対応付けることに
より証明します。
37
今回紹介した論文
• Induction of Decision Trees, Machine
Learning 1:81-106, 1986
• Anytime Learning of Decision Tree, JMLR
8(2007) 891-933
• Mining Optimal Decision Trees from Itemset
Lattices, KDD 2007
• Random Forests, Machine Learning, 45, 5-32,
2001
38

Download Report