Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 40 ยท Classification

k-Nearest Neighbors Classifier

Classify by majority vote of nearby samples with KNeighborsClassifier: choosing k, distance weighting, metrics, why scaling matters and the curse of dimensionality.

k-nearest neighbors (k-NN) is the most intuitive classifier: to label a new sample, find the k most similar training samples and let them vote. There is no model to train, only data to store. It is simple, flexible, and a good way to understand how closeness drives prediction.

flowchart LR
    A["New sample"] --> B["Measure distance<br/>to every training sample"]
    B --> C["Take the k closest"]
    C --> D["Majority vote<br/>of their labels"]

Prediction time does all the work; fit only stores the data.

A first k-NN classifier

Python KNeighborsClassifier on wine

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=5, predict_proba is simply the share of the 5 neighbors in each class (0, 0.2, 0.4 ...).

Choosing k

  • Small k (1-3): flexible, follows noise (high variance, overfits).
  • Large k: smooth, but blurs small classes (high bias, underfits).
  • Use an odd k for two classes to avoid ties; pick the best by cross-validation.
Python Cross-validated accuracy for several 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.

A common rule of thumb is to start near the square root of the number of samples, then tune.

Weighting neighbors

By default every neighbor has an equal vote. With weights="distance", closer neighbors count for more, which helps when the neighborhood is uneven.

Python Uniform versus distance weights

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 digits dataset has 1,797 tiny images of handwritten digits, each as 64 pixel values, and k-NN does very well on it.

Distance metrics

The default is Euclidean distance (p=2 in the Minkowski metric). Other choices include metric="manhattan" (sum of absolute differences, more robust in high dimensions), "cosine" (angle between vectors, good for text) and your own function.

Python Changing the metric

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.

Always scale

Because k-NN is built on distance, a column with large values dominates. Compare the same model with and without scaling:

Python Scaling matters for k-NN

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.

See Scaling and Normalization for the choices.

The curse of dimensionality

In many dimensions every point is far from every other, so "nearest" loses meaning. Adding irrelevant columns damages k-NN quickly:

Python Noise columns hurt k-NN

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.

Select useful features or reduce dimensions (for example with PCA) before using k-NN on wide data.

Practical notes

  • Prediction is slow on huge datasets, because it compares to the stored samples. scikit-learn speeds this up with KD-trees and ball trees (algorithm="auto" chooses).
  • It needs the whole training set in memory.
  • Related: RadiusNeighborsClassifier votes among all points within a fixed radius, and NearestCentroid compares to class averages, which is much cheaper.
  • For regression, see Decision Tree and k-NN Regression.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does KNeighborsClassifier.fit do?

    k-NN is a lazy learner: the work happens at prediction time.
  2. 2. k=1 on a noisy dataset usually leads to:

    The single nearest point may be a noisy sample, so the boundary is jagged.
  3. 3. What does weights='distance' do?

    Votes are weighted by inverse distance.
  4. 4. Why does adding many irrelevant columns hurt k-NN?

    Irrelevant dimensions add random distance, drowning the useful signal.

Summary

  • k-NN labels a sample by a vote among its k closest training samples.
  • Tune k by cross-validation; small k overfits, large k underfits.
  • Scale features; consider weights="distance" and other metrics.
  • It suffers when there are many irrelevant dimensions and is slow on very large data.

Next: Decision Tree Classifier