Source-linked AI summary
Radial-Based Undersampling for Imbalanced Data Classification
Michał Koziarski
TL;DR
Data imbalance and difficult dataset structures challenge traditional classifiers and can limit SMOTE-based resampling. This paper extends mutual class potential from RBO to propose RBU, reporting reduced complexity and comparable performance to RBO, especially with decision trees and difficult datasets.
Problem
Data imbalance biases traditional classifiers toward the majority class, while small disjuncts, outliers, and few minority observations limit SMOTE-based methods.
Method
The paper proposes Radial-Based Undersampling, ranking majority observations by mutual class potential and removing them in decreasing-potential order.
Results
RBU has reduced computational complexity, achieves performance comparable to RBO, and performs statistically significantly better when combined with decision trees.
Takeaways & Limitations
RBU is a computationally efficient alternative to RBO whose observed usefulness is strongest on difficult datasets and in combination with decision trees.
Takeaways & Limitations
The undersampling selection criterion is relatively simple, motivating further development of theoretically motivated mutual-class-potential criteria.
Abstract
from arXiv · showhide
Data imbalance remains one of the most widespread problems affecting contemporary machine learning. The negative effect data imbalance can have on the traditional learning algorithms is most severe in combination with other dataset difficulty factors, such as small disjuncts, presence of outliers and insufficient number of training observations. Aforementioned difficulty factors can also limit the applicability of some of the methods of dealing with data imbalance, in particular the neighborhood-based oversampling algorithms based on SMOTE. Radial-Based Oversampling (RBO) was previously proposed to mitigate some of the limitations of the neighborhood-based methods. In this paper we examine the possibility of utilizing the concept of mutual class potential, used to guide the oversampling process in RBO, in the undersampling procedure. Conducted computational complexity analysis indicates a significantly reduced time complexity of the proposed Radial-Based Undersampling algorithm, and the results of the performed experimental study indicate its usefulness, especially on difficult datasets.
1. Introduction
Data imbalance biases traditional classifiers toward the majority class, especially when difficult dataset factors are present. The paper proposes Radial-Based Undersampling and reports lower complexity with comparable performance to RBO.
- Motivation: Imbalanced data can bias traditional classifiers toward the majority class at the expense of minority-class discrimination.Small disjuncts and insufficient training observations can further worsen performance and contribute to overfitting.
- Motivation: Data-level approaches address imbalance by increasing minority observations through oversampling or reducing majority observations through undersampling.
- Motivation: SMOTE-based neighborhood methods can be susceptible to small disjuncts, outliers, and small numbers of minority observations.RBO was previously proposed to mitigate some of these limitations.
- Contributions: The paper extends mutual class potential from RBO to undersampling to preserve potential-guided performance gains while reducing computational complexity.
- Contributions: RBU is proposed, analyzed computationally, examined across parameter settings, and evaluated against diverse datasets and state-of-the-art data-level reference algorithms.
- Results: RBU achieved performance comparable to RBO and statistically significantly better results when combined with decision trees.
2. Related Work
Related work frames resampling as the selection of regions for generating or removing observations. Existing methods differ in how they handle difficult minority distributions, information loss, overfitting, computational cost, and classifier-specific behavior.
- Neighborhood-based oversampling: SMOTE generates minority instances by interpolating observations with randomly selected nearest minority neighbors.
- Guided undersampling: Guided undersampling methods identify redundant or low-confidence observations, using cleaning heuristics, clustering, or ensemble-oriented selection strategies.
- Resampling trade-offs: Undersampling risks discarding valuable information, whereas oversampling risks classifier overfitting and increased training cost on enlarged datasets.
- Resampling trade-offs: Resampling performance depends on the classifier and dataset conditions; for example, undersampling outperformed SMOTE with C4.5 in one cited study, while random undersampling performed best at high noise levels in another.
- Applicability: Because no single method is expected to perform best on every dataset, identifying conditions of applicability remains important.
- Minority object types: Minority objects can be categorized as safe, borderline, rare, or outlier according to the proportion of same-class neighbors.
3. Radial-Based Undersampling
RBU uses mutual class potential to rank majority observations for removal, extending RBO’s radial approach from oversampling to undersampling. Its total complexity is O(mn^2), compared with RBO’s O(imn^2).
- Potential estimation: Mutual class potential assigns signed Gaussian radial basis functions to observations, with positive polarity for majority and negative polarity for minority objects.Its value indicates the local affiliation of a point to either class.
- Potential estimation: RBO uses mutual class potential to locate low-absolute-potential regions for generating synthetic minority observations.The approach was intended to reduce majority bias and move the decision border toward the minority class.
- Computational complexity: RBO was computationally expensive because it recalculated class potential at every optimization step, limiting applicability to very large datasets.
- RBU procedure: RBU assumes majority observations with the highest potential are least informative and most redundant, then removes them in decreasing-potential order.Potential values for remaining observations are updated after each removal.
- RBU procedure: RBU takes majority and minority collections plus radial-function spread γ and an undersampling ratio, returning an undersampled majority collection.
- RBU procedure: RBU’s implementation initializes potentials, repeatedly removes the highest-potential majority object, updates remaining potentials, and stops at the requested ratio.
- Computational complexity: O(mn^2) is the simplified total complexity of RBU when balancing the classes.The comparison passage gives RBO complexity as O(imn^2), where i is the number of algorithm iterations.
4. Experimental Study
The study evaluates RBU through parameter analysis, comparisons with reference resampling methods, and dataset-characteristic analysis. Performance depends on classifier, metric, parameters, and minority-object composition, with strongest results generally for NB and difficult datasets under several classifiers.
- Parameter analysis: Increasing the undersampling ratio generally improved recall while reducing precision, but the best combined-metric ratio depended on the classifier and metric.Complete undersampling was favorable for AUC and G-mean, whereas F-measure favored lower or intermediate ratios and never favored complete undersampling.
- Parameter analysis: Smaller γ values in {0.001, 0.01, 0.1} produced the best performance across classifiers and evaluation metrics.Higher γ values either failed to improve average performance or significantly reduced it; γ also affected the precision–recall trade-off differently across classifiers.
- Comparison with other methods: RBU performed best with NB, and comparatively well with CART and SVM, while KNN produced the weakest comparison results.RBU significantly outperformed at least one reference method for 10 of 17 methods with NB, 6 with CART, and 7 with SVM; with KNN, all SMOTE variants and NCL significantly outperformed RBU.
- Comparison with other methods: Compared with RBO, RBU differed significantly only with CART, where it achieved significantly better AUC and G-mean.The largest remaining rank difference favored RBO with SVM, but it was not statistically significant.
- Dataset characteristics: With CART, KNN, and SVM, RBU suited datasets containing many rare or outlier minority objects but performed relatively worse on safe datasets.For NB, performance patterns differed: AUC and G-mean were significantly worse with many outliers, while AUC was significantly better with many borderline minority objects.
5. Conclusions
RBU is a computationally efficient mutual-class-potential undersampling method whose usefulness varies by classifier and dataset composition. It performs especially well with Naive Bayes and on datasets containing more rare and outlier minority instances, while its simple selection criterion remains open to refinement.
- Contributions: RBU is a novel undersampling algorithm based on mutual class potential and offers a computationally more efficient alternative to RBO.The paper frames RBU as an extension of non-nearest-neighbor resampling from oversampling to undersampling.
- Applicability: RBU was most suitable with Naive Bayes, and comparatively suitable with CART and SVM.The conclusion identifies Naive Bayes as the strongest applicability setting, with CART and SVM providing lesser suitability.
- Comparison with RBO: RBU achieved statistically significantly better performance than RBO when combined with a CART decision tree.
- Dataset characteristics: RBU achieved comparatively better results on difficult datasets with a higher proportion of rare and outlier minority instances.Table 3 relates minority-object proportions to RBU rank, where negative correlations indicate increasing performance.
- Future development: The proposed undersampling selection criterion is relatively simple, motivating further exploration of theoretically motivated mutual-class-potential criteria.