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.

-1-0.8-0.6-0.4-0.200.20.40.60.811.2-1-0.8-0.6-0.4-0.200.20.40.60.811.2Scaled feature 1Scaled feature 2
Class AClass BNew input
The three closest points to (0, 0) are A at distance 0.2, B at 0.4 and A at 0.5; uniform voting predicts A.

How it works

  1. Store training features and labels after fitting any scaling on training data.
  2. Compute distances from the new input to stored examples.
  3. Select the $k$ nearest examples with a defined tie rule.
  4. 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)

Learn it

Interview questions about k-nearest neighbors