読者です 読者をやめる 読者になる 読者になる

ランダムフォレストのつくりかた(C++の実装例つき)

マラソンマッチ 機械学習 C++ TopCoder

この記事はCompetitive Programming Advent Calendar 2014 - PARTAKE24日目の記事のつづきです。前日の関連記事「ランダムフォレストのつかいかた」もありますので、こちらもよろしくお願いします。ランダムフォレストのつかいかた - じじいのプログラミング


ランダムフォレストは、機械学習の中でも、確率統計の知識がほぼ無しで実装できる簡単なアルゴリズムで、しかも性能もなかなかのものです。TopCoder機械学習マッチのいくつかは、コードを提出してTopCoderサーバで実行するルールなので、実装しやすいランダムフォレストは有力な選択肢です。実際にランダムフォレストが1位をとったコンテストもかなりあります。

決定木の作り方さえ理解すれば、ランダムフォレストは実装できたも同然ですので、この記事では、決定木を作る部分をメインに取り上げます

C++の実装例

とにかくコードを見れば分かる人のために最初に載せておきます。

  • 回帰(regression, 予想したい変数(目的変数)yが実数のとき)
  • 分類(classification, 予想したい変数yが正整数や列挙型のとき)
    • ランダムフォレスト分類のジニ係数を使った実装例 http://ideone.com/1einvv
      • (注:こちらは実践でまだ使ってないので、間違いがあるかもしれません。あったらぜひ教えてください)

出力を見れば、木が増えるほど、誤差が少なくなっていくのが分かると思います。

問題と方針

ランダムフォレストで、分類も回帰もできますが、ここでは、ランダムフォレストで分類する問題を例として挙げます。
ある競技で、レートと年齢に応じて「プロ」「趣味」と呼ばれることがあるとしましょう。すでに8人分のデータがあります。このとき、年齢35歳・レート1500の人(白丸の部分)は、「プロ」「趣味」どちらでしょうか?

f:id:shindannin:20141226102245p:plain

他の人のデータを見る限り、近い年齢とレートの人が「趣味」なので、おそらくこの人も「趣味」ではないかと予測できそうです。実際に「プロ」の人が多い「プロ」の領域と、「趣味」の人が多い「趣味」の領域を分ければ良く、良さげな領域の分け方を決める良いアルゴリズムがあれば、予測できます。この領域分けに決定木を使います。

f:id:shindannin:20141226102246p:plain

決定木をつくる

グラフを左に、決定木の両方を示しながら説明します。

  • グラフの点が、1つのデータに相当します。
  • グラフの領域が、決定木のノードに相当します。
  • グラフの太いオレンジの仕切り線が、決定木の条件(x0<2500など)に相当します。
  • ノード内に書かれている番号は、グラフの領域に含まれている点番号に相当します。

まずルートノードを作ります。全領域に全点が含まれているので、0,1,2,3,4,5,6,7となっています。
(なお、ランダムフォレストでは、通常は重複を許しランダムに選びます(例:5,1,1,3,7,2,5,0)。また全部の点を使わず2/3程度の点だけを使う場合も多いです。ただ、ここでは決定木を分かりやすく説明したいのでバラで全部を選びました。)
f:id:shindannin:20141226102247p:plain
次に分割する線を決めます。分割する軸(x0,x1)と分割する場所(0,1,2,3,4,5,6,7)の候補は、オレンジの線になります。この中でベストな分け方を選びます。ベストな分け方については、次の章で説明します。なお、ランダムフォレストでは、全部の候補を試すと遅いので、この中から、いくつかだけを試します。
f:id:shindannin:20141226102248p:plain
ベストな分け方がx1<2500と決まったとしましょう。まず、領域を分けます。2つの領域に分かれるので、子ノードを2つ作ります。左の子ノードにx1<2500を満たす点を、右の子ノードにx1<2500を満たさない点を入れます。
f:id:shindannin:20141226102249p:plain
次は子ノードを見ていきます(探索順は幅優先でも深さ優先でもどちらでも良いです)。対象の領域はx1<2500を満たす、グラフの下の部分。今回は分割する場所の候補は(0,2,5)だけになります。
f:id:shindannin:20141226102250p:plain
ベストな分け方が決まったので、ノードを分けます。
f:id:shindannin:20141226102251p:plain
もう、後は繰り返しです。次のノードに行きます。x1≧2500の領域です。
f:id:shindannin:20141226102252p:plain
ベストな分け方を決めます。
f:id:shindannin:20141226102253p:plain
もし、領域内の点が全て趣味(青)か全てプロ(赤)になったら、もう領域を分割しても無意味なので、終了です。このノードは葉となります。なお、ランダムフォレストでは、領域分割を打ち切る条件として以下のようなものも使う場合があります。

  • ノード内の点の数が一定以下になった
  • ノードの深さが一定以上深くなった

