2005年度情報理論ガイダンス

決定木-II
• 学習目標
1.○与えられた事例集合から,指定された属性選択基準
に基づいて決定木を生成できる
利得
利得比
2.△事例数に応じた決定木の検証法を設定できる
事例が十分
事例が不十分
3.△枝刈を適切に行える
決定木
• 属性とクラスの対からなる事例集合
身長
収入
学歴
クラス
L
M
H
+
H
L
L
-
H
L
H
-
H
H
H
+
L
L
H
-
H
H
M
+
L
M
M
-
H
M
M
-
• 身長H,
• 収入L,
• 学歴Hの場合は?
決定木
• 属性とクラスの対からなる事例集合
• ID3で生成された決定木
身長
収入
学歴
クラス
L
M
H
+
H
L
L
-
H
L
H
-
H
H
H
+
L
L
H
-
H
H
M
+
L
M
M
-
H
M
M
-
•
•
•
赤(楕円)ノードは判別ノード
最も上の判別ノードをルートノード
青ノードはクラスノード
– なぜ「収入」→「学歴」の順?
L
H,L,M:-
H,L,H:• 身長H,
L,L,H:• 収入H,
• 学歴Lの場合は?
収入
H
M
H,H,H:+
学歴
H,H,M:+
M
L,M,M:H,M,M:-
H
L,M,H:+
属性選択基準
• 利得 (Information Gain)
該当(現時点で残った)事例集合のエントロピー
-
候補属性で分岐した場合のエントロピーの期待値
• 利得比 (Gain Ratio)
利得/候補属性で分岐した場合の分割エントロピー
判別ノード1
• 身長
エントロピーの期待値 = 0.95 bit
• 収入
エントロピーの期待値 = 0.34 bit
• 学歴
エントロピーの期待値 = 0.84 bit
最も低い
(予想つきやすい)
ので選択
エントロピー(情報量の期待値)
じゃんけんしよう!
– n個の事象がそれぞれ確率p1, p2 ,…, pnで
発生するとき、この事象の集合の不確定度
を示す

p log p
i
2
i
収入のときのエントロピーの平均
= 0.344 bit
L
H,L,M:H,L,H:L,L,H:-
収入
H
M
H,H,H:+
L,M,H:+
H,H,M:+
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
判別ノード2は?
L
H,L,M:H,L,H:-
収入
H
M
H,H,H:+
H,H,M:+
L,L,H:-
?
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
M
H
+
H
L
L
-
H
L
H
-
H
H
H
+
L
L
H
-
H
H
M
+
L
M
M
-
H
M
M
-
L
H,L,M:H,L,H:L,L,H:-
収入
H
M
H,H,H:+
学歴
H,H,M:+
M
L,M,M:-
H,M,M:-
H
L,M,H
属性選択基準(再登場)
• 利得 (Information Gain)
該当(現時点で残った)事例集合のエントロピー
-
候補属性で分岐した場合のエントロピーの期待値
• 利得比 (Gain Ratio)
利得/候補属性で分岐した場合の分割エントロピー
利得
H(C) - H(C, A)
• 利得が最も高かい属性A = A*を選択
• H(C)は該当事例集合Cのエントロピー
  p(i) log p(i)
m
2
i 1
m: Cのクラスの種類
p(i) : Cに含まれているクラスiの事例の確率
• H(C, A)はCをn種類の属性値を持つAでn分岐した場合の
エントロピーの期待値
n

i 1
p(a ) H (C )
i
i
p(ai) :Cにおいて属性Aが値aiをとる確率
ルートノードの属性を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をn種類の属性値を持つ候補Aで
n分岐した場合の「分割エントロピー」
  p(a ) log p(a )
n
2
i 1
i
i
p(ai) :Cにおいて属性Aが値aiをとる確率
次回
•
•
•
•
•
開始までに課題提出
決定木の検証法
枝刈
面白い?論文紹介
決定木に関する質疑応答