ランダムフォレスト 特徴量の重要度（C++の実装例つき）
はじめに
今回の記事は、alfredplplさんの以下の記事とだいぶかぶっています…。図つきで、とても分かりやすい記事なので、お勧めです。こちらをはじめに読んだほうが良いと思います。alfredplpl.hatenablog.com
alfredplplさんの記事は分類を例にあげてましたので、こちらは回帰を例にあげて説明します。基本的な中身は一緒ですので、比較しながら読んでもらえればと思います。
Rのランダムフォレストの重要度
Rのランダムフォレストには２種類の重要度(importance)があります。この記事で説明するのは、IncMSEとIncNodePurityです。
| アプローチ | 回帰(regression) | 分類(classification) |
|---|---|---|
| シャッフルしたOOBデータで予測して求める | IncMSE | MeanDecreaseAccuracy |
| 決定木のノードの純度(Purity)の増分から求める | IncNodePurity | MeanDecreaseGini |
Rでの求め方
(以下の例はTopCoder機械学習マッチ"ChildStuntedness5"でのデータを使用しました。要ログイン→TopCoder)
(1)randomForestの引数にimportance=TRUEをセットする。（注：以下はただの例ですので、他の引数とかは適宜変更してください。）
forest <- randomForest(GENIQ~., data=data.train, ntree=200, importance=TRUE)
(2) プロットしたいならvarImpPlot、しないならimportanceを呼ぶ。
ret1 = varImpPlot(forest) ret2 = importance(forest)
結果は以下のようになります。
- IncMSEとIncNodePurityは別なので、重要度の値はもちろんのこと、上記のように順位が異なってくる場合もあります。
- 上記の方法ではなく、importance(forest)で重要度を出力すると、IncNodePurityは標準誤差で割られた値になります。*1
IncMSE
C++での実装例
C++の実装例と実行結果をideoneにアップしました。#define INCMSE (1)で使用するしないを切り替えられます。#if INCMSEで囲まれている部分を見れば、どう計算してるか分かると思います。もし、ランダムフォレストそのものの部分が分からない場合は、ランダムフォレストのつくりかた（C++の実装例つき） - じじいのプログラミングを参照してください。
アルゴリズム
入力変数X, 目標変数をyとします。データサンプルは(X1,y1),(X2,y2),...(Xi,yi),...(Xn,yn)のn個あるとします。
またXはベクトルでXi = {xi1, xi2, xi3, ..., xim}とm個の特徴量を持つとします。
以下の処理は、ランダムフォレストの決定木１本１本に対して行います。
- ランダムフォレストで、決定木を作るときに訓練に使われなかったデータサンプル（ブートストラップサンプリングで外れたデータ）を使います。これをOOBデータと呼びます（Out-of-bag(OOB) data、OOB examplesとも）。
- まずOOBエラーを求めます。OOBデータのXを決定木に入力すると、予測した結果y'を求められます。y'と目標変数yがどれだけズレてるかがOOBエラーです。回帰のときは、MSE(mean square error、平均二乗誤差)をOOBエラーとします。つまりΣ(yi-yi')^2 / kとなります（kはOOBデータのデータ個数）。
- m個の特徴量それぞれに対して重要度を求めます。単純にm回ループして、ループ変数を特徴量fとして、以下のことをします。
- OOBデータの特徴量fだけをシャッフルします。他の特徴量とyはシャッフルしないので、気を付けてください。
- X1=( 1.0, 2.1, 3.2) y1=1.2
- X2=( 0.5, 1.6,-2.1) y2=2.1
- X3=(-1.2, 1.5, 2.0) y3=3.5
- ↓シャッフル
- X1=( 1.0, 1.6, 3.2) y1=1.2
- X2=( 0.5, 1.5,-2.1) y2=2.1
- X3=(-1.2, 2.1, 2.0) y3=3.5
- シャッフルしたデータを使って、(2)と同じようにOOBエラーを求めます。特徴量fだけシャッフルしたので、特徴量fが重要なのであれば、重要なデータがシャッフルでおかしくなったわけなので予測が悪くなるはずです。予測が悪化した値、つまり、(シャッフルしたデータのOOBエラー) - (元のOOBエラー) を重要度IncMSEとします。
- OOBデータの特徴量fだけをシャッフルします。他の特徴量とyはシャッフルしないので、気を付けてください。
最後に、全ての決定木のIncMSEの総和を求めて、最後に木の本数で割って平均を求めます。
ポイント
- 計算時間は、かかります。訓練の計算は1回だけで済みますが、予測は、（OOBデータ個数）＊（木の本数）＊（特徴量の数）＊（特徴量1つあたりのシャッフル予測の回数 nPerm）回だけ行うことになります。予測は訓練に比べたら計算時間はずっと短いですが、回数が増えればもちろん時間はかかります。時間がかかりすぎの場合は、上記の4つのどれかを減らす必要があります。
- 重要度として、それなりに信頼できます。シャッフルする部分以外は、通常のOOBデータを使った予測と変わらないので。
- マイナスの値もとりえます。予測に影響をほぼ及ぼさない特徴量だと、シャッフルして、たまたま逆に予測精度があがることもあり得ます。もちろん、重要度は最悪という意味です。
- Rでの変数名は、%IncMSEと%がついていますが、全部足して100%になるわけではありません。
R Projectによる、C言語での実装例
本体はC言語で書かれています。CRAN - Package randomForestからrandomForest_4.6-10.tar.gzをダウンロードしましょう。 src/regrf.c の262-295行と327-338行のあたり、if(varimp){} のスコープ内のコードを読むと分かりやすいと思います。
IncNodePurity
C++での実装例
先程のコードの#if INCNODEPURITYで囲まれている部分で、求めています。
アルゴリズム
ランダムフォレストのノードの分け方を知ってるなら、何も新しい知識はいりません。
決定木を作る際に、各ノードを子2つに分けるベストな分け方は、（親のMSE）-（子2つのMSE）が最大をとるときです（（親のMSE）は固定なので、（子2つのMSE）の最小化でもいいです）。数式で書けば以下のようになります。
Aを集合として、i番目の目的変数をYiとして、親の集合Pを、子の集合Lと集合Rに2つに分割する。
要素数 |A|
総和 S[A] = {Σ[i∈A]Yi}
平均 E[A] = S[A]/|A|
と表す。MSE（平均2乗誤差）の変化量は以下のようになる。
{Σ[i∈P](Yi-E[P])^2} - {Σ[i∈L](Yi-E[L])^2} - {Σ[i∈R](Yi-E[R])^2}これを選ばれた特徴量別に足していくだけです。最後に木の数で割ります。
ポイント
- 計算時間は速いです。決定木を作る際に求まるので、訓練をすればいいだけで、予測の時間はかかりません。これはIncNodePurityの最大のメリットです。
- 重要度としては、あまり信頼できません。確かに分割の際に使われる特徴量は重要とは言えますが、あまり直接的ではないので。ただ、例えば、特徴量が1000個あるときに下位50個を削りたいと言った、ざっくりとした特徴量抽出には使いやすいです。 （実際、1位を取ったマッチToxCast Challenge | EPA TopCoderでは、これを使いました。）
- 決定木の数が増えても、値は増えません（木の数で割って平均をとってるので）。
- サンプルデータの数に比例して、値は大きくなります。
- 経験上、決定木の数が少ない場合でも、かなり値は安定することが多いです。最初は多くの決定木を使って、次に少ない決定木を使って、結果があまり変わらなかったら、それ以降は少ない本数で試すというアプローチが、時間を節約にもなって良いと思います。
R Projectによる、C言語での実装例
先ほどダウンロードした、randomForest_4.6-10.tar.gzを参照してください。
- src/regrf.c の変数tginiがIncNodePurityになります。
- src/regTree.cで、tginiを計算していますが、変数crit→critvar→critmax→decsplit→tginiというふうにデータが渡されています。247行目 crit = (suml * suml / npopl) + (sumr * sumr / npopr) - critParent; が重要です。平均2乗誤差を使う場合は式展開すると、以下のように簡単になり、これで合ってます。
{Σ[i∈P](Yi-E[P])^2} - {Σ[i∈L](Yi-E[L])^2} - {Σ[i∈R](Yi-E[R])^2}
= {Σ[i∈P]Yi^2} - 2E[P]{Σ[i∈P]Yi} + |P|E[P]^2 - {Σ[i∈L]Yi^2} + 2E[L]{Σ[i∈L]Yi} - |L|E[L]^2 - {Σ[i∈R]Yi^2} + 2E[R]{Σ[i∈R]Yi} - |R|E[R]^2 ... 2乗を展開した
= - 2E[P]{Σ[i∈P]Yi} + |P|E[P]^2 + 2E[L]{Σ[i∈L]Yi} - |L|E[L]^2 + 2E[R]{Σ[i∈R]Yi} - |R|E[R]^2 ... {Σ[i∈P]Yi^2} = {Σ[i∈L]Yi^2} + {Σ[i∈R]Yi^2} で消した。
= - 2E[P]S[P] + |P|E[P]^2 + 2E[L]S[L] - |L|E[L]^2 + 2E[R]S[R] - |R|E[R]^2 ... 総和Sであらわした
= - 2S[P]^2/|P| + S[P]^2/|P| + 2S[L]^2/|L| - S[L]^2/|L| + 2S[R]^2/|R| - S[R]^2/|R| ... E[A] = S[A]/|A|で平均Eを消した
= - S[P]^2/|P| + S[L]^2/|L| + S[R]^2/|R| ... 足し算
重要度をどう使うか？
特徴量選択
無意味な特徴量を削ることで、予測精度を上げることができます。また、計算時間も速くなり、多くの木を作れるので、それでも精度を上げることができます。
以下に、自分が行う特徴量選択の方法をまとめてみました。今回の2つは(3)(4)にあたります。
| 手法 | 選択性能 | 計算時間 |
|---|---|---|
| (1) 特徴量を削りクロスバリデーションで予測するのを、全ての特徴量で試す | 良い*2 | とても遅い |
| (2) 特徴量を削りOOBデータを使って予測するのを、全ての特徴量で試す | 良い | 遅い |
| (3) IncMSEで重要度の低い特徴量を削ってみる | 普通 | 普通 |
| (4) IncNodePurityで重要度の低い特徴量を削ってみる | 悪い | 短い |
- かけられる時間やデータ量にもよるのですが、(4)→(3)→(2)→(1)の順に試すのが良いと、自分は思います。基本は(2)になると思います
- (1)(2)(3)については、MSEではなく、精度の評価関数（scoring function）に置き換えることもできます。例えば、yの大きい順を予測したい順位当ての問題のときは、順位差の絶対値の総和をMSEの変わりに使うといったこともできるでしょう。
- ただ「重要度を低い特徴量を削る」と簡単に書きましたが、貪欲に１番重要度が低い特徴量を削っていけば良いというものでもなく、とても難しいです*3。特徴量間に強い関係があれば、特徴例をけずるたびに、重要度も大きく変わってきます。良い方法があったら（というか研究されていると思いますが）、ぜひ教えてもらえるとうれしいです。一応、自分のアイディアレベルのネタとしては、
- (2)(3)であれば、複数の特徴量をシャッフルする手はあるでしょう。ただ、（OOBデータ個数）＊（木の本数）＊（特徴量の数 ^ シャッフル個数）＊（特徴量1つあたりのシャッフル予測の回数 nPerm）回となるので、特徴量が多いときは、シャッフル個数2個にするのすら遅すぎて難しいかもしれません。
- 探索枝仮り・焼きなまし法・ビームサーチといった最適化手法で削っていく方法もあるでしょう。
- 特徴量を１つ削ったとき、他の重要度がどう変化するかで、どの特徴量間に強い関係があるかというグラフのようなものを作れば、最適化手法を使っていく上で役に立つかもしれません。例えば、「特徴量はx1,x2は片方を削ると、もう片方の重要度が大きく下がるので、たぶんペアで意味がある特徴量だ。焼きなまし法を試すときは、この２つはまとめて追加したり削除したりするようにしよう。」といったことはできそうな気がします。
ランダムフォレストのパラメータ調整がひどいのに気付くきっかけ
最初にあげた図では、SUBJIDという特徴量は、重要度IncMSEで最小、重要度IncNodePurityで最大になっています（SUBJIDは、本当に無意味なIDで、実際はIncMSEが正しかったです）。
このように、IncMSEの大きさの順位とIncNodePurityの大きさの順位が異なる場合、経験上ですが、予測精度も悪くなる傾向にあります（）。恐らく原因としては、
- 元の特徴量が少なすぎる
- 木を深いところまで作りすぎている（nodeSizeが大きい or maxLevelが大きい）
のあたりでしょう。
ideoneのコードの645行目
rf->train(trainingFeatures, trainingAnswers, 5, 999, 2, 5, 0.66f, numTrees);
のnodeSizeとmaxLevelのパラメータを変化させ、IncMSE・IncNodePurity・totalErrorの変化をみてみると良いと思います。
以上です。ご感想・ご意見お待ちしてます。
*1:今回は詳細は述べませんが、詳しく知りたい方は、RのソースコードをimportanceSD, impSDで検索したり、importance.Rからソースを追ってみてください。SDという名前で標準偏差に見えますが、なぜか標準誤差なので注意してください（ネットでも多数の間違いが見られます…）
*2:「とても良い」の可能性もありますが、OOBデータ vs クロスバリデーションの議論は奥深いようなので踏み込みません
*3:あくまで自分のイメージですが、「特徴量の追加削除」を近傍、「重要度」を関数の傾きと置き換えると、近傍にいっただけで関数の傾きが大きく変化したりする関数を最適化しないといけないようなものなので、やばいかんじしかしません…
ランダムフォレストと他の機械学習（or統計）を組み合わせて使う
もしかしたら、プロにとっては当たり前のテクニックかもしれませんが、自分は初めて見たので書きたいと思います。また、おそらく大きい効果を出すのが難しいテクニックだと思われるので、まずは基本的なことを先にやったあとに試したほうがいいでしょう。
追記 3/13 このテクニックは「stacking」と呼ばれるそうです。Twitterで教えていただきました。ありがとうございます！
Stacking, Blending and Stacked Generalization | Garbled Notes
Ensemble learning - Wikipedia, the free encyclopedia
ここから本題です。
前々回のTopCoder機械学習マラソンマッチTripSafetyは、飛行機のフライトデータから、違反フライトを予測するという問題でした。問題やデータはこちら
予測精度をよくするために特徴量を追加したりするのですが、自分を含めて多くの人がやった手法は、特徴量(x24,x25,x26,x27,x28)だけを使って、新たな特徴量(x29)を追加するものでした。x24-x28は重混雑・中混雑・軽混雑と似たような指標なので、重み付けをして１つの特徴量にまとめるという発想は自然にでてくると思います。自分はx29 = 32*x25 + 8*x26 + 2*x27 + x28としました。
しかし、優勝したPsyhoさんは、元の特徴量(x24,x25,x26,x27,x28)と目的変数yに対してを使って、ここで正則化つきの線形回帰を使って、その結果を新たな特徴量(x29)として追加しています。新たな特徴量を追加するのにxだけではなくyも使っているのが最大のポイントです。*1
全体の流れは以下のようになります。
- 上記のように、訓練データのx24～x28とyを入力して、線形回帰して、x29=α24x24+...+α28x28+βの、α,βを求める。*2
- 訓練データのx1～x29（x29はx24～x28,α24～α28,βから求める）とyを入力して、ランダムフォレストで学習させる
- テストデータのx1～x29（同じくx29はx24～x28,α24～α28,βから求める）を学習させたランダムフォレストに入力して、yを予測する
線形回帰での予測結果x29を、y=x29としてそのまま答えにすることもできるのですが、線形回帰とランダムフォレストの２段構えになっています。
なぜ、これがうまいのかというと、
- 線形回帰の予想精度が良ければ、その結果をほぼそのまま返すことができる。
- 線形回帰の予想精度が悪かったとしても、ムダな特徴量が１つランダムフォレストに追加されただけなので、全体としての予想精度の低下はほとんどない。（ランダムフォレストでの寄与度がとても低い変数が増えただけ）
- 線形回帰自体は表現力が高くないけど、その弱点をランダムフォレストでカバーできる。今回の場合でいうと、x29とyの値は近くないけど（特にy=1のとき）、この後にまだランダムフォレストがあるので、そこで精度を上げられる可能性がある。
参考までに、実際に100ケースで、自分のPCでテストしたところ、得点は285363点→288294点と約3000点増えています。あまり大きくはないですが、本番で2位だった112atn323さんとの点差も約3000点差と僅差だったなので、他の部分も十分詰めたあとなら試す価値はあると思います。*3
今回の問題では線形回帰でしたが、簡単にいえば機械学習（or統計）の手法の多くは、２つ組み合わせることができるということです。Psyhoさんのコードを見る限りでは、ロジスティック回帰＋ランダムフォレストも試そうとしていたようです。
もちろん、複数の機械学習手法を試す人は多くいると思いますが、以下のどちらかが多いです。
- 複数の手法を試して、その中で一番良かった手法を使う
- 問題をいくつかのケースに分けて、ケースごとに一番良いものを使う（例：データが大きいケースはランダムフォレスト、小さいケースはニューラルネット）
でも、今回のPsyhoさんの解のように、２つの機械学習をあわせて使うのは、自分は初めて見ました。
ただ、まだ分かっていないのが、「どの特徴量に対して使うのが効果的か？」。これは難しいです。今回の問題だと、混雑度が大きければ大きいほど、違反フライトは単調増加しそうなので、線形回帰のように表現力低めの手法でも合いそうな気がしますが…。今のところは色々試す、そしてそれを自動化するぐらいしかないですね…。今後の課題です。
PS4「信長の野望 創造 with パワーアップキット」の感想
PS4「信長の野望 創造（無印版）」の感想は以前こちらに書きました。
http://shindannin.hatenadiary.com/entry/2014/08/16/190652
今回はパワーアップキット版の感想を書きます。
いろんな要素が追加されて、ダメになった部分はほとんどないので、その点では、パワーアップキット版は、安心してプレイできると思います。
ただ、ゲームの攻略が主目的（難しい条件で天下統一とか）のプレイヤーにとっては不満もあるかも。根本的な部分「攻め続けるのがベスト」なのは、パワーアップキットになっても変わっていません。たとえ、多くの要素が追加されても、多くの大名・シナリオがプレイできても、ここが同じだと「解法は一緒でした！」ということで、すぐ飽きてしまいます。戦略の幅が広いほうが良かったと思います。
例えば、戦争しすぎることに対するペナルティーがあっても良かったと思います。ひどい一揆がおこるとか、兵が回復しないとか。そうすれば、軍事以外の選択をすべき状況も増えて、今回追加された内政面・人事の追加要素や、城の改修といった地味な要素も、もっと生きてきたと思います。
あと、バグの問題が多くありました。「会戦中のゲーム強制終了」「文字がでなくなる」「部隊の操作不能」「変なファンファーレが延々と流れる」など…。今回PC版とPS4版が同時発売で、事前にPC版でデバッグされる期間がなかったので、バグが多いだろうなぁと思ってたのですが、実際多かったです。ただ、アップデータがわりとまめで、バグの対応も早いです。PS4だと動画つきバグレポートが送信できるので、それで送って待つしかないです。
会戦
| 会戦キャンセル問題が解消された。 |
| 操作性がいまいち。 |
| あまり奥の深さが感じられない。 |
| 会戦のチュートリアルはあるのだけど、気づかれない可能性が高い。 |
まず、無印版の一番の問題だったと思われる、会戦キャンセル問題が治ったのは大きいです。キャンセルはいまだにできるのですが、キャンセルしたあともう一回会戦をした場合、状況はそのまま引き継がれます。これは良い対応だと思いました。
操作性で気になった部分は、
- カーソルが重い
- 大会戦のキャンセル（兵が４割ぐらい無条件で減る大ペナルティ）も割と簡単で、誤爆しそうになる（実際、１回した）。
カーソルに変な重力がかかった感じで、部隊の選択が思うようにできないことがありました。アップデートで若干解消されてる気もしますが…。
新しい会戦は、無印版よりは良いです。ただ、思ったよりは工夫する余地がなく、単調な気がします。「うまく部隊を操って、寡兵で敵を打ち破った！」というのは、そんなに味わえないかもしれません。
- 索敵（敵の場所が分からない）要素はあるものの、敵はほとんど直進してくるので、「敵が意外な位置から来た。やべー」といった緊張感は全くありません。
- マップに障害物がほとんどないので、「２つのルートがあって、敵がこっちから来ると予想できるので、ここで迎え撃とう」というのもありません。（まぁ、川の戦闘はありますが、川の前にいればいいだけなので、奥深さはかんじないです…）
- 通常の会戦では、勝利条件が「敵の全滅」しかないので、まぁ、部隊が同士討ちされない程度にまとまって集中弓攻撃（狙われてる部隊は逃げる）ぐらいしか考えられないです、
- 戦法については、いろいろあり、「誘導＋同士打ち」みたいなこともできるので、悪くはないです。ただ、機会は少ないかも。
軍団長
| 直轄領以外の金・兵糧がコントロールできるようになった。 |
| 軍団長でも、やはり遠くに遠征はできないので、結局軍団を解散して、１つ１つ出陣させるはめに。 |
| 軍団長がしゃべるのは面白い。 |
無印版だと、自分が操作できない城にたくさんの兵糧が溜まってしまい、それを本体に輸送してほしいのですが、それができないという問題がありました。わりと金・兵糧不足で悩まされるゲームなので、この修正はうれしいです。
内政
| 城の改修はいろいろできるけど、あまり生きない。 |
自分が生かし方に気づいてないだけかもしれません。もしそうだったらごめんなさい。城にも内政値アップとか部隊の戦闘力アップとかいろいろとメリットがあるのですが、基本的には守備の施設です。序盤は城の改修するほど金がないですし、後半なら城は強くなりますが攻めてくる兵力も大きく、それは防ぎきれないかんじです。わざと攻めさせてカウンターするといった使い方もありますが、交通の要衝でないと、生かせません。城を作るよりも、「攻撃は最大の防御」で、攻めたほうが良いんですよね…。
人事
| 引き抜き・不戦などが追加され、忠誠度が意味のあるものになった。 |
| 無印よりも敵国に武将が行ってしまうことが多くなった。 |
これは改善されたと思います。
朝廷
| どんなケースでも朝廷信用100で停戦できるので、ゲームが少し簡単になった気がする。 |
断絶で「裏切りものとは手を組まない」とかになると、一切止められなくて、すごく難しい（やりがいもある）かったのですが、朝廷を使えば、結構防げます。ぼけーっとしてて、強い大名の同盟が途切れて責められたりしても、保険として使えます。
連合
| 関ヶ原の再現という意味では、非常に良い。 |
| 信用がすごい勢いで増えるので、援軍出し放題になり、ゲームがだいぶ簡単になった気がする。 |
仮に敵に連合を作られても、こちらも連合作れます。工作せずにどんどん信用が上がっていくのは大きく、援軍・同盟結び放題。連合が解散になっても、高い信用を生かしてまた連合が作れるので、ちょっと有利すぎかもしれません。
戦国伝
| すばらしい。かなり渋いイベントもある。 |
これは大満足です。歴史好きの人もやりこみ系の人も、満足しそう。「慶長出羽合戦」がお気に入り。
まぁ、いろいろ不満点も書きましたが、今回無印版からですが、戦略時のAI、兵・米・金のバランスなど基本の部分はしっかりしていて、興ざめするということは少ないと思います。実際、長時間プレイしましたし、満足です。ぜひ、次回作もこんなかんじでお願いしたいです。
2015年 競技プログラミングの目標
評価
目標：2015年は100点以上
| 200～ | 偉大すぎるので、誰かが奢ってくれるはず |
| 150～199 | PERFECT |
| 120～149 | GREAT |
| 100～119 | GOOD |
| 60～99 | 進歩なし |
| 30～59 | 怠惰・堕落(FUJIYAMAに乗る) |
| 0～29 | 人としてダメ(FUJIYAMAに乗る) |
(なお、2014年は60点でした)
得点表
| SRMに56.6%以上参加*1 | 20点 |
| SRMに56.6%以上参加したうえでRating1800以上 | 20点 |
| TCO15 SRM Round 3 | 20点 |
| マラソンマッチ レッドコーダー | 80点 |
| TCO15 マラソン予選10位以内 1回ごとに | 20点 |
| TCO15 マラソンワールドファイナル出場 | 300点 |
| Google Code Jam Round 3 | 10点 |
| プロコンTシャツゲット1枚ごとに | 5点 |
| プロコン賞金10万円ごとに | 10点 |
| プロコンでオンサイト決勝出場 | 50点 |
| ニコ生放送200枠分（=100時間） | 10点 |
| 海外でプロコンオフ会をやる | 10点 |
| Codeforcesで栗原市ランキングいり | 10点 |
*1:2015/8/2 SRM30回参加にしてましたが、当初予定されていた月4回SRMでなくなってしまったので、割合に変えます。30回/53回(SRM48回+TCO5回)=56.6%
ランダムフォレストのつくりかた（C++の実装例つき）
この記事は24日目の記事のつづきです。前日の関連記事「ランダムフォレストのつかいかた」もありますので、こちらもよろしくお願いします。
ランダムフォレストのつかいかた - じじいのプログラミング
ランダムフォレストは、機械学習の中でも、確率統計の知識がほぼ無しで実装できる簡単なアルゴリズムで、しかも性能もなかなかのものです。TopCoder機械学習マッチのいくつかは、コードを提出してTopCoderサーバで実行するルールなので、実装しやすいランダムフォレストは有力な選択肢です。実際にランダムフォレストが１位をとったコンテストもかなりあります。
決定木の作り方さえ理解すれば、ランダムフォレストは実装できたも同然ですので、この記事では、決定木を作る部分をメインに取り上げます。
- アドバイスをいただけると、とてもうれしいです。間違いのご指摘は大歓迎です。
- 実装は、TopCoderの他の競技者（PsyhoさんやJacoCronjeさん）のをベースに作ったものです。
- ランダムフォレストもバリエーションがあり、実装もいろいろあるので、注意してください。
- ランダムフォレストの概要を知るには、以下の記事がとても良いと思います。ぜひ事前に目を通してもらえればと思います。
C++の実装例
とにかくコードを見れば分かる人のために最初に載せておきます。
- 回帰(regression, 予想したい変数（目的変数）yが実数のとき）
- ランダムフォレスト回帰の実装例 https://ideone.com/BmvLEq
- 分類(classification, 予想したい変数yが正整数や列挙型のとき）
- ランダムフォレスト分類のジニ係数を使った実装例 http://ideone.com/1einvv
- （注：こちらは実践でまだ使ってないので、間違いがあるかもしれません。あったらぜひ教えてください）
- ランダムフォレスト分類のジニ係数を使った実装例 http://ideone.com/1einvv
出力を見れば、木が増えるほど、誤差が少なくなっていくのが分かると思います。
問題と方針
ランダムフォレストで、分類も回帰もできますが、ここでは、ランダムフォレストで分類する問題を例として挙げます。
ある競技で、レートと年齢に応じて「プロ」「趣味」と呼ばれることがあるとしましょう。すでに8人分のデータがあります。このとき、年齢35歳・レート1500の人（白丸の部分）は、「プロ」「趣味」どちらでしょうか？
他の人のデータを見る限り、近い年齢とレートの人が「趣味」なので、おそらくこの人も「趣味」ではないかと予測できそうです。実際に「プロ」の人が多い「プロ」の領域と、「趣味」の人が多い「趣味」の領域を分ければ良く、良さげな領域の分け方を決める良いアルゴリズムがあれば、予測できます。この領域分けに決定木を使います。
決定木をつくる
グラフを左に、決定木の両方を示しながら説明します。
- グラフの点が、１つのデータに相当します。
- グラフの領域が、決定木のノードに相当します。
- グラフの太いオレンジの仕切り線が、決定木の条件（x0<2500など）に相当します。
- ノード内に書かれている番号は、グラフの領域に含まれている点番号に相当します。
まずルートノードを作ります。全領域に全点が含まれているので、0,1,2,3,4,5,6,7となっています。
（なお、ランダムフォレストでは、通常は重複を許しランダムに選びます（例：5,1,1,3,7,2,5,0）。また全部の点を使わず2/3程度の点だけを使う場合も多いです。ただ、ここでは決定木を分かりやすく説明したいのでバラで全部を選びました。）
次に分割する線を決めます。分割する軸（x0,x1）と分割する場所（0,1,2,3,4,5,6,7）の候補は、オレンジの線になります。この中でベストな分け方を選びます。ベストな分け方については、次の章で説明します。なお、ランダムフォレストでは、全部の候補を試すと遅いので、この中から、いくつかだけを試します。
ベストな分け方がx1<2500と決まったとしましょう。まず、領域を分けます。２つの領域に分かれるので、子ノードを２つ作ります。左の子ノードにx1<2500を満たす点を、右の子ノードにx1<2500を満たさない点を入れます。
次は子ノードを見ていきます（探索順は幅優先でも深さ優先でもどちらでも良いです）。対象の領域はx1<2500を満たす、グラフの下の部分。今回は分割する場所の候補は(0,2,5)だけになります。
ベストな分け方が決まったので、ノードを分けます。
もう、後は繰り返しです。次のノードに行きます。x1≧2500の領域です。
ベストな分け方を決めます。
もし、領域内の点が全て趣味（青）か全てプロ（赤）になったら、もう領域を分割しても無意味なので、終了です。このノードは葉となります。なお、ランダムフォレストでは、領域分割を打ち切る条件として以下のようなものも使う場合があります。
- ノード内の点の数が一定以下になった
- ノードの深さが一定以上深くなった
次のノードに行きます。まだ、ここは青と赤の両方あるので、分けます。
ベストな分け方を決めます
すべてのノードが葉になったので終了です。
決定木ができたので、もう予測するのは簡単です。年齢35歳・レート1500の人がどの領域に属するかは、決定木のルートから条件をたどっていけば良いだけです。簡単ですね。
ベストな分け方はどうやって決めるのか？
公式については、最初に挙げた資料を参考にすると良いと思いますので、具体的な計算例だけ書きます。
分類
上の例であげた「プロ」「趣味」のように、yが列挙型とか0,1,2...といった値しかとらない場合は分類（classification）と呼びます。
分類の場合は、ジニ係数を使う方法とエントロピーを使う方法が知られています。以下の図を見てもらえれば計算方法は分かると思います。この値が最小となる分け方を選びます。データ個数による重みづけの部分(*10/15, *5/15の部分)は忘れないようにしてください。左側の点がすべて同種（yが同じ値）、右側の点もすべて同種であれば、ジニ係数もエントロピーもどちらも0になります。
回帰
yの値が実数を取るときは、回帰と呼びます(regression)。
回帰の場合には、左側・右側でそれぞれ平均をとり、それぞれ平均との差の2乗の総和を取ればよいです。重みづけは必要ありません。この値が最小となる分け方を選びます。データ個数による重みづけは必要ありません。左側の点のyが全て同じ、右側の点のyが全て同じときは、0になります。
実践での応用
ただ、これらの分け方は絶対なやり方というわけではありません。例えば、こういう応用があります。
- 多クラス分類の性能が悪い時に、2クラス分類に落とす。例えば、4クラスa,b,c,dに分類するときに、「クラスaとクラスa以外（クラスb,c,d）」「クラスbとクラスb以外」「クラスcとクラスc以外」「クラスdとクラスd以外」と、クラスの数4つのランダムフォレストをつくって、評価する。
- 回帰の平均との２乗差の方法を、分類で使う。実際のところ、2クラス分類であれば、回帰のコードを分類で使っても、それなりに良い性能がでることも。
- ジニ係数やエントロピーなどに、クラスごとに重みづけの係数をかける。TopCoderの場合、問題によっては、クラスxをクラスyと間違えたときと、クラスyをクラスxと間違えたときでは、ペナルティスコアが異なることがあります。平たくいえば、許される間違いと、許しがたい間違いがあるということです。こういう場合、分け方の評価関数に重みづけをすることで、良い結果が出せる場合があります。
決定木をたくさんつくって、ランダムフォレストにする。
あとは、ランダムフォレストにするだけです。といっても、単に多くの決定木をつくるだけです。もちろん、決定木をつくる際にランダムな要素があるので、決定木は同じにはなりません。全ての決定木で値を予想してみて、分類のときは多数決で、回帰のときは平均をとるだけです。本当にそれだけなので、実装を見た方が早いと思います。
みなさんも実装したら、ぜひ教えてください。楽しいランダムフォレストライフを！
ランダムフォレストのつかいかた
この記事は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ルールの場合は、メモリ制限もあるので、その制限にひっかからないようにするためにも、木を少しずつ増やす手法は有効です。
データの一部を過学習チェック用にとっておく。
正直ランダムフォレストでは、あまり重要ではありませんが、それでもデータが少ない場合、調整すべき変数が多い機械学習手法の場合は、やはりやったほうが良いと思います。
自分の場合は、以下のような手順で行っています。
- データを90%（クロスバリデーション用）と10%（過学習対策用）にわける
- クロスバリデーション。この90%のデータをさらに2つに分けて、片方を訓練データ、片方をテストデータとする。これで、説明変数を増やしたり、定数の調整をしたりして、良いスコアがでるようにする。これをデータの分け方を変えて、何度も繰り返す。
- 満足がいったら、残り10%の過学習対策用をテストデータとして使う。これで結果がぐっと悪くなったら、過学習が疑われるので(2)からやり直し。（ただ、(2)(3)を何度も繰り返すと、データを分けた意味がないので、注意）
ちなみに、TopCoderの通常のマラソンマッチでも、最終調整時の最適化（＝最後にプログラム上に残った定数を調整することでスコアを稼ぐ）のときも、調整時に使わなかったテストケースを使って実行し、同じぐらいの得点がとれるか確認します。これでガクンと点数が下がったら、過学習を疑います。
/////
以上です。みなさんも、ぜひランダムフォレストを使ってみてください。
明日12/25最終日は、Advent Calendar主催者の tanzakuさん（毎年ありがとうございます）と、いつも衝撃の記事で楽しませてくれるli_sakuさんです。お楽しみに！
TopCoderマラソンマッチのはじめかた
注意：TopCoderマラソンマッチはデザインが大きく変わってしまいました。これから始める方はphocomさんの以下の記事をお勧めします！
qiita.com
TopCoderマラソンマッチは、1-2週間ぐらいの長期間で、正解を出すのではなく、より良い性能のプログラムを書き、高スコアを出すことを競うコンテストです。短時間マッチのSRM（シングルラウンドマッチ）とは違った魅力があります。
ただ、SRMと比べると、参加方法がわかりにくいです。公式の解説はあるのですが、マラソンマッチをやったことがない方向けに、おおまかな参加方法を書きました。
まずTopCoder自体に参加したことのない方は、TopCoderへの登録が必要です。http://www.topcoder.com/の右上の"sign up"から登録を。うまくいかなければTwitterの@nico_shindanninまでご連絡ください。
また、この記事では、マラソンマッチの攻略法については述べません。特別なアルゴリズムの知識はなくても参加できます。ただ、TCO World Finalsに進出した方々による、とても良い記事がありますので、知りたい方はこれらを参考にしてください。
2012-05-02 - TopCoderの学習のお時間 - TopCoder部 by tomerunさん
マラソンマッチの取り組み方 – システム工房コルン by colunさん
マラソンマッチ トップページ
こちらの古い方（http://community.topcoder.com/longcontest/）のトップページを使って説明します。
*1
右側には、現在開催されているコンテストが表示されます。
- discuss : フォーラムです。問題の変更・公式テスターのバグ修正など、とても重要な連絡がされることがあるので、マメにチェックしてください。
- standings : 現在までの仮順位が表示されます。
- Problem : 問題文です。
- Register/Submit : 自分の解答コードを提出します。
- Start Time, End Time : 時間が表示されます。日本標準時ではなく、東部標準時で表示されるので、注意してください。
左側にも、いくつか機能があります。現在無くなっているので、リンクを追加しました。
- Match Archive : 過去のマラソンマッチの結果があります。他の人の提出コードも見れます。
- Practice : 練習ページです。過去のマラソンマッチの問題で練習できます。Practice内でも、standingsで順位をみたり、submitで提出できます。自分の好きなときにできて締切もないので、活用しましょう。
- Queue Status : 現在、結果を待っている人がいるかが分かります。
コンテストの流れ
開催中のコンテストに参加する場合の流れです。Practiceで練習するときには関係ありません。
ルール
- 個人戦です。他の人と相談してはいけません。
- コードは自分で書く必要があります。ただし、問題によっては、特殊ルールで、外部ライブラリ使用可能だったり、他人のコードが使用可能ということもあるので、問題を良く読みましょう。
- コンテスト期間中は、ネタバレ禁止です。コードをさらすのはもちろん、観察・考察をさらす（「こうやると○○点取れそうとか」「このアルゴリズムを試してみよう」）のも禁止です。
- 残念ながら、賞金がもらえるマッチは、年齢制限（18歳以上）があるときが多いです。
スケジュール
スケジュールは以下のようなかんじです。
開始 → コード提出期間（3日～1ヶ月）→ コード提出終了・採点（1日～5日）→ 採点終了・順位確定
- 突然始まるマッチもかなり多いです。TopCoderからのお知らせメールなどはマメにチェックしてください。
- マラソンマッチの期間は1週間が一番多いですが、3日～1ヶ月ぐらいまでと幅広いです。
- コード提出期間内には、standingsのリンクで、仮順位が分かります。スコアを上げて、上の順位を目指しましょう。
- コード提出期間本採点終了後に、順位が確定します。結果に応じてレーティングが上下したり、上位に入れば賞金がもらえたりします。
問題文
多くの問題では、問題文のページと公式テスターのページと、2つのページがあります。どちらも読む必要があります。公式テスターのページへのリンクは、以下のように問題文のページにまぎれてあるので、絶対に見逃さないようにしましょう。
SRMと違って、英語を読む時間はじっくりあるので、ちゃんと読みましょう。特にメモリ制約・制限時間は毎回異なりますし、間違うと0点になるので、必ずチェックしましょう。あと、どうしても問題の意味が分からないなら、以下で述べる公式テスターを先に実行してみるのも良いかもしれません。
スコアの算出方法も書いてあります。他の参加者との相対スコアか、絶対スコアかなど、細かいことまで書いてあります。スコアで順位が決まるので、とても大事です。必ずチェックしてください。
コーディングとオフライン実行環境
問題の解答のコーディングだけではなく、問題の解答をオフライン実行する環境が必要になってきます。一番よくある形は以下のとおりですが、公式テスター/ビジュアライザが無い場合もあります。その場合は問題文ページを良く読んでください。
公式テスターのページは、[A][B][C]を取り扱っています。以下のようなページになっています。
また、[B]と[C]の各言語ごとの例をダウンロードとすると、コードは以下のようになっています。
[A] 公式テスター（ビジュアライザ）
- 公式テスターを使うと、自分のパソコンで、オフラインで自分の解答の得点を確認したり、ビジュアルつきで実行結果が見れます。
- 公式テスターはほぼ常にJavaです。Java runtimeかSDKを予めダウンロードしておいてください。
- まずは公式テスターのページ上部 Executable JAR of the visualizer からダウンロードしてきましょう。
- 実行は、コマンドラインから行います。公式テスターのページの下の方に説明があります。
- 実行する場合は、[B][C]のコードを書いてコンパイルをして、実行ファイルを作る必要があります。その実行ファイルのパスを、コマンドラインの引数として渡します("..\..\Release\marathon_main.exe"の部分）
java -jar Tester.jar -exec "..\..\Release\marathon_main.exe"
- 公式テスターのソースコードもダウンロードできます。もし改良したい場合は、これを書き換え、javacでコンパイルしましょう。
[B] main
- [A]と標準入出力で、データのやりとりをします。
- [B]と[C]はJava,C++,C#,VB,Pythonのどれか好きなものを使えますが、同じ言語を使ってください。
- 上記の各言語ごとの例を丸ごと使えば、問題ないでしょう。書き換えることはないと思います。
難しくはないのですが、１つでも入出力を間違えると、全く動作しないので、公式テスターのページをよく読んで、正確に書いてください。Javaから実行されるコードになるので、間違えたときエラーメッセージもJavaで出るので、どこで間違えたのかデバッグがしづらく、ハマりやすいです。
- C#,Java等他の言語を使用する場合の、実例は http://apps.topcoder.com/forums/?module=Thread&threadID=670892&start=0 に書いてあります。
[C] クラス
- 上記の各言語ごとの例から、はじめましょう。
- Topcoder SRMと同じように、ここに自分の解答コードを書きます。
- よくあるハマる例として、[C]で標準入出力を使ってはいけません。[B]が動かなくなります。つい、デバッグの際にprintfとか書きたくなりますがダメです。何かログを表示させたいなら、標準エラー出力か、ファイル出力を使いましょう。
- また、次に述べる"Submit"で提出するときは、すべてのログ出力コードは消した方がよいです。プログラムの実行時間が遅くなるだけなので。
提出
Submitボタンを押すと、以下の画面に移動します。
まず、画面右上で、言語を選択しましょう。そして、[C]のクラスのみを貼り付けて提出します。[B]は入れてはいけません。（なお、TopCoderでは、提出時に、複数ファイルのコードを提出するということはできません。よって１つのテキストにまとめて提出する必要があります。最大の難点です…。）
提出には"Test Example"と"Submit"の2種類あります。
- Test Example
- 実行するケース数は少ないです。通常のマラソンマッチだと10ケース程度です。
- 1ケースごとの得点・実行時間・ログ出力が見れます。（Standingsページで、自分のExample提出回数のところをクリックします）
- Standingsのスコアには反映されません。
- 1度"Test Example"で提出したら、次の"Test Example"での提出までは15分待たないといけません。
- Submit
- 実行するケース数はやや多めです。通常のマラソンマッチだと100ケース程度です。
- 100ケースの平均得点が見れます。
- Standingsのスコアに反映されます。仮順位も変動します。
- 1度"Submit"で提出したら、次の"Submit"での提出までは2時間待たないといけません。
通常は、まず"Test Example"で提出してみて、オフラインの結果と同じになるかをチェックします。もし良さげであれば"Submit"で同じコードを提出、何かおかしければ修正して"Test Example"でもう1度提出、というふうにすると思います。
提出が受理され、実行が終わると、TopCoderからメールが届きます。1度提出すると、15分間or2時間提出できません。最終的な順位は、一番最後に"Submit"で提出したコード決まります。例えば、残り時間2時間以内で、誤って0点のコードを提出したら、もう再提出はできませんので、0点確定です。締切ギリギリの提出は避けることをお勧めします。
マラソンマッチが終了したら
- メインメニュー左側のMatch Archiveから、最終順位を見ることができます。また、他の参加者のコードは、右のほうにあるSubmissionの数字をクリックすると、過去の提出も含め、全て見ることができます。復習にぜひ活用してください。
- discussのリンクから行けるフォーラムに行きましょう。
- "Post your approach"というスレッドが立っていることがあります。ここで、他の人の解法を知ることができます。非常に勉強になるので、ぜひ見に行ってください。また、自分の解法を書くのも良いと思います。
- 賞金つきマッチでは、たまに「追加マッチ」の情報が載っていることがあります。チェックしましょう。
- 賞金つきマッチで入賞したら、賞金を受け取る手続きをして、もらいましょう。しないと、消えるのでご注意ください。
以上です。さぁ、みんなで楽しいマラソンマッチライフを！
*1:もう１つの新しいトップページ（http://www.topcoder.com/challenges/data/active/?pageIndex=1） は工事中で、結局古い方へリンクがつながってたり、新しい方から提出できないなどの問題も起きているので、古い方の画面を使って説明したいと思います。
