An Efficient Reference-Based Approach to Outlier Detection in Large Datasets
Authors:
- 1 December 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE International Conference on Data Mining (ICDM)
- No. 15504786,p. 478-487
Abstract
A bottleneck to detecting distance and density based outliers is that a nearest-neighbor search is required for each of the data points, resulting in a quadratic number of pairwise distance evaluations. In this paper, we propose a new method that uses the relative degree of density with respect to a fixed set of reference points to approximate the degree of density defined in terms of nearest neighbors of a data point. The running time of our algorithm based on this approximation is 0(Rn log n) where n is the size of dataset and R is the number of reference points. Candidate outliers are ranked based on the outlier score assigned to each data point. Theoretical analysis and empirical studies show that our method is effective, efficient, and highly scalable to very large datasets.Keywords
This publication has 7 references indexed in Scilit:
- Mining distance-based outliers in near linear time with randomization and a simple pruning rule2003
- A Geometric Framework for Unsupervised Anomaly Detection2002
- Mining top-n local outliers in large databases2001
- Efficient algorithms for mining outliers from large data sets2000
- LOF2000
- A survey of adaptive sorting algorithmsACM Computing Surveys, 1992
- Identification of Outliers1980