Concept
The simplest grouping algorithm — from 1957 Bell Labs to every data scientist's first tool.
Understand it in one breath
The simplest way to group similar data into clusters. Place k centers at random → assign each point to its nearest center → recompute centers → repeat. The first tool for customer segmentation, image-color compression, gene-expression classification, and recommender systems.
At a glance
Iteration | Step | Result |
|---|---|---|
Initialization | Choose k centers at random | Example: μ₁=(2,3), μ₂=(8,7) |
1 | Assign each point to its nearest center | Point (3,3) → cluster 1 |
1 | Recompute centers (cluster means) | New μ₁, μ₂ |
2 | Reassign → recompute | Some points switch clusters |
… | Repeat until nothing changes | Convergence (local minimum) |
Converged | Final cluster partition | Applications: customer segments, image color compression, gene clustering |
K-means can become trapped in a local minimum, so it is usually run several times with different initializations and the best result is selected.
Key formula
Key moments
Lloyd — a Bell Labs internal report
Stuart Lloyd developed the algorithm for pulse-code modulation quantization, but the work remained unpublished in archival form for decades.
MacQueen names k-means
James MacQueen presented and generalized the iterative clustering method under the name k-means.
K-means++ — better initialization
David Arthur and Sergei Vassilvitskii proposed a principled way to choose initial centers, improving both theoretical guarantees and practical reliability.
Modern applications
Customer segmentation, image compression, genomic analysis, recommendation systems, anomaly detection, and preparation of AI training data.
Beyond MathVoyage
Loading…