Efficient algorithms for mining outliers from large data sets

By S. Ramaswamy, Rajeev Rastogi, Kyuseok Shim. ACM SIGMOD Conference, 2000

2,649 citations recorded by the source corpus.

In this paper, we propose a novel formulation for distance-based outliers that is based on the distance of a point from its kth nearest neighbor. We rank each point on the basis of its distance to its kth nearest neighbor and declare the top n points in this ranking to be outliers. In addition to developing relatively straightforward solutions to finding such outliers based on the classical nested-loop join and index join algorithms, we develop a highly efficient partition-based algorithm for mining outliers. This algorithm first partitions the input data set into disjoint subsets, and then prunes entire partitions as soon as it is determined that they cannot contain outliers. This results in substantial savings in computation. We present the results of an extensive experimental study on real-life and synthetic data sets. The results from a real-life NBA database highlight and reveal several expected and unexpected aspects of the database. The results from a study on synthetic data sets demonstrate that the partition-based algorithm scales well with respect to both data set size and data set dimensionality.

Subfields: Artificial Intelligence, Signal Processing

View Paper: https://www.semanticscholar.org/paper/a8db789522b9375396bd91de631342740ba19a12

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Signal Processing

Citations in the corpus

Online outlier detection in sensor data using non-parametric models (2006, methodology): “The usefulness and validity of distance-based outliers has been established in the literature [6, 28, 38].”
A Survey of Clustering Data Mining Techniques (2006, background): “[184] noticed that this definition can be improved by eliminating parameter .”
Map building with mobile robots in dynamic environments (2003, background): “The identification of outliers is an important subtask in various application areas such as data mining [12, 3, 16], correspondence establishment [6, 2], clustering [8], or statistics [1].”
Progress in Outlier Detection Techniques: A Survey (2019, methodology): “KNN method [123], it showed an improved performance in the detection rate.”
Outlier Analysis (2013, methodology): “The work in [381] provides a first approach along this line of methods.”
Generative Adversarial Active Learning for Unsupervised Outlier Detection (2018, methodology): “They can be divided into seven categories: (i) two density-based methods, LOF [18] and KDEOS [37]; (ii) two density estimators, GMM [11] and Parzen [17]; (iii) a typical distance-based approach, kNN [36]; (iv) an angle-based model, FastABOD [37]; (v) a cluster-based model, k-means; (vi) a popular on”
ECOD: Unsupervised Outlier Detection Using Empirical Cumulative Distribution Functions (2022, background): “Speciﬁcally, the 11 competitors are Angle-Based Outlier Detection (ABOD) [58], Clustering-Based Local Outlier Factor (CBLOF) [40], Histogram-based Outlier Score (HBOS) [30], Isolation Forest (IForest) [17], k Nearest Neighbors (KNN) [15], Lightweight On-line Detector of Anomalies (LODA) [59], Local ”
Local Search Methods for k-Means with Outliers (2017, background): “, separating the outlier detection from the clustering objective [2, 4, 7, 25, 26, 30, 37, 38].”
Statistical Analysis of Nearest Neighbor Methods for Anomaly Detection (2019, methodology): “Two versions of the NN anomaly detection algorithms have been proposed: kNN [20] and kNN [6].”
Feature bagging for outlier detection (2005, background): “Several recently proposed distance based outlier detection algorithms are based on (1) computing the full dimensional distances of points from one another using all the available features [19, 27] or only feature projections [3], and (2) on computing the densities of local neighborhoods [10].”
LOF: identifying density-based local outliers (2000, neutral): “Intuitively, outliers can be defined as given by Hawkins [10].”
Learning Discriminative Reconstructions for Unsupervised Outlier Removal (2015, methodology): “The dense areas can be estimated by statistical methods [6, 27, 11], neighbor-based methods [17, 3, 7], and reconstruction-based methods [23, 26].”
Anomaly Detection in Time Series: A Comprehensive Evaluation (2022, methodology): “Representatives of this category in our evaluation are: CBLOF [59], COF [130], DBStream [55], HOT SAX [70], Hybrid KNN [124], k-Means [151], KNN [110], LOF [22], NormA-SJ [15], PhaseSpaceSVM (PS-SVM) [85], SAND [17], SSA [155], STAMP [156], STOMP [164], Sub-LOF [22], VALMOD [82], and Left STAMPi [15”
k-means-: A Unified Approach to Clustering and Outlier Detection (2013, methodology): “In this paper we will propose a generalization of the k-means problem with the aim of simultaneously clustering data and discovering outliers.”
Outlier Detection with Autoencoder Ensembles (2017, methodology): “Numerous methods such as distance-based methods [5, 11, 17], density-based methods [6], linear methods [21], and spectral methods [8, 18] have been proposed.”
Foreground object detection in highly dynamic scenes using saliency (2014, methodology): “Inspired by the work of outlier detection using the distance of the k nearest neighbor [6], we address the aforementioned problem by making a given pixel be the central region and its k nearest neighbors in a feature space be the surround region.”