Source-linked AI summary
Combined Cleaning and Resampling Algorithm for Multi-Class Imbalanced Data with Label Noise
Michał Koziarski, Michał Woźniak, Bartosz Krawczyk
TL;DR
Multi-class imbalanced classification remains difficult because noise, overlap, small disjuncts, and complex inter-class relationships limit existing oversampling approaches, while research has largely focused on binary tasks. The paper proposes MC-CCR, combining energy-based oversampling, simultaneous cleaning, and dedicated multi-class handling; benchmark experiments report robustness to label noise and high quality compared with state-of-the-art methods.
Problem
Multi-class imbalanced classification is relatively underexplored despite added difficulty from noise, overlapping distributions, small disjuncts, and complex class relationships that can limit existing oversampling strategies.
Method
MC-CCR combines energy-based modeling of oversampling regions with simultaneous cleaning and an iterative multi-class decomposition strategy using information from previously processed classes.
Results
Benchmark experiments report high robustness to label noise and high quality compared with state-of-the-art methods, with acceptable computational complexity comparable to those methods.
Takeaways & Limitations
MC-CCR supports guided oversampling of multiple classes while using inter-class relationships and local data characteristics to address challenging imbalanced datasets.
Takeaways & Limitations
Existing multi-class imbalance taxonomies do not adequately represent relationships in which a class can be majority, minority, or comparable in size relative to different classes.
Abstract
from arXiv · showhide
The imbalanced data classification is one of the most crucial tasks facing modern data analysis. Especially when combined with other difficulty factors, such as the presence of noise, overlapping class distributions, and small disjuncts, data imbalance can significantly impact the classification performance. Furthermore, some of the data difficulty factors are known to affect the performance of the existing oversampling strategies, in particular SMOTE and its derivatives. This effect is especially pronounced in the multi-class setting, in which the mutual imbalance relationships between the classes complicate even further. Despite that, most of the contemporary research in the area of data imbalance focuses on the binary classification problems, while their more difficult multi-class counterparts are relatively unexplored. In this paper, we propose a novel oversampling technique, a Multi-Class Combined Cleaning and Resampling (MC-CCR) algorithm. The proposed method utilizes an energy-based approach to modeling the regions suitable for oversampling, less affected by small disjuncts and outliers than SMOTE. It combines it with a simultaneous cleaning operation, the aim of which is to reduce the effect of overlapping class distributions on the performance of the learning algorithms. Finally, by incorporating a dedicated strategy of handling the multi-class problems, MC-CCR is less affected by the loss of information about the inter-class relationships than the traditional multi-class decomposition strategies. Based on the results of experimental research carried out for many multi-class imbalanced benchmark datasets, the high robust of the proposed approach to noise was shown, as well as its high quality compared to the state-of-art methods.
1. Introduction
MC-CCR addresses multi-class imbalanced classification by combining energy-based oversampling, guided cleaning, and inter-class relationship modeling. The paper presents benchmark evaluation and computational-complexity analysis supporting its robustness and comparison with state-of-the-art methods.
- 1. Introduction: The paper identifies multi-class imbalance as especially challenging because overlapping classes, noise, outliers, and cross-class effects complicate data-level interventions.Binary decomposition can lose information about relationships among more than one selected class pair.
- 1. Introduction: MC-CCR uses inter-class relationships during artificial instance generation to target minority classes without discarding information through pairwise decomposition.The proposed strategy is designed for multi-class settings where class interactions are more complex than in binary classification.
- 1. Introduction: MC-CCR combines energy-based oversampling, simultaneous cleaning, and dedicated multi-class handling to address noisy, overlapping, and atypical data distributions.The approach targets better placement of synthetic instances while reducing drawbacks associated with SMOTE-based methods.
- 1. Introduction: The contributions include evaluation on diverse benchmark datasets and analysis of computational complexity relative to improvements in handling imbalanced data.The introduction states that the approach is compared with state-of-the-art methods.
- 1. Introduction: The paper is organized around background on noisy and imbalanced multi-class learning, MC-CCR, experimental evaluation, and conclusions with future directions.These sections cover the problem setting, proposed preprocessing method, experiments, and implications.
2. Learning from imbalanced data
Imbalanced classification is especially difficult in multi-class settings because class relationships, overlapping distributions, atypical examples, and label noise interact. Existing approaches include data-level resampling, algorithm-level modifications, binarization, and native multi-class methods, but each has important limitations.
- Data-level methods alter class frequencies through undersampling or oversampling, whereas algorithm-level methods modify learning algorithms using tools such as kernels, tree criteria, or cost-sensitive losses.
- SMOTE generates synthetic minority observations by interpolation, but disjoint distributions, noise, and outliers can cause inappropriate class-distribution changes.
- Multi-class imbalance is complicated by class relationships, overlapping distributions, noise, and outliers that can affect several class boundaries simultaneously.
- Binarization decomposes an M-class problem into M(M −1)/2 one-vs-one or M one-vs-all subproblems, enabling binary classifiers but losing information about class relationships.
- Native multi-class methods exploit complex inter-class relationships but generally require substantial algorithmic changes or novel approaches.
- Multi-class imbalance evaluation uses metrics such as Average Accuracy, Class Balance Accuracy, multi-class G-measure, and Confusion Entropy because ordinary Accuracy favors majority classes.
3. MC-CCR: Multi-Class Combined Cleaning and Resampling algorithm
MC-CCR combines energy-based neighborhood cleaning with targeted oversampling and a dedicated multi-class decomposition strategy. It constrains regions around difficult or noisy minority observations while preserving information from inter-class relationships.
- Binary CCR: Energy-based spheres expand around minority observations until their budget is exhausted, with increasing costs after encountering majority observations.Majority observations inside the resulting sphere are pushed toward its outskirts during cleaning.
- Binary CCR: Smaller spheres constrain cleaning around minority observations surrounded by many majority observations, while broader regions remain available for legitimate outliers and underrepresented areas.The method is designed to distinguish likely mislabeled instances from outliers in overlapping or sparse regions.
- Binary CCR: Synthetic-instance allocation uses sphere radii to emphasize difficult minority observations, with the number generated around each observation determined by relative radius.The weighting is analogous to ADASYN but treats distant outliers differently when their spheres can expand fully.
- Multi-class decomposition: MC-CCR iteratively resamples each minority class using sampled observations from previously processed classes as a combined majority class, then preserves generated instances and cleaning translations.Classes are processed in descending order of size, and the combined majority observations are merged into a binary CCR problem for each class.
- Behavior and comparison: Compared with SMOTE-based alternatives and ENN postprocessing, MC-CCR limits noise-driven overlap without entirely discarding underrepresented regions.The comparison concerns a multi-class dataset containing disjoint distributions and mislabeled observations.
- Computational complexity analysis: The method’s computational cost is analyzed as O((m+log n)n^2) for sphere construction, O(mn) for cleaning, and additional linear work for synthesis.These terms are derived per dataset using feature count m and observation counts summarized by n.
4. Experimental Study
The experimental study evaluates MC-CCR’s parameter choices, comparative predictive performance, classifier flexibility, and robustness to label noise across multi-class imbalanced benchmarks. MC-CCR generally outperformed reference oversampling methods and degraded more gradually as label noise increased.
- 4. Experimental Study: The study evaluated MC-CCR on 20 multi-class imbalanced KEEL datasets selected for challenging characteristics including small disjuncts, borderline and noisy instances, and class overlap.The experiments also compared multiple state-of-the-art oversampling methods and classifiers.
- 4.2. Examination of a validity of the design choices behind MC-CCR: The best-performing configuration combined cleaning by translation, proportional seed selection, and sampling during multi-class decomposition.Across datasets, classifiers, and performance measures, this combination produced the best average performance; omitting cleaning yielded significantly worse results.
- 4.3. Comparison with the reference methods: MC-CCR generally outperformed reference oversampling strategies, achieving the highest average ranks across performance metrics and statistically significant improvements over most methods.The comparison used multiple classifiers, per-dataset analyses, pairwise win-loss-tie results, and statistical tests.
- 4.5. Lessons learned: MC-CCR performed especially well with C5.0 and k-NN, while also producing good results with Naïve Bayes and MLP classifiers.The method was reported as effective on both noisy and noise-free data, with classifier-dependent differences in strength.
- 4.4. Evaluation of the impact of class label noise: MC-CCR showed the smallest predictive-performance decrease as label noise increased or affected more classes, with degradation closer to linear than quadratic.The study examined noise levels from 0% to 25% and evaluated both noise magnitude and the number of affected classes.
5. Conclusion and future works
The paper concludes that MC-CCR is an effective preprocessing framework for multi-class imbalanced classification, combining energy-based oversampling, cleaning, and multi-class decomposition. Experiments support strong comparative performance and robustness to label noise, while future work targets broader cleaning, noise, scalability, and application settings.
- 5. Conclusion and future works: MC-CCR combines energy-based modeling of oversampling regions, simultaneous cleaning, and multi-class decomposition to exploit inter-class imbalance relationships.The framework is intended for multi-class imbalanced classification and uses benchmark experiments to assess its effectiveness.
- 5. Conclusion and future works: The experimental results support MC-CCR’s effectiveness compared with state-of-the-art methods, robustness to label noise, and acceptable computational complexity.The conclusion describes the computational complexity as comparable to state-of-the-art methods.
- 5. Conclusion and future works: Future work includes alternative cleaning regions, other preprocessing methods, different label-noise distributions, feature noise, ensemble integration, large-scale parallelization, and real-world noisy data.The proposed extensions include applications to medical data and evaluation on massive datasets or data streams.