==============================================================================================
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 1 OF 6
Looking at a Sheet With No Answers: Means, Distance, and the Ruler Problem
============================================================================================
Every post before this one had an answer column to check against.
That answer column held a house price, a car's mileage, a sick-or-well flag, or a diabetes score.
This post has NO answer column at all.
The sheet here is just 50 states and 3 measurements.
No answer column means you cannot ask "did the machine get it right?"
So the question changes.
The new question is: which states look like each other?
And: which states are strange?
The tools are simple.
There is the mean, which is the middle value of a column (add every value, divide by how many).
There is the spread, which is how far the values sit from that middle.
There is a ruler, which measures the gap between two rows.
The catch is also simple. Put two columns side by side -- Murder, which runs 0
to about 17, and Assault, which runs 0 to about 292 -- and ask for the gap
between two states, Alabama and Arizona:
Murder gap : 13.2 vs 8.1 -> 5.1
Assault gap: 236 vs 294 -> 58
total gap = sqrt(5.1^2 + 58^2) = sqrt(26 + 3364) ~ 58.2
The 58 from Assault swallows the 5.1 from Murder almost whole -- whatever the
two states differ by in murder rate is lost in the rounding. You meant to
compare on two columns and secretly compared on one, the loud one, dressed up
as two.
So before measuring any gap, stand every column on the same ruler: shift each
to the same spread, a z-score. Now Murder and Assault speak at equal volume and
every column casts a real vote in the gap.
THE SHEET
State Murder Assault UrbanPop
------- ------ ------- --------
Alabama 13.2 236 58
Alaska 10.0 263 48
Arizona 8.1 294 80
Arkansas 8.8 190 50
California 9.0 276 91
Colorado 7.9 204 78
... ... ... ...
Wyoming 6.8 161 60
50 states (rows). 3 measurements (columns). Zero answer columns.
Murder = murder arrests per 100,000 people
Assault = assault arrests per 100,000 people
UrbanPop = percent of people living in cities
No right answer. The goal: find which states are most alike.
MIDDLE AND THE SPREAD
For each column, compute two numbers.
The first is the middle, called the mean: add up all 50 values, then divide by 50.
The second is the spread, called the standard deviation: it says how far the values sit from the mean.
To get the spread, measure each value's gap from the mean.
Then square that gap.
Then average the squares.
Then take the square root of that average.
With the full sheet in front of you (all 50 states):
column mean spread
------- ----- -------
Murder 7.79 4.36
Assault 170.76 83.34
UrbanPop 65.54 14.47
Assault's mean is 170.76.
Murder's mean is 7.79.
Divide one by the other: 170.76 / 7.79 ~= 21.9.
Which means Assault's middle is about twenty-two times larger than Murder's middle.
Assault's spread is 83.34.
Murder's spread is 4.36.
Divide one by the other: 83.34 / 4.36 ~= 19.1.
Which means Assault's spread is about twenty times larger than Murder's spread.
This is a warning light: Assault's numbers are much bigger.
Therefore Assault will dominate any gap measurement unless we intervene.
RULER PROBLEM
The range of a column is its biggest value minus its smallest value (max - min).
Look at the range of each column:
Murder: 17.4 - 0.8 = 16.6
Assault: 337 - 45 = 292
UrbanPop: 91 - 32 = 59
Assault has the widest range by far.
When you measure "how far apart are two states", the Assault gap can be up to 292 units.
But the Murder gap is at most 16.6 units.
Divide the two ranges: 292 / 16.6 ~= 17.6.
Which means the Assault column shouts about seventeen times louder than Murder.
Therefore the gap number mostly reflects Assault, not the full picture.
GAP BETWEEN TWO STATES: TWO RULERS
IN HAND: a sheet of 50 states by 3 columns.
In hand also: a middle (mean) and a spread (standard deviation) for each column.
And a warning: Assault's range is 337 - 45 = 292, which dwarfs Murder's range of 17.4 - 0.8 = 16.6.
This section adds the ruler itself.
There are two ways to measure the gap between two rows.
You have two states.
Each state has three numbers.
How far apart are the two states?
--- STRAIGHT-LINE GAP (Euclidean distance) ---
Euclidean distance is the straight-line gap, the way a ruler laid flat measures it.
In the formula below, m1 and m2 are the two Murder values, a1 and a2 the two Assault values, u1 and u2 the two UrbanPop values.
gap = sqrt( (m1 - m2)^2 + (a1 - a2)^2 + (u1 - u2)^2 )
Square each difference, so a negative gap and a positive gap don't cancel.
Then add the squares.
Then take the square root, to get back to the original units.
--- CITY-BLOCK GAP (Manhattan distance) ---
Manhattan distance is the city-block gap.
The bars |...| mean absolute value: drop any minus sign and keep the size.
gap = |m1 - m2| + |a1 - a2| + |u1 - u2|
There is no squaring.
There is no square root.
You just take the absolute differences and add them up.
It is called "city-block" because it measures like walking around a grid.
That is the opposite of cutting diagonally through the block.
A WORKED EXAMPLE: ALABAMA VS ALASKA, BY HAND
Alabama: Murder=13.2 Assault=236 UrbanPop=58
Alaska: Murder=10.0 Assault=263 UrbanPop=48
STRAIGHT-LINE:
Murder gap: 13.2 - 10.0 = 3.2 squared = 3.2 * 3.2 = 10.24
Assault gap: 236 - 263 = -27 squared = 27 * 27 = 729
UrbanPop gap: 58 - 48 = 10 squared = 10 * 10 = 100
sum of squares: 10.24 + 729 + 100 = 839.24
sqrt: sqrt(839.24) ~= 28.97
Straight-line gap = 28.97
CITY-BLOCK:
Murder gap: |13.2 - 10.0| = 3.2
Assault gap: |236 - 263| = 27
UrbanPop gap: |58 - 48| = 10
sum: 3.2 + 27 + 10 = 40.2
City-block gap = 40.2
The city-block gap (40.2) is larger than the straight-line gap (28.97).
This holds for the same two points every time.
The reason: the diagonal is shorter than the L-shaped walk.
Two more states (made-up).
State X has Murder 6.0, Assault 200, UrbanPop 50.
State Y has Murder 9.0, Assault 240, UrbanPop 60.
Work BOTH gaps on the slate.
check your slate:
STRAIGHT-LINE -- Murder gap 6 - 9 = -3, squared = 9.
Assault gap 200 - 240 = -40, squared = 1600.
UrbanPop gap 50 - 60 = -10, squared = 100.
sum 9 + 1600 + 100 = 1709.
sqrt(1709) ~= 41.3.
CITY-BLOCK -- 3 + 40 + 10 = 53.
City-block (53) tops straight-line (41.3), as the L-walk always does.
And Assault's 1600 drowns the other two.
THE SHEET OF GAPS
Now repeat the straight-line gap for ALL pairs of states.
There are 50 states.
So you get a 50x50 sheet.
Each cell holds the gap between state i and state j:
AL AK AZ AR CA CO ...
AL [ 0 28.97 ... ... ... ... ]
AK [28.97 0 ... ... ... ... ]
AZ [ ... ... 0 ... ... ... ]
AR [ ... ... ... 0 ... ... ]
CA [ ... ... ... ... 0 ... ]
CO [ ... ... ... ... ... 0 ]
...
Diagonal = 0 (a state is zero distance from itself).
Symmetric: AL-AK = AK-AL.
This sheet IS the foundation of clustering.
Every grouping method starts from some version of "who is closest to whom."
THE SAME RULER: STANDARDISATION
The gap between Alabama and Alaska came out to 28.97.
That number is heavily influenced by Assault.
The reason: Assault's numbers are huge, with a gap of 236 - 263 = -27, so 27 in size.
The Murder gap is only 13.2 - 10.0 = 3.2, which barely registers.
Fix: put every column on the SAME ruler before measuring gaps.
The same-ruler value is called the z-score.
It says how many spreads above or below the mean a raw value sits.
standardised value (z-score) = (raw value - column mean) / column spread
The mean and spread for each column, restated here so you need nothing else:
Murder: mean=7.79, spread=4.36
Assault: mean=170.76, spread=83.34
UrbanPop: mean=65.54, spread=14.47
Alabama after standardisation:
Murder z: (13.2 - 7.79) / 4.36 = 5.41 / 4.36 = 1.24
Assault z: (236 - 170.76) / 83.34 = 65.24 / 83.34 = 0.78
UrbanPop z: (58 - 65.54) / 14.47 = -7.54 / 14.47 = -0.52
Alaska after standardisation:
Murder z: (10.0 - 7.79) / 4.36 = 2.21 / 4.36 = 0.51
Assault z: (263 - 170.76) / 83.34 = 92.24 / 83.34 = 1.11
UrbanPop z: (48 - 65.54) / 14.47 = -17.54 / 14.47 = -1.21
Now every column has mean about 0 and spread about 1.
Therefore no column shouts louder than another.
Standardised Alabama:
Murder: 1.24 Assault: 0.78 UrbanPop: -0.52
Standardised Alaska:
Murder: 0.51 Assault: 1.11 UrbanPop: -1.21
FAIR GAP (AFTER SAME-RULER)
Straight-line gap on standardised numbers:
Murder gap: 1.24 - 0.51 = 0.73 squared = 0.73 * 0.73 = 0.53
Assault gap: 0.78 - 1.11 = -0.33 squared = 0.33 * 0.33 = 0.11
UrbanPop: -0.52 - (-1.21) = 0.69 squared = 0.69 * 0.69 = 0.48
sum of squares: 0.53 + 0.11 + 0.48 = 1.12
sqrt: sqrt(1.12) ~= 1.06
Fair gap = 1.06
The raw gap was 28.97.
The fair gap is 1.06.
The raw gap was dominated by Assault's units, which run into the hundreds.
The fair gap treats every column equally.
A state (made-up) has Murder = 16.0.
Murder's mean is 7.79.
Murder's spread is 4.36.
Put that one number on the same ruler (the z-score = (raw - mean) / spread).
check your slate:
z = (16.0 - 7.79) / 4.36.
16.0 - 7.79 = 8.21.
8.21 / 4.36 ~= 1.88.
The state sits about 1.88 spreads ABOVE the average murder rate.
So it is a high-murder state.
And it is now in plain ruler-units, which any other column can be compared against.
CLOSEST PAIR
Build the 50x50 fair gap sheet.
Fair gap means the straight-line gap measured on standardised numbers, not raw numbers.
Now find the smallest non-zero entry in that sheet.
The two states with the smallest gap are the most similar state-pair.
Which pair is it?
That is for you to look up from the full sheet.
ASK THE CLOSEST NEIGHBORS
For any state, you can find its k nearest neighbours.
The k nearest neighbours are the k states with the smallest fair gaps to it.
Take California, and pick k = 3.
Then your paper would list the three states with the smallest standardised gaps to California.
This is the same "ask the closest rows" idea.
k-nearest neighbours means: to label or describe a row, look at the k rows with the smallest gaps to it.
Here there is NO answer column.
So you just list who is nearby.
That is the core of unsupervised learning: looking at neighbours without a right answer to check.
A few places this lab bites, each a thing that looks right.
The raw Alabama-Alaska gap of 28.97 is not wrong -- the arithmetic is exact. It is
unfair:
28.97 ~ almost entirely the Assault gap + a sliver of everything else
(Assault's big units swamp the rest)
Mathematically correct, practically misleading. For any distance-based method,
standardising first is not optional.
ddof picks which spread formula you divide by, and the two disagree:
ddof=0 -> divide by n (population) -- matches StandardScaler
ddof=1 -> divide by n-1 (sample) -- a slightly different number
Standardise with ddof=1 and your z-scores will not match the scaler's. Use ddof=0
so the two agree.
Forget index_col=0 on load and the state names come in as a data column instead of
row labels:
with index_col=0: shape (50, 3) state = label, 3 real columns
without: shape (50, 4) "Alabama" becomes a 4th "number" column
Then the distance maths tries to subtract state names. Always mark the label
column.
Two rulers, neither right nor wrong, just for different jobs:
Euclidean: straight-line gap sqrt(dx^2 + dy^2) (the default)
Manhattan: city-block gap |dx| + |dy| (handles outliers better)
No squaring in Manhattan means no single huge gap dominates. Pick by the job, not
by "correctness".
Every state is distance 0 from itself, so the gap sheet's diagonal is all zeros:
AL AK AZ
AL [ 0 .. .. ]
AK [ .. 0 .. ] the 0s are state-to-self, not real closest pairs
AZ [ .. .. 0 ]
Hunt the smallest gap as-is and you "find" a state paired with itself. Set the
diagonal to infinity before searching for the minimum.
The straight diagonal is the shortest way between two points; walking the grid is
always at least as long:
B
/| straight (Euclidean) = 5
/ | grid (Manhattan) = 3 + 4 = 7
/ |
A---+
So Manhattan >= Euclidean, every time. If yours comes out smaller, the arithmetic
slipped.
Last, standardising can change which pair is closest -- and that is correct, not a
bug:
raw: A-B closest (one big-range column dominated)
standardised: A-C closest (now every column gets an equal say)
A different column carries the gap once the scales are fair, so the order moves.
Expected.
Plain term used above Standard label
----------------------------------- ------------------------------------------
sheet with no answer column unlabelled data / unsupervised learning
middle of a column mean / average
spread of a column standard deviation (std / sigma)
range (max - min) feature range
straight-line gap Euclidean distance (L2)
city-block gap Manhattan distance (L1)
sheet of gaps pairwise distance matrix
same ruler / standardised z-score / StandardScaler
fair gap standardised Euclidean distance
closest pair (smallest gap) nearest neighbours
closest k states to anchor k-nearest neighbours (KNN lookup)
column feature / variable
row observation / sample
Nothing above needed a computer -- only pencils, clerks, and patience.
This last section is for the day you meet one.
It is the same work, spoken in Python.
First the Alabama-Alaska gaps from the worked example, hard-coded:
import math
ALABAMA AND ALASKA, RAW MEASUREMENTS
al_murder, al_assault, al_urbanpop = 13.2, 236, 58
ak_murder, ak_assault, ak_urbanpop = 10.0, 263, 48
LINE THE TWO ROWS UP AND SUBTRACT, COLUMN BY COLUMN
Alabama [ 13.2 236 58 ]
Alaska [ 10.0 263 48 ]
---------------------------------
gap 3.2 -27 10 (Alabama minus Alaska)
STRAIGHT-LINE (EUCLIDEAN) GAP -- RAW, UNFAIR: square each gap, add, root
euclid_raw = math.sqrt((al_murder-ak_murder)**2 + (al_assault-ak_assault)**2 + (al_urbanpop-ak_urbanpop)**2)
# 3.2**2 + 27**2 + 10**2 = 10.24 + 729 + 100 = 839.24
# sqrt(839.24) = 28.97 -- 729 dwarfs the rest, so the raw gap is almost all Assault
print(round(euclid_raw, 2)) # 28.97
CITY-BLOCK (MANHATTAN) GAP -- RAW, UNFAIR: add the bare gaps, no squaring
manhattan_raw = abs(al_murder-ak_murder) + abs(al_assault-ak_assault) + abs(al_urbanpop-ak_urbanpop)
# 3.2 + 27 + 10 = 40.2
print(round(manhattan_raw, 1)) # 40.2 (city-block always >= straight-line)
STANDARDISE: Z = (RAW - MEAN) / SPREAD (MEANS AND SPREADS FROM THE FULL 50-STATE SHEET)
murder_mean, murder_spread = 7.79, 4.36
assault_mean, assault_spread = 170.76, 83.34
urbanpop_mean, urbanpop_spread = 65.54, 14.47
al_m_z = (al_murder - murder_mean) / murder_spread # (13.2-7.79)/4.36 = 1.24
al_a_z = (al_assault - assault_mean) / assault_spread # (236-170.76)/83.34 = 0.78
al_u_z = (al_urbanpop- urbanpop_mean) / urbanpop_spread # (58-65.54)/14.47 = -0.52
ak_m_z = (ak_murder - murder_mean) / murder_spread # (10-7.79)/4.36 = 0.51
ak_a_z = (ak_assault - assault_mean) / assault_spread # (263-170.76)/83.34 = 1.11
ak_u_z = (ak_urbanpop- urbanpop_mean) / urbanpop_spread # (48-65.54)/14.47 = -1.21
print(round(al_m_z,2), round(al_a_z,2), round(al_u_z,2)) # 1.24 0.78 -0.52
print(round(ak_m_z,2), round(ak_a_z,2), round(ak_u_z,2)) # 0.51 1.11 -1.21
FAIR GAP -- STRAIGHT-LINE ON STANDARDISED NUMBERS
# the standardised gap, column by column: (1.24-0.51, 0.78-1.11, -0.52-(-1.21))
# = ( 0.73, -0.33, 0.69 )
euclid_fair = math.sqrt((al_m_z-ak_m_z)**2 + (al_a_z-ak_a_z)**2 + (al_u_z-ak_u_z)**2)
# 0.73**2 + 0.33**2 + 0.69**2 = 0.53 + 0.11 + 0.48 = 1.12 ; sqrt(1.12) = 1.06
print(round(euclid_fair, 2)) # 1.06 (fair: each column gets equal voice)
That is one pair by hand. The same squaring-and-rooting, run over all 50 states,
fills a 50x50 sheet of gaps -- every state against every other. Here is the
top-left 5x5 corner, every entry computed exactly as the 28.97 was (the three
column-gaps squared, summed, rooted):
RAW DISTANCE SHEET (Euclidean), a corner of the full 50x50:
Alabama Alaska Arizona Arkansas California
Alabama 0.00 28.97 62.24 46.90 52.02
Alaska 28.97 0.00 44.59 73.04 44.93
Arizona 62.24 44.59 0.00 108.24 21.11
Arkansas 46.90 73.04 108.24 0.00 95.27
California 52.02 44.93 21.11 95.27 0.00
... ... ... ... ... ...
(50 rows x 50 cols. the diagonal is 0 -- each state to itself. the sheet is
mirror-symmetric: Alabama-to-Alaska equals Alaska-to-Alabama, both 28.97)
One worked off-diagonal entry, Arizona-California, so the sheet is not magic:
Arizona [ 8.1 294 80 ]
California [ 9.0 276 91 ]
----------------------------------
gap -0.9 18 -11
sqrt(0.9**2 + 18**2 + 11**2) = sqrt(0.81 + 324 + 121) = sqrt(445.81) = 21.11
To find the closest PAIR, blank out the zero diagonal and hunt the smallest number.
In this corner the smallest off-diagonal gap is Arizona-California at 21.11. On the
full standardised sheet -- every column on one ruler first -- the nearest two states
come out closer still.
And the same thing, for the day you meet a computer:
import pandas as pd
from scipy.spatial.distance import pdist, squareform
from sklearn.preprocessing import StandardScaler
df = pd.read_csv("us_arrests.csv", index_col=0) # 50 rows x 3 columns
raw = squareform(pdist(df, metric="euclidean")) # the 50x50 sheet above
print(round(raw[0, 1], 2)) # 28.97 Alabama-Alaska
z = StandardScaler().fit_transform(df) # each column -> mean 0, spread 1
fair = squareform(pdist(z, metric="euclidean")) # the fair sheet
print(round(fair[0, 1], 2)) # 1.06 Alabama-Alaska, fair
Two reads of that fair sheet answer the usual questions. The closest PAIR is the
smallest number anywhere off the zero diagonal. The k NEAREST states to one anchor
is just that anchor's ROW, sorted, with its own 0 dropped:
fair[Alabama] = [ 0.00 1.06 ... ] sort ascending, drop the 0, take k
AL AK -> the states most like Alabama
# closest PAIR: smallest off-diagonal entry in the whole sheet
np.fill_diagonal(fair, np.inf) # hide each state-to-itself 0
i, j = np.unravel_index(fair.argmin(), fair.shape)
print(df.index[i], df.index[j]) # the two most-alike states
# k NEAREST to one state: sort that state's row, take the first k
row = fair[df.index.get_loc("Alabama")]
print(list(df.index[np.argsort(row)[:4]])) # Alabama, then its 3 closest
----------------------------------------------------------------------------------------------
IN THIS CHAPTER (Chapter 6 -- Finding Patterns Without Answers):
Part 1 (this post) .
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 (Re-visited) .
Part 6 -- Filling the Blanks (Recommender Systems)
<- Back to all posts
----------------------------------------------------------------------------------------------
home . source on GitHub
==============================================================================================