2004 · 851 citations · 22 references
ComputingData ScienceData AnalyticsData MiningMachine LearningAnomaly DetectionCluster DetectionOutlier DetectionCluster-based Outlier DetectionCutoff OptimizationDistance-based Outlier DetectionOutlier Detection EvaluationOutlier Loci DetectionOutlier RemovalPoint Outlier DetectionStatistical Outlier Detection
Outlier detection is a key data mining task that has attracted extensive research, and this work is the first to employ approximate computations to accelerate the process. The authors introduce LOCI, a new method for assessing outlierness. LOCI evaluates outlierness by computing a local correlation integral that yields a data‑driven cutoff and a detailed plot for each point. Experiments on synthetic and real datasets demonstrate that LOCI and its fast approximation aLOCI automatically detect outliers and micro‑clusters without user‑defined cutoffs, outperforming prior methods.
Outlier detection is an integral part of data mining and has attracted much attention recently [M. Breunig et al., (2000)], [W. Jin et al., (2001)], [E. Knorr et al., (2000)]. We propose a new method for evaluating outlierness, which we call the local correlation integral (LOCI). As with the best previous methods, LOCI is highly effective for detecting outliers and groups of outliers (a.k.a. micro-clusters). In addition, it offers the following advantages and novelties: (a) It provides an automatic, data-dictated cutoff to determine whether a point is an outlier-in contrast, previous methods force users to pick cut-offs, without any hints as to what cut-off value is best for a given dataset. (b) It can provide a LOCI plot for each point; this plot summarizes a wealth of information about the data in the vicinity of the point, determining clusters, micro-clusters, their diameters and their inter-cluster distances. None of the existing outlier-detection methods can match this feature, because they output only a single number for each point: its outlierness score, (c) Our LOCI method can be computed as quickly as the best previous methods, (d) Moreover, LOCI leads to a practically linear approximate method, aLOCI (for approximate LOCI), which provides fast highly-accurate outlier detection. To the best of our knowledge, this is the first work to use approximate computations to speed up outlier detection. Experiments on synthetic and real world data sets show that LOCI and aLOCI can automatically detect outliers and micro-clusters, without user-required cut-offs, and that they quickly spot both expected and unexpected outliers.
22
Robust Regression and Outlier Detection
Gregory F. Piepel, Peter J. Rousseeuw, Annick M. Leroy · Technometrics · 1989 · 6.2K citations
Markus Breunig, Hans‐Peter Kriegel, Raymond T. Ng et al. · ACM SIGMOD Record · 2000 · 5.2K citations
Similarity Search in High Dimensions via Hashing
Aristides Gionis, Piotr Indyk, Rajeev Motwani · 1999 · 3.1K citations
<i>Outliers in Statistical Data</i>
V. Barnett, T. Lewis, Francine F. Abeles · Physics Today · 1979 · 2.8K citations
An optimal algorithm for approximate nearest neighbor searching fixed dimensions
Sunil Arya, David M. Mount, Nathan S. Netanyahu et al. · Journal of the ACM · 1998 · 2.3K citations · Full text