Learning Minimum Volume Sets and Anomaly Detectors from KNN Graphs
We propose a non-parametric anomaly detection algorithm for high dimensional data. We first rank scores derived from nearest neighbor graphs on $n$-point nominal training data. We then train limited complexity models to imitate these scores based on the max-margin learning-to-rank framework. A test-point is declared as an anomaly at $\alpha$-false alarm level if the predicted score is in the $\alpha$-percentile. The resulting anomaly detector is shown to be asymptotically optimal in that for any false alarm rate $\alpha$, its decision region converges to the $\alpha$-percentile minimum volume level set of the unknown underlying density. In addition, we test both the statistical performance and computational efficiency of our algorithm on a number of synthetic and real-data experiments. Our results demonstrate the superiority of our algorithm over existing $K$-NN based anomaly detection algorithms, with significant computational savings.
Code (0)
등록된 구현이 없습니다.
Tasks
Anomaly DetectionComputational EfficiencyLearning-To-RankSimilar Papers 제목 키워드 기반
Efficient anomaly detection using bipartite k-NN graphs
Learning minimum volume sets of an underlying nominal distribution is a very effective approach to anomaly detection. Several approaches to learning minimum volume sets have been proposed in the literature, including the…
Anomaly DetectionLearning Efficient Anomaly Detectors from $K$-NN Graphs
We propose a non-parametric anomaly detection algorithm for high dimensional data. We score each datapoint by its average $K$-NN distance, and rank them accordingly. We then train limited complexity models to imitate the…
Anomaly DetectionComputational EfficiencyLearning-To-RankSubgraph Centralization: A Necessary Step for Graph Anomaly Detection
Graph anomaly detection has attracted a lot of interest recently. Despite their successes, existing detectors have at least two of the three weaknesses: (a) high computational cost which limits them to small-scale networ…
Anomaly DetectionGraph Anomaly DetectionMeta-Learning for Automated Selection of Anomaly Detectors for Semi-Supervised Datasets
In anomaly detection, a prominent task is to induce a model to identify anomalies learned solely based on normal data. Generally, one is interested in finding an anomaly detector that correctly identifies anomalies, i.e.…
Anomaly DetectionMeta-LearningLess is More: Building Selective Anomaly Ensembles
Ensemble techniques for classification and clustering have long proven effective, yet anomaly ensembles have been barely studied. In this work, we tap into this gap and propose a new ensemble approach for anomaly mining,…
ClusteringEvent Detection