決定木の学習 - 知能ソフトウェア研究室

認知システム論知識と推論（４）
知識を表現し，それを用いて推論する
決定木による知識の獲得
• 学習と帰納推論
• 決定木
• ID3アルゴリズム
• 性能評価と応用
学習の一般的な概念
訓練データ
入力： x1,x2,x3,…
テストデータ
x101,x102,x103,…
エージェント
エージェント
訓練
うまく動く
うまく動かない
仮説
知識
評価
y101,y102,y103,…
出力： y1,y2,y3,…
環境
いろいろな学習技術
関数近似
ニューラルネットワーク
非線形関数 y=f(x;w) の数値パラメータ w の値を調整
強化学習
非線形方程式
状態 sで行動 a をとるときの報酬の推定値Q(s,a)を調整
数
値
の
学
習
決定木の学習
属性値から概念を識別するための木構造を生成
説明に基づく学習
将来の探索を削減するための効率良いルールを生成
帰納論理プログラミング
与えられた入出力関係を満たす帰納パターンを生成
構
造
の
学
習
帰納推論(inductive inference)
多くの学習アルゴリズムは帰納推論の形式をとる．
例 (example)
( xi , f ( xi ))
帰納推論
仮説 (hypothesis)
f を近似する h
ある仮説を他の仮説より優先して選ぶ基準をバイアス(bias)という．
丸暗記学習アルゴリズム
データを一般的に説明する有益な知識を獲得していない
学習（x, y) {
(x,y)をデータベースＤＢに記録する．
}
予測（x) {
if（ＤＢに(x,y)が記録されている）
return y；
else ｛
ＤＢ中のデータから多数決などで y を決める；
return y；
}
}
決定木 (decision tree)
属性とその値の組によって表現されたデータをクラスに分類
決定木
属性
病院へ
行きなさい
Attribute
質問
熱
値
判断
Value
熱＝無
頭痛＝有
無
有
Yes
INPUT
OUTPUT
Yes
頭痛
無
No
有
Yes
決定木の学習
訓練例 (training set)
｛熱＝無，頭痛＝有｝: Yes
｛熱＝無，頭痛＝無｝: No
INPUT
学習アルゴリズム
OUTPUT
熱
有
無
Yes
頭痛
決定木
無
有
No
Yes
学習システム
訓練例 (training set)
｛熱＝無，頭痛＝有｝: Yes
｛熱＝無，頭痛＝無｝: No
INPUT
学習アルゴリズム
OUTPUT
質問
熱＝無
頭痛＝有
判断
熱
INPUT
OUTPUT
有
無
Yes
頭痛
決定木
Yes
無
有
No
Yes
訓練例(training set)
A
B
C
D
E
F
G
H
I
J
性別
男性
女性
年齢
未成年
未成年
薬物
覚醒剤
覚醒剤
犯罪歴
初犯
初犯
実刑
No
No
女性
男性
男性
男性
老人
成年
老人
老人
麻薬
覚醒剤
シンナー
麻薬
初犯
初犯
累犯
初犯
No
Yes
Yes
Yes
女性
男性
男性
成年
未成年
老人
シンナー
シンナー
麻薬
累犯
累犯
累犯
Yes
Yes
Yes
女性
未成年
麻薬
累犯
Yes
負例
正例
複数の決定木
麻薬
シンナー
年齢
年齢
未成年
成年
犯罪歴
性別
女性
累犯
Yes
犯罪歴
老人
未成年
No
薬物
覚醒剤
決定木
１
初犯
決定木
２
Yes
男性
No
Yes
◆どちらも訓練例を正しく分類している．
◆未知の例を正しく分類できるか？
（女性，老人，シンナー，初犯）
◆効率（テストの回数）
（男性，成年，麻薬，初犯）
No
成年
Yes
累犯
初犯
Yes
性別
女性
No
Yes
男性
Yes
【オッカムのかみそり】
最もありそうな仮説は，
すべての観測に無矛盾な仮説の中で，
最も簡潔なものである
計算量的に困難
識別力の高い順に属性をテストする
正：A,C,D,E
負：B,F,G,H
正：A,C,D,E
負：B,F,G,H
A1
1
正：
負：B,H
A2
3
2
正：D,E
負：
正：A,C
負：F,G
識別力が高い
1
3
2
正：A
負：G
正：C
負：H
正：D,E
負：B,F
識別力が低い
情報理論を利用する
平均情報量（エントロピー）
n
n
1
I ( P1, , Pn )   Pi log2    Pi log2 Pi (ビット）
Pi i1
i 1
◆正例が p 個，負例が n 個のときの平均情報量
p
n
p
pn
n
pn
I(
,
)
log 2

log 2
pn pn pn
p
pn
n
識別力＝情報ゲイン
I (7 /10,3/10)  0.881
正：D,E,F,G,H,I,J
負：A,B,C
「薬物」属性
の
識別力
薬物
覚醒剤
正：D
負：A,B
3
10
麻薬
4
10
シンナー
正：F,I,J
負：C
I (1/ 3, 2 / 3)  0.918 I (3/ 4,1/ 4)  0.811
3
10
正：E,G,H
負：
I (1,0)  0
Gain
0.281 bits
Yes
平均　(3/10)  0.918  (4 /10)  0.811  (3/10)  0  0.600
ゲインの最大の属性を木の根とする
属性
ゲイ
ン
性別 0.091
I (7 /10,3/10)  0.881
年齢 0.157
正：D,E,F,G,H,I,J
負：A,B,C
薬物 0.281
犯罪歴
犯罪歴 0.396
5
10
初犯
正：D, F
負：A,B,C
I (2 / 5,3/ 5)  0.971
累犯
5
10
正：E,G,H,I,J
負：
I (1,0)  0
平均 0.5  0.971  0.5  0  0.485
Gain
0.396 bits
Yes
分割された訓練例について再帰
属性ゲイン
正：D, F
負：A,B,C
性別 0.042
年齢 0.571
薬物 0.020
初犯
累犯
年齢
未成年
Yes
正：E,G,H,I,J
負：
老人
成年
正：
負：A,B
属性ゲイン
性別 1.000
犯罪歴
No
正：D
負：
正：F
負：C
Yes
性別
女性
薬物 0.000
正：
負：C
No
男性
正：F
負：
Yes
学習結果の決定木
犯罪歴
初犯
累犯
年齢
Yes
未成年
老人
成年
No
Yes
性別
女性
男性
No
Yes
決められなければ多数決(1)
正：D, F
負：A,B,C
犯罪歴
初犯
累犯
Yes
薬物
覚醒剤
シンナー
麻薬
正：D
負：A,B
正：F
負：C
正：
負：
No
訓練例が空集合の場合
親ノードの多数決
により，２対３で
No
とする
決められなければ多数決(2)
誤り（ノイズ）のあるデータ
性別
年齢
薬物
犯罪歴
犯罪歴
実刑
女性
老人
麻薬
初犯
No
女性
老人
麻薬
初犯
Yes
女性
老人
麻薬
初犯
Yes
女性
老人
麻薬
初犯
Yes
初犯
C
年齢
P
Q
R
老人
性別
女性
属性が残っていなく，
正負の例が混在する場合
多数決
により，３対１でYesとする
薬物
麻薬
Yes
正：P,Q,R
負：C
ＩＤ３アルゴリズム
S: 訓練例の集合
A: 属性の集合
決定木ＩＤ３（S，A，default）｛
default: Yes / No の既定値
if（Sが空集合） return default
else if（Sがすべて正例） return Yes
else if（Sがすべて負例） return No
else if（Aが空集合） return 多数決（S）
else {
bestA ← Aのうちでゲインが最大の属性；
tree ← new 決定木（bestA）；
bestAdomain ← bestA の取りうるすべての値；
for each v in bestAdomain do {
S' ← SのうちbestA=vとなっている全データ；
subtree ← ＩＤ３（S', A－bestA, 多数決（S））；
tree の下に subtree を v の枝で連結する；
}
return tree；
}
ノイズと過剰一致
過学習(overfitting)
細かく分類しすぎて，ノイズまで再
現するような意味のない仮説を生
成することがある．
枝刈り(pruning)
統計的仮説検定で，有意性のない
分類を防ぐ
学習アルゴリズムの性能評価
training set
訓練集合
例の集合
学習アルゴリズム
決定木
検査集合
test set
正答率
学習曲線(learning curve)
100
正答率（％）
80
60
40
20
0
0
20
40
60
訓練例の数
80
100
決定木学習の現実的応用例
• 飛行学習（1992）
– フライトシミュレータでセスナ機の操縦を学習
– ３人の熟練パイロットの３０回の繰り返しから学習
– 性能は先生をしのぐ

Download Report