rubyでRANSAC

研究で必要になったから調べてみた

観測したデータから最小二乗法などでモデルを推定する際に、観測したデータに外れ値が混じっていた場合、推定したモデルは外れ値に引っ張られてしまいます。そこで、RANSACアルゴリズムを利用することで、外れ値を無視したモデルの推定を行うことが出来ます

RANSACアルゴリズム

1.観測データ群からランダムに幾つかのデータを取り出す
2.取り出したデータを用いてモデルを推定
3.推定したモデルに対して、観測データ群を適用し、モデルを評価する
4.1~3を複数回行い、一番評価が高いモデルを採用

意外とシンプルなアルゴリズムです。

実験

今回は、直線のモデルを最小二乗法で推定します。
直線のモデルなんで、
{Y = aX + b}
のaとbの部分を推定します。

今回は正解のモデルを
{Y = X}
っぽい直線としました。
正解データは

(1- rand() / 10) * x

また外れ値は

rand(0.0..5.0) * x

として生成しました。

ちなみにxは1から100までの整数です。
グラフの描画はgnuplotなるライブラリを使いました。



まずは外れ値なしの最小二乗法から

f:id:ogidow:20151030230915j:plain

なかなかよい感じ

続いて、外れ値ありの最小二乗法

f:id:ogidow:20151030231407j:plain

めっちゃ外れ値に引っ張られてます。

最後にRANSAC使った場合です。

f:id:ogidow:20151030231604j:plain

きれいに外れ値を無視してくれました。


RANSACは簡単に実装できて、強力なんですが、
複数回、モデルの推定を行って、それを更に観測データ群に適応させるので、
計算量がめっちゃ大きい感じがします。

実際にRANSACを使う場合には工夫が必要かもしれません


ちなみに今回書いたコードはこんな感じです。