k-Nearest Neighbors

Imagine you move into a new neighborhood and want to guess whether your street is likely to have quiet or lively evenings. You would not rely on a national average; you would ask your neighbors. If most of the five houses on your block are quiet at night, you predict your own evenings will be quiet too. That single act, looking at the people closest to you and letting them vote, illustrates the basic idea of the k-nearest neighbors (kNN) algorithm. No equation is fit, no coefficients are learned, and no parametric shape is imposed on the data. Instead, the training set itself is the model, and predictions are made by inspecting which training points are most similar to the query we care about.

Standard models such as the linear regression and logistic regression chapters we studied previously compress the training data into a small set of parameters. kNN takes the opposite stance. It is a non-parametric, instance-based method. Every prediction is anchored to concrete examples we have already observed. The "learning" phase is essentially storing the data. The real work happens at prediction time when we compute distances. This makes kNN flexible, capable of tracing arbitrarily curved decision boundaries, but also demanding in terms of memory, distance calculations, and, as we will see, the quality of our feature space.

This chapter builds kNN from first principles. We start with a clear definition of a distance and how a local prediction rule turns neighbors into an answer. We then work through classification by majority vote and regression by local averaging, examine how neighborhood size and feature scaling reshape the predictions, and quantify why high-dimensional spaces break the intuition that "nearby" means "similar." Along the way, we implement brute-force kNN in NumPy, compare several values of $k$ on noisy data, and confirm our results against scikit-learn.

A short clarification before we start. Nearest neighbors in this chapter always means supervised prediction, classifying or regressing using labeled training points. This is a very different idea from k-means clustering (a chapter we will encounter in the unsupervised part of the book), which is also "center-based" and uses distances but has no labels to reason about. Keeping the two separate avoids a common confusion.

One advantage of kNN is that it can approximate essentially any decision boundary without requiring an explicit functional form. A small neighborhood can follow local changes without fitting a global curve. Whether its prediction is useful depends on the available observations, the metric, and the noise near the query. Use kNN as a "sanity check" baseline: compare its held-out performance with a more elaborate model under the same evaluation protocol. A similar score is evidence about that comparison, rather than proof that both models capture the same structure.

A second advantage is simplicity and interpretability of the prediction. Given a query point, we can literally list the training points that voted or contributed to the average. For applications where explainability matters, say, showing a clinician the five training patients most similar to a new patient, kNN offers a transparent, case-based rationale for every decision. No hidden coefficients need to be decoded.

Finally, kNN is naturally suited to multi-class problems and to problems where we expect local structure. The same counting rule extends from two classes to ten: count how many neighbors belong to each class and apply the chosen tie rule. It requires no separate parametric distribution for each class. This contrasts with parametric approaches that may need special treatment or new estimation procedures for multi-class settings.

The same flexibility that makes kNN effective also creates weaknesses. First, kNN does not tell us which features matter. If a feature is irrelevant but has a large numeric range, its contribution to the distance can dominate the calculation and produce neighborhoods that are essentially determined by noise. Choose feature scales deliberately, as discussed in the earlier standardization chapter. Unintended unit differences can reshape neighborhoods even when the underlying observations are unchanged.

Second, kNN is computationally expensive at prediction time. The training set must be stored. With brute-force search, each query computes the distance to every stored point, a cost that grows linearly with the number of training samples and the number of features. For a small dataset this is trivial; for millions of points in dozens of dimensions, brute-force kNN can become the bottleneck. Exact spatial indexes can reduce distance calculations while preserving the nearest neighbors, at the cost of building and storing the index, plus tuning it. Approximate search introduces a separate speed–recall tradeoff and may return a different neighbor set.

Third, kNN can suffer from the curse of dimensionality. With many noise features, the relative contrast between nearest and farthest distances can shrink, making it harder to identify a useful local neighborhood. We quantify this under an independent Gaussian feature model later in the chapter. This motivates using informative features or a suitable low-dimensional representation; high dimension alone does not determine how kNN will perform.

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

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

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

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

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

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:

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)$:

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:

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

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

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$:

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

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,

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,

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.

The clearest way to understand kNN is to see its decision boundary change with $k$ and with feature scaling. We generate a two-dimensional, mildly noisy classification problem and draw the decision region for $k = 1$, $k = 5$, and $k = 25$ on a grid of query points. The following cell defines the majority-vote classifier before computing those decision regions.

:::

In the right figure, the decision regions form narrow vertical bands. Multiplying the first feature by 50 multiplies its own squared-distance contribution by $50^2 = 2500$, while leaving the second feature unchanged. On this sample, neighbors are then chosen largely by similarity in the first feature. The distance depends on the scales on which features are measured. Use scaling when needed to prevent units from imposing unintended feature weights.

These figure groups show the behavior of $k$ and of feature scaling. The implementation below turns the same mechanics into auditable NumPy code and compares it with scikit-learn.

Before trusting code, it is worth carrying out one prediction entirely by hand. A single worked example with $k=3$ confirms that every operation (distance, ranking, tie-breaking, voting, averaging) is exactly what we think it is, and it exposes the one place where the rules leave us a choice.

Suppose a two-dimensional binary classification training set contains five points:

The query is $\mathbf{x}_q = (2.5, 2.5)$. Class-0 points sit near the origin, and class-1 points form a diagonal ridge going out toward $(5, 5)$, so the query lies between the two groups and the class votes are close. That is deliberate: an ambiguous query is exactly where the mechanics become visible.

Step 1: compute Euclidean distances to every training point.

For $\mathbf{x}_1$:

For $\mathbf{x}_2$:

For $\mathbf{x}_3$:

For $\mathbf{x}_4$:

For $\mathbf{x}_5$:

The distances already show the ranking: $\mathbf{x}_2$ and $\mathbf{x}_3$ are closest and exactly tied, $\mathbf{x}_1$ and $\mathbf{x}_4$ form the next tier, and $\mathbf{x}_5$ is farthest. How we resolve the ties will decide which points enter the neighborhood, so it is worth handling them explicitly.

Step 2: sort the distances in increasing order:

Notice that $\mathbf{x}_2$ and $\mathbf{x}_3$ are exactly tied at $\sqrt{0.5}$, and $\mathbf{x}_1$ and $\mathbf{x}_4$ are tied at $\sqrt{4.5}$. Duplicate inputs or rounded and discrete features can produce exact ties in any dimension. This hand-designed coordinate set makes their effect visible. When they occur, we need a deterministic rule. We break equal-distance ties by training-row order, using np.argsort(..., kind="stable") in the implementation. If a class vote is tied, our classifiers choose the smallest class label. A different distance-tie rule can change the selected neighbor at the cutoff and therefore change the prediction.

Step 3: select the $k=3$ nearest neighbors. The first three sorted indices are $\{2, 3, 1\}$. Their labels are $y_2 = 0$, $y_3 = 1$, and $y_1 = 0$.

Step 4: count votes. Class 0 receives two votes and class 1 receives one vote. The majority class is therefore class 0, and our kNN prediction is $\hat{y}_q = 0$.

We can now check what happens with weighted voting. Suppose we use $w_i = 1/d_i^2$. The weights for the three neighbors are:

where:

• $w_i$: weight assigned to neighbor $i$, equal to the reciprocal of its squared distance
• $d_i$: Euclidean distance from the query to neighbor $i$

Class 0 weight is $w_2 + w_1 \approx 2.222$; class 1 weight is $w_3 \approx 2$. Weighted voting still predicts class 0, but the margin is now narrow. Uniform voting predicted class 0 by a 2-to-1 vote; weighted voting predicts it by 2.22 versus 2.00. This illustrates how sensitive predictions near the decision boundary can be: the same neighbor set can carry very different levels of confidence depending on how much each neighbor is allowed to count.

Step 5 (regression analogue). If the same five training points had numeric labels $y = (0, 0, 1, 1, 1)$ as targets for a regression task, uniform kNN with $k=3$ would produce the local average

This is the same set of neighbors, but now the answer is a continuous value rather than a class, and each observed label is contributing equally to the prediction. The result sits between the class-0 and class-1 values, which is what a local average should do. The uniform average is, in effect, the least-squares minimizer over the local neighborhood, the same justification used in the OLS chapter, restricted here to three nearby examples.

We now turn the formulas into code using only NumPy primitives, then compare the result with scikit-learn on the same synthetic data. Writing it by hand makes every step auditable: distance computation, sorting, and voting or averaging. It is not intended to replace scikit-learn. Compare results with the same distance, weighting, and tie conventions, allowing for numerical tolerance. A remaining discrepancy calls for inspecting both implementations; a different tie rule can produce a different valid result.

We will deliberately use a one-dimensional, noisy regression problem first, because it is the easiest setting to visualize and to reason about. Then we build a classification example. The examples below also use explicit NumPy generator seeds.

