K-Nearest Neighbors algorithm — AI-ML notes

WHY does KNN work at all?

WHY no training? KNN is a lazy learner: it stores the data and does all the work at query time. There is no model to fit — the training data is the model. This is called instance-based or memory-based learning.

WHAT exactly is the algorithm?

HOW do we measure "nearness"? (Derive the distances)

We need a function $d(x, x')$ that is $0$ when $x=x'$ and grows as they differ.

Formula Minkowski distance (the parent formula)

Start from the idea: total difference = combine per-feature differences. Raise each to power $p$ , sum, take the $p$ -th root: $d_p(x, x') = \left(\sum_{j=1}^{D} |x_j - x'_j|^p\right)^{1/p}$ Why the $1/p$ root? So the units of $d$ match the units of a single coordinate (scale-consistency: doubling all coordinates doubles the distance).

$p=2$ → Euclidean (straight-line): $\sqrt{\sum (x_j - x'_j)^2}$ .
$p=1$ → Manhattan/taxicab: $\sum |x_j - x'_j|$ .
$p\to\infty$ → Chebyshev: $\max_j |x_j - x'_j|$ (the largest single-coordinate gap dominates).

Why $p\to\infty$ gives the max: in $\left(\sum a_j^p\right)^{1/p}$ , the largest term $a_{\max}$ dominates: factor it out, $a_{\max}\left(\sum (a_j/a_{\max})^p\right)^{1/p}$ . Each ratio $\le 1$ , so raised to huge $p$ they vanish except the max's own $1$ -term. Result $\to a_{\max}$ .

HOW to pick $k$ ? (The bias–variance story)

The killer weakness: scale & the curse of dimensionality

Distance-weighted KNN (an upgrade)

Worked Examples

Recall Feynman: explain to a 12-year-old

Imagine a new kid joins school and you must guess if they like football or chess. You look at the 3 kids sitting closest to them. If 2 like football and 1 likes chess, you guess football. That's KNN — guess by asking your nearest neighbors and going with the crowd. If you ask too few neighbors you might get fooled by one weird kid; ask too many and you're just guessing what the whole class likes, ignoring who's actually nearby.

Active Recall

KNN — what is stored as the "model"?

The entire training dataset itself (instance-based, lazy learning); no parameters are fit.

KNN classification prediction rule

Majority vote of the labels of the

k

nearest training points.

KNN regression prediction rule

Mean (or distance-weighted mean) of the

y

-values of the

k

nearest points.

General distance formula (Minkowski)

d_p(x,x') = (\sum_j |x_j-x'_j|^p)^{1/p}

; p=1 Manhattan, p=2 Euclidean, p→∞ Chebyshev.

Effect of small k vs large k

Small k → low bias, high variance (jagged/overfit); large k → high bias, low variance (smooth/underfit).

Why use odd k in binary classification

To avoid tie votes and guarantee a strict majority.

Why standardize features before KNN

So large-range features don't dominate the distance; each feature contributes comparably.

Curse of dimensionality for KNN

In high dimensions all points become nearly equidistant, so "nearest" loses meaning and neighborhoods must be huge.

Distance-weighted KNN weight

w_i = 1/d(x,x_i)^2

; closer neighbors count more.

Heuristic starting value for k

k \approx \sqrt{N}

, then tune with cross-validation.

Connections

Decision Trees — also non-parametric, but partitions space globally vs KNN's local view.
Bias-Variance Tradeoff — $k$ directly controls it.
Feature Scaling & Standardization — prerequisite for meaningful distances.
Curse of Dimensionality — main failure mode.
K-Means Clustering — shares "distance to centers" idea but is unsupervised (don't confuse!).
Cross-Validation — how we pick $k$ .

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

KNN ka funda bilkul simple hai: kisi naye point ka label predict karna hai, to us point ke sabse paas wale $k$ points dekho jo tumne pehle se store kiye hue hain, aur unse "voting" kara lo. Classification me majority class jeet jaati hai, regression me neighbors ke values ka average le lete hain. Isliye ise "lazy learner" bolte hain — training me kuch seekhna nahi padta, poora data hi model ban jaata hai, mehnat prediction ke time hoti hai.

"Paas" ka matlab distance se hota hai — sabse common Euclidean distance $\sqrt{\sum (x_j-x'_j)^2}$ . Ek bahut important cheez: features ko pehle standardize karo. Kyunki agar ek feature salary hai (lakhs me) aur doosra age (0-100), to distance sirf salary decide kar dega, age ignore ho jaayegi. Standardize karne se sab features barabar ka contribution dete hain.

$k$ choose karna ek balance ka game hai. Chhota $k$ (jaise 1) bahut sensitive hota hai — ek galat neighbor se answer flip ho jaata hai (high variance, overfit). Bada $k$ zyada smooth hota hai par detail miss karta hai (high bias, underfit). Isliye $k$ ko cross-validation se tune karo, aur 2 classes ke liye odd $k$ lo taaki tie na ho.

Ek warning: high dimensions me KNN struggle karta hai — "curse of dimensionality" ke kaaran saare points lagbhag equidistant ho jaate hain aur "nearest" ka meaning khatam ho jaata hai. To pehle feature selection ya dimensionality reduction useful hai. Yaad rakho: "Lazy Voters Standing Close."

Test yourself — Tree-Based & Instance Methods

Connections