PaperlayerView exact revision on arXiv

Source-linked AI summary

Anomaly Detection with Score functions based on Nearest Neighbor Graphs

Manqi Zhao, Venkatesh Saligrama

arXiv:0910.5461v1cs.LG

TL;DR

Anomaly detection is challenging when the nominal distribution is unknown and difficult to estimate from limited, high-dimensional data. This paper derives adaptive anomaly scores from nearest-neighbor graphs; the scores are asymptotically optimal at a specified false-alarm level for a nominal-plus-known-density mixture.

  • Problem

    Nominal distributions are often unknown and difficult to estimate reliably from limited, high-dimensional training data.

    Source: §1 · p. 1

  • Method

    The method derives adaptive scores from nearest-neighbor graphs on nominal data and declares anomalies when a score falls below α.

    Source: §1 · p. 1, §2 · p. 3

  • Results

    The detector is uniformly most powerful at a specified false-alarm level when the anomaly density is a mixture of the nominal density and a known density.

    Source: §1 · p. 1

  • Takeaways & Limitations

    The graph-based scores estimate minimum-volume-set volumes, avoiding explicit computation of high-dimensional level sets while retaining optimality guarantees.

    Source: §5 · p. 9

    The formal setup assumes data and nominal support on [0, 1]^d and models anomalies as a mixture with another density.

    Source: §3 · p. 4

Abstract

from arXiv · show

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.

1 Introduction

Because nominal distributions are often unknown and difficult to estimate from limited, high-dimensional data, the paper proposes graph-based scores for anomaly detection. It connects these scores to multivariate p-values and minimum-volume sets, with optimality guarantees under a specified mixture model.

1 Introduction

  • Nominal distributions are often unknown and cannot be reliably estimated from limited training data in high-dimensional settings.The introduction identifies limited sample size and high dimensionality as contributing factors.Source: §1 · p. 1
  • The proposed adaptive, non-parametric detector derives scores from a K-nearest neighbor graph and flags test samples scoring below the desired false-alarm level.The scores map samples to [0, 1].Source: §1 · p. 1
  • Unlike distance-to-neighbor approaches [8], the detector uses global information from the full K-NN graph and has provable optimality properties.Its scores estimate volumes of minimum-volume sets containing the test point, avoiding explicit high-dimensional level-set computation.Source: §1 · p. 2
  • The method is uniformly most powerful at a specified false-alarm level when anomalies follow a mixture of the nominal density and another density.Its score is asymptotically consistent with the proposed multivariate p-value.Source: §1 · pp. 1–2
  • The algorithm scales linearly with dimension and quadratically with data size, adapts to local dimensionality, and needs neither complex tuning parameters nor function approximation classes.It assumes no linearity, smoothness, continuity, or convexity of level sets.Source: §1 · p. 2

2 Anomaly Detection Algorithm: Score functions based on K-NNG

The algorithm constructs neighbor graphs from nominal training data and assigns test points scores based on their relative concentration. Scores below a chosen significance level indicate anomalies; the paper illustrates the procedure and its score behavior on a Gaussian-mixture example.

2 Anomaly Detection Algorithm: Score functions based on K-NNG

  • The setup uses n nominal training points in [0, 1]^d and treats the test point as nominal or as drawn from a mixture with another known density.The section presents the algorithm apart from its statistical analysis.Source: §2 · p. 2
  • The method allows Euclidean or geodesic distances, and coordinate weighting can account for pronounced local-dimensionality changes.Geodesic distance is the shortest distance on the manifold.Source: §2 · p. 2
  • It builds a K-nearest-neighbor graph or an ε-neighbor graph, using each training point's Kth-neighbor distance or ε-graph degree, respectively.These graph quantities form the basis for the test-point scores.Source: §2 · pp. 2–3
  • For an anomaly density that is a mixture of nominal and uniform density, the graph-based scores estimate relative concentration and flag test points whose score is at most α.The algorithm is called Localized p-value Estimation (LPE).Source: §2 · p. 3
  • At α = 0.05, the nominal scores are approximately uniform on [0, 1], while uniform-anomaly scores cluster near zero.The figure illustrates K-LPE with K = 6, 200 nominal training samples, and 150 test points.Source: §2 · p. 3, Figure 1 · p. 3
  • LPE avoids explicit high-dimensional density or level-set estimation by computing scalar scores for test samples.The scores are estimates of multivariate p-values and serve as sufficient statistics for optimal anomaly detection.Source: §2 · p. 4

