k-Nearest Neighbors › Formula

This section defines the distance and neighborhood rules used by kNN, then examines neighborhood size, weighting, scaling, and computational cost.

The whole of kNN is built from two questions. First, how similar is the query to each stored example? Second, which examples are similar enough to count? The first question needs a number, a distance. The second needs a rule, a neighborhood. Everything else, including voting and averaging, follows from how we answer those two questions. It makes sense to build them in that order, because the prediction rule only becomes meaningful once we know which points are allowed to speak.

Suppose our training set is a collection of $n$ labeled observations

$$\mathcal{D} = \{(\mathbf{x}_1, y_1), (\mathbf{x}_2, y_2), \dots, (\mathbf{x}_n, y_n)\},$$

where each $\mathbf{x}_i \in \mathbb{R}^p$ is a vector of $p$ features, and $y_i$ is its label or target. The query point is a feature vector $\mathbf{x}_q$ with unknown label. Here $\mathbf{x}$ is bold because it is a vector, and the subscript indexes the training example. In words: $\mathcal{D}$ is the stored dataset, $\mathbf{x}_i$ is the $i$-th training input, and $y_i$ is the corresponding output.

Why start with a distance rather than a probability or a parameter? Because kNN is non-parametric: it does not restrict the regression function or decision boundary to a fixed parametric family. Its predictions compare examples directly, and their usefulness depends on a distance that places inputs with similar targets near one another. A distance is the minimal machinery that turns "these two inputs look alike" into something a computer can sort. Everything we add later is built on this single measurable notion of resemblance.

The Euclidean distance between the query and the $i$-th training point is

$$d(\mathbf{x}_q, \mathbf{x}_i) = \sqrt{\sum_{j=1}^{p} (x_{qj} - x_{ij})^2}$$

where:

• $x_{qj}$: the $j$-th feature of the query point
• $x_{ij}$: the $j$-th feature of the $i$-th training point
• $p$: number of features
• $d(\cdot, \cdot)$: Euclidean distance between two feature vectors

Read it in four moves: take the difference between the query and the training point in each feature $j$; square it; sum over the $p$ features; then take the square root. The squaring does real work: it lets a positive and a negative deviation of the same size count identically, and it lets a few large disagreements outweigh many small ones. The square root returns the total to the original units, so features measured in the same physical unit yield a distance in that unit. With mixed or transformed feature units, the distance is a modeling quantity whose interpretation depends on those scales.

We can also write the same expression compactly using vector notation. Let $\mathbf{d} = \mathbf{x}_q - \mathbf{x}_i$ be the elementwise difference vector. Then

$$d(\mathbf{x}_q, \mathbf{x}_i) = \|\mathbf{x}_q - \mathbf{x}_i\|_2 = \sqrt{\mathbf{d}^\top \mathbf{d}}$$

where:

• $\mathbf{x}_q$: the query feature vector
• $\mathbf{x}_i$: the $i$-th training feature vector
• $\mathbf{d}$: the elementwise difference vector $\mathbf{d} = \mathbf{x}_q - \mathbf{x}_i$
• $\|\cdot\|_2$: Euclidean (L2) norm

Here $\mathbf{d}^\top \mathbf{d}$ is the dot product of $\mathbf{d}$ with itself, which equals $\sum_j d_j^2$. This is the same quantity as before, only now expressed as a matrix multiplication. The vector form is also computationally useful. Stack all $\mathbf{x}_i$ into an $n \times p$ matrix $\mathbf{X}$, and the array of distances becomes $\sqrt{\sum_{j} (\mathbf{x}_{qj} - \mathbf{X}_{:,j})^2}$, where $\mathbf{x}_{qj}$ is the $j$-th feature of the query and $\mathbf{X}_{:,j}$ is the $j$-th column of $\mathbf{X}$. That single vectorized expression is what makes brute-force kNN feasible even for moderately large $n$, and it is exactly the computation the code later performs.

Euclidean distance is only one choice. Minkowski distance generalizes it as

$$d(\mathbf{x}_q, \mathbf{x}_i) = \left(\sum_{j=1}^p |x_{qj} - x_{ij}|^r\right)^{1/r}$$

where:

• $r \ge 1$: the Minkowski order parameter controlling how large feature differences are weighted
• $x_{qj}$: the $j$-th feature of the query point
• $x_{ij}$: the $j$-th feature of the $i$-th training point
• $p$: number of features

Here $r=2$ recovers Euclidean distance and $r=1$ gives Manhattan distance (sum of absolute differences). Any choice of distance defines a slightly different notion of "closeness", and therefore different neighbors. This is the first hint that the distance is a modeling decision, not a neutral measurement. Euclidean distance is a common starting point for comparably scaled continuous features. Manhattan distance adds absolute coordinate differences, while Euclidean distance combines their squares before taking a square root, so a large coordinate discrepancy can have greater relative influence in Euclidean neighborhoods. Both distances remain sensitive to extreme observations, and standardization does not make their neighbor rankings agree. Compare the metric choices under the same validation protocol.

With a distance in hand, every training point carries a single number: how far it sits from the query. The natural next move is to keep the smallest $k$ of those numbers, and that is exactly what defines the neighborhood. Formally, the set of the $k$ nearest training indices is

$$\mathcal{N}_k(\mathbf{x}_q) = \operatorname*{arg\,min}_{S \subset \{1,\dots,n\}, \, |S|=k} \sum_{i \in S} d(\mathbf{x}_q, \mathbf{x}_i),$$

where:

• $\mathcal{N}_k(\mathbf{x}_q)$: the set of indices of the $k$ nearest training points to the query
• $S$: a subset of training indices with $|S|=k$
• $d(\mathbf{x}_q, \mathbf{x}_i)$: distance from the query to the $i$-th training point
• $n$: number of training points

which reads: "the subset $S$ of the $n$ training indices of size $k$ that minimizes the total distance from the query". In practice we never solve this as an optimization; we simply sort the distances and take the first $k$. The $\operatorname{arg\,min}$ notation is a compact description of the sorted order, not a computational instruction.

Two design choices are hidden inside this definition, and both matter:

• Why fix the count $k$ instead of a radius? Because a fixed count lets the neighborhood radius adapt when local density varies. In a dense region, the $k$ nearest points sit within a small ball; in a sparse region, the same $k$ points spread out over a much larger ball. Fixing $k$ therefore lets the neighborhood adapt its radius to local density automatically. A fixed radius would instead yield many neighbors where data is dense and too few, or none, where it is sparse.
• Why rely on locality at all? The locality heuristic is that nearby inputs have similar conditional means or class probabilities in the chosen representation. It motivates local averaging or voting; noise still permits different labels at identical inputs.

The neighborhood depends on the query, the stored training inputs, the metric, and the tie rule. Neighbor lookup is performed for each new query; this is the sense in which kNN is instance-based. There is no fitted global parametric curve to inspect; each prediction requires a local comparison against the stored examples. Ties are the one wrinkle: when two training points are exactly equidistant, the sorted order must break the tie somehow. We return to that in the worked example.

One more design choice deserves a note:

• Distance metric: Euclidean distance suits comparably scaled, roughly symmetric continuous features; Manhattan distance gives large coordinate discrepancies a different relative influence; cosine distance can suit nonzero sparse or text-derived vectors when direction is more relevant than magnitude. The metric defines the neighborhood, so record and reuse it consistently.

Classification votes and regression averagesLink Copied

Once the neighborhood $\mathcal{N}_k$ exists, the prediction is a reduction over it. The reduction depends on whether the target is categorical or numeric, and the distinction deserves its own heading because it changes the interpretation even though the machinery stays the same.

For classification with $C$ classes, each neighbor casts a vote for its own label. The predicted class is the one receiving the most votes:

$$\hat{y}_q = \operatorname*{arg\,max}_{c \in \{1,\dots,C\}} \sum_{i \in \mathcal{N}_k(\mathbf{x}_q)} \mathbb{1}[y_i = c]$$

