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

arXiv: https://arxiv.org/abs/2203.02502 · HTML: https://mlsanity.com/paper/2203.02502/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 24 references that are in the map.
- First posted on arXiv 4 Mar 2022.

## Builds on (most cited first, 8 of 8)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Identifying and Reducing Gender Bias in Word-Level Language Models](https://mlsanity.com/paper/1904.03035/) (2019)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [Fair k-Center Clustering for Data Summarization](https://mlsanity.com/paper/1901.08628/) (2019)
- [How to Solve Fair k-Center in Massive Data Models](https://mlsanity.com/paper/2002.07682/) (2020)
- [Size Matters: Cardinality-Constrained Clustering and Outlier Detection via Conic Optimization](https://mlsanity.com/paper/1705.07837/) (2017)
- [Robust Trimmed k-means](https://mlsanity.com/paper/2108.07186/) (2021)

## Built on by (most cited first, 1 of 1)

- [A Scalable Algorithm for Individually Fair K-means Clustering](https://mlsanity.com/paper/2402.06730/) (2024)

## Abstract (arXiv)

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 ℓ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