K-Nearest Neighbors algorithm — Hinglish notes

2.3.15 · AI-ML › Tree-Based & Instance Methods

KNN kaam karta hi kyun hai?

Training kyun nahi? KNN ek lazy learner hai: yeh data store karta hai aur saara kaam query time par karta hai. Fit karne ke liye koi model nahi hota — training data hi model hai. Isse instance-based ya memory-based learning kehte hain.

Algorithm exactly KAISE kaam karta hai?

"Nazdiki" measure KAISE karte hain? (Distances derive karna)

Humein ek function $d (x, x^{'})$ chahiye jo $0$ ho jab $x = x^{'}$ ho aur jaise woh alag hote hain, badhta jaaye.

$p \to \infty$ par max kyun milta hai: $(\sum a_{j}^{p})^{1/ p}$ mein, sabse bada term $a_{m a x}$ dominate karta hai: isse factor out karo, $a_{m a x} (\sum (a_{j} / a_{m a x})^{p})^{1/ p}$ . Har ratio $\leq 1$ hai, isliye huge $p$ tak raise karne par woh vanish ho jaate hain, siwaaye max ke apne $1$ -term ke. Result $\to a_{m a x}$ .

$k$ kaise chunen? (Bias–variance story)

Sabse badi weakness: scale aur curse of dimensionality

Distance-weighted KNN (ek upgrade)

Worked Examples

Recall Feynman: 12-saal ke bachche ko samjhao

Socho ek naya bachcha school mein aata hai aur tumhe guess karna hai ki use football pasand hai ya chess. Tum 3 bacchon ko dekho jo unke sabse paas baithe hain. Agar 2 ko football pasand hai aur 1 ko chess, tum football guess karte ho. Yahi KNN hai — nearest neighbors se poochhkar aur crowd ke saath jaake guess karo. Agar bahut kam neighbors se poochho toh koi ek weird bachcha tumhe fool kar sakta hai; bahut zyada se poochho toh tum basically sirf yeh guess kar rahe ho ki poori class ko kya pasand hai, yeh ignore karke ki actually kaun paas mein hai.

Active Recall

KNN — "model" ke roop mein kya store hota hai?

Poora training dataset khud (instance-based, lazy learning); koi parameters fit nahi hote.

KNN classification prediction rule

k

nearest training points ke labels ka majority vote.

KNN regression prediction rule

k

nearest points ke

y

-values ka mean (ya distance-weighted mean).

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.

Chhote k vs bade k ka effect

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

Binary classification mein odd k kyun use karein

Tie votes se bachne ke liye aur strict majority guarantee karne ke liye.

KNN se pehle features standardize kyun karein

Taaki badi-range features distance dominate na karein; har feature comparably contribute kare.

KNN ke liye curse of dimensionality

High dimensions mein sabhi points nearly equidistant ho jaate hain, isliye "nearest" ka matlab khatam ho jaata hai aur neighborhoods bahut badi ho jaati hain.

Distance-weighted KNN weight

w_{i} = 1/ d (x, x_{i})^{2}

; paas ke neighbors zyada count karte hain.

k ke liye heuristic starting value

k \approx N

, phir cross-validation se tune karo.

Connections

Decision Trees — yeh bhi non-parametric hai, lekin space ko globally partition karta hai vs KNN ka local view.
Bias-Variance Tradeoff — $k$ directly isse control karta hai.
Feature Scaling & Standardization — meaningful distances ke liye prerequisite.
Curse of Dimensionality — main failure mode.
K-Means Clustering — "distance to centers" idea share karta hai lekin unsupervised hai (confuse mat karo!).
Cross-Validation — $k$ kaise choose karte hain.