f:id:shindannin:20141226102254p:plain
次のノードに行きます。まだ、ここは青と赤の両方あるので、分けます。
f:id:shindannin:20141226102255p:plain
ベストな分け方を決めます
f:id:shindannin:20141226102256p:plain
すべてのノードが葉になったので終了です。
f:id:shindannin:20141226102257p:plain
決定木ができたので、もう予測するのは簡単です。年齢35歳・レート1500の人がどの領域に属するかは、決定木のルートから条件をたどっていけば良いだけです。簡単ですね。

ベストな分け方はどうやって決めるのか?

公式については、最初に挙げた資料を参考にすると良いと思いますので、具体的な計算例だけ書きます。

分類

上の例であげた「プロ」「趣味」のように、yが列挙型とか0,1,2...といった値しかとらない場合は分類(classification)と呼びます。
分類の場合は、ジニ係数を使う方法とエントロピーを使う方法が知られています。以下の図を見てもらえれば計算方法は分かると思います。この値が最小となる分け方を選びます。データ個数による重みづけの部分(*10/15, *5/15の部分)は忘れないようにしてください。左側の点がすべて同種(yが同じ値)、右側の点もすべて同種であれば、ジニ係数もエントロピーもどちらも0になります。
f:id:shindannin:20141226143839p:plain

回帰

yの値が実数を取るときは、回帰と呼びます(regression)。
回帰の場合には、左側・右側でそれぞれ平均をとり、それぞれ平均との差の2乗の総和を取ればよいです。重みづけは必要ありません。この値が最小となる分け方を選びます。データ個数による重みづけは必要ありません。左側の点のyが全て同じ、右側の点のyが全て同じときは、0になります。
f:id:shindannin:20141226143844p:plain

実践での応用

ただ、これらの分け方は絶対なやり方というわけではありません。例えば、こういう応用があります。

  • 多クラス分類の性能が悪い時に、2クラス分類に落とす。例えば、4クラスa,b,c,dに分類するときに、「クラスaとクラスa以外(クラスb,c,d)」「クラスbとクラスb以外」「クラスcとクラスc以外」「クラスdとクラスd以外」と、クラスの数4つのランダムフォレストをつくって、評価する。
  • 回帰の平均との2乗差の方法を、分類で使う。実際のところ、2クラス分類であれば、回帰のコードを分類で使っても、それなりに良い性能がでることも。
  • ジニ係数やエントロピーなどに、クラスごとに重みづけの係数をかける。TopCoderの場合、問題によっては、クラスxをクラスyと間違えたときと、クラスyをクラスxと間違えたときでは、ペナルティスコアが異なることがあります。平たくいえば、許される間違いと、許しがたい間違いがあるということです。こういう場合、分け方の評価関数に重みづけをすることで、良い結果が出せる場合があります。

決定木をたくさんつくって、ランダムフォレストにする。

あとは、ランダムフォレストにするだけです。といっても、単に多くの決定木をつくるだけです。もちろん、決定木をつくる際にランダムな要素があるので、決定木は同じにはなりません。全ての決定木で値を予想してみて、分類のときは多数決で、回帰のときは平均をとるだけです。本当にそれだけなので、実装を見た方が早いと思います。

みなさんも実装したら、ぜひ教えてください。楽しいランダムフォレストライフを!