decision tree

ID3 → C4.5 → C5.0と発展

ID3: Quinlan, J.R.(1986). Induction of decision trees. Machine Learning, 1, 81-106. (東京大学附属図書館の左列の「電子ジャーナル・電子ブックを読む」 →タイトル「machine learning」で検索実行。2の「Machine Leanring」をクリック。欲しいのはVol.1なので、中央の列の「Current-65」を「4-1」に変更。表示されたなかの一番下のNumber 1をクリック。そのなかの下から2番目。
C4.5: Bagging, Boosting, and C4.5
Ross Quinlanのページ

用語

decision tree(決定木): いくつかの属性値から、予測値を返すもの。
classification learning: 属性値と予測値が離散値の場合のdecision treeの学習
regression(回帰): 属性値と予測値が連続値の場合のdecision treeの学習
boolean classification: 予測値がYes/Noの二値のもの

以下では離散的なdecision treeを考える。

例: decision tree

まず、属性Aを調べ、それがaなら次に属性Bを調べ、それがeならDの値はYesと予測する。

以下の表(A,B,Cが属性値、Dが予測(するべき)値の時)
A B C D
a e s Yes
a f s No
b e s Yes
b e t No
が与えられた時に、classification learningにより、上のようなdecision treeを作ることを考える。

用語

training set: 学習のための教師例
test data: できたdecision treeをチェックするためのデータ
peeking: test dataを学習のために使うこと（反則！）「学習してできたdecision treeが複数あり、test dataを適用して最も結果のよかったdecision treeを採用する」ということもpeekingである。
noise: 正しくないデータ
positive example: 予測値がYesとなるデータ
negative example: 予測値がNoとなるデータ
error rate: decision treeで計算した予測値が実際の予測値と異なる割合
cross validation(交差検定): 予測値が分かっている学習用のデータの一部を、学習に使わずにとっておき、学習してできたdecision treeをそれに適用して、予測値の一致の程度を計る方法。 k-fold cross validationの場合、データの1/kをテスト用に残しておく。 test dataはランダムに選び、k回試行を行った平均を取る。データを昇順に並べてk個ごとにサンプルして、データの大きさの偏りを避ける方法もある。 (stratified)

アルゴリズム: 以下をdecision treeの根から適用する。

最も効果的にYesの集合とNoの集合を分離する属性を選ぶ。(方法は後ほど)
その属性に関して、Yes/Noの集合を属性値ごとに分け、それぞれに対してこの処理を再帰的に適用する。

例: 上の表を例とする。 Yesの集合は{(a,e,s),(b,e,s)}、Noの集合は{(a,f,s),(b,e,t)}となる。

まず、属性Aを選んだとする。
- A=aについては、Yesの集合は{(a,e,s)}、Noの集合は{(a,f,s)}となる。
  - 次に、属性Bを選ぶと、 B=eでYesの集合は{(a,e,s)}、Noの集合は{}, B=fでYesの集合は{}、Noの集合は{(a,f,s)}となって、Yes/Noの集合の分離に成功する。
  - 次に、属性Cを選ぶと、 C=sしかなく、Yesの集合は{(a,e,s)}、Noの集合は{(a,f,s)}となり分離できない。
- A=bについては、Yesの集合は{(b,e,s)}、Noの集合は{(b,e,t)}となる。
  - 次に、属性Cを選ぶとC=sでYesの集合は{(b,e,s)}、Noの集合は{}, C=tでYesの集合は{}、Noの集合は{(b,e,t)}となって、Yes/Noの集合の分離に成功する。

最も効果的にYes/Noの集合を分離する属性を選ぶ方法

情報量で比較する。
集合中のYesの確率がp, Noの確率がn(=1-p)の時、その情報量(YesかNoを判定するために必要な情報の量)は $I(p,n)=-p\log_2{p}-n\log_2{n}$ である。
集合中のYesの数をP、Noの数をNとすると、 $I({P \over P+N},{N \over P+N})=-{P \over P+N}\log_2{{P \over P+N}}-{N \over P+N}\log_2{{N \over P+N}}$ 。
集合がC₁, C₂, ...のいくつかの集合に分かれたとする。それぞれの集合のYesの数をP₁, P₂, ...、それぞれの集合のNoの数をN₁, N₂, ...、とすると、 C_iの情報量はI(P_i, N_i)となる。
全体の情報量は、 C_iが ${P_i+N_i \over P+N}$ の確率で選ばれるので、その情報量の加重平均となる。集合がC₁, C₂, ...のいくつかの集合に分かれることによる情報量を $I(\{C_1,C_2,...\})$ と表すと、 $I(\{C_1,C_2,...\})=\sum_{i=1} {P_i+N_i \over P+N} I({P_i \over P_i+N_i},{N_i \over P_i+N_i})$ となる。
information gain(情報利得): 指定された属性AでC_iに分離する事で減少した情報量。 Gain(A) $=I({P \over P+N},{N \over P+N})-I(C_i)$ 。

例:

前の例で属性A=aに対するGain(B)を求める。属性Bで分離する前の情報量はI(1/2,1/2) = 1。属性Bで分離した後の情報量は1/2 I(1,0) + 1/2 I(0,1) = 0。従って、Gain(B) = 1。(1ビットなので2つが完全に分離できる。)

前の例で属性A=aに対するGain(C)を求める。属性Cで分離する前の情報量はI(1/2,1/2) = 1。属性Cで分離した後の情報量は2/2 I(1/2,1/2) + 0/2 I(0,0) = 1。従って、Gain(C) = 0。(0ビットなので全く分離できない。)

最初に属性Aで分離してない時のGain(A)を求める。分離してないときの情報量はI(2/4,2/4) = 1。属性Aで分離した時の情報量は2/4 I(1/2,1/2) + 2/4 I(1/2,1/2) = 1。 Gain(A) = 0。

最初に属性Aで分離してない時のGain(B)を求める。分離してないときの情報量はI(2/4,2/4) = 1。属性Bで分離した時の情報量は3/4 I(2/3,1/3) + 1/4 I(0/1,1/1) = 0.69。 Gain(B) = 0.31。従って、実は、最初に属性Bで分離した方が効率がよい。

3つ以上の値をもつ属性をmultivalued(多値)という。例えば、晴/曇/雨のどれかを値に持つ属性がそうである。多値の属性に対して、２つの値だけを持つ属性をbinary(二値)という。例えば、Yes/Noのどちらかを値に持つ属性がそうである。

多値の属性の値を使って集合を分解すると、細かく分かれるのでinformation gainが大きくなる傾向にある。 4つの集合に分けるのは、 2つの集合に分けるのを2回繰りかえすことに相当するので、 2倍のinformation gainがあって同等となる。そこで、この分を割り引いた量としてgain ratioを考える。

split information: SplitInfo( $\{C_1,C_2,...\}$ ) = $\sum_i-{|C_i| \over |C|} \log_2 {|C_i| \over |C|}$
例: 同じ大きさの2つのC_iに分かれる場合の SplitInfo( $\{C_1,C_2,...\}$ ) = $\sum_{i=1}^2-{1 \over 2} \log_2 {1 \over 2} = 1$
同じ大きさの4つのC_iに分かれる場合の SplitInfo( $\{C_1,C_2,...\}$ ) = $\sum_{i=1}^4-{1 \over 4} \log_2 {1 \over 4} = 2$
gain ratio(利得比): Gain(A)/SplitInfo( $\{C_1,C_2,...\}$ )

属性値が連続値の場合

split point: それより大きな値の集合とそれ以下の集合に分ける区切りの値

属性Aでsplit pointがpの時、与えられた集合を、 C₁ = { 属性Aの値pを超えている。}、C₂ = { 属性Aの値がp以下である。} に分ける。このGain(C_i)が最大になるようなsplit pointを求める。

属性値95, 90, 85に対して予測値がYes、70、65に対して予測値がNoの場合は、 85と70の間のどこかをsplit pointとするとinformaiton gainが最大となる。 Yesの場合の最小の85とNoの場合の最大の70の平均の77.5か、それ以下で実際のデータに含まれる値を使う。

複数のsplit pointで分離することも考えられる。例えば、属性値95, 90, 85に対して予測値がYes、 70、65に対して予測値がNo、 40, 35に対して予測値がYes の場合は、85と70の間のどこかと、65と40の間のどこかをsplit pointにすると分離できる。

最適なsplit pointを求めるには、 s個の属性値があれば、s-1通りのsplit pointを試す必要があり、計算が大変である。複数のsplit pointを求めるのは更に大変である。

枝狩り

overfit: 学習のためのデータに過剰にフィットし、汎化能力が損なわれること。 (学習のためのデータに対するerror rateは0%だが、他のデータに対するerror rateが90%になってしまったりすること)
decision tree pruning: overfitを避けるためにdecision treeの枝狩りをすること。
postpruning: 枝を作ってしまってから、不要な枝を削るやりかた

属性の選択/枝狩りの基準

$\chi^2$ pruning: それまでの属性と独立かどうかを検定し、独立でなければ使わない。上の例のようにYesの数をP、Noの数をN、その属性を使って分離した結果の各C_iにおけるYesの数をP_i、Noの数をN_i とする。元のYes/Noと分布が同じ場合は、Yes/Noの数は比例配分となるので、 C_iで期待されるYesの数 $\hat{P}_i = P {{P_i + N_i} \over {P+N}}$ 、 Noの数 $\hat{N}_i = N {{P_i + N_i} \over {P+N}}$ となる。実際の値はランダムなのでこの期待される値からのずれる。 $\hat{P}_i$ が $P_i$ になる確率が高ければこの属性はそれまでの属性と独立ではないので使わない。その確率が低ければ、単なるランダムネスによるズレではないので、使うことにする。 $\sum({(\hat{P}_i-P_i)^2\over{\hat{P}_i}}+{(\hat{N}_i-N_i)^2\over{\hat{N}_i}})$ は $\chi^2$ 分布になるので、与えられたズレがどの程度の確率で起るかが計算できるので、例えば、5%以下でしか起らないズレなら、独立と考えて採用する、というようなことができる。
MDL原理に基づくアルゴリズム: decision treeを表現するために必要なビット数と errorのデータを例外として表現するために必要なビット数を足したものを最小化する
cost complexity algorithm: decision treeの葉の数(木の大きさ)と error rateの関数を定め、それを最小化する。

ツール: WEKAを使う。(WEKAの準備)

WEKAのGUIを起動
→ Explore
→ Open file
→ weather.arff(湿度等が数値のままのデータ) 
→ Classify 
→ Choose 
→ trees 
→ J48 
→ Start [ 実行結果が表示される ]
→ 左下の「Result list (right-click for options)」の「時刻 - trees.J48」を右クリック
→ Visualize treeを選択 [ decision treeが表示される ]

コマンドライン「-t ファイル名」で学習に使うデータファイルを指定する。
java weka.classifiers.trees.J48 -t data/weather.arff
GUIでは、-C 0.25と-M 2のオプションが指定されている。オプションの意味を知るには、資料を参照するか、以下のように実行して表示されるものを見る。
java weka.classifiers.trees.J48
「-d ファイル名」で作成したdecision treeを保存することができる。 (以下のwork.modelには書き込まれるので、大事なファイルを指定しないように注意)
java weka.classifiers.trees.J48 -C 0.25 -M 2 -t data/weather.arff -d data/weather.model
「-l ファイル名」でdecision treeを読み込む事ができる。「-T ファイル名」でdecision treeをテストファイルに適用することができる。 (以下のweather2.arffは適当に自作しておく)
java weka.classifiers.trees.J48 -l data/weather.model -T data/weather2.arff
「-p 列番号」を指定すると、その列番号の値を推測値として推定しようとする。
java weka.classifiers.trees.J48 -p 5 -l data/weather.model -T data/weather2.arff

以下から選んでレポートを作成し、CFIVEから提出せよ。 (昼間は混雑してつながらないことがある。どうしても提出できない場合はメールで送信せよ。) 5月14日までに提出すること。

Q1: (アルゴリズム) decision treeのアルゴリズムを更に調べてみる。

Q2: (システムの動作) WEKAの実行結果を調べ、正しいかどうかを確認せよ。

Q3: (ツール) trivialでないデータを用意し、WEKAでdecision treeを生成してその結果を吟味せよ。

yamaguch@mail.ecc.u-tokyo.ac.jp
Copyright 2008 Kazunori Yamaguchi 山口和紀@東京大学総合文化研究科

decision tree

yamaguch@mail.ecc.u-tokyo.ac.jp Copyright 2008 Kazunori Yamaguchi 山口和紀@東京大学総合文化研究科

yamaguch@mail.ecc.u-tokyo.ac.jp
Copyright 2008 Kazunori Yamaguchi 山口和紀@東京大学総合文化研究科