Rapid Distance-Based Outlier Detection via Sampling
Mahito Sugiyama, Karsten Borgwardt · 2013
Distance-based approaches to outlier detection are popular in data mining, as they do not require to model the underlying probability distribution, which is particu-larly challenging for high-dimensional data. We present an empirical comparison of various approaches to distance-based outlier detection across a large number of datasets. We report the surprising observation that a simple, sampling-based scheme outperforms state-of-the-art techniques in terms of both efficiency and ef-fectiveness. To better understand this phenomenon, we provide a theoretical anal-ysis why the sampling-based approach outperforms alternative methods based on k-nearest neighbor search. 1