東京工科大学大学院 バイオニクス・情報メディア学専攻科 担当： 亀田 弘之 先進的データ分析法2015 東京工科大学大学院 バイオニクス・情報メディア学専攻科 担当：　亀田　弘之

Decision Tree for PlayTennis Outlook Sunny Rain Overcast Humidity Wind Yes High Normal Strong Weak No Yes No Yes

Training Examples Day Outlook 天候 Temperature 温度 Humidity 湿度 Wind 風 Play Tennis D1 D2 D3 D4 D5 D6 D7 D8 D9 D10 D11 D12 D13 D14 Sunny Overcast Rain Hot Mild Cool High Normal Weak Strong No Yes

Top-down Induction of Decision Tree Main loop: A ← the best decision attribute for next node Assign A as decision attribute for node For each value of A, create new descendant of node Sort training examples to leaf nodes If training examples perfectly classified, then HALT, else iterate over new leaf nodes.

Which attribute is the best? [29+, 35-] A1=? A2=? [29+, 35-] F T F T [21+, 5-] [8+, 30-] [18+, 33-] [11+, 2-]

Entropy S is a sample of training examples p+ is the proportion of positive examples in S p- is the proportion of negative examples in S Entropy measures the impurity of S

Entropy（エントロピー）

Interpretation of Entropy Entropy(S)とは…２つのグループ（各生起確率がp+とp-）を符号化するのに必要なビット数（情報量） その理由は… P+ P-

Information Theory（情報理論） 生起確率pのメッセージに対する最適符号長符号(optimal length code)は、　　　　　　で与えられる。 したがって、それぞれ確率p+とp-で生起する２つの組に対する平均符号長は、 　　で与えられる。これはEntropyの公式そのものである。

Entropyの本当の定義 無記憶情報源Sから、シンボルs1, s2, s3, …, snがそれぞれp1, p2, p3, … ,pn の生起確率で出現するとき、この無記憶情報源Sのエントロピーは以下の式で定義される。

Information Gain(情報利得) Gain(S,A)：　「もともと（S)のエントロピー」と「Aに着目する分類後のエントロピー」の差。 これを情報利得と呼ぶ。 (注)A: attribute(属性)

Which attribute is the best? [29+, 35-] A1=? A2=? [29+, 35-] F T F T [21+, 5-] [8+, 30-] [18+, 33-] [11+, 2-]

Which is the best? - Selecting the next attribute - [9+, 5-], E=0.940 Humidity Wind strong high normal weak [3+, 4-], E=0.985 [6+, 1-], E=0.592 [6+, 2-], E=0.811 [3+, 3-], E=1.00 Gain(S,Humidity)=0.151 Gain(S,Wind)=0.048

Training Examples Day Outlook 天候 Temperature 温度 Humidity 湿度 Wind 風 Play Tennis D1 D2 D3 D4 D5 D6 D7 D8 D9 D10 D11 D12 D13 D14 Sunny Overcast Rain Hot Mild Cool High Normal Weak Strong No Yes

分類前のエントロピー ・Yes 9 S[9+, 5-] ・No 5

Outlookに着目する場合 Sunny [2+, 3-] Overcast [4+, 0-] Rain [3+, 2-]

Temperatureに着目する場合 Hot [2+, 2-] Mild [4+, 2-] Cool [3+, 1-]

Humidityに着目する場合 High [3+, 4-] Normal [6+, 1-]

Windに着目する場合 Weak [6+, 2-] Strong [3+, 3-]

情報利得を計算すると… 自分で計算してみてください。 どの場合の情報利得が一番大きいですか？

Decision Tree for PlayTennis Outlook Sunny Rain Overcast Humidity Wind Yes High Normal Strong Weak No Yes No Yes

決定木まとめ 決定木は分類器 決定木が例から学習出来る 過学習(overfiting)回避の工夫が必要 ＝＞ 枝刈り(pruning) 決定木学習は命題論理の命題学習に相当 ＝＞述語論理への拡張が必要 ＝＞帰納的論理プログラミング (ILP; Inductive Logic Programming)