💻 computer science

A Relative Probabilistic Density Weighted Granular-Ball Twin Support Vector Machine for Robust Classification

This paper proposes RPDLDGBTWSVM, a robust classification method that enhances Twin Support Vector Machines by generating granular balls from high-density real samples and applying KLIEP-based relative probabilistic density weighting at the granular-ball-center level to improve accuracy and efficiency on complex datasets.

Original authors: Yuxin Qiu, Peiai Zhang, Duxin Deng, Xiaowei Cheng, Zhisheng Li

Published 2026-10-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yuxin Qiu, Peiai Zhang, Duxin Deng, Xiaowei Cheng, Zhisheng Li

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of machine learning, computers are often asked to sort things into categories, such as distinguishing healthy tissue from diseased tissue in a medical scan or separating legitimate bank transactions from fraudulent ones. One of the most trusted tools for this task is a method called the Support Vector Machine. Imagine a computer trying to draw a line between two groups of points scattered on a piece of paper. The classic approach draws a single line that keeps the two groups as far apart as possible. However, a more modern variation, known as the Twin Support Vector Machine, draws two separate lines. One line hugs the first group of points, and the other hugs the second group, leaving a wide gap between them. This approach is often faster and more flexible, but it still faces a significant hurdle when dealing with messy, real-world data.

Real-world data is rarely perfect. It contains errors, outliers, and samples that sit right on the boundary between categories, making it difficult for the computer to decide where to draw the lines. To handle this, researchers often try to simplify the data by grouping nearby points together, treating each group as a single unit rather than thousands of individual dots. This technique, known as granular-ball computing, is like looking at a forest from a distance: instead of counting every single leaf, you see the shape of the trees. While this speeds up the process, previous methods of grouping these points often created artificial centers that did not truly represent the original data, especially when the data was complex or sparse. Furthermore, the way these groups were weighted to handle noise often relied on simple distance measurements that could fail in high-dimensional spaces.

A team of researchers at Jinan University has developed a new approach to solve these specific problems, creating a system they call RPDLDGBTWSVM. Their method improves upon existing techniques by changing how the data groups are formed and how they are valued during the learning process. Instead of calculating a mathematical average to find the center of a group, which can result in a virtual point that doesn't actually exist in the data, their system selects real samples that have a high concentration of neighbors. These real, dense points become the anchors for the groups. Once these groups are formed, the system evaluates how consistent each group is with its own category versus the opposite category. Groups that sit clearly within their own category are given more importance, while groups that are ambiguous or sit near the boundary of the other category are given less weight. This ensures that the computer focuses on the most reliable information and ignores the confusing noise.

The researchers tested this new system on nineteen different datasets, ranging from credit classification and molecular data to medical image analysis. The results showed that their method achieved the highest or tied-for-highest accuracy on eighteen of these datasets, with an average accuracy of 90.39%. In specific cases, such as a dataset involving Parkinson's disease diagnosis, the new method improved accuracy by more than three percentage points compared to the next best alternative. Beyond accuracy, the system proved to be highly efficient. On a large dataset involving spam detection, the new method completed the task in less than a second, whereas older methods took several seconds or even minutes. This speed advantage comes from the fact that the system reduces the number of items the computer needs to process without losing the essential details of the data.

However, the study also identified the limits of this approach. When the data was subjected to severe noise, such as when the features of the data were heavily distorted, the system's ability to compress the data diminished. In one instance involving a Parkinson's dataset with high levels of noise, the system could no longer group the data effectively and had to treat almost every sample individually, which slowed it down and reduced its accuracy. This suggests that while the method is robust against typical errors, it relies on the underlying structure of the data remaining somewhat intact. The researchers also noted that for very small or simple datasets, the benefits of grouping were less pronounced, as the data was already easy to sort.

The theoretical foundation of this work confirms that the new method is mathematically sound. The researchers proved that the approximation error introduced by grouping the data is controlled by the size of the groups; smaller, tighter groups lead to results that are nearly identical to analyzing every single point individually. They also demonstrated that the optimization problems created by their method remain solvable and stable, meaning the computer will not get stuck or produce erratic results. By combining the selection of real, dense data points with a sophisticated way of weighing their importance, this new model offers a more reliable and efficient way for machines to learn from complex, noisy information. It represents a step forward in making machine learning tools more practical for real-world applications where data is rarely clean and perfect.

Technical Summary: A Relative Probabilistic Density Weighted Granular-Ball Twin Support Vector Machine for Robust Classification

1. Problem Statement

Classical Twin Support Vector Machines (TWSVM) construct two nonparallel hyperplanes for binary classification but suffer from high computational complexity when processing large-scale datasets, as they treat individual samples as input units. While Granular-Ball Twin Support Vector Machines (GBTWSVM) address this by replacing point-level inputs with granular-ball-level inputs (clusters of samples), existing methods face two primary limitations:

