RANSAC

いくつか回帰分析の亜種について紹介しきましたが、データを扱っているとノイズが多く含まれるデータに遭遇することがあります。ノイズをうまく避ける手法として、今回はランダムサンプリングに基づくRANSAC(RANdom SAmple Consensus)について書きます。傾きの中央値を求めるPassing-Bablockなどとは違って、サンプリング結果と残サンプルの適合性からそもそも回帰に用いるデータを選別するアイデアです。

RANSACのアルゴリズム

アルゴリズムの概要は以下の通りです。外れ値をアウトライア(outlier)、そうでないものをインライア(inlier)と呼びます。

1. データ集合から繰り返しを許さず規定回数サンプリング（非復元抽出）
2. サンプリングデータに対して回帰分析などでモデル作成
3. サンプリングされなかったデータに対して、誤差が閾値以下のデータ（inlier）を集めてカウント、集められたデータはconsensus setと呼ぶ
4. 2,3を規定回数繰り返して最もカウント数が多いモデルを選択
5. 最後に全てのconsensus setデータを使用してモデル更新

RANSACはデータをどのように使ってモデル作成するかの枠組みの話なので、回帰分析に限定するものではないです。モデル作成時にPassing-BablockやTheil's Incomplete methodなどを適用することも可能ですし、高次の多項式近似を適用することも可能です。

Iteration回数について

何回繰り返す（Iteration）か、についても目安があるようです。

インライアを選ぶ確率を[math] w = \frac{N_{inlier}}{N} [/math]とした場合、[math]n[/math]個選んで全てインライアからのデータである確率は[math]w^n[/math]となります。

上記から少なくとも一つアウトライアを選ぶ確率は[math]1-w^n[/math]。[math] k [/math]回のサンプリングで全てアウトライアを選ぶ確率は[math] (1-w^n)^k [/math]。

[math] k [/math]回のサンプリングで一つもアウトライアが選ばれない確率は[math] 1-(1-w^n)^k [/math]。これを[math] p [/math]と置くと、

[math] p=1-(1-w^n)^k [/math]

[math] (1-w^n)^k =1-p [/math]

対数をとると

[math] k log (1-w^n)=log(1-p) [/math]

[math] k=\frac{log(1-p)}{log (1-w^n)} [/math]

となります。

ここで少しケーススタディをしてみます。アウトライアが50%入っているデータ（[math]w=0.5[/math]）について、[math] k [/math]回サンプリングのアウトライア混入率[math] p [/math]を0.5~0.0001、サンプリング個数[math]n[/math]を2~30とした時、アウトライアが含まれないサンプリングが存在するために必要なサンプリング回数[math] k [/math]は下記のようになります。

確率計算からもわかる通り、サンプリング個数が多いとアウトライア混入率が激増するので、私見ですが[math]n=[/math]10~20が現実的に思われます。

今度はサンプリング個数[math]n=10[/math]について、[math] k [/math]回サンプリングのアウトライア混入率Pを0.5~0.0001、アウトライア混入率（[math]w=[/math]0.5~0.01）とした時、アウトライアが含まれないサンプリングが存在するために必要なサンプリング回数[math] k [/math]は下記のようになります。

アウトライアが多すぎる（[math] p [/math]が大きいと）と、この場合も必要なサンプリング回数が激増します。

サンプリング個数[math]n=2[/math]の場合はこのようになります。

アウトライアが多すぎるデータについては、サンプリング個数[math]n[/math]を極力抑える必要があるので、最終的にはPassing-Bablockのようなアプローチに漸近していくと思われます。

適用例

RANSACといくつかの回帰分析例をノイズの多いデータに適用してみます。

下図ではおそらく単調増加な関係性がありそうですが、無相関なノイズが多く判然としません(50%のデータは無相関なデータです)。/p>

このデータに通常の単回帰(OLS)を適用すると下記のようになります。ノイズが多いため、なんとなく相関がありそうな領域とズレた場所に回帰直線が引かれています。

本稿で述べたRANSACを適用した結果は以下の通りです。ノイズ影響を受けず、良い感じで線を引いてくれます。

ちなみにPassing-Bablockを適用すると下記の通りです。ノイズの割合が多いためか、よくわからないところに線を引いています。

Theil's Incomplete methodの場合は下記のようになり、OLSより多少良い程度です。

終わりに

RANSACを紹介しました。少しマニアックですが、実は異常値の多い実験データを扱ったりする場合非常に有用です。マニュアルで外れ値を取り除いている方も多いのではないでしょうか？詳しい内容は知らずとも、こういったツールが存在することを頭の片隅に入れておくことは重要です。問題に直面した場合に思い出すことが出来れば、データ処理にかかる時間を大幅削減することが可能です。

RANSACはこちらでも実装しています。モデルは線形単回帰です。遊んでみてください。