Decision Boundaries of Nearest-Neighbor Models

This article starts with a short program rather than a definition. A program that uses KNeighborsClassifier prints two things: an array of predicted labels for the test points, and an accuracy value. Before you run any program like this, try to picture what each line does and what it will print. Write down your expectation for each output and the reason behind it. The rest of the article explains the mechanism that produces those outputs.

The k-nearest neighbors algorithm is a classification method. To predict the label of a new data point, it looks at the training points that lie closest to that new point and uses their labels. The algorithm does not first build a set of learned rules. Instead it stores the training examples and does its work when a prediction is requested.

The simplest version uses one neighbor. Suppose a new point sits among labeled training points. You find the training point nearest to it, read that point's label, and give the same label to the new point. With one neighbor, the model's behavior is fully determined by which training point is closest.

Finding the nearest neighbor is a search over the stored training points. For each new point, the algorithm measures how far it is from every training point and identifies the closest one. The distance between two points measures how similar their feature values are. A small distance means the two points are near each other in feature space. Notice that the nearest neighbor is chosen by distance alone, before any labels are considered.

Using only the closest point can be fragile. A single unusual training point can decide the answer for everything near it. So the algorithm can consider an arbitrary number k of neighbors instead. This is the origin of the name k-nearest neighbors. When more than one neighbor is considered, the algorithm uses voting: for each test point, it counts how many of its k neighbors belong to each class, and assigns the class that appears most often.

The same voting rule works beyond two classes. The algorithm counts the neighbors belonging to each class and predicts the most common one. Notice what the vote does not depend on. The value of k is the number of neighbors that vote. It is not tied to how many distinct labels exist in the data.

The flowchart below shows the order of operations for one new point. The steps happen in sequence: distances are computed to every stored training point, those distances are used to rank the training points, the k closest are selected, their labels are counted, and the majority label becomes the prediction. Read the diagram from top to bottom and notice that the labels are not consulted until the neighbors have already been chosen.

Consider a small one-dimensional dataset written for this article. The training points are at positions 1, 2, 3, 6, and 7, with labels A, A, B, B, and B. The new point sits at position 2.8. Distance here is simply the absolute difference in position. Distances from 2.8 are 1.8 to the point at 1, 0.8 to the point at 2, 0.2 to the point at 3, 3.2 to the point at 6, and 4.2 to the point at 7.

The same new point can receive a different label when k changes. The before-and-after diagram compares the two cases for the point at position 2.8. With k equal to 1, the only neighbor is the point at 3, so the label is B. With k equal to 3, the neighbors include two A points that are farther away than the B point but still count in the vote. The changed label is the outcome of the vote, not of the nearest point alone.

In scikit-learn, the algorithm is wrapped in a class called KNeighborsClassifier. The number of neighbors is set when the object is created, through the n_neighbors argument. The three calls that matter most are fit, predict, and score. The sequence below shows which parts of the program send data to the classifier and what each call returns. Pay attention to the order, because the work happens at different times.

The creation step and the fit step only record information. The fit call does not compute a boundary or a set of rules. The predict call does the real work by searching for neighbors and voting for each test point. The score call also does real work: it calls predict internally, then compares the predicted labels with the true labels and reports the result as accuracy.

The accuracy value is computed on the test set, not the training set. The model has already stored every training point, so a score on training data would only show how well it recalls points it has already seen. The test set is what checks generalization to new points.

The score is the fraction of test points whose predicted label matches the true label. If a test set has four points and three of them are predicted correctly, the score is 3 out of 4, which is 0.75. The score therefore moves in steps: each additional correct test point raises it by one fraction of the test set size.

A decision boundary is the place in feature space where the predicted label changes. For k equal to 1, every location is assigned to the class of its nearest training point. In the one-dimensional dataset from the worked example, the boundary is a single point, halfway between the A point at 2 and the B point at 3, which is position 2.5. Positions below 2.5 are closer to an A point and receive label A. Positions above 2.5 are closer to a B point and receive label B.

In two dimensions, the same idea produces regions instead of a single cut point: each location in the plane belongs to whichever class its nearest neighbors favor, and the regions meet along boundary lines. The one-dimensional picture is enough to see the mechanism. The boundary moves when the vote changes, which is why increasing k can shift where the regions meet.

When an accuracy value looks wrong, the useful question is where the result diverged from what you expected. The table below uses k equal to 1 on a small test set written for this article. Each row compares the predicted label with the true label. The one row marked as a mismatch is the point that lies on the wrong side of the learned boundary.

The point at 3.4 is predicted B because the training point at 3 is its nearest neighbor, at distance 0.4. The true label is A, so this point sits on the wrong side of the boundary at 2.5 relative to its true class. The score of 0.75 summarizes this result, but the table identifies which test point caused the miss.