Worked examples — K-Means++ initialization

This page is a drill hall. The parent note taught you the machinery: pick the first centroid at random, then pick each next one with probability proportional to $D(x{)}^2$ (the squared distance to the nearest centroid you already have). Here we push that machinery through every kind of situation it can face, so you never meet a case you haven't seen.

Before the first symbol appears, one reminder in plain words:

The recipe we repeat every single time:

---

The scenario matrix

Every example below is stamped with which cell it fills. Together they cover the whole grid.

Cell	What makes it special	Example
A Well-separated blobs	The clean, textbook case	Ex 1
B First pick lands inside a blob	Random start biases nothing badly	Ex 1
C Two candidates equidistant	A tie — how probability splits	Ex 2
D Degenerate: duplicate points	$D=0$ points, what happens to them	Ex 3
E Zero-input edge: all points identical	$\Phi =0$, the division breaks	Ex 4
F Outlier present	The far-away troublemaker	Ex 5
G Limiting behaviour: one point infinitely far	Deterministic-in-the-limit	Ex 5
H $D$ vs $D^2$ head-to-head	Why we square	Ex 6
I Real-world word problem	Store locations on a map	Ex 7
J Exam twist: compute $\Phi$ after a re-pick	Recompute nearest, not first	Ex 8

---

[!example] Example 1 — Cells A & B: clean blobs, first pick inside one

Statement. Six points, two obvious groups: Left group $L$: $(0,0),(1,0),(0,1)$. Right group $R$: $(10,0),(11,0),(10,1)$. We already chose $c_1=(0,0)$. Compute every $D(x{)}^2$ and the probability of each point being $c_2$.

Forecast. Guess: which group grabs almost all the probability? (You should feel the right group must win — it is far from $(0,0)$.)

Step 1 — distance from each point to $c_1=(0,0)$. Why this step? With only one centroid chosen, "nearest centroid" is $c_1$, so $D$ is just distance to $(0,0)$.

point	$D^2=x^2+y^2$
$(0,0)$	$0$
$(1,0)$	$1$
$(0,1)$	$1$
$(10,0)$	$100$
$(11,0)$	$121$
$(10,1)$	$101$

Step 2 — total $\Phi$. Why this step? The denominator of every probability is the same total, so compute it once. $\Phi =0+1+1+100+121+101=324.$

Step 3 — probabilities. Why this step? Divide each $D^2$ by $\Phi$ (the recipe). $P(10,0)=\frac{100}{324}\approx 0.309,P(11,0)=\frac{121}{324}\approx 0.373,P(10,1)=\frac{101}{324}\approx \mathrm{0.312.}$ The left group totals $\frac{2}{324}\approx 0.006$.

Verify. The right group carries $\frac{322}{324}\approx 0.994$ of all probability — as forecast, $c_2$ almost surely lands in the far group, exactly the "spread out" behaviour we want. Probabilities sum to $1$: $\frac{0+1+1+100+121+101}{324}=1$. ✓

---

[!example] Example 2 — Cell C: a perfect tie

Statement. Points $A=(-3,0)$, $B=(3,0)$, and $c_1=(0,0)$. What is $P(A)$ vs $P(B)$?

Forecast. Guess: symmetric points at equal distance — do they get equal chance? By how much do they beat a third, closer point at $(1,0)$ if we add one?

Step 1 — squared distances (only $A,B$). Why this step? Both sit distance $3$ from origin, so $D^2=9$ each.

Step 2 — probabilities. Why? $\Phi =9+9=18$, so $P(A)=P(B)=\frac{9}{18}=0.5$.

Step 3 — add closer point $E=(1,0)$, $D^2=1$. Why? To see how a tie survives when a nearer point joins. Now $\Phi =9+9+1=19$. $P(A)=P(B)=\frac{9}{19}\approx 0.474,P(E)=\frac{1}{19}\approx \mathrm{0.053.}$

Verify. The tie is preserved ($A,B$ equal) and the near point is $9\times$ less likely than each far point — matching the ratio of their $D^2$ values ($9:1$). Sum $=\frac{9+9+1}{19}=1$. ✓

---

