Anomaly Detection with Score functions based on Nearest Neighbor Graphs

Details Anomaly Detection with Score functions based on Nearest Neighbor Graphs Anomaly Detection with Score functions based on Nearest Neighbor Graphs

2009-10-28

arxiv.org/abs/0910.5461v1

Computer Science

Learning

10 pages, 10 figures, accepted by NIPS 2009

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Anomaly Detection with Score functions based on Nearest Neighbor Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Anomaly Detection with Score functions based on Nearest Neighbor Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Anomaly Detection with Score functions based on Nearest Neighbor Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-718553