The effectiveness of lloyd-type methods for the k-means problem

• DOI: 10.1145/2395116.2395117
• Publication Date: 2013-01-08T15:34:16Z
• Authors: Rafail Ostrovsky; Yuval Rabani; Leonard J. Schulman; Chaitanya Swamy
• Keywords: Popularity

We investigate variants of Lloyd's heuristic for clustering high-dimensional data in an attempt to explain its popularity (a half century after introduction) among practitioners, and order suggest improvements application. propose justify a clusterability criterion sets. present that quickly lead provably near-optimal solutions when applied well-clusterable instances. This is the first performance guarantee variant heuristic. The provision on output quality does not come at expense speed: some our algorithms are candidates being faster practice than currently used method. In addition, other instances recently proposed approximation algorithms, while maintaining similar guarantees quality. Our main algorithmic contribution novel probabilistic seeding process starting configuration Lloyd-type iteration.