[Classification/Regression]
K-Nearest Neighbors (KNN).
Predicts based on the k closest training examples in feature space.
SPEC SHEET
FIG — THE MECHANISM, LIVE
Every pixel is coloured by voting among its nearest labelled neighbours - the boundary is wherever the vote flips.
C — How it actually works
No training at all - just memorise the dataset. To classify a new point, find its k nearest labelled neighbours and take a vote. The entire notion of "model" is replaced by "similar things have similar labels", which makes it the most honest baseline in the toolbox.
D — The math
ŷ(x) = majority vote (or distance-weighted mean) over the k points minimising dist(x, xᵢ) - usually Euclidean or cosine. All the intelligence lives in the distance metric and the value of k.
Training
O(1) (store the data)
Inference
O(n·d) brute force; O(log n) with KD/ball trees at low d
E — When NOT to use it
- High dimensions - the curse of dimensionality makes all distances nearly equal by d≈20-30 raw features
- Latency-critical serving on large datasets (inference cost lives where you least want it)
- Features on wildly different scales or with many irrelevant columns - distance gets polluted
F — Tuning that matters
- Scale features first; it changes everything about the distance
- Odd k avoids ties; sweep k over 1-31 with CV - small k = low bias/high variance
- weights="distance" usually beats uniform voting
- Above ~100k points, switch to approximate nearest neighbours (FAISS, Annoy, HNSW)
G — Production pitfalls
- Using raw unscaled features (income in lakhs vs age in years = income decides everything)
- Deploying brute-force kNN behind a 50ms SLA on millions of rows
- Ignoring class imbalance - the majority class wins every vote in dense regions
- Forgetting kNN has zero compression: your "model" is your training data, PII and all
H — Minimal starting point
PYTHONfrom sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
clf = make_pipeline(StandardScaler(),
KNeighborsClassifier(n_neighbors=15, weights="distance"))
clf.fit(X_train, y_train)I — The interview question
Why does kNN fall apart in high dimensions?
In high-dimensional space the ratio between the nearest and farthest neighbour distances approaches 1 - everything is roughly equally far away, so "nearest" stops carrying information. Fixes: reduce dimensions first (PCA, embeddings) or learn a metric.
J — In the wild
Modern retrieval-augmented AI is kNN at planetary scale: every vector database answering "find the most similar documents to this query embedding" is approximate k-nearest-neighbours (HNSW/IVF) - the same idea, industrialised.
K — Consider instead
- Random Forest— handles mixed scales and irrelevant features without metric engineering
- Support Vector Machine (SVM)— when you want a real margin instead of local voting in medium dimensions
Other classification/regression options