k-means
Also: k-means clustering, K-means, k-means++, Lloyd’s algorithm
An iterative algorithm that minimizes the within-cluster sum of squared distances (WCSS). It needs k chosen in advance (elbow or silhouette methods help), is sensitive to initialization (k-means++ helps) and assumes roughly spherical, similar-sized clusters.
minimize Σₖ Σ_{x ∈ Cₖ} ‖x − μₖ‖²
Example
For points 1, 2, 10, 12 with k = 2 and starting centroids 1 and 2, one assign-and-update round gives centroids 1 and 8, the next gives 1.5 and 11, where it converges.