Dealing with Multiple Classes in Online Class Imbalance Learning

Shuo Wang, Leandro L. Minku, Xin YaoIJCAI 2016

Introduction

Machine learning models frequently encounter the "double whammy" of multi-class data streams where certain classes are significantly rarer than others. While binary class imbalance is well-studied, real-world scenarios—such as fault diagnosis with multiple distinct failure modes—require handling multiple minority classes simultaneously. In an online learning context, this challenge is exacerbated by the need to adapt to shifting class distributions in real-time without the luxury of processing the entire dataset at once.

This paper introduces MOOB (Multi-class Oversampling-based Online Bagging) and MUOB (Multi-class Undersampling-based Online Bagging), two ensemble-based algorithms designed to adaptively resample data on-the-fly. These methods ensure that rare classes are not ignored by the model, even as the stream evolves.

Methodology: Adaptive Online Resampling

Both MOOB and MUOB build upon the Online Bagging (OB) framework. Standard OB trains an ensemble by presenting each new data point to each model $K$ times, where $K$ follows a Poisson(1) distribution.

The proposed methods introduce a time-decayed class size tracker using a forgetting factor ($\theta$) to prioritize recent data. This allows the algorithms to adjust the Poisson parameter ($\lambda$) dynamically:

  • MOOB (Oversampling): Sets $\lambda$ to the ratio of the largest class size to the current class size. Rare class examples are effectively "seen" more frequently by the learners.
  • MUOB (Undersampling): Sets $\lambda$ to the ratio of the smallest class size to the current class size, reducing the weight of majority examples.

This mechanism allows for strictly online processing while automatically adjusting sampling rates as the stream's distribution shifts, requiring no pre-existing validation set or "warm-up" period.

Experimental Evaluation

The authors evaluated these methods against baseline Online Bagging and aggressive competitors like VWOS-ELM using both synthetic and real-world datasets (e.g., Chess games and Twitter topic prediction). A primary focus was the "Multi-Minority" scenario, where one majority class exists alongside several minority classes ($N_{min}$).

Comparison of recall for minority and majority classes across different algorithms in Multi-Minority scenarios.

As shown in the experimental results, MOOB maintains the most stable performance across varying numbers of minority classes. While baseline OB struggles to identify minority instances as $N_{min}$ increases, MOOB successfully boosts minority recall without catastrophic losses in majority class accuracy.

Key Insights

The "Sacrificial Majority" Problem

A critical finding was that aggressive methods like VWOS-ELM often focus so intensely on minority classes that their accuracy on the majority class collapses. In the "Min5" test (5 minority classes), VWOS-ELM's majority recall plummeted toward zero, whereas MOOB maintained a much healthier balance.

The 'Sacrificial Majority' problem: VWOS-ELM's majority class recall collapses as minority classes increase.

Oversampling vs. Undersampling in Online Streams

While undersampling is often preferred in offline learning for its speed, the authors found that oversampling (MOOB) is superior for online streams. MUOB (undersampling) frequently leads to "insufficient learning" because throwing away majority examples in a single-pass stream results in the loss of information the model has not yet fully mastered.

Complexity of Multi-Minority Scenarios

The study revealed that increasing the number of minority classes is significantly more detrimental to performance than increasing the number of majority classes. Having many distinct "rare" events creates more confusion for the model than having many "common" ones, making the adaptive boosting of MOOB essential for these complex environments.

Conclusion

MOOB provides a robust, "plug-and-play" solution for multi-class imbalanced streams. By adaptively oversampling based on real-time class proportions, it achieves a stable balance between minority and majority class recall, outperforming both standard online bagging and more aggressive undersampling-based alternatives.

Summary updated

BibTeX
@inproceedings{wang2016dealing,
  author = {Shuo Wang and Leandro L. Minku and Xin Yao},
  title = {{Dealing with Multiple Classes in Online Class Imbalance Learning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure