An Efficient and Adaptive Granular-ball Generation Method in Classification Problem

I. INTRODUCTION

• Granularity trades off efficiency and noise robustness against attention to detail and accuracy, motivating adjustable-granularity classifier inputs.The introduction identifies implementing a multi-granularity classifier as a challenge and proposes granular-balls as a high-dimensional feature representation.Source: §I · pp. 1–2
• The paper proposes division in place of k-means to accelerate granular-ball generation and a purity-adaptive method to remove manual threshold setting.It also presents mathematical models for granular-ball covering.Source: §I · p. 2

A. Granular-ball Computing

• A granular-ball represents a sample group by its center and radius, enabling multi-granularity learning with a compact feature representation.The radius may be the average or maximum distance from the center; the ball can serve as a learning input or measurement of the sample space.Source: A. Granular-ball Computing · p. 3
• Generation starts with the whole dataset as one ball, then splits balls below a purity threshold until the resulting balls meet the requirement.Splitting increases ball purity and makes the decision boundary clearer.Source: A. Granular-ball Computing · p. 3

B. Granular-ball k-Nearest Neighbor

• GBkNN assigns a query the label of its nearest granular-ball, whose majority label is determined adaptively without optimizing k.The number of granular-balls is much smaller than the number of sample points, reducing the nearest-neighbor search computation.Source: B. Granular-ball k-Nearest Neighbor · p. 4

C. Granular-ball Sampling

• GBS selects same-label points closest to coordinate-axis intersections on each ball, yielding sparser samples whose boundary better matches the original than random sampling.Fig. 5 illustrates the original data, generated balls, boundary-point selection, and the resulting sample set.Source: C. Granular-ball Sampling · p. 4, Figure 5 · p. 5
• In label-noise classification, GBS reduces dataset size and improves data quality; it also supports imbalanced-class undersampling and has O(n) time complexity.Source: C. Granular-ball Sampling · p. 5

• Coverage degree measures the share of samples represented by the balls; greater coverage means less information loss and more accurate characterization.Source: §III · p. 5
• Fewer, coarser balls can improve efficiency and robustness, while a quality threshold requires balls to remain fine enough to describe the problem accurately.Source: §III · p. 5
• The formulation uses λ1 and λ2 as the corresponding weight coefficients, with the number of balls m less than the number of samples n.Source: §III · p. 5
• Coverage, ball count, and ball quality are all necessary: omitting quality permits one poor ball, while omitting coverage rate permits balls to represent only a small part of the dataset.Fig. 6 depicts these invalid coverage cases.Source: §III · p. 5, Figure 6 · p. 6

A. Motivation

• Full k-means splitting is inefficient for this task because stable intermediate results are unnecessary; only balls satisfying the required lower bound are needed.Source: A. Motivation · p. 6

B. The Process of the Acceleration Granular-ball Generation Method

• A final global division uses all division points; during splitting, the division point serves as the ball center rather than the center computed by the existing method.Source: B. The Process of the Acceleration… · p. 6
• The method replaces iterative k-means with k divisions, where k is the number of classes in a ball, and reuses the original center to reduce distance computations.The original center remains the center of one child ball, so only k−1 new centers are selected.Source: B. The Process of the Acceleration… · p. 6
• After global division, ball centers move closer to their true centers, points become more tightly and uniformly distributed, and the boundary is clearer; noisy-data boundaries are also fit well.Fig. 9 compares the distributions before and after global division and shows the noisy-data case.Source: Figure 9 · p. 7, B. The Process of the Acceleration… · p. 7

C. Time Complexity

• Each round generates division centers and computes distances between points in the ball and those centers.The algorithm repeats splitting until the number of balls no longer increases, then performs a global division.Source: C. Time Complexity · p. 7
• The method’s total time complexity is O((mn−n+k+1)N), but most granular-balls stop splitting midway, making actual complexity much lower.The final global division costs O(kN).Source: C. Time Complexity · p. 7
• The acceleration method remains linear in time complexity and avoids unnecessary calculations.Source: C. Time Complexity · p. 7

A. Motivation

• The existing purity-threshold parameter does not adapt to each dataset’s distribution, and finding a matching splitting standard is difficult.Source: A. Motivation · pp. 7–8
• The proposed purity-adaptive generation method is based on the acceleration method.Source: A. Motivation · p. 8
• The authors describe purity adaptation as making generation completely parameter-free and note that a parameter-free GBkNN classifier has been developed.Source: A. Motivation · p. 8

B. The Adaptive Conditions of Granular-ball Splitting

• Three conditions govern adaptive splitting: child-ball weighted purity, overlap between heterogeneous balls, and reaching the initial ball’s purity as a lower bound.Source: B. The Adaptive Conditions of… · p. 8

1) Weighed purity sum of child balls:

• The weighted purity sum gives more weight to child balls containing more samples and is compared with the parent ball’s purity to assess splitting.If all child balls share the parent’s label, W equals T; if any child label differs, W is greater than T.Source: 1) Weighed purity sum of child balls · p. 8
• When W exceeds T, minority samples in the parent can become majorities in child balls, increasing the number of correctly classified samples.Source: 1) Weighed purity sum of child balls · p. 8
• Purity-based splitting alone can converge prematurely because accuracy does not increase monotonically when heterogeneous granular-balls overlap.The method adds a condition prohibiting overlap between heterogeneous balls; Fig. 10 illustrates splitting and de-overlap.Source: 1) Weighed purity sum of child balls · p. 9, Figure 10 · p. 9

2) De-overlap between heterogeneous granular-balls:

• After an overlap is found, the method further splits and refines the overlapping balls; later detection checks only their child balls.Source: 2) De-overlap between heterogeneous… · p. 9
• Overlap detection targets heterogeneous granular-balls because overlap between same-class balls does not affect the decision boundary.Source: 2) De-overlap between heterogeneous… · p. 9

3) An adaptive purity lower bound:

• The purity lower bound is the initial granular-ball’s purity, preventing retained granular-balls from falling below that level.The paper describes lower-purity balls as too low in quality and harmful to final GBkNN accuracy.Source: 3) An adaptive purity lower bound · p. 9
• With added label noise, the adaptive method generates granular-balls around the two original classes while treating randomly relabeled samples as noise.The paper illustrates this in Fig. 10(e).Source: 3) An adaptive purity lower bound · p. 9
• The optimization requires each child granular-ball’s quality to exceed T0 and the parent ball’s quality.T0 is the adaptive purity lower bound; W denotes the weighted purity sum of the child balls.Source: 3) An adaptive purity lower bound · p. 9

C. Method Design

• When a split produces children whose weighted purity sum exceeds the parent’s purity and the purity floor is met, the children are retained for overlap checking.The method checks overlap between heterogeneous granular-balls; the converged boundaries are described as consistent with the data-set boundary.Source: C. Method Design · pp. 9–10
• The method uses k-way division, where k is the number of classes in a granular-ball, reducing computation cost directly.It applies the accelerated generation method to each ball to pre-generate k child balls.Source: C. Method Design · pp. 9–10
• Generation repeats until the number of balls stops increasing, then performs a global division and de-overlaps heterogeneous granular-balls.The algorithm starts with the whole data set as one ball and iterates over the current balls.Source: C. Method Design · p. 10

VI. EXPERIMENTS

• The evaluation uses ten real data sets randomly selected from the UCI benchmarks and compares the proposed methods with kNN, GBkNN, and GBS.Experiments use both raw and noise-added data; accuracy is evaluated for both proposed methods, while efficiency is assessed for the acceleration method.Source: §VI · p. 10

A. Experiments on Raw Data Sets

• The proposed methods have higher raw-data accuracy than the existing method and kNN, with global division after splitting stopped cited as the reason.Table I reports average test accuracy under noise-free conditions.Source: A. Experiments on Raw Data Sets · p. 10, Table I · p. 10
• After GBS sampling, the proposed methods achieve higher accuracy on most data sets than the other compared methods.Table II compares average test accuracy after GBS sampling; its first three columns use GBS, while the last directly classifies raw data with kNN.Source: A. Experiments on Raw Data Sets · p. 10, Table II · p. 11
• On raw data sets, the acceleration method improves accuracy and efficiency on most data sets while generating a similar number of granular-balls.The comparison is with the existing granular-ball generation method.Source: A. Experiments on Raw Data Sets · p. 11

B. Experiments on Noise Data Sets

• The adaptive method is slightly less accurate than the existing method on noisy data sets, while making the generation process adaptive.The authors suggest its adaptive purity floor may be too low, producing poor-quality balls that affect overall accuracy.Source: B. Experiments on Noise Data Sets · p. 11
• For noise rates of 10%, 20%, 30%, and 40%, the proposed methods follow a similar pattern to the existing method, with a larger advantage over original kNN at higher noise rates.The adaptive method nevertheless shows slightly lower accuracy than the existing method on noisy data.Source: B. Experiments on Noise Data Sets · p. 11

VII. CONCLUSIONS AND FUTURE WORK

• The authors report that the acceleration method performs better than the adaptive method on both noisy and non-noisy data, but both methods are less accurate than the existing method in some cases.They identify improving accuracy and exploring adaptive optimization based on granular-ball internal-distribution consistency as future work.Source: §VII · p. 11