Subspace Outlier Detection in Linear Time with Randomized Hashing
Authors:
- Saket SatheSSSaket Sathe
- Charu C. AggarwalCACharu C. Aggarwal
- 1 December 2016
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 459-468
Abstract
Outlier detection algorithms are often computationally intensive because of their need to score each point in the data. Even simple distance-based algorithms have quadratic complexity. High-dimensional outlier detection algorithms such as subspace methods are often even more computationally intensive because of their need to explore different subspaces of the data. In this paper, we propose an exceedingly simple subspace outlier detection algorithm, which can be implemented in a few lines of code, and whose complexity is linear in the size of the data set and the space requirement is constant. We show that this outlier detection algorithm is much faster than both conventional and high-dimensional algorithms and also provides more accurate results. The approach uses randomized hashing to score data points and has a neat subspace interpretation. Furthermore, the approach can be easily generalized to data streams. We present experimental results showing the effectiveness of the approach over other state-of-the-art methods.Keywords
This publication has 20 references indexed in Scilit:
- Theoretical Foundations and Algorithms for Outlier EnsemblesACM SIGKDD Explorations Newsletter, 2015
- RS-Forest: A Rapid Density Estimator for Streaming Anomaly DetectionIEEE International Conference on Data Mining (ICDM), 2014
- Outlier Detection with Space Transformation and Spectral Analysis2013
- AnyOut: Anytime Outlier Detection on Streaming Data2012
- Angle-based outlier detection in high-dimensional data2008
- Feature bagging for outlier detection2005
- Mining distance-based outliers in near linear time with randomization and a simple pruning rule2003
- Outlier detection for high dimensional data2001
- Efficient algorithms for mining outliers from large data sets2000
- LOF2000