MENU Efficient anomaly detection using bipartite k-NN graphs
Kumar Sricharan, and Alfred O. Hero III
Abstract
Finding the minimum volume sets of the underlying distribution of the nominal events is a very effective approach to detecting anomalies. Several approaches to finding minimum volume sets have been proposed in literature, including the K-kNNG algorithm based on the geometric entropy minimization (GEM) principle~\cite{herogem}. The K-kNNG detector, while possessing several desirable characteristics, suffers from a significant drawback in that it is computationally intractable. In this paper, we propose a novel bipartite k-NN graph anomaly detection scheme (BP-kNNG) for estimating minimum volume sets using the GEM principle. Our bipartite estimator retains all the desirable properties of the K-kNNG, while simultaneously being computationally efficient as compared to K-kNNG and the surrogate L10-kNNG detectors proposed in~\cite{herogem}. Furthermore, we show that BP-kNNG is asymptotically consistent in recovering the p-value of each test point. Finally, we show experimental results to illustrate the superior performance of BP-kNNG over L10-kNNG and other state of the art anomaly detection schemes.
Paper
K. Sricharan, and A. O. Hero III. Efficient anomaly detection using bipartite k-NN graphs. In Proc. Advances in Neural Information Processing Systems (NIPS), 2011. .pdf