PaperlayerView exact revision on arXiv

Source-linked AI summary

A Systematic Study of Online Class Imbalance Learning with Concept Drift

Shuo Wang, Leandro L. Minku, Xin Yao

arXiv:1703.06683v1cs.LG

TL;DR

Online learning with class imbalance and concept drift remains insufficiently studied, especially when both challenges coexist in one-by-one data streams. This paper combines a comprehensive review with experiments across drift types and data settings, finding that adaptive class-imbalance handling is central to prediction and drift detection. It concludes with guidance for designing algorithms that address both issues together.

  • Problem

    Research on online learning rarely studies class imbalance and concept drift together, despite their interaction and the difficulty of learning from single instances.

  • Method

    The paper systematically reviews the field and experimentally compares drift types, detection methods, adaptive resampling, and real-world data performance.

  • Results

    Adaptive class-imbalance techniques were more crucial for online prediction than traditional drift handling in several drift settings, and PAUC-PH with OOB was best overall among tested approaches.

  • Takeaways & Limitations

    Effective algorithms should study class imbalance and concept drift simultaneously and incorporate adaptive imbalance handling alongside drift detection where appropriate.

Abstract

from arXiv · show

As an emerging research topic, online class imbalance learning often combines the challenges of both class imbalance and concept drift. It deals with data streams having very skewed class distributions, where concept drift may occur. It has recently received increased research attention; however, very little work addresses the combined problem where both class imbalance and concept drift coexist. As the first systematic study of handling concept drift in class-imbalanced data streams, this paper first provides a comprehensive review of current research progress in this field, including current research focuses and open challenges. Then, an in-depth experimental study is performed, with the goal of understanding how to best overcome concept drift in online learning with class imbalance. Based on the analysis, a general guideline is proposed for the development of an effective algorithm.

I. INTRODUCTION

Online learning with class imbalance and concept drift is a difficult, underexplored problem because the two issues interact and only one instance may be available at a time. The paper addresses this gap through a systematic review, experiments, and guidelines for effective algorithms.

  • Motivation: Class imbalance and concept drift jointly hinder predictive performance because each can affect how the other is handled.Imbalanced error can weaken drift detection, while changing imbalance rates can make preferential treatment target the wrong class.
  • Research gap: Very little work addresses their coexistence in one-by-one online learning, which is harder than chunk-based learning.Online learners receive only a single instance at a time, limiting both training and adaptation.
  • Research gap: Existing research largely studies posterior-probability drift, while prior-probability changes linked to class imbalance remain overlooked.Most drift detectors are designed for or tested on balanced streams, and few methods address both issues simultaneously.
  • Approach: The paper reviews definitions, categories, evaluations, applications, and current approaches for online class imbalance learning with concept drift.The review is intended to reveal research challenges and gaps in the field.
  • Approach: An experimental study investigates drift-detection challenges, method performance across drift types, and the effects of class-imbalance techniques.The study is organized around three research questions concerning detection, comparative performance, and interactions with resampling.
  • Contributions: The paper derives guidelines for effective algorithms and emphasizes studying the mutual effects of class imbalance and concept drift.Its stated contributions include systematic comparison of approaches and analysis of their advantages and disadvantages.

A. Learning Procedure

Online class-imbalanced learning processes examples sequentially while addressing skewed class distributions and changing data-generating conditions. Its framework separates imbalance detection, drift detection, and adaptive response, while evaluation and resampling must account for online constraints.

  • Online learning receives one example at a time, predicts before observing its true label, then uses that label for evaluation and further training.
  • Class imbalance underrepresents some classes, which can bias learning toward majority classes and produce poorly generalizing or missing minority-class rules.
  • Concept drift is a time-varying data distribution that invalidates the static train-test assumption and requires monitoring and model adaptation.
  • The online class imbalance framework uses three modules: a class imbalance detector, a concept drift detector, and an adaptive online learner.The learner uses information from the first two modules to decide when and how to respond while maintaining performance.
  • 1) Class imbalance:: Time-decayed class size provides an incremental, current-status indicator for identifying minority and majority classes in streams.A forgetting factor emphasizes recent data and weakens the influence of older observations.
  • 1) Class imbalance:: AUC is insensitive to class distribution but cannot directly evaluate online learning without memorizing data, because it requires multiple confusion matrices.

2) Concept drift:

Concept drift can change priors, class-conditional distributions, or posteriors, with different implications for detection and adaptation. Drift handling is commonly divided into active and passive approaches, but evaluation must account for evolving streams and class imbalance.

  • Drift types: Concept drift comprises changes in P(y), p(x | y), or P(y | x), corresponding to prior, class-conditional, and posterior shifts.Prior and class-conditional changes are virtual drift; posterior change is real drift, while multiple types may coexist.
  • Drift types: Virtual drift can make a learned decision boundary unsuitable without changing the true boundary, so recalibration may be preferable to resetting and retraining.Previous examples may remain valid under virtual drift, unlike real-drift settings where forgetting the old concept can help.
  • Detection approaches: Active approaches detect when drift occurs before acting, whereas passive approaches adapt without an explicit drift trigger.Active methods are generally effective for abrupt drift, while passive methods are generally effective for gradual drift.
  • Evaluation: Artificial drifts enable controlled analysis of drift type and timing, while real-world streams test effectiveness under unknown drifts.Both settings are needed to fully assess drift detection approaches, especially active detectors.
  • Evaluation: Drift detection is evaluated using true detection rate, false alarm rate, and detection delay, which involve explicit trade-offs.A high true detection rate can accompany a high false alarm rate; detection-point histograms summarize all three aspects.
  • Evaluation: Prequential evaluation tests each instance before training, but accumulated measures can hide poor adaptation after a drift.Sliding windows or time-based fading factors reduce the masking effect of historical observations.

III. OVERCOMING CLASS IMBALANCE AND CONCEPT DRIFT SIMULTANEOUSLY

When class imbalance and concept drift occur together, each complicates the treatment of the other. Drift detectors may become less effective under imbalance, while imbalance methods must adapt to changing P(y).

  • Simultaneous challenges: Class imbalance can distort error-based drift detection, while changing P(y) can make previously favored minority-class treatment inappropriate.The combined problem requires methods that address both evolving distributions and skewed class frequencies.

A. Illustrative Applications

Concept drift and class imbalance occur together in many real-world applications. The paper uses three examples to illustrate their different forms.

  • Illustrative applications: The paper presents three real-world application examples to clarify how combined class imbalance and concept drift can arise.The examples are intended to illustrate each type of concept drift.

1) Environment monitoring with P (y) drift:

Environment monitoring illustrates prior-probability drift in an imbalanced stream, while spam filtering and social media analysis illustrate class-conditional and posterior drift. In practice, these drift types may coexist and be difficult to identify in advance.

  • Environment monitoring with P(y) drift: Sensor-fault prediction is imbalanced because faults are costly to obtain, and worsening damage can increase fault frequency, indicating P(y) drift.The example requires timely prediction from high-speed sensor streams.
  • Spam filtering with p(x | y) drift: Spam filtering combines a minority spam class and adaptive adversary behavior, implying possible p(x | y) drift.Spammers may change email content and presentation to evade filtering.
  • Mixed drift: Different drift types often coexist in real-world problems and may be hard to know in advance.In spam filtering, users’ reinterpretation of categories can also produce posterior-probability change.

B. Approaches to Tackling Both Class Imbalance and Concept Drift

Existing approaches address the joint problem through active drift detection, passive adaptation, ensembles, and resampling. However, true online processing remains difficult because only one example is available at a time, and most approaches do not explicitly handle P(y) drift.

  • Uncorrelated Bagging balances training data through resampling and addresses concept drift passively with weighting.
  • Chunk-based methods are unsuitable for online processing, where minority-class statistics must be estimated from one example at a time.
  • DDM-OCI detects drift by monitoring minority-class recall, whereas LFR monitors four confusion-matrix rates with statistically supported bounds.
  • PAUC-PH uses prequential AUC as a drift indicator, but requires access to historical data.
  • RLSACP and ONN passively adapt perceptron models using forgetting functions and error weighting for class imbalance.
  • ESOS-ELM combines resampling with performance-based voting weights adjusted using G-mean on separate validation data.
  • CID tracks real-time class proportions to identify changes in minority and majority classes, explicitly targeting P(y) drift.
  • Adaptive time-decayed class sizes can determine resampling rates for online ensembles such as OOB and UOB.

IV. PERFORMANCE ANALYSIS

The paper evaluates how concept-drift detection operates under class imbalance, comparing drift types and the effects of class-imbalance techniques on online prediction.

  • The experimental analysis examines difficulties in detecting each type of concept drift in imbalanced data streams.

A. Data Sets

The experiments combine artificial streams with controlled drift types and speeds and real-world streams with unknown drift. Multiple online algorithms are compared using imbalance-insensitive prequential metrics and significance testing.

  • Data Sets: SINE1 and SEA generate imbalanced streams containing P(y), p(x | y), and P(y | x) drift types.
  • Data Sets: Each artificial generator includes abrupt and gradual drift, distinguished by how quickly the new concept replaces the old one.
  • Data Sets: The real-world evaluation uses PAKDD credit-card, Weather, and UDI TweeterCrawl data with different tasks, imbalance levels, and temporal settings.
  • Experimental and Evaluation Settings: Ten algorithms are compared, including OB, OOB, active-detector combinations, RLSACP, and ESOS-ELM, with OB as the baseline.
  • Experimental and Evaluation Settings: Prequential recall and G-mean are tracked because they are insensitive to imbalance rates.
  • Experimental and Evaluation Settings: Average recall and G-mean are computed before and after drift, with values reset at drift boundaries for analysis.

C.1. P (y) Concept Drift

For P(y) drift, active detectors are highly sensitive to imbalance changes, while adaptive resampling can maintain predictive performance without additional drift detection. False alarms from mismatched detectors can instead cause resetting and performance loss.

  • P(y) Concept Drift: The P(y) streams include severe minority-majority reversal in SINE1 and SINE1g and a balanced-to-imbalanced transition in SEA and SEAg.
  • P(y) Concept Drift: DDM-OCI and LFR achieve high detection sensitivity to P(y) changes, while PAUC-PH reports 0% TDR in all cases.
  • P(y) Concept Drift: Oversampling in OOB increases DDM-OCI’s probability of reporting drift by improving minority-class performance for detection.
  • P(y) Concept Drift: ESOS-ELM achieves the best minority-class recall but sacrifices majority-class recall, especially on SINE1 and SINE1g.
  • P(y) Concept Drift: OOB and OOB with PAUC-PH achieve the best G-mean, indicating the strongest balance between class performances.
  • P(y) Concept Drift: DDM-OCI and LFR can trigger false alarms that cause excessive resetting and predictive-performance loss.
  • P(y) Concept Drift: The study concludes that adaptive resampling in OOB is sufficient for P(y) drift, whereas unsuitable active detectors can be detrimental.
  • P(y) Concept Drift: On the new concept, OB models can reach minority-class recall of 0 on SINE1 and SINE1g.

C.3. P (y | x) Concept Drift

The study evaluates online learners under P (y | x) concept drift, using artificial and real-world streams to compare drift detectors, imbalance handling, and predictive performance. Results indicate that real concept drift can sharply reduce performance, while adaptive imbalance handling and active detection help selectively, especially in fast-changing streams.

  • Artificial data: The artificial streams fix the imbalance ratio at 1:9 and compare concept-swap and threshold-moving changes under P (y | x) drift.SINE1 and SINE1g use concept swaps, whereas SEA and SEAg use threshold movement; the latter is less severe.
  • Drift detection: DDM-OCI and LFR detect drift poorly with OB but achieve detection rates above 90% in most cases with OOB.OOB improves recall and G-mean, which facilitates detection; LFR is more sensitive but produces higher false alarms and shorter detection delay.
  • Drift detection: PAUC-PH achieves 100% TDR with OB on SINE1 and SINE1g but performs poorly with OOB, showing that oversampling does not consistently improve drift detection.The analysis suggests imbalance techniques can sometimes hide performance drops caused by real concept drift.
  • Prediction performance: OB produces very low minority-class recall and G-mean on the new concept, while models solely addressing class imbalance achieve the best recall and G-mean.The authors note that the 1:9 imbalance ratio may contribute and identify P (y | x) drift as the most performance-reducing change.
  • Real-world data: On real-world data, OOB and PAUC-PH have similar G-mean on Weather and PAKDD, whereas ESOS-ELM performs worse overall.The comparison uses time-decayed G-mean with decay factor 0.995 and averages metrics over 100 runs.
  • Real-world data: PAUC-PH+OOB improves G-mean over OOB alone on Tweet, where topic changes are faster and more noticeable than the gradual changes in PAKDD.PAUC-PH detects three drifts in PAKDD without much difference in prediction, but active detection is more beneficial on the faster-changing Tweet stream.

E. Further Discussions

The discussion concludes that class imbalance and concept drift must be handled jointly, because imbalance status strongly affects prediction and drift detection. The preferred design depends on drift type and detector behavior, with adaptive imbalance handling central to effective learning.

  • Overall findings: Class imbalance status and changes are more crucial to online prediction than traditional concept drift, making adaptive techniques such as OOB necessary alongside drift detectors.The paper warns that most existing work does not consider how imbalance techniques affect final prediction and drift detection.
  • Drift types: P (y | x) drift is the most severe change, yet existing detectors provide little performance improvement across the three drift types.Detection is difficult without imbalance handling, and detector performance depends on the imbalance technique and detection mechanism.
  • Drift types: For P (y) drift, detectors not designed for imbalance changes can cause false alarms and model resets, so imbalance changes should be detected and handled promptly.The discussion specifically recommends avoiding unsuitable traditional detectors in this setting.
  • Real-world drift: For fast and significant real-world drift, applying PAUC-PH appears more beneficial to prediction performance.The reported benefit depends on the type and speed of concept drift.
  • Method comparison: Passive methods such as ESOS-ELM and RLSACP generally perform poorly because their imbalance handling is not sufficiently adaptive and their classifiers impose additional limitations.ESOS-ELM also requires initialization and validation data reflecting the correct concepts, while weighted OS-ELM can overemphasize the minority class and show large variance.
  • Method comparison: DDM-OCI and LFR are more sensitive than PAUC-PH, achieving higher detection rates but also producing more false alarms; OOB can substantially improve their detection performance.The trade-off motivates algorithms that account for the mutual effects of imbalance handling and drift detection.

V. CONCLUSION

This paper presents a systematic review and empirical study of online learning with simultaneous class imbalance and concept drift. Across drift types and methods, adaptive imbalance handling is especially important, while PAUC-PH combined with OOB performs best overall on minority recall and G-mean.

  • Contribution: The paper provides the first systematic study of concept drift in class-imbalanced data streams through a review and online-learning experiments.It frames the combined problem as distinct from studying imbalance or drift separately.
  • Review: The review identifies limited systematic treatment of P (y) drift and notes that most drift detectors are designed for or tested on balanced streams.It also categorizes the combined challenges, existing solutions, and example applications.
  • Experimental study: The empirical study compares six approaches across P (y), p (x | y), and P (y | x) changes and examines detection, prediction, and imbalance-handling interactions.The study uses artificial data generation and evaluates which methods work best for each drift type.
  • Findings: P (y) changes can be handled by adaptive imbalance techniques, whereas P (y | x) changes are the most challenging and traditional detectors add little performance improvement.For p (x | y) changes, adaptive imbalance handling alone can effectively improve prediction.
  • Findings: PAUC-PH combined with OOB is the best overall approach among the compared methods based on minority-class recall and G-mean.Passive methods perform poorly generally, while DDM-OCI and LFR trade higher detection rates for higher false alarms.
  • Guidance: Adaptive class imbalance techniques are necessary because they deliver the greatest prediction improvement and, in the experiments, help DDM-OCI and LFR detect drift.The paper therefore treats imbalance adaptation as complementary to drift detection.
  • Future work: Future work should develop better drift detection for imbalanced streams, study the mutual effects of imbalance and drift, and expand real-world evaluation across settings.The authors identify these as ongoing challenges for algorithm design.
Loading 1703.06683v1…