Source-linked AI summary
Oversampling for Imbalanced Learning Based on K-Means and SMOTE
Felix Last, Georgios Douzas, Fernando Bacao
TL;DR
Class-imbalanced learning is difficult because standard classifiers and accuracy can underrepresent minority performance, while existing oversamplers may be complex or noisy. The paper combines k-means clustering with SMOTE to target useful regions and address multiple imbalance types. Across 71 datasets, k-means SMOTE improves classification and consistently outperforms popular oversampling methods.
Problem
Class imbalance can make accuracy misleading and minority errors costly, while many oversampling methods are complex and may generate unnecessary noise.
Method
The method combines k-means clustering with SMOTE to focus generation on crucial input-space areas, avoid noisy clusters, and allocate more samples to sparse minority clusters.
Results
Across 71 datasets, k-means SMOTE consistently outperforms widely available oversampling methods and improves classification results across evaluated classifiers and metrics.
Takeaways & Limitations
K-means SMOTE provides a simple oversampling approach that improves performance on imbalanced classification problems, especially those that are neither extremely easy nor extremely difficult.
Takeaways & Limitations
The study focuses on binary classification, and guidance for choosing optimal k and other hyperparameters remains an open issue.
Abstract
from arXiv · showhide
Learning from class-imbalanced data continues to be a common and challenging problem in supervised learning as standard classification algorithms are designed to handle balanced class distributions. While different strategies exist to tackle this problem, methods which generate artificial data to achieve a balanced class distribution are more versatile than modifications to the classification algorithm. Such techniques, called oversamplers, modify the training data, allowing any classifier to be used with class-imbalanced datasets. Many algorithms have been proposed for this task, but most are complex and tend to generate unnecessary noise. This work presents a simple and effective oversampling method based on k-means clustering and SMOTE oversampling, which avoids the generation of noise and effectively overcomes imbalances between and within classes. Empirical results of extensive experiments with 71 datasets show that training data oversampled with the proposed method improves classification results. Moreover, k-means SMOTE consistently outperforms other popular oversampling methods. An implementation is made available in the python programming language.
1 Introduction
Class imbalance can make standard accuracy misleading and minority-class errors costly, motivating data-level oversampling. The paper proposes combining k-means with SMOTE to target useful regions while addressing between- and within-class imbalance and noise.
- Motivation: Class imbalance can produce high accuracy while missing every minority instance, as illustrated by fraud detection with 0.1% fraudulent transactions.A classifier labeling all transactions legitimate would score 99.9% accuracy while detecting no fraud.
- Motivation: Minority-class mistakes often cost more than majority-class mistakes, but many classifiers assume uniform misclassification costs.The paper gives database marketing as an example where missing a respondent costs more than mailing to a non-respondent.
- Motivation: Small disjuncts make rules covering few training examples more error-prone, threatening detection of sparse minority patterns.The paper connects this issue to rare combinations of characteristics in credit-card fraud.
- Existing approaches: Data-level methods modify training data and are more versatile than algorithm-level or cost-sensitive methods because they can be applied independently of a classifier.Oversampling adds minority instances through duplication or generation, whereas undersampling risks losing important concepts.
- Existing approaches: Existing oversamplers include effective methods such as SMOTE, but many variants are complex, address only one weakness, or lack unified practitioner-facing availability.The paper positions simplicity and accessibility as unresolved practical concerns.
- Contribution: The proposed method combines k-means and SMOTE to target effective input-space regions, aiming to address between-class and within-class imbalance while avoiding noisy samples.The approach relies on widely available underlying algorithms and is focused on binary classification, although it could be extended to multiclass problems.
2 Related Work
SMOTE generates minority samples by interpolation, but random selection can ignore sparse minority regions and amplify noise. Related methods target particular regions or imbalance types, motivating more targeted clustering-based oversampling.
- SMOTE: Random oversampling duplicates minority instances, which can encourage overfitting because classifiers may learn replicated observations rather than the underlying distribution.SMOTE instead generates artificial samples to reduce this particular risk.
- SMOTE: SMOTE generates a synthetic minority sample by interpolating a randomly selected minority observation with one of its nearest minority neighbors.The interpolation uses x = a + w × (b − a), where w is randomly chosen in [0, 1].
- SMOTE limitations: Uniformly selecting minority observations lets SMOTE correct between-class imbalance but ignores within-class imbalance and small disjuncts.Dense minority areas may be inflated further while sparse areas remain sparse.
- SMOTE limitations: SMOTE may amplify noise by interpolating a noisy minority sample located among majority instances with its nearest minority neighbor.The method does not distinguish overlapping class regions from safe areas.
- SMOTE limitations: SMOTE does not specifically enforce the decision boundary, assigning equal sampling probability to observations near and far from the class border.Some extensions therefore target minority instances close to the boundary.
- Related methods: SMOTE extensions variously emphasize class regions, combat within-class imbalance, or avoid noise, while clustering-based alternatives differ in complexity and targeting.Examples include borderline-SMOTE, Cluster-SMOTE, A-SUWO, SOMO, CURE-SMOTE, and cluster-based oversampling.
3 Proposed Method
K-means SMOTE combines clustering with SMOTE to target safe, minority-dominated regions and allocate more synthetic samples to sparse minority areas. The method addresses between-class and within-class imbalance while avoiding noise and encompassing SMOTE and random oversampling as limit cases.
- Algorithm: More synthetic samples are assigned to clusters where minority instances are sparsely distributed, helping combat within-class imbalance and small disjuncts.Sampling weights are based on cluster sparsity, so low minority density yields more generated samples.
- Algorithm: K-means SMOTE clusters the entire dataset, filters minority-dominated clusters, weights them by minority sparsity, and applies SMOTE within each selected cluster.Its three stages are clustering, filtering, and oversampling; selected clusters receive samples according to their sampling weights.
- Algorithm: Clusters with at least 50% minority samples are selected by default, while the imbalance ratio threshold controls how selective cluster filtering is.Increasing the threshold requires a higher minority proportion; lowering it permits clusters with a higher majority proportion.
- Algorithm: For each filtered cluster, density uses minority counts and mean pairwise minority distance, which is inverted into sparsity and normalized into sampling weights.The density calculation uses the average minority distance raised to the number of features m.
- Algorithm: Unsupervised clustering of all observations can reveal overlapping class regions and help avoid unsafe oversampling areas, unlike methods clustering only minority instances.The method also differs by distributing samples according to cluster density rather than cluster size.
- Limit Cases: SMOTE and random oversampling are limit cases of k-means SMOTE, so their configurations can serve as fallbacks during hyperparameter search.This containment means the method can perform at least as well as the better of those two oversamplers under the stated search strategy.
4 Research Methodology
The methodology evaluates oversampling through classifier performance on unseen data, using cross-validation and metrics suited to imbalanced classification. It benchmarks methods across classifiers and controlled oversampling settings.
- Evaluation framework: Oversampling effectiveness is assessed indirectly by comparing classifiers trained on resampled data with the same classifiers trained on original data.This also enables ranking multiple oversampling techniques by classifier performance.
- Evaluation framework: Cross-validation repeatedly trains classifiers on one data portion and evaluates them on the remaining portion to reduce bias from arbitrary splits.Repeated k-fold cross-validation can further reduce bias from random grouping.
- Evaluation framework: Stratified cross-validation is needed because random folds can distort minority-class representation, potentially leaving test sets without minority instances.Such folds can make evaluation ill-defined or strongly biased.
- Metrics: Sensitivity measures minority-class recall, specificity measures majority-class recall, and precision measures the correctness of positive predictions.These metrics distinguish different aspects of classification quality in imbalanced data.
- Metrics: The F1-score combines precision and recall, while g-mean combines sensitivity and specificity with equal importance.G-mean produces a single value in [0, 1].
- Metrics: The evaluation uses unweighted metrics because no single classification aspect should determine a general oversampler ranking.Metric choice otherwise depends on the practical goal, such as prioritizing false negatives in medical diagnosis.
- Experimental framework: Several classifiers, including logistic regression, k-nearest neighbors, and gradient boosting, are used to reduce dependence on one classifier.Logistic regression also provides a reproducible baseline, whereas KNN and GBM represent alternative model structures.
5 Experimental Results
Across classifiers and evaluation metrics, k-means SMOTE achieved the strongest mean rankings and generally improved scores over SMOTE across the 71 datasets. The gains were statistically significant and were especially pronounced for KNN and moderately difficult classification problems.
- Statistical significance: At a 0.05 significance level, Friedman tests rejected chance differences in oversampler ranks for every evaluated classifier and metric.The ranking analysis used five repetitions and aggregated ranks across datasets.
- Mean rankings: Mean ranks showed k-means SMOTE outperforming the other evaluated oversamplers across all evaluation metrics and independently of classifier choice.It ranked better than two in six of nine classifier–metric combinations and was the only method ranking better than three for F1 and AUPRC.
- Score improvements: KNN showed the largest gains from k-means SMOTE, exceeding 0.2 in maximum score improvement across all metrics and averaging 0.034 improvement for AUPRC.With one exception, maximum improvements exceeded 0.1 for every classifier–metric combination.
- Cross-classifier pattern: The general improvement trend observed for KNN with AUPRC was also reported for other metrics and classifiers, although absolute scores depended on both choices.Figure 8 presents the KNN–AUPRC combination because it had the largest average benefit.
- Score improvements: K-means SMOTE outperformed SMOTE on most datasets, with no improvement in only 2 of 71 datasets and an average AUPRC gain of 0.034.The largest gains occurred mainly for scores between 0.2 and 0.8, including more than 0.2 on the glass6 dataset.
- Overall findings: Overall, five-repetition 5-fold cross-validation found that k-means SMOTE dominated the evaluated oversamplers, with gains up to 0.26 and benefits for almost all datasets.The authors report that all classifiers benefited from the clustering and sample-distribution procedure.
6 Conclusion
The conclusion presents k-means SMOTE as a simple oversampler that targets safe, sparse minority regions to reduce noise and address both between- and within-class imbalance. Experiments found improved classification across classifiers and metrics, while multi-class extension and hyperparameter guidance remain future work.
- Method and motivation: K-means SMOTE addresses noisy artificial samples and within-minority imbalance by targeting safe, sparse regions of the input space.It clusters the data, oversamples clusters dominated by the minority class, and allocates more synthetic samples to sparse minority clusters.
- Empirical conclusion: Across various classifiers and metrics, k-means SMOTE improved classification over unmodified imbalanced data and consistently outperformed SMOTE, borderline-SMOTE, and random oversampling.The reported results were statistically robust, with the largest gains in problems that were neither extremely difficult nor extremely simple.
- Practical use: The method combines simple, widely available k-means clustering and SMOTE components, and a Python implementation is available for practical use.The authors state that the approach does not require high complexity.
- Potential applications: Because it can rebalance datasets independently of classifier choice, k-means SMOTE may apply to fraud detection, disease diagnosis, and environmental-abnormality detection.These applications are presented as potential areas of impact rather than evaluated deployment settings.
- Scope and future work: The study focuses on binary classification, although the proposed method could be extended to multi-class problems.The authors identify multi-class application as future work.
- Scope and future work: Rules of thumb for selecting k and other hyperparameters are not yet established and require further analysis of dataset properties.The authors propose relating optimal hyperparameters to characteristics of a given dataset.