==============================================================================================
RAHUL'S ML BLOG -- notes on machine learning, worked out by hand est. 2026
==============================================================================================
home | about | archive | glossary | contact
----------------------------------------------------------------------------------------------
CHAPTER 6 . FINDING PATTERNS WITHOUT ANSWERS . PART 3 OF 6
Grouping by Nearest Centre: K-Means From a Blank Sheet
============================================================================================
Every row is a list of numbers.
The straight-line gap between two rows is one number that says how far apart they sit.
To get it: subtract the two rows column by column.
Square each of those differences.
Add the squares.
Take the square root of that sum.
That square root is the straight-line (Euclidean) gap.
This post does the grouping.
There is no answer column: nobody tells us which rows belong together.
So we have to carve the cloud of dots into K piles ourselves.
We carve it using nothing but that straight-line gap.
K-means is the simplest grouping machine there is.
The whole thing is two moves repeated until nothing changes.
MOVE 1 -- ASSIGN every dot to its nearest centre.
MOVE 2 -- MOVE each centre to the middle of the dots that chose it.
That is it.
Two moves, on a loop.
The two moves look circular. To put each dot with a centre you need centres; to
place the centres you need to know which dots group together. Chicken, egg:
need centres --------> to assign dots
^ |
| v
need grouped dots <----- to place centres
So break the circle by cheating: drop K centres down anywhere at all. The first
sort is sloppy -- but a sloppy grouping still gives better centres than the
random ones, and better centres give a less sloppy grouping:
random centres --> rough piles --> better centres --> tighter piles --> ...
total gap (each dot to its centre):
84 --> 51 --> 38 --> 33 --> 31 --> 31 (stops)
Each move can only shrink that total gap, never grow it -- the loop always walks
downhill, so it has to stop, and it stops when neither move changes a thing. The
opening guess is wrong; the loop does not mind, because repairing it is the loop.
JOB
a cloud of dots (rows), and a number K you pick
carve the cloud into K piles so each pile is tight (its dots sit close together)
* * * [ * * ] [ * ]
* * * * -> [ * * ] and [ * * ] (K = 2 piles)
* * * tight pile tight pile
You choose K up front -- "I want 3 groups."
The machine does not invent K.
It only finds the best K piles once you name the number.
Picking K well is its own problem.
We get to it at the end.
TWO MOVES
A centre is one point that stands for a pile.
Start by dropping K centres anywhere.
To drop them, pick K random dots and call them the first centres.
Then loop:
MOVE 1 -- ASSIGN. For every dot, measure its straight-line gap to all K centres.
The straight-line gap subtracts column by column, squares, adds, roots.
The dot joins the pile of its NEAREST centre.
MOVE 2 -- UPDATE. For each pile, find the middle: the mean of its dots, column
by column. The mean of a list adds the values and divides by how many
there are. That mean becomes the pile's new centre.
repeat ASSIGN, then UPDATE, then ASSIGN, then UPDATE ...
STOP when no dot changes pile (the centres stop moving)
Each loop can only make the piles tighter or leave them the same.
It never makes them worse.
Therefore it always settles.
The settling point is the answer.
Why can UPDATE never make things worse?
The mean of a pile is the one spot that makes that pile's squared gaps smallest.
That is what a mean does.
So moving the centre to the mean either lowers the pile's tightness or leaves it alone.
It cannot raise it.
(A quiz likes to claim "the update step increases the within-group sum of squares."
That is exactly backwards.)
>> NOTE: COMPARE SQUARED GAPS -- SKIP THE SQUARE ROOT
ASSIGN only asks WHICH centre is nearest, never HOW FAR.
If gap A-squared is smaller than gap B-squared, then gap A is smaller than gap B.
Squaring keeps the order.
So the machine compares squared gaps directly and never takes a root.
Same winner, less arithmetic.
A WORKED EXAMPLE, BY HAND
Six dots on one ruler (one column, to keep the arithmetic small). K = 2.
dots: 1 2 3 10 11 12
Drop two starting centres. Say the random pick lands on 2 and 10.
ROUND 1 -- ASSIGN (each dot to nearest centre):
dot 1 -> centre 2 (gap 1 vs 9) pile A
dot 2 -> centre 2 (gap 0) pile A
dot 3 -> centre 2 (gap 1 vs 7) pile A
dot 10 -> centre 10 pile B
dot 11 -> centre 10 (gap 1) pile B
dot 12 -> centre 10 (gap 2) pile B
ROUND 1 -- UPDATE (mean of each pile):
pile A = mean(1,2,3) = 2
pile B = mean(10,11,12) = 11
new centres: 2 and 11
ROUND 2 -- ASSIGN: every dot stays in the same pile.
Nobody moved. STOP.
Final piles: {1, 2, 3} and {10, 11, 12}. Centres 2 and 11.
The machine found the two obvious clumps on its own.
It used no answer key.
A seventh dot walks in at 5. The settled centres are 2 and 11. Which pile does
ASSIGN hand it to? Compare squared gaps -- no roots needed.
check your slate: gap to centre 2: 5 - 2 = 3, squared 9; gap to centre 11:
5 - 11 = -6, squared 36. 9 < 36, so the dot joins pile A -- and since squaring
keeps the order, the winner is the same one a square root would have crowned.
SCORE: TIGHTNESS (INERTIA)
IN HAND: six dots carved into two piles, {1,2,3} and {10,11,12}, by two moves on a
loop; the settled centres are mean(1,2,3) = 6/3 = 2 and mean(10,11,12) = 33/3 = 11.
This section adds: one number that says how GOOD that grouping is.
How good is a grouping?
Measure how tight the piles are.
For every dot, take its squared gap to its OWN centre.
Then add them all up.
Tightness is this total, and its standard name is inertia.
tightness = sum over all dots of (gap from dot to its centre)^2
small tightness = dots hug their centres = tight, good piles
big tightness = dots sprawl far from their centres = loose, poor piles
Foot it on the six dots.
Pile A first.
Pile A holds dots {1, 2, 3}.
Its centre is mean(1,2,3) = 6/3 = 2:
dot gap to centre 2 squared
-----------------------------------
1 1 - 2 = -1 1
2 2 - 2 = 0 0
3 3 - 2 = 1 1
pile A sum = 2
Foot pile B the same way (dots 10, 11, 12; centre mean(10,11,12) = 33/3 = 11),
then add the two piles into one tightness for the whole grouping.
check your slate: 10 - 11 = -1, squared 1; 11 - 11 = 0, squared 0;
12 - 11 = 1, squared 1; pile B sum = 1 + 0 + 1 = 2. Whole grouping:
2 + 2 = 4. Four is the number the two moves were driving down all along.
K-means is just the machine that drives this one number as low as it can.
It drives it down by the two moves on a loop.
The number is the total of squared gaps from dots to their centres.
Recall the six dots {1,2,3} and {10,11,12} settle at 2 + 2 = 4.
The machine pushes that total of squared gaps to its smallest reachable value.
Here the "miss" being squared is a dot's gap from its centre.
There is no answer column anywhere.
THE CATCH: WHERE YOU DROP THE FIRST CENTRES MATTERS
K-means always settles.
But it can settle into a BAD grouping if the starting centres were unlucky.
It finds a low point.
It does not always find the LOWEST point.
unlucky start: two centres land inside the same clump
-> the machine splits one real clump in half and merges two others
-> it settles, but the piles are wrong
The fix is cheap.
Run the whole thing several times from different random starts.
Keep the run with the smallest tightness.
The total of squared gaps from dots to their own centres is that tightness.
The toolbox does this for you; the setting is named n_init.
There is also a smarter starting trick named k-means++.
K-means++ spreads the first centres far apart on purpose, so an unlucky start is rarer.
CHOOSING K: THE ELBOW
IN HAND: two moves on a loop, a tightness to score what they settle on (the six-dot
grouping foots to 1+0+1 = 2 per pile, 2 + 2 = 4 in all), and the warning that an
unlucky start can strand the machine in a poor low spot. This section adds: how to
choose K itself.
You picked K by hand.
But which K?
Run K-means for K = 1, 2, 3, 4, 5, ... and plot the tightness for each.
Tightness is the total of squared gaps from dots to their own centres.
tightness |*
| \
| \
| *
| \___
| *----*----*----* <- the curve flattens out
+------------------------- K
1 2 3 4 5 6
Tightness always drops as K grows.
More centres means each dot can sit closer to one.
At K equal to the number of real clumps, the drop suddenly flattens.
Adding more centres past that point barely helps.
That bend in the curve is the ELBOW.
The elbow is your best guess at the true number of groups.
>> NOTE: THE ELBOW IS A JUDGEMENT CALL, NOT A FORMULA
There is no equation that spits out "K = 3."
You look at the bend and decide.
Sometimes the bend is sharp and obvious.
Sometimes it is a gentle curve with no clear corner.
Then reasonable people pick different K.
That is honest: with no answer column, there is no single right number of groups.
If "big vs small by eye" feels like astrology, there is a judgement-free trick.
Lay a ruler from the FIRST dot of the curve to the LAST dot.
Then measure how far each dot sags below that ruler.
The dot with the BIGGEST sag is the elbow.
The two endpoints always sag zero.
So the answer is forced to sit somewhere in between.
A SECOND RULER: HOW WELL DOES EACH DOT FIT ITS PILE?
IN HAND: a grouping for every K, each scored by one tightness total (at K = 2 the six
dots foot to 2 + 2 = 4), and an elbow to squint at on the tightness curve. This
section adds: a second ruler, read per dot, with a peak instead of a bend.
The elbow reads ONE number for the whole grouping: total tightness.
Total tightness is the sum of squared gaps from dots to their own centres.
The elbow then asks you to eyeball a bend.
There is a second, sharper question you can ask of EVERY single dot.
"Are you snug in your own pile -- or would the pile next door fit you better?"
For one dot, compute two averages.
The straight-line gap here subtracts column by column, squares, adds, roots.
a = average gap from this dot to its OWN pile-mates (how far from home)
b = average gap from this dot to the NEAREST OTHER pile (how far to next door)
Then form the fit score from a and b.
The fit score's standard name is the silhouette.
fit score = (b - a) / whichever of a, b is bigger
near +1 -> home is much closer than next door. snug. well-grouped.
near 0 -> home and next door are the same distance. on the fence.
negative -> next door is CLOSER than home. this dot is in the WRONG pile.
By hand, on the six dots from before.
The two piles are {1,2,3} and {10,11,12}:
dot 1: a = avg gap to {2,3} = (1 + 2) / 2 = 1.5
b = avg gap to {10,11,12} = (9 + 10 + 11) / 3 = 10
fit = (10 - 1.5) / 10 = 0.85 <- snug at home
dot 3: a = avg gap to {1,2} = (2 + 1) / 2 = 1.5
b = avg gap to {10,11,12} = (7 + 8 + 9) / 3 = 8
fit = (8 - 1.5) / 8 = 0.81 <- the pile's edge dot, still snug
Average the fit score over ALL dots.
That average is one number for the whole grouping.
Its standard name is the mean silhouette score.
Now run K-means for K = 2, 3, 4, 5 ... and plot that average:
avg fit | *
| / \
| / \
| * *---*
| /
+--------------------- K
2 3 4 5
No bend to squint at.
You just pick the K with the HIGHEST peak.
A clean maximum instead of a fuzzy corner.
TWO RULERS, SAME QUESTION, PICK DIFFERENTLY
The elbow reads TIGHTNESS (squared gaps to centres) and you hunt a BEND.
The fit score reads HOME-VS-NEXT-DOOR gaps and you hunt a PEAK.
They answer the same "how many groups?" question with different measurements,
and the peak is the easier read. When both agree on K, trust it.
>> NOTE: THE FIT SCORE STARTS AT K = 2, NOT K = 1
With one pile there is no "next door."
So b does not exist.
Therefore the score is undefined.
The elbow curve can start at K = 1.
The fit-score curve cannot.
That is why the loop below runs K = 2 upward.
One more read the fit score gives for free.
Average it PER PILE, not just overall.
A whole pile averaging near 0 means that entire pile straddles the border with its
neighbour.
That is two piles drawn where the data holds one.
WHAT MAKES ANY GROUPER GOOD
Before the tripwires, here is the yardstick that outlives K-means.
Whatever grouping machine you ever meet, it is judged on the same short list:
within a pile: look-alikes hugging -> want gaps SMALL
between piles: piles far from each other -> want gaps BIG
bonus: handles bent or stretched crowds, not only round blobs
bonus: still runs when the sheet holds a million dots
never: depends on an answer column -- there isn't one
K-means scores well on the million-dots line.
K-means fails the bent-crowds line.
One gap-to-centre treats every pile as a round, same-size blob.
So crowds shaped like ribbons or crescents get butchered.
A different machine builds a family tree: it joins the two nearest dots, then the
next nearest, growing piles by closeness, so it chains along bent shapes.
That machine is covered in Part 4 (single linkage), linked below.
There are also machines that fit each pile a lean-and-stretch recipe instead of a
single centre; these are called Gaussian mixtures.
A fair number of places this bites, each a belief that feels right.
K-means lives entirely on the straight-line gap, so a column measured in thousands
hijacks every distance:
raw gap ~ the thousands-column, almost alone
Put every column on the same ruler (mean 0, spread 1) before the first centre
drops -- same as Part 1.
That "nearest centre" rule draws straight walls halfway between centres, so it can
only cut round blobs:
blobs: ( o o ) ( x x ) walls fall cleanly between them -> good
ribbon: o o o o x x x x one long crescent sliced in half -> wrong
When the real shape is a ribbon or crescent, the family tree (Part 4) or DBSCAN do
better. K-means assumes blobs.
Two runs can hand back different piles:
start A --> piles {..}
start B --> piles {..} differ, because the opening centres landed elsewhere
Not a bug -- the unlucky-start problem. Run it several times (n_init) and keep the
tightest.
K is yours to set, and the machine obeys blindly. Ask for K = 5 on data with 2 real
clumps and it splits real groups to reach the count:
2 real clumps, K=5 --> [ o | o ] [ x | x | x ] real groups carved up
It never argues. The elbow is your guard against a silly K.
Tightness (inertia) only ever falls as K rises -- so "smallest tightness" just
picks the biggest K (one centre per dot, tightness 0, useless):
tightness
|\
| \
| \____ <- ELBOW: where the falling stops paying off
| \______
+------------------ K
1 2 3 4 5 6
Pick K at the elbow. Chasing the "smallest DROP between neighbours" is just as
wrong -- the smallest drop sits at the far right where the curve is flat, the most
useless K of all.
A centre is not a real dot. It is the MEAN of its pile, usually a point with no row
sitting on it:
* *
C C is the centre of gravity, a member of nothing
* *
The fit score's b is the gap to the ONE closest foreign pile, not the average over
all of them:
dot in pile A: gap to nearest B-dot = 2.0 <- b uses this
gap to far-off C-dots = 9.0 <- not this
The question is "would next door fit better?" -- and next door means the single
nearest pile, not the whole neighbourhood averaged.
Two different shapes of number, easy to swap:
tightness: ONE total for the whole grouping (every squared gap summed)
fit score: one per dot first, then averaged into one at the end
Tightness is summed; the fit score is per-dot-then-averaged. Do not mix the shapes.
After .fit, km.labels_ holds one integer per row -- WHICH pile, never HOW FAR:
km.labels_ -> [0, 2, 1, 0, ...] pile numbers, no distance
km.transform(X) -> gap-to-every-centre matrix <- distances live here
For distances, call transform, not labels_.
The loop stops when a whole round switches no dot -- not when distances stop moving:
round n: assignment = [0, 1, 1, 2, 0]
round n+1: assignment = [0, 1, 1, 2, 0] identical -> STOP
A dot can keep its label while its distance shifts (the centre moved as its
pile-mates moved). The check is "same assignment as last round?", not "distances
stopped shrinking?".
Last, only one of the two moves measures a gap at all:
ASSIGN: straight-line gap to each centre -> pick the nearest (distance here)
UPDATE: average each pile's coordinates -> new centre (no distance)
UPDATE just averages coordinates; it never measures anything. Keeping the two moves
separate keeps the whole thing easy to reason about.
Plain term used above Standard label
----------------------------------- ------------------------------------------
grouping with no answer column clustering (unsupervised)
a pile of dots a cluster
the centre of a pile centroid / cluster mean
assign each dot to nearest centre the assignment step
move each centre to its pile's mean the update step
tightness (sum of squared gaps) inertia / within-cluster sum of squares
the bend in the tightness curve the elbow method
the biggest sag below the ruler the perpendicular-distance elbow rule
home vs next-door fit score silhouette coefficient
average fit over all dots mean silhouette score
lean-and-stretch pile recipes Gaussian mixture models (GMM)
pick K at the highest peak silhouette analysis
run from several random starts n_init / multiple restarts
spread first centres far apart k-means++ initialisation
number of piles you pick K (the n_clusters hyperparameter)
Nothing above needed a computer -- only pencils, clerks, and patience. This last
section is for the day you meet one: the same steps, spoken in Python.
First the 6-dot example from the worked section, hard-coded -- one dot per line so
every assign, update, tightness, and silhouette number lands visibly:
DOTS: 1, 2, 3 (PILE A) AND 10, 11, 12 (PILE B); K=2; STARTING CENTRES: 2 AND 10
The six dots on a line, with the two starting centres marked:
0 1 2 3 4 5 6 7 8 9 10 11 12
o o o o o o
^ centre A = 2 ^ centre B = 10
\__ pile A __/ \__ pile B __/
ROUND 1 -- ASSIGN: GAP FROM EACH DOT TO EACH CENTRE (SQUARED -- ORDER PRESERVED)
sq_1_c2, sq_1_c10 = (1-2)**2, (1-10)**2 # 1, 81 -> pile A (centre 2)
sq_3_c2, sq_3_c10 = (3-2)**2, (3-10)**2 # 1, 49 -> pile A
sq_10_c2, sq_10_c10 = (10-2)**2, (10-10)**2 # 64, 0 -> pile B (centre 10)
print(sq_1_c2, sq_1_c10, sq_3_c2, sq_3_c10) # 1 81 1 49
ROUND 1 -- UPDATE: NEW CENTRES = MEAN OF EACH PILE
centre_A = (1+2+3)/3 # 2.0
centre_B = (10+11+12)/3 # 11.0
print(centre_A, centre_B) # 2.0 11.0
ROUND 2 -- ASSIGN: SAME PILES, NOBODY SWITCHED -> STOP
TIGHTNESS (INERTIA): SQUARED GAP FROM EACH DOT TO ITS OWN CENTRE
tight_A = (1-2)**2 + (2-2)**2 + (3-2)**2 # 1 + 0 + 1 = 2
tight_B = (10-11)**2 + (11-11)**2 + (12-11)**2 # 1 + 0 + 1 = 2
total_tight = tight_A + tight_B # 4
print(tight_A, tight_B, total_tight) # 2 2 4
SILHOUETTE FOR DOT 1: A = AVG GAP TO OWN PILE-MATES; B = AVG GAP TO OTHER PILE
a_1 = (abs(1-2) + abs(1-3)) / 2 # (1+2)/2 = 1.5
b_1 = (abs(1-10) + abs(1-11) + abs(1-12)) / 3 # (9+10+11)/3 = 10
fit_1 = (b_1 - a_1) / max(a_1, b_1) # (10-1.5)/10 = 0.85
print(round(a_1,1), round(b_1,1), round(fit_1,2)) # 1.5 10.0 0.85
SILHOUETTE FOR DOT 3: EDGE OF PILE A
a_3 = (abs(3-1) + abs(3-2)) / 2 # (2+1)/2 = 1.5
b_3 = (abs(3-10) + abs(3-11) + abs(3-12)) / 3 # (7+8+9)/3 = 8
fit_3 = (b_3 - a_3) / max(a_3, b_3) # (8-1.5)/8 = 0.8125
print(round(a_3,1), round(b_3,1), round(fit_3,2)) # 1.5 8.0 0.81
Six dots, two piles, tightness 4, both edge dots snug. The toolbox block below runs
the same two moves on the full 50-state sheet:
>> NEW TO PYTHON? Each named once:
KMeans(n_clusters=K) -- the grouping machine, K piles
.fit(X) -- run the two moves on a loop until settled
.labels_ -- which pile each row landed in (0..K-1)
.cluster_centers_ -- the final centre of each pile
.inertia_ -- the tightness score (lower = tighter)
silhouette_score(X, labels) -- the average home-vs-next-door fit score
import numpy as np
import matplotlib.pyplot as plt
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import KMeans
SAME-RULER FIRST
X_scaled = StandardScaler().fit_transform(df)
ONE GROUPING WITH K = 3
km = KMeans(n_clusters=3, n_init=10, random_state=42)
km.fit(X_scaled)
labels = km.labels_ # pile per row
centres = km.cluster_centers_ # the 3 centres
print(km.inertia_) # the tightness
ELBOW: TIGHTNESS FOR K = 1..8 -- run k-means once per k, keep each tightness
tightness = []
for k in range(1, 9):
km = KMeans(n_clusters=k, n_init=10, random_state=42).fit(X_scaled)
tightness.append(km.inertia_)
The list `tightness` now holds one number per k, falling fast then flattening:
tightness
| * k=1: one pile, everything lumped -> huge
| *
| * . steep drop as the real groups split out
| * . .
| * . . . the BEND: extra piles stop helping here
+----------------------------- k
1 2 3 4 5 6 7 8
plt.plot(range(1, 9), tightness, marker="o"); plt.show() # draws the curve above
PICK K AT THE BEND
SECOND RULER: AVERAGE FIT SCORE PER K (STARTS AT K=2 -- SEE THE NOTE)
from sklearn.metrics import silhouette_score
fits = []
for k in range(2, 9):
km = KMeans(n_clusters=k, n_init=10, random_state=42).fit(X_scaled)
fits.append(silhouette_score(X_scaled, km.labels_))
plt.plot(range(2, 9), fits, marker="o")
plt.xlabel("K (number of piles)")
plt.ylabel("average fit score (silhouette)")
plt.title("Fit score: pick K at the highest peak")
plt.grid(True, linestyle="--", alpha=0.4)
plt.show()
PICK K AT THE PEAK -- NO SQUINTING AT A BEND
----------------------------------------------------------------------------------------------
IN THIS CHAPTER (Chapter 6 -- Finding Patterns Without Answers):
Part 1 -- Looking at a Sheet With No Answers .
Part 2 -- The Strongest Direction (PCA) .
Part 3 (this post) .
Part 4 -- The Family Tree (Hierarchical Clustering) .
Part 5 -- Both Tools on NCI60 (Re-visited) .
Part 6 -- Filling the Blanks (Recommender Systems)
<- Back to all posts
----------------------------------------------------------------------------------------------
home . source on GitHub
==============================================================================================