Distance measurement

KNN measures distance between examples using Euclidean or Manhattan distance.

Euclidean distance

KNN's default distance is Euclidean distance: the square root of the sum of squared differences, i.e. the straight-line length between two points.

a = np.array([1, 2])
b = np.array([4, 6])
print(np.sqrt(((a - b) ** 2).sum()))   # 5.0
print(np.linalg.norm(a - b))           # 5.0

All features enter the sum with the same weight, so features with different units must be scaled first.

Manhattan and metric

Manhattan distance is the sum of the absolute differences, like walking city blocks. In KNN it is chosen with the metric parameter:

print(np.abs(a - b).sum())   # 7  Manhattan
m = KNeighborsClassifier(n_neighbors=3, metric="manhattan")

With outliers or many dimensions, Manhattan sometimes does better; which one fits is chosen by validation.

Exercise Compute the distances

Compute the Euclidean distance from the query point q to every point in X using broadcasting (np.sqrt(((X - q) ** 2).sum(axis=1))) and print it. Then print the index of the nearest point with argmin.

Show example solution

import numpy as np

X = np.array([[0, 0], [3, 4], [1, 1], [6, 8]])
q = np.array([1, 0])

d = np.sqrt(((X - q) ** 2).sum(axis=1))
print(d)
print(d.argmin())

Test yourself

What is the Euclidean distance between (0, 0) and (6, 8)?
- 14
- 48
- 100
- 10
Show answer

10 — ��(6² + 8²) = √100 = 10.

Use the Manhattan distance.

m = KNeighborsClassifier(n_neighbors=3, metric=____)

Show answer

m = KNeighborsClassifier(n_neighbors=3, metric="manhattan")

Match the distances with the formulas.

Euclidean

√Σ(a-b)²
Manhattan

Σ|a-b|
np.linalg.norm(a-b)

Euclidean length
metric=

KNN distance choice

Next lesson: Classification

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies