k-Nearest Neighbors
How does KNN classify a point?
There's no training — it just stores the data. To classify a new point it finds the k closest stored points and takes a majority vote. That's why it's called a lazy learner: all the work happens at prediction time.
- “Which distance metric?” — Euclidean by default; Manhattan for high dimensions; cosine for text/embeddings.
- “Can KNN do regression?” — Yes — average (or distance-weight) the k neighbors' values instead of voting.
- “Training vs prediction cost?” — Training is O(1) (just store data); prediction is O(n·d) per query without an index.
How do you choose k?
k is the bias-variance dial. Small k follows every wiggle (low bias, high variance, noise-sensitive); large k smooths the boundary (high bias, low variance). Tune it with cross-validation, and use an odd k to avoid ties.
- Jagged boundary; fits noise.
- Low bias, high variance.
- One mislabeled neighbor flips the answer.
- Smooth boundary; may blur real structure.
- High bias, low variance.
- Very large k just predicts the majority class.
- “How to weight neighbors?” — Weight votes by 1/distance so closer points count more.
Why does KNN break in high dimensions?
The curse of dimensionality: as features grow, points spread out and all distances become nearly equal, so “nearest” stops meaning anything. KNN also gets slow and memory-heavy because every prediction scans the whole dataset.
In high dimensions the nearest and farthest neighbors are almost the same distance — the vote is meaningless.
A feature with a big range dominates Euclidean distance. Always scale features.
Use PCA or feature selection to cut dimensions; KD-trees / approximate search to speed lookups.
What does the KNN decision boundary look like?
KNN draws a non-linear, piecewise boundary that follows the data and makes no assumption about its shape. With k=1 the boundary is jagged and wraps every point; as k grows it smooths out.
- “Parametric or non-parametric?” — Non-parametric: it keeps all the data and assumes no fixed functional form, so the model grows with the dataset.
How does class imbalance affect KNN?
The majority class tends to dominate the vote simply because it has more points nearby, so the minority class gets under-predicted.
- “How do you counter it?” — Distance-weighted voting, resampling the data, or adjusting the decision threshold.