SyntaxPilot
Courses/Machine Learning/Lesson 27

Machine Learning · Lesson 27 of 90 · 14 min

k-nearest neighbours

instance-based learninglazy learningkNN classification and regressiondistance metrics (Euclidean, Manhattan, Minkowski)choosing kdistance-weighted kNNneed for scalingcurse of dimensionalityKD-treeball tree

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.

Decision regions

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: fit only stores the data; all the work happens when a prediction is asked for. The opposite, eager learning (logistic regression), does the work during fit and 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:

  1. Measure the distance from the query to every stored example.
  2. Sort by distance.
  3. Keep the k closest.
  4. 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=1 or metric="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
  • KNeighborsRegressor predicts the mean of the k neighbours' targets (with weights="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 fit too and you'll see it is almost instant for brute force (it only stores the data) while predict does 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

  1. Add distance weighting to the from-scratch knn_predict (vote = 1 / distance).
  2. Use Manhattan distance in the from-scratch kNN. Do the three predictions change?
  3. 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?
  4. 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

  1. 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).
  2. Why is kNN called lazy? It does no work at training time beyond storing data; all computation happens at prediction time.
  3. How do you choose k? Cross-validation; small k overfits (high variance), large k underfits (high bias); odd k avoids ties in binary problems.
  4. Why must features be scaled for kNN? Distances add up raw differences, so features with large units dominate; standardise inside a pipeline.
  5. Euclidean vs Manhattan distance? Straight-line √Σd² vs sum of absolute differences Σ|d|; both are Minkowski distances with p = 2 and p = 1.
  6. What is the curse of dimensionality? In many dimensions distances concentrate (nearest ≈ farthest) and data becomes sparse, so neighbours stop being meaningfully near.
  7. 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.
  8. Time and memory complexity of brute-force kNN? Training O(1) besides storing O(n·d); each prediction O(n·d) distance computations.
  9. What does distance weighting change? Closer neighbours get larger votes (1/distance), reducing the influence of far neighbours when k is large.
  10. 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.