Part III — Classification

Chapter 12 · K-Nearest Neighbors (K-NN)

The simplest classifier in the book: no equation, no training, no parameters to fit — just "tell me who your neighbors are and I'll tell you who you are." Behind that simplicity sits everything this course cares about: distance computed by hand, scaling's life-or-death role proven with real numbers, k as a bias-variance dial, and the curse that haunts every distance-based method.

📖 Chapter 12 of 33 ⏱ ~80 min read Mostly Core Stable 📝 Quiz · 30 MCQs

🎯 Learning Objectives

Explain lazy (instance-based) learning and how it differs from every parametric model met so far
Compute Euclidean and Manhattan distances by hand, and read Minkowski's p parameter
Demonstrate — with real distances and a real accuracy drop — why unscaled features destroy K-NN
Choose k defensibly: the vote, odd values, and the real k-sweep with its memoriser at k = 1
State the curse of dimensionality and its practical consequences
Compare K-NN's local boundary against Chapter 11's straight line, with both confusion matrices real

1. Lazy Learning: No Model, Just Memory

Every model so far has been eager and parametric: training compresses the data into a small set of numbers — OLS coefficients, an SVR's support vectors, a tree's splits — after which the data itself can be discarded. K-NN refuses the compression. Training is literally storing the dataset; prediction asks: which stored rows are closest to the newcomer, and what do they say?

prediction(x′) = majority vote of the k nearest training rows' labels

That is the entire algorithm. The "model" is the training set; the maths is distance; the decision is a show of hands. This is instance-based (lazy) learning — work deferred from training time to prediction time.

The personality shift is worth feeling. Logistic regression (Chapter 11) generalises before you arrive: its boundary is fixed, the data forgotten. K-NN keeps every anecdote and consults the relevant ones per customer — flexible, local, and entirely dependent on the neighbourhood being meaningful. Same dataset as Chapter 11 (400 users, age + salary → purchased), so every comparison to come is apples-to-apples.

📝

Note: "No parameters to fit" does not mean "no knobs". The neighbourhood size k, the distance metric and the scaling decision are all modelling choices — hyperparameters in Chapter 31's vocabulary. K-NN's laziness relocates the decisions; it never removes them.

2. Distance: The Only Geometry

If neighbourhoods decide everything, "near" must be defined. The default is straight-line — Euclidean — distance:

d(a, b) = √[ (a₁−b₁)² + (a₂−b₂)² ]

Manhattan replaces squares and root with absolute sums: |a₁−b₁| + |a₂−b₂| — city-block distance. Both are special cases of Minkowski with parameter p (p = 2 → Euclidean, p = 1 → Manhattan) — the source code's metric='minkowski', p=2 is Euclidean wearing its formal name.

2.1 By hand — three real customers

Take A = (35, ₹20k), B = (35, ₹40k), C = (45, ₹20k) — real coordinate ranges from the dataset:

d(A, B) — same age, salary +20k: √(0² + 20,000²) = 20,000
d(A, C) — age +10 years, same salary: √(10² + 0²) = 10

Pause on those two numbers, because they contain this chapter's entire drama: in raw units, B (a ₹20k wealthier peer) is 2,000 times farther from A than C (a decade older peer). To raw Euclidean distance, age is noise and salary is everything — regardless of what actually drives purchases. Section 3 repairs this; Section 2.2 first finishes the toolkit.

💡

