Skip to content

K-Nearest Neighbors

What This Is

K-nearest neighbors (KNN) predicts from the labels of the k closest training points under a distance metric. The model has no parameters: the training set is the model.

The practical lesson is that KNN is a transparent baseline that exposes every data hygiene issue you have — scaling, noise, wrong distance choice, local label density — in one line. If KNN behaves strangely, the problem is usually in the features or the split, not the algorithm.

When You Use It

  • a fast sanity-check baseline on a cleaned, scaled feature matrix
  • small-to-medium datasets where the local structure is genuinely informative
  • a diagnostic: if a distance-based lookup beats your trained model, the features and a lookup table are doing the work
  • prototype phases where you want a runnable answer before deciding on a real model
  • intuition-building — KNN is the easiest model to reason about visually

Do Not Use It When

  • the feature matrix is high-dimensional and distances lose their meaning (curse of dimensionality)
  • the dataset is very large — inference is O(n) per query without a spatial index
  • features are on wildly different scales and you cannot scale them
  • the relationship is globally structured (linear, monotone) rather than local — use a linear model or a tree

Tooling

  • KNeighborsClassifier
  • KNeighborsRegressor
  • Pipeline + StandardScaler
  • n_neighbors
  • weights="uniform" or weights="distance"
  • metric="euclidean", "manhattan", "cosine", "minkowski"
  • algorithm="ball_tree", "kd_tree", "brute"
  • leaf_size for tree-based indexing

How The Decision Is Made

For classification with k=5:

  1. compute distances from the query point to every training point
  2. pick the 5 smallest
  3. vote — majority class wins, or weight votes by 1/distance if weights="distance"

For regression, the vote becomes an average (optionally weighted).

That is the whole algorithm. Every issue you hit with KNN is either in the distance, in the scaling, in the k choice, or in the data itself.

Scaling Is Not Optional

Without scaling, a feature that happens to live on a bigger numerical range dominates the distance. That is not a KNN quirk — it is the literal definition of Euclidean distance on unequal axes. Put StandardScaler in the pipeline before the KNN step or the coefficients of scale win over every other signal.

Choosing k

  • small k (1, 3) — low bias, high variance; the decision boundary follows every local label
  • large k (25, 51) — higher bias, smoother boundary; outliers and label noise wash out
  • choose odd values for binary classification to avoid ties
  • sweep k with cross-validation and plot the validation metric against k — the curve is almost always smooth and convex

Minimal Example

from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier

model = make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=5))
model.fit(X_train, y_train)

The pipeline is the point. Scaling outside the pipeline leaks test-set statistics into the training split — KNN will silently reward the leak.

Curse Of Dimensionality

In high dimensions, all pairwise distances concentrate around the same value — the ratio between the farthest and the nearest point approaches 1. When that happens, "nearest" stops being a useful notion and KNN degrades into near-random behavior.

The practical signs:

  • validation accuracy plateaus around the majority-class rate
  • sweeping k barely changes the answer
  • switching distance metric barely changes the answer

The fix is dimensionality reduction (see PCA or Advanced Clustering and Dimensionality Reduction) or a different model family.

Distance Metric Choice

Metric Good for
Euclidean scaled continuous features, default
Manhattan grid-like or sparse-continuous features
Cosine text or embeddings where magnitude should not count
Hamming categorical or binary features

Change the metric before giving up on KNN. The right distance is often the whole game.

What To Inspect

  • the validation curve as a function of k — convex and smooth is the expected shape
  • the decision boundary on a 2D projection
  • whether scaling was actually applied before distance computation
  • how much accuracy moves when you switch from euclidean to manhattan
  • whether the nearest neighbor of a test point is itself (data leak — the same example is in both splits)
  • whether high-dimensional distances are collapsing — histogram them

Failure Pattern

Running KNN without scaling and blaming the algorithm for noisy predictions. The distance is literally not measuring what you think it is measuring.

A second failure pattern is picking k=1 and mistaking memorization for performance. With k=1 on a training-set split, the accuracy is 100% and meaningless — only the held-out split reveals what the model has.

A third failure pattern is running KNN on 500-dimensional features with no reduction and being surprised by the poor result. The curse of dimensionality is a geometric fact, not a hyperparameter.

Quick Checks

  1. Is the scaler in the pipeline?
  2. Is k being chosen from a validation curve, not guessed?
  3. Does the problem have fewer than ~20 truly informative features? If not, reduce first.
  4. Does switching metric change the answer meaningfully?
  5. Is the inference time acceptable for the production query rate?

Practice

  1. Fit a KNN classifier on a 2D toy problem and plot the decision boundary.
  2. Sweep k from 1 to 51 and plot the validation accuracy curve.
  3. Compare metric="euclidean" against metric="manhattan" on the same split.
  4. Remove the scaler from the pipeline and explain what happens to the predictions.
  5. Run KNN on a 2-feature version of a dataset and on the full 50-feature version. Compare and explain the gap.
  6. Explain why weights="distance" can help when the labels near the boundary are noisy.
  7. Describe one case where KNN's high inference cost makes it the wrong choice.
  8. State the relationship between k and bias-variance.
  9. Explain why the training-set accuracy of KNN with k=1 is always 100% and why that is not useful.
  10. Describe one way to tell whether the curse of dimensionality is kicking in.

Longer Connection

KNN sits next to:

KNN is the model that refuses to hide anything. The features you feed it, the scale you forgot, and the split you made — it shows all of them in the first validation number.