狠狠撸

はじめての decision tree
2019/07/25
データサイエンス第二グループ田口直弥

2
今日のテーマは決定木について

決定木って？
? 木構造を使った予測器
? ルートから説明変数をもとに走査し、回帰?分類を行う
? 各ノードが１変数についての条件分岐を担う
3
[Loh, 2014]

なぜ決定木について話す？
? テーブルデータでは以下の点で非常に有用 (主に vs NN)
? 単純に予測精度が高い
? kaggle では初手 GBDT はよくあること
? 予測根拠の解釈がしやすい
? 外れ値に対して頑健
? 欠損値をそのまま扱う手法が充実 (今回は紹介しない)
? GPU 使わなくてもある程度高速に学習できる
? NN 世代はあまりちゃんと勉強してない (と思ってるけどどうですか…？)
? 要所の概要は知ってるけどちゃんと理解してない
? 基礎的なモデルとか歴史とか全然わからない
4

5
決定木の学習アルゴリズムについて

AID (Automatic Interaction Detection) [Morgan & Sonquist, 1963]
? 史上初 [Loh, 2014] の回帰木アルゴリズム
? 二分木を前提
? ノード内偏差平方和 ( ? ?? ? ? ?
?) を小さくするようにノードを分割していく
ことで近い ?? がまとまる様に学習
? 予測値は学習データにおける葉ノードの ?? の平均値
6

? 学習アルゴリズムの大枠
① ルートノードに全ての学習データを
配置して学習開始
7
all train data
処理が完了していないノード
処理中のノード
処理が完了した中間ノード
処理が完了した葉ノード

8
all train data
② 注目ノードにおいて分割に用いる
変数 ? と分割条件を決める
年齢 > 25

9
all train data
③ ② の分割結果が終了条件に該当
しない場合、分割を実行して処理
が完了していないノードに遷移
年齢 > 25

10
all train data
④ ② の分割結果が終了条件に該当
する場合、分割を実行せず処理
年齢 > 25
男 or 女
体重 > 50

11
all train data
⑤ 処理が完了していないノードが
なくなったら学習完了
年齢 > 25
男 or 女
体重 > 50

12
all train data
年齢 > 25
男 or 女
体重 > 50

? 分割に使う変数と条件を決めるアルゴリズム
13
partial
train data
① 注目ノード内の不純度 ? = ? ?? ? ? ?
?
を計算
? = ??. ?

14
partial
train data
① 注目ノード内の不純度 ? = ? ?? ? ? ?
?
を計算
② 全特徴の全分割候補に対して分割を行い、
それぞれについて分割後の子ノードの
不純度の和 ? ??? = ? ? + ? ? を求める
numerical : ? ? ? 通り (? は unique 値数)
categorical : ? ???
? ? 通り (? は unique 値数)
? = ??. ?
変数条件 ? ? ? ?
性別男 or 女 2.8 7.3
年齢 < 20 10.2 2.1
年齢 < 21 9.8 1.9
…

15
partial
train data
① 注目ノード内の不純度 ? = ? ?? ? ? ?
?
を計算
不純度の和 ? ??? = ? ? + ? ? を求める
categorical : ? ???
③ 情報利得 ? = ? ? ? ??? が最も大きい変数?分割
条件を採用
? = ??. ?
? ? = ?. ?
? ? = ?. ?
変数条件 ? ? ? ?
性別男 or 女 2.8 7.3
年齢 < 20 10.2 2.1
年齢 < 21 9.8 1.9
…

? 終了条件
? 分割による情報利得が一定値を下回った場合に終了
? 学習を始める前にハイパーパラメータとして設定
? ハイパーパラメータなので over (or under) fitting が問題
となりがち
16

THAID (THeta Automatic Interaction Detection) [Messenger & Mandell, 1972]
? 史上初 [Loh, 2011] の分類木アルゴリズム
? 二分木を前提
? ジニ不純度 (? ? ? ??
?
) (またはエントロピー関数) を小さくするようにノードを
分割していくことで同じラベルがまとまる様に学習 (?? はノード内のラベル ? の比率)
? 予測値は学習データにおける葉ノードの中でもっとも比率の多いラベル
17

18
配置して学習開始all train data
年齢 > 25
男 or 女
体重 > 50

19
partial
train data
① 注目ノード内の不純度 ? = (? ? ? ??
?
)を計算
不純度の和 ? ??? = ? ? + ? ? を求める
categorical : ? ???
③ 情報利得 ? = ? ? ? ??? が最も大きい変数?分割
条件を採用
? = ?. ?
? ? = ?. ?
? ? = ?. ?
変数条件 ? ? ? ?
性別男 or 女 0.1 0.3
年齢 < 20 0.3 0.3
年齢 < 21 0.2 0.3
…

