高次元データの外れ値検出

データマイニング ELKI

高次元データの外れ値検出についてのメモ．

高次元データと次元の呪い

次元が大きくなるほど，点の間の距離は均一になっていく．
例として，2000個の点の各座標を一様乱数で発生させて，次元を変えながら点の間の距離の平均値，最大値，最小値，平均値±1σ，平均値±2σをみてみよう．

library(ggplot2)
set.seed(123)

# 次元のリスト
dims <- c(1:9, 10*(1:9), 100*(1:10))
# 算出する統計量
stats <- c("min", "mean-sd", "mean", "mean+sd", "max")
# 発生させる点の個数
N <- 2000 

# 各次元に対して算出した統計量を格納する行列
ans <- matrix(NA, length(dims), length(stats), dimnames=list(dims, stats))

# 各次元に対して発生させた点間の距離の統計量を算出する
for (d in dims) {
message("d=", d)
　# 点を発生させる(N * d の行列)
　x <- replicate(d, runif(N))
　# 点間の距離を算出する
　x.dist <- as.matrix(dist(x))
　xd <- x.dist[upper.tri(x.dist)]
　# 点間の距離の統計量を算出する
　xd.min <- min(xd, na.rm=T)
　xd.mean <- mean(xd, na.rm=T)
　xd.max <- max(xd, na.rm=T)
　xd.sd <- sd(xd, na.rm=T)
　# 統計量を格納する(次元間を比較できるようにsqrt(dim)で割る)
　ans[as.character(d), ] <- 
　　c(xd.min, xd.mean-xd.sd, xd.mean, xd.mean+xd.sd, xd.max)/sqrt(d)
}

# 次元と統計量の関係をプロットする
ans.m <- melt(ans)
ans.m$X2 <- factor(ans.m$X2, levels=rev(stats))
p <- ggplot(data=ans.m, aes(x=Var1, y=value, group=Var2, colour=Var2)) + 
　　　geom_point() + geom_line() + 
　　　theme_bw() %+replace% 
　　　theme(legend.position="bottom", legend.direction="horizontal", 
　　　　　　legend.title=element_blank()) + 
　　　xlab("dimension") + ylab("normalized distance")
print(p)



確かに次元が高くなるほど点の間の距離は近づいていることが分かる．

この現象は次元の呪い(curse of dimension)に起因しており，高次元において近傍や点の乖離といった概念が意味をなさなくなってしまうことを物語っている．低次元のデータに対しては有効であったデータ間の距離や密度などに基づく外れ値検出が，高次元においては有効ではなくなってしまうのである．

高次元データの外れ値検出のアルゴリズム

このような問題点を解決するために，非常に多くの高次元データの外れ値検出アルゴリズムが提案されている．ここでは，Aggrarwalの"Outlier Analysis"，および，Zimek,Schubert,Kriegelによるtutorialを参考に，代表的（と思われる）アルゴリズムをいくつか選び，そのアイディアについて整理する*1．

方針 アルゴリズム アイディア
角度に基づく方法 ABOD
(H.-P.Kriegel, M.Schubert, and A.Zimek, 2008)		 外れ値は，自身と他の2点のデータのなす角度の分散が小さい*2．
グリッドによる方法 Aggarwal and Yu
(Aggarwal and Yu, 2001)		 空間をグリッドで分割してデータの個数が少ないグリッドに属する点を外れ値とする．
距離に基づく方法(部分空間への射影) SOD
(H.-P.Kriegel, P.Kroger, E.Schubert, and A.Zimek, 2009)		 各点に対して，k-近傍点の分散が最も小さくなる超平面との距離を外れ値スコアとする．
ランダムな部分空間の選択 Feature Bagging
(C.Sutton, M.Sindelar, and A.McCallum, 2005)		 部分空間をランダムに選択する試行を複数回繰り返し，各試行における外れ値スコアの平均値を算出する．
コントラストが高い部分空間の選択 HiCS
(F.Keller, E.Muller, and K.Bohm, 2012)		 ある座標の周辺確率密度関数と，他の座標の条件付き確率密度関数が大きく異なる(コントラストが高い)点を外れ値として検出する．このような部分空間を探索し，外れ値スコアを算出する．部分空間の探索と外れ値スコアの算出を完全に分離している点に特徴がある．
任意の方向の部分空間への射影 COP
(H.-P.Kriegel, P.Kroger, E.Schubert, and A.Zimek, 2012)		 各点のk-近傍点に対してロバスト主成分分析を実行しマハラノビス距離の分布を推定．これにより，座標軸方向だけでなく，任意の方向の部分空間への射影により外れ値を検出することが可能になる．

