ボツネタ集（だいたいランダムフォレスト）
どうでもよいまえがき
今回の記事を最後に、機械学習関係の記事は、しばらくお休みにします！
- 我流すぎて、機械学習の知識が不足していて、記事を書くのに妙に時間がかかる。
- 最近、機械学習マッチで結果を出してないので、その中で記事を書いても、自分の中で説得力がいまいち。
というわけでしばらくの間は、機械学習について、以下のことに専念します。
- 本とか論文とか読んでインプット
- 機械学習マッチで結果を出す
ただ、記事を書こうと思ってたボツネタがあるので、勢いで書きました。雑です。メモ書き程度だと思ってもらえば。
それではスタートじゃ！！！！
ボツネタ1 : ID分解
世の中のIDというものは、複数の情報を持っていることがあります。これを別の特徴量として追加します。数学も機械も関係ない、セコいテクニックですが、意外と実戦的かもしれません。
まず、データを眺めてください。
自分だったら、x0のidの赤で囲われた桁を、別な特徴量として追加します。紫で囲った部分も念のため追加するかもしれません。なぜでしょう？
なぜかというと、いろいろと法則に気づくからです。
- 紫の最初の5桁は、startdayが同じとき、常に同じ値になります。日時にかかわる値だと推測できます。ただ、この5桁とstartdayの大小関係違うので、一応特徴量として追加します。
- 赤の桁は、完全に独立した値です。0～2の値しかとりません。とてもあやしいので、特徴量として追加します。
- 下2桁と3桁は常に31なので不要です。
- 下1桁はcyclesと常に同じ値なので不要です
まぁ、ただ注意点は、
- 分解前の元の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色。
これを見ると、一見カラフルで、いろんな木ができてますが、上部の色はだいたい、茶色か水色か黄緑しか来ていないことが分かります。
念のため、上記の画像を出力するコードも貼っておきます。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とツッコむ）というのを実装するのは割と簡単。ただ、まじめなブースティングは、木の重みづけの部分とかも含めて理論になってるっぽく、そこは理解してないので、やめた。また、実戦で使ったことがないのも不安なので、やめた。
以上です。では、さようなら～。ほっほー。
