A Better k-means++ Algorithm via Local Search

[edit]

Silvio Lattanzi, Christian Sohler ;
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:3662-3671, 2019.

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.

Related Material