where:

• $\hat{y}_q$: the predicted class for the query
• $c$: a class label in $\{1, \dots, C\}$
• $y_i$: the label of the $i$-th neighbor
• $\mathbb{1}[\cdot]$: indicator function (1 when the condition is true, 0 otherwise)

We can also divide the count by $k$ to obtain the local class probability $\hat{p}(c \mid \mathbf{x}_q)$:

$$\hat{p}(c \mid \mathbf{x}_q) = \frac{1}{k} \sum_{i \in \mathcal{N}_k(\mathbf{x}_q)} \mathbb{1}[y_i = c].$$

The indicator function $\mathbb{1}[y_i = c]$ takes value $1$ when the $i$-th neighbor's label equals class $c$, and $0$ otherwise. The inner sum therefore counts how many of the $k$ neighbors are of class $c$, and $\operatorname*{arg\,max}_c$ selects the class with the largest count. If we also divide by $k$, the inner expression becomes the local class probability $\hat{p}(c \mid \mathbf{x}_q)$. That probability is not required for the hard label, but it is useful for ranking predictions or for calibration.

For regression, each neighbor contributes its numeric label, and the prediction is the local average:

$$\hat{y}_q = \frac{1}{k} \sum_{i \in \mathcal{N}_k(\mathbf{x}_q)} y_i$$

where:

• $\hat{y}_q$: the predicted numeric value for the query
• $y_i$: the numeric target of the $i$-th neighbor
• $k$: number of neighbors in the neighborhood

The average is the continuous analogue of the majority vote: instead of selecting a discrete class with the most votes, we select the value that minimizes the squared error among the neighbors. That connection is worth remembering: the sum of squared errors to the local neighbors is minimized by their mean. To see why, minimize

$$\mathrm{SSE}(c) = \sum_{i \in \mathcal{N}_k(\mathbf{x}_q)} (y_i - c)^2$$

with respect to the constant $c$. Taking the derivative and setting it to zero,

$$\begin{aligned} \frac{d}{dc}\,\mathrm{SSE}(c) &= \sum_{i \in \mathcal{N}_k(\mathbf{x}_q)} -2(y_i - c) \\ &= -2 \sum_{i \in \mathcal{N}_k(\mathbf{x}_q)} y_i + 2kc \\ &= 0, \end{aligned}$$

so $c = \frac{1}{k}\sum_{i \in \mathcal{N}_k(\mathbf{x}_q)} y_i$, which is exactly the local average above. This is the same logic that underlies ordinary least squares in the earlier OLS chapter. Local averaging is essentially OLS with an implicit neighborhood restriction: one tiny least-squares fit per query, using only the $k$ nearest examples.

Both rules are the same weighted sum in disguise. Stack the labels into a vector $\mathbf{y}$ and let $\mathbf{W}$ be a sparse matrix whose $q$-th row is nonzero only at the indices of the neighborhood of query $q$:

$$\hat{\mathbf{y}} = \mathbf{W} \mathbf{y}, \qquad \mathbf{W}_{qi} = \frac{1}{k} \mathbb{1}[i \in \mathcal{N}_k(\mathbf{x}_q)],$$

where:

• $\hat{\mathbf{y}}$: vector of predictions for all queries
• $\mathbf{y} \in \mathbb{R}^n$: vector of training labels
• $\mathbf{W}$: sparse weight matrix whose $q$-th row selects the neighborhood of query $q$
• $\mathbf{W}_{qi}$: weight of training point $i$ for query $q$
• $k$: number of neighbors in the neighborhood

In regression, $\mathbf{W}$ multiplies the numeric labels; in classification, the same structure applied to one-hot encoded labels reproduces voting exactly. This "weight" view is a useful bridge to the next subsection, where the weights are no longer forced to be equal.

Neighborhood size, weighting, and scalingLink Copied

Three knobs determine how kNN behaves, and they are easiest to understand in the order they were introduced.

