Anomaly Detection with Score functions based on Nearest Neighbor Graphs
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 q, 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, q, 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.
Code (0)
등록된 구현이 없습니다.
Tasks
Anomaly DetectionSimilar Papers 제목 키워드 기반
Deep Nearest Neighbor Anomaly Detection
Nearest neighbors is a successful and long-standing technique for anomaly detection. Significant progress has been recently achieved by self-supervised deep methods (e.g. RotNet). Self-supervised features however typical…
Anomaly DetectionTarget before Shooting: Accurate Anomaly Detection and Localization under One Millisecond via Cascade Patch Retrieval
In this work, by re-examining the "matching" nature of Anomaly Detection (AD), we propose a new AD framework that simultaneously enjoys new records of AD accuracy and dramatically high running speed. In this framework, t…
Anomaly DetectionSupervised Anomaly DetectionCKNN: Cleansed k-Nearest Neighbor for Unsupervised Video Anomaly Detection
In this paper, we address the problem of unsupervised video anomaly detection (UVAD). The task aims to detect abnormal events in test video using unlabeled videos as training data. The presence of anomalies in the traini…
Anomaly DetectionVideo Anomaly Detectionk-NNN: Nearest Neighbors of Neighbors for Anomaly Detection
Anomaly detection aims at identifying images that deviate significantly from the norm. We focus on algorithms that embed the normal training examples in space and when given a test image, detect anomalies based on the fe…
Anomaly DetectionA Rank-SVM Approach to Anomaly Detection
We propose a novel non-parametric adaptive anomaly detection algorithm for high dimensional data based on rank-SVM. Data points are first ranked based on scores derived from nearest neighbor graphs on n-point nominal dat…
Anomaly DetectionComputational Efficiency