[!example] Example 3 — Cell D: duplicate points, $D=0$

Statement. Points $(2,0)$ appears twice (a genuine duplicate), plus one point $(6,0)$. Take $c_1=(2,0)$. Can a duplicate of $c_1$ ever become $c_2$?

Forecast. Guess: a point sitting exactly on a centroid has distance $0$ — what does the recipe do with a $0$?

Step 1 — squared distances. Why? Both copies of $(2,0)$ are distance $0$ from $c_1$, so $D^2=0$. The point $(6,0)$ has $D^2=(6-2{)}^2=16$.

Step 2 — probabilities. Why? $\Phi =0+0+16=16$. $P(\text{each duplicate})=\frac{0}{16}=0,P(6,0)=\frac{16}{16}=1.$

Step 3 — interpret. Why? A probability of exactly $0$ means the duplicate can never be chosen as $c_2$. Good — you never want two centroids on the same spot.

Verify. Only the far point has non-zero mass and it gets it all: $P=1$. Duplicates are automatically excluded. Sum $=1$. ✓

---

[!example] Example 4 — Cell E: the degenerate case $\Phi =0$

Statement. All three points are identical: $(4,4),(4,4),(4,4)$, and $c_1=(4,4)$. Try to compute $c_2$'s probabilities.

Forecast. Guess: if everyone sits on the centroid, what is $\Phi$, and what breaks?

Step 1 — squared distances. Why? Every point equals $c_1$, so every $D^2=0$.

Step 2 — the total. Why? $\Phi =0+0+0=0$. The recipe wants us to compute $\frac{0}{0}$ — undefined. Division by zero is illegal.

Step 3 — the correct handling. Why? When $\Phi =0$ the data has fewer distinct locations than $k$. A real implementation detects $\Phi =0$ and falls back to a uniform random pick (every remaining point equally likely) or stops because more clusters than distinct points is meaningless.

Verify. With $k=2$ requested but only $1$ distinct location, no valid second centroid exists; uniform fallback gives $P=\frac{1}{3}$ each — a legal distribution summing to $1$. ✓

---

[!example] Example 5 — Cells F & G: an outlier and the limiting case

Statement. Cluster of three points near origin: $(0,0),(1,0),(0,1)$, plus one outlier $O=(100,0)$. With $c_1=(0,0)$, find $P(O)$. Then let the outlier drift to $(M,0)$ and see what happens as $M\to \infty$.

Forecast. Guess: does the outlier grab nearly all the probability? Does it grab all of it in the limit? (This is the danger the parent note warned about.)

Step 1 — squared distances at $M=100$. Why? Distance to $c_1=(0,0)$. Inliers: $0,1,1$. Outlier: $100^2=10000$.

Step 2 — probability of $O$. Why? $\Phi =0+1+1+10000=10002$. $P(O)=\frac{10000}{10002}\approx \mathrm{0.9998.}$

Step 3 — the limit $M\to \infty$. Why this step? To see the degenerate limit. $\Phi =2+M^2$, so $P(O)=\frac{M^2}{2+M^2}\underset{M\to \infty }{\to }1.$ As the outlier flies to infinity, its selection probability approaches $1$ — the algorithm becomes deterministically forced onto the outlier.

Verify. At $M=100$: $\frac{10000}{10002}\approx 0.99980$. The limit expression $\frac{M^2}{2+M^2}$ is below $1$ for all finite $M$ and tends to $1$. ✓

---

[!example] Example 6 — Cell H: $D$ versus $D^2$ head-to-head

Statement. Three candidates with distances (not squared) $D=1,2,4$ from the nearest centroid. Compute the pick-probabilities using linear weighting $D$ and using squared weighting $D^2$. Compare.

Forecast. Guess: which scheme gives the farthest point ($D=4$) a bigger share?

Step 1 — linear scheme. Why? Sum the raw distances: $1+2+4=7$. $P_{\text{lin}}=\frac{1}{7},\frac{2}{7},\frac{4}{7}\approx 0.143,0.286,\mathrm{0.571.}$

