Choosing K and the curse of dimensionality

Context: In k-Nearest Neighbors (kNN) we classify a point by the majority vote (or average) of its $k$ closest training points. Two questions decide whether kNN works at all: How big should $k$ be? and Why does kNN quietly die in high dimensions?

1. The role of $k$ — bias vs variance

WHY small $k$ = high variance

With $k=1$ , your prediction is one training label. If that neighbor happens to be a mislabeled or noisy point, you copy the error. Perturb the training set slightly → the nearest neighbor can flip → prediction flips. High sensitivity to data = high variance.

WHY large $k$ = high bias

As $k \to N$ (all points), every query returns the same answer: the global majority class / global mean. The model ignores $x$ entirely. That systematic wrongness is bias.

2. The curse of dimensionality

Figure — Choosing K and the curse of dimensionality

WHY neighborhoods explode — the volume argument

Suppose data is uniform in the unit cube $[0,1]^d$ . To capture a fraction $r$ of the data with a small cube of side $\ell$ , we need the volume to match: $\ell^d = r \;\Rightarrow\; \ell = r^{1/d}.$

WHY distances concentrate

For random points in $d$ dimensions, the ratio between the farthest and nearest neighbor distances shrinks toward 1: $\frac{d_{\max} - d_{\min}}{d_{\min}} \xrightarrow{d\to\infty} 0.$ Each coordinate adds a roughly independent squared term to $\|x-y\|^2 = \sum_{i=1}^d (x_i-y_i)^2$ . By the law of large numbers the average term stabilizes, so all pairwise distances cluster near the same value — their relative spread vanishes. If everything is equidistant, "the $k$ nearest" is essentially random.

3. Practical prescription (the 80/20)

Standardize features first (z-score), else large-scale features hijack distance.
Choose $k$ by cross-validation, expect a U-curve; use 1-SE rule for robustness.
Reduce $d$ before kNN: drop irrelevant features, PCA, or embeddings.
Rule of thumb: kNN shines when $d$ is small (say $\lesssim 15$ ) and $N$ is large.

Recall Feynman: explain to a 12-year-old

Imagine finding friends by "who lives closest." On a single street (1D), your closest neighbor is genuinely next door — easy. Now imagine everyone lives in a giant 20-dimensional apartment building where each person differs on 20 traits. Suddenly everybody is "sort of similar and sort of different" — nobody is clearly your closest friend. That's the curse: in many dimensions, closeness stops being meaningful, so "ask your nearest neighbor" gives useless advice. And $k$ ? It's how many neighbors you ask: ask one and a weird person misleads you; ask everyone and you just get the crowd's average, ignoring you completely. Pick a middle number by testing.

Flashcards

What does

k

control in kNN, in bias–variance terms?

Small

k

= high variance (overfit); large

k

= high bias (underfit). It's a smoothing knob.

Approximate degrees of freedom of kNN?

\text{df}\approx N/k

; more neighbors → fewer effective regions → simpler model.

How do you choose

k

in practice?

Cross-validation, pick the

k

minimizing CV error (U-shaped curve); 1-SE rule for a simpler, robust choice.

Edge length to capture fraction

r

of uniform data in

d

dims?

\ell = r^{1/d}

; grows toward 1 as

d

increases.

For

r=0.01

d=10

, what is

\ell

0.01^{0.1}\approx 0.63

— must span 63% of each axis, so "local" is meaningless.

Why do distances concentrate in high dimensions?

\|x-y\|^2=\sum_i(x_i-y_i)^2

; many independent terms average out, so all pairwise distances cluster near one value; relative spread → 0.

How does required sample size scale with dimension for fixed density?

Exponentially,

N\propto b^d

Why doesn't "add more features" help kNN like it can help linear models?

kNN has no coefficients; each feature adds equally to distance, so irrelevant features inject noise into every neighbor computation.

Is picking odd

k

a universal rule?

No — only avoids ties in binary problems; with >2 classes ties still occur. Use distance weighting / CV instead.

Connections

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

kNN me do cheezein sabse important hain: $k$ kitna rakhein aur high dimensions me kya hota hai. $k$ ek smoothing knob samjho. Agar $k=1$ rakha, to model sirf ek closest neighbor ki baat maanega — agar wahi point galti se noisy ya galat labelled hua, prediction bhi galat. Isko high variance bolte hain (overfitting). Agar $k$ bahut bada, model bas majority class ya average de dega, tumhare point $x$ ko ignore karke — ye high bias (underfitting) hai. Isliye beech ka $k$ cross-validation se choose karte hain; error vs $k$ ka graph U-shape banta hai, aur U ke bottom pe best $k$ milta hai.

Ab curse of dimensionality. Formula yaad rakho: uniform data me sirf fraction $r$ pakadne ke liye har axis pe edge length $\ell = r^{1/d}$ . Maano $d=10$ aur tum sirf 1% data chahte ho — $\ell = 0.01^{0.1} \approx 0.63$ , matlab har axis ka 63% span cover karna padega! To "nearest neighbor" ab local raha hi nahi. High dimensions me saare points ki aapas ki distance almost barabar ho jaati hai, isliye "nearest" ka matlab hi khatam.

Practical baat: pehle features ko standardize karo (z-score), warna bade scale wala feature distance ko hijack kar lega. Phir agar dimensions zyada hain to PCA ya feature selection se kam karo — kyunki kNN me har feature distance me equally add hota hai, irrelevant features sirf noise dalte hain. Ek common galti: "odd $k$ lo taaki tie na ho" — ye sirf 2-class me kaam ka hai, 3+ classes me phir bhi tie ho sakta hai. So bharosa cross-validation pe rakho, rule-of-thumb pe nahi.

Test yourself — Tree-Based & Instance Methods

Connections