Improved Guarantees for k-means++ and k-means++ Parallel
Abstract
In this paper, we study k-means++ and k-means||, the two most popular algorithms for the classic k-means clustering problem. We provide novel analyses and show improved approximation and bi-criteria approximation guarantees for k-means++ and k-means||. Our results give a better theoretical justification for why these algorithms perform extremely well in practice.
k-means++ is the standard way to start k-means clustering and is the default in scikit-learn and MATLAB. Its scalable variant, the default in Apache Spark MLlib, often outperforms it, yet its known guarantees were much weaker. We improved the k-means++ guarantee from 8(ln k + 2) to 5(ln k + 2), gave sharper bi-criteria bounds, and proved new guarantees for the parallel variant.
Following the convention in theoretical computer science, authors are listed alphabetically and contributed equally.
Aravind Reddy
Principal Project Scientist
I work on theoretical machine learning, responsible AI and computer vision.