verum ipsum factum

sudillap's blog

「金塊か、キノコ料理か」(外れ値検出問題)を解く[ランダムフォレスト]

一般的に、ランダムフォレストは分類や回帰問題に用いられますが、実はデータ間の近接度も求めることができます。この近接度から外れ度(後述)を計算できるので、この値が大きいデータを外れ値とみなすことができます。

Rスクリプトとその結果は次のとおりです。87番目のデータが外れ値になります。なお、実行ごとに結果が異なるため次のスクリプトでは20回実行しています。
下の図は外れ度のグラフ(一例)です。

library(randomForest)
outliers <- c()
for(i in 1:20){
  gold.rf <- randomForest(gold, proximity=TRUE)
  outliers <- c(outliers,order(outlier(gold.rf),decreasing=TRUE)[1:3])
}
table(outliers)

outliers
16 17 18 73 79 87 
 1  1 15 17  6 20 

f:id:sudillap:20130325194436p:plain

アルゴリズム概要

$prox(n,k)$をデータ$n$と$k$の近接度、$cl(k)$をデータ$k$が属するクラス、$N$をデータ数とします。このときデータ$n$の外れ度(outlier measure)は次の式で定義されます(詳細は参考文献参照)。
$$
\frac{O(n)-\text{median}(O(n))}{||O(n)-\text{median}(O(n))||}
$$
ここで、$O(n)$は
$$
O(n)=\frac{N}{\sum_{cl(k)=j}prox(n, k)^2}
$$
です。

この外れ度が大きいデータが外れ値となります。


参考文献:

Leo Breiman and Adele Cutler,