人工知能特論 ７．決定木の学習 北陸先端科学技術大学院大学 鶴岡 慶雅
今日の講義内容 決定木とは？ 決定木の作り方 過学習 講義資料 エントロピー 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 Humidity Wind Sunny Overcast Rain Yes High Normal Strong Weak No Yes No Yes
決定木による分類の例 事例 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
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
決定木に適した問題 離散的な属性値 ターゲットも離散的 Disjunctive な記述が必要とされる 学習データに誤りが存在するかもしれない 学習データの属性値に欠損があるかもしれない
学習データ例 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
どの属性で分割する？ 最終的には小さな決定木にしたい 分割した結果、学習データが、より整理されたデータになるような属性で分割 学習データの「乱雑さ」をエントロピーで定量化
エントロピー クラスが２つの場合 一般には
Information Gain ある属性に着目して事例の集合を分割したときにどれだけエントロピーを減らせるか
例
Information Gain の計算例 Humidity Wind High Normal Weak Strong
どの属性で分割する？ 属性ごとに information gain を計算してみると
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 ? （練習） ?
過学習（Overfitting） 機械学習の本来の目的 過学習 未知の入力を正しく分類すること 学習事例を正しく分類することではない（！） 学習事例は精度よく分類できるが、学習データに存在しない未知の例をうまく処理できない 特徴空間の次元をやみくもに大きくするのは危険
Reduced Error Pruning 枝刈り（Pruning）を行って過学習を防ぐ どのノードを刈る？ 分類精度が悪化しないノードを刈る Validation set を利用して分類精度を推定 Greedy にノードを刈っていき、推定精度が悪化する直前で枝刈りを止める
Validation (development) set 学習データの一部を性能評価用にまわす 学習データが少なくなってしまう Training set Training set Validation set Test set Test set