No More Than 6ft Apart: Robust K-Means via Radius Upper Bounds

Ahmed Imtiaz Humayun, Randall Balestriero, Anastasios Kyrillidis, Richard G. Baraniuk

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

Abstract

Centroid based clustering methods such as k-means, k-medoids and k-centers are heavily applied as a go-to tool in exploratory data analysis. In many cases, those methods are used to obtain representative centroids of the data manifold for visualization or summarization of a dataset. Real world datasets often contain inherent abnormalities, e.g., repeated samples and sampling bias, that manifest imbalanced clustering. We propose to remedy such a scenario by introducing a maximal radius constraint r on the clusters formed by the centroids, i.e., samples from the same cluster should not be more than 2r apart in terms of ℓ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</inf> distance. We achieve this constraint by solving a semi-definite program, followed by a linear assignment problem with quadratic constraints. Through qualitative results, we show that our proposed method is robust towards dataset imbalances and sampling artifacts. To the best of our knowledge, ours is the first constrained k-means clustering method with hard radius constraints. <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sup>
BibTeX
@inproceedings{humayun2022no,
  author = {Ahmed Imtiaz Humayun and Randall Balestriero and Anastasios Kyrillidis and Richard G. Baraniuk},
  title = {{No More Than 6ft Apart: Robust K-Means via Radius Upper Bounds}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2022},
  url = {https://openreview.net/forum?id=b8j-DjTPzKl},
}
Figure