Document

先進的データ分析法2015
東京工科大学大学院
バイオニクス・情報メディア学専攻科
担当：亀田弘之
Decision Tree for PlayTennis
Outlook
Sunny
Rain
Overcast
Humidity
High
No
Wind
Yes
Normal
Yes
Strong
No
Weak
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
Sunny
Overcast
Rain
Rain
Rain
Overcast
Sunny
Sunny
Rain
Sunny
Overcast
Overcast
Rain
Hot
Hot
Hot
Mild
Cool
Cool
Cool
Mild
Cool
Mild
Mild
Mild
Hot
Mild
High
High
High
High
Normal
Normal
Normal
High
Normal
Normal
Normal
High
Normal
High
Weak
Strong
Weak
Weak
Weak
Strong
Strong
Weak
Weak
Weak
Strong
Strong
Weak
Strong
No
No
Yes
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
Yes
No
Top-down Induction of
Decision Tree
Main loop:
1. A ← the best decision attribute for next node
2. Assign A as decision attribute for node
3. For each value of A, create new descendant
of node
4. Sort training examples to leaf nodes
5. If training examples perfectly classified, then
HALT, else iterate over new leaf nodes.
Which attribute is the best?
[29+, 35-]
T
[21+, 5-]
A1=?
F
[8+, 30-]
[29+, 35-]
T
[18+, 33-]
A2=?
F
[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( S )   p log 2 p  p log 2 p
(0  p , p  1, p  p  1)
Entropy（エントロピー）
1
0.9
0.8
0.7
0.6
0.5
Entropy
0.4
0.3
0.2
0.1
0
0
0.5
1
Interpretation of Entropy
• Entropy(S)とは…２つのグループ（各生起確
率がp+とp-）を符号化するのに必要なビット数
（情報量）
• その理由は…
P+
P-
Information Theory（情報理論）
• 生起確率pのメッセージに対する最適符号長符号
(optimal length code)は、  log 2 p で与えられる。
• したがって、それぞれ確率p+とp-で生起する２つの組
に対する平均符号長は、
p ( log 2 p )  p ( log 2 p )
で与えられる。これはEntropyの公式そのものである。
Entropyの本当の定義
• 無記憶情報源Sから、シンボルs1, s2, s3, …, snがそ
れぞれp1, p2, p3, … ,pn の生起確率で出現するとき、
この無記憶情報源Sのエントロピーは以下の式で定
義される。
n
Entropy( S )   pk log 2 pk
k 1
0  pk　 1　（ k  1,2,3,..., n）
p1  p2  p3  ...  pn  1
Information Gain(情報利得)
• Gain(S,A)：「もともと（S)のエントロピー」と「Aに着目
する分類後のエントロピー」の差。
これを情報利得と呼ぶ。
| Si |
Gain( S , A)  Entropy( S )  
Entropy( Si )
iValues( A ) | S |
(注)A: attribute(属性)
Which attribute is the best?
[29+, 35-]
T
[21+, 5-]
A1=?
F
[8+, 30-]
[29+, 35-]
A2=?
T
[18+, 33-]
| Si |
Gain( S , A)  Entropy( S )  
Entropy( Si )
iValues( A ) | S |
F
[11+, 2-]
Which is the best?
- Selecting the next attribute -
high
[3+, 4-],
E=0.985
S[9+, 5-],
E=0.940
[9+, 5-],
E=0.940
Humidity
Wind
normal
[6+, 1-],
E=0.592
Gain(S,Humidity)=0.151
weak
[6+, 2-],
E=0.811
Gain(S,Wind)=0.048
strong
[3+, 3-],
E=1.00
Training Examples
Day
Outlook
天候
Temperature
温度
Humidity
湿度
Wind
風
Play
Tennis
D1
D2
D3
D4
D5
D6
D7
D8
D9
D10
D11
D12
D13
D14
Sunny
Sunny
Overcast
Rain
Rain
Rain
Overcast
Sunny
Sunny
Rain
Sunny
Overcast
Overcast
Rain
Hot
Hot
Hot
Mild
Cool
Cool
Cool
Mild
Cool
Mild
Mild
Mild
Hot
Mild
High
High
High
High
Normal
Normal
Normal
High
Normal
Normal
Normal
High
Normal
High
Weak
Strong
Weak
Weak
Weak
Strong
Strong
Weak
Weak
Weak
Strong
Strong
Weak
Strong
No
No
Yes
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
Yes
No
分類前のエントロピー
・Yes
・No
9
5
S[9+, 5-]
9
9
5
5
E ( S )   log 2 ( )  log 2 ( )
14
14 14
14
 0.94
Outlookに着目する場合
• Sunny
• Overcast
• Rain
[2+, 3-]
[4+, 0-]
[3+, 2-]
5
4
5
E (Outlook )  E ( Sunny )  E (Overcast )  E ( Rain )  0.767
14
14
14
2
2 3
3
E ( Sunny )   log 2 ( )  log 2 ( )  0.97
5
5 5
5
4
4 0
0
E (Overcast )   log 2 ( )  log 2 ( )  0.00
4
4 4
4
3
3 2
2
E ( Rain )   log 2 ( )  log 2 ( )  0.97
5
5 5
5
Temperatureに着目する場合
• Hot
• Mild
• Cool
[2+, 2-]
[4+, 2-]
[3+, 1-]
4
6
4
E (Temp)  E ( Sunny )  E (Overcast )  E ( Rain )  0.911
14
14
14
2
2 2
2
E ( Hot )   log 2 ( )  log 2 ( )  1.00
4
4 4
4
4
4 2
2
E ( Mild )   log 2 ( )  log 2 ( )  0.918
6
6 6
6
1
1 3
3
E (Cool )   log 2 ( )  log 2 ( )  0.811
4
4 4
4
Humidityに着目する場合
• High
• Normal
[3+, 4-]
[6+, 1-]
7
7
E ( Humidity )  E ( High )  E ( Normal )  0.789
14
14
3
3 4
4
E ( High )   log 2 ( )  log 2 ( )  0.985
7
7 7
7
6
6 1
1
E ( Normal )   log 2 ( )  log 2 ( )  0.592
7
7 7
7
Windに着目する場合
• Weak
• Strong
[6+, 2-]
[3+, 3-]
8
6
E (Wind )  E (Weak )  E ( Strong )  0.892
14
14
6
6 2
2
E (Weak )   log 2 ( )  log 2 ( )  0.811
8
8 8
8
3
3 3
3
E ( Strong )   log 2 ( )  log 2 ( )  1.00
6
6 6
6
情報利得を計算すると…
Gain( S , Outlook )  E ( S )  E (Outlook ) 
Gain( S , Humidity )  E ( S )  E ( Humidity ) 
Gain( S , Wind )  E ( S )  E (Wind ) 
Gain( S , Temperature)  E ( S )  E (Temperature) 
自分で計算してみてください。
どの場合の情報利得が一番大きいですか？
Decision Tree for PlayTennis
Outlook
Sunny
Rain
Overcast
Humidity
High
No
Wind
Yes
Normal
Yes
Strong
No
Weak
Yes
決定木まとめ
• 決定木は分類器
• 決定木が例から学習出来る
• 過学習(overfiting)回避の工夫が必要
＝＞枝刈り(pruning)
• 決定木学習は命題論理の命題学習に相当
＝＞述語論理への拡張が必要
＝＞帰納的論理プログラミング
(ILP; Inductive Logic Programming)

Download Report