Abstract
In large-scale machine learning, redundant and noisy data can impede training efficiency and classifier performance. This paper introduces GBABS (Granular-Ball based Approximate Borderline Sampling), a framework designed to prioritize informative samples near class boundaries. By representing data clusters as "Granular-Balls" (GBs) through a restricted diffusion process, the method prevents class overlap and filters noise. Evaluations on 13 benchmark datasets show that GBABS significantly reduces dataset size while enhancing accuracy and robustness against noise with linear time complexity.
Introduction
The paradigm of "more data is better" often encounters diminishing returns due to redundancy and label noise. Data sampling aims to extract a representative subset that preserves the underlying decision boundaries. Borderline samples—those situated at the intersection of different classes—are particularly critical for defining these boundaries. Traditional Granular-Ball Computing (GBC) methods often suffer from overlapping granules and a lack of focus on these borderline regions. This work addresses these gaps by proposing a two-stage framework: Restricted Diffusion-based GB Generation (RD-GBG) and GB-based Approximate Borderline Sampling (GBABS).
Methodology
The proposed framework consists of two primary components:
1. Restricted Diffusion-based GB Generation (RD-GBG)
Unlike standard splitting techniques, RD-GBG "grows" balls from local-density centers using a constrained expansion strategy. A ball expands until it encounters a sample from a different class or the boundary of an existing ball, ensuring non-overlapping coverage that respects the data's geometry. This phase also includes an implicit noise detection mechanism, where low-density centers surrounded by heterogeneous classes are identified as noise.
2. GB-based Approximate Borderline Sampling (GBABS)
Following GB generation, the algorithm identifies "borderline GBs" by examining the neighbors of ball centers across all feature dimensions. If a neighbor belongs to a different class, the ball is marked as borderline. Sampling is then focused on points within these balls that are closest to the class boundary, effectively capturing the most informative regions for the classifier.
Key Insights: Balls over Points
A core innovation is treating the Granular-Ball (defined by a center and radius) as the fundamental computing unit. This shift from point-to-point calculations to ball-based operations achieves linear time complexity, making the approach highly scalable.
By identifying heterogeneous nearest neighbors among ball centers, GBABS pinpoints regions of high uncertainty. Furthermore, the RD-GBG phase naturally filters outliers, as balls require local consistency to form, precluding the need for separate pre-processing steps.
Experimental Results
The framework was evaluated on 13 datasets from UCI and KEEL, ranging from 690 to 58,000 samples and up to 256 features.
- Data Compression: GBABS achieved sampling ratios as low as 29% without sacrificing performance.
- Accuracy Improvements: Using Decision Trees, GBABS outperformed standard random sampling and existing GBC methods on 77% of datasets, with accuracy gains up to 4.49% on the Diabetes dataset.
- Robustness to Noise: In environments with up to 40% class noise, GBABS-based models (e.g., XGBoost, Random Forest) maintained higher stability than competitors, which tended to overfit to noisy points.
- Imbalanced Data Performance: The method consistently achieved high G-mean scores on imbalanced datasets, demonstrating its ability to balance class representation effectively during sampling.
Conclusion
GBABS provides an efficient, linear-time solution for borderline data sampling. By focusing on the most informative regions and inherently handling noise, it offers a robust alternative to traditional sampling methods. Future work will focus on optimizing the framework for extremely high-dimensional spaces where geometric boundary definition becomes more complex.
Summary updated