Classic machine learning
K-nearest neighbors
Like asking the people whose tastes are closest to yours, K-nearest neighbors predicts from similar examples. It stores labeled training data and finds the closest examples to a new input. Their labels vote for a class, or their target values are averaged for regression.
Class AClass BNew input
How it works
- Store training features and labels after fitting any scaling on training data.
- Compute distances from the new input to stored examples.
- Select the $k$ nearest examples with a defined tie rule.
- Vote over classes or average numeric targets, optionally weighting by distance.
$$\hat y(x)=\frac1k\sum_{i\in N_k(x)}y_i\quad\text{(regression)}$$
The knobs that matter
- n_neighbors
- Small k gives a flexible, noisy prediction; large k smooths it.
- Distance metric
- Defines which examples count as similar.
- Distance weighting
- Gives nearby examples more influence.
- Feature scaling
- Prevents units alone from controlling neighbor selection.
What interviewers ask
- How does k affect bias and variance?
- Is KNN supervised, and how does it differ from K-means?
- What happens to distances in high dimensions?
- How would prediction cost change with a million stored examples?
Common mistakes
- Leaving features on incompatible scales before computing distances.
- Assuming cheap training implies cheap prediction or low memory use.
When to use it
Use it as a baseline for modest datasets where distance captures useful similarity. Large datasets and many irrelevant dimensions can make prediction costly and neighbors less informative.
Implement it (2 problems)
- K-Nearest Neighbors SearchFreeEasySolve