本日はランダムフォレストに関して勉強したことをまとめていきます。
ランダムフォレストとは？
ランダムフォレストとは弱学習器(決定木)を複数(並列に)作成して、各弱学習器の出力結果の平均(or多数決)を算出して予測を行うモデルとなります。
ブースティングなどの前の木の情報を利用する直列的なアルゴリズムに対して、同時に複数の木を作成することができるため計算コストが低いアルゴリズムな半面、各決定木の出力値を等しく扱うこともあり？精度が勾配ブースティング系のアルゴリズムと比べて低く、kaggleなどのコンペではあまり活躍していない印象です。
とはいえ、どういうアルゴリズムか興味があったので簡単に基本的なことをまとめていきます。データやアルゴリズムの勉強は下記レクチャーで行いました。後はこちらの論文も参考にさせていただきました。
アルゴリズムの中身
動画でもあるように例として下記のようなゴルフクラブの特定のお客さんが、天気などのコンディションをもとにプレイしたかをまとめたデータセットを考えています。
上記データを学習データとしてモデルを作成して、下記Day15のサンプルに対して分類を行うタスクを考えます。
早速決定木を複数作り学習を進めていきますが、ランダムフォレストで使用する決定木では不純度という指標を用いて分岐を行います。
不純度の計算方法は二つあり、1つ目がInformation Gain、2つ目がGINI係数といsklearnで手軽に実装する場合にはパラメータで切り替え可能なようです。
ここでは１つ目のInformation Gainによる不純度の計算の仕方を見ていきます。
最初にあるデータセットにおける不純度は下記の式で定義されます。
プラスは正例、マイナスは負例を表しており、不純度という名前の通りpは全体のデータに対する各属性の割合を表しています。(0≦p≦1)
真数が上記の範囲のため、H(S)は必ず>0となり、グラフは下記の通りとなるため割合が半々の時に不純度が最大となります。
具体的なイメージのために計算したいデータに含まれる属性が3:3の場合は下記のように計算されます。
この不純度を用いて、各変数のどの値で分岐を行えば分岐前の不純度の値と、分岐後の左右のノードに属する不純度の合計値が大きく変わるかを算出して分岐点を決定していきます。
下記の分岐の時にどちらのInformation gainが高いかを考えていきます。
先程計算した通り、各分岐でデータを分けた時のそれぞれの不純度(情報エントロピー)を計算し、分岐前後での差分を計算します。
以上の計算より、天気で分岐した方が属性をよく分類できることがわかりました。以下同様に指定した深さまで分岐させる、又は各ノードに単一のターゲットしか入らなくなったら分岐が終了になります。
最初に解説したようにGINI係数という指標を用いて決定木を作成することができます。GINI係数も同様に正例・負例の割合から計算される値となり定義からグラフを書くと下記のように書けるかと思います。
グラフ形状はInformation Gainと似ており、最大値が0.5となっています。具体的な計算をイメージするために、例えばサンプルが14個あり、正例負例が9:5の場合、GINI係数は下記のように計算されます。
各データセットでGINI係数を計算した後は先ほどのInformation Gainと同じように分岐前後の差分が最大化するように分岐を行っていきます。
このような過程で決定木を複数作成していき、全ての決定木におけるレコードの最終的な出力値を属するノードの正例、負例の比率からクラス分類を行い多数決を取り予測値としています。
ランダムフォレストの特徴
ランダムフォレストの特徴として木を作るときにバギングという方法で、ランダムにレコードをサンプリングして決定木を作成しています。また、それだけではなく特徴量も木毎にサンプリングを行っています。
訓練データからランダムにデータを抜き取る
まず1つの決定木を作る際に重複を許してランダムに指定の個数データをサンプリングして木を作成しています。
このようにデータセットを用意する方法をブートストラップと言い、ブートストラップを用いて複数の弱い学習器(決定木)を複数作って組み合わせる方法をブートストラップアグリゲーション(bootstrap aggregation)略してバギングと言います。
バギングによって作成することによって各木を作成する際のデータが異なるため、木同士の相関が低くなります。
またブートストラップでデータを作成すると、重複が許されているため本来あるデータから決定木を作成するのに選ばれないデータ(Out of bagging)が出てきます。そのデータセットを検証データとして使ってモデルの評価を行うことも可能です。
分岐作成時の特徴量の抜き出し
バギングはデータセットのサンプルを行う方法でしたが、ランダムフォレストではさらに分岐を決める際にも使う特徴量をランダムで選んでいます。
英語ですが上記のテクニックは下記のようにアルゴリズムに組み込まれています。
The Elements of Statistical Learning参照
一般に分散σ^2を持つB個の独立な確率変数の分散はσ^2/Bで表されます。今各木から得られる出力は同じデータから作られているため独立ではなく、同一分布だと考えられるため各木の出力は正の相関ρを持ちます。
任意の２つの確率変数に正の相関がある場合、平均の分散は下記の式で表されます。
Bは決定木の数でρは相関係数を表します。ρ微分を行うと正になることから、相関係数が上がると全体の分散が上がることがわかります。
またBを増やすこと(バギングすること)で第2項が減少して平均からの分散が小さくなることがわかります。
分散を1、相関係数を変えた場合の全体の分散の推移です。木の数を増やすほど分散の値が第2項に収束していきますが、相関が高いもの程収束が速い傾向にあるようです。
まとめ
kaggleでほとんど見ないランダムフォレストですが、並列で計算が可能な(前の木の情報を使わない)ため、計算コストが低いことがメリットになるかと思います。
また、ランダムフォレストを使うことはなくてもバギングや特徴量のサンプリングの考え方に関しては、今流行りの勾配ブースティングでもパラメータとして設定できるので大事なポイントになるかと思います。