This section introduces the following fitting and prediction methods, plus methods for inspecting neighbors:

• fit(X, y): Stores the training examples and labels and may build a search index; neighbor lookup and prediction happen for each query. The kneighbors method inspects the selected neighbors separately from prediction.
• predict(X): Returns a class label or numeric prediction for each query in X, using the configured voting or averaging weights.
• predict_proba(X): Returns class-support estimates normalized to sum to one (classification only). Uniform weights give neighbor-count fractions; distance weights give normalized weighted totals. Assess their calibration on held-out observations.
• kneighbors(X): Returns the distances and indices of the $k$ nearest training points for each query, useful for inspecting neighborhoods and identifying queries with weak local support.

Below are some of the main parameters that affect how kNN works and performs:

• n_neighbors / $k$: Number of neighbors used for each prediction. Small values can follow individual observations closely and can be sensitive to changes in them. Larger values average a broader neighborhood and can smooth away local signal. The effect on bias and variance depends on the data and target, and on the weights. Choose from a validation grid such as $\{1, 3, 5, 9, 15, 25\}$, evaluated under the same protocol for all compared models.
• weights: Uniform weights treat all neighbors equally. Distance weighting lets closer neighbors count more; this chapter uses inverse-squared distance, while scikit-learn's weights="distance" uses inverse distance.
• metric / p: Distance used to define the neighborhood. Euclidean (metric="minkowski", p=2) is the default; Manhattan (p=1) sums absolute coordinate differences and can select different neighbors.
• algorithm: Search strategy. "auto" picks a strategy in scikit-learn; the NumPy code scans and sorts all training distances.

This section covers where kNN is useful, how to tune and preprocess it, common pitfalls, and deployment considerations.

kNN is a reasonable first choice when the data is low- to moderate-dimensional, the training set fits comfortably in memory, and there is reason to believe that inputs close in feature space tend to share similar targets. In tabular problems with a few dozen well-chosen features it supplies a non-parametric benchmark that imposes almost no structural assumptions on the relationship. Running a quick baseline (standardized features, Euclidean distance, and a small grid of $k$ values evaluated by cross-validation) indicates how much local structure the problem contains. The comparison helps decide whether a more elaborate model offers enough predictive benefit for its operational cost; latency and interpretability requirements also matter, as do uncertainty requirements.

The method is also well matched to settings where a case-based explanation is acceptable, or even preferable. Recommender interfaces that display "customers similar to you", retrieval systems that retrieve the closest labeled items, and diagnostic tools that present the most similar prior cases all align with the way kNN reasons. The prediction is a summary over identifiable training examples rather than a coefficient vector, so the rationale can be shown directly without post-hoc approximation. The same symmetry over classes makes the extension to many classes trivial, which is convenient in problems such as document or product categorization where the label set is large.

The converse cases are equally clear. kNN is a poor fit when a per-feature effect estimate is required, when prediction latency must be very low at large $n$, or when the feature space contains many uninformative dimensions and no useful reduction is available. In those situations the flexibility of the method is purchased at a price the application cannot pay, and a parametric or linear model is often the better starting point.

Tune the neighborhood size under the evaluation protocol. For uniform binary-class votes, odd values of $k$ avoid tied class counts; distance-weighted totals can still tie. A grid such as $k \in \{1, 3, 5, 9, 15, 25\}$ evaluated with stratified cross-validation spans the range from flexible to smooth. The heuristic $k \approx \sqrt{n}$ is a serviceable starting point but should not substitute for validation, and the selected $k$ should be re-checked whenever the training set size changes substantially. For regression the same grid logic applies, and it is worth evaluating both weights="uniform" and weights="distance", because weighting changes the balance between bias and variance while reusing the selected neighbors.

The metric deserves a deliberate rather than default choice. Euclidean distance suits continuous features that are comparably scaled and roughly symmetric in their error structure; Manhattan distance changes the relative influence of large coordinate discrepancies; validate whether that improves predictions when features have heavy tails or outliers. For nonzero count or text vectors, consider cosine distance when direction should matter more than magnitude. When all vectors have Euclidean length one, cosine and Euclidean distances give the same neighbor ranking. Whatever the choice, the same metric must be applied when neighbors are selected in training and at prediction time, and the choice should be recorded alongside the fitted model.

