Anomaly Detection with Score functions based on Nearest Neighbor Graphs

Abstract

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 $\alpha$, 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, $\alpha$, 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.

10 pages, 10 figures, accepted by NIPS 2009

Cited by in corpus (14)

• Real-Time Nonparametric Anomaly Detection in High-Dimensional Settings
• Nonparametric Divergence Estimation with Applications to Machine Learning on Distributions
• Denoising Autoencoders for Overgeneralization in Neural Networks
• ATD: Anomalous Topic Discovery in High Dimensional Discrete Data
• Multi-criteria Similarity-based Anomaly Detection using Pareto Depth Analysis
• Human-Inspired Multi-Agent Navigation using Knowledge Distillation
• Network Representation Learning: Consolidation and Renewed Bearing
• OneFlow: One-class flow for anomaly detection based on a minimal volume region
• Fixing Bias in Reconstruction-based Anomaly Detection with Lipschitz Discriminators
• Graph-based Learning with Unbalanced Clusters
• A Neural Network Approach for Online Nonlinear Neyman-Pearson Classification
• Data-Driven Nonparametric Existence and Association Problems
• A Rank-SVM Approach to Anomaly Detection
• Spectral Clustering with Imbalanced Data