K-Nearest Neighbors, machine learning lesson

Three labeled points lie in the plane, and a new unlabeled point arrives close to one of them. Should it take the label of its single closest neighbor, or the label most common among several nearby points? K-nearest neighbors answers by looking up stored training examples instead of fitting a formula. This lesson defines the distance, the vote and the average the method uses, states the tie rules that make it a well-defined algorithm, and chooses the number of neighbors on validation data.

Key terms

Euclidean distance

Definition For two vectors $\mathbf{x}$ and $\mathbf{z}$ in $\mathbb{R}^p$ , the Euclidean distance is

\begin{aligned} d(\mathbf{x}, \mathbf{z}) &= \lVert \mathbf{x} - \mathbf{z} \rVert_2 \\[0.4em] &= \sqrt{\sum_{j=1}^{p} (x_j - z_j)^2} . \end{aligned}

It is never negative, it equals 0 exactly when $\mathbf{x} = \mathbf{z}$ , it is symmetric, and it satisfies the triangle inequality. In two dimensions it is the length of the hypotenuse given by the Pythagorean theorem. The square root is increasing, so sorting by squared distance gives the same order as sorting by distance. The value depends on the units of every feature, so features are first put on comparable scales with a scaler fitted on the training data.

In plain words Subtract coordinate by coordinate, square each difference so that signs do not matter, add the squares and take the root. Every feature adds a nonnegative amount, so an irrelevant feature with large variation can swamp the relevant ones. When many features vary independently with similar spread, the distances from a query to the training points also tend to become close to one another in relative terms, and the nearest point is then barely nearer than a typical one.

Example The constructed training points are A at $(0, 0)$ with class 0, B at $(2, 0)$ with class 1 and C at $(0, 2)$ with class 1, and the query is $(0.4, 0.3)$ . The coordinate differences are $(0.4, 0.3)$ from A, $(-1.6, 0.3)$ from B and $(0.4, -1.7)$ from C, so the squared distances are

\begin{aligned} d_A^2 &= 0.4^2 + 0.3^2 = 0.25, \\[0.4em] d_B^2 &= 1.6^2 + 0.3^2 = 2.65, \\[0.4em] d_C^2 &= 0.4^2 + 1.7^2 = 3.05. \end{aligned}

The distances are 0.5, about 1.628 and about 1.746, and A is the nearest point.

K-nearest neighbors

Definition Let the training data be pairs $(\mathbf{x}_i, y_i)$ for $i = 1, \dots, n$ , with feature vectors $\mathbf{x}_i$ in $\mathbb{R}^p$ prepared by preprocessing fitted on the training data. Fix a distance $d$ , an integer $k$ with $1 \le k \le n$ and a tie-breaking rule. For a query $\mathbf{x}$ , sort the training indices by $d(\mathbf{x}, \mathbf{x}_i)$ , order equal distances by the tie rule, and let $N_k(\mathbf{x})$ be the set of the first $k$ indices, the $k$ nearest neighbors. A k-nearest neighbors classifier predicts the class with the most votes in $N_k(\mathbf{x})$ , and a k-nearest neighbor regressor predicts the average of their targets. Fitting only stores the training data together with the fitted preprocessing. The work happens at prediction time, where a direct search computes $n$ distances for every query. The method assumes that closeness in the chosen representation goes with similar targets.

In plain words To predict for a new case, find the stored cases that look most like it and let them decide. The method has no coefficients to fit, but its prediction depends on several choices, namely the features and their scaling, the distance, the value of $k$ , the weights and the tie rules. A nearest neighbor always exists, even for a query far from every training point, so nearest does not mean similar enough, and the distances themselves deserve a look.

Example For the query $(0.4, 0.3)$ the order by distance is A, B, C. With $k = 1$ the neighbor set holds A alone and the prediction is class 0. With $k = 3$ all three points vote, two for class 1 and one for class 0, and the prediction changes to class 1. More neighbors gave a different answer, not necessarily a better one.

Majority vote

Definition In classification, let $n_c(\mathbf{x})$ be the number of neighbors in $N_k(\mathbf{x})$ whose label is $c$ . The majority vote predicts

\hat{y}(\mathbf{x}) = \operatorname{argmax}_{c} \ n_c(\mathbf{x}),

