rubyでRANSAC
研究で必要になったから調べてみた
観測したデータから最小二乗法などでモデルを推定する際に、観測したデータに外れ値が混じっていた場合、推定したモデルは外れ値に引っ張られてしまいます。そこで、RANSACアルゴリズムを利用することで、外れ値を無視したモデルの推定を行うことが出来ます
RANSACアルゴリズム
1.観測データ群からランダムに幾つかのデータを取り出す
2.取り出したデータを用いてモデルを推定
3.推定したモデルに対して、観測データ群を適用し、モデルを評価する
4.1~3を複数回行い、一番評価が高いモデルを採用
意外とシンプルなアルゴリズムです。
実験
今回は、直線のモデルを最小二乗法で推定します。
直線のモデルなんで、
のaとbの部分を推定します。
今回は正解のモデルを
っぽい直線としました。
正解データは
(1- rand() / 10) * x
また外れ値は
rand(0.0..5.0) * x
として生成しました。
ちなみにxは1から100までの整数です。
グラフの描画はgnuplotなるライブラリを使いました。
まずは外れ値なしの最小二乗法から
なかなかよい感じ
続いて、外れ値ありの最小二乗法
めっちゃ外れ値に引っ張られてます。
最後にRANSAC使った場合です。
きれいに外れ値を無視してくれました。
RANSACは簡単に実装できて、強力なんですが、
複数回、モデルの推定を行って、それを更に観測データ群に適応させるので、
計算量がめっちゃ大きい感じがします。
実際にRANSACを使う場合には工夫が必要かもしれません
ちなみに今回書いたコードはこんな感じです。