Machine Learning Full Course · Episode 27. Every code sample below was run with Python 3.13, NumPy 2.5.3 and scikit-learn 1.9.1; the output shown is the real output (timings vary by machine). All data (pizza orders) is made up for teaching, except the mini project, which uses the handwritten-digits dataset bundled with scikit-learn.
The big idea: to predict for a new example, find the k most similar stored examples and let them vote (classification) or average their values (regression). There is no training beyond storing the data (lazy, instance-based learning), so kNN can follow any shape the data has, even a circle a straight line can't draw. Its quality depends on three choices: the distance metric, the number of neighbours k, and the scale of the features. It struggles with many features (the curse of dimensionality), and KD-trees or ball trees make the neighbour search fast when features are few.
Words you need first
- Feature: an input column (km east, km north). Label: the answer to predict (on time / late).
- Classification / regression: predicting a category / a number (Episode 1).
- Distance: a number saying how far apart two examples are, computed from their features (vectors, Episode 3).
- Overfitting / underfitting: memorising noise / missing the pattern (Episode 20).
- Cross-validation: scoring a model on several train/test splits and averaging (Episode 26).
- Hyperparameter: a setting we choose (here k), not learned by the model (Episode 8).
The problem: a pattern straight lines can't draw
A pizza shop has 2,000 made-up past orders: where each customer lives (km east, km north of the shop) and whether the pizza arrived within 30 minutes. Only customers in a rough circle around the shop get it on time.
import numpy as np
from sklearn.model_selection import train_test_split
rng = np.random.default_rng(27); n = 2000 # made-up pizza orders around one shop
X = rng.uniform(-6, 6, (n, 2)) # customer's location: km east, km north
dist = np.sqrt((X ** 2).sum(1))
y = (dist + rng.normal(0, 0.6, n) < 3.5).astype(int) # 1 = arrived within 30 minutes
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.25, random_state=0)
from sklearn.linear_model import LogisticRegression
from sklearn.neighbors import KNeighborsClassifier
print(f"on time: {y.mean():.1%} of orders")
lr = LogisticRegression().fit(X_tr, y_tr)
print(f"logistic regression accuracy {lr.score(X_te, y_te):.3f}")
print(f"always 'late' (baseline) {1 - y_te.mean():.3f}")
knn = KNeighborsClassifier(n_neighbors=15).fit(X_tr, y_tr)
print(f"kNN (k = 15) accuracy {knn.score(X_te, y_te):.3f}")
print("new order at (1, 1):", knn.predict([[1, 1]]), " at (5, 4):", knn.predict([[5, 4]]))
Output:
on time: 28.7% of orders
logistic regression accuracy 0.718
always 'late' (baseline) 0.718
kNN (k = 15) accuracy 0.928
new order at (1, 1): [1] at (5, 4): [0]
- Logistic regression scores exactly the baseline (0.718 = always say "late"). Its decision boundary is a straight line (Episode 22), and no straight line separates a circle from its surroundings, so it gives up and predicts "late" everywhere.
- kNN with k = 15 scores 0.928 and gets new orders right.

