1 説明 2 課題

1
説明
決定木とは，節点に属性名，枝に属性値，葉にクラスが与えられた木である．与えられたデー
タを分類する際は，木の根から順に節点の属性に対応するデータの属性値を調べ，対応する属
性値の枝を辿る．葉まで達したとき，そのデータを葉のクラスに分類する．
ID3 は，情報量に基づき分類力の高い属性を選択することにより，簡潔な決定木を生成す
ることができる．
• エントロピー (平均情報量) の定義
エントロピーは以下のように定義できる．
∑
Entropy(X) = − x∈X p(x) log p(x)
ただし，X は事象の集合，x は事象，p(x) は事象 x の生起確率である．
以下では簡単のために，事象の代わりに，生起確率を直接記述した式も用いる．
e(p) = −p log2 p − (1 − p) log2 (1 − p)
e(0)=e(1)=0, e(1/4)=e(3/4)=0.8113, e(1/3)=e(2/3)=0.9183, e(1/2)=1
• 情報利得, 獲得情報量 (Information Gain) 事例集合 S をある属性 A で分類したときに獲
得される情報量を information gain といい，G(S, A) と表現する．
Entropy(S) − 集合 S を属性 A で分類後の情報量
∑ |SA=v |
Entropy(SA=v )
= Entropy(S) −
|S|
(1)
= {s|s ∈ S and s の属性 A の値が v}
(3)
G(S, A) =
(2)
v∈A
SA=v
ただし，|S|,|SA=v | は集合 S,SA=v の要素数である．
• 分類属性の選択
G(S, A) が最大となる属性 A を S の分類属性として選択する．なお，G(S, A)/|A| を基
準とする場合もある．ここでは G(S, A) を基準とし，G(S, A) が同じ場合，属性値の数が
少ない属性を用いる．
2
課題
以下の事例集合 D に対して，ID3 アルゴリズムにより，決定木を学習せよ．
• 事例空間 X
–
–
–
–
–
–
事例の表現: < aoutlook , atemp , ahumidity , awind >
予報: Aoutlook = { 晴, 曇, 雨 }
気温: Atemp = { 暖, 適, 冷 }
湿度: Ahumidity = { 高, 並 }
風: Awind = { 強, 弱 }
クラス: C = {Y es, N o}
• 訓練事例集合 D
No
d1
d2
d3
d4
d5
d6
d7
d8
Examples
< 晴, 暖, 高,
< 晴, 暖, 高,
< 曇, 暖, 高,
< 雨, 適, 高,
< 雨, 冷, 並,
< 雨, 冷, 並,
< 曇, 冷, 並,
< 晴, 適, 高,
1
弱
強
弱
弱
弱
強
強
弱
>
>
>
>
>
>
>
>
Yes/No
No
No
Yes
Yes
Yes
No
Yes
No
3
解答
• D における分類前の情報量
分類前の情報量はその集合のエントロピーと等しい．Entropy(D)=e(4/8)=e(1/2)=1
• D における情報利得と分類属性の選択
分類属性
A
予報
気温
湿度
風
分類後の情報量
3/8 Entropy(D予報=晴 ) + 2/8 Entropy(D予報=曇 ) + 3/8 Entropy(D予報=雨 )
= 3/8 e(0/3) + 2/8 e(2/2) +3/8 e(2/3) = 3/8 ∗ 0.9183 = 0.3444
3/8 Entropy(D気温=暖 ) + 2/8 Entropy(D気温=適 ) + 3/8 Entropy(D気温=冷 )
= 3/8 e(1/3) + 2/8 e(1/2) + 3/8 e(2/3) = 6/8 ∗ 0.9183 + 2/8 ∗ 1= 0.9387
3/8 Entropy(D湿度=高 ) + 2/8 Entropy(D湿度=並 )
= 5/8 e(2/5) + 3/8 e(2/3) = 5/8∗0.9709 + 3/8∗0.9183 = 0.9512
3/8 Entropy(D風=強 ) + 5/8 Entropy(D風=弱 )
= 3/8 e(1/3) + 5/8 e(3/5) = 3/8∗0.9183+5/8∗0.9709 = 0.9512
したがって，分類のための属性値としては，予報を選べばよい．
• 予報により D を分類後の集合
(4)
S2
= D予報=晴 = {d1(N o), d2(N o), d8(N o)}
= D予報=曇 = {d3(Y es), d7(Y es)}
S3
= D予報=雨 = {d4(Y es), d5(Y es), d6(N o)}
(6)
S1
(5)
S1 のラベルは全て No，S2 のラベルは全て Yes なので葉ノードになる．
• S3 における分類前の情報量
Entropy(S3 )=e(2/3)=0.9183
• S3 における情報利得と分類属性の選択
分類属性
A
気温
湿度
風
分類後の情報量
1/3 Entropy(S3 気温=適 ) + 2/3 Entropy(S3 気温=冷 )
= 1/3 e(1/1) + 2/3 e(1/2) = 2/3∗1 = 0.6667
1/3 Entropy(S3 湿度=高 ) + 2/3 Entropy(S3 湿度=並 )
= 1/3 e(1/1) + 2/3 e(1/2) = 2/3∗1 = 0.6667
1/3 Entropy(S3 風=強 ) + 2/3 Entropy(S3 風=弱 )
= 1/3 e(0/1) + 2/3 e(2/2) = 0
情報利得
G(S3 , A − { 予報 })
0.2516
0.2516
0.9183
したがって，分類のための属性値としては，風を選べばよい．
• 風により S3 を分類後の集合
S31
S32
= S3 風=強 = {d6(N o)}
= S3 風=弱 = {d4(Y es), d5(Y es)}
(7)
(8)
S31 , S32 はいずれも正事例あるいは負事例のみなので，Yes あるいは No のラベルを付
けて終了．
• 決定木
2
情報利得
G(D, A)
0.6556
0.0613
0.0488
0.0488
ணሗ
ᬕ
d1,d2,d8 No
㞵
᭎
㢼 d4,d5,d6
Yes
d3,d7
3
ᙉ
ᙅ
No
Yes
d6
d4,d5

Download Report