Tool · 2026-07-27
K-means, on Lloyd's algorithm.
Given a cloud of points and a chosen number k, k-means partitions the cloud into k groups whose members sit near the same mean. Lloyd's iteration is the workhorse: assign every point to its nearest current mean, then move each mean to the centroid of the points it caught. Repeat until nothing moves. It almost always finds a decent answer. Sometimes it finds a nonsense one, and the presets at the bottom show why.
Click to add a point
One Lloyd step
Every step has two halves. First, each point looks at the current centroids and takes the colour of the nearest one under Euclidean distance. Second, each centroid slides to the average position of all points now wearing its colour. Both halves reduce the same quantity: the sum of squared distances from every point to its own centroid, called the within-cluster sum of squares, or inertia. Since inertia can only fall or stay put, and the number of possible labellings is finite, the iteration always halts.
k-means++ seeding
The starting positions of the centroids matter a lot. Purely random seeding often drops two centroids inside the same natural cluster and starves a real one, and Lloyd has no way to move a centroid across an empty gap. The Reset seeds button uses the k-means++ trick: pick the first centroid uniformly at random from the points, then pick each of the remaining centroids with probability proportional to the squared distance from that point to its nearest already-chosen centroid. In expectation the seeds spread out, and the final inertia lands within a constant factor of the true optimum.
Where it fails
The rings preset is a fair test that k-means cannot pass. It only knows how to draw straight cuts between centroids, so a cluster shaped like a ring around another gets sliced in two by any single centroid. The half-moons preset fails the same way for the same reason. If the ground-truth clusters are not roughly convex and not roughly the same size, the answer will be wrong no matter how many restarts you do. Spectral clustering and DBSCAN drop the convex assumption at the cost of extra parameters, and are what you reach for on non-round shapes.
Sources
- Lloyd, S. P. (1982). Least Squares Quantization in PCM. IEEE Transactions on Information Theory, 28(2), 129–137. The published version of a Bell Labs technical note from 1957.
- MacQueen, J. (1967). Some Methods for Classification and Analysis of Multivariate Observations. Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, Vol. 1, 281–297. The paper that gave the algorithm its current name.
- Arthur, D. and Vassilvitskii, S. (2007). k-means++: The Advantages of Careful Seeding. Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, 1027–1035. The seeding trick used by the Reset button here.