Green = predicted on time. Logistic regression (left) predicts late everywhere; kNN follows the round pattern. k = 1 is jagged, k = 15 smooth, k = 1001 predicts late everywhere again.
Plotting code:
# (first 7 lines: the same data set-up as above)
import matplotlib.pyplot as plt
from sklearn.neighbors import KNeighborsClassifier
from sklearn.linear_model import LogisticRegression
gx, gy = np.meshgrid(np.linspace(-6, 6, 300), np.linspace(-6, 6, 300)); G = np.c_[gx.ravel(), gy.ravel()]
fig, ax = plt.subplots(1, 4, figsize=(16, 4.6))
models = [("logistic regression", LogisticRegression()), ("kNN, k = 1", KNeighborsClassifier(1)),
("kNN, k = 15", KNeighborsClassifier(15)), ("kNN, k = 1001", KNeighborsClassifier(1001))]
for a, (name, m) in zip(ax, models):
m.fit(X_tr, y_tr); Z = m.predict(G).reshape(gx.shape)
a.contourf(gx, gy, Z, levels=[-.5, .5, 1.5], colors=["#f6c7b6", "#bfe3d0"], alpha=.8)
a.scatter(X_tr[:400, 0], X_tr[:400, 1], c=y_tr[:400], cmap="coolwarm_r", s=10)
a.plot(0, 0, "k*", ms=16); a.set_title(f"{name}: test acc {m.score(X_te, y_te):.3f}")
plt.tight_layout(); plt.savefig("regions.png", dpi=90)
The idea: ask the neighbours
Real-life example: you move into a new colony and want to know whether the water supply is good. You don't survey the city; you ask the 5 nearest houses. 4 say yes, 1 says no: you go with the majority. For a number like rent, you average their answers.
- k-nearest neighbours (kNN) classification: find the k stored examples closest to the new one; predict the most common label among them (majority vote).
- kNN regression: predict the average of the k neighbours' values.
- Instance-based learning: predictions come directly from stored examples (instances), not from learned weights.
- Lazy learning:
fitonly stores the data; all the work happens when a prediction is asked for. The opposite, eager learning (logistic regression), does the work duringfitand predicts quickly.
kNN from scratch in plain Python
import math
from collections import Counter
# 10 past pizza orders: (km east, km north) of the customer -> on time or late
orders = [((1, 1), "on time"), ((-2, 1), "on time"), ((0, -2), "on time"), ((2, -1), "on time"),
((-1, -1), "on time"), ((5, 4), "late"), ((-4, 3), "late"), ((3, -5), "late"),
((-5, -2), "late"), ((4, 1), "late")]
def euclidean(a, b):
return math.sqrt(sum((x - y) ** 2 for x, y in zip(a, b)))
def knn_predict(train, query, k):
dists = sorted((euclidean(x, query), label) for x, label in train) # 1. measure, 2. sort
nearest = dists[:k] # 3. keep k closest
print(" ", [(round(d, 2), lab) for d, lab in nearest])
return Counter(lab for _, lab in nearest).most_common(1)[0][0] # 4. majority vote
for q in [(0, 1), (4, 3), (2.5, 0)]:
print(q, "->", knn_predict(orders, q, k=3))
Output:
[(1.0, 'on time'), (2.0, 'on time'), (2.24, 'on time')]
(0, 1) -> on time
[(1.41, 'late'), (2.0, 'late'), (3.61, 'on time')]
(4, 3) -> late
[(1.12, 'on time'), (1.8, 'late'), (1.8, 'on time')]
(2.5, 0) -> on time
The whole algorithm in four steps:
- Measure the distance from the query to every stored example.
- Sort by distance.
- Keep the k closest.
- Vote (or average for regression).
Counter(...).most_common(1)returns the most frequent label.
Cost: every prediction measures n distances, so prediction time grows with the size of the stored data. That is the price of lazy learning (fixed at the end with trees).
Distance metrics
Real-life example: the shop is 3 km east and 4 km north. A crow flies straight: 5 km (Euclidean). An auto-rickshaw follows grid streets: 3 + 4 = 7 km (Manhattan).
| Metric | Formula | Example (3, 4) |
|---|---|---|
| Euclidean (L2) | √Σ(xᵢ − yᵢ)² | 5.0 |
| Manhattan (L1, city-block) | Σ|xᵢ − yᵢ| | 7.0 |
| Minkowski (order p) | (Σ|xᵢ − yᵢ|ᵖ)^(1/p) | p=1 → 7, p=2 → 5, p=3 → 4.498 |
| Chebyshev (p → ∞) | max |xᵢ − yᵢ| | 4 |
def minkowski(a, b, p):
return sum(abs(x - y) ** p for x, y in zip(a, b)) ** (1 / p)
home, shop = (0, 0), (3, 4) # 3 km east, 4 km north
print("Manhattan (p=1):", minkowski(home, shop, 1)) # like an auto on grid streets
print("Euclidean (p=2):", minkowski(home, shop, 2)) # as the crow flies
print("Minkowski p=3: ", round(minkowski(home, shop, 3), 3))
print("p = 50 (max): ", round(minkowski(home, shop, 50), 3))
Output:
Manhattan (p=1): 7.0
Euclidean (p=2): 5.0
Minkowski p=3: 4.498
p = 50 (max): 4.0
- Bigger p → the single largest difference dominates; at very large p only the maximum survives.
- In scikit-learn:
KNeighborsClassifier(metric="minkowski", p=2)is the default (Euclidean);p=1ormetric="manhattan"gives Manhattan. - Manhattan is often a little more robust when there are many features or outliers; try both with cross-validation.
Choosing k, and distance weighting
Real-life example: ask 1 neighbour and you might hit the one house with a broken pipe; ask 15 for a sensible local opinion; ask 1,000 and you're asking half the town, which isn't local any more.
# (first 7 lines: the same pizza data as above)
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import cross_val_score
for k in [1, 5, 15, 51, 201, 1001]:
m = KNeighborsClassifier(n_neighbors=k).fit(X_tr, y_tr)
cv = cross_val_score(KNeighborsClassifier(n_neighbors=k), X_tr, y_tr, cv=5).mean()
print(f"k = {k:<5} train {m.score(X_tr, y_tr):.3f} 5-fold CV {cv:.3f}")
w = cross_val_score(KNeighborsClassifier(n_neighbors=1001, weights="distance"), X_tr, y_tr, cv=5).mean()
print(f"k = 1001, weights='distance': 5-fold CV {w:.3f}")
Output:
k = 1 train 1.000 5-fold CV 0.882
k = 5 train 0.934 5-fold CV 0.912
k = 15 train 0.927 5-fold CV 0.916
k = 51 train 0.927 5-fold CV 0.922
k = 201 train 0.921 5-fold CV 0.915
k = 1001 train 0.711 5-fold CV 0.711
k = 1001, weights='distance': 5-fold CV 0.863
- k = 1: training accuracy 1.000 (each training point's nearest neighbour is itself) but CV 0.882: it memorises noise. Overfitting, high variance (jagged regions in the figure).
- k = 1001: half the training data votes, and the majority is always "late": 0.711 = baseline. Underfitting, high bias. This is the bias-variance trade-off of Episode 20.
- Best here: k = 51 (CV 0.922). Choose k with cross-validation, never by test accuracy. For two classes an odd k avoids tie votes.
- Distance-weighted kNN (
weights="distance"): each neighbour votes with weight 1 / distance, so close neighbours count more. It rescued the far-too-large k = 1001 (0.711 → 0.863). With a good k it changes little.
kNN regression
# (first 7 lines: the same pizza data as above)
from sklearn.neighbors import KNeighborsRegressor
from sklearn.metrics import mean_absolute_error
minutes = 12 + 6 * dist + rng.normal(0, 3, n) # delivery time in minutes
m_tr, m_te = minutes[:1500], minutes[1500:]
for metric in ["euclidean", "manhattan"]:
reg = KNeighborsRegressor(n_neighbors=15, metric=metric).fit(X[:1500], m_tr)
print(f"{metric:<9} MAE {mean_absolute_error(m_te, reg.predict(X[1500:])):.2f} minutes")
reg = KNeighborsRegressor(n_neighbors=15).fit(X[:1500], m_tr)
d, i = reg.kneighbors([[1, 1]])
p = reg.predict([[1, 1]]).round(1)
print("(1, 1): neighbours took", m_tr[i[0][:5]].round(0), "->", p, "min")
Output:
euclidean MAE 2.46 minutes
manhattan MAE 2.48 minutes
(1, 1): neighbours took [23. 27. 22. 24. 15.] -> [21.2] min
KNeighborsRegressorpredicts the mean of the k neighbours' targets (withweights="distance", a weighted mean).kneighbors(X)returns the distances and the row indices of the neighbours: handy for explaining a prediction ("these 15 orders took about 21 minutes").- MAE (mean absolute error, Episode 19): average size of the error, here about 2.5 minutes.
Why kNN needs feature scaling
The problem: add a useless feature, the bill amount in rupees (200 to 2,000).
# (first 7 lines: the same pizza data as above)
from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import make_pipeline
bill = rng.uniform(200, 2000, n) # order value in rupees: unrelated to lateness
X2 = np.c_[X, bill]; A_tr, A_te = X2[:1500], X2[1500:]; b_tr, b_te = y[:1500], y[1500:]
print("first order:", X2[0].round(1), " <- km, km, rupees")
raw = KNeighborsClassifier(n_neighbors=15).fit(A_tr, b_tr)
print(f"kNN, raw features accuracy {raw.score(A_te, b_te):.3f}")
pipe = make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=15)).fit(A_tr, b_tr)
print(f"kNN, scaled features accuracy {pipe.score(A_te, b_te):.3f}")
Output:
first order: [ 2.4 -2.2 777.3] <- km, km, rupees
kNN, raw features accuracy 0.698
kNN, scaled features accuracy 0.902
- distance² = Δeast² + Δnorth² + Δbill². A bill difference of 500 contributes 250,000; a location difference of 2 km contributes 4. The units decide who is "nearest": neighbours become orders with similar bills, and accuracy (0.698) falls below the baseline.
- Standardisation (Episode 16) gives every feature mean 0 and standard deviation 1, so each gets a fair say: 0.902, the same as using location alone on these orders (Practice 4).
- Put the scaler inside a pipeline (Episode 17) so it is fitted on training folds only.
- Scaling matters when features have different units. When all features share a unit (pixel brightness in the mini project), scaling may not help, and can even hurt slightly.
- kNN weighs every feature equally, useful or not, so also drop features that don't matter.
The curse of dimensionality
Real-life example: finding a friend on one street is easy; in a whole city (two directions) the same people are more spread out; in a hundred directions, everyone is far from everyone, and "nearest" stops meaning anything. Each feature is one dimension.
# (first 7 lines: the same pizza data as above)
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import cross_val_score
for d in [2, 10, 100, 1000]: # random points in d dimensions
pts = rng.uniform(0, 1, (1000, d)); q = rng.uniform(0, 1, d)
dd = np.sqrt(((pts - q) ** 2).sum(1)); r = dd.max() / dd.min()
print(f"{d:>4} features: nearest {dd.min():5.2f} farthest {dd.max():5.2f} ratio {r:6.2f}")
for extra in [0, 5, 20, 100]: # add useless random features to the orders
Xn = np.c_[X_tr, rng.uniform(-6, 6, (len(X_tr), extra))]
s = cross_val_score(KNeighborsClassifier(n_neighbors=15), Xn, y_tr, cv=5).mean()
print(f"2 real + {extra:>3} noise features: CV accuracy {s:.3f}")
Output:
2 features: nearest 0.01 farthest 1.19 ratio 139.64
10 features: nearest 0.67 farthest 2.11 ratio 3.14
100 features: nearest 3.25 farthest 4.65 ratio 1.43
1000 features: nearest 12.11 farthest 13.54 ratio 1.12
2 real + 0 noise features: CV accuracy 0.916
2 real + 5 noise features: CV accuracy 0.854
2 real + 20 noise features: CV accuracy 0.715
2 real + 100 noise features: CV accuracy 0.671
- In 2 dimensions the farthest point is ~140 times farther than the nearest; in 1,000 dimensions only 1.12 times. Distances concentrate: nearest and farthest look alike.
- To keep points close you need exponentially more data per added feature.
- Every useless feature adds random noise to every distance: 100 noise features drop accuracy from 0.916 to 0.671, below the baseline.
- Fixes: feature selection, domain knowledge, or dimensionality reduction (squeezing many features into a few, e.g. PCA, later in the course).
- kNN works best with few, meaningful, scaled features and plenty of rows.
Faster search: KD-tree and ball tree
Real-life example: to find a book you could check every shelf (brute force), or use the library's organisation (floor → section → shelf) and skip whole floors.
- Brute force (
algorithm="brute"): compute the distance to every stored row. Simple; fast with vectorised NumPy for moderate sizes. - KD-tree (
"kd_tree", k-dimensional tree): recursively splits the data on one feature at a time into boxes; a search skips boxes that are too far away. Excellent with few features. - Ball tree (
"ball_tree"): groups points into nested balls (centre + radius) and skips balls that are too far. Copes somewhat better than a KD-tree as features grow, and with non-Euclidean metrics. algorithm="auto"(default) chooses based on the data. All three return exactly the same neighbours; only speed differs.
This takes over a minute, so it was run once in the course container (times vary by machine):
import numpy as np, time
from sklearn.neighbors import KNeighborsClassifier as KNN
rng = np.random.default_rng(0)
for d in [2, 50]:
X = rng.normal(0, 1, (200000, d)); y = X[:, 0] > 0
Q = rng.normal(0, 1, (2000, d))
for algo in ["brute", "kd_tree", "ball_tree"]:
m = KNN(n_neighbors=5, algorithm=algo).fit(X, y)
t = time.time(); m.predict(Q); s = time.time() - t
print(f"{d:>2} features {algo:<9} {s:5.2f} s")
Output (one run):
2 features brute 0.47 s
2 features kd_tree 0.01 s
2 features ball_tree 0.04 s
50 features brute 0.87 s
50 features kd_tree 51.91 s
50 features ball_tree 27.75 s
- 2 features: the KD-tree answers 2,000 queries about 50 times faster than brute force.
- 50 features: the trees are far slower than brute force (the KD-tree about 60 times slower): the curse of dimensionality again (no box or ball can be skipped when everything is roughly equally far).
- Time
fittoo and you'll see it is almost instant for brute force (it only stores the data) whilepredictdoes the work: lazy learning in numbers.
kNN at a glance
| Strengths | Weaknesses |
|---|---|
| No training; easy to explain ("these 15 similar orders") | Slow predictions on big data (without trees) |
| Any boundary shape; multiclass for free | Needs scaling; sensitive to useless features |
| Classification and regression with one idea | Breaks down with many features |
| New data: just add rows | Stores the whole training set in memory |
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| Linear model on a round pattern | accuracy 0.718 = always "late" | A straight boundary can't bend | kNN (or engineered features) |
| k = 1 | train 1.000, CV 0.882 | Memorises noise | Choose k by cross-validation |
| Huge k | k = 1001: 0.711 = baseline | The majority of the whole dataset wins | Smaller k, or weights="distance" |
| Unscaled features | 0.698 with the bill in rupees | Units decide the neighbours | make_pipeline(StandardScaler(), KNeighborsClassifier()) |
| Many useless features | 0.671 with 100 noise features | Curse of dimensionality | Select or reduce features |
| More neighbours than rows | ValueError: Expected n_neighbors <= n_samples_fit, but n_neighbors = 5, n_samples_fit = 3, n_samples = 1 |
k larger than the stored data | k ≤ number of training rows |
| Choosing k on the test set | Optimistic test score | Test set used for a decision | CV on the training data |
| Even k with two classes | Arbitrary tie-breaking | 2 votes vs 2 votes | Odd k, or distance weights |
Mini project: handwritten digits
scikit-learn ships 1,797 handwritten digits, each an 8×8 image = 64 pixel features. Tune k, weights and p with a grid search, and compare with and without scaling.
from sklearn.datasets import load_digits
from sklearn.model_selection import train_test_split, GridSearchCV
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
X, y = load_digits(return_X_y=True) # 1,797 handwritten digits, 8x8 pixels = 64 features
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.25, stratify=y, random_state=0)
pipe = make_pipeline(StandardScaler(), KNeighborsClassifier())
grid = {"kneighborsclassifier__n_neighbors": [1, 3, 5, 7, 9, 15],
"kneighborsclassifier__weights": ["uniform", "distance"],
"kneighborsclassifier__p": [1, 2]}
search = GridSearchCV(pipe, grid, cv=5).fit(X_tr, y_tr)
print("best:", search.best_params_)
print(f"CV {search.best_score_:.3f} test {search.score(X_te, y_te):.3f}")
raw = GridSearchCV(KNeighborsClassifier(), {"n_neighbors": [1, 3, 5, 7, 9, 15]}, cv=5).fit(X_tr, y_tr)
print(f"without scaling: best k {raw.best_params_['n_neighbors']}, test {raw.score(X_te, y_te):.3f}")
Output:
best: {'kneighborsclassifier__n_neighbors': 1, 'kneighborsclassifier__p': 1, 'kneighborsclassifier__weights': 'uniform'}
CV 0.976 test 0.973
without scaling: best k 1, test 0.982
- About 97–98% on handwritten digits with a 15-line model.
- Here scaling slightly hurt (0.973 vs 0.982): all 64 features are pixel brightness on the same 0–16 scale, and standardising blows up the noise in edge pixels that are almost always blank. Scale when units differ; check with cross-validation.
- k = 1 wins here because digits of the same class really do look alike and the labels are clean.
Practice
- Add distance weighting to the from-scratch
knn_predict(vote = 1 / distance). - Use Manhattan distance in the from-scratch kNN. Do the three predictions change?
- Plot (or print) the 5-fold CV accuracy for every k from 1 to 100 on the pizza data. Which k is best, and what's its test accuracy?
- In the scaling example, drop the bill feature instead of scaling. What accuracy do you get?
Solution 1
import math
from collections import defaultdict
orders = [((1, 1), "on time"), ((-2, 1), "on time"), ((0, -2), "on time"), ((2, -1), "on time"),
((-1, -1), "on time"), ((5, 4), "late"), ((-4, 3), "late"), ((3, -5), "late"),
((-5, -2), "late"), ((4, 1), "late")]
def euclidean(a, b):
return math.sqrt(sum((x - y) ** 2 for x, y in zip(a, b)))
def knn_weighted(train, query, k):
nearest = sorted((euclidean(x, query), label) for x, label in train)[:k]
votes = defaultdict(float)
for d, label in nearest:
votes[label] += 1 / (d + 1e-9) # closer = bigger vote; 1e-9 avoids dividing by 0
print(" votes:", {lab: round(v, 2) for lab, v in votes.items()})
return max(votes, key=votes.get)
for q in [(0, 1), (4, 3), (2.5, 0)]:
print(q, "->", knn_weighted(orders, q, k=3))
Output:
votes: {'on time': 1.95}
(0, 1) -> on time
votes: {'late': 1.21, 'on time': 0.28}
(4, 3) -> late
votes: {'on time': 1.45, 'late': 0.55}
(2.5, 0) -> on time
Same predictions, but now we see how confident each one is.
Solution 2
import math
from collections import Counter
orders = [((1, 1), "on time"), ((-2, 1), "on time"), ((0, -2), "on time"), ((2, -1), "on time"),
((-1, -1), "on time"), ((5, 4), "late"), ((-4, 3), "late"), ((3, -5), "late"),
((-5, -2), "late"), ((4, 1), "late")]
def manhattan(a, b):
return sum(abs(x - y) for x, y in zip(a, b))
def knn_predict(train, query, k, dist):
nearest = sorted((dist(x, query), label) for x, label in train)[:k]
print(" nearest:", nearest)
return Counter(lab for _, lab in nearest).most_common(1)[0][0]
for q in [(0, 1), (4, 3), (2.5, 0)]:
print(q, "->", knn_predict(orders, q, 3, manhattan))
Output:
nearest: [(1, 'on time'), (2, 'on time'), (3, 'on time')]
(0, 1) -> on time
nearest: [(2, 'late'), (2, 'late'), (5, 'on time')]
(4, 3) -> late
nearest: [(1.5, 'on time'), (2.5, 'late'), (2.5, 'on time')]
(2.5, 0) -> on time
The distances change (and the third neighbour of (0, 1) is a different order), but the predictions stay the same here.
Solution 3
# (first 7 lines: the same pizza data as above)
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import cross_val_score
ks = range(1, 101)
cv = [cross_val_score(KNeighborsClassifier(n_neighbors=k), X_tr, y_tr, cv=5).mean() for k in ks]
best = ks[int(np.argmax(cv))]
print(f"best k {best}, CV {max(cv):.3f}; k=1: {cv[0]:.3f} k=100: {cv[-1]:.3f}")
m = KNeighborsClassifier(n_neighbors=best).fit(X_tr, y_tr)
print(f"test accuracy with k={best}: {m.score(X_te, y_te):.3f}")
Output:
best k 36, CV 0.925; k=1: 0.882 k=100: 0.921
test accuracy with k=36: 0.934
The CV curve is flat between about k = 15 and k = 100; any k in that range is fine. (Plot with plt.plot(ks, cv).)
Solution 4
# (first 7 lines: the same pizza data as above)
from sklearn.neighbors import KNeighborsClassifier
bill = rng.uniform(200, 2000, n)
X2 = np.c_[X, bill]; b_tr, b_te = y[:1500], y[1500:]
m = KNeighborsClassifier(n_neighbors=15).fit(X2[:1500, :2], b_tr) # location only, bill dropped
print(f"bill dropped: accuracy {m.score(X2[1500:, :2], b_te):.3f}")
Output:
bill dropped: accuracy 0.902
The same as the scaled version: after scaling, the useless bill hardly disturbed the neighbours here. Dropping it is still simpler and safer.
Quick quiz
k = 3, the 3 nearest orders:
1.0 km away -> late
1.5 km away -> on time
2.0 km away -> late
majority vote = ?
A) late B) on time C) a tie D) error
Answer
A) late, two votes to one. With weights="distance": late gets 1/1.0 + 1/2.0 = 1.5, on time 1/1.5 ≈ 0.67, still late.
Interview questions
- How does kNN make a prediction? Compute distances to all training points, take the k nearest, return the majority class (or the mean value for regression).
- Why is kNN called lazy? It does no work at training time beyond storing data; all computation happens at prediction time.
- How do you choose k? Cross-validation; small k overfits (high variance), large k underfits (high bias); odd k avoids ties in binary problems.
- Why must features be scaled for kNN? Distances add up raw differences, so features with large units dominate; standardise inside a pipeline.
- Euclidean vs Manhattan distance? Straight-line √Σd² vs sum of absolute differences Σ|d|; both are Minkowski distances with p = 2 and p = 1.
- What is the curse of dimensionality? In many dimensions distances concentrate (nearest ≈ farthest) and data becomes sparse, so neighbours stop being meaningfully near.
- What do KD-trees and ball trees do? Index the data so a neighbour search can skip far-away regions; fast in low dimensions, little help in high dimensions.
- Time and memory complexity of brute-force kNN? Training O(1) besides storing O(n·d); each prediction O(n·d) distance computations.
- What does distance weighting change? Closer neighbours get larger votes (1/distance), reducing the influence of far neighbours when k is large.
- When would you not use kNN? Very large datasets needing fast predictions, many (noisy) features, or when a compact model is required.
Glossary
| Term | Meaning | Example |
|---|---|---|
| k-nearest neighbours (kNN) | Predict from the k most similar stored examples | k = 15: 0.928 |
| Neighbour | A stored example close to the query | (1, 1), 1.0 km away |
| Query point | The new example we predict for | order at (1, 1) |
| Majority vote | Most common label among the neighbours | 2 late vs 1 on time → late |
| kNN regression | Average of the neighbours' values | 21.2 minutes |
| Instance-based learning | Predicting directly from stored examples | kNN |
| Lazy learning | No work at fit time; all work at prediction time | fit stores, predict searches |
| Eager learning | Work done during training, fast prediction | logistic regression |
| Decision boundary | Where the predicted class changes | a straight line vs a round blob |
| Distance metric | Rule for measuring how far apart two examples are | Euclidean, Manhattan |
| Euclidean distance (L2) | √Σ(xᵢ − yᵢ)²: as the crow flies | (3, 4) → 5 |
| Manhattan distance (L1) | Σ|xᵢ − yᵢ|: along grid streets | (3, 4) → 7 |
| Minkowski distance | (Σ|xᵢ − yᵢ|ᵖ)^(1/p); p = 1 Manhattan, p = 2 Euclidean | p = 3 → 4.498 |
| Chebyshev distance | max|xᵢ − yᵢ| (Minkowski with p → ∞) | (3, 4) → 4 |
k (n_neighbors) |
Number of neighbours consulted; a hyperparameter | best ≈ 36–51 here |
| Distance-weighted kNN | Votes weighted by 1 / distance (weights="distance") |
k = 1001: 0.711 → 0.863 |
| Feature scaling / standardisation | Putting features on comparable scales (mean 0, std 1) | 0.698 → 0.902 |
| Curse of dimensionality | With many features, distances concentrate and data is sparse | ratio 139.64 → 1.12 |
| Dimension | One feature / one direction in feature space | 2 vs 1,000 |
| Dimensionality reduction | Squeezing many features into a few (later episode) | PCA |
| Brute force search | Compute the distance to every stored row | algorithm="brute" |
| KD-tree | Tree of axis-aligned boxes for fast neighbour search | 2 features: 0.01 s |
| Ball tree | Tree of nested balls for fast neighbour search | algorithm="ball_tree" |
kneighbors |
Returns neighbour distances and indices | explain a prediction |
Summary
- A straight line can't draw a circle: logistic regression scored the 0.718 baseline; kNN scored 0.928.
- kNN = measure, sort, keep k, vote (or average). It is lazy and instance-based: fit only stores the data.
- Distance metrics: Euclidean (5), Manhattan (7), Minkowski with a dial p.
- k controls the bias-variance trade-off (k = 1 overfits, k = 1001 underfits); choose it by cross-validation; distance weighting helps when k is large.
- Scale features with different units (0.698 → 0.902), and keep features few and meaningful: 100 noise features dropped accuracy to 0.671 (curse of dimensionality).
- KD-trees and ball trees speed up the search in low dimensions (about 50× faster with 2 features) but not in high ones.
Next episode: Naive Bayes: generative vs discriminative models, Gaussian, multinomial and Bernoulli naive Bayes, Laplace smoothing, bag-of-words and text classification.