機械学習

ランダムフォレストの基本的なことをまとめていく

本日はランダムフォレストに関して勉強したことをまとめていきます。

kaggleではランダムフォレストはあまり使われなく、XGBoostやLightGBMなどのモデルが主流となっていますが、それらのアルゴリズムを理解する上で決定木やバギングなどの考え方も理解しなければならないと思うので疑問に思ったことを中心にまとめていきます。

ランダムフォレストとは?

最初にランダムフォレストとは何だ?というところですが、下記のようなあるデータに対して決定木を複数作り、それらをアンサンブルすることで全ての決定木の予測値を活用して最終的な予測を行うというアルゴリズムになります。

ということで気になるのは

・どのように分岐を行うのか?

・ランダムフォレストの特徴は?

あたりなので簡潔にまとめていきます。ちなみにデータは下記レクチャーのをそのまま使っています。後はこちらの論文も参考にさせていただきました。

どのように分岐をさせるか?

今回は例として下記のようなゴルフクラブの特定のお客さんが、天気などのコンディションをもとにプレイしたかをまとめたデータセットを考えています。

このデータをもとにモデルを作りDay15の条件の時お客さんがプレイするか否かの分類を行うタスクを考えていきます。

早速決定木を複数作り学習を進めていきますが、決定木ではターゲットの値(プレイ or not)が良く分かれるようにサンプルを分けていきます。

なのでよく分かれたかどうかを定量的に評価するために、まずはあるデータセットに対しての不純度を計算して分岐箇所を決定していきます。

不純度の計算方法は二つあり、1つ目がInformation Gain、2つ目がGINI係数といいアルゴリズムによってどちらを使うかが変わってくるようです。

ここでは1つ目のInformation Gainによる不純度の計算、そして分岐点を決めるための指標である情報エントロピーというものの説明をしていきます。

最初にあるデータセットにおける不純度は下記の式で定義されます。

プラスは正例マイナスは負例を表し、あるノードに含まれるサンプル数における各ターゲットの属性の割合を表しています。また、マイナスが付いていますが真値pは0~1の値を取るためH>0となり、この値が低いほど不純度が低く(純度が高い)なります。

具体的なイメージのためにあるデータセットに含まれるターゲットが正例、負例3つずつの場合を考えると情報エントロピーは下記のように計算できます。

上記のようにターゲットの割合が半々であるということは、そのデータは未だ不純度が高い(最大)であると言えます。

分岐を行う際は分岐前後の情報エントロピーの差分(Information Gain)が最大になるように分岐の点を決定します。

下記の分岐の時にどちらのInformation gainが高いかを考えていきます。

先程計算した通り、各分岐でデータを分けた時のそれぞれの情報エントロピーを計算し、分岐をする前とした後での差分(Information gain)を計算します。

以上の計算より、天気で分岐した方がInformation gainの差分が大きくサンプルをより分けられることがわかりました。以下同様に指定した深さまで分岐させるか、又は各ノードに単一のターゲットしか入らなくなったら分岐が終了になります。

 

Information Gain以外にもGINI係数という値の分岐前後の差分でも決定木を作成するアルゴリズムがあります。GINI係数はInformation Gainと非常に似ており、正例・負例の割合を元に計算されるデータの不純度を表す値になります。

例えばサンプルが14個あり、正例が9個、負例が5個の場合GINI係数は下記のように計算されます。

各データセットでGINI係数を計算した後は先ほどのInformation Gainと同じように分岐前後の差分が最大化するように分岐を行っていきます。

アルゴリズムによってどちらの指標を使って分岐点を決めるか異なりますが、このような過程で決定木を複数作成していき、各決定木における各サンプルの出力値を用いて分類器なら多数決で回帰なら平均を用いて予測を行います。

何故「ランダム」フォレスト?

さらにランダムフォレストでは各木を作るときにバギングと特徴量のサンプリングというテクニックを用いて汎化性能を上げています。それぞれどういうものか簡単に説明していきます。

訓練データからランダムにデータを抜き取る

まず1つの決定木を作るときに重複を許してランダムに指定の個数データをサンプリングして1つの決定木用にデータセットを作成しています。

このようにデータセットを作成する方法をブートストラップと言い、ブートストラップを用いて複数の弱い学習器を複数作って組み合わせる方法をブートストラップアグリゲーション(bootstrap aggregation)略してバギングと言います。

またブートストラップでデータを作成すると、重複が許されているため本来あるデータから選ばれないデータ(Out of bagging)が出てきます。そのデータセットを検証データとして使ってモデルの評価を行うことも可能です。

分岐作成時の特徴量の抜き出し

バギングはデータセットのサンプルを行う方法でしたが、さらに分岐を決める際にも使う特徴量をランダムで選んでいます。例えばsckit learnのデフォルトでは特徴量が16個あった場合4個の特徴量から不純度を計算して分岐を決めます。

次に分岐を行う際は分岐で既に選んだ特徴量を除いたものから再び指定個数選びランダムで不純度を出すための特徴量を選びます。

英語ですが上記のテクニックは下記のようにアルゴリズムに組み込まれています。

The Elements of Statistical Learning参照

複数のモデルを組み合わせた後の分散は下記の式で表されます。

Bは決定木の数でρは各決定木の相関係数ですが、決定木を複数作ることで第2項目がゼロに近づき、バギングや特徴量のランダムサンプリングにより第1項も0に近づけたいという気持ちだと思います。

まとめ

今ではkaggleでほとんど見ないランダムフォレストですが、勾配ブースティングのように前の木の計算結果を使用して次の木を構築していくわけではないので計算コストが低く精度のあたりを付けるのには向いているのかもしれません。