the class with the largest count. With three or more classes this is a plurality, and the winner may hold half of the votes or fewer. When several classes share the largest count, the tie-breaking rule decides. The vote fraction $n_c(\mathbf{x})/k$ is a score that takes one of the values $0, 1/k, 2/k, \dots, 1$ . It is not automatically a calibrated probability, so a fraction of $2/3$ need not mean that two thirds of such queries belong to the class.

In plain words Each neighbor casts one vote for its own class, and the class with the most votes wins. With uniform weights, the neighbor at the edge of the set counts as much as the nearest one.

Example With $k = 3$ for the query $(0.4, 0.3)$ , the counts are $n_0 = 1$ and $n_1 = 2$ , so the prediction is class 1 with vote fraction $2/3$ . With three classes and $k = 4$ , counts of 2, 1 and 1 elect a class that holds only half of the votes. With $k = 3$ , counts of 1, 1 and 1 tie all three classes, so an odd $k$ does not prevent vote ties once there are more than two classes.

K-nearest neighbor regression

Definition For a numerical target, k-nearest neighbor regression with uniform weights predicts the mean of the neighbors’ targets,

\hat{y}(\mathbf{x}) = \frac{1}{k} \sum_{i \in N_k(\mathbf{x})} y_i .

The prediction always lies between the smallest and the largest neighbor target. With $k = n$ every query receives the mean of all training targets. Distance-weighted versions give nearer neighbors more influence, for example with weights $1/d(\mathbf{x}, \mathbf{x}_i)$ , and they need a declared rule for a neighbor at distance 0.

In plain words Instead of voting, the neighbors average their numbers, so a prediction can fall between the observed targets rather than on one of a fixed set of classes. With uniform weights the prediction stays constant wherever the neighbor set stays the same, and it jumps where the set changes.

Example Suppose A, B and C have the targets 10, 20 and 25 minutes. For the query $(0.4, 0.3)$ , one neighbor gives 10 minutes, two neighbors give $(10 + 20)/2 = 15$ minutes, and three neighbors give

\frac{10 + 20 + 25}{3} = \frac{55}{3} \approx 18.33 \ \text{min}.

Tie-breaking rule

Definition A tie-breaking rule makes the k-nearest neighbor prediction well defined when ties occur. A distance tie occurs when several training points share the distance of the $k$ th nearest point, so the set of the $k$ nearest points is not fixed by distance alone. A vote tie occurs when several classes share the largest vote count. This page orders equal distances by training row index, lowest first, and breaks a vote tie in favor of the smallest class label. These are reproducible computational conventions, not evidence that one class is preferable. Other rules are possible, such as including every point tied at the boundary or giving the tie to the tied class with the nearest member, and a decision with unequal costs of errors belongs in a separately stated rule. Regression needs only the rule for distance ties.

In plain words Ties are common with small integer coordinates, or with two classes and an even $k$ . Without a stated rule, two correct programs can return different answers for the same query. Writing the rule down makes every prediction reproducible.

Example The query $(1, 1)$ is at squared distance 2 from each of A, B and C. With $k = 1$ the index rule picks A and predicts class 0, while a rule that preferred the last row would pick C and predict class 1. With $k = 2$ the neighbors are A and B, the votes tie at one each, and the smaller-label rule predicts class 0. With $k = 3$ there is no vote tie and the prediction is class 1.

Number of neighbors

Definition The number of neighbors $k$ is a hyperparameter, an integer with $1 \le k \le n$ , chosen by comparing performance on validation data or by cross-validation within the training data, never on the test set. Every preprocessing step, such as the scaler, is fitted on the training part only. With $k = 1$ the classifier reproduces every training label, unless two training points share a feature vector but differ in label, so its training error says little about new data. With $k = n$ every query receives the same prediction, the most frequent training class or the mean training target. No single $k$ is best for every problem. A larger $k$ smooths away isolated points but can mix regions where the target behaves differently. With two classes, an odd $k$ rules out vote ties.

In plain words A small $k$ follows individual points, noise included, and a large $k$ averages over a wide neighborhood. Validation data show which compromise predicts new cases best for the problem at hand.

