Learning Minimum Volume Sets and Anomaly Detectors from KNN Graphs
This addresses anomaly detection for high-dimensional data, offering improved performance and efficiency, though it appears incremental as it builds on existing K-NN approaches.
The paper tackles anomaly detection in high-dimensional data by proposing a non-parametric algorithm that uses nearest neighbor graphs and max-margin learning-to-rank to predict scores, achieving asymptotic optimality by converging to the minimum volume level set of the underlying density. Results show superiority over existing K-NN methods with significant computational savings.
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 $α$-false alarm level if the predicted score is in the $α$-percentile. The resulting anomaly detector is shown to be asymptotically optimal in that for any false alarm rate $α$, its decision region converges to the $α$-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.