Pro Tip — choosing a metric: Euclidean for smooth, isotropic features; Manhattan when features are many or outliers abound (absolute values dampen the squaring's tantrums); and for categorical features, Hamming (mismatch counts). Minkowski's p is the dial that interpolates — rarely tuned, occasionally decisive.

3. Why Scaling Is Non-Negotiable

Chapter 3's table promised that distance-based models must be scaled; Chapter 7's SVR showed kernels suffering; K-NN is the purest demonstration, because distance is all it has. Standardise both features (age SD ≈ 10.5 years, salary SD ≈ ₹34,054 on this data) and recompute Section 2's distances:

Pair	Difference	Raw distance	Scaled distance	Verdict
A ↔ B	salary +₹20k (≈ 0.59 SD)	20,000	0.59	Wealth gap, modest
A ↔ C	age +10 yrs (≈ 0.96 SD)	10	0.96	Age gap — actually the bigger difference

The verdict flips. Raw units ranked B as 2,000× farther; standardised units rank C (the older peer) as farther. Which is right? Chapter 11 already answered: age moves purchase odds 7.98× per SD versus salary's 3.03× — age is the stronger driver, and only the scaled geometry lets it speak. Now the accuracy price of ignoring this (real, same split, same k = 5):

Pipeline	Test accuracy	Confusion matrix
Standardised (source)	0.93	[[64, 4], [3, 29]]
Raw units	0.83	ten customers misclassified

Ten points of accuracy — an entire marketing segment — lost to unit choice. No error is raised, nothing looks broken; the model simply becomes a salary-only classifier with age as a rounding error. Silent failure is the expensive kind.

⚠

Warning: Imputation matters here too — a NaN in any feature poisons every distance to that row (Chapter 3's ritual precedes every algorithm, lazy ones included). And remember the fit/transform discipline: the scaler learns SDs from the training rows only.

4. The Vote & Choosing k

Figure 12.1 — The vote: the newcomer's five nearest stored customers, three of them buyers.

k controls how many neighbours get a vote — and it is this chapter's bias-variance dial, in Chapter 6's exact sense:

k = 1: each point is classified by its single closest neighbour — zero training errors by construction, every noise point becomes a law unto itself. Low bias, high variance: the memoriser.
k = n (all rows): every prediction is the global majority class ("no", for our 64/36 data). High bias, zero variance: the flatliner.
Sensible k: enough votes to average out noise, few enough to stay local.

The real sweep, same split and scaling (test accuracy alongside training accuracy):

k	1	3	5	7	9	11	15	21	31	41	51
Test acc	0.87	0.93	0.93	0.93	0.93	0.93	0.93	0.93	0.93	0.93	0.92
Train acc	1.000	0.913	0.910	0.907	0.910	0.917	0.910	0.900	0.897	0.893	0.890

Two real signatures in that table. First, k = 1: training accuracy 1.000 against test 0.87 — the memorisation gap of Chapters 8–9, here in its purest form (each point is its own nearest neighbour). Second, the remarkable plateau: test accuracy sits at 0.93 from k = 3 all the way to k = 41 before sagging. This dataset's neighbourhoods are genuinely clean, so the choice of k is robust — a luxury; on noisier data the curve wobbles and the choice matters.

💡

Pro Tip — three habits for k: (1) prefer odd k in binary problems — an even vote can tie. (2) Choose from the middle of a stable plateau, not its edge. (3) The honest selector is cross-validation (Chapter 31) — our sweep consulted the test set, so treat 0.93 as indicative; the plateau's existence, not its exact height, is the finding.

One more subtlety the real run exposed: K-NN's predict_proba returns the vote share — for customer (30, ₹87k), [1.0, 0.0]: all five neighbours were non-buyers, a unanimous verdict. Contrast Chapter 11's calibrated [0.887, 0.113]. K-NN "probabilities" come in steps of 1/k (0, 0.2, 0.4, …, 1.0 here) — coarse confidence, not calibrated chance. When the business needs real probabilities, this matters.

📋 Stable content — Reviewed: August 2026

5. Implementation in Python

import numpy as np
import pandas as pd

dataset = pd.read_csv('Social_Network_Ads.csv')
X = dataset.iloc[:, :-1].values
y = dataset.iloc[:, -1].values

from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.25, random_state=0)

from sklearn.preprocessing import StandardScaler
sc = StandardScaler()
X_train = sc.fit_transform(X_train)
X_test = sc.transform(X_test)

from sklearn.neighbors import KNeighborsClassifier
classifier = KNeighborsClassifier(n_neighbors=5, metric='minkowski', p=2)
classifier.fit(X_train, y_train)          # "training" = storing

print(classifier.predict(sc.transform([[30, 87000]])))        # [0]
print(classifier.predict_proba(sc.transform([[30, 87000]])))  # [[1. 0.]] unanimous

from sklearn.metrics import confusion_matrix, accuracy_score
y_pred = classifier.predict(X_test)
cm = confusion_matrix(y_test, y_pred)
print(cm)                                # [[64  4]
                                         #  [ 3 29]]
print(accuracy_score(y_test, y_pred))    # 0.93

Listing 12.1 — The complete K-NN pipeline (source: k_nearest_neighbors.py).

# The k-sweep of Section 4 — and the honest note
for k in [1, 3, 5, 11, 21, 51]:
    m = KNeighborsClassifier(n_neighbors=k).fit(X_train, y_train)
    print(f'k={k:2d}  train={m.score(X_train, y_train):.3f}  '
          f'test={m.score(X_test, y_test):.3f}')

# The unscaled failure, one line
raw = KNeighborsClassifier(n_neighbors=5).fit(
    X_train_original, y_train)            # raw units!
print(raw.score(X_test_original, y_test)) # 0.83

Listing 12.2 — Reproduce both dramas: the k-sweep and the scaling collapse.

💡

Pro Tip: n_neighbors=5 (sklearn's default) with metric='minkowski', p=2 (Euclidean) is the canonical start. When neighbours disagree loudly, try weights='distance' — closer neighbours vote harder — a gentler alternative to shrinking k.

6. The Curse of Dimensionality

K-NN's promise — "nearest neighbours carry the answer" — quietly assumes those neighbours are genuinely near. In a handful of dimensions they are. As features multiply, space inflates so fast that nearness itself dissolves: the curse of dimensionality.

The arithmetic of emptiness: a d-dimensional unit cube contains the fraction of volume within distance 0.1 of its edges that grows explosively with d — equivalently, the volume near the boundary approaches 100%. Every point becomes an edge case. Concretely: in 2 dimensions, a small circle around a customer captures a healthy crowd; in 100 dimensions, a sphere of the same relative radius is almost empty — you must reach enormously far before finding any neighbours at all, and "nearest" starts describing noise rather than kinship.

Dimensions	Neighbourhood behaviour	K-NN consequence
2–3 (this chapter)	Dense, meaningful nearness	Excellent — 93% here
~10	Distances begin to equalise	Needs careful scaling, feature choice
50+	Nearly all points equidistant; nearest ≈ average	Vote degenerates toward the majority class

Two responses dominate practice. Feature selection: fewer, better features (Chapter 5's tools). Dimensionality reduction: compress features while keeping their structure — Part IX's PCA and LDA, built for exactly this. The curse is also why "just add more columns" is never free: in distance-land, every added dimension dilutes every neighbourhood.

🌎

Real World: Recommendation systems feel the curse daily — "users similar to you" over thousands of product dimensions is why naive K-NN recommenders lose to matrix factorisation and embedding models. The fix is always the same idea: learn a compact space where nearness is meaningful again — the embedding philosophy Chapters 25–27 develop.

7. Reading the Results: K-NN vs Logistic

Same data, same split, same scaling — two philosophies, both real:

	Logistic (Ch 11)	K-NN, k=5 (this chapter)
Confusion matrix	[[65, 3], [8, 24]]	[[64, 4], [3, 29]]
Accuracy	0.89	0.93
Errors	11 (8 missed buyers)	7 (only 3 missed buyers)
Boundary	One straight line	Local, wiggly, adapts to clusters
Probabilities	Calibrated (0.113, 0.491…)	Vote shares (steps of 1/5)
Explanation	Odds ratios per feature	"Your 5 neighbours: 3 bought"
Prediction cost	One matrix multiply	Search all 300 rows

Why did K-NN win? Because the true purchase region is not linearly separable — young-high-salary and old-low-salary customers complicate any single straight line (recall Chapter 11's boundary-sitter at (30, ₹150k)). A local vote handles that curvature for free; logistic pays for its interpretability with a stiffer boundary. And note what the errors became: K-NN misses only 3 buyers versus logistic's 8 — the confusion matrix, not the accuracy, is where a marketing team should look (Chapter 18 formalises this).

But read the last two rows before declaring a winner: logistic answers "why" with odds ratios and predicts in microseconds; K-NN offers anecdote-level explanations and pays a per-prediction search cost that grows with the training set. A tie in accuracy, broken by completely different currencies.

8. Strengths, Limits & the Road Ahead

Strengths	Limitations
Zero training cost; trivially simple to explain	Scaling mandatory — 10 accuracy points lost here when skipped
Naturally nonlinear; no boundary assumptions	Prediction cost grows with training size (lazy ≠ free)
Robust when data is dense and low-dimensional	Curse of dimensionality: neighbourhoods dissolve as features grow
Intuitive explanations ("your neighbours")	Coarse vote-share probabilities; sensitive to imbalanced classes (majority drowns the vote)

K-NN is the great baseline: when a local-vote memory beats your sophisticated model, your model has a problem. The chapters ahead march toward trained boundaries of increasing sophistication — and Chapter 13 returns to geometry with intent: the Support Vector Machine, which learns not just a boundary but the widest street between classes, decided — as in Chapter 7's SVR — by a handful of support vectors.

🛠 Hands-On: Dial the NeighbourhoodBeginner

A colleague shipped K-NN without scaling and is defending 83% as "fine". Reproduce both pipelines, map the k-sweep, and write the two-paragraph verdict: why scaling was the difference, and which k you would deploy.

Steps

Fit scaled k=5; verify [[64, 4], [3, 29]] and 0.93.
Fit unscaled k=5 (same split). Quantify the drop and explain the mechanism in one sentence, using the raw distances 20,000 vs 10.
Hand-compute the scaled distances for A(35, 20k), B(35, 40k), C(45, 20k) using SDs ≈ 10.5 years / ₹34,054; confirm the verdict flip.
Run the k-sweep {1, 3, …, 51} with train and test accuracy; identify the memoriser row and the plateau.
For customer (30, ₹150k) — Chapter 11's boundary-sitter — what does K-NN predict, and with what vote share?
Recommend a deployment configuration (k, metric, scaling) with the two-paragraph justification.

View Solution / Walkthrough

import numpy as np, pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import confusion_matrix, accuracy_score

ds = pd.read_csv('Social_Network_Ads.csv')
X, y = ds.iloc[:, :-1].values, ds.iloc[:, -1].values
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.25, random_state=0)
sc = StandardScaler()
Xs_tr, Xs_te = sc.fit_transform(X_tr), sc.transform(X_te)

scaled = KNeighborsClassifier(n_neighbors=5).fit(Xs_tr, y_tr)
print(confusion_matrix(y_te, scaled.predict(Xs_te)),
      accuracy_score(y_te, scaled.predict(Xs_te)))          # 0.93

raw = KNeighborsClassifier(n_neighbors=5).fit(X_tr, y_tr)
print('unscaled:', raw.score(X_te, y_te))                    # 0.83

for k in [1, 3, 5, 11, 21, 51]:
    m = KNeighborsClassifier(n_neighbors=k).fit(Xs_tr, y_tr)
    print('k=%2d train=%.3f test=%.3f' % (k, m.score(Xs_tr, y_tr), m.score(Xs_te, y_te)))

p = scaled.predict_proba(sc.transform([[30, 150000]]))[0]
print('(30,150k):', scaled.predict(sc.transform([[30, 150000]]))[0], p)

Expected results (real):

Steps 1–2: scaled 0.93 ([[64,4],[3,29]]) vs unscaled 0.83 — mechanism: raw salary units make distance ≈ salary distance (20,000 vs 10 for equal-sized human differences), so age — the stronger driver — is silenced.
Step 3: scaled d(A,B) = 20,000/34,054 ≈ 0.59 vs d(A,C) = 10/10.5 ≈ 0.96 — the age gap now measures larger, matching its stronger effect on purchase.
Step 4: k=1: train 1.000 / test 0.87 (memoriser); plateau 0.93 from k=3 to 41; 0.92 at k=51.
Step 5: K-NN predicts 1 (buy) for (30, ₹150k) — where logistic sat on its fence at p = 0.491, the local vote finds wealthy young buyers nearby and commits.
Step 6: deploy scaled, k = 5 (odd, mid-plateau, sklearn default), Euclidean — plus the honest note that final k should be confirmed by cross-validation (Ch 31), not the test sweep.

🎯 Key Takeaways

K-NN is lazy: training = storage, prediction = search + majority vote. The model IS the memory.

Distance is the only geometry — and it's unit-blind: raw units made a ₹20k gap 2,000× "farther" than a 10-year gap. Scaling flipped the verdict.

The scaling failure was real and silent: 0.83 vs 0.93 — ten customers lost to unit choice, no error raised.

k is the bias-variance dial: k=1 memorised (train 1.000/test 0.87); the plateau 0.93 from k=3–41 shows robustness. Odd k avoids ties.

K-NN "probabilities" are vote shares in steps of 1/k — [1.0, 0.0] unanimous — not calibrated chances like logistic's.

93% vs logistic's 89%: the local wiggly boundary captured the nonlinear region — at the price of coarse explanations and per-prediction search.