人工知能特論 6．機械学習概論とバージョン空間法

人工知能特論
７．決定木の学習
北陸先端科学技術大学院大学鶴岡慶雅
今日の講義内容
• 決定木とは？
• 決定木の作り方
• エントロピー
• Information Gain
• 過学習
• 汎化性能
• 枝刈り
• 講義資料
• http://www.jaist.ac.jp/~tsuruoka/lectures/
決定木の学習
Chapter 3 of Mitchell, T., Machine Learning (1997)
• 決定木（Decision Trees）
– Disjunction of conjunctions
– 実用に使われる分類器
• 病気の診断
• クレジットリスクの評価
• 特長
– 学習結果が人間にとって理解しやすい
– ルールの集合
決定木の例
• Concept: PlayTennis
Outlook
Sunny
Humidity
High
No
Normal
Yes
Overcast
Rain
Wind
Yes
Strong Weak
No
Yes
決定木による分類の例
• 事例
<Outlook = Sunny, Temperature = Hot, Humidity = High, Wind = Strong>
Outlook
Sunny
Humidity
High
No
Normal
Yes
Overcast
Rain
Wind
Yes
Strong Weak
No
Yes
Disjunction of conjunctions
(Outlook = Sunny ^ Humidity = Normal)
v
(Outlook = Overcast)
v (Outlook = Rain ^ Wind = Weak)
Outlook
Sunny
Humidity
High
No
Normal
Yes
Overcast
Rain
Wind
Yes
Strong Weak
No
Yes
決定木に適した問題
•
•
•
•
離散的な属性値
ターゲットも離散的
Disjunctive な記述が必要とされる
学習データに誤りが存在するかもしれない
• 学習データの属性値に欠損があるかもしれな
い
学習データ例
Day
Outlook
Temperature
Humidity
Wind
PlayTennis
D1
Sunny
Hot
High
Weak
No
D2
Sunny
Hot
High
Strong
No
D3
Overcast
Hot
High
Weak
Yes
D4
Rain
Mild
High
Weak
Yes
D5
Rain
Cool
Normal
Weak
Yes
D6
Rain
Cool
Normal
Strong
No
D7
Overcast
Cool
Normal
Strong
Yes
D8
Sunny
Mild
High
Weak
No
D9
Sunny
Cool
Normal
Weak
Yes
D10
Rain
Mild
Normal
Weak
Yes
D11
Sunny
Mild
Normal
Strong
Yes
D12
Overcast
Mild
High
Strong
Yes
D13
Overcast
Hot
Normal
Weak
Yes
D14
Rain
Mild
High
Strong
No
どの属性で分割する？
• 最終的には小さな決定木にしたい
• 分割した結果、学習データが、より整理され
たデータになるような属性で分割
• 学習データの「乱雑さ」をエントロピーで定量
化
エントロピー
• クラスが２つの場合
EntropyS    p log2 p  p log2 p
Entropy[9,5]  9 / 14 log2 9 / 14  5 / 14 log2 5 / 14
 0.940
• 一般には
c
EntropyS     pi log2 pi
i 1
Information Gain
• ある属性に着目して事例の集合を分割したと
きにどれだけエントロピーを減らせるか
GainS , A  EntropyS  
 
vValues A
Sv
S
EntropySv 
例
ValuesWind   Weak , Strong
S  [9,5]
SWeak  [6,2]
S Strong  [3,3]
GainS , Wind   EntropyS  

vWeak , Strong 
Sv
S
EntropyS v 
8
6
 EntropyS   EntropySWeak   EntropyS Strong 
14
14
8
6
 0.940 0.811 1.00
14
14
 0.048
Information Gain の計算例
S  [9,5]
E  0.940
S  [9,5]
E  0.940
Humidity
Wind
High
S  [3,4]
E  0.985
Normal
S  [6,1]
E  0.592
GainS , Hum idity
7
7
 0.940 0.985 0.592
14
14
 0.151
Weak
S  [6, 2 ]
E  0.811
Strong
S  [3,3]
E  1.00
GainS ,Wind 
8
6
 0.940 0.811 0.592
14
14
 0.048
どの属性で分割する？
• 属性ごとに information gain を計算してみると
GainS , Outlook  0.246
GainS , Hum idity  0.151
GainS ,Wind   0.048
GainS , Tem perature   0.029
Outlook 属性による枝分かれ
{D1,D2,…,D14}
[9+,5-]
Outlook
Sunny
Overcast
Rain
{D1,D2,D8,D9,D11}
[2+,3-]
{D3,D7,D12,D13}
[4+,0-]
{D4,D5,D6,D10,D14}
[3+,2-]
? （練習）
Yes
?
過学習（Overfitting）
• 機械学習の本来の目的
– 未知の入力を正しく分類すること
– 学習事例を正しく分類することではない（！）
• 過学習
– 学習事例は精度よく分類できるが、学習データに
存在しない未知の例をうまく処理できない
– 特徴空間の次元をやみくもに大きくするのは危険
Reduced Error Pruning
• 枝刈り（Pruning）を行って過学習を防ぐ
• どのノードを刈る？
• 分類精度が悪化しないノードを刈る
• Validation set を利用して分類精度を推定
• Greedy にノードを刈っていき、推定精度が悪
化する直前で枝刈りを止める
Validation (development) set
• 学習データの一部を性能評価用にまわす
Training set
Training set
Validation set
Test set
Test set
• 学習データが少なくなってしまう

Download Report