Statistical Analysis of Nearest Neighbor Methods for Anomaly Detection

By Xiaoyi Gu, Leman Akoglu, Alessandro Rinaldo. 2019

111 citations recorded by the source corpus.

Nearest-neighbor (NN) procedures are well studied and widely used in both supervised and unsupervised learning problems. In this paper we are concerned with investigating the performance of NN-based methods for anomaly detection. We first show through extensive simulations that NN methods compare favorably to some of the other state-of-the-art algorithms for anomaly detection based on a set of benchmark synthetic datasets. We further consider the performance of NN methods on real datasets, and relate it to the dimensionality of the problem. Next, we analyze the theoretical properties of NN-methods for anomaly detection by studying a more general quantity called distance-to-measure (DTM), originally developed in the literature on robust geometric and topological inference. We provide finite-sample uniform guarantees for the empirical DTM and use them to derive misclassification rates for anomalous observations under various settings. In our analysis we rely on Huber's contamination model and formulate mild geometric regularity assumptions on the underlying distribution of the data.

Subfields: Artificial Intelligence, Epidemiology, Statistics and Probability

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

1. Wojciech Samek
2. Grgoire Montavon
3. K. Müller
4. Klaus‐Robert Müller 
5. Yiyou Sun
6. Yixuan Li
7. Sebastian Lapuschkin
8. Marius Kloft

In Epidemiology

1. Thomas G. Dietterich
2. Yixuan Li
3. Minlie Huang
4. Marius Kloft
5. Guanyi Chen
6. Yinhe Zheng

In Statistics and Probability

1. Thomas G. Dietterich
2. Grgoire Montavon
3. Yixuan Li
4. Wojciech Samek
5. Minlie Huang
6. Xiaojin Zhu
7. Klaus‐Robert Müller 
8. Marius Kloft

Citations in the corpus

• Out-of-Domain Detection for Natural Language Understanding in Dialog Systems (2019, methodology): “[27], using classifier ensembles [13], [28], applying Bayesian models [29], relying on distances to nearest-neighbors [9], [30], or even explicitly learning a detection score [31].”
• Artificial intelligence based anomaly detection of energy consumption in buildings: A review, current trends and new perspectives (2021, unknown): “In this regard, in [131], a distance-based anomaly detection is proposed via analyzing the theoretical properties of the nearest neighbors of each power observation.”
• HRN: A Holistic Approach to One Class Learning (2020, unknown): “In general, anomaly detection algorithms can be classified into the following categories: distance based methods [42, 3, 28, 31, 60], density based methods [38, 56, 6], mixture models [3, 43], one-class classification based methods [75, 78, 39], deep learning based representation learning using…”
• A Unifying Review of Deep and Shallow Anomaly Detection (2020, methodology): “Examples of such methods include nearestneighbor-based methods [8], [9], [420]–[422], such as LOF [10] and partitioning tree-based methods [423], such as iForest [424], [425].”
• Out-of-distribution Detection with Deep Nearest Neighbors (2022, background): “Some other recent works (Dang et al., 2015; Gu et al., 2019; Pires et al., 2020) explore the effectiveness of KNN-based anomaly detection for the tabular data.”