Online anomaly detection via class-imbalance learning

Chandresh Kumar Maurya, Durga Toshniwal, Gopalan Vijendran Venkoparao

TL;DR

This paper introduces OGMEAN, a novel online learning algorithm for anomaly detection that directly optimizes the G-mean metric, a crucial measure for imbalanced datasets. OGMEAN achieves competitive performance with existing methods while offering faster training times and more consistent results across diverse datasets.

What Problem Does This Paper Address?

Anomaly detection is vital in many real-world applications, from fraud detection to healthcare monitoring. A significant challenge in this field is dealing with class-imbalanced data, where anomalies (the minority class) are far less frequent than normal instances (the majority class). Traditional accuracy metrics can be misleading in such scenarios; a classifier that simply predicts everything as normal might achieve high accuracy but completely miss all anomalies. Furthermore, many existing anomaly detection techniques rely on offline training, which is unsuitable for dynamic environments where data arrives sequentially. This paper addresses the need for an online learning approach that effectively handles class imbalance by directly optimizing a metric that accounts for both minority and majority class performance.

Methods

The core of this paper lies in its novel approach to optimizing the G-mean metric within an online learning framework. G-mean is defined as the geometric mean of recall on positive (minority) and negative (majority) classes, providing a balanced measure of performance. The authors first demonstrate that maximizing G-mean is equivalent to minimizing a specific objective function. However, this objective function involves a non-convex indicator function. To overcome this, they propose a convex surrogate loss function, which is a modified hinge loss.

Based on this convex loss, they develop the Online G-mean (OGMEAN) algorithm. OGMEAN operates in an online setting, processing one data point at a time. It makes a prediction, and if incorrect, it updates its model parameters using an online gradient descent approach. A key aspect of their method is that it directly optimizes the G-mean formulation, unlike some prior methods that might use approximations or indirect estimations. They also highlight that their approach avoids explicit regularization, relying on the online learning framework to prevent overfitting.

Datasets

The paper evaluates OGMEAN on several benchmark datasets commonly used for class-imbalance learning. These include:

  • covtype
  • german
  • svmguide3
  • ijcnn1

The paper provides a summary of these datasets, including their size, number of features, and class imbalance ratios, in Table I. No new datasets were introduced.

Key Insights and Ideas

  • Direct G-mean Optimization is Key: The paper strongly suggests that directly optimizing the G-mean metric, rather than relying on approximations or indirect methods (like Laplace estimation used in CSOCsum), leads to better and more consistent performance in online anomaly detection.
  • Convex Surrogate for G-mean: Transforming the non-convex G-mean objective into a convex surrogate loss function is a crucial step that enables efficient online learning.
  • Consistency Matters: A significant finding is that while some competitive online algorithms perform well on certain datasets, they lack consistency across datasets of varying sizes and characteristics. OGMEAN, however, demonstrates more stable performance.
  • Efficiency Gains: OGMEAN achieves comparable or better results than existing methods like CSOCsum while maintaining running times close to the simpler Perceptron algorithm, indicating significant efficiency improvements.

Key Results

  • Competitive "Sum" Metric Performance: OGMEAN achieves performance on the "sum" metric (a weighted combination of sensitivity and specificity) that is equal to or better than the recently proposed CSOCsum algorithm across various benchmark datasets.
  • Improved Mistake Rate and Updates: OGMEAN consistently outperforms CSOCsum in terms of mistake rate and requires fewer updates on weights compared to CSOCsum on most datasets.
  • Faster CPU Time: The algorithm demonstrates competitive CPU times, often comparable to or faster than CSOCsum, and significantly faster than many other online learning algorithms.
  • Consistent Performance: Unlike some other online algorithms, OGMEAN shows consistent performance across datasets of varying sizes, highlighting its robustness. For instance, Figure 3 and 4 show that OGMEAN and CSOCsum are more consistent than other algorithms tested.

Limitations and Future Work

  • Multi-class Extension: The authors acknowledge that extending their approach to multi-class anomaly detection is a significant challenge. The G-mean metric for multi-class problems is non-decomposable, which complicates the use of existing optimization techniques. This is identified as a key area for future research.
  • Parameter Tuning: While OGMEAN requires only one parameter (learning rate $\tau$), finding the optimal value might still require some experimentation, though the paper suggests setting it to $1/\sqrt{t}$ or a constant for simplicity.

Summary updated

Abstract

Anomaly detection is an important task in many real world applications such as fraud detection, suspicious activity detection, health care monitoring etc. In this paper, we tackle this problem from supervised learning perspective in online learning setting. We maximize well known Gmean metric for class-imbalance learning in online learning framework. Specifically, we show that maximizing Gmean is equivalent to minimizing a convex surrogate loss function and based on that we propose novel online learning algorithm for anomaly detection. We then show, by extensive experiments, that the performance of the proposed algorithm with respect to sum metric is as good as a recently proposed Cost-Sensitive Online Classification(CSOC) algorithm for class-imbalance learning over various benchmarked data sets while keeping running time close to the perception algorithm. Our another conclusion is that other competitive online algorithms do not perform consistently over data sets of varying size. This shows the potential applicability of our proposed approach.
BibTeX
@inproceedings{maurya2015online,
  author = {Chandresh Kumar Maurya and Durga Toshniwal and Gopalan Vijendran Venkoparao},
  title = {{Online anomaly detection via class-imbalance learning}},
  booktitle = {IC3},
  year = {2015},
  url = {https://openreview.net/forum?id=Xq4wV9Gfp4},
}
Figure