Where randomness enters
Randomness shows up in four places, which do three jobs. Click a box to jump to its demos.
Two seeds, two answers
Same data, same algorithm, same k. Only the random seed changes. Both runs "finish successfully", but one may be much worse by k-means' own measure (inertia = sum of squared distances to the nearest centroid; lower is better).
Colours in panel B are matched to panel A where clusters overlap, so you can compare them directly. The × marks are centroids.
Lloyd's algorithm, step by step
k-means alternates two steps: assign each point to its nearest centroid, then update each centroid to the mean of its points. Inertia never goes up, so it always stops, but only in the nearest "valley" (a local optimum). The shaded regions show which centroid owns each area.
k-means++: shaping the randomness
k-means++ picks the first centre at random, then each next centre with probability proportional to D(x)², the squared distance to the nearest centre so far. Point size and colour show that probability. Compare with uniform random picks and with deterministic farthest-first, and add outliers to see which method chases them.
How often do we get stuck? Random init vs k-means++
Run k-means many times with different seeds and plot the final inertia of each run. A run counts as stuck when it ends more than the threshold above the best inertia found. Increase n_init (restarts per run, keep the best) to see how restarts rescue random initialization.
Mini-batch k-means, live
Instead of looking at every point each iteration, mini-batch k-means (Sculley, 2010) takes a small random batch, and nudges each centroid toward its batch points with a learning rate of 1/(points seen so far). Ringed points are the current batch; hollow circles are where full k-means ends up from the same start.
Speed benchmark: full vs mini-batch
Generate a large synthetic dataset and time both algorithms in your browser from the same k-means++ start. The curve shows quality (mean squared distance, measured on a fixed 5,000-point sample, evaluation time excluded) against compute time. Expect mini-batch to reach "nearly as good" much sooner, and to settle a little worse.
Full k-means here is plain single-threaded JavaScript. The real win for mini-batch is when data doesn't fit in memory or arrives as a stream, because it never needs all points at once.
Random projections preserve distances
Multiply high-dimensional data by a random matrix to get far fewer dimensions. The Johnson–Lindenstrauss lemma says pairwise distances survive within a factor (1 ± ε), and the dimensions needed depend on the number of points, not the original dimension. The histogram shows projected/original distance for every pair of points; 1 means perfectly preserved.
One projection is unstable; an ensemble is robust
Five clusters live in 100 dimensions. Project them randomly to a few dimensions and run k-means: the result depends on which projection you drew (Fern & Brodley, 2003). Clustering many projections and combining them through a co-association matrix turns that instability into diversity. Agreement with the true groups is measured by the Adjusted Rand Index (ARI: 1 = perfect, 0 = chance).
Scatter plots show the first two projected coordinates of the current projection, coloured by cluster label.
Consensus clustering: randomness as a measuring tool
Cluster many random subsamples. For every pair of points, record how often they land in the same cluster (out of the runs where both were sampled). Reordered, clean dark blocks mean stable clusters; blurry blocks mean the algorithm is inventing boundaries. PAC = share of pairs with consensus between 0.1 and 0.9 (lower is more stable). Try the noise dataset, and try a k smaller than the truth: stable is not the same as correct.
Does your conclusion survive other seeds?
A fixed random_state makes a result repeatable, not reliable. Run the same configuration over several seeds and compare the results with the Adjusted Rand Index, which ignores arbitrary label names. If the seeds disagree, a single plot is not evidence.