Step 2 — squared scheme (the real K-Means++). Why? Square first: $1,4,16$; sum $=21$. $P_{\text{sq}}=\frac{1}{21},\frac{4}{21},\frac{16}{21}\approx 0.048,0.190,\mathrm{0.762.}$

Step 3 — compare the far point's share. Why? The $D=4$ point rises from $0.571$ to $0.762$. Squaring sharpens the preference for far points, giving the theoretical $O(\log k)$ guarantee the parent note cites.

Verify. Both sets sum to $1$: $\frac{1+2+4}{7}=1$ and $\frac{1+4+16}{21}=1$. The squared far-point share $0.762>0.571$ linear share. ✓

---

[!example] Example 7 — Cell I: real-world word problem (store map)

Statement. A chain owns $5$ shops at grid coordinates (in km): $S_1(0,0),S_2(2,0),S_3(0,2),S_4(9,9),S_5(10,8)$. They want $k=2$ distribution hubs. The first hub is seeded at $S_1=(0,0)$. Where is the second hub most likely placed?

Forecast. Guess: which of the two natural clusters (the origin trio or the far pair) should the second hub serve?

Step 1 — squared distances to hub $S_1=(0,0)$. Why? Only one hub so far; nearest-hub distance = distance to $S_1$.

shop	$D^2$
$S_1$	$0$
$S_2$	$4$
$S_3$	$4$
$S_4$	$81+81=162$
$S_5$	$100+64=164$

Step 2 — total and probabilities. Why? $\Phi =0+4+4+162+164=334$. $P(S_4)=\frac{162}{334}\approx 0.485,P(S_5)=\frac{164}{334}\approx \mathrm{0.491.}$ The nearby trio shares only $\frac{8}{334}\approx 0.024$.

Step 3 — business reading. Why? The far pair carries $\approx 0.976$ of the probability, so hub $2$ almost surely lands near $(9,9)$–$(10,8)$, serving the distant shops — exactly the spread a logistics planner wants.

Verify. $P(S_4)+P(S_5)+\text{trio}=\frac{162+164+8}{334}=1$. Far pair total $\frac{326}{334}\approx 0.976$. ✓ Units: coordinates in km, $D^2$ in km², probabilities unitless. ✓

---

[!example] Example 8 — Cell J: exam twist, recompute after a re-pick

Statement. Points $P_1(0,0),P_2(6,0),P_3(3,5)$. We already picked two centroids: $c_1=(0,0)$ and $c_2=(6,0)$. Compute $\Phi$ now (the third-round total) — the trap is that each point uses its nearest of the two, not the first.

Forecast. Guess: which centroid is nearest to $P_3=(3,5)$, and does it matter that there are now two centroids?

Step 1 — nearest centroid for each point. Why this step? The whole twist: $D$ is the minimum over all chosen centroids.

• $P_1$ sits on $c_1$: distances $0$ and $6$ → nearest $=0$.
• $P_2$ sits on $c_2$: distances $6$ and $0$ → nearest $=0$.
• $P_3=(3,5)$: to $c_1$ is $\sqrt{9+25}=\sqrt{34}$; to $c_2$ is $\sqrt{9+25}=\sqrt{34}$ — a tie, nearest${}^2=34$.

Step 2 — squared distances. Why? $D^2(P_1)=0,D^2(P_2)=0,D^2(P_3)=34$.

Step 3 — total and probability. Why? $\Phi =0+0+34=34$. Then $P(P_3)=\frac{34}{34}=1$: if we needed a third centroid, $P_3$ is forced.

Verify. $\sqrt{34}$ from both existing centroids gives $D^2=34$; the two on-centroid points contribute $0$; $\Phi =34$ and $P(P_3)=1$. ✓

---

[!recall]- Quick self-test

Whole matrix in one place — cover the right side and answer.

---

See also

• Elbow Method and Silhouette Score — how you judge whether the resulting $k$ clusters are good.
• K-Medoids (PAM) — a cousin that seeds and updates with actual data points, gentler on outliers.
• Random Seed Setting — because K-Means++ is randomized, fixing the seed makes Ex 1–8 reproducible.
• Computational Complexity — the cost of recomputing $D^2$ each round (Ex 8's "recompute" step).