ランダムフォレストのつかいかた

この記事はCompetitive Programming Advent Calendar 2014 - PARTAKE24日目の記事です。関連記事に実装編もあります。

ランダムフォレストのつくりかた（C++の実装例つき） - じじいのプログラミング

今年は、TopCoderの機械学習マッチに積極的に参加して、経験もいろいろ詰めたので、そのノウハウを公開しようと思います。

• 自分のやり方は我流なので、アドバイスをいただけると、とてもうれしいです。
• この記事にはランダムフォレストの説明はありません。ネット上に良い記事が多くあります。「はじめてでもわかる RandomForest 入門－集団学習による分類・予測 －」 －第７回データマイニング+WEB勉強会＠東京の記事は読みやすいと思いました。
• この中のコツのいくつかは、ランダムフォレストに限らず使えると思います。
• 実装はないので、Rã‚„Pythonパッケージ等のツールを使う方にも使えると思います。実装したい方は、上記の記事をみてください。

まずはデータを眺める。

ビジュアライズしてデータを眺めるのが、まず第一歩です。「データに不正値が混ざっていないか」「人間が見ればすぐ分かるような法則はないか」などをチェックします。ExcelでもRでもいいので、見ましょう。極端な話ですが、TopCoderの過去の機械学習マッチ中で、答えが必ず「ある実数*整数倍」になるデータというのもありました。こういった特別な法則を見逃すと、大きく不利になります。

説明変数を、自己判断で削らない。

これはありがちな失敗です。機械学習では、説明変数x0,x1,x2...から目的変数yを予想しますが、たいていの問題では、説明変数の内容が書かれあります。ただ、問題文で内容説明を読み、「あ、これは今回の問題に関係ないな。」と思って、削るのはやめましょう。自己判断で追加するのは良いですが、削るのはダメです。
例えば、TopCoderのOctaveClassifier（"http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=15879&pm=13017"）という問題ではsetIDという変数を、説明変数に残したかどうかが、上位に入れるかどうかの鍵になりました。本体データ分析の依頼者は意味なくつけた値だったはずなのですが、実際にデータを眺めてみると以下のように、近くのsetIDのものが、なんとなく似たような配置になっているのが分かると思います。

説明変数が多すぎて、削りたくなることはあるかと思います。ランダムフォレストの場合は、説明変数の寄与度が求められるので、寄与度が低い変数を取り除くというのはありです（ただ、経験上、あまり大きな効果はないです）。もしくは次元削減のアルゴリズムで説明変数を削りましょう。

説明変数を追加する。

問題で与えられたデータをそのまま説明変数にツッコむだけだと、それは他の人もやっているので、上位10%とかに入るのは難しいと思います。すでにあるデータから、新たな説明変数を求め追加することで、性能をぐっとあげることができます。いいかえれば、説明変数x0,x1,x2しかないような問題でも、x3,x4…を自分で定義して追加すると、性能が上がる場合があるということです。

（1）同種のデータとのかかわりを表す変数を追加する

これは意外と見落としがちです。どうしても１つ１つ別のデータとして見がちなのですが、他のデータとの関係は重要です。例えば、以下の図で、同じ色の点が同種のデータだったとします。黒淵の緑の点が、他の緑点を含む矩形領域のどの辺にあるかというのは、明らかに特徴の１つといえます。他にも、重心・回帰直線・共分散行列など、集合から求まる統計情報はいろいろとあります。さらに応用して、重心からの距離とか、密度とか、同じラベル内でxの値が何番目に大きいとか、そういった変数を追加するのも有効な場合はあります。
また、同種のデータであるという情報が、データの説明変数に含まれていない場合も、同種とみなせる場合もあります。以下の例では、「右斜め上に伸びるデータの集合が緑ラベルになる」という法則がありそうです。こういう場合は、k-meansのようなクラスタリングアルゴリズムで同種とみなしたり、密度が高い領域をUnionFindでつないで、それを同種のデータをみなせば取り扱えます。

（2）不正値の数を追加する

データがおかしいということ自体が特徴ともいえるので、不正値の数をカウントして、説明変数として追加したほうが良いです。

（3）x1-x2, x1+x2等を追加する

ランダムフォレストは、軸に平行な分け方しかできないので、x1-x2といった差分を追加するのは有効なことがあります。でかい決定木１本だけを作るというわけではないので、足さなかったからと言って、そこまで悪い結果になるってことはないのですが、そこそこ効果があるときはあります。

（4）他のジャンルの機械学習で使われる特徴量を追加する

文字列が出てきたらそのまま列挙型にせずいったん単語に分けて単語別にIDを付けたりとか、化学式に対してn-gramを使ってみたりとか、いろいろ工夫できます。他のジャンルの機械学習で使われる特徴量もいろいろと追加できないか考えましょう。

木は少しずつ増やす

ランダムフォレストで木を増やすことで結果が悪くなるということは、まずありません。つまり、計算時間が余っているなら、どんどん木を増やしていったほうが良いです。特にTopCoderルールの場合は、計算時間制限があるので。最初に木を作る本数を多めで決め打ちしてしまうと、時間ギリギリまで木を増やすということはできません。10本とか100本とか少ない本数を足していき、その都度時間を計測して、時間ギリギリまで追加する形がよいです。自前でコードを書いた場合は簡単にできますし、R言語でもforest <- grow(forest, 100)のように書いて繰り返し呼べば少しずつ増やすことができます。
また、TopCoderルールの場合は、メモリ制限もあるので、その制限にひっかからないようにするためにも、木を少しずつ増やす手法は有効です。

データの一部を過学習チェック用にとっておく。

正直ランダムフォレストでは、あまり重要ではありませんが、それでもデータが少ない場合、調整すべき変数が多い機械学習手法の場合は、やはりやったほうが良いと思います。

自分の場合は、以下のような手順で行っています。

1. データを90%（クロスバリデーション用）と10%（過学習対策用）にわける
2. クロスバリデーション。この90%のデータをさらに2つに分けて、片方を訓練データ、片方をテストデータとする。これで、説明変数を増やしたり、定数の調整をしたりして、良いスコアがでるようにする。これをデータの分け方を変えて、何度も繰り返す。
3. 満足がいったら、残り10%の過学習対策用をテストデータとして使う。これで結果がぐっと悪くなったら、過学習が疑われるので(2)からやり直し。（ただ、(2)(3)を何度も繰り返すと、データを分けた意味がないので、注意）

ちなみに、TopCoderの通常のマラソンマッチでも、最終調整時の最適化（＝最後にプログラム上に残った定数を調整することでスコアを稼ぐ）のときも、調整時に使わなかったテストケースを使って実行し、同じぐらいの得点がとれるか確認します。これでガクンと点数が下がったら、過学習を疑います。

/////
以上です。みなさんも、ぜひランダムフォレストを使ってみてください。

明日12/25最終日は、Advent Calendar主催者の tanzakuさん（毎年ありがとうございます）と、いつも衝撃の記事で楽しませてくれるli_sakuさんです。お楽しみに！