Example A separate constructed one-dimensional data set has the training features 0, 1, 2, 3 and 4 with labels 0, 0, 1, 0 and 1. The scaler is fitted on these five values, with mean 2 and standard deviation $\sqrt{2}$ under the divisor $n$ , and in one dimension a positive scale keeps the order of the distances. The validation features 0.2, 1.8 and 3.8 have labels 0, 0 and 1. With $k = 1$ the middle query follows the isolated class 1 point at 2 and is wrong, while the other two are right, so the validation accuracy is $2/3$ . With $k = 3$ the middle query’s neighbors are the points 2, 1 and 3 with labels 1, 0 and 0, so it predicts 0, and all three validation cases are right. The value $k = 3$ is selected and then applied once to the test features 1.4 and 3.4 with labels 0 and 1, which it predicts as 0 and 1. Two test cases demonstrate the procedure but are far too few to measure performance. A NumPy version of the procedure, with the tie rules of this page, is short.

import numpy as np

def knn_classify(Z_train, y_train, z, k):
    n = len(y_train)
    if not (isinstance(k, int) and 1 <= k <= n):
        raise ValueError("k must be an integer from 1 to n")
    d2 = ((Z_train - z) ** 2).sum(axis=1)        # squared distances
    order = np.lexsort((np.arange(n), d2))       # by distance, then row index
    labels, counts = np.unique(y_train[order[:k]], return_counts=True)
    return labels[np.argmax(counts)]             # first maximum is the smaller label

X_train = np.array([[0.0], [1.0], [2.0], [3.0], [4.0]])
y_train = np.array([0, 0, 1, 0, 1])
mu = X_train.mean(axis=0)
sd = X_train.std(axis=0)                         # divisor n, training data only
sd[sd == 0] = 1.0
Z_train = (X_train - mu) / sd

X_val, y_val = np.array([[0.2], [1.8], [3.8]]), np.array([0, 0, 1])
for k in (1, 3):
    pred = np.array([knn_classify(Z_train, y_train, (x - mu) / sd, k) for x in X_val])
    print(k, (pred == y_val).mean())             # k = 1 gives 2/3, k = 3 gives 1

Check yourself

Constructed points are A at $(1, 1)$ with class 0, B at $(3, 1)$ with class 1 and C at $(1, 4)$ with class 1, and the query is $(1, 2)$ . Find the squared distances and the predictions for $k = 1$ and $k = 3$ .

Show the answer

The coordinate differences from the query are $(0, 1)$ to A, $(2, -1)$ to B and $(0, 2)$ to C, so the squared distances are $0 + 1 = 1$ , $4 + 1 = 5$ and $0 + 4 = 4$ . The order is A, C, B. With $k = 1$ the neighbor is A and the prediction is class 0. With $k = 3$ all three points vote, two for class 1 and one for class 0, so the prediction is class 1.

For the same points and query, find the prediction for $k = 2$ under the tie rules of this page. Then suppose A, B and C have the numerical targets 8, 20 and 14, and find the two-neighbor regression prediction.

Show the answer

The two nearest points are A and C, at squared distances 1 and 4. Their labels 0 and 1 give one vote each, a vote tie, and the smaller-label rule predicts class 0. A rule that favored the larger label would predict class 1, which is why the rule is part of the method. The regression prediction averages the targets of A and C,

\frac{8 + 14}{2} = 11.

The target 20 of B does not enter, because B is farther from the query than C.

Take the query $(0, 0)$ , the point A at $(2, 0.1)$ with class 0 and the point B at $(0.5, 3)$ with class 1, where the first feature is measured in kilometers. Find the one-neighbor prediction, then express the first feature in meters and predict again. What happens if the second feature is multiplied by 1000 instead, and how does standardization help?

Show the answer

In the original units the squared distances are $4 + 0.01 = 4.01$ to A and $0.25 + 9 = 9.25$ to B, so the prediction is class 0. In meters the first coordinates become 2000 and 500, and the squared distances become $2000^2 + 0.01 = 4{,}000{,}000.01$ to A and $500^2 + 9 = 250{,}009$ to B, so the prediction switches to class 1 although no point moved. Multiplying the second feature by 1000 instead gives $4 + 100^2 = 10{,}004$ to A and $0.25 + 3000^2 = 9{,}000{,}000.25$ to B, and A stays nearest. A change of units can therefore flip a prediction or leave it alone, depending on which feature gains weight. Standardizing each feature with its training mean and standard deviation removes this dependence, because a change of units multiplies the values, the mean and the standard deviation by the same factor, so the standardized inputs stay the same.

K-Nearest Neighbors

Key terms

Euclidean distance

K-nearest neighbors

Majority vote

K-nearest neighbor regression

Tie-breaking rule

Number of neighbors

Check yourself

How this lesson connects

Builds on

Used later in