Context: k-Nearest Neighbors (kNN) mein hum ek point ko uske k sabse nazdeeki training points ke majority vote (ya average) se classify karte hain. Do sawaal decide karte hain ki kNN kaam karega bhi ya nahi: k kitna bada hona chahiye? aur kNN high dimensions mein quietly kyun mar jaata hai?
k=1 ke saath, tumhari prediction ek training label hi hai. Agar wo neighbor mislabeled ya noisy point nikla, tum error copy kar lete ho. Training set ko thoda sa perturb karo → nearest neighbor flip ho sakta hai → prediction flip ho jaati hai. Data ke liye high sensitivity = high variance.
Jab k→N (sab points) hota hai, har query same answer return karti hai: global majority class / global mean. Model x ko bilkul ignore karta hai. Ye systematic galti hi bias hai.
Maan lo data unit cube [0,1]d mein uniform hai. Data ka fraction r capture karne ke liye side ℓ ke chote cube se, volume match karna padega:
ℓd=r⇒ℓ=r1/d.
d dimensions mein random points ke liye, farthest aur nearest neighbor distances ka ratio 1 ki taraf shrink ho jaata hai:
dmindmax−dmind→∞0.
Har coordinate ∥x−y∥2=∑i=1d(xi−yi)2 mein roughly ek independent squared term add karta hai. Law of large numbers se average term stabilize ho jaata hai, isliye saari pairwise distances ek hi value ke aas-paas cluster karti hain — unka relative spread vanish ho jaata hai. Agar sab equidistant hain, toh "k nearest" essentially random hai.
Pehle features ko Standardize karo (z-score), warna large-scale features distance hijack kar lenge.
k cross-validation se choose karo, U-curve expect karo; robustness ke liye 1-SE rule use karo.
kNN se pehle d reduce karo: irrelevant features hatao, PCA, ya embeddings.
Rule of thumb: kNN tab shine karta hai jab d chota ho (roughly ≲15) aur N bada ho.
Recall Feynman: 12-saal ke bachche ko samjhao
Socho tum dost dhundh rahe ho "kaun sabse kareeb rehta hai" ke hisaab se. Ek akeli gali (1D) par, tumhara sabse kareeb waala padosi genuinely agle ghar mein hota hai — aasaan. Ab socho sab log ek bade 20-dimensional apartment building mein rehte hain jahan har insaan 20 traits par alag hai. Achanak sabhi "thode similar aur thode alag" lagte hain — koi clearly tumhara sabse kareeb dost nahi. Ye hai curse: bahut dimensions mein, closeness meaningful nahi rehti, toh "apne nearest neighbor se pucho" bekar advice deta hai. Aur k? Ye kitne neighbors se poochte ho: ek se pucho aur ek weird insaan mislead kar deta hai; sabse pucho aur tum sirf crowd ka average paate ho, tumhe poori tarah ignore karke. Testing se ek beech ka number chuno.
kNN mein k kya control karta hai, bias-variance terms mein?
Chota k = high variance (overfit); bada k = high bias (underfit). Ye ek smoothing knob hai.
kNN ke approximate degrees of freedom?
df≈N/k; zyada neighbors → kam effective regions → simpler model.
Practice mein k kaise choose karte hain?
Cross-validation, wo k chuno jo CV error minimize kare (U-shaped curve); simpler, robust choice ke liye 1-SE rule.
d dims mein uniform data ka fraction r capture karne ke liye edge length?
ℓ=r1/d; d badhne ke saath 1 ki taraf badhta hai.
r=0.01, d=10 ke liye, ℓ kya hai?
0.010.1≈0.63 — har axis ka 63% span karna padta hai, toh "local" meaningless hai.
High dimensions mein distances kyun concentrate hoti hain?
∥x−y∥2=∑i(xi−yi)2; bahut saare independent terms average out ho jaate hain, isliye saari pairwise distances ek value ke paas cluster karti hain; relative spread → 0.
Fixed density ke liye dimension ke saath required sample size kaise scale karta hai?
Exponentially, N∝bd.
"Zyada features add karo" kNN ko linear models ki tarah kyun help nahi karta?
kNN ke paas koi coefficients nahi hote; har feature distance mein equally add hota hai, isliye irrelevant features har neighbor computation mein noise inject karte hain.
Kya odd k choose karna universal rule hai?
Nahi — sirf binary problems mein ties avoid karta hai; 2 se zyada classes ke saath ties phir bhi hoti hain. Iske bajaye distance weighting / CV use karo.
