Fast Anomaly Detection for Streaming Data

Swee Chuan Tan, Kai Ming Ting, Fei Tony LiuIJCAI 2011 · DOI

Introduction

Detecting anomalies in streaming data presents a unique set of challenges characterized by infinite volume, extreme class imbalance, and concept drift. Traditional off-line tools, such as Support Vector Machines (SVMs) or Local Outlier Factor (LOF), are unsuitable for these environments as they require multiple passes over static datasets. Even existing streaming models often struggle with the computational overhead of restructuring trees as new data arrives. This paper introduces Streaming Half-Space-Trees (HS-Trees), an ultra-fast, one-class anomaly detector designed specifically for evolving data streams. By decoupling tree structure from the data distribution, the algorithm achieves constant memory usage and constant amortized time complexity.

Methodology: Streaming Half-Space-Trees

The core innovation of HS-Trees is a data-independent structure. Unlike traditional decision trees that split based on information gain from training data, HS-Trees are constructed by randomly selecting dimensions and bisecting them at the midpoint before any data is processed. This eliminates the most computationally expensive part of tree learning: attribute evaluation.

Visualization of space partitioning and the corresponding HS-Tree structure

Mass-Based Scoring and Adaptation

The algorithm uses "mass" (the number of points in a region) as a proxy for density. The anomaly score for a point $x$ is calculated as $r \times 2^k$, where $r$ is the mass of the node and $k$ is its depth. This normalization allows for density comparisons across different levels of the tree. To handle concept drift, the system maintains a dual-window approach:

  1. Reference Window: Used to score incoming points.
  2. Latest Window: Captures the current distribution.

Once the latest window reaches a predefined size, it replaces the reference window, allowing the model to adapt to shifting patterns without altering the physical tree structure.

Experimental Evaluation

The model was evaluated on several large-scale datasets, including real-world network intrusion data (KDD Cup 99 HTTP & SMTP), forest cover data (COVERTYPE), and artificial datasets with dense anomaly clusters (MULCROSS). To test adaptability, the authors created a concatenated SMTP+HTTP dataset to simulate sudden concept drift.

Key Results and Discussion

Streaming HS-Trees (HSTa) demonstrated exceptional performance across all metrics:

  • Accuracy: HSTa achieved AUC scores comparable to or better than "oracle-informed" Hoeffding Trees. On the HTTP dataset, it reached an AUC of 0.996.
  • Speed: HS-Trees were significantly faster than competitors, typically running 4 to 6 times faster. For instance, processing 567k points in the HTTP dataset took only 48 seconds, compared to 227 seconds for Hoeffding Trees.
  • Adaptability: In drift tests, the updating version (HSTa) maintained high accuracy (AUC 0.996), whereas the non-updating version (HSTn) failed significantly (AUC 0.387).
  • Robustness: The model is remarkably stable regarding hyperparameters. As shown in the evaluation, performance stabilizes quickly once the ensemble size reaches approximately 25 trees.
AUC performance relative to ensemble size and tree depth

Conclusion

Streaming HS-Trees provide a robust solution for high-speed anomaly detection. By utilizing a fixed structure and mass-based scoring, the algorithm ensures constant complexity $O(h)$ per point, where $h$ is tree depth. While the model assumes an initial "work range" for attributes, its efficiency and adaptability make it ideal for real-time systems. Future work may explore semi-supervised scenarios and more sophisticated space-partitioning for extremely high-dimensional data.

Summary updated

BibTeX
@inproceedings{tan2011fast,
  author = {Swee Chuan Tan and Kai Ming Ting and Fei Tony Liu},
  title = {{Fast Anomaly Detection for Streaming Data}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2011},
  doi = {10.5591/978-1-57735-516-8/ijcai11-254},
}
Figure