The size $k$. At $k = 1$, every prediction equals the label of the single closest training point. The decision boundary can then trace every jagged detail of the training set with low bias and high variance. Small perturbations of the data, or of the query, can flip the prediction to a completely different neighbor. As $k$ grows, voting or averaging uses a larger neighborhood. This can reduce sensitivity to noise while blurring local changes, but boundaries and conditional bias need not change monotonically for every dataset. For independent equal-variance regression errors at fixed training inputs, the noise variance of a uniform $k$-neighbor average is the common error variance divided by $k$. With uniform weights, the extreme $k = n$ makes every query use the full training set: classification predicts a most common class, using the chosen tie rule if needed, and regression predicts the global mean. Distance weights can still produce query-dependent predictions at $k=n$. At $k=n$, the selected neighborhood contains every training example, but distance weights can still concentrate influence near the query. That limit is a useful sanity check: both neighborhood size and weighting affect how strongly nearby examples influence the prediction.

The weighting. Uniform voting treats all $k$ neighbors equally, even when some are much closer than others. Distance weighting lets proximity affect their influence. The weighted prediction is

$$\hat{y}_q = \frac{\sum_{i \in \mathcal{N}_k(\mathbf{x}_q)} w_i y_i}{\sum_{i \in \mathcal{N}_k(\mathbf{x}_q)} w_i}, \qquad w_i = \frac{1}{d(\mathbf{x}_q, \mathbf{x}_i)^2}$$

where:

• $\hat{y}_q$: the distance-weighted prediction for the query
• $y_i$: the label or target of the $i$-th neighbor
• $w_i$: the weight assigned to the $i$-th neighbor, inversely proportional to squared distance
• $d(\mathbf{x}_q, \mathbf{x}_i)$: distance from the query to the $i$-th neighbor

The weights $w_i$ are larger for close neighbors and smaller for distant ones. When all distances are equal, the formula reduces to the simple mean, so weighting is a strict generalization rather than a different algorithm. Closer training points effectively get more votes. This can reduce the influence of more distant targets near a boundary or an unevenly sampled region, but it also concentrates weight on fewer observations and can amplify noise. Whether predictions improve should be checked on held-out data. This chapter uses inverse-squared weights for positive distances; inverse distance is another common choice and is scikit-learn’s built-in weights="distance" convention. For a zero-distance query, we average only the exact matches. For weighted classification, sum the weights separately for each class and select the largest class total.

The scaling. Feature scaling can substantially change kNN neighborhoods when coordinate ranges differ. As described earlier in the standardization chapter, large differences in feature scale can let one coordinate dominate raw distances. If differences in one feature are much larger than those in another, their squared contributions can largely determine the neighbor ranking. Choose scaling so that feature differences have the intended influence on distance, and fit any learned scaling parameters on the training set only. This is the same data leakage discipline described in the validation chapter: computing a mean or standard deviation using the test set and then using those values to scale the training set leaks test-distribution information into preprocessing. The resulting score no longer evaluates a procedure fitted solely on the training data; the direction of the score difference is not guaranteed in every realized split. Any chosen scaling transform becomes part of the distance definition and must also be applied to future queries.

The cost of kNN has two faces: computation and geometry. They are easy to confuse.

The computational face is straightforward. Computing all brute-force distances requires $O(np)$ operations per query. Our full-sort implementation adds $O(n\log n)$ neighbor-ordering work per query, giving $O(mn(p+\log n))$ work for $m$ queries, before vote aggregation. A partial-selection implementation can avoid sorting all $n$ distances. This repeated distance calculation and sorting make our implementation expensive at inference. Our brute-force implementation scans every stored training point for each query. Exact or approximate search indexes can reduce this search work. Dimensionality reduction can reduce the work per distance, but brute-force prediction still scans the transformed training set. Exact trees trade construction and storage costs for query pruning while preserving the neighbor set. Approximate search can change that set; dimensionality reduction changes the feature representation and can change its distances. Evaluate suitability from measured storage, index-building, and query costs under a representative workload.

