# K-Medoids For K-Means Seeding

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Sep 2016.

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

- [JITServe: SLO-aware LLM Serving with Imprecise Request Information](https://mlsanity.com/paper/2504.20068/) (2025)
- [Exact Acceleration of K-Means++ and K-Means|](https://mlsanity.com/paper/2105.02936/) (2021)
- [Fuzzy K-Means Clustering without Cluster Centroids](https://mlsanity.com/paper/2404.04940/) (2024)
- [EMA: Efficient Model Adaptation for Learning-based Systems](https://mlsanity.com/paper/2605.13942/) (2026)

## Abstract (arXiv)

We run experiments showing that algorithm clarans (Ng et al., 2005) finds better K-medoids solutions than the Voronoi iteration algorithm. This finding, along with the similarity between the Voronoi iteration algorithm and Lloyd's K-means algorithm, suggests that clarans may be an effective K-means initializer. We show that this is the case, with clarans outperforming other seeding algorithms on 23/23 datasets with a mean decrease over K-means++ of 30% for initialization mse and 3% or final mse. We describe how the complexity and runtime of clarans can be improved, making it a viable initialization scheme for large datasets.