← Back to papers
2019 ICML ICML 2019

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.

🌉 Interdisciplinary Bridge — Machine Learning and Mathematics & Optimization
🧭 Keyword Pioneer — seeding algorithm
🐝 Cross-Pollinator — Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning

Authors

Silvio Lattanzi , Christian Sohler

Topics

Machine Learning > Core Methods > Clustering Mathematics & Optimization > Optimization > Combinatorial Optimization

Keywords

k-means clustering approximation guarantee local search seeding algorithm
Download PDF

Related papers

Bayesian leave-one-out cross-validation for large data 2019
A Block Coordinate Descent Proximal Method for Simultaneous Filtering and Parameter Estimation 2019
EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks 2019
Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously 2019
Improved Convergence for $\ell_1$ and $\ell_∞$ Regression via Iteratively Reweighted Least Squares 2019