k-Nearest Neighbors

A KNeighborsClassifier is fitted on the Breast Cancer dataset many times.

Programming

An Experiment Before Any Definition

This article begins with a short experiment rather than a definition. A KNeighborsClassifier is fitted on the Breast Cancer dataset many times. Each time, only one setting changes: the number of neighbors, called n_neighbors. Each fitted model is then scored on two different sets of data, the training data and the test data. Everything the article explains is a way of interpreting the numbers this loop produces.

What do you think happens?

Across the range of n_neighbors values tried, which setting gives the best test performance on the Breast Cancer experiment?

One neighbor
Around six neighbors
Ten neighbors

Reveal answer

Answer:

Around six neighbors. Both extremes perform worse.

The best performance lies in the middle of the range. A single neighbor fits the training data perfectly but generalizes less well than models with more neighbors, and ten neighbors is already too simple.

Keep this result in mind. The rest of the article explains why the middle value wins and how to read the evidence that shows it.

Watching the Decision Boundary Form

For a two-dimensional dataset, every point in the plane can be treated as a hypothetical test point. If you ask the classifier which class it would assign to each location and color each location by that answer, the colored plane reveals a divide. This divide is the decision boundary: the line separating the region where the algorithm assigns class 0 from the region where it assigns class 1.

The boundary is not a fixed property of the data. The classifier produces it, and its shape depends on how many neighbors each prediction consults. With one neighbor, every location in the plane takes the label of its single nearest training point, so the boundary bends around each individual training example. With more neighbors, each location is labeled by a vote among several nearby points, so small irregularities are averaged out and the boundary becomes smoother.

How does the boundary between class 0 and class 1 become smoother or more jagged as n_neighbors goes from 1 to a large value?

Read the diagram from left to right. A small neighbor count produces a jagged boundary that follows the training points closely. A large neighbor count produces a smooth boundary that depends on broad regions of the plane. The change is gradual: the boundary does not jump, it smooths as more neighbors take part in each vote.

Neighbor Count and Model Complexity

Model complexity describes how flexible a model is in fitting the patterns in its training data. For KNeighborsClassifier, the neighbor count controls this flexibility. A small number of neighbors yields a model with high complexity, because its predictions can follow fine local detail. A large number of neighbors yields a model with low complexity, because its predictions depend on broad regions and change gently.

How does increasing or decreasing n_neighbors change model complexity, and how does that change affect generalization to new data?

Generalization is the question of how well the model performs on data it has not seen. Complexity and generalization are linked through the neighbor count: moving to either extreme can hurt generalization, which is why the best value in the experiment sits in the middle.

Reading the Accuracy Plot

The plot produced by the loop puts n_neighbors on the horizontal axis and accuracy on the vertical axis. It has two lines: one for training accuracy and one for test accuracy. Because fewer neighbors means a more complex model, the plot runs opposite to a textbook sketch of complexity. The most complex model sits on the left, not the right.

Region of the plot	What the two lines do	What it indicates
Far left, one neighbor	Training accuracy is perfect; test accuracy is lower than at larger neighbor counts	Too complex: overfitting
Middle, around six neighbors	Training and test accuracy are both high, with test accuracy at its best	Balanced: best generalization
Far right, around ten neighbors	Both accuracies drop, with performance worse than in the middle	Too simple: underfitting

Reading the training-versus-test plot from left to right

Worked example

Locating overfitting and underfitting on the curve

Given the training-versus-test plot for the Breast Cancer experiment, where does overfitting appear, where does underfitting appear, and where is the best setting?

1
Check the leftmost point
At one neighbor, training accuracy is perfect, but test accuracy is lower than at larger neighbor counts. The gap between the lines points to overfitting: the model is too complex.
2
Check the rightmost point
At ten neighbors, both accuracies fall. When both lines drop together, the model is too simple, which is underfitting.
3
Find the middle
Around six neighbors, test accuracy reaches its peak. The model is complex enough to capture real patterns but not so complex that it memorizes the training set.

Result

Overfitting is on the left, underfitting is on the right, and the best setting is around six neighbors.

python

from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier

X, y = load_breast_cancer(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=0, stratify=y)

