人工知能特論 ７．決定木の学習 北陸先端科学技術大学院大学　鶴岡 慶雅.

Presentation on theme: "人工知能特論 ７．決定木の学習 北陸先端科学技術大学院大学　鶴岡 慶雅."— Presentation transcript:

1 人工知能特論 ７．決定木の学習 北陸先端科学技術大学院大学　鶴岡 慶雅

2 今日の講義内容 決定木とは？ 決定木の作り方 過学習 講義資料 エントロピー Information Gain 汎化性能 枝刈り

3 決定木の学習 Chapter 3 of Mitchell, T., Machine Learning (1997)
決定木（Decision Trees） Disjunction of conjunctions 実用に使われる分類器 病気の診断 クレジットリスクの評価 特長 学習結果が人間にとって理解しやすい ルールの集合

4 決定木の例 Concept: PlayTennis Outlook Humidity Wind Sunny Overcast Rain
Yes High Normal Strong Weak No Yes No Yes

5 決定木による分類の例 事例 Outlook Humidity Wind Sunny Overcast Rain Yes High
<Outlook = Sunny, Temperature = Hot, Humidity = High, Wind = Strong> Outlook Sunny Overcast Rain Humidity Wind Yes High Normal Strong Weak No Yes No Yes

6 Disjunction of conjunctions
(Outlook = Sunny ^ Humidity = Normal) v (Outlook = Overcast) v (Outlook = Rain ^ Wind = Weak) Outlook Sunny Overcast Rain Humidity Wind Yes High Normal Strong Weak No Yes No Yes

7 決定木に適した問題 離散的な属性値 ターゲットも離散的 Disjunctive な記述が必要とされる 学習データに誤りが存在するかもしれない
学習データの属性値に欠損があるかもしれない

8 学習データ例 Day Outlook Temperature Humidity Wind PlayTennis D1 Sunny Hot
High Weak No D2 Strong D3 Overcast Yes D4 Rain Mild D5 Cool Normal D6 D7 D8 D9 D10 D11 D12 D13 D14

9 どの属性で分割する？ 最終的には小さな決定木にしたい 分割した結果、学習データが、より整理されたデータになるような属性で分割
学習データの「乱雑さ」をエントロピーで定量化

10 エントロピー クラスが２つの場合 一般には

11 Information Gain ある属性に着目して事例の集合を分割したときにどれだけエントロピーを減らせるか

12 例

13 Information Gain の計算例 Humidity Wind High Normal Weak Strong

14 どの属性で分割する？ 属性ごとに information gain を計算してみると

15 Outlook 属性による枝分かれ ? （練習） ? Outlook Yes {D1,D2,…,D14} [9+,5-] Sunny
Overcast Rain {D1,D2,D8,D9,D11} [2+,3-] {D3,D7,D12,D13} [4+,0-] {D4,D5,D6,D10,D14} [3+,2-] Yes ? （練習） ?

16 過学習（Overfitting） 機械学習の本来の目的 過学習 未知の入力を正しく分類すること 学習事例を正しく分類することではない（！）
学習事例は精度よく分類できるが、学習データに存在しない未知の例をうまく処理できない 特徴空間の次元をやみくもに大きくするのは危険

17 Reduced Error Pruning 枝刈り（Pruning）を行って過学習を防ぐ どのノードを刈る？
分類精度が悪化しないノードを刈る Validation set を利用して分類精度を推定 Greedy にノードを刈っていき、推定精度が悪化する直前で枝刈りを止める

18 Validation (development) set
学習データの一部を性能評価用にまわす 学習データが少なくなってしまう Training set Training set Validation set Test set Test set