PaperlayerView exact revision on arXiv

Source-linked AI summary

Self-paced Ensemble for Highly Imbalanced Massive Data Classification

Zhining Liu, Wei Cao, Zhifeng Gao, Jiang Bian, Hechang Chen, Yi Chang, Tie-Yan Liu

arXiv:1909.03500v3cs.LGcs.AIstat.ML

TL;DR

Highly imbalanced, large-scale, and noisy datasets make existing classifiers inaccurate or inefficient, while class overlap and noise compound the imbalance problem. The paper proposes Self-paced Ensemble, which harmonizes classifier-specific hardness through iterative under-sampling to build ensembles. Experiments report robust, efficient performance across challenging synthetic and real-world tasks and compatibility with multiple canonical classifiers.

  • Problem

    Existing learning methods struggle with large-scale, highly imbalanced, noisy data, where minority examples can be ignored and class overlap further degrades classification.

  • Method

    Self-paced Ensemble uses classifier-specific classification-hardness distributions to guide self-paced under-sampling of majority data and construct an ensemble.

  • Results

    SPE consistently outperforms other methods on checkerboard data with 8 classifiers and reports the best performance on tested real-world tasks using 5 classifiers across 4 criteria.

  • Takeaways & Limitations

    SPE offers a computationally efficient framework that is adaptable to canonical classifiers and robust under highly overlapping classes and extreme skew.

  • Takeaways & Limitations

    Existing ensemble-based methods can suffer low efficiency, poor applicability, and noise sensitivity, while distance-based re-sampling can become extremely slow at large scale.

Abstract

from arXiv · show

Many real-world applications reveal difficulties in learning classifiers from imbalanced data. The rising big data era has been witnessing more classification tasks with large-scale but extremely imbalance and low-quality datasets. Most of existing learning methods suffer from poor performance or low computation efficiency under such a scenario. To tackle this problem, we conduct deep investigations into the nature of class imbalance, which reveals that not only the disproportion between classes, but also other difficulties embedded in the nature of data, especially, noises and class overlapping, prevent us from learning effective classifiers. Taking those factors into consideration, we propose a novel framework for imbalance classification that aims to generate a strong ensemble by self-paced harmonizing data hardness via under-sampling. Extensive experiments have shown that this new framework, while being very computationally efficient, can lead to robust performance even under highly overlapping classes and extremely skewed distribution. Note that, our methods can be easily adapted to most of existing learning methods (e.g., C4.5, SVM, GBDT and Neural Network) to boost their performance on imbalanced data.

I. INTRODUCTION

Highly imbalanced, large-scale, noisy data challenge conventional classifiers because imbalance, noise, and class overlap jointly hinder accurate learning. The paper introduces Self-paced Ensemble (SPE), which uses classification hardness to guide self-paced under-sampling and ensemble construction.

  • Motivation: Real-world imbalanced datasets are often massive, noisy, and dominated by majority instances, causing traditional classifiers to overlook the minority class.This affects applications including advertising, fraud detection, medical diagnosis, record linkage, and intrusion detection.
  • Limitations of existing methods: Existing data-level, algorithm-level, and ensemble methods face applicability, computational, overfitting, or underfitting problems on realistic imbalanced data.Distance-based methods may not support categorical or missing-value features; some methods are costly at scale, require expert-set costs, or become sensitive to noise.
  • Proposed perspective: Classification hardness represents how difficult each sample is for a specific classifier and captures information about task difficulties such as noise and class overlap.Hardness distributions are model-specific and avoid reliance on predefined distance metrics.
  • Self-paced Ensemble: SPE iteratively selects informative majority samples using hardness-guided, self-paced under-sampling while retaining easy-sample knowledge to reduce overfitting.The framework first harmonizes hardness contributions across bins, then gradually focuses on harder samples.
  • Framework scope: SPE is designed to boost canonical classifiers including C4.5, SVM, GBDT, and Neural Network while remaining computationally efficient.The paper characterizes SPE as accurate, fast, robust, and adaptive compared with existing methods.
  • Evaluation: The study evaluates imbalance classification with recall, precision, F1-score, G-mean, MCC, and AUCPRC rather than relying on accuracy alone.Experiments report consistent SPE advantages on synthetic and real-world tasks across multiple classifiers and evaluation criteria.

III. LIMITATIONS OF EXISTING METHODS

Existing imbalance-learning methods face efficiency, applicability, and robustness problems on large-scale, noisy datasets. Data-level, algorithm-level, and ensemble approaches each impose limitations that become important in realistic imbalanced tasks.

  • Existing solutions are grouped into data-level, algorithm-level, and ensemble methods.
  • Data-level methods may be unsuitable for categorical or incomplete data and can be computationally expensive at scale.Distance-based methods may not handle categorical features or missing values, while SMOTE and ADASYN incur large computational costs.
  • Algorithm-level methods require task-specific domain expertise and may not balance minority examples effectively for batch-trained neural networks.Cost-sensitive methods depend on predefined cost matrices, while minority samples may appear in only a few training batches.
  • Ensemble methods can suffer from high training cost, poor applicability, and noise sensitivity that leads to underfitting or overfitting.BalanceCascade may overweight outliers in later iterations and deteriorate the resulting ensemble.

