A Better k-means++ Algorithm via Local Search

Silvio Lattanzi; Christian Sohler

ICML 2019oral76 citations

A Better k-means++ Algorithm via Local Search

Abstract

In this paper, we develop a new variant of k-means++ seeding that in expectation achieves a constant approximation guarantee. We obtain this result by a simple combination of k-means++ sampling with a local search strategy. We evaluate our algorithm empirically and show that it also improves the quality of a solution in practice.

BibTeX

@InProceedings{pmlr-v97-lattanzi19a,
  title = 	 {A Better k-means++ Algorithm via Local Search},
  author =       {Lattanzi, Silvio and Sohler, Christian},
  booktitle = 	 {Proceedings of the 36th International Conference on Machine Learning},
  pages = 	 {3662--3671},
  year = 	 {2019},
  editor = 	 {Chaudhuri, Kamalika and Salakhutdinov, Ruslan},
  volume = 	 {97},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {09--15 Jun},
  publisher =    {PMLR},
  pdf = 	 {http://proceedings.mlr.press/v97/lattanzi19a/lattanzi19a.pdf},
  url = 	 {https://proceedings.mlr.press/v97/lattanzi19a.html},
  abstract = 	 {In this paper, we develop a new variant of k-means++ seeding that in expectation achieves a constant approximation guarantee. We obtain this result by a simple combination of k-means++ sampling with a local search strategy. We evaluate our algorithm empirically and show that it also improves the quality of a solution in practice.}
}