Distance and Norms

Context

The distance between two listings is the length of the vector that runs from one to the other, their difference measured with Lesson 2.3.1's length. A norm is a rule for measuring the length of a single vector, and this lesson is built on two: the straight-line length, and the sum of the absolute values of the entries.

Finding the listings most like the one a buyer is looking at, flagging a listing that sits far from every other, and the nearest-neighbor model Module 3 introduces (one that predicts for a listing from the listings closest to it) all begin by computing the distance from one listing to many. An appraiser's list of comparable sales, read this way, is the smallest distances in a table.

A distance computed on raw features is dominated by the features whose values spread the widest. Area runs into the tens and hundreds of square meters and rooms into single figures, so the listing nearest to a four-room flat can turn out to have one room, and the result looks like any other number. A norm taken without its axis collapses a whole table into one number where one distance per listing was wanted. Lessons 2.3.1 and 2.3.2 measured how vectors point and how they combine, and this lesson measures how far apart they sit.

Goal

• Compute the Euclidean distance between two listings from its formula and with np.linalg.norm.
• Compute L2 and L1 norms, scale a vector to unit length, and take one norm per row of a table with axis=1.
• Compute the distance from one listing to every listing in a table, find the nearest with np.argmin, and build the full pairwise distance table.
• Show with a run how unscaled features decide which listing is nearest, and standardize first so that every feature counts.

Prerequisites

Optional, both of them. The lesson computes every distance from scratch, and these show the two kinds of distance it uses before you meet them.

• YouTube - "Euclidean Distance and Manhattan Distance" by Krish Naik. The straight-line distance and the distance measured along the axes, the two this lesson computes, explained side by side.
• Official docs - NumPy, numpy.linalg.norm. The table under Notes lists what each ord computes for a vector and for a matrix, the difference that decides what a missing axis returns.

Table of Contents

• Euclidean Distance
• Norms - L2 and L1
• Distances to Many Points at Once
• Why Feature Scale Dominates Distance

Theory

The examples describe a listing by two features, area_sqm and rooms, so every distance can be checked by hand, and every idea carries over to any number of features unchanged.

Euclidean Distance

What. The Euclidean distance between two listings is the straight-line distance between their points: subtract one vector from the other, square each difference, add the squares and take the square root, sqrt(sum((a - b) ** 2)). np.linalg.norm(a - b) computes the same number in one call, and on float features the two can differ in the last digits. Why. Distance measures similarity when being close on every feature is what matters, and it is the number a search for the nearest listing ranks by. When. Whenever two listings are compared feature by feature: finding comparables, catching near-duplicates, measuring how far one listing sits from the rest.

import numpy as np

a = np.array([80, 2])              # area_sqm, rooms
b = np.array([84, 5])

diff = a - b
print(diff)                        # [-4 -3]
print(diff ** 2)                   # [16  9]
print(np.sqrt((diff ** 2).sum()))  # 5.0

Squaring makes every difference count positively, whatever its sign, and the square root brings the total back to the features' own units. The sum under the root is the difference dotted with itself, so the distance is Lesson 2.3.1's length of the difference vector. np.linalg is NumPy's linear algebra module, part of NumPy with nothing extra to install, and np.linalg.norm returns that length directly, as a float64.

import numpy as np

a = np.array([80, 2])
b = np.array([84, 5])

print(np.sqrt((a - b) @ (a - b)))  # 5.0
print(np.linalg.norm(a - b))       # 5.0
print(np.linalg.norm(b - a))       # 5.0
print(np.linalg.norm(a - a))       # 0.0

The distance is the same in both directions, because b - a is a - b with every sign flipped and squaring removes the signs. It is zero only when the two listings match on every feature, as a listing does against itself or against a duplicate row, because any feature that differs adds a positive square to the sum.

DON'T:

• DON'T add the raw differences, (a - b).sum() is -7 here, and for [84, 1] against [80, 5] the differences 4 and -4 cancel to 0 for two listings that are 5.656854249492381 apart.
• DON'T subtract two lengths to get a distance, np.linalg.norm(a) - np.linalg.norm(b) is about -4.12 for these two listings, whose distance is 5.0, and two different listings of equal length would come out 0.
• DON'T forget the square root, ((a - b) ** 2).sum() is 25, the squared distance, which ranks listings in the same order but is in squared units and cannot be compared with a distance.

Norms - L2 and L1

What. A norm measures the length of one vector. np.linalg.norm(v) is the L2 norm, sqrt(v . v), the length of Lesson 2.3.1. np.linalg.norm(v, ord=1) is the L1 norm, the sum of the absolute values of the entries, also called the Manhattan norm. Why. A distance is the norm of a difference, so the norm decides what close means: L2 squares the gaps, so one large gap counts for more than several small ones with the same total, while L1 adds every gap at face value. When. L2 for the ordinary straight-line distance, L1 when a total of gaps should count the same however it is spread across the features, and a norm per row whenever a table holds one vector per listing.

import numpy as np

a = np.array([80, 2])            # area_sqm, rooms
b = np.array([84, 5])
d = a - b                        # [-4 -3]

print(np.linalg.norm(d))         # 5.0
print(np.linalg.norm(d, ord=1))  # 7.0

The L1 distance is the one a taxi drives on a street grid, 4 blocks along one axis and then 3 along the other, while the L2 distance is the straight line across the blocks. How the two treat one large gap against several small ones is the real difference between them.

import numpy as np

one_gap = np.array([4, 0])              # one feature differs by 4
two_gaps = np.array([2, 2])             # two features differ by 2 each

print(np.linalg.norm(one_gap, ord=1))   # 4.0
print(np.linalg.norm(two_gaps, ord=1))  # 4.0
print(np.linalg.norm(one_gap))          # 4.0
print(np.linalg.norm(two_gaps))         # 2.8284271247461903

A unit vector has length 1 and keeps only the direction: v / np.linalg.norm(v), for any vector but the all-zero one, which has no direction, so the division returns nan in every entry. Dividing two vectors by their lengths and then taking their dot product is Lesson 2.3.1's cosine computed in the other order.

import numpy as np

a = np.array([80, 2])
b = np.array([84, 5])
d = a - b
unit = d / np.linalg.norm(d)  # the direction from b to a

print(unit)                   # [-0.8 -0.6]
print(np.linalg.norm(unit))   # 1.0

