==============================================================================================
RAHUL'S ML BLOG -- notes on machine learning, worked out by hand est. 2026
==============================================================================================
home | about | archive | glossary | contact
----------------------------------------------------------------------------------------------
APPENDIX . DISTANCE AND CLUSTERING REFERENCE
Rulers, Traps, and the Ethics of Sorting People Into Piles
============================================================================================
This is the appendix to Chapter 6 (Finding Patterns Without Answers). The chapter draws
each idea by hand; this is a flip-to reference for the loose ends the chapter does not
stop for -- two more rulers, the pitfalls that bite, and the part nobody puts in the lab
but everybody should: the ethics of sorting people into piles. Plain language first,
standard labels at the very bottom.
Picture a galaxy's arm: a long curve of dots, each close to its neighbour, but
the two ends nowhere near each other.
* *
* *
* * * * * * * * * * *
|<--------- one real group ---------->|
A Z
K-means and hierarchical clustering ask only one thing: how far is each dot
from a CENTRE, in a straight line? Drop a centre in the middle of that arm and
the tips A and Z sit miles from it -- further than dots in a whole separate
blob. So the method tears the single arm into ten little balls and calls them
ten groups. It knows only round.
Stop measuring to a centre, then. Measure dot to dot and follow the chain: if A
touches its neighbour, and that one touches the next, they are one group no
matter how the curve bends:
A - * - * - * - * - * - * - * - * - Z one chain held together = one cluster
That is density-based clustering (DBSCAN): a cluster is any run of dots packed
closely enough to hold hands, whatever shape the run happens to make.
HOW MANY PILES? -- THE K YOU PICK
K-means (Chapter 6, Part 3) cannot invent the number of groups. You name it first.
you say k = 3 -> the machine builds exactly 3 piles, no more, no fewer
The machine obeys blindly: ask for k = 5 on data with 2 real clumps and it WILL hand you
5 piles, splitting real groups to do it. Pick k at the elbow (Part 3), not by feel.
MEASURING WORDS, NOT NUMBERS -- HAMMING DISTANCE
Every ruler in Chapter 6 (straight-line, city-block) needs numbers to subtract. But a
column might hold WORDS -- "yes/no", "red/blue/green", a strand of DNA letters. You
cannot subtract "red" from "blue".
The fix is the simplest ruler there is: walk the two rows box by box and COUNT THE
MISMATCHES.
row A: yes red L yes
row B: yes blue L no
--------------------
match? ok X ok X -> 2 mismatches -> Hamming gap = 2
Same boxes match -> add nothing. Boxes differ -> add one. That mismatch count is the
Hamming distance.
Two bit-strings (made-up): 10110 and 11100. Count the Hamming gap.
check your slate: compare position by position -- 1=1 ok, 0 vs 1 X, 1=1 ok,
1 vs 0 X, 0=0 ok. Two boxes differ, so the Hamming gap = 2.
Two words: HOT and HAT. Count the Hamming gap.
check your slate: H=H ok, O vs A X, T=T ok. One box differs, so the Hamming
gap = 1 -- a single-letter swap apart.
It is the natural gap for categories and bit-strings, where "how far
apart" just means "how many positions disagree."
WHEN THE ROOM HAS TOO MANY WALLS -- MAHALANOBIS DISTANCE
The straight-line ruler quietly assumes every column is independent and on the same
scale. When columns move together as a pack (collinearity, from Chapter 2) or the cloud
is stretched lopsided, plain straight-line distance is misled -- it double-counts the
directions where the data is already wide.
plain straight-line: treats the cloud as a round ball
Mahalanobis: first un-stretches the cloud back to a ball, THEN measures
Mahalanobis distance accounts for how the dots are spread and correlated -- it divides
out the stretch before measuring, so a step across a narrow direction counts for more
than a step along a wide one. It is the stronger ruler for many-walled, correlated rooms.
(It is the same un-tangling move as the straight-stick rule's (X^T X)^-1 -- a sheet of
numbers that records how the columns stretch and lean together, then divides that stretch
back out before measuring.)
SPILLED COFFEE -- MISSING DATA
Real sheets have holes: someone never answered, a sensor failed, coffee erased a cell.
Two tempting moves are both dead ends:
DROP the row -> you may throw away most of the sheet, and bias what is left
WRITE A FAKE -> guessing the mean fills the hole but RUINS the fair ruler
(it shrinks the spread and pulls every gap toward that row)
Before patching anything, put on the detective hat and ask WHY the hole is there:
missing at random -> a careful fill (imputation) is defensible
missing for a reason -> the hole itself is a signal (e.g. "income" blank
only for the unemployed) -- filling it hides the truth
The pattern of the holes matters more than the holes. Decide what the blank MEANS before
you decide what to write in it.
WHY CRUSH THE ROOM -- DIMENSIONALITY REDUCTION
PCA (the strongest-direction tool from Chapter 6, Part 2) crushes a many-wall room to a
flat page. Three reasons it is worth doing, beyond just "to draw it":
- throw away noise -- the weak, redundant walls only confuse the gap; drop them
- let human eyes see it -- you cannot picture 13 walls; you can picture 2
- less math to do -- fewer walls means far cheaper distances and fits
The cost is blur (reconstruction error, Part 2): crush too hard and you lose real
structure. Keep enough shadows to stay honest (the 80% rule of thumb), no more.
PART THE LAB SKIPS -- ETHICS OF SORTING PEOPLE
Every tool in this chapter sorts rows into piles. When the rows are PEOPLE, the math
carries weight it never warns you about:
BIAS IN THE DATA
If the sheet only recorded tall people, every pile is unfair to short people.
The machine cannot find a pattern the data never showed it -- and it will
confidently mistreat whoever was under-counted.
PRIVACY
A clustering sheet can hold secret, sensitive things. Grouping people by their
data can leak what they never agreed to share -- and a pile label can out someone.
TRANSPARENCY
If a person asks "why did you put me in the bad pile?", you must be able to point
to the gap you measured and the columns that drove it. A secret black box that
cannot explain its piles is not just unhelpful -- it is unfair.
A PILE IS A DECISION ABOUT A PERSON
The moment a cluster decides who gets the loan, the ad, or the scrutiny, "it is just
distance" stops being an excuse. Measure on data you trust, guard what it holds, and
be ready to explain every wall you used.
WHAT THE PILES ARE FOR -- CUSTOMER SEGMENTATION
The whole point of grouping with no answer column: sweep look-alikes together so you can
treat each pile sensibly. The everyday name is CUSTOMER SEGMENTATION.
a shop sorts its buyers into piles by what they buy:
"Bargain Hunters" -> send the discount flyer
"Luxury Buyers" -> send the premium catalogue
No one labelled those shoppers in advance. The piles fall out of the data, and the names
are the story you tell after looking at each pile -- exactly the unsupervised idea from
the whole of Chapter 6.
The worked examples above (Hamming, dimension count, pinch-to-fit with an outlier) need
no library. Here they are as plain variables.
--- HAMMING DISTANCE: COUNT POSITIONS THAT DISAGREE ---
ROW A: YES, RED, L, YES
ROW B: YES, BLUE, L, NO
pos1 = 0 # yes == yes -> match
pos2 = 1 # red != blue -> mismatch
pos3 = 0 # L == L -> match
pos4 = 1 # yes != no -> mismatch
hamming_rows = pos1 + pos2 + pos3 + pos4 # 2
BIT-STRINGS 10110 AND 11100
b1 = [1, 0, 1, 1, 0]
b2 = [1, 1, 1, 0, 0]
mm1 = 0 if b1[0]==b2[0] else 1 # 0 (1==1)
mm2 = 0 if b1[1]==b2[1] else 1 # 1 (0!=1)
mm3 = 0 if b1[2]==b2[2] else 1 # 0 (1==1)
mm4 = 0 if b1[3]==b2[3] else 1 # 1 (1!=0)
mm5 = 0 if b1[4]==b2[4] else 1 # 0 (0==0)
hamming_bits = mm1 + mm2 + mm3 + mm4 + mm5 # 2
WORDS HOT AND HAT
ch1 = 0 if 'H'=='H' else 1 # 0
ch2 = 0 if 'O'=='A' else 1 # 1 (mismatch)
ch3 = 0 if 'T'=='T' else 1 # 0
hamming_words = ch1 + ch2 + ch3 # 1
Plain term used above Standard label
----------------------------------- ------------------------------------------
how many piles you pick (k) the number of clusters (n_clusters)
count the mismatches Hamming distance
un-stretch the cloud, then measure Mahalanobis distance
the holes in the sheet missing data
fill a hole with a guess imputation
why the hole is there missing-at-random vs missing-not-at-random
crush the room dimensionality reduction
throw away weak walls noise / redundancy removal
unfair because of who was counted sampling bias / fairness
explain which walls drove the pile model interpretability / transparency
sweep buyers into piles customer segmentation
----------------------------------------------------------------------------------------------
SEE ALSO (Chapter 6 -- Finding Patterns Without Answers):
Part 1 -- Looking at a Sheet With No Answers .
Part 2 -- The Strongest Direction (PCA) .
Part 3 -- Grouping by Nearest Centre (K-Means) .
Part 4 -- The Family Tree (Hierarchical Clustering) .
Part 5 -- Both Tools on NCI60 .
Part 6 -- Filling the Blanks (Recommender Systems)
<- Back to all posts
----------------------------------------------------------------------------------------------
home . source on GitHub
==============================================================================================