  We propose a novel non-parametric adaptive anomaly detection algorithm for
high dimensional data based on score functions derived from nearest neighbor
graphs on $n$-point nominal data. Anomalies are declared whenever the score of
a test sample falls below $\alpha$, which is supposed to be the desired false
alarm level. The resulting anomaly detector is shown to be asymptotically
optimal in that it is uniformly most powerful for the specified false alarm
level, $\alpha$, for the case when the anomaly density is a mixture of the
nominal and a known density. Our algorithm is computationally efficient, being
linear in dimension and quadratic in data size. It does not require choosing
complicated tuning parameters or function approximation classes and it can
adapt to local structure such as local change in dimensionality. We demonstrate
the algorithm on both artificial and real data sets in high dimensional feature
spaces.