A table holds one vector per listing, so it takes one norm per row, and that takes axis=1. In a standardized table (Lesson 2.2.5's mean 0 and standard deviation 1 per feature) the average listing sits at the origin, so a row's norm is how far that listing sits from the average one.

import numpy as np

# four listings from a standardized table: area_sqm, rooms
Z = np.array([[2, 1], [0, 0], [-1, 3], [-2, -2]])

norms = np.linalg.norm(Z, axis=1)
print(np.round(norms, 2))  # [2.24 0.   3.16 2.83]
print(np.linalg.norm(Z))   # 4.795831523312719

The second listing, all zeros, sits exactly on the average, and the third is the most unusual. Without axis, np.linalg.norm treats the whole table as one long vector and returns the square root of every squared entry added together, one number that belongs to no listing.

DON'T:

• DON'T drop axis=1 when you want one norm per listing, np.linalg.norm(Z) returns the single number 4.795831523312719 for the whole table and raises nothing.
• DON'T drop it with ord=1 either, np.linalg.norm(Z, ord=1) on a table is a different quantity again, the largest column sum of absolute values, 6.0 here, and not one L1 norm per listing.

Distances to Many Points at Once

What. X - x0 subtracts one listing from every row of a table by broadcasting, and np.linalg.norm(X - x0, axis=1) turns the differences into one distance per listing. np.argmin on those distances gives the position of the nearest listing. Why. Searching a table for the listings closest to a query is the core of a comparables report and of the nearest-neighbor model Module 3 introduces in 3.5.1, and one vectorized line does it for every listing at once. When. Whenever one listing is compared against many, and, with the pairwise table, whenever every listing is compared against every other.

import numpy as np

# area_sqm, rooms
X = np.array([[82, 1], [95, 4], [60, 3], [120, 5], [70, 2]])
x0 = np.array([85, 4])     # the query listing

print((X - x0).shape)      # (5, 2)
dist = np.linalg.norm(X - x0, axis=1)
print(np.round(dist, 2))   # [ 4.24 10.   25.02 35.01 15.13]
print(np.argmin(dist))     # 0
print(X[np.argmin(dist)])  # [82  1]

(5, 2) minus (2,) pairs from the right, 2.2.4's rule, so x0 is subtracted from every row, and axis=1 takes one norm per row. np.argmin returns a position, 2.2.5's, and X at that position is the nearest listing: 82 square meters with 1 room, for a query with 4 rooms. Keep that answer in mind, the last subtitle questions it.

The distance between every pair of listings needs every row subtracted from every row, which 2.2.4's np.newaxis sets up as a broadcast.

import numpy as np

X = np.array([[82, 1], [95, 4], [60, 3], [120, 5], [70, 2]])

diffs = X[:, np.newaxis, :] - X[np.newaxis, :, :]
print(diffs.shape)            # (5, 5, 2)
D = np.linalg.norm(diffs, axis=2)
print(D.shape)                # (5, 5)
print(np.abs(D - D.T).max())  # 0.0
print(np.round(D, 1))

[[ 0.  13.3 22.1 38.2 12. ]
 [13.3  0.  35.  25.  25.1]
 [22.1 35.   0.  60.  10. ]
 [38.2 25.  60.   0.  50.1]
 [12.  25.1 10.  50.1  0. ]]

X[:, np.newaxis, :] is (5, 1, 2) and X[np.newaxis, :, :] is (1, 5, 2), so the subtraction broadcasts to (5, 5, 2), and entry [i, j] is listing i minus listing j. The norm along axis=2, the features, leaves a (5, 5) table in which D[i, j] is the distance between listings i and j. Its diagonal is all zeros, each listing against itself, and it is symmetric, the same value on both sides of the diagonal, which np.abs(D - D.T).max() being 0.0 confirms.

DON'T:

• DON'T read np.argmin(dist) as a distance, it is a position, and dist[np.argmin(dist)] is the distance, 4.242640687119285 here.
• DON'T build the full pairwise table for a large set, the broadcast holds n times n times k numbers before the norm, 8,000,000,000 bytes of 64-bit values for 10,000 listings with 10 features.

Why Feature Scale Dominates Distance

What. Euclidean distance adds squared differences in each feature's own units, so the features whose values spread the widest dominate the distance. Standardizing the columns first, Lesson 2.2.5's (X - X.mean(axis=0)) / X.std(axis=0), measures every feature in its own standard deviations, so each gap counts by how unusual it is. Why. Area runs in the tens to hundreds and rooms in single figures, so on the table below an unscaled distance lets area decide which listing is nearest, and the listing it finds can be wrong on every other feature. When. Before any distance between listings whose features are measured in different units, which is nearly every real table.

import numpy as np

X = np.array([[82, 1], [95, 4], [60, 3], [120, 5], [70, 2]])
x0 = np.array([85, 4])

print((X - x0) ** 2)

[[   9    9]
 [ 100    0]
 [ 625    1]
 [1225    1]
 [ 225    4]]

Each row holds one listing's squared gaps, area first. The area column runs to 1225 while the rooms column never passes 9, so area decides which listing is nearest. The first listing won by being 3 square meters away, and its 3-room shortfall cost it no more than those 3 square meters did, although to a buyer three rooms are a far bigger difference.

import numpy as np

X = np.array([[82, 1], [95, 4], [60, 3], [120, 5], [70, 2]])
x0 = np.array([85, 4])

mu = X.mean(axis=0)
sd = X.std(axis=0)
Z = (X - mu) / sd
z0 = (x0 - mu) / sd        # the query, on the table's scale

dist = np.linalg.norm(Z - z0, axis=1)
print(np.round(sd, 2))     # [20.9   1.41]
print(np.round(dist, 2))   # [2.13 0.48 1.39 1.82 1.59]
print(X[np.argmin(dist)])  # [95  4]

The standard deviations are 20.9 square meters and 1.41 rooms, so once scaled a 3-room gap is worth about 2.1 units and a 3 square meter gap about 0.14. The nearest listing is now the second one, 10 square meters larger and identical in rooms. The query is scaled with the table's mean and standard deviation, the same mu and sd, so the query and the listings sit on one scale. Module 3's scaling lesson, 3.2.1, rests on this.

DON'T:

• DON'T measure distance on unscaled features with different units, area outvoted rooms above and handed a four-room query a one-room listing.
• DON'T standardize the query separately from the table, subtract the table's mu and divide by the table's sd, or the query and the listings sit on different scales.

Lab Exercises

Lab Exercise 1: Two Listings and the Gap Between Them

Two listings are described by area_sqm, rooms and age: p = np.array([70, 3, 10]) and q = np.array([72, 4, 12]). Compute their Euclidean distance three ways, from the formula with **, .sum() and np.sqrt, as the square root of the difference dotted with itself, and with np.linalg.norm, then show that swapping p and q changes nothing. Compute their L1 distance, and the unit vector pointing from q to p, printed rounded to 3 places, with its norm rounded to 10 places.

Then, for four listings taken from a standardized table, Z = np.array([[1, 2, 2], [0, 0, 0], [-2, 1, 2], [3, 0, -4]]), print each listing's distance from the average listing, then what np.linalg.norm(Z) returns without an axis, with a comment saying what that number is.

Lab Exercise 2: The Nearest Listing, Before and After Scaling

A buyer wants a listing like query = np.array([100, 2]), 100 square meters with 2 rooms, from this table of area_sqm and rooms.

import numpy as np

L = np.array([[96, 5], [110, 2], [130, 3], [75, 2], [102, 6], [90, 3]])

Print the distance from the query to every listing, rounded to 2 places, and the nearest listing. Build the pairwise distance table of the six listings, print it rounded to 1 place, and confirm in code that its diagonal is all zeros and that it is symmetric. Then standardize the table, scale the query on the table's scale, and print the distances and the nearest listing again, with a comment saying why the answer changed.

import numpy as np

p = np.array([70, 3, 10])                  # area_sqm, rooms, age
q = np.array([72, 4, 12])

print(np.sqrt(((p - q) ** 2).sum()))       # 3.0
print(np.sqrt((p - q) @ (p - q)))          # 3.0
print(np.linalg.norm(p - q))               # 3.0
print(np.linalg.norm(q - p))               # 3.0
print(np.linalg.norm(p - q, ord=1))        # 5.0

unit = (p - q) / np.linalg.norm(p - q)
print(np.round(unit, 3))                   # [-0.667 -0.333 -0.667]
print(np.round(np.linalg.norm(unit), 10))  # 1.0

import numpy as np

Z = np.array([[1, 2, 2], [0, 0, 0], [-2, 1, 2], [3, 0, -4]])

print(np.linalg.norm(Z, axis=1))  # [3. 0. 3. 5.]
# the whole table as one long vector: no listing's distance
print(np.linalg.norm(Z))          # 6.557438524302

import numpy as np

L = np.array([[96, 5], [110, 2], [130, 3], [75, 2], [102, 6], [90, 3]])
query = np.array([100, 2])

dist = np.linalg.norm(L - query, axis=1)
print(np.round(dist, 2))      # [ 5.   10.   30.02 25.    4.47 10.05]
print(L[np.argmin(dist)])     # [102   6]

D = np.linalg.norm(L[:, np.newaxis, :] - L[np.newaxis, :, :], axis=2)
print(np.round(D, 1))
# times the identity keeps only the diagonal
print((D * np.eye(6)).sum())  # 0.0
print(np.abs(D - D.T).max())  # 0.0

[[ 0.  14.3 34.1 21.2  6.1  6.3]
 [14.3  0.  20.  35.   8.9 20. ]
 [34.1 20.   0.  55.  28.2 40. ]
 [21.2 35.  55.   0.  27.3 15. ]
 [ 6.1  8.9 28.2 27.3  0.  12.4]
 [ 6.3 20.  40.  15.  12.4  0. ]]

# continuing the script above
mu = L.mean(axis=0)
sd = L.std(axis=0)
dist_z = np.linalg.norm((L - mu) / sd - (query - mu) / sd, axis=1)
print(np.round(dist_z, 2))   # [2.01 0.59 1.88 1.47 2.67 0.89]
print(L[np.argmin(dist_z)])  # [110   2]
# Unscaled, the 6-room listing won by being 2 sqm away: its 4-room gap
# counted like 4 sqm. Scaled, one standard deviation is 1.5 rooms but
# 17 sqm, so a room gap counts about 11 times a sqm gap.

Theory Assessment

Q1: The Distance Between Two Listings

For the listings [80, 2] and [84, 5], compute the Euclidean distance by hand, step by step. Explain why swapping the two listings cannot change the answer, when a distance can be zero, and how this distance relates to Lesson 2.3.1's length.

Hint: Follow the formula from the inside out. For the second half, ask what squaring does to a sign, and what the sum under the square root is in dot-product terms.

Q2: Two Norms and a Missing Axis

For d = [-4, -3], give the L2 and L1 norms and say why they differ. Then explain what the difference vectors [4, 0] and [2, 2] show about the two norms. Finally, for a table Z of standardized listings, say what np.linalg.norm(Z, axis=1) and np.linalg.norm(Z) each return.

Hint: One norm squares before it adds and one does not. For the table, ask how many numbers each call returns and which listing each number belongs to.

Q3: One Query Against a Table

Explain how np.linalg.norm(X - x0, axis=1) produces one distance per listing, naming the broadcast and the axis, and what np.argmin then returns. Then explain why, in the lesson's run, the nearest listing changed from [82, 1] to [95, 4] once the features were standardized, and why the query had to be scaled with the table's mean and standard deviation.

Hint: Look at the squared gaps of the first listing before scaling, area against rooms. Then ask what one unit of each feature is worth once it is divided by that feature's standard deviation.

Q4: Three Ways to Find the Nearest Listing

Three teammates each wrote one line to find the listing most like z0 in a table of standardized listings. Read the following without running it, then state what the last line prints.

import numpy as np

# listings from a standardized table: area_sqm, rooms
Z = np.array([[-2, -1], [0, 0], [2, 2], [1, 2]])
z0 = np.array([2, 1])  # the query listing

lengths = np.linalg.norm(Z, axis=1)
v1 = np.argmin(lengths - np.linalg.norm(z0))
v2 = np.argmin(np.abs(lengths - np.linalg.norm(z0)))
v3 = np.argmin(np.linalg.norm(Z - z0, axis=1))
print(v1, v2, v3)

Which line answers the question, and what did each of the other two find instead? Then explain why v2, whose idea sounds the most reasonable of the wrong two, picked the worst listing in the table.

Hint: Work out the length of every row and of z0, then the distance from z0 to every row. Two rows have exactly the same length as z0, and np.argmin returns the first position of the smallest value.

Assignment

Assignment: Comparables for an Appraiser

An appraiser values a listing of 88 square meters with 3 rooms, built 15 years ago, by looking at the three most comparable listings in a table of eight.

import numpy as np

# area_sqm, rooms, age
A = np.array([
    [90, 1, 14],
    [84, 3, 16],
    [100, 3, 15],
    [86, 5, 40],
    [70, 3, 14],
    [89, 3, 60],
    [120, 4, 10],
    [92, 2, 18],
])
query = np.array([88, 3, 15])

Write a script that ranks all eight listings by their distance to the query and reports the three nearest: their positions, their rows and their distances rounded to 2 places. Rank them with Lesson 2.2.2's np.argsort, whose first three positions, np.argsort(d)[:3], point at the three smallest values of d.

Produce the ranking twice, once on the raw features and once on features standardized with the table's own mean and standard deviation, and say in a comment which listing left the top three, which one entered, and what in their features explains the swap. Then rank the standardized listings by L1 distance, and again by the largest single gap, which np.linalg.norm returns with ord=np.inf, the norm that keeps only the largest absolute entry of a vector, and say whether the top three change. Finish by printing the squared standardized gaps of the listing that left and the listing that entered, and point in a comment at the feature that moved each one.

Hints:

• np.argsort returns positions, not distances, so use its first three entries to index both the table and the distances, A[order[:3]] and d[order[:3]].
• Compute the mean and the standard deviation once, with axis=0, from the eight listings, and give the query exactly the same treatment before taking any distance.

import numpy as np

# area_sqm, rooms, age
A = np.array([
    [90, 1, 14],
    [84, 3, 16],
    [100, 3, 15],
    [86, 5, 40],
    [70, 3, 14],
    [89, 3, 60],
    [120, 4, 10],
    [92, 2, 18],
])
query = np.array([88, 3, 15])

d_raw = np.linalg.norm(A - query, axis=1)
order_raw = np.argsort(d_raw)
print(order_raw[:3])                      # [0 1 7]
print(A[order_raw[:3]])
print(np.round(d_raw[order_raw[:3]], 2))  # [3.   4.12 5.1 ]

[[90  1 14]
 [84  3 16]
 [92  2 18]]

# continuing the script above
mu = A.mean(axis=0)
sd = A.std(axis=0)
Z = (A - mu) / sd
z_query = (query - mu) / sd           # the table's scale

d_z = np.linalg.norm(Z - z_query, axis=1)
order_z = np.argsort(d_z)
print(order_z[:3])                    # [1 2 7]
print(A[order_z[:3]])
print(np.round(d_z[order_z[:3]], 2))  # [0.3  0.89 0.96]
# Listing 0, 90 sqm with ONE room, left the top three: unscaled, its
# 2-room gap cost no more than 2 sqm. Listing 2, 100 sqm with 3 rooms
# and the same age, entered: 12 sqm is under one standard deviation.

[[ 84   3  16]
 [100   3  15]
 [ 92   2  18]]

# continuing the script above
d_l1 = np.linalg.norm(Z - z_query, ord=1, axis=1)
d_inf = np.linalg.norm(Z - z_query, ord=np.inf, axis=1)
print(np.argsort(d_l1)[:3])   # [1 2 7]
print(np.argsort(d_inf)[:3])  # [1 2 7]
# The same three both times: once every feature is in standard
# deviations, the straight-line, the grid and the largest-gap distance
# agree on these comparables.

print(np.round((Z[[0, 2]] - z_query) ** 2, 2))
# row 0, listing 0: rooms, 3.2, decides its distance
# row 1, listing 2: area, 0.8, is its only gap

[[0.02 3.2  0.  ]
 [0.8  0.   0.  ]]

Additional Resources

Optional, and nothing later depends on either. Worth opening if you want to see where nearest listings lead or what scaling does to a real model.

• YouTube - "StatQuest: K-nearest neighbors, Clearly Explained" by StatQuest with Josh Starmer. How a new point can be classified by the labels of its nearest neighbors, the step that comes after finding them.
• Official docs - scikit-learn, "Importance of Feature Scaling", the section "Effect of rescaling on a k-neighbors models". Two features of very different magnitudes, and how a nearest-neighbor classifier's decision boundary changes once they are standardized.

Summary

Distance turns out to be nothing new. It is the length from Lesson 2.3.1, applied to the difference between two listings, and the norms of this lesson are that same length with the rule for adding up the gaps made explicit. Squaring and adding gives the straight line, adding the absolute values gives the walk along the grid, and the choice between them is a choice about whether one large gap should outweigh several small ones. None of it needs new arithmetic, only a clear idea of which vector is being measured.

What the lesson adds is scale, in both senses. One line now measures a query against every listing in a table, and one broadcast measures every listing against every other, so a comparables search or an outlier check is a single expression rather than a loop. The same power is what makes the mistakes cheap to commit: a missing axis still returns a number, a ranking still returns positions, and nothing in the output says it measured the wrong thing.

The deepest point is the one about units. A distance has no idea that a room and a square meter are different things, so it lets the features with the widest spread dominate, and the answer it gives looks exactly as confident as a right one. Standardizing is the decision to count each feature by how unusual its gap is rather than by how widely its numbers happen to spread, and it is a modeling choice wearing the clothes of arithmetic. Every distance-based method you meet later inherits that choice, which is why the scaling step comes before the model and never after.

Cheat Sheet

Part A - Reference Table

Part B - Compact Code Block

import numpy as np

np.linalg.norm(a - b)                  # Euclidean distance
np.linalg.norm(v, ord=1)               # L1, Manhattan
v / np.linalg.norm(v)                  # unit vector
np.linalg.norm(Z, axis=1)              # one norm per row

dist = np.linalg.norm(X - x0, axis=1)  # query against all
X[np.argmin(dist)]                     # the nearest listing
np.argsort(dist)[:3]                   # three nearest positions
diffs = X[:, np.newaxis, :] - X[np.newaxis, :, :]
D = np.linalg.norm(diffs, axis=2)      # (n, n), zero diagonal

mu, sd = X.mean(axis=0), X.std(axis=0)
dist_z = np.linalg.norm((X - mu) / sd - (x0 - mu) / sd, axis=1)