備忘録

勉強や読書の記録

ISLR: Chapter 8 Tree-Based Methods

数学 機械学習 統計学 ISLR

8.1　The Basics of Decision Trees

8.1.1　Regression Trees

Predicting Baseball Players' Salaries Using Regression Trees
Prediction via Stratification of the Feature Space

　regression treeの構築方法は以下の2ステップ．

  1. 説明変数X_1, X_2,\ldots , X_pを，重複がないようにJ個の領域R_1, R_2, \ldots , R_Jに切り分ける．

  2. 全てのR_Jについて，観測がR_Jに属する場合は，R_Jに属する訓練データの平均値を予測値として返す．

　どうやってR_Jを見つけるかが問題だが，残差二乗和が最小になるようにする． \displaystyle \begin{align} \sum_{j=1}^{J}\sum_{i \in R_j} {(y_i-\hat{y}_{R_j})}^{2} \end{align} ここで，\hat{y}_{R_j}はR_jに属する訓練データの平均値，要するに決定木による予測値を表す．もう少し具体的に言うと，R_1(j,s)={X\mid X_j \lt s} \mbox{ and } R_2(j,s)={X\mid X_J \geq s}となるsを見つけなければならないが，それを残差二乗和が最小になるように決めるということ．つまり，下式を最小化するようなj,sを求める． \displaystyle \begin{align} \sum_{i:x_i\in R_1(j,s)} {(y_i-\hat{y}_{R_1})}^{2} + \sum_{i:x_i\in R_2(j,s)} {(y_i-\hat{y}_{R_2})}^{2} \end{align} で，終了条件を満たすまでこれを繰り返していくと分岐がどんどん増える．

Tree Pruning

　ところが上の方法でできる決定木は複雑過ぎるので過学習になりやすい．そこで，バイアスを少し大きくする代わりに，より分散が小さく，かつ解釈しやすい木が欲しい．

　では，どうやるのか？一度巨大な木T_0を作って，そこから部分木を刈り取っていく．Cost complexity pruningもしくはweakest link pruningと呼ばれる効率的な刈り取り方がある．これは以下の式を最小化する． \displaystyle \begin{align} \sum_{m=1}^{|T|}\sum_{x_i\in R_m} {(y_i-\hat{y}_{R_m})}^{2}+\alpha |T|,\mbox{ where } T \subset T_0\mbox{ and }\alpha > 0 \end{align} |T|はterminal nodesの総数．部分木の数が増えると|T|の項が最小化において効いてくるので，結果的に小さくなる．\alphaはvalidation setもしくはcross-validationで決める．詳細は以下のアルゴリズムの通り．

  1. 各terminal nodeの中の観測の個数が一定数以下になるまで領域に分割する．

  2. \alphaの関数としてcost complexity pruningを適用する．

  3. K-fold cross-validationを行う．For each k=1,\ldots, K:

    1. Step1, 2をk番目のデータセット以外に適用する．
    2. \alphaの関数として，k番目のデータセットを除いたMean squared prediction errorを求める．そして，\alpha毎に結果を平均し，average errorが最小となる\alphaを選択する．

  4. Step 3で求まった\alphaをStep 2で求めた関数に代入し，部分木を返す．

8.1.2　Classification Trees

　予測として返すのは，その領域に含まれている観測の中で最も属する観測が多いクラス．Regression Treesでは残差二乗和を使ってたが，Classfication Treesではそれに対応する概念として，classification error rate Eを用いて定義されるジニ係数がある． \displaystyle \begin{align} E=1 - \max_{k}\hat{p}_{mk} \end{align} ここで，\hat{p}_{mk}はR_mに含まれる観測におけるクラスkの比率．したがって，Eで求まるのは，R_mで最も出現しているクラスに属していない観測の割合ということになる．また，ジニ係数は以下のように定義される． \displaystyle \begin{align} G=\sum_{k=1}^{K}\hat{p}_{mk}(1-\hat{p}_{mk}) \end{align} 結局これはK個のクラスについて分散を求めており，\hat{p}_{mK}が0か1に近ければジニ係数は非常に小さくなるので，node purityを測るのに使われる．ジニ係数が小さければ，領域内でのクラスのばらつきの少ない木ということになる．また，ジニ係数の代わりとしてクロス・エントロピーもある． \displaystyle \begin{align} D=-\sum_{k=1}^{K}\hat{p}_{mk}\log \hat{p}_{mk} \end{align} 0 \leq \hat{p}_{mk} \leq 1というのは0 \leq -\hat{p}_{mk}\log \hat{p}_{mk}であるので，クロス・エントロピーはジニ係数と同様の尺度として扱える．そういうわけで，ジニ係数とクロス・エントロピーはclassification error rateよりもnode purityに強く反応するので，pruningする際に使われる．classification error rateはprediction accuracyを重視する時はジニ係数やクロス・エントロピーよりも良い指標になる．

8.1.3　Trees Versus Linear Models

　線形回帰は \displaystyle \begin{align} f(X)=\beta_0+\sum_{j=1}^{p}\beta_jX_j \end{align} であるのに対し，regression treeは \displaystyle \begin{align} f(X)=\sum_{m=1}^{M}c_m\cdot 1_{(X\in R_m)} \end{align} という形を取るので，かなり違う．というわけで気になるのはどちらが優れているのか．問題が線形に近いなら線形回帰の方が良いし，そうでないならregression treeの方が良い場合が多い．とは言えどのくらいモデルを解釈したいか，可視化したいかというのも手法選択の規準になりうるので，目的に合わせて自分で選べという感じ．

8.1.4　Advantages and Disadvantages of Trees

  • メリット
    • 決定木の方が線形回帰よりも人に説明しやすい．
    • 決定木による分類は，これまでの章で扱ってきた手法よりも人の意思決定に近いと信じる人もいる（なんのこっちゃ）
    • 可視化が楽なので専門家でなくても解釈しやすい
    • 質的データに対してわざわざダミー変数を作らなくても木を構築できるため，他の手法よりも質的な説明変数を扱いやすい
  • デメリット
    • 決定木は他の手法よりも予測精度が悪い
    • 決定木はrobustじゃない．つまり，データが変われば簡単に木構造が変わってしまう．

　ただし，Bagging, Random Forests, Boostingを使えば予測精度は上がる．

8.2　Bagging, Random Forests, Boosting

8.2.1　Bagging

　決定木は分散が大きいのでつらい．そこでbootstrapを応用したBaggingを考える．bootstrapは欲しい量の標準偏差を直接求めることが困難な場合に使われる．具体的には，それぞれの分散が\sigma^{2}であるようなn個の観測集合Z_1,\ldots , Z_nを平均すると，平均した観測集合の分散が\displaystyle \frac{\sigma^{2}}{n}になり，結果的にデータセットの分散が小さくなってハッピー，だからなるべく母集団からたくさんの観測をサンプルしようという話でした．

　Baggingは，bootstrapでたくさんデータセットを生成し，それらを用いて\hat{f}^{*b}(x)を求め，平均する．つまり， \displaystyle \begin{align} \hat{f}_{bag}(x)=\frac{1}{B}\sum_{b=1}^{B}\hat{f}^{*b}(x). \end{align} もちろんBaggingは他の手法にも適用可能だが，決定木には特に有効．というのもそれぞれの決定木はhigh variance, low biasだが，それらを平均すると分散が小さくなるから．分類問題に対しては，それぞれの決定木で予測し，その結果の中で最も多かった予測値を採用するという方法で対応可能．

Out-of-Bag Error Estimation
Variable Importance Measures

8.2.2　Random Forests

　Baggingとほぼ同じ．違いは，Baggingでは各ブートストラップサンプルに対し全ての変数を用いて決定木を構築していたのに対し，Random Forestsでは各ブートストラップサンプルに対しランダムに選択された m（m \approx \sqrt{p}とすることが多いらしい）個の変数を使って決定木をサンプルの個数分作る．Baggingと比べて変数の数が少ないので，結果的に，各木の分散が小さくなって良い．

8.2.3　Boosting

　BaggingやRandom Forestsのようなもの，これらは並列計算できるが，Boostingはその前のモデルに依存して新しいモデルが作られるので並列計算不可．また，Boostingは他の手法にも適用可能．パラメタとしては\lambda（よく使われるのは0.01もしくは0.001），サンプル数B（\lambdaが大きければBも大きい必要があるが，過学習しやすくなる），各木の分割数dの3種類．最適なBはクロス・バリデーションで決める．