Skip to content
Tutorials Center
My learning

Topics

Lesson 23 of 111 ยท Classification

k-Nearest Neighbors

Learn how k-nearest neighbors predicts from the closest training points: choosing k, distance metrics, why scaling matters, the curse of dimensionality and speed.

Here is the simplest idea in machine learning: to predict something about a new case, find the most similar cases you have already seen and copy their answer. That is k-nearest neighbors (kNN). There are no coefficients to learn and no equation to fit. The "model" is just the stored training data, and prediction means looking up the k closest points and letting them vote (for classification) or averaging them (for regression).

kNN is easy to understand, a good teaching tool and a surprisingly decent baseline for small, low-dimensional problems. It also makes three big ideas visible: how a hyperparameter (k) controls over- and underfitting, why feature scaling is not optional for distance-based methods, and why too many features hurt (the curse of dimensionality). It follows the other classifiers in this chapter, starting at Logistic Regression.

How kNN predicts

Locate Place the new point among the training points.
Measure Compute the distance to every training point.
Vote Take the k closest and let them vote.

Regression averages the neighbors instead of voting.

1 / 2

The idea in code

KNeighborsClassifier follows the usual estimator API from The scikit-learn API. fit just memorizes the data (and builds a search structure); all the work happens at prediction time. Below we also compute the answer by hand, with plain NumPy, to show there is no magic.

Python kNN by hand and with scikit-learn

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

predict_proba for kNN is just the share of the k neighbors in each class, so with k = 3 it can only be 0, 1/3, 2/3 or 1. That is a coarse probability, not a well-calibrated one.

Choosing k

k is the main hyperparameter. With k = 1 the model memorizes the training set: every training point is its own nearest neighbor, so the training accuracy is perfect and the boundary is jagged and sensitive to noise (overfitting). With a very large k the model averages over so many points that it ignores local structure (underfitting). In between is a sweet spot, and you find it with held-out data or cross-validation. An odd k avoids ties in binary problems.

Python Training and test accuracy as k grows

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the training curve: it starts at 1.0 for k = 1 and falls as k grows, while the test curve rises, peaks and then declines. This "complexity curve" shape is the heart of Overfitting, Underfitting and Bias-Variance. (Picking k by the test score as done here is fine for a demonstration, but in a real project pick it on validation data, never the final test set.)

Distance metrics

"Nearest" needs a definition of distance. The default is Euclidean distance (straight line). Others are available through the metric parameter:

  • Euclidean (p=2): the usual ruler distance.
  • Manhattan (p=1): sum of absolute differences, like walking city blocks; less sensitive to one large difference.
  • Cosine: compares directions, not lengths; common for text vectors.
  • Minkowski: the generalization with parameter p.

You can also set weights="distance" so closer neighbors count for more than distant ones, which softens the effect of k.

Python Metrics and weighting compared

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The differences are small here, which is typical. Metrics matter most when the data has a special geometry (sparse text, angles, binary features), and k and scaling usually matter more.

Scaling matters

Distance adds up differences across features. If one feature is measured in dollars (thousands) and another in years (tens), the dollar difference dominates and the age feature is effectively ignored. Standardizing every feature to zero mean and unit variance puts them on equal footing. We cover scalers in Scaling and Normalization; for kNN, always put a scaler in front, inside a pipeline.

Python The same data with and without scaling

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The label depends only on age, but income is thousands of times larger, so unscaled distances are almost entirely about income and the neighbors are essentially random with respect to age. Scaling restores the signal.

Warning: Fit the scaler on training data only. Putting the scaler inside a pipeline guarantees that, including during cross-validation. See Pipelines.

Decision boundaries and Voronoi cells

A classifier divides the feature space into regions, one per class; the lines between regions are its decision boundary. The shape of that boundary shows how the model thinks.

For k = 1 nearest neighbor the picture is exact and beautiful: every training point owns the part of space that is closer to it than to any other training point. These regions are called Voronoi cells, and the 1-NN decision boundary is the union of the cell edges that separate points of different classes. The boundary can be very jagged, and a single mislabeled or noisy point carves out an island around itself. That is overfitting seen as geometry.

With a larger k the vote of several neighbors smooths the boundary: small islands disappear and the line becomes simpler (and eventually too simple, which is underfitting). The code below classifies every point of a grid with different values of k and reports how the number of separate class regions (islands) and the boundary length fall as k grows, along with the test accuracy. With matplotlib you would paint the grid by predicted class (DecisionBoundaryDisplay.from_estimator(model, X)) to see the regions; here the numbers tell the same story.

Python 1-NN Voronoi cells and smoother boundaries for larger k

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For k = 1 the boundary is longest (964 boundary cells on the grid) and the plane is cut into 14 separate regions: every noisy point carries its own island. As k grows the boundary shortens (601, 449, 356) and the islands merge until only 3 regions remain. The test accuracy changes much less (0.875 for k = 1 and 3, 0.856 for 15 and 75): on this small test set a few points decide the second digit, so a smoother boundary mainly buys stability, not a big jump in score. That is why k is chosen by cross-validation and not by one split. The last line shows the Voronoi cells themselves: each of the 240 training points owns part of the grid. Because the cells are built from distances, scale the features first; a feature on a large scale would stretch the cells in one direction.

The curse of dimensionality

kNN assumes that near points are similar. As you add features, points spread out and the difference between the nearest and the farthest neighbor shrinks: in many dimensions everything is far from everything. Irrelevant features add noise to every distance. The cure is fewer, better features (see Feature Selection) or dimensionality reduction such as Principal Component Analysis.

Python Adding useless features hurts kNN

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

kNN for regression and speed

KNeighborsRegressor averages the targets of the k nearest neighbors, giving a piecewise-constant, step-like curve. It cannot extrapolate beyond the range of the training targets.

Speed is kNN's practical weakness. Training is instant, but each prediction searches the stored data. By default scikit-learn chooses a smart structure (a KD-tree or ball tree for low dimensions, brute force for high ones) with algorithm="auto"; memory grows with the dataset and prediction gets slower as data grows. For millions of rows consider approximate nearest-neighbor libraries or a different model.

Python kNN regression on a noisy curve

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

k = 1 chases every noisy point, k = 40 flattens the curve into a blur, and k = 9 follows the sine wave. Next, a fast probabilistic classifier that works especially well with text: Naive Bayes.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does KNeighborsClassifier.fit do?

    kNN is a lazy learner. The work of finding neighbors happens at prediction time.
  2. 2. With k = 1, what is the accuracy on the training set (no duplicate points with different labels)?

    Each training point's nearest neighbor is itself, so it predicts its own label. That is memorization, not a sign of a good model.
  3. 3. Why should features be scaled before kNN?

    Euclidean distance adds squared differences, so a feature in the tens of thousands overwhelms one in the tens unless both are standardized.
  4. 4. What is a symptom of the curse of dimensionality for kNN?

    In high dimensions distances concentrate, so 'nearest' carries less information, especially when many features are irrelevant.

Summary

  • kNN predicts from the k nearest stored examples: a majority vote for classification, the mean for regression.
  • Small k overfits (jagged), large k underfits (blurry); choose k with validation data or cross-validation.
  • Metric (euclidean, manhattan, cosine) and weights="distance" are secondary knobs.
  • Always scale features inside a pipeline; unscaled large-range features dominate the distance.
  • Many (especially irrelevant) features hurt; reduce dimensions or select features. Prediction cost grows with the data size.

Next up: Naive Bayes.