Anomaly Detection with Score functions based on Nearest Neighbor Graphs

By Manqi Zhao, Venkatesh Saligrama. 2009

117 citations recorded by the source corpus.

We propose a novel non-parametric adaptive anomaly detection algorithm for high dimensional data based on score functions derived from nearest neighbor graphs on n-point nominal data. Anomalies are declared whenever the score of a test sample falls below α, which is supposed to be the desired false alarm level. The resulting anomaly detector is shown to be asymptotically optimal in that it is uniformly most powerful for the specified false alarm level, α, for the case when the anomaly density is a mixture of the nominal and a known density. Our algorithm is computationally efficient, being linear in dimension and quadratic in data size. It does not require choosing complicated tuning parameters or function approximation classes and it can adapt to local structure such as local change in dimensionality. We demonstrate the algorithm on both artificial and real data sets in high dimensional feature spaces.

Subfields: Artificial Intelligence, Biomedical Engineering, Computer Networks and Communications

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 Computer Networks and Communications

Citations in the corpus

One-Class Support Measure Machines for Group Anomaly Detection (2013, methodology): “Lastly, we compare the OCSMM with existing group anomaly detection techniques, namely, K-nearest neighbor (KNN) based anomaly detection (Zhao and Saligrama 2009) with NP-L2 divergence and NP-Renyi divergence (Póczos et al. 2011), and Multinomial Genre Model (MGM) (Xiong et al. 2011b) on Sloan…”
Nonparametric Divergence Estimation with Applications to Machine Learning on Distributions (2011, methodology): “We use a simple detection algorithm based on nearest neighbors (Zhao and Saligrama, 2009).”
Video anomaly detection based on local statistical aggregates (2012, background): “Our focus is on problems, where we are given a set of nominal training videos samples.”
Distribution Free Prediction Sets (2013, methodology): “We compare our method with the approach introduced by Zhao and Saligrama (2009) (ĈZS), where the prediction set is constructed by ranking the distances from each data point to its kth nearest neighbor.”
Group Anomaly Detection using Flexible Genre Models (2011, methodology): “Then, a k-nearest neighbor (KNN) based point detector [21] is used to score the groups’ features.”
Hierarchical Probabilistic Models for Group Anomaly Detection (2011, methodology): “For example, Zhao (2009) uses the distances to nearest neighbors as an anomaly score.”
Learning Novel Policies For Tasks (2019, methodology): “One possible approach would be using nearest-neighbour based approch as in (Zhao & Saligrama, 2009; Liao & Vemuri, 2002) to measure the difference between the newly generated rollout and the rollouts from previous policies and aggregate them to obtain a novelty measurement.”