ELKIで外れ値検出

ELKIは，インデクス構造を用いたデータマイニングの開発・評価ツール．ルートヴィヒ・マクシミリアン大学ミュンヘンのKriegel教授を中心に開発が進められている．クラスタリング，外れ値検出のアルゴリズム，インデクスを用いたデータ構造がJavaで実装されている．

ELKIには，上記のアルゴリズムも含め，高次元データの外れ値検出のアルゴリズムが複数実装されている．Javaがインストールされた環境であれば，リリースページからjarファイルをダウンロードしてくるだけですぐに使用できる．現時点での最新版のバージョンは0.6．

以下，HiCSを例に，コマンドラインから実行し結果を確認する方法を示す．

HiCSは，以下のコマンドにより実行できる．ここでは，ELKIのウェブページで提供されているmouseデータセットを使用する*3．

$ java -jar elki.jar KDDCLIApplication -algorithm outlier.meta.HiCS -dbc.in mouse.csv -out output/meta/HiCS/mouse -lof.k 10 -hics.limit 10

algorithmオプションにHiCSを，dbc.inオプションに入力データのファイル名，outオプションに結果を格納するディレクトリを指定している．それ以降は，HiCSのパラメータである．

入力データのmouseデータセットは，以下のように「x座標 y座標 データが属するカテゴリ」の3つのフィールドからなる人工データである*4．

0.45660137634625386 0.43280640922410835 Head
0.6113784672224188 0.5286245988894975 Head
0.45029897412145387 0.7116061205092745 Head
0.6390150501606866 0.46074398219372076 Head
0.6289567839292338 0.32346951478531516 Head

HiCSを適用して外れ値スコアを算出するだけならば，3フィールド目の「データが属するカテゴリ」は必ずしも必要ではなく，各点の座標の値をスペース区切りで指定すれば良い．
カテゴリは"Head", "Ear_left", "Ear_right", "Noise"の4種類あり，"Noise"のカテゴリが割り当てられた点が，外れ値を意図して生成されていると思われる．

指定できるHiCSのパラメータと内容は以下の通りである．

パラメータ デフォルト値 内容
hics.m 50 モンテカルロシミュレーションの試行回数
hics.alpha 0.1 サンプリングパラメータ \alpha
hics.algo lof.LOF 外れ値スコアを算出するために使用するアルゴリズム
hics.test KolmogorovSmirnovTest 用いる統計的検定
hics.limit 100 ?
hics.seed null 乱数種
lof.k なし(指定必須) LOFを実行する際の近傍点の個数

上記のコマンドを実行した結果，出力先のディレクトリには以下のファイルが生成されている．

$ ls output/meta/HiCS/mouse
HiCS-outlier_order.txt  head.txt               pr-curve.txt        settings.txt
ear_left.txt            noise.txt              precision-at-k.txt
ear_right.txt           outlier-histogram.txt  roc-curve.txt

これらのファイルは，以下の5種類に分けることができる．

  • 外れ値スコアのランキング (HiCS-outlier_order.txt)
  • カテゴリごとの外れ値スコアのランキング (ear_left.txt / ear_right.txt / head.txt / noise.txt)
  • 外れ値検出の精度評価結果 (pr-curve.txt / precision-at-k.txt / roc-curve.txt)
  • 外れ値スコアのヒストグラムのテーブル (outlier-histogram.txt)
  • 外れ値検出実行時の条件 (settings.txt)

