> ML_LITERATURE // ARTHUR-VASSILVITSKII-2007-KMEANS-PLUS-PLUS_v1.0
k-means++: The Advantages of Careful Seeding
David Arthur, Sergei Vassilvitskii · ACM-SIAM Symposium on Discrete Algorithms (SODA) (2007)
algorithm2007industry-standardthirdPartyReproduced
Principal Contribution
Proposed probabilistic D^2 distance seeding, proving an O(log k) approximation guarantee for k-means clustering.
Operational Relevance
Default initialization technique in scikit-learn, Spark MLlib, and R for fast and reliable clustering convergence.
Assumptions
- Spreading initial cluster centroids proportionally to squared Euclidean distance prevents poor clustering configurations
Limitations
- Sequential initialization requires k passes over the full dataset before Lloyd iterations begin