Mining top-n local outliers in large databases

By Wen Jin, Anthony K. H. Tung, Jiawei Han. Knowledge Discovery and Data Mining, 2001

375 citations recorded by the source corpus.

Outlier detection is an important task in data mining with numerous applications, including credit card fraud detection, video surveillance, etc. A recent work on outlier detection has introduced a novel notion of local outlier in which the degree to which an object is outlying is dependent on the density of its local neighborhood, and each object can be assigned a Local Outlier Factor (LOF) which represents the likelihood of that object being an outlier. Although the concept of local outliers is a useful one, the computation of LOF values for every data objects requires a large number of &kgr;-nearest neighbors searches and can be computationally expensive. Since most objects are usually not outliers, it is useful to provide users with the option of finding only n most outstanding local outliers, i.e., the top-n data objects which are most likely to be local outliers according to their LOFs. However, if the pruning is not done carefully, finding top-n outliers could result in the same amount of computation as finding LOF for all objects. In this paper, we propose a novel method to efficiently find the top-n local outliers in large databases. The concept of "micro-cluster" is introduced to compress the data. An efficient micro-cluster-based local outlier mining algorithm is designed based on this concept. As our algorithm can be adversely affected by the overlapping in the micro-clusters, we proposed a meaningful cut-plane solution for overlapping data. The formal analysis and experiments show that this method can achieve good performance in finding the most outstanding local outliers.

Subfields: Artificial Intelligence, Biomedical Engineering, Signal Processing

View Paper: https://www.semanticscholar.org/paper/0fe59f1630eaae55da2626acb1003e244a3733ee

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 Biomedical Engineering

In Signal Processing

Citations in the corpus

Outlier mining in large high-dimensional data sets (2005, background): “Given an application dependent parameter k, the weight of a point is defined as the sum of the distances separating it from its k nearest-neighbors.”
A comparative study of RNN for outlier detection in data mining (2002, background): “This leads to the concept of local outliers in the data mining literature [17].”
LOCI: fast outlier detection using the local correlation integral (2003, methodology): “[15] proposed an algorithm to efficiently discover top-n outliers using clusters, for a particular value of MinPts .”
Anomaly detection: A survey (2009, background): “Jin et al. [2001] propose a variant, in which only the top n anomalies are found instead of finding LOF score for every data instance.”
Outlier Analysis (2013, background): “For example, the work in [241] proposed the concept of top-n local outliers, where the top-n outliers were determined on the basis of the density.”
Classifying large data sets using SVMs with hierarchical clusters (2003, neutral): “The concept of a “micro-cluster” is similar to those in [25, 12], which de notes a statistically summarized representation of a group of dat a which are so close together that they are likely to belong to the sam e cluster.”
Hierarchical Density Estimates for Data Clustering, Visualization, and Outlier Detection (2015, methodology): “…basic LOF model have been proposed, for example a COF (connectivity-based outlier factor) [Tang et al. 2002], or using the concept of micro-clusters to efficiently mine the top-n density-based local outliers in large databases (i.e., those n objects having the highest LOF value) [Jin et al. 2001].”
Outlier Detection Using k-Nearest Neighbour Graph (2004, neutral): “Definitions fall roughly into five categories [ 7 ]: i) distribution-based, ii) depth-based, iii) distance-based, iv) clustering-based and v) density-based.”
Interpreting and Unifying Outlier Scores (2011, methodology): “Several extensions of the basic LOF model and algorithms for efficient (topn ) computation have been proposed [22] [23] [49] [50] that basically use different notions of neighborhoods.”
Ranking Outliers Using Symmetric Neighborhood Relationship (2006, methodology): “The estimation of density distribution at the location of an object has so far been based on the density distribution of its k-nearest neighbors [2, 11].”
Trajectory Outlier Detection: A Partition-and-Detect Framework (2008, background): “However, the computation of LOF values requires a large number of k-nearest neighbor queries, and thus, can be computationally expensive [11] .”