Learning 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 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 제목 키워드 기반
Subgraph 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 DetectionAn End-to-End Framework for Functionality-Embedded Provenance Graph Construction and Threat Interpretation
Provenance graphs model causal system-level interactions from logs, enabling anomaly detectors to learn normal behavior and detect deviations as attacks. However, existing approaches rely on brittle, manually engineered …
Less 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 DetectionLearning 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 …
Anomaly DetectionComputational EfficiencyLearning-To-Ranktegdet: An extensible Python Library for Anomaly Detection using Time-Evolving Graphs
This paper presents a new Python library for anomaly detection in unsupervised learning approaches. The input for the library is a univariate time series representing observations of a given phenomenon. Then, it can iden…
Anomaly DetectionTime SeriesTime Series Analysis