New statistic in P-value estimation for anomaly detection

Given n nominal samples, a query point η and a significance level a, the uniformly most powerful test for anomaly detection can be to test p(η) ≤ α, where p(η) is the p-value function of η. In [1] a p-value estimator is proposed which is based on ranking some statistic over all data samples, and is shown to be asymptotically consistent. Relying on this framework we propose a new statistic for p-value estimation. It is based on the average of K nearest neighbor (K-NN) distances of η within a K-NN graph constructed from n nominal training samples. We also provide a bootstrapping strategy for estimating p-values which leads to better robustness. We then theoretically justify the asymptotic consistency of our ideas through a finite sample analysis. Synthetic and real experiments demonstrate the superiorities of our scheme.