Anomaly detection and classification for streaming data using partial differential equations

Bilal Abbasi, Jeff Calder, Adam M. ObermanarXiv 2016 · DOI · OpenReview

TL;DR

This paper introduces a novel, real-time anomaly detection and classification system for streaming data by leveraging partial differential equations (PDEs) to approximate complex sorting algorithms. This approach significantly speeds up processing, enabling rapid adaptation to changing data trends, and offers a new method for classifying anomalies based on how they violate different criteria.

What Problem Does This Paper Address?

Detecting anomalies in data streams is crucial for many applications, from cybersecurity to financial fraud detection. Traditional methods often rely on "nondominated sorting" (also known as Pareto Depth Analysis or PDA), which ranks data points based on multiple criteria. While effective, PDA is computationally expensive, especially for streaming data where new points arrive continuously and the underlying data distribution might change over time. This high computational cost makes it difficult to update anomaly detection models in real-time or adapt them to evolving data patterns. The paper addresses this by developing a faster, PDE-based approximation of PDA that can handle streaming data efficiently and adapt to changing trends.

Methods

The core innovation lies in using "PDE continuum limits" to approximate nondominated sorting. The authors build upon existing work that established a PDE continuum limit for nondominated sorting, leading to a fast algorithm called PDE-based ranking. They extend this by:

  • Real-time Streaming Anomaly Detection: Adapting the PDE-based ranking for streaming data by using a sliding window of recent data to estimate the data distribution and then solving the PDE. This allows for O(T) complexity per time step, where T is the window size, a significant improvement over the O(T^2) complexity of exact sorting.
  • New PDE Continuum Limits for Classification: Deriving new PDE continuum limits specifically for ordering points within their nondominated layers (Pareto fronts). This allows for a more nuanced understanding of how anomalies deviate from normal data, enabling classification based on which criteria are most violated.
  • Upwind Finite Difference Schemes: Developing efficient numerical schemes (upwind finite difference) to solve the derived PDEs, ensuring computational tractability.
  • Convergence Analysis: Proving statistical convergence rates for the PDE-based ranking, demonstrating that the approximation error decreases as the sample size increases.

Datasets

The paper evaluates its methods on:

  • Synthetic Data:
    • Uniformly distributed data: Used to test anomaly detection and classification with changing trends.
  • Categorical data: Used to test anomaly detection and classification with changing categorical distributions.
  • Real-World Data:
    • Pedestrian trajectory data: A large dataset used to evaluate the streaming anomaly detection algorithm on real-world scenarios.

The paper does not introduce new benchmark datasets but uses existing synthetic data setups and a real-world dataset commonly used in anomaly detection research.

Key Insights and Ideas

  • PDEs as a Shortcut for Complex Sorting: The paper demonstrates that PDEs can effectively capture the asymptotic behavior of complex algorithms like nondominated sorting, offering a computationally cheaper alternative.
  • Ordering Within Pareto Fronts for Classification: The novel PDE continuum limits for ordering points within Pareto fronts are a key contribution. This allows for a richer understanding of anomalies beyond just their "depth" (rank), enabling classification based on the nature of their deviation.
  • Real-time Adaptability is Achievable: By combining PDE-based ranking with streaming techniques, the algorithm can adapt to significant trend changes in data streams quickly and efficiently, as evidenced by the rapid recovery of AUC scores.
  • Trade-off Between Exactness and Speed: The PDE-based approach sacrifices perfect accuracy for significant computational gains, which is a crucial trade-off for real-time applications. The convergence analysis shows this trade-off is well-controlled.

Key Results

  • Computational Speedup: The PDE-based approximations reduce the complexity from O(T^2) to O(T) for streaming anomaly detection. For example, processing 1500 samples with a history of T=500 took 27 seconds with PDE approximations versus 413 seconds with exact sorting. This difference becomes even more pronounced with larger datasets and history sizes.
  • Effective Anomaly Detection and Classification: The algorithm achieved performance comparable to exact sorting methods, as shown by similar Area Under the Curve (AUC) values in ROC analyses.
  • Rapid Trend Adaptation: In simulated streams with trend changes, the algorithm showed a sharp recovery in AUC for anomaly detection, demonstrating its ability to learn new data distributions quickly.
  • Statistical Convergence: The paper provides theoretical guarantees on the convergence of the PDE-based ranking to the true continuum limits.

Limitations and Future Work

  • Non-Rigorous Derivations: The authors acknowledge that the derivations of the new PDE continuum limits for sorting within layers are not fully rigorous and are an active area of investigation.
  • Convergence of Numerical Schemes: The convergence of the upwind schemes is proven under assumptions (e.g., exact derivatives, C¹ continuity) that may not always hold in practice. Extending this to more realistic scenarios is a future direction.
  • Higher Dimensions: The new PDE continuum limits for sorting within fronts are currently derived for 2D. Extending these to higher dimensions (d ≥ 3) is a significant area for future research, involving exploring different sorting strategies within fronts.
  • Generalization of Schemes: The numerical schemes for the transport equations are currently analyzed for the case where the underlying PDE solution is C¹. Further work is needed for cases where this assumption does not hold.

Summary updated

Abstract

Nondominated sorting, also called Pareto Depth Analysis (PDA), is widely used in multi-objective optimization and has recently found important applications in multi-criteria anomaly detection. Recently, a partial differential equation (PDE) continuum limit was discovered for nondominated sorting leading to a very fast approximate sorting algorithm called PDE-based ranking. We propose in this paper a fast real-time streaming version of the PDA algorithm for anomaly detection that exploits the computational advantages of PDE continuum limits. Furthermore, we derive new PDE continuum limits for sorting points within their nondominated layers and show how the new PDEs can be used to classify anomalies based on which criterion was more significantly violated. We also prove statistical convergence rates for PDE-based ranking, and present the results of numerical experiments with both synthetic and real data.
BibTeX
@misc{abbasi2016anomaly,
  author = {Bilal Abbasi and Jeff Calder and Adam M. Oberman},
  title = {{Anomaly detection and classification for streaming data using partial differential equations}},
  year = {2016},
  eprint = {1608.04348},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1608.04348},
}
Figure