入力データにカテゴリが指定されなかった場合は，「カテゴリごとの外れ値スコアのランキング」，「外れ値検出の精度評価結果」，「外れ値スコアのヒストグラムのテーブル」の各ファイルは出力されない*5．

中核となるのは，1番目の外れ値スコアのランキングである．このランキングは，以下のように「ID=XXX X座標 Y座標 カテゴリ HiCS-outlier=外れ値スコア」というフォーマットで出力されている．外れ値スコアの上位10件は，すべてNoiseというカテゴリが付与された点であることが分かる．

$ head -n 10 output/meta/HiCS/mouse/HiCS-outlier_order.txt 
ID=493 0.040554927744786196 0.5072400792452862 Noise HiCS-outlier=4.990745232367167
ID=494 0.8351619113805846 0.13894038814840037 Noise HiCS-outlier=4.54623153237365
ID=499 0.9160298083819269 0.523390593285425 Noise HiCS-outlier=2.9713913373033023
ID=496 0.15150612475114178 0.8765856628207388 Noise HiCS-outlier=2.676335528483546
ID=498 0.8620825903226392 0.5918053842487218 Noise HiCS-outlier=2.4841215287717135
ID=492 0.7500676018742642 0.897027660749859 Noise HiCS-outlier=2.478742342093093
ID=500 0.42732547274373656 0.8337665738193867 Noise HiCS-outlier=2.3224593385443324
ID=495 0.17474033164278335 0.3636861115238198 Noise HiCS-outlier=2.2063046357373977
ID=497 0.8603082847506063 0.6338333996208041 Noise HiCS-outlier=2.0582792064801536
ID=491 0.290949977617754 0.8557666871174766 Noise HiCS-outlier=1.7418386083077688

このファイルをRに読み込んで，点の座標とカテゴリ，外れ値スコアを表示させてみよう．

library(ggplot2)
z <- read.csv("output/meta/HiCS/mouse/HiCS-outlier_order.txt", sep=" ", header=FALSE, colClasses=c("character", "numeric", "numeric", "factor", "character"))
z$V5 <- as.numeric(gsub("HiCS-outlier=", "", z$V5))
colnames(z) <- c("ID", "x", "y", "category", "rank")
p <- ggplot(data=z, aes(x=x, y=y, group=category, colour=category, size=rank)) + geom_point()
print(p)



カテゴリが"Head", "Ear_left", "Ear_right"のクラスタの外側に，"Noise"とカテゴリが付与された点で外れ値スコアが大きくなっていることが確認できる．

他のアルゴリズムも，algorithmオプションの引数を変更することにより実行できる．アルゴリズムと引数の対応は下表の通りである．

アルゴリズム algorithmオプションの引数
ABOD outlier.ABOD/outlier.FastABOD/outlier.LBABOD
Aggarwal and Yu outlier.AggarwalYuNaive/outlier.AggarwalYuEvolutionary
Feature Bagging outlier.meta.FeatureBagging
HiCS outlier.meta.HiCS
COP outlier.COP
OUTRES outlier.subspace.OUTRES
OutRank outlier.subspace.OutRankS1


参考文献

*1:どこかで各アルゴリズムの詳細についてまとめたいところ…

*2:愚直な方法は O(n^3)の計算量が必要であり，原論文中で O(n^2)の近似計算法が提案されている．さらに，2012年にPham and Pughにより， O(n\log{n})の計算量の近似計算法が提案されている．

*3:高次元データの外れ値検出の記事なのに，2次元のデータを例として使うことには違和感が拭えないが…

*4:実際は，データの発生方法などのコメントが入っているが，ここでは省略

*5:別途，"cluster.txt"という名前で，入力データの各点の外れ値スコアを記したファイルが出力される．