Given n i.i.d. samples from some unknown nominal density f_0, the task of anomaly detection is to learn a mechanism that tells whether a new test point η is nominal or anomalous, under some desired false alarm rate α. Popular non-parametric anomaly detection approaches include one-class SVM and density-based algorithms. One-class SVM is computationally efficient, but has no direct control of false alarm rate and usually gives unsatisfactory results. In contrast, some density-based methods show better statistical performance but have higher computational complexity at test time. We propose a novel anomaly detection framework that incorporates statistical density information into the discriminative Ranking SVM procedure. At training stage a ranker is learned based on rankings R of the average k nearest neighbor (k-NN) distances of nominal nodes. This rank R(x) is shown to be asymptotically consistent, indicating how extreme x is with respect to the nominal density. In test stage our scheme predicts the rank R(η) of test point η, which is then thresholded to report anomaly. Our approach has much lower complexity than density-based methods, and performs much better than one-class SVM. Synthetic and real experiments justify our idea.
展开▼