k-means++ & the elbow method

Step through the seeding process. Every point gets a bar proportional to how far it is from every centroid chosen so far — a point already close to an existing centroid barely registers, while a point stuck in an untouched blob towers over the rest. That's the whole trick: distant points get picked more often, without ever being forced to.

k-means++ replaces uniform-random seeding with distance-weighted sampling, and the elbow method replaces a guessed $k$ with one read off a curve.

• $D(x)$ — the distance from point $x$ to the nearest centroid already chosen.
• $P(x)$ — the probability of picking $x$ as the next centroid: proportional to $D(x)^2$, normalized over every not-yet-chosen point.
• $J(k)$ — the inertia: total squared distance from every point to its assigned centroid, once $k$ centroids have converged via Lloyd's algorithm.

1. First centroid, then weighted draws

   The first centroid is picked arbitrarily (uniformly at random in practice). Every centroid after that is sampled from $P(x)$ — walk the cumulative $D(x)^2$ distribution until a random draw lands inside a point's slot.

2. Farther points are more likely, never guaranteed

   A point ten units from every existing centroid has a much bigger slice of the distribution than one sitting right next to a centroid — but it's still a lottery, not a rule. Any point can still be drawn.

3. Run Lloyd's algorithm to convergence, once seeded

   With $k$ centroids chosen this way, ordinary k-means (assign, recompute, repeat) takes over from here.

4. Increase k and watch inertia only ever fall

   More centroids can only help — $J(k)$ never increases with $k$. The elbow is the $k$ whose drop is dramatically larger than the next one: the last point where adding a centroid genuinely helped, before returns collapse to "barely worth it."

At $k=1$, everything is forced into one centroid at the grand mean — a big inertia, badly fit. At $k=3$, one centroid per true blob, and inertia bottoms out almost entirely. At $k=4$, a blob gets needlessly split in two, but the improvement over $k=3$ is tiny compared to every earlier jump.

Three tight blobs of 3 points each, far apart from one another; the very first draw is fixed to land exactly halfway through the cumulative distribution each time:

1. D(x)^2 from the first centroid, (0,0)

   Squared distance $D(x)^2=x^2+y^2$ (since the centroid is the origin) to each of the other 8 points:

   • $(1,0)$: $1^2+0^2=1$
   • $(0,1)$: $0^2+1^2=1$
   • $(10,0)$: $10^2=100$
   • $(11,0)$: $11^2=121$
   • $(10,1)$: $10^2+1^2=101$
   • $(5,10)$: $5^2+10^2=125$
   • $(6,10)$: $6^2+10^2=136$
   • $(5,11)$: $5^2+11^2=146$

   Summing: $1+1+100+121+101+125+136+146=731$.

2. The halfway draw lands on the far blob

   Half of $731$ is $365.5$. Walking the cumulative sum in point order:

   • $(1,0)$: cumulative $1$
   • $(0,1)$: cumulative $2$
   • $(10,0)$: cumulative $102$
   • $(11,0)$: cumulative $223$
   • $(10,1)$: cumulative $324$
   • $(5,10)$: cumulative $449$ — first exceeds $365.5$ here

   The second centroid is $(5,10)$.

3. A third halfway draw finds the last untouched blob

   With centroids at $(0,0)$ and $(5,10)$, $D(x)^2$ is now the smaller of the two distances to each point. Every point in the first two blobs is far closer to $(0,0)$ than to $(5,10)$, so their $D(x)^2$ is unchanged from step 1: $0,1,1,100,121,101$ (for $(0,0),(1,0),(0,1),(10,0),(11,0),(10,1)$), while the third blob's points are now essentially at distance $0$ from the chosen $(5,10)$: $0,1,1$. Summing: $0+1+1+100+121+101+0+1+1=326$; half is $163$. Walking the cumulative sum, it passes $163$ at $(11,0)$ (cumulative $223$) — the third centroid. All three blobs now have exactly one seed.

4. Inertia across k=1..4

   $J(3)$ is the cleanest to check by hand: with one centroid per blob, each blob's centroid is its own mean, e.g. blob A's mean is $(\frac13,\frac13)$, giving squared distances $\frac29, \frac59, \frac59$ to its three points — summing to $\frac{12}{9}=\frac43$. All three blobs have the same shape, so each contributes $\frac43$, and $J(3) = 3\times\frac43 = 4$.

   The same sum-of-squared-distances recipe, applied to the (worse-fitting) 1- and 2-centroid clusterings and the (needlessly-split) 4-centroid one, gives $J(1)=354$, $J(2)=154$, and $J(4)=19/6\approx3.17$. The drop from $k=2$ to $k=3$ is $150$; the drop from $k=3$ to $k=4$ is under $1$. $k=3$ is the elbow.