No More Than 6ft Apart: Robust K-Means via Radius Upper Bounds
  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
