Abstract
Standard K-means clustering often fails in the presence of sampling bias, as centroids naturally drift toward high-density regions, leaving sparse but significant areas of the data manifold poorly represented. This paper proposes a robust alternative that enforces a hard radius constraint on every cluster. By formulating the problem as a Mixed Integer Semi-Definite Program (MISDP) and utilizing a convex relaxation, the authors demonstrate a method that ensures geometric coverage across imbalanced datasets. Experimental results on synthetic benchmarks show that this approach maintains balanced representation where standard K-means and cardinality-constrained methods fail.
Introduction
Clustering is a foundational tool in unsupervised learning, yet its most popular implementation—K-means—relies on the assumption that clusters possess similar spatial variance and sample sizes. In real-world scenarios, data often suffers from sampling bias, where certain regions are over-represented. In these cases, K-means centroids tend to "clump" in high-density areas, a phenomenon that can lead to downstream algorithmic bias in sensitive applications like facial recognition or natural language processing.
While previous attempts to mitigate this have focused on cardinality constraints (limiting the number of points per cluster), these methods typically require prior knowledge of the underlying data distribution. This paper introduces a geometric solution: limiting the physical size of the clusters. By ensuring no two points in a cluster are further than a specified distance apart, the algorithm is forced to distribute centroids more equitably across the entire data manifold.
Methodology
The authors redefine the K-means objective as a constrained optimization problem centered on a radius parameter $r$.
1. Hard Radius Constraint
The core innovation is the requirement that for any cluster, the maximum distance between any two points (the diameter) must not exceed $2r$. This prevents a single cluster from expanding to absorb distant outliers or spanning across low-density gaps to capture multiple distinct modes.
2. Optimization and Relaxation
Because hard-constrained clustering is NP-hard, the authors formulate the task as a Mixed Integer Semi-Definite Program (MISDP). To make the computation tractable for practical use, they apply a semi-definite programming (SDP) relaxation. This transformation converts the discrete point-to-cluster assignment into a continuous space that can be solved efficiently using interior-point methods.
3. Rounding Algorithm
To return to a valid clustering assignment, the continuous solutions from the SDP relaxation are mapped back to binary assignments. This is achieved through a two-step linear assignment process with quadratic constraints, ensuring that the final output respects the original hard radius limits.
Experimental Evaluation
The proposed method was evaluated against several baselines, including standard K-means, K-medoids, K-center, and cardinality-constrained K-means, using synthetic datasets designed to trigger clustering failures.
- Imbalanced Two-Moons: This dataset features two moon-shaped distributions where one contains 85% of the samples and the other only 15%. While standard K-means biased its centroids toward the dense moon, the radius-constrained method successfully assigned an equal number of centroids (8 per moon) to both shapes.
- 1D Synthetic Mixture: Using 102 samples from three uniform distributions of varying densities, the authors showed that their method correctly identified the boundaries between distributions, whereas standard K-means mixed samples from different distributions into single clusters.
Key Insights
The Feasibility Certificate
A significant advantage of this approach is the "feasibility certificate." If the chosen radius $r$ is too small to cover the dataset with $K$ clusters, the optimization returns an empty set. This provides an explicit signal to the user that the current parameters are insufficient to represent the data's geometry, suggesting a need to either increase the radius or the number of clusters.
Quantitative Performance
Quantitative analysis confirms the geometric tightness of the clusters. In comparative testing, the proposed method achieved a "Max Partition Radius" of 0.181, significantly lower than standard K-means (0.228) and K-center (0.224). This indicates that the clusters are not only more representative of the manifold but also more compact and consistent in size.
Limitations and Future Directions
Despite its robustness, the method faces challenges regarding computational scaling. The current MISDP formulation has a complexity of $O(K \cdot N^2)$, where $N$ is the number of data points. This limits its immediate application to massive datasets. Additionally, the selection of the radius $r$ remains a hyperparameter that may require iterative tuning, although the feasibility certificate aids this process.
Future work aims to replace the expensive SDP step with faster initialization techniques, such as a modified K-center approach. Such optimizations could reduce the computational overhead, making radius-constrained clustering a viable option for large-scale industrial data processing where fairness and representation are critical.
Summary updated