3 Theory: Consistency of LPE

The theory formulates anomaly detection as testing nominal data against a mixture alternative and connects low multivariate p-values to optimal level-α tests. It then establishes asymptotic consistency of the nearest-neighbor score under stated smoothness conditions.

3 Theory: Consistency of LPE

  • The K-LPE score is shown to be an asymptotically consistent estimator of the multivariate p-value, making low-score thresholding asymptotically optimal.The proof first establishes convergence of the expected estimator, then uses concentration to show convergence of the estimator itself.Source: §3 · pp. 4–5
  • The anomaly alternative is f(η) = (1−π)f0(η)+πf1(η), and the testing objective is to maximize detection power while keeping false alarms at or below α.The nominal density is supported on the unit cube, and the alternative mixing density is also supported there.Source: §3 · p. 4
  • The p-value transformation assumes the likelihood ratio has no non-zero flat spots on any open ball in [0, 1]^d, and its distribution under H0 is uniform on [0, 1].If the support of f0 is a lower-dimensional manifold and f1(η) > 0 while f0(η) = 0, then p(η) = 0 and an anomaly is always declared (low score).Source: §3 · p. 4
  • At false-alarm level α, the paper characterizes a uniformly most powerful test for the nominal-versus-mixture anomaly hypothesis and uses low p-values as its decision rule.For a uniform mixing density, the corresponding acceptance region is a density level set and a minimum-volume set.Source: §3 · pp. 4–5
  • The consistency result assumes bounded Hessian eigenvalues and a positive lower bound for f0 on its support, with a suitable choice of K.The theorem considers i.i.d. nominal training data and an arbitrary test sample in the unit cube.Source: §3 · p. 5
  • For nominal data supported on a lower-dimensional manifold, using the geodesic metric gives faster convergence, with intrinsic dimension d′ replacing d in Δ1.The proof divides the nominal sample to simplify analysis; because neighborhood comparisons are correlated, it uses a concentration-of-measure inequality rather than the ordinary law of large numbers.Source: §3 · pp. 5, 7

4 Experiments

Experiments assess parameter robustness and compare empirical ROC behavior with one-class SVM and a clairvoyant curve, then evaluate LPE on three real datasets.

4 Experiments

  • On Banana, K-LPE consistently outperformed one-class SVM and was relatively insensitive to K=2–12; empirical FA was 0.06 at α = 0.05 and 0.09 at α = 0.08.The comparison uses the empirical ROC curves for n = 400.Source: §4 · pp. 7–8, Figure 2 · p. 8
  • With K = 6, the average empirical ROC improved as n increased from 40 to 160, and at n = 160 it was close to the clairvoyant ROC.The empirical curves average 15 trials.Source: Figure 3 · p. 8, §4 · p. 8
  • Real-data ROC experiments cover Wine, Ionosphere, and USPS; geodesic distance is used for high-dimensional data.The reported feature dimensions are 13, 34, and 256, respectively.Source: §4 · pp. 8–9, Figure 4 · p. 9
  • On USPS, empirical false-positive was 6.1% and empirical false alarm rate was 5.7%, versus OC-SVM FP = 7% and FA = 9% at ν = 5%.Source: §4 · p. 9

5 Conclusion

The conclusion presents a non-parametric anomaly detector that scores test points using a K-nearest neighbor graph and gives computational efficiency with provable optimality guarantees.

5 Conclusion

  • The algorithm uses a K-nearest neighbor graph to score each test point, with scores estimating the volume of the minimum-volume level set containing it.Source: §5 · p. 9
  • The score is a real-valued sufficient statistic for the optimal tradeoff between false alarms and misses, avoiding direct computation of high-dimensional minimum-volume sets.Source: §5 · p. 9
  • Computational cost scales linearly with dimension and quadratically with data size.Source: §5 · p. 9

Related papers

Loading 0910.5461v1…