Evaluation protocol matters as much as the hyperparameter grid. Use stratified folds for classification so that each fold preserves the class proportions, and repeat the split a few times when the dataset is small, because kNN predictions are sensitive to which points happen to be held out. For regression, report at least two error measures, because RMSE squares residuals before averaging and taking a square root, whereas MAE averages their absolute magnitudes. It also helps to record the neighbor distances themselves: a large distance to the $k$-th neighbor signals weak local support in the chosen feature units, even when the query lies inside the observed input domain, and that information is invisible in an aggregate score.

The scratch implementation requires numeric, dense feature arrays. kNN estimators such as scikit-learn’s also support sparse input with compatible distances, using brute-force search for sparse data. Categorical variables must be encoded before any distance is meaningful: one-hot encoding for nominal categories, ordinal or otherwise ordered encodings for ranked ones, while accounting for how the indicator columns change the metric. Under squared Euclidean distance, matching categories add zero through those columns; differing categories can add positive terms. Existing numeric squared-difference terms remain unchanged unless rescaled, while their relative influence depends on the chosen representation. Missing values are not accommodated by the standard distance formulas. For these dense Euclidean calculations, first resolve the missing entries, for example by imputing continuous features with training medians and categorical features with training modes before encoding. A missingness indicator can be added alongside imputation, but it does not replace the missing numeric entries. Learn the imputation statistics on the training portion only.

The choice of scaling transform should match the shape of each feature. Standardization is appropriate when features are roughly symmetric and unbounded; min-max scaling is natural when values are known to lie in a bounded interval; robust scaling based on the median and interquartile range is preferable when outliers are present but should not be discarded. Whatever the transform, it defines part of the distance and therefore part of the model, which is why it must be stored and reapplied unchanged to every future query.

Outliers and noise require attention because squared differences let a single extreme value dominate a distance. If extreme observations are distorting neighborhoods, compare justified clipping or winsorization and alternative metrics on held-out data; Manhattan distance changes coordinate influence but does not make the predictor immune to outliers. Feature relevance also matters. When uninformative features distort neighborhoods, compare feature selection or supervised dimensionality reduction with $k$ tuning under the same validation protocol.

A preprocessing pitfall is computing scaling statistics on the full dataset before splitting, which leaks information from the evaluation set into the distance definition. The fix is structural rather than numerical: wrap the scaler and the estimator in a single pipeline so that each cross-validation fold recomputes its mean and standard deviation from its own training portion, and refit the scaler on the full training set only after the model configuration is fixed.

A second cluster of problems concerns the neighborhood itself. Even values of $k$ in binary classification invite tied votes whose resolution is arbitrary; exact distance ties are resolved by sort order, which differs across implementations; and small $k$ can make predictions sensitive to individual noisy observations. At distinct training inputs, 1NN reproduces the observed labels when those inputs are queried. It is also easy to over-read local class-support estimates. With uniform weights and $k=5$, the neighbor-count fractions can only take the values $0, 0.2, \dots, 1$; distance-weighted estimates are not restricted to that grid. These are probability estimates whose calibration needs evaluation on held-out data, rather than validated confidence levels. Additional calibration may help, but it is not automatically required for every dataset.

A third pitfall is assuming that kNN is immune to irrelevant features because it makes no distributional assumptions. The distance calculation gives each included coordinate a role regardless of its predictive relevance. An uninformative feature with a large numeric scale can dominate the metric and change which neighbors are selected. Similarly, comparing kNN against a tuned alternative on a single split can understate or overstate the gap; the baseline is only useful if it is evaluated under the same protocol as the competitor.

Distance computation costs $O(np)$ per query; our full-sort implementation additionally uses $O(n\log n)$ ordering work. Storing the training matrix requires $O(np)$ floating-point values. Exact KD-tree and ball-tree indexes can reduce query work by pruning regions that cannot improve the neighbor set. The scikit-learn guide uses roughly 20 dimensions as a caution for KD-tree performance, rather than a universal cutoff: tree efficiency also depends on intrinsic structure, the metric, $k$, leaf size, and the number of queries. Ball trees can benefit from structured data even in higher ambient dimensions. Benchmark index construction and representative queries against brute force; the chapter establishes no sample-size crossover at $n=10^5$.

Batch prediction introduces a memory concern: our broadcasting code first forms an $m \times n \times p$ difference tensor, then an $m \times n$ distance matrix and neighbor-index array. The difference tensor alone uses $O(mnp)$ memory and can exceed available RAM before arithmetic becomes slow. Processing queries in blocks limits the size of the query-dependent working arrays without changing each query's prediction when the training data and prediction settings stay fixed. Choose the block size using the peak memory of the block-by-training-by-feature difference and square arrays, the block-by-training distance and sorting-index arrays, and other live arrays; leave headroom for the stored training set and other process memory. When the training set is static, a search index can be built once and reused. Sorted neighbor indices depend on the query. Reuse an evaluated query's ordering for that same query, or for a new query only when a bound or region check verifies that the ordering is unchanged; otherwise search again. When the training set changes frequently, rebuild time becomes part of the operational budget.

When exact search is too slow, approximate nearest-neighbor methods offer a tunable tradeoff between search work and neighbor recall; measure both recall and downstream prediction quality. Dimensionality reduction, for instance with PCA, can reduce distance-computation cost. It may help accuracy when it removes irrelevant directions, but PCA preserves input variance rather than target information, so validate the representation and its dimension. Hardware acceleration of the distance computation helps as well, but it does not address the geometric problem that motivates the reduction.

Report metrics against a trivial baseline rather than in isolation: the majority-class rate for classification and the global mean for regression indicate what a model that ignores the features would achieve. Balanced accuracy, per-class F1, or the confusion matrix are more informative than overall accuracy when classes are imbalanced, while RMSE and MAE together characterize regression error. Learning curves compare validation error across training-set sizes under the same protocol. A descending curve suggests that more observations may help in that setting; weigh the observed gain and labeling cost against other improvements rather than treating the curve as a guarantee.

Deployment is dominated by the fact that the fitted model is the training matrix itself, together with the scaler, metric, chosen $k$, weighting, and tie rules. That artifact can be large, so versioning and storage planning deserve early attention, and any change to the stored examples changes the model. Neighbor search can dominate prediction latency. Benchmark it alongside preprocessing and aggregation, and include data transfer; keeping a reusable index in memory can avoid repeated loading or construction. Exact repeated-query results can be cached for a fixed model. Reusing a result for a nearby query is an approximation: even nearby queries can have different neighbors or predictions, so assess that error before using such a cache.

Because there are no coefficients to inspect, monitoring has to work indirectly. Tracking neighbor distances, for example the mean distance to the $k$-th neighbor, can flag queries with weaker local support in the chosen metric. Comparing feature distributions can also flag input shifts. Neither check guarantees that predictive degradation will be detected before labels arrive, and unchanged input distributions do not rule out a changed relationship with the target. When new labels arrive, refresh the stored examples and re-validate $k$ and the scaling transform, since both were chosen for a training set that no longer exists.

k-Nearest Neighbors is a non-parametric, instance-based method where predictions are computed only at query time. The model retains the training examples and prediction configuration. Our brute-force implementation computes distances to all training points, selects the $k$ nearest, and produces a prediction by majority vote (classification) or local average (regression); an exact search index can retrieve the same neighbors with less distance work. This local prediction rule explains both its flexibility, as it can trace arbitrarily curved decision boundaries, and its brittle dependence on feature scaling, distance choice, and neighborhood size.

We built the mechanism from first principles. Here are the central quantities again, with their symbols defined. The Euclidean distance between a query and a training point is the square root of the sum of squared feature differences; it is the same quantity as the norm of the difference vector, and it can be computed efficiently for all training points at once. Once we have the distances, the k-nearest set is defined by sorting and taking the first $k$; the prediction is a reduction over that neighborhood. The neighborhood size $k$ acts as a bias-variance dial, and kernel weighting lets closer neighbors count more heavily without changing the underlying rule. Feature scales determine the relative contribution of each coordinate to distance. Transform them when their raw units would otherwise impose unintended weights.

We also examined distance concentration under the stated independent Gaussian feature model: as the number of noise features grows in that experiment, nearest and farthest distances become closer in relative terms. This is a reason to examine feature relevance and local support, rather than a claim that every high-dimensional dataset lacks useful neighbors. The worked example showed every step, from distances and sorting through ties, majority vote, weighted vote, and the regression average, in a hand-computable case. Our NumPy implementation, verified against scikit-learn to floating-point precision, demonstrated that the algorithm is nothing more than distance and reduction once written out. With kNN in hand, we turn next to Naive Bayes, which models class-conditional feature distributions and combines them with Bayes’ theorem under a conditional independence assumption.

Ready to test your understanding? Take this quick quiz to reinforce what you've learned about k-nearest neighbors, from distance and voting rules to scaling, the curse of dimensionality, and class-support estimates.