狠狠撸

A Near-linear Time Approximation
for Angle-based Outlier Detection
in High-dimensional Data [KDD’12]

by N. Pham & R. Pagh Univ. of Copenhagen

発表者：数理情報学専攻修士２年山田直敬
1

発表の流れ
1. Outlier Detection in High-dimensional data
- 高次元では次元の呪いによる性能悪化が発生する

2. Angle-based Outlier Detection (ABOD)
- 距離や密度による手法よりも高次元でロバストな手法

3. A Near Linear Time Approximation for ABOD
- ABODの計算量は O(dn3). 近似でこれを大幅に高速化
本論文のcontribution

2

1.
Outlier Detection
in High dimensional data

3

次元の呪い
図：次元数増加に伴う距離の同質化 [2]

次元数: 順に
2, 4,
20, 50
横軸 : マハラノビス距離の値
縦軸：観測頻度

?高次元化が進むと，距離の近接性が意味を成さなくなる.
?実際となる. [1]

?データは非常にスパース. ほとんどの点が外れ値になる. 4

高次元データに対する外れ値検出手法
図: 外れ値検知の代表的な手法 (出典 : 第一回授業の配布資料)

●次元の呪いにより, 距離やk-近傍を用いる手法は性能悪化
●次元についてスケールしない計算を含む(凸包, LOF etc...)
→ 次元の呪い＆計算の非効率化を回避する手法が必要
5
アプローチ：ロバストな距離関数を定義 or 射影

2.
Angle-based Outlier Detection

6

Angle-Based Outlier Detection
by Kriegel+ ’08 [1]
発想
?角度は高次元においてマハラノビス距離よりもロバスト
e.g. コサイン類似度は文書に対しても良く用いられる.

?外れ値では他の二点間との角度がどれも似ている
図: 外れ値、正常値、境界点での角度の分布

縦軸:
角度(rad)

Outlier Factorを角度の分散としてモデル化
7
出典: [3]

Angle-Based Outlier Detection(cont.)

?角度の分散をoutlier factorとしてモデル化する.
?点pにおいては

*
と書ける.
?一点のABODを求めるためにnC2 回角度を評価している.

?ABOD値が小さければ外れ値として検出する.
8

ABOD vs. LOF (Local Outlier Factor)
?人工データによる実験. 5つの混合ガウス+10個のoutlier
?precision recallともにABODが上回る.

9
出典: [1]

础叠翱顿の欠点
?全ての点でABODを求めるための計算量は O(dn3).
?データ数 n の増加に対してスケールしない.

10
出典: [1]より見やすく編集

3.
A Near Linear Approximation for
Angle-based Outlier Detection
[main part]

11

概要
? ABODの高速化.
? 角度の分散を直接計算するかわりに不偏推定
量で評価する.
– 不偏推定量: 期待値が真の値と一致するような統計
量
– 今回の設定では推定量の分散も小さいことが示さ
れた.
? random projection, AMS sketchを利用.
? 並列化も容易. 計算量は”near linear”
– O(tn(d + log n + s1s2))
– t : random proj.の回数, s : sketchの回数
12

Angle-based Outlier Factor
?先程同様,点p での角度を分散を外れ値のスコアに用いる.
定義 :
Given: d 次元Euclid空間上の点集合S (|S |=n )と点p ∈S.
異なる適当な2点 a,b ∈ S {p }に対して, ベクトル a-p, b-p が
なす角を Oapb とする. このとき Oapbの分散をスコアとする.

但し,

mean of angle

である.
13

用いる手法
? Random Hyperplane Projection
– ランダムな超平面でデータを２分割する.
– MOA1 の不偏推定量を求める.

? AMS Sketch
– モーメント統計量の近似を行う.
– MOA2 を近似する

14

Random Hyperplane Projection 1/2
?t 個のランダムベクトルをとる.
?これらの各成分は独立に標準正規分布に従う.
?それぞれの ri を法線に持つ超平面でデータを分割する.

ri

p

15

?それぞれの ri を法線に持つ超平面でデータを分割する.

ri

p

16

?それぞれの ri を法線に持つ超平面にデータを分割する

ri
b

a
p

この状況で角度を考えてみる
17


?各i =1,...,t でランダムベクトルri , 適当な二点a,b について
確率変数 Xapb(i) を次のように定義する.

ri

?X が 1となるのは b

かつ a
a-p, b-p が超平面で分離 p
されているときのみ

?それが起こる確率は, 任意のi,a,b,pに対して

＝
18

AMS Sketch 1/2
?高次元ベクトルとランダムビットの内積(Sketch)は
２次のモーメント統計量を近似する性質を持つ.

?高次元ベクトル w = ( ) に対して
各座標で独立*なランダムビットベクトル

を取り内積を取ったものを
AMS Sketch という.

? とすると .

ここで、が成り立つ

19

AMS Sketch 2/2
?ベクトルの外積 uv に対するSketchも次のように与えられる.

2つのランダムビットを用いて

とする. すなわち, u,v のそれぞれのAMSスケッチの外積が
外積 uv のスケッチである.

? とすると :フロベニウスノルム2

このときが成立.

20

础叠翱顿の近似
?Random Hyperplane Projection における関係

＝を利用.

? の推定量 F1 は,

超平面を
跨ぐ回数

Lp 超平面の下(左)側の点
21
Rp 超平面の上(右)側の点

ri
?|Lp||Rp| は超平面を跨ぐ回数
b

a
p

? t 回の平均をとることでより精度が高まる.

? F1(p) はMOA1(p)の不偏推定量
?しかも分散も小さいことが示されている. (Chernoff bound)
?L,Rはsortで得る. F1 を求める計算量はO(t n (d+log n) ) 22

?MOA２の不偏推定量 F2 を求める.

詳細はフクザツなので割愛

?分散が3/4 と F1 のように小さくはない
→ 何度か繰り返して平均をとることで精度を上げる.

?任意の精度ε> 0 を高確率 1-δ で達成するためには
s1= 32π4/ε2 , s2 = O(log(1/δ)) として
s1s2 回 F2を計算する必要がある.

?AMSはO(n). ここの計算量は O( tn s1s2 ) 23

础叠翱顿の近似擬似コード

?計算量 O( tn(d + log n + s1s2)) 特に O( t n s1s2 )が支配的
?t =O(log n) で十分. t回のprojectionは独立.並列化可能.
?s1s2も精度次第
→ 並列化込みでnear linearを実現 !
24

人工データによる実験

5000
1000

※ABODの実験と同じ人工データ
25

実データによる実験

?どれも100次元程度
?緑のFastVOAが提案手法, 青, 赤がナイーブな解

?ABODでPRが良いデータでFastVOAで劣化
?ABODがダメなデータにはそこそこの性能 26

実データによる実験

?CPU timeではかなり高速化を実現している (t=100) 27

まとめ感想

?高次元において距離ベースでの外れ値検出が困難である
という問題へのアプローチ
?比較的ロバストなAngle-based Outlier detectionに注目
計算量をnear linear に改善
?手法がクール ( random projection, AMS sketch)
?不偏推定量を使っている. &
精度の保証が理論的に示されていて良い.

?実験結果 precision-recallはいまひとつ…
?必要な精度を決めるノウハウが別途必要そう(ε,δ)
etc...

28

References [年代順]
1. H.P. Kriegel, M.Schubert, & A. Zimek. Angle-based
outlier detection in high-dimensional data. In KDD
2008.

1. H.P. Kriegel, M. Schubert, & A. Zimek. Outlier
detection techniques. In tutorial at KDD 2010.

1. N. Pham & R. Pagh. A Near-linear Time
Approximation Algorithm for Angle-based Outlier
Detection in High-dimensional Data. In KDD 2012.

29

狠狠撸

Angle-Based Outlier Detection周辺の論文紹介

Recommended

More Related Content

What's hot (20)

Similar to Angle-Based Outlier Detection周辺の論文紹介 (20)

Recently uploaded (15)

Angle-Based Outlier Detection周辺の論文紹介