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

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

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

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

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

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

収入のときのエントロピーの平均 = 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 = 0.917 bit エントロピーの 平均 ＝0x3/8 + 0x2/8 + 0.917x3/8 =0.34 bit

判別ノード２は？ 残りのデータに対して 身長のエントロピーの平均＝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

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

決定木の例 事例集合 収入 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:-

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

利得 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)のエントロピー

ルートノードの属性を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 -

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

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