loading...
running...
How to use
Choose a preset or generate your own data (blobs, spread, noise). Press Step to see the two half-steps one at a time, or Converge to run to the fixed point. Compare random seeding with k-means++ and with the corner start, then change k and read the elbow graph, silhouette and adjusted Rand score. Drag to orbit, wheel to zoom. Space pauses automatic stepping, R restarts the algorithm on the same data.
The bench, cube frame, point and centroid models and textures were modelled and baked in Blender; Three.js r160 drives every instance from the k-means state.
The science
k-means (Lloyd, 1957; MacQueen, 1967) partitions n points x_i into k clusters by minimising the within-cluster sum of squares (WCSS, the inertia):
J = sum_j sum_(i in S_j) | x_i - c_j |²
Lloyd's algorithm alternates two half-steps, both of which can only lower J. Assignment: each point joins its nearest centroid. Update: each centroid moves to the mean of its points, because the mean is exactly the minimiser of the sum of squared distances. J is bounded below and there are finitely many partitions, so the iteration stops, but only at a local minimum that depends on the start. That is why initialisation matters.
k-means++ (Arthur and Vassilvitskii, 2007) picks the first centre at random and each next centre with probability proportional to D(x)², the squared distance to the nearest centre already chosen. This spreads the seeds and gives an expected O(log k) approximation of the optimum. The "bad start" option puts all seeds in one corner so you can watch a poor local optimum or several slow iterations.
Choosing k. J always falls as k grows (k = n gives J = 0), so the elbow graph looks for the k after which the improvement flattens; with overlapping blobs the elbow is vague, which is the honest answer. The silhouette s = (b - a) / max(a, b) compares the mean distance to the own cluster (a) with the mean distance to the nearest other cluster (b); it is computed on every n/200-th point to keep the page fast. The adjusted Rand index compares the found partition with the blobs that generated the data (1 = identical, about 0 = random); noise points form their own group in the truth.
Checks. (1) J never increases over the Lloyd iterations. (2) At the fixed point every centroid equals the mean of its cluster. (3) For k = 1 the inertia is the sum of squared deviations from the global mean. (4) The decomposition TSS = WCSS + BCSS holds, where BCSS = sum_j n_j |c_j - mean|². (5) Well separated blobs are recovered by k-means++ (best of two starts).
Simplifications. Euclidean distance in the unit cube, equal-variance spherical blobs (which is the model k-means implicitly assumes: it fails on elongated or ring-shaped clusters), empty clusters keep their old centroid, and the data are synthetic. The optional influence spheres have radius proportional to the square root of the cluster share; they are a visual aid, not a model quantity.