1,2

Mahito Sugiyama


1,2,3

Karsten Borgwardt .

Rapid Distance-Based Outlier Detection via Sampling
Machine Learning and Computational Biology Research Group



Max Planck Institute for Intelligent Systems, Tübingen, Max Planck Institute for Developmental Biology, Tübingen, ZBIT, Eberhard Karls Universität Tübingen

EXPERIMENTAL RESULTS– Intrusions in network traﬃc, credit card fraud, defective products in industry,
medical diagnosis from X-ray images, …
∘ Specific task: Assign an outlierness score to each point using pairwise distances– is distance-based approach has been successfully applied in various domains∘ Example: th nearest neighbor [1,2], LOF [Breunig et al. SIGMOD 2000]– It does not require to model the underlying probability distribution,
which is particularly challenging for high-dimensional data

∘ Computation of all pairwise distances is needed:∘ Two state-of-the-art solutions()

1. Partial computation to obtain only top- outliers
2. Indexing of objects

PROPOSAL: SAMPLING-BASED OUTLIER DETECTION

Solution: Sampling∘ Given a dataset ( data points, dimensions)∘ Randomly and independently sample a subset ( ) ⊂∘ Define the score( ) for each object ∈ as
∈ ( )

( ,)

Nearest neighborin samples– Our method: one-time sampling, their method: iterative sampling for each point.

351
452
569
600
960
768
1000
1688
4601
6435
24505737316128604848984315734488
10000000

126
207
212
200
240
268
30
554
1813
626
50859
1259532747
703067
20887
30

34
274
30
649
617
8
1000
64
57
36
351
10
6
720

( ; ): the set of Knorr and Ng’s DB( , )-outliers:∈ ( ; ) if

∘ ( ; )
∘ Define (0.50Our method
Wu’s method

Wu’s

Ours

iForest∀ ∈ ( ; ), {0.40LOF

50
200
Number of samples

1000∣ ( ,)}∈ ( ; ),( )())}

1.0
0.9
0.8
0.7
0.6
0.5
0.40.2∘ Result 2: is bound is maximized at
106

102
130

> 2 months

Wu’s

Ours

iForestLOF

FastVOA

SVM

0.8

20
100.2

– is value tends to be small

0.4

β0.6

0.8

More detailed results∘ A -partition 𝒫 of ( ; ): ∀ ∈ 𝒫 ,∘ For an outlier ∈ ( ; ) and a cluster∀

10–2

β0.6α = 0.95
α = 0.99
α = 0.999

4001040.450( is the number of samples)– is lower bound tends to be high in a typicalsetting ( is large, is moderate)

SVM

IonosphereArrhythmia
Wdbc
Mfeat
IsoletPima
Gaussian
Optdigits
Spambase
Statlog
Skin
Pamap2
Covtype
Kdd1999
RecordGaussian
Average
Avg.rank
RMSD∈∈ ( ; ) and( )FastVOA∣ ( ,⧵ ( ; ), the set of inliers) as the minimum value s.t.

∘ Result 1: For

5 10

∈

∈ ℝ is a distance threshold∈ℝ() is the fraction of objects which locate far away from ;this should be close to by definition of outliers– NOTE: ese parameters are not needed in practice

0.55

0.45

{––Sensitivity in sample sizes

IonosphereArrhythmia
Wdbc
Mfeat
IsoletPima
Gaussian
Optdigits
Spambase
Statlog
Skin
Pamap2
Covtype
Kdd1999
RecordGaussiankthNN∘ Related work: Wu and Jermaine [3] proposed a sampling-based method:.

IonosphereArrhythmia
Wdbc
Mfeat
IsoletPima
Gaussian*
Optdigits
Spambase
Statlog
Skin
Pamap2
Covtype
Kdd1999
RecordGaussian*

AUPRC (area under the precision-recall curve; * are best scores))– Input parameter: the number of samples| ( )|– e time complexity is () and the space complexity is (6 samples(randomelychosen)# of objects # of outliers # of dimskthNN

1. e number of outliers oen increases in direct proportion to the size of the dataset,
which deteriorates the eﬃciency of partial computation
2. Index structures are oen not eﬃcient enough for high-dimensional data( )∶Datasets (* are synthetic)

Running time (in seconds)∘ Unfortunately, both strategies are not suﬃcient∘– Parameters were set to be the same in the original papers or popular values.

Problem: Scalability

Main results

Maximized lower bound∘ Outliers are objects located far away from the remaining objects∘ Outliers appear everywhere:∘ Comparison partners:
thNN (the latest technique iORCA [2] is used), Wu and Jermaine’s method [3] (iterativesampling), iForest (random forest-like method) [Liu et al. 2012], LOF, FastVOA (anglebased method) [Pham and Pagh, 2012], One-class SVM [Schölkopf et al. 2001]

AUPRC (average)

How can we find outliers eﬃciently in massive datasets?

THEORETICAL ANALYSIS

Number of samples

BACKGROUND∈ ,( )( , ), ∈( ; )and ⋃ ∈𝒫

∈𝒫,( )() with(| |)/∘ Let ( ; ) ⊂ ( ; ) s.t. ∀ ∈ ( ; ),),𝒫{ , … , } be∈ ( ; ) ( ,a -partition of ( ; ), and| |/| ( ; )| for each ∈ { , … , }∘ Let ( ) ∑∀ ; ⪈ ( , … , ; , , … , ), where is the probability mass function of
the multinomial distribution, and| ( ; )|/ . en

1.0∀ ∈ ( ; ), ∀∈ ( ; ),( )

( )

𝒫( )

0.8

CONCLUSION
0.6∘ Our method is much (2 to 6 orders of magnitude) faster than exhaustive methods∘ Our method is the most eﬀective on average

0.4

REFERENCES
0.2
0
0.453
3.750
0.259

0.410
3.875
0.274

0.534
2.188
0.068

0.479
3.875
0.133

0.400
4.538
0.152

0.468
4.563
0.140

0.421
4.000
0.094

1. Original paper on distance-based outliers: Korr, E. M., Ng, R. T., and Tucakov, V. Distancebased outliers: algorithms and applications. e VLDB Journal, 8(3):237–253, 2000.
2. State-of-the-art of thNN detection: Bhaduri, K., Matthews, B. L., and Giannella, C. R.
Algorithms for speeding up distance-based outlier detection. KDD 2011.
3. Related sampling-based method: Wu, M. and Jermaine, C. Outlier detection by samplingwith accuracy guarantees. KDD 2006.