IV. CLASSIFICATION HARDNESS DISTRIBUTION

Classification hardness measures sample-level difficulty for a given classifier and captures task difficulty beyond class imbalance. Its distribution reflects class overlap, noise, and classifier-specific behavior, guiding distinctions among trivial, noise, and borderline samples.

  • Classification hardness is computed with a decomposable error function for each sample relative to a trained classifier.The overall error is the sum of individual sample errors, and H may use absolute error, squared error, or cross entropy.
  • Hardness connects imbalance ratio with task difficulty: overlapping classes become substantially harder as imbalance increases, unlike disjoint Gaussian components.
  • Hardness distributions differ across classifiers, so under-sampling can account for the capacity and behavior of the chosen model.The paper contrasts KNN and AdaBoost hardness distributions on the same dataset.
  • Trivial samples contribute little individually but are numerous, whereas noise samples contribute large hardness and can promote overfitting.
  • Borderline samples near the current decision boundary are treated as informative because increasing their importance can improve model performance.

V. SELF-PACED ENSEMBLE

Self-paced Ensemble uses classification hardness to under-sample majority data while harmonizing contributions across hardness levels. A self-paced factor then shifts sampling toward harder samples as training progresses, reducing uninformative or noisy influence.

  • SPE is a framework for massive imbalance classification built around hardness harmonization and self-paced training.
  • Hardness Harmonize: Hardness harmonization partitions majority samples into k hardness bins and selects a balanced subset with equal total hardness contribution per bin.
  • Self-paced Under-sampling: Uniform hardness harmonization can retain too many trivial samples as the ensemble fits the training set, slowing later iterations.

2) Self-paced Factor:

SPE uses classification hardness to divide majority samples into bins and adjusts their sampling through a self-paced procedure. The algorithm updates hardness during ensemble training and progressively emphasizes harder samples.

  • 2) Self-paced Factor:: The self-paced factor α starts at 0 and approaches infinity, gradually shifting emphasis toward harder samples.The tan function controls α’s growth across iterations.
  • 2) Self-paced Factor:: SPE updates hardness values in every iteration to select samples most beneficial for the current ensemble.Each newly under-sampled subset is used to train another base classifier.
  • 2) Self-paced Factor:: The formal algorithm begins with random majority under-sampling so the initial majority subset matches the minority-set size.The first classifier is trained on N′0 ∪ P, where |N′0| = |P|.
  • 2) Self-paced Factor:: SPE partitions the majority set into k hardness-based bins for adaptive under-sampling.The bins are defined using each sample’s classification hardness under the current classifier.
  • 2) Self-paced Factor:: The framework assigns each bin an average hardness contribution and an unnormalized sampling weight.These quantities determine how many majority samples are selected from each bin.

VI. EXPERIMENTS & ANALYSIS

The experiments evaluate SPE on a synthetic checkerboard dataset and compare it with multiple imbalance-learning approaches. The synthetic setup is designed to examine performance in a controlled imbalanced classification task.

  • VI. EXPERIMENTS & ANALYSIS: The experimental study includes one synthetic and five real-world extremely imbalanced datasets.It tests SPE with different base-classifier types and evaluates results using multiple criteria.
  • VI. EXPERIMENTS & ANALYSIS: The synthetic study uses a 4×4 checkerboard dataset containing 16 Gaussian components.The minority and majority sample counts are 1,000 and 10,000, respectively.
  • VI. EXPERIMENTS & ANALYSIS: Fig. 4 illustrates the checkerboard dataset used for the synthetic evaluation.Blue dots denote majority samples and red dots denote minority samples.

1) Setup Details:

The checkerboard experiment compares SPE with conventional classifiers, re-sampling methods, and ensemble baselines using AUCPRC. SPE is evaluated across eight classifiers and consistently outperforms the other methods.

  • 1) Setup Details:: The evaluated imbalance-learning methods include random under-sampling, neighbourhood cleaning, SMOTE, EasyEnsemble, and BalanceCascade.Random under-sampling balances the majority subset to the minority-set size, while SMOTE generates synthetic minority instances.
  • 1) Setup Details:: The comparison includes KNN, decision tree, SVM, MLP, AdaBoost, Bagging, Random Forest, and GBDT.These eight canonical classifiers are used to test the applicability of different imbalance-learning methods.
  • 1) Setup Details:: The checkerboard experiment reports AUCPRC using means and standard deviations over 10 independent runs.The implementations use imbalanced-learn, scikit-learn, LightGBM, and Pytorch packages.
  • 1) Setup Details:: SPE consistently outperforms other methods on the checkerboard dataset with all 8 classifiers.This result is reported for the generalized AUCPRC comparison in Table II.
  • 1) Setup Details:: Distance-based re-sampling performs poorly with specific classifiers, including SMOTE+KNN and Clean+RandForest.The authors attribute this invalidity to ignoring differences in model capacity.
  • 1) Setup Details:: Easy and Cascade are more robust than other comparison methods but remain worse than SPE.The comparison identifies SPE as the strongest ensemble framework in this experiment.

3) Robustness under Class Overlapping:

SPE is tested under different degrees of class overlap while dataset size and imbalance ratio remain fixed. Greater overlap degrades classification, but SPE is reported to resist the later-iteration decline observed for Cascade.

  • 3) Robustness under Class Overlapping:: The synthetic datasets vary overlap by changing the covariance factor from 0.05×I2 to 0.1×I2 and 0.15×I2.A larger covariance factor produces more overlap, while dataset size and imbalance ratio remain unchanged.
  • 3) Robustness under Class Overlapping:: Distributional overlap significantly influences classification performance even when dataset size and imbalance ratio are identical.The comparison tracks AUCPRC on the test set during training.
  • 3) Robustness under Class Overlapping:: As overlap increases, Cascade shows a clearer downward performance trend in later iterations.The authors explain this as Cascade overfitting noise samples.
  • 3) Robustness under Class Overlapping:: SPE alleviates the overlap-related issue by retaining a reasonable proportion of trivial and borderline samples.The visualization contrasts SPE’s training and prediction behavior with Clean, SMOTE, Easy, and Cascade.
  • 3) Robustness under Class Overlapping:: On the checkerboard visualization, Cascade retains many outliers in late iterations, which leads to bad generalization.SPE instead obtains more accurate and robust results by considering the classification-hardness distribution.

1) Setup Details:

The experiments evaluate SPE across real-world datasets, classifiers, resampling baselines, and imbalance metrics. SPE achieves strong performance while using limited data and processing time, whereas alternatives face classifier dependence, information loss, or computational costs.

  • Setup Details: The evaluation covers 5 real-world tasks, 6 imbalance-learning approaches, 5 canonical classifiers, and 4 criteria.The criteria are AUCPRC, F1-score, G-mean, and MCC, with means and standard deviations over 10 runs.
  • Results on Real-world Datasets: SPE demonstrates the best performance on all tested real-world tasks using 5 classifiers over 4 evaluation criteria.
  • Comparison with Resampling Methods: RandUnder and Easy10 suffer from severe information loss and high potential variance on highly imbalanced datasets.Clean and SMOTE can also incur unacceptable computational costs or require unavailable distance metrics.
  • Comparison with Resampling Methods: SPE significantly boosts canonical classifiers while requiring very little training data and short processing time.Model-agnostic resampling can work well with some classifiers but fail with others, reflecting classifier-capacity differences.
  • Comparison with Resampling Methods: On Credit Fraud with IR=578.88:1, straightforward oversampling can deteriorate performance because the minority class is poorly represented and lacks clear structure.

2) Comparison with Ensemble Methods:

SPE is compared with under-sampling and over-sampling ensemble methods using C4.5-based ensembles and varying base-classifier counts. It achieves stronger or competitive results with less training data and more consistent performance, while over-sampling methods require substantially more resources.

  • Comparison with Ensemble Methods: The comparison tests ensemble sizes of 10, 20, and 50 base models, although over-sampling methods require more data and resources per base model.
  • Comparison with Ensemble Methods: SPE significantly outperforms 3 under-sampling ensemble methods over 4 evaluation criteria using the same amount of training data.
  • Comparison with Ensemble Methods: SPE demonstrates competitive performance using around 1/300 of the training data required by 2 over-sampling ensemble methods.
  • Comparison with Ensemble Methods: Over-sampling ensembles generate many synthetic samples, enlarging the training set and increasing the computing resources needed for each base model.Higher imbalance ratios and larger datasets worsen this resource burden.
  • Comparison with Ensemble Methods: Across Credit Fraud and Payment Simulation, SPE maintains desirable and consistent performance across independent runs, while other methods show greater randomness.

3) Robustness under Missing Values:

The robustness experiment evaluates ensemble methods on Credit Fraud after randomly replacing feature values with zero at missingness levels from 0% to 75%.

  • Robustness under Missing Values: Credit Fraud is tested with 0%, 25%, 50%, and 75% of feature values missing in both training and test datasets.Missing values are simulated by randomly selecting feature values and replacing them with meaningless 0.
  • Robustness under Missing Values: The experiment reports AUCPRC performance for 6 ensemble methods under progressively larger missing-value conditions.

4) Sensitivity to Hyper-parameters:

SPE’s sensitivity study varies the number of bins and hardness function on two real-world tasks. The method is robust to these choices, although too few bins can reduce performance.

  • Sensitivity to Hyper-parameters: SPE is robust to different choices of the number of bins and hardness function.
  • Sensitivity to Hyper-parameters: Setting the number of bins below 10 may lead to poor performance because bins determine the detail of the hardness-distribution approximation.
  • Sensitivity to Hyper-parameters: Distance-based resampling can be computationally inefficient and difficult to apply when datasets contain categorical features or missing values.
Loading 1909.03500v3…