Inaccurate Data Representation: Most granular-ball generation methods rely on virtual mean centers (e.g., via k-means). These virtual centers may deviate from the original data distribution, particularly in datasets with sparse structures, complex boundaries, or high dimensionality.
Insufficient Weighting Mechanisms: Existing relative-density weighting methods primarily operate at the point level. There is a lack of investigation into distribution-aware weighting mechanisms at the granular-ball-center level, which is crucial for handling noisy samples, outliers, and class-overlapping regions effectively.

2. Methodology: RPDLDGBTWSVM

The paper proposes RPDLDGBTWSVM (Twin Support Vector Machine based on Local Density Granular-Ball Generation and Relative Probabilistic Density weighting). The methodology integrates three core components:

A. Local Density Granular-Ball Generation (LDGBG)

Instead of using virtual mean centers, LDGBG selects real samples with relatively high local densities as granular-ball centers.

Center Selection: Local density is calculated based on the number of neighboring samples and their compactness within a defined neighborhood radius.
Radius Determination: The radius of each granular ball is determined by the distance to the nearest center of a different class (or same class, depending on density), ensuring intra-class compactness and inter-class separability.
Benefit: This approach preserves the original data distribution more accurately than mean-based methods, especially for sparse or non-spherical data.

B. Relative Probabilistic Density (RPD) Weighting

To assign weights to granular balls, the method employs KLIEP (Kullback–Leibler Importance Estimation Procedure) to estimate the relative probabilistic density at the granular-ball-center level.

Mechanism: KLIEP directly estimates the ratio of probability densities between the positive and negative classes ( $r(x) = p_{nu}(x)/p_{de}(x)$ ) without estimating individual densities, avoiding error accumulation.
Weight Assignment: The weight for a granular ball is inversely proportional to its RPD score ( $s_i = 1 / (RPD(c_i) + \epsilon)$ ). Granular balls consistent with the opposite-class distribution (likely boundary, noisy, or mislabeled) receive lower weights, reducing their influence on the classification hyperplane.

C. Optimization Formulation

The proposed model constructs two nonparallel hyperplanes. The optimization problems differ from standard TWSVM in three ways:

Input: Uses granular-ball centers instead of individual samples.
Constraints: Incorporates granular-ball radii into the constraints, ensuring the hyperplanes separate the surfaces of the balls rather than just their centers.
Penalty: Integrates RPD-based weights into the slack-variable penalty terms.

The paper provides theoretical proofs demonstrating that:

The approximation error between the granular-ball-level RPD-weighted loss and the point-level weighted loss is controlled by the granular-ball radii.
The resulting subproblems remain convex and feasible, guaranteeing finite optimal solutions and unique hyperplane parameters.
The model can be extended to nonlinear classification via kernel methods.

3. Key Contributions

Distribution-Aware Framework: A novel framework combining LDGBG, RPD, and TWSVM. It utilizes real high-density samples as centers to reduce deviation from the original data distribution and uses granular balls to reduce input size.
RPD-Weighted Model: The development of a TWSVM variant where KLIEP estimates relative density ratios at the granular-ball level. These weights are integrated into slack penalties and dual variable bounds to mitigate the impact of unreliable granular balls.
Theoretical and Empirical Validation:
- Theoretical analysis establishes the approximation bound and convexity of the model.
- Extensive experiments on 19 datasets (including UCI benchmarks and medical image datasets) demonstrate superior performance in accuracy, computational efficiency, and noise robustness compared to TWSVM, GBTWSVM, GBFTWSVM, RPDGBTWSVM, and RPDTWSVM.

4. Experimental Results

Classification Accuracy: RPDLDGBTWSVM achieved the highest or tied-highest accuracy on 18 out of 19 datasets, with an average accuracy of 90.39%. Significant improvements were observed on datasets like Parkinson (93.13%), Darwin (89.71%), and Mammographic (85.83%).
Computational Efficiency: The method achieved the best average running-time rank. On large datasets like Spambase, it reduced training time from ~14s (RPDTWSVM) to ~0.7s. However, on high-dimensional datasets with weak compression (e.g., Parkinson, Med-Pneumonia), the cost of density estimation remains a factor.
Robustness: Under Gaussian feature noise, the model maintained high accuracy on most datasets. However, on the Parkinson dataset with severe noise ( $t=0.30$ ), the local-density structure was destroyed, leading to a granular-ball ratio of 100% (no compression) and a sharp drop in accuracy, highlighting a limitation under extreme perturbation.
Statistical Significance: The Friedman and Nemenyi tests confirmed that RPDLDGBTWSVM is significantly better than TWSVM, GBTWSVM, GBFTWSVM, and RPDGBTWSVM. Its performance was statistically comparable to RPDTWSVM.

5. Significance and Claims

The paper claims that RPDLDGBTWSVM offers a robust solution for complex, noisy, and large-scale classification tasks by effectively balancing computational efficiency (via granular-ball compression) and model robustness (via local-density centers and distribution-aware weighting).

The authors acknowledge limitations, specifically that the method's efficiency depends on the granular-ball compression ratio. In high-dimensional datasets with complex local structures, the compression may be low, and severe feature noise can degrade the local-density neighborhood structure, causing the granular-ball representation to degenerate toward point-level input. Future work is suggested to focus on adaptive granularity control and more stable density-ratio weighting for severely corrupted data.