決定木の学習決定木とは？

決定木の学習
対象クラスの決定木
1
決定木とは？
• 対象の属性値とそれが属するクラスの対であるデータから，そ
れぞれデータをクラスに分類する木を決定木（クラス分類の一
般化規則）と呼ぶ
– 中間ノードがテストされる属性（重量，価格など）を表す → 判別ノード
– 枝がその属性値（多い・少ない，高い・低いなど）を表す
– 葉ノードがクラス（＋・ー，A・B・Cなど任意のID）を表す → クラスノード
重量
重い
多い，重い，高い：－
多い，重い，安い：－
少ない，重い，安い：－
軽い
多い，軽い，安い：＋
多い，軽い，普通：＋
普通
価格
普通
少ない，普通，普通：－
多い，普通，普通：－
安い
少ない，普通，安い：＋
2
属性・属性値と決定木の例
laptop PC 購入の条件
インストールソフト
重量
価格
クラス
少ない
普通
安い
＋
多い
重い
高い
－
多い
重い
安い
－
多い
軽い
安い
＋
少ない
重い
安い
－
多い
軽い
普通
＋
少ない
普通
普通
－
多い
普通
普通
－
重量
重い
多い，重い，高い：－
多い，重い，安い：－
少ない，重い，安い：－
軽い
多い，軽い，安い：＋
多い，軽い，普通：＋
普通
価格
安い
普通
少ない，普通，普通：－
多い，普通，普通：－
少ない，普通，安い：＋
3
決定木の応用例
• Akinator [1] (?)
[1] http://jp.akinator.com/
4
ID３による決定木の生成
• 入力
– 属性値と属性の対の集合
• 出力
– 決定木
• 分類効率のよい決定木作り
• 空の決定木から始まって，すべてのデータが正
しく分類できるような決定木が得られるまでノー
ドを付け加えていく
• データを正しく分類する決定木は，複数種類あり
える
– 分類の効率や決定木の一般性を考えて，できるだけ
単純な決定木を生成する
5
ID３による決定木生成アルゴリズム
• Step０
– 根ノードである全てのデータ集合をCとする
• Step１
– 集合C中のすべてのデータが同一クラスに属するなら，そ
のクラスノードを作り停止する．それ以外なら，属性の基
準判断により一つの属性Aを選んで判別ノードを作る
• どの属性をまず選んで分岐を行ったほうが，効率の良いクラス分
類のための決定木が作れるか？
• Step2
– 属性Aの属性値によりCを部分集合C1，C2，…，Cnに分
けてノードを作り，属性値の枝をはる
• Step３
– それぞれのノードCi（１≦i≦n）について，このアルゴリズ
ムを再帰的に適用する（Steｐ１に戻る）
6
属性の選択基準１／４
• ID３では，情報理論的基準を用いて分類におけるテスト
回数をできるだけ少なくする
– ここにおける情報理論の利用法は？
• 決定木は，質問（分岐）による分類によってデータ集合
をよりランダムさの少ない集合に分割していくと考える：
分岐を繰り返すたびに，クラスが絞りこまれていく
→ もちろん，早い段階で（少ない分岐回数で一つに絞り
込みたい）
• ランダムさを測る基準として情報量（エントロピー，単位
はbit）を用いて，もっともランダムさを減少させる質問を
Step１で選択する
7
属性の選択基準２／４
• ＋と－の２つのクラスだけを考え，それぞれの事前確率（各
クラスに属しているデータの割合で近似）をp+，p－とすると，
その情報量の期待値は
M(C) = –p+log2p+ – p－log2p－
※－∑クラス数px(C)logクラス数px(C)
• データ集合Cの決定木の情報量の期待値をM（C）とし，次に
テストすべき属性（子ノード）としてAが選択されたとすると，
属性Aの値ai（1≦i≦n）は互いに排他的なので，属性Aでテ
ストした場合の情報量の期待値は以下となる
– B(C, A) = Σ{（属性Aがaiをとる確率）×M(ai)}
• ランダム性（情報量）を減少させる属性をまず選ぶのが好ま
しい
→ M(C) － B(C,A) （情報利得）を最大にする属性Aを選択
属性A
a1
A1
a2
A2
an
An
8
属性の選択基準３／４
• クラス＋と－のデータ数は３と５なので，p+=3/8 , p－=5/8
• M(C) = －(3/8 log2 3/8) – (5/8 log2 5/8) = 0.954 bit
• 属性「インストールソフト」をAとして選びテストした場合
– 多い：－(2/5 log2 2/5) – (3/5 log2 3/5) = 0.971 bit
– 少ない：－(1/3 log2 1/3) – (2/3 log2 2/3) = 0.919 bit
• 属性「インストールソフト」により得られる情報量の期待値は，
– B(C,インストールソフト) =
(「インストールソフト」が多い確率×M(多い)) +
(「インストールソフト」が少ない確率×M(少ない))
= 5/8 × 0.971 + 3/8 × 0.919 = 0.952 bit
• M(C) – B(C,インストールソフト) = 0.954 – 0.952 = 0.002 bit
インストールソフト
重量
価格
クラス
少ない
普通
安い
＋
少ない
重い
安い
－
多い
重い
高い
－
多い
軽い
普通
＋
多い
重い
安い
－
少ない
普通
普通
－
多い
軽い
安い
＋
多い
普通
普通
－
10
演習１
• 属性「重量」「価格」についても同様に
– M(C) – B(C,重量)
– M(C) – B(C,価格)
を計算せよ（計算の途中経過を示すこと）
11
属性の選択基準４／４
• 評価値が最大の属性「重量」を選ぶ
• 部分集合のクラスが確定すれば葉ノード確定
（Step1）
• クラスが確定していなければアルゴリズムを再
帰的に適用する
重量
重い
多い，重い，高い：－
多い，重い，安い：－
少ない，重い，安い：－
クラス確定
軽い
多い，軽い，安い：＋
多い，軽い，普通：＋
クラス確定
普通
少ない，普通，普通：－
多い，普通，普通：－
少ない，普通，安い：＋
クラス未確定
再帰的に分割
13
決定木生成アルゴリズムの改良
• 紹介したアルゴリズムでは，データはすべて正しく，
誤ったクラス分けはされていない（すなわち，属性値
とクラスの対応付けがすべて正しい）という前提が
ある
→ 多少の間違ったデータを含む，つまりノイズを含
むデータへの対応
• すべての学習データが与えられた時点で決定木が
作成される
→ バッチ的にデータを一度にまとめて与えるのでは
なく，少しずつ与えて徐々に学習
14
決定木生成アルゴリズムの改良例
•
ID3
– John Ross Quinlan, “Introduction of decision trees,” Machine Learning, 1986.
•
C4.5 (ID3からデータ欠損，誤差，などへの対応がなされる)
– John Ross Quinlan, “C4.5: Programs for Machine Learning,” 1993.
• CART
– L. Breiman, J. Friedman, R. Olshen, C. Stone, “Classification and regression trees,” 1984
ID3
C4.5
学習データの属性欠損
欠損学習データの入力不可能
該当データの欠損属性を除い
て木生成
離散値（整数，実数など）
属性
使用不可能
閾値で分岐
属性値のバリエーションに
応じた属性重み
属性重み考慮なし
情報利得を分割情報量で割
る: Σ(1/N)log2(1/N)
過学習への対応
対応なし
サンプルにおいてエラー率を
上昇させる分岐を消す
15
更なる決定木の拡張
• Random Forest
– 木を複数作成し，属性値の多い（入力ベクトルが
多次元），または，外れ値を多く含むサンプルか
らの頑健な学習を実現
• 多数のサンプルからランダムに，学習サンプルを抽出
して，各木を学習
• 多数の属性値からランダムに，木の分岐決定におい
て参照する属性値を選択して，各木を学習
16
Random Forest
(…)
(…)
(…)
(…)
学習サンプル
２クラス識別
＋
＋
ー＋
＋
ー
ー＋
多数決
多クラス識別
２
１
３
１
１
４
多数決
２
２
多クラス識別
１２３４
１２３４
１２３４
１２３４
１２３４
平均値の最大
17
決定木の学習のまとめ
• 対象の属性値とそれが属するクラスの対であ
るデータから，それぞれデータをクラスに分類
する木（決定木）を生成する
• 代表的なアルゴリズム ID３, C4.5 では，情報
理論を利用して，早い段階でランダム性を減
少させる（クラスの絞り込みを早める）ような
決定木を生成する
• より複雑・巨大な問題に対するため，Random Forestのように多数の決定木を組み合わせる
方法も有効
18
演習２
• 決定木が確定するまでID3アルゴリズムを再帰的に
適用せよ
– 情報量を計算し，次の分岐に参照する属性を決定せよ
– 下図中の？の分岐属性を決定する際の集合Cは？
重量
重い
多い，重い，高い：－
多い，重い，安い：－
少ない，重い，安い：－
クラス確定
軽い
多い，軽い，安い：＋
多い，軽い，普通：＋
普通
？
クラス確定
19
演習 1/4
• Matlab による決定木生成
– Matlab は個人常用計算機から実行可能
• Matlab から load できる carsmall をクラス分類
– carsmall に含まれる属性（および属性値の例）
• Acceleration（14.0, 19.6）, Cylinders（4, 6, 8）, Displacement（91, 360）, Horsepower（63, 120）, MPG（13, 31）, Model（honda civic）, Model_Year（70, 82）, Origin（Japan, USA）, Weight（1965, 3870）
• 決定木は関数 classregtree により生成
演習 2/4
•
演習１
•
演習２
•
演習３
– 属性 Cylinders, Model_Year により，Origin をクラス分類せよ
– 属性 Cylinders, Model_Year, MPG により，Origin をクラス分類せよ
– 属性 Cylinders, Model_Year, MPG により，Origin をクラス分類せよ
– ただし，MPG は離散カテゴリ値ではなく連続値として扱う
•
演習４
– 属性 Cylinders, Model_Year, MPG, Weightにより，Origin をクラス分類せよ
– ただし，1000ポンド台，2000ポンド台，3000ポンド台，4000ポンド台を離散カテゴリ値と
する（これを指定するオプションが関数 classregtree にあるわけではない）
– MPG は連続値として扱う
•
•
全ての演習結果はコードと出力の決定木を可視化した結果（関数 view を使用す
る）を合わせて提出すること
関数 classregtree には多くのオプションがあるが，各演習で指定した以外のポイ
ントについてはどのようなオプションを用いても良い．ただし,各オプションの意味
（どのような決定木が生成されることを期待するか）をコード中にコメントとして残
すこと
演習3/4
• Akinator を作ってみよう
– 自分で「名前」「属性の集合」の組み合わせを学習データ
として用意する
• 学習データに含まれる推定対象数と属性数は，それぞれ15以上
，4以上とする
• 推定対象は自由に決めてよい
– スポーツ選手でも，動物でも，車でも．．．．
– 事前に用意した学習データに対して動作すれば，課題は
満点
– さらに推定失敗した際に，推定失敗対象を学習データに
組み込むプログラムを書けば，加点
22
演習 4/4
• 提出先
– endo.tamotsu.em7@is – 全ての提出物を zip で添付
– 期限
• 6/29 (mon), 24:00

Download Report