On Lloyd's Algorithm: New Theoretical Insights for Clustering in Practice
Cheng Tang, Claire Monteleoni · 2016
A paradox for “k-means clustering” k-means objective φ of C = {ci, i ∈ [k]} on a dataset X: φX(C) = x∈X ‖x − C(x)‖2, where C(x) = arg min c∈C ‖x − c‖ Even though approximation algorithms exist, they are rarely used for applications. Instead, a few heuristics, most notably Lloyd’s algorithm, are preferred and often successful in practice. Lloyd’s algorithm (a.k.a. the “k-means ” algorithm) Input: dataset X, |X | = n); k; samples size m, m> k.