Computer Science Department
School of Computer Science, Carnegie Mellon University
LOCI: Fast Outlier Detection Using the Local Correlation Integral
Spiros Papadimitriou, Hiroyuki Kitagawa*, Phillip B. Gibbons**, Christos Faloutsos
a) It provides an automatic, data-dictated cut-off 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 outlier-ness 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.
*University of Tsukuba, Japan