No More Than 6ft Apart: Robust K-Means via Radius Upper Bounds
This addresses the issue of obtaining representative centroids for visualization or summarization in exploratory data analysis, particularly for datasets with abnormalities like repeated samples and sampling bias, though it is incremental as it builds on existing centroid-based clustering methods.
The paper tackles the problem of imbalanced clustering in real-world datasets by proposing a k-means method with a hard maximal radius constraint to ensure samples in the same cluster are within a specified distance, showing robustness to dataset imbalances and sampling artifacts.
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 $\ell_2$ 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. Codes at https://bit.ly/kmeans-constrained