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}$).
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.
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