for n in range(1, 11):
    clf = KNeighborsClassifier(n_neighbors=n)
    clf.fit(X_train, y_train)
    print(n, clf.score(X_train, y_train), clf.score(X_test, y_test))

from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier

X, y = load_breast_cancer(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=0, stratify=y)

for n in range(1, 11):
    clf = KNeighborsClassifier(n_neighbors=n)
    clf.fit(X_train, y_train)
    print(n, clf.score(X_train, y_train), clf.score(X_test, y_test))

Notes on the code

The split uses random_state and stratify, so the test set stays fixed across iterations
A new classifier is built on every pass with the current n_neighbors value
Training accuracy is computed on X_train and test accuracy on X_test

The code above is an illustrative reconstruction of the loop the source describes, not the source's exact listing. Each printed row gives one neighbor count followed by its training accuracy and its test accuracy, which is exactly the data needed to draw the two-line plot.

Mistakes When Reading the Results

Common mistake
Assuming more neighbors always means a better model
Why it fails
The source shows performance rising to a middle value and then falling. Both extremes perform worse than the middle.
Do this instead
Locate the peak of the test curve and check both sides of it.
Common mistake
Reading the complexity axis in the textbook direction
What it looks like
Expecting the most complex model on the right side of the plot.
Why it fails
Here fewer neighbors means more complexity, so the most complex model is on the left.
Do this instead
Remember that n_neighbors increases from left to right, and complexity decreases in that direction.
Common mistake
Calling every gap between the lines overfitting
Why it fails
Overfitting is a training-versus-test gap in a complex model. Underfitting is different: both lines are low together.
Do this instead
Ask whether the model is complex and fits training data well but not new data, or simple and poor on both.
Common mistake
Treating a single run as the final answer without checking the split settings

Tracing an Unexpected Result

Suppose you run the loop and the test accuracy curve peaks at a different place than the explanation predicts. Debugging means finding which line of the experiment produced the unexpected value. Work through the experiment in order, because each step passes its output to the next. The diagram below lays out that order.

Which step in the sequence of data split, fitting, prediction, and scoring produces the surprising number, and what does each step pass to the next?

First, confirm that the data split uses the same random_state and stratify options. Changing either changes the test set, which changes every test accuracy in the curve.
Second, confirm that each loop iteration builds a new classifier with the current n_neighbors value.
Third, confirm that training accuracy is computed on X_train and test accuracy on X_test, not the other way around.

Edge case

Swapping the two scoring arguments produces a plausible-looking curve with the wrong meaning. Test accuracy would then be measured on the data the model trained on, so the reported test values would no longer show generalization.

Practice: Diagnosing a Curve

MEDIUM

A colleague reports that for n_neighbors equal to 1, training accuracy is perfect, test accuracy is clearly lower than at 6, and at 10 both accuracies have dropped. Which model is overfitting, which is underfitting, and which setting would you choose, and why?

Hints

Overfitting shows up as a complex model with a gap between training and test accuracy.
Underfitting shows up as a simple model where both accuracies are low together.
The best setting is the one where test accuracy peaks.

Your attempt (not saved)

MEDIUM

If the test curve peaked at 2 neighbors instead of around 6 when you reran the loop, list the three steps of the experiment you would check first, in order, and state what each check confirms.

Hints

Start with the data split, since it fixes which examples form the test set.
Then check how the classifier is rebuilt on each iteration.
Finally check which data each accuracy is computed on.

Your attempt (not saved)

Summary of the Neighbor Count Story

The loop in this article changed one setting and read two accuracies. Each interpretation in the article follows from those numbers and the code that produced them.

At a glance

A decision boundary is the divide between the regions where a classifier assigns class 0 and class 1, made visible by coloring the plane with predictions.
A small n_neighbors gives a complex model with a jagged boundary that follows training points; a large n_neighbors gives a smoother, simpler boundary.
On the training-versus-test plot, overfitting appears on the left as a gap between lines, underfitting appears on the right as both lines dropping, and the best setting is around six neighbors in the Breast Cancer experiment.
When a result is unexpected, trace the experiment in order: data split, new classifier per iteration, fitting, scoring on the correct sets, then plotting.

Related concepts

More concepts starting with K