A Better K-Means++ Algorithm via Local Search

ICML 2019 pp. 3662-3671

/icml/2019/lattanzi2019icml-better/

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.

PDF ICML Semantic Scholar

Cite

Text

Lattanzi and Sohler. "A Better K-Means++ Algorithm via Local Search." International Conference on Machine Learning, 2019.

Markdown

[Lattanzi and Sohler. "A Better K-Means++ Algorithm via Local Search." International Conference on Machine Learning, 2019.](https://mlanthology.org/icml/2019/lattanzi2019icml-better/)

BibTeX

@inproceedings{lattanzi2019icml-better,
  title     = {{A Better K-Means++ Algorithm via Local Search}},
  author    = {Lattanzi, Silvio and Sohler, Christian},
  booktitle = {International Conference on Machine Learning},
  year      = {2019},
  pages     = {3662-3671},
  volume    = {97},
  url       = {https://mlanthology.org/icml/2019/lattanzi2019icml-better/}
}