Clusters in 3D

The same three generating processes as the 2-D experiments, with a third coordinate added (300 points each). Colours are K-means assignments (K-means++, 10 restarts); diamonds mark the cluster means. Drag to rotate, use the toolbar (top right of each plot) to zoom or reset, and hover for coordinates.

Generation: blobs are x = c + σ·ε with ε ~ N(0, I₃). Clear clusters: σ = 0.6, centres on 4 vertices of a cube, so all are 8.5 apart. Nested: 3 groups 10–12 apart, each split into 2 subgroups 2.4 apart along x, σ = 0.35. Uniform: points spread evenly over the cube [0, 10]³.

Elbow method: how the cost falls with K

For each K from 1 to 10, Lloyd's algorithm was run with K-means++ and 10 restarts, keeping the lowest cost F*(K) = Σ‖xᵢ − μ_zᵢ‖². The cost always falls as K grows. The elbow is where it suddenly stops falling much: the next drop is less than 20% of this one. Circles mark the elbows.

4 clear clusters: each cluster up to K = 4 cuts the cost by about 2,700, because it separates a real blob. After that each one cuts only about 20. A single clear elbow at K = 4.
3 groups × 2 subgroups: two elbows. The cost collapses once the 3 groups are separated (K = 3), falls by about 150 per step while subgroups are split off, and flattens at K = 6.
No structure: every drop is 60–80% of the previous one, so the curve bends smoothly with no elbow. That tells you there are no real clusters. In 3-D the cost only falls to 20% of its K = 1 value by K = 10 (9.5% in 2-D), matching the K^−2/d law.

Lloyd's algorithm: random starts vs K-means++

K-means++ isn't a separate algorithm: it's a smarter starting point for Lloyd's. Each start below was run 200 times as a single run (no restarts) at the true K. Each dot is one run's final cost; the dashed line is the best cost any run found. On the first two datasets the cost axis is logarithmic.

Random partitionPut each point into a random cluster, then compute means.

Random pointsUse K random data points as the starting means.

K-means++First mean at random; each next mean sampled with probability ∝ D(x)², the squared distance to the nearest mean so far.

K-means++ starts close to the answer. On the clear clusters its starting cost (1,350) is already below random's final average, and Lloyd's needs only about 1.4 iterations to finish.
Bad local minima are real. The band of runs near 3,000 on the clear clusters merged two true blobs and split another. Random starts landed there 20–28% of the time, K-means++ 3%. Lloyd's always converges (L15), but not always to the best answer.
The harder the data, the bigger the gap. With 6 subgroups in close pairs, random partition never found the best answer, because every starting mean begins near the overall centre. K-means++ found it 63% of the time, and its worst run (418) beat both random methods' worst (about 5,500).
With no real clusters, the start barely matters. Many partitions have almost the same cost, so all three end up spread across 3,300–3,800, and Lloyd's needs about 12 iterations instead of 2–4.
Restarts still help. K-means++ still missed the best answer 37% of the time on the nested data, which is why the usual practice is K-means++ plus several restarts.

ARI (adjusted Rand index) measures agreement with the true groups: 1 is perfect, 0 is no better than chance. It isn't defined for the uniform data, which has no true groups.