ランダムフォレスト 特徴量の重要度(C++の実装例つき)

はじめに

今回の記事は、alfredplplさんの以下の記事とだいぶかぶっています…。図つきで、とても分かりやすい記事なので、お勧めです。こちらをはじめに読んだほうが良いと思います。alfredplpl.hatenablog.com
alfredplplさんの記事は分類を例にあげてましたので、こちらは回帰を例にあげて説明します。基本的な中身は一緒ですので、比較しながら読んでもらえればと思います。

Rのランダムフォレストの重要度

Rのランダムフォレストには2種類の重要度(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)

結果は以下のようになります。

f:id:shindannin:20150424021604p:plain

  • 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個の特徴量を持つとします。

以下の処理は、ランダムフォレストの決定木1本1本に対して行います。

  1. ランダムフォレストで、決定木を作るときに訓練に使われなかったデータサンプル(ブートストラップサンプリングで外れたデータ)を使います。これをOOBデータと呼びます(Out-of-bag(OOB) data、OOB examplesとも)。
  2. まずOOBエラーを求めます。OOBデータのXを決定木に入力すると、予測した結果y'を求められます。y'と目標変数yがどれだけズレてるかがOOBエラーです。回帰のときは、MSE(mean square error、平均二乗誤差)をOOBエラーとします。つまりΣ(yi-yi')^2 / kとなります(kはOOBデータのデータ個数)。
  3. m個の特徴量それぞれに対して重要度を求めます。単純にm回ループして、ループ変数を特徴量fとして、以下のことをします。
    1. 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. シャッフルしたデータを使って、(2)と同じようにOOBエラーを求めます。特徴量fだけシャッフルしたので、特徴量fが重要なのであれば、重要なデータがシャッフルでおかしくなったわけなので予測が悪くなるはずです。予測が悪化した値、つまり、(シャッフルしたデータのOOBエラー) - (元のOOBエラー) を重要度IncMSEとします。

最後に、全ての決定木の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の変わりに使うといったこともできるでしょう。
  • ただ「重要度を低い特徴量を削る」と簡単に書きましたが、貪欲に1番重要度が低い特徴量を削っていけば良いというものでもなく、とても難しいです*3。特徴量間に強い関係があれば、特徴例をけずるたびに、重要度も大きく変わってきます。良い方法があったら(というか研究されていると思いますが)、ぜひ教えてもらえるとうれしいです。一応、自分のアイディアレベルのネタとしては、
    • (2)(3)であれば、複数の特徴量をシャッフルする手はあるでしょう。ただ、(OOBデータ個数)*(木の本数)*(特徴量の数 ^ シャッフル個数)*(特徴量1つあたりのシャッフル予測の回数 nPerm)回となるので、特徴量が多いときは、シャッフル個数2個にするのすら遅すぎて難しいかもしれません。
    • 探索枝仮り・焼きなまし法・ビームサーチといった最適化手法で削っていく方法もあるでしょう。
    • 特徴量を1つ削ったとき、他の重要度がどう変化するかで、どの特徴量間に強い関係があるかというグラフのようなものを作れば、最適化手法を使っていく上で役に立つかもしれません。例えば、「特徴量はx1,x2は片方を削ると、もう片方の重要度が大きく下がるので、たぶんペアで意味がある特徴量だ。焼きなまし法を試すときは、この2つはまとめて追加したり削除したりするようにしよう。」といったことはできそうな気がします。

ランダムフォレストのパラメータ調整がひどいのに気付くきっかけ

最初にあげた図では、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:あくまで自分のイメージですが、「特徴量の追加削除」を近傍、「重要度」を関数の傾きと置き換えると、近傍にいっただけで関数の傾きが大きく変化したりする関数を最適化しないといけないようなものなので、やばいかんじしかしません…

ボツネタ集(だいたいランダムフォレスト)

どうでもよいまえがき
今回の記事を最後に、機械学習関係の記事は、しばらくお休みにします!

  • 我流すぎて、機械学習の知識が不足していて、記事を書くのに妙に時間がかかる。
  • 最近、機械学習マッチで結果を出してないので、その中で記事を書いても、自分の中で説得力がいまいち。

というわけでしばらくの間は、機械学習について、以下のことに専念します。

  • 本とか論文とか読んでインプット
  • 機械学習マッチで結果を出す

ただ、記事を書こうと思ってたボツネタがあるので、勢いで書きました。雑です。メモ書き程度だと思ってもらえば。

それではスタートじゃ!!!!

ボツネタ1 : ID分解

世の中のIDというものは、複数の情報を持っていることがあります。これを別の特徴量として追加します。数学も機械も関係ない、セコいテクニックですが、意外と実戦的かもしれません。

まず、データを眺めてください。
f:id:shindannin:20150425163540p:plain

自分だったら、x0のidの赤で囲われた桁を、別な特徴量として追加します。紫で囲った部分も念のため追加するかもしれません。なぜでしょう?
f:id:shindannin:20150425163552p:plain

なぜかというと、いろいろと法則に気づくからです。

  • 紫の最初の5桁は、startdayが同じとき、常に同じ値になります。日時にかかわる値だと推測できます。ただ、この5桁とstartdayの大小関係違うので、一応特徴量として追加します。
  • 赤の桁は、完全に独立した値です。0~2の値しかとりません。とてもあやしいので、特徴量として追加します。
  • 下2桁と3桁は常に31なので不要です。
  • 下1桁はcyclesと常に同じ値なので不要です

f:id:shindannin:20150425163601p:plain

まぁ、ただ注意点は、

  • 分解前の元のIDを削るのは、特に慎重になったほうがいいです。気づいてない重要な情報があるかもしれないので。とりあえずは分解したのを追加するだけにとどめておきましょう。
  • つねに同じ値というのも、必ず全部のデータで常に同じ値になってるか確認しましょう。まれに違うことがあって、それが重要度の高い特徴量になってたら。大惨事です。

データを数値でも眺めるのは本当に重要です。機械学習する前に、必ず見るようにしましょう。まぁ、こういうのすら自動化するのが最高ですけどね。

ボツネタ2 : ランダムフォレスト実装例の簡単なバリエーションについて

過去の記事で、ランダムフォレストといってもバリエーションがいろいろあるといって逃げっぱなしなので、「ちょっとは説明しないと…」という罪悪感をかんじていました。

  • 効果 : ★が大きいほど、効果が高そう…といいたいですが、完全に自分の経験上なので、信ぴょう性はあまりないです。
  • 謎度 : ★が大きいほど、めったにみかけないもので、謎度を高くしてます。

C++の実装例を使って、ちょっと説明します。改良はみんなの宿題!

ルートバッグ1.5倍

効果 ★
謎度 ★★★★★
TopCoderのPsyhoさんのコードをみて知ったテクの中でも、もっとも謎なものです。

ブートストラッピングでは、ルートバッグのサイズは元のデータは0.632倍が使われています。
bootstrap - What is the .632+ rule in bootstrapping? - Cross Validated
実装例のrootBagSizeRatioの部分です。
115行目

const int rootBagSize = static_cast<int>(numData * rootBagSizeRatio); // ルートに入るデータの数
root.bags.resize(rootBagSize);

#if INCMSE
vector <int> freq(numData); // データ番号別の、ルートに選ばれた個数
#endif // INCMSE

// ブートストラップサンプリング
for (int i = 0; i < rootBagSize; i++)
{
    // ここで、同じIDが選ばれる可能性があるが、問題なし。
    int row = randxor.random() % numData;
    root.bags[i] = row;
#if INCMSE
    freq[row]++;
#endif // INCMSE
}

rootBagSizeRatioの部分は、調整するにしても、普通は1以下の値を入れようと考えますが、Psyhoさんはここで1.5倍のように、1を超える値を入れてくることもあります。いったいどういう意味があるのか分かりませんが…。
なお、

  • 1.5倍を入れるようにした場合でも、OOBデータもわずかに残ります。重複も許してるので。
  • このままだと計算時間も長くなるので、防ぐために特徴量毎にweightという変数を用意し、何回でてきたかをとっておけば、計算時間は長くなりません。ソースコードの改良は読者の宿題!!

領域を分けるとき、全部の境界を試す

効果 ★★★
謎度

Rのランダムフォレスト実装であるので、そちらが標準だと思います。

ある特徴量の、全部の境界を試してます。自分の実装例では以下のように、numRandomPositions個しか試していません。
224行目

for (int j = 0; j<numRandomPositions; j++)	 // どの位置で分けるか
{
    const int positionID = randxor.random() % SZ(node.bags);
    const FeatureType splitValue = features[node.bags[positionID]][featureID];

ただ、多く分けるほうが必ず良いというわけでもありません。特に、少ない特徴量で似たような木ができる現象の要因になることも。計算時間も長いです。

上記の実装を全部の境界で切るようにしたいなら、

for (int j = 0; j<SZ(node.bags); j++)	 // どの位置で分けるか
{
    const int positionID = j;

とすれば、機能としてはRの実装と一緒になりますが、速度としてはお話にならないです、ダメ!前回の日記で述べた式

  {Σ[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|                    ... 足し算

これで評価するようにすれば、xが小さいほうから高速に全ての分け方を試せます(予めqsortを使います)。まぁ、説明不足なので、本家のソースコードregTree.cの関数findBestSplitを熟読して、実装しましょう。読者の宿題!
なお、後述する平均2乗誤差、3乗誤差や1.5乗誤差を変えるというのをやると、以上の数式展開が使えず、速くできません。

領域を分けるとき、任意の場所で分けられるようにする。

効果 ???
謎度 ★★★
一度も試したことはありません。上記の例ではデータのある場所で分けていますが、現在のノードに入ってるデータの、特徴量xの最大と最小を求めておき、(max-min)*rand + min の位置で切るといった感じの実装で、任意の場所で分けることができます。これをやるとxの値の差で選ばれる確率が変わるようになるので、いろいろと問題が起きそうな気もしますが…。

領域を分けるとき、マージン最大化っぽいことをする

効果 ★★
謎度
過去の日記で、yowaさんからコメントをいただきました。Rの実装でもやっているので、謎ではありません。
ランダムフォレストのつくりかた(C++の実装例つき) - じじいのプログラミング

おそらく日記をみて、「せっかく赤色と青色の領域を分けるのに、なぜ、わざわざギリギリの点上で分けるのか。中間で分けた方がいいのではないか」と思った人もいるのではないかと思います。それです。

改良前
278行目

node.value = bestValue;

改良後はこんなかんじになるでしょうか。

FeatureType nextValue = -BIG;

for (int i = 0; i < SZ(node.bags); ++i)
{
    if( features[node.bags[i]][bestFeatureID] < bestValue)
    {
        nextValue = max(nextValue, features[node.bags[i]][bestFeatureID]);
    }
}
node.value = (bestValue + nextValue) / 2.0;
if (!(node.value > nextValue)) node.value = bestValue;

あまり効果があった経験はないのですが、計算のオーダーが増えるわけでもないので、いれていいと思います。

木の深さに応じ、特徴量を選ぶ数numRandomFeaturesを変える

効果 ★★★
謎度 ★★★

以下のnumRandomFeaturesは、通常は固定ですが、これを木の深さに応じて変えます。

198行目

for (int i = 0; i<numRandomFeatures; i++)
{
    // x0,x1,x2...の、どの軸で分けるかを決める
    int featureID = randxor.random() % numFeatures;

実装は読者の宿題!まぁ、これは簡単でしょう。木の深さを表す変数をノードにもたせておき、numRandomFeatures[depth]みたいにすればよろしい。

これは割と効果があります。特に、後述する似た木ができる現象を避けるのに使えます。つまり、木の浅いところではnumRandomFeaturesの値を少なく、深いところではnumRandomFeaturesを大きめにすると良いです。

MSE以外の誤差を使用する

効果 ★★
謎度 ★★★

311行目

double lossFunction(double y, double mean) const
{
    return (y - mean)*(y - mean);
}

ここを、絶対値の3乗誤差、絶対値の1.5乗誤差、絶対値などに置き換える方法です。

ボツネタ3 : ランダムフォレストで似た木ばかりができると予測性能が落ちる

ランダムフォレストで、同じような木がたくさんできてしまうと、極端に予測性能が落ちることがあります。以下のような条件のとき要注意です。

  • 特徴量が少ない(10個以下)
  • 特徴量に比べて、ノード分割の際に選ぶ数numRandomFeatures(RのmTry)が多い。(目安は、回帰 特徴量の数/3、分類 特徴量の数^0.5)
  • 切る場所を試す数numRandomPositionsが大きい(Rだと全部で切るので、多い)

木をたくさん増やすことである程度解消できますが、限度があります。ちゃんとパラメータを調整して、避けましょう。

以下の図は、特徴量が7個しかないケースで、予測性能が極端に落ちたときの、決定木10本をビジュアライズしたものです。

  • 上側がルートです。
  • 帯の長さが、ノードの属するデータの個数に当たります。
  • 帯の色が、ノードをどの特徴量xで分割したかにあたります。計7色。

これを見ると、一見カラフルで、いろんな木ができてますが、上部の色はだいたい、茶色か水色か黄緑しか来ていないことが分かります。
f:id:shindannin:20150425190854p:plain

念のため、上記の画像を出力するコードも貼っておきます。htmlで出力する手抜きなやつですが…。

    void visualize(int id)
    {
        char path[1001];
        sprintf(path,"../visual/VisualTree.html");
        FILE *fp = fopen(path, id==0 ? "w" : "a");

        vector <string> colors = 
        {
            "Red",
            "Maroon",
            "Yellow",
            "Olive",
            "Lime",
            "Aqua",
            "Teal",
            "Blue",
            "Green",
        };

        if (fp)
        {
            fprintf(fp,"<canvas id=\"sample%d\" width=\"15000\" height=\"300\">\n",id);
            fprintf(fp,"<p></p>\n");
            fprintf(fp,"</canvas>\n");
            fprintf(fp,"<script>\n");
            fprintf(fp,"var canvas = document.getElementById('sample%d');\n",id);
            fprintf(fp,"var context = canvas.getContext('2d');\n");

            float xRatio = 0.5f;

            queue < pair <int, int> > q; // ノード番号, 左座標
            q.push(make_pair(0,0));
            while(!q.empty())
            {
                pair <int,int> now = q.front();
                q.pop();

                const TreeNode& nd = m_nodes[now.first];


                fprintf(fp,"context.fillStyle = \"%s\";\n", colors[(nd.featureID+SZ(colors))%SZ(colors)].c_str());
                fprintf(fp,"context.fillRect(%d,%d,%d,%d);\n", now.second, 10*nd.level, (int)(SZ(nd.bags)*xRatio), 10);

                if(!nd.leaf)
                {
                    q.push(make_pair(nd.left,now.second));
                    q.push(make_pair(nd.right,now.second+(int)(SZ(m_nodes[nd.left].bags)*xRatio)));
                }
            }
            fprintf(fp,"</script>\n");
            fclose(fp);
        }
    }

ボツネタにすらまとめられなかったボツネタ

カテゴリカル変数ごとに、他の特徴量xや目的変数の統計データを求めて、新たな特徴量として追加する。

機械学習は、基本不等式で分けるので、カテゴリカル変数(列挙型)はやっかい。そのままは使えない。ただ集計して特徴量を足すのに使いやすい。カテゴリカル変数x1をだとしたら、x1の値ごとに、他の特徴量x2,x3..やyを集計して(足す・割る・割合を求める・最大・最小)、新たな特徴量を追加する話。なぜボツにしたかというと、
ランダムフォレストのつかいかた - じじいのプログラミング
の「同種のデータとのかかわりを表す変数を追加する」とネタがかぶってるから。ただ、あの記事ではカテゴリカル変数とは言わなかったので、改めて書くか迷った。ただ非常に効果があるテクニックなので、みなさん使ってほしいです。

ブースティングのC++の実装例

C++の実装例で決定木の部分は実装してるので、てきとーなブースティング(木0の予測外れ分を木1のyとツッコむ)というのを実装するのは割と簡単。ただ、まじめなブースティングは、木の重みづけの部分とかも含めて理論になってるっぽく、そこは理解してないので、やめた。また、実戦で使ったことがないのも不安なので、やめた。







以上です。では、さようなら~。ほっほー。