CART (Classification And Regression Trees)[Breiman et al., 1984]
? 最近の論文でも出てくるし、scikit-learn のもこれの最適化版
? AID, THAID とほぼ同様のアルゴリズムで回帰?分類木を構築
? AID, THAID に比べて終了条件を緩め (ノード内のデータ数で決める等)、
代わりに pruning を行う
? AID, THAID で問題となる over (or under) fitting に対応
20

21
年齢 > 25
男 or 女
体重 > 50

22
なくなったら pruning 後に学習完了
年齢 > 25
男 or 女
体重 > 50

? Pruning の方法
? 葉ノードの親ノード全てについて ↓ を終了するまで実行
? validation set における評価値が最も良くなる枝を pruning,
良くなる枝がない場合 pruning 終了
23
all train data
train data
validation
data
学習
pruning

ID3 (Iterative Dichotomiser 3) [Quinlan, 1986]
? 多分木を生成
? 多分木は二分木を繰り返せば得られ、また分割されすぎるので
好ましくない (統計的学習の基礎より)
? エントロピー関数を用い、分類問題のみ対応
? Categorical 変数については種類数分の分岐を生成
24

FACT (Fast and Accurate Classification Tree) [Loh & Vanichsetakul, 1988]
? Biases in variable selection
? CART や ID3 では各変数の全分割候補を探索しているため、分割候補
の回数の多い特徴に対する試行が増えて選択されやすくなる [Breiman, 1984]
? 原因は variable selection と分割選択を同時に行っていること
? 特徴選択と分割を別で行う
? 特徴選択 : それぞれ分散分析を行い、最も F 統計量が大きい特徴を選択
? 分割 : 選択された特徴に対して線形判別分析 (LDA) 等で決定境界決め
25

26
その他知っておいて損はなさそうな話

Single decision tree
アンサンブル
? Bagging
? 学習データをブートストラップサンプリングし、各サンプルを学習に使用
? 各木の予測値の平均 (回帰?分類) や多数決 (分類) 等で予測
? Random Forest [Breiman et al., 2001] では更に使用する変数もサンプリング
27
Original train
sampled train sampled train sampled train…
Single decision tree Single decision tree
Bootstrap sampling
…

? Boosting
? 木の学習結果に依存してどんどん木を構築していく
? ? 番目の木の予測値は ? ? ? 番目までの予測値の和との合計値
? 各ノード ? の予測値は ?? の平均ではなく ? =
?∈? ? ?
?∈? ? ?
で評価
? 分割用の不純度も ? に基づいて求められる
?? と ?? の誤差を ? ? ? まで
の予測値について
二次近似し、微分を 0 とおく
アンサンブル
28
Single decision tree
? ? = ?
? ? Single decision tree
? ? = ? ? ? ?
? ? Single decision tree
? ? = ? ? ? ? ? ? ?
? ?
https://www.kdd.org/kdd2016/papers/files/rfp0697-chenAemb.pdf

Importance score
? 木の可視化による解釈の限界
? 木が大きくなると把握しきれない
? アンサンブルしたら可視化してもわからない
29
https://explained.ai/decision-tree-viz/index.html

Importance score
? Mean Decrease in Impurity
? 各特徴について分岐に使われた回数を各ノードのサンプル数で
重み付けしたものの和
? 各特徴について分岐で得た情報利得を各ノードのサンプル数で
重み付けしたものの和
その他目にするやつ達
? Permutation importance
? Null importance
? SHAP
30
https://medium.com/the-artificial-impostor/feature-importance-measures-for-tree-models-part-i-47f187c1a2c3

まとめ
? 決定木の予測アルゴリズム
? 決定木の基礎的な学習アルゴリズム
? AID, THAID, CART, ID3, FACT
? アンサンブル
? Bagging, Boosting
? Feature importance
31

参考文献
- Loh WY (2014). Fifty years of classification and regression trees. International Statistical
Review, 82, 329–348.
- Morgan, J.N. & Sonquist, J.A. (1963). Problems in the analysis of survey data, and a proposal. J.
Amer. Statist. Assoc., 58, 415–434.
- Messenger, R. & Mandell, L. (1972). A modal search technique for predictive nominal scale
multivariate analysis. J. Amer. Statist. Assoc., 67, 768–772.
- Breiman, L., Friedman, J.H., Olshen, R.A. & Stone, C.J. (1984). Classification and Regression
Trees. Belmont: Wadsworth.
- Quinlan, J.R. (1986). Induction of decision trees. Mach. Learn., 1, 81–106.
- Loh, W.-Y. & Vanichsetakul, N. (1988). Tree-structured classification via generalized
discriminant analysis (with discussion). J. Amer. Statist. Assoc., 83, 715–728.
- Breiman, L. (2001). Random forests. Mach. Learn., 45, 5–32.
- Trevor Hastie et al. (2009). 統計的学習の基礎
32

狠狠撸

20190725 taguchi decision_tree_for_pubshare

More Related Content

20190725 taguchi decision_tree_for_pubshare

Editor's Notes