決定木-II 学習目標 １．○与えられた事例集合から，指定された属性選択基準に基づいて決定木を生成 できる 利得 利得比

Presentation on theme: "決定木-II 学習目標 １．○与えられた事例集合から，指定された属性選択基準に基づいて決定木を生成 できる 利得 利得比"— Presentation transcript:

1 決定木-II 学習目標 １．○与えられた事例集合から，指定された属性選択基準に基づいて決定木を生成 できる 利得 利得比
１．○与えられた事例集合から，指定された属性選択基準に基づいて決定木を生成 できる 利得 利得比 ２．△事例数に応じた決定木の検証法を 設定できる 事例が十分 事例が不十分 ３．△枝刈を適切に行える

2 決定木 属性とクラスの対からなる事例集合 身長Ｈ， 収入Ｌ， 学歴Ｈの場合は？ 身長 収入 学歴 クラス L M H + -

3 決定木 属性とクラスの対からなる事例集合 ＩＤ３で生成された決定木 身長Ｈ， 収入Ｈ， 学歴Ｌの場合は？ なぜ「収入」→「学歴」の順？
赤（楕円）ノードは判別ノード 最も上の判別ノードをルートノード 青ノードはクラスノード なぜ「収入」→「学歴」の順？ 身長 収入 学歴 クラス L M H + - L 学歴 H M L,M,H:+ L,M,M:- H,M,M:- 収入 H,H,H:+ H,H,M:+ H,L,L:- H,L,H:- L,L,H:-

4 属性選択基準 利得 (Information Gain) 利得比 (Gain Ratio) 該当（現時点で残った）事例集合のエントロピー －
　 該当（現時点で残った）事例集合のエントロピー　 － 候補属性で分岐した場合のエントロピーの期待値 利得比 (Gain Ratio) 利得/候補属性で分岐した場合の分割エントロピー 補足 　　エントロピー　→　クラスに関するエントロピー

5 判別ノード１ 身長 収入 学歴 エントロピーの期待値 = 0.95 bit エントロピーの期待値 = 0.34 bit
最も低い （予想つきやすい） ので選択

6 エントロピー(情報量の期待値) n個の事象がそれぞれ確率p1, p2 ,…, pnで　発生するとき、この事象の集合の不確定度　を示す

7 収入のときのエントロピーの平均 = 0.344 bit 収入 L H M H,L,M:- H,L,H:- L,L,H:- H,H,H:+
H,H,M:+ L,M,H:+ L,M,M:- H,M,M:- エントロピー = 0 bit エントロピー = 0 bit エントロピー = -1/3 log2 1/3 - 2/3 log2 2/3 = bit エントロピーの 平均 ＝0x3/8 + 0x2/ x3/8 =0.34 bit

8 判別ノード２は？ 残りのデータに対して 身長のエントロピーの平均＝0.666 bit 学歴のエントロピーの平均＝0 bit 収入 L H M
H,L,M:- H,L,H:- L,L,H:- H,H,H:+ H,H,M:+ ？ L,M,H:+ L,M,M:- H,M,M:- 残りのデータに対して 身長のエントロピーの平均＝0.666 bit 学歴のエントロピーの平均＝0 bit

9 決定木生成アルゴリズム STEP1: 該当事例集合Cのすべての事例が同一　クラスに属するなら，そのクラスノードをつくり，停止する．それ以外なら，属性選択基準により一つの　属性A*を選んで判別ノードをつくる． STEP2: 属性A*の属性値（a1, a2,…, an ）によりCをC1, C2,…, Cnにわけてノードをつくり，属性値の枝を張る． STEP3: それぞれのノードCi(1≦i≦n ) に対して　　このアルゴリズムを再起的に適用する．

10 決定木の例 事例集合 収入 L H M H,L,M:- H,L,H:- H,H,H:+ H,H,M:+ L,L,H:- 学歴 L,M,M:-
身長 収入 学歴 クラス L M H + - L 学歴 H M L,M,H:+ L,M,M:- H,M,M:- 収入 H,H,H:+ H,H,M:+ H,L,M:- H,L,H:- L,L,H:-

11 属性選択基準（再登場） 利得 (Information Gain) 利得比 (Gain Ratio)
　　該当（現時点で残った）事例集合のエントロピー　 － 候補属性で分岐した場合のエントロピーの期待値 利得比 (Gain Ratio) 利得/候補属性で分岐した場合の分割エントロピー

12 利得 H(C) － H(C|A) 利得が最も高かい属性A = A*を選択 H(C)は該当事例集合Cのエントロピー m: Cのクラスの種類
　　p(i) : Cに含まれているクラスiの事例の確率 H(C|A)はCをｎ種類の属性値を持つAでn分岐した場合の　エントロピーの期待値(Cの条件付きエントロピー) p(ai) :Cにおいて属性Aが値aiをとる確率 　H(C|ai):　Aの値がaiである事例集合(ノードCi)のエントロピー

13 ルートノードの属性を30秒以内で 決めよ！ ID 身長 収入 学歴 クラス 1 L M H + 2 H L L - 3 H L H - 4
ルートノードの属性を30秒以内で　　決めよ！ ID 身長 収入 学歴 クラス 1 L M H + 2 H L L - 3 H L H - 4 H H H + 5 L L H - 6 H H M + 7 L M M - 8 H M M -

14 利得比 H(C) － H(C|A) split(C, A) 利得比が最も高かい属性A = A*を選択
split(C, A)はCをｎ種類の属性値を持つ候補Aで　　n分岐した場合の「分割エントロピー」 p(ai) :Cにおいて属性Aが値aiをとる確率

15 次回 決定木の検証法 枝刈 面白い？論文紹介 決定木に関する質疑応答