The geometric face is the curse of dimensionality, and it is more fundamental. Under the independent centered Gaussian feature-difference model below, with fixed variance $\sigma^2>0$, query-to-training distances concentrate in relative terms as $p$ grows. To see the effect quantitatively, consider the squared Euclidean distance between a query and a training point,

$$\|\mathbf{x}_q - \mathbf{x}_i\|_2^2 = \sum_{j=1}^{p} (x_{qj} - x_{ij})^2$$

where:

• $x_{qj}$: the $j$-th feature of the query point
• $x_{ij}$: the $j$-th feature of the $i$-th training point
• $p$: number of features
• $\|\cdot\|_2^2$: squared Euclidean (L2) norm

If the feature differences $x_{qj} - x_{ij}$ are independent centered Gaussian variables with variance $\sigma^2$, then the sum of their $p$ squares has mean $p\sigma^2$ and variance $2p\sigma^4$. The standard deviation of the squared distance is therefore $\sqrt{2p}\sigma^2$, which grows more slowly than the mean $p\sigma^2$. Their ratio,

$$\frac{\sqrt{2p}\sigma^2}{p\sigma^2} = \frac{\sqrt{2}}{\sqrt{p}},$$

shrinks as $1/\sqrt{p}$, so the squared distance concentrates around its mean as $p$ grows. Taking the square root carries this concentration over to the distances themselves. For a fixed finite number of training points under this independent Gaussian model, the nearest-to-farthest distance ratio approaches one in probability as $p$ grows. Correlated features, a low-dimensional representation, or a training-set size that grows with $p$ require separate analysis.

The concentration argument can be checked numerically. The next simulation draws independent standard normal training and query points, computes the nearest-to-farthest distance ratio for each query, and averages those ratios across queries at each dimension.

Practically, this means:

• In high dimensions, kNN may appear to have many "close" neighbors that are far away, causing predictions to be dominated by seemingly unrelated points.
• Feature aggregation does not rescue the situation unless the resulting representation preserves information about the target. Extra noise coordinates can weaken the relative distance contrast.
• In high-dimensional settings, kNN is often combined with feature selection or with a learned low-dimensional representation before prediction.

The kNN predictor is closely related to a classical non-parametric estimator. For a concrete regression result, suppose the training observations are iid, the feature domain is bounded, and $Y=f(X)+\epsilon$ with $f$ Lipschitz with constant $L$. Conditional on the training inputs, assume the errors are independent, have mean zero, and have common finite variance $\sigma^2$. Conditional on the training inputs, the uniform kNN average has noise variance $\sigma^2/k$ and absolute bias bounded by $L R_k(x)$, where $R_k(x)$ is the distance to the $k$-th neighbor. At a query in the distributional support, $k\to\infty$ and $k/n\to0$ make its mean squared estimation error tend to zero. With the additional local mass condition $P(\|X-x\|\le r)\ge c r^p$ for a positive constant $c$ and sufficiently small $r$, a representative bound is $O((k/n)^{2/p}+1/k)$; balancing the terms gives $O(n^{-2/(p+2)})$. This regularity-based bound is slower than the $O(n^{-1})$ estimation-error rate of regular, correctly specified finite-dimensional parametric models; it is not a claim that every individual kNN problem converges strictly more slowly. For classification, Cover and Hart’s large-sample result bounds the error of the one-nearest-neighbor rule by twice the Bayes error under their sampling and regularity conditions. The Bayes error is a property of the underlying distribution, not of the fitted classifier. This bound does not imply that another classifier must outperform nearest neighbors.

The relationship between uniform and weighted kNN also has a precise form. Under kernel weighting, the local estimator is a Nadaraya-Watson-type kernel regression estimator, and the weights satisfy $\sum_i w_i = 1$ when normalized. Nonnegative weights with a positive total, normalized to sum to one, keep regression predictions within the convex hull of the neighbor targets. Dividing all class-vote totals by that same positive total leaves their ranking unchanged. These connections show that kNN is a non-parametric estimator with asymptotic results under stated sampling and regularity conditions.