Introduction to k-Nearest Neighbors

The k-nearest neighbors algorithm, usually abbreviated kNN, makes predictions from a simple premise: observations that are close in a meaningful feature space should tend to have similar outputs. To classify a new point, find the \(k\) closest labeled observations and let them vote. To predict a numerical value, average the targets of those same neighbors.

This simplicity is deceptive. kNN has almost no training phase, but every important modeling decision moves into the geometry: which features are used, how they are scaled, what distance means, how many neighbors count, and how ties are resolved. Once those choices are explicit, classification, regression, local probability estimates, and the algorithm's characteristic strengths and failures all follow from one neighborhood definition.

From Data to a Neighborhood

Let the training set contain \(m\) observations,

\[ \mathcal D=\{(\mathbf x_i,y_i)\}_{i=1}^{m}, \qquad \mathbf x_i\in\mathbb R^n. \]

Each feature vector \(\mathbf x_i\) represents one observation by \(n\) numerical coordinates. The target \(y_i\) is a class label for classification or a real number for regression. Given a query \(\mathbf x\), kNN begins by assigning a dissimilarity to every training point.

The usual choice is the Euclidean distance

\[ d(\mathbf x,\mathbf x_i) =\lVert\mathbf x-\mathbf x_i\rVert_2 =\sqrt{\sum_{j=1}^{n}(x_j-x_{i,j})^2}. \]

Sorting these distances gives indices \(i_{(1)},i_{(2)},\ldots,i_{(m)}\) such that

\[ d(\mathbf x,\mathbf x_{i_{(1)}}) \le d(\mathbf x,\mathbf x_{i_{(2)}}) \le\cdots\le d(\mathbf x,\mathbf x_{i_{(m)}}). \]

The set of the first \(k\) observations is the k-neighborhood of \(\mathbf x\):

\[ N_k(\mathbf x)=\{i_{(1)},\ldots,i_{(k)}\}. \]

The square root may be omitted when only the ranking is needed. Squaring is strictly increasing on nonnegative numbers, so \(d^2\) and \(d\) order all candidates identically. The squared Euclidean quantity itself is not a metric, however: it does not generally satisfy the triangle inequality. This distinction matters when an indexing method or mathematical claim specifically requires a metric.

Classification by Local Vote

Suppose the class labels belong to a finite set \(\mathcal C\). For every class \(c\), count how many of the selected neighbors carry that label:

\[ n_c(\mathbf x)=\sum_{i\in N_k(\mathbf x)}\mathbf 1(y_i=c), \]

where \(\mathbf 1(\cdot)\) equals one when its condition is true and zero otherwise. The kNN classifier chooses

\[ \boxed{\hat y(\mathbf x)=\operatorname*{arg\,max}_{c\in\mathcal C}n_c(\mathbf x)}. \]

Dividing each count by \(k\) gives a local class-frequency estimate,

\[ \boxed{ \widehat P(Y=c\mid\mathbf X=\mathbf x) =\frac{1}{k}\sum_{i\in N_k(\mathbf x)}\mathbf 1(y_i=c) }. \]

The predicted class is the one with the largest estimated local probability. These fractions are useful scores, but they are quantized in steps of \(1/k\) and need not be calibrated probabilities, particularly when the sample is small, classes are imbalanced, or neighbor selection is biased by feature scaling.

The dashed circle expands just far enough to contain five observations. Three filled neighbors outvote two open neighbors, so the query is assigned to class A.

Regression by Local Averaging

When \(y_i\in\mathbb R\), voting becomes averaging. The unweighted kNN regression estimate is

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

This is a local constant model: around every query, kNN approximates the unknown response function by one number. The fitted function is piecewise constant because the selected neighbor set changes only when the query crosses a boundary at which two training points exchange rank.

Classification and regression are therefore the same construction with different summaries. Classification averages one-hot class indicators; regression averages numerical targets.

A Complete Classification Example

Consider six labeled points and the query \(\mathbf x=(3,2)^\mathsf T\):

For \(k=1\), points 2 and 4 are tied at distance one but have different classes. A deterministic implementation therefore needs a documented tie rule. For \(k=3\), both distance-one points enter together with either of the two class-A points at distance squared two, so class A wins by two votes to one. For \(k=5\), the choice between the two class-B points tied at distance squared five does not change the result: three A points and two B points vote, so

\[ \widehat P(A\mid\mathbf x)=\frac35, \qquad \widehat P(B\mid\mathbf x)=\frac25, \qquad \hat y=A. \]

This example exposes two separate ties. Equal distances determine which points enter the neighborhood; equal class counts determine which label wins after selection. Stable input order is reproducible but arbitrary. Better policies include choosing the class with smaller total neighbor distance or reporting that the prediction is ambiguous.

Choosing the Number of Neighbors

The parameter \(k\) controls the scale at which the data is viewed. With \(k=1\), every training point owns a region and determines the prediction throughout that region. The classifier can reproduce the training labels exactly when no duplicate feature vectors disagree, but its boundary reacts strongly to noise. Increasing \(k\) averages over a wider neighborhood, smoothing isolated irregularities while potentially erasing small but genuine structures.

This is the usual bias-variance trade-off:

• Small \(k\): low smoothing bias, high sensitivity to individual observations.
• Large \(k\): smoother and more stable predictions, but increased local bias.
• \(k=m\): every query receives the global majority class or global target mean, so all spatial information is lost.

A small neighborhood follows local fluctuations and produces an irregular boundary. A larger neighborhood smooths the same sample, trading variance for bias.

There is no universally correct value. Choose \(k\) using validation data or cross-validation and evaluate the metric that matches the task. Accuracy can conceal poor minority-class behavior; precision, recall, F-scores, or class-specific error rates may be more informative. For regression, common choices include mean squared error and mean absolute error. Selection must occur inside each training fold so that validation labels do not influence the chosen \(k\).

Feature Scaling Defines the Geometry

Euclidean distance compares numerical coordinate differences. If one feature is measured in meters and another in millimeters, or one ranges from 0 to 1 while another ranges from 0 to 100000, the larger numerical scale can dominate every neighbor search even when it is less informative.

A common correction is standardization. For feature \(j\), compute its training-set mean \(\mu_j\) and standard deviation \(s_j\), then transform

\[ z_j=\frac{x_j-\mu_j}{s_j}. \]

The same training-set parameters must transform validation and future query points. Computing them from the full dataset before cross-validation leaks information across folds. Robust scaling by a median and interquartile range can be preferable when features contain severe outliers.

Scaling is not merely numerical housekeeping; it encodes what one unit of separation means in each direction. Feature selection, transformation, and learned distance metrics can matter more than the neighbor search itself.

Other Distance Functions

The Minkowski family is

\[ d_p(\mathbf x,\mathbf z) =\left(\sum_{j=1}^{n}|x_j-z_j|^p\right)^{1/p}, \qquad p\ge1. \]

• \(p=1\) gives Manhattan distance, which sums absolute coordinate differences.
• \(p=2\) gives Euclidean distance.
• The limit \(p\to\infty\) gives Chebyshev distance, the largest coordinate difference.

Different data types require different notions of proximity. Hamming distance counts mismatches in categorical or binary coordinates. Cosine dissimilarity compares vector direction and is often useful for normalized text or embedding vectors. Mahalanobis distance accounts for correlated scales through a positive-definite matrix \(M\):

\[ d_M(\mathbf x,\mathbf z) =\sqrt{(\mathbf x-\mathbf z)^\mathsf T M(\mathbf x-\mathbf z)}. \]

A distance must match the semantics of the features. Encoding unordered categories as consecutive integers and then applying Euclidean distance invents an order and spacing that the original categories did not possess.

Distance-Weighted Neighbors

An observation just beside the query usually deserves more influence than one near the edge of the neighborhood. Assign nonnegative weights \(w_i(\mathbf x)\), for example

\[ w_i(\mathbf x)=\frac{1}{(d(\mathbf x,\mathbf x_i)+\varepsilon)^q}, \qquad q>0, \]

and replace counts or means by weighted versions:

\[ \hat y_{\mathrm{class}}(\mathbf x) =\operatorname*{arg\,max}_{c\in\mathcal C} \sum_{i\in N_k(\mathbf x)}w_i(\mathbf x)\mathbf 1(y_i=c), \]

\[ \hat y_{\mathrm{reg}}(\mathbf x) =\frac{\sum_{i\in N_k(\mathbf x)}w_i(\mathbf x)y_i} {\sum_{i\in N_k(\mathbf x)}w_i(\mathbf x)}. \]

The \(\varepsilon\) avoids division by zero, but exact matches deserve explicit handling. If one or more training observations have zero distance to the query, predict from those observations alone. Conflicting labels at identical feature vectors represent irreducible ambiguity in the available features, not a search problem.

Class Imbalance and Unequal Costs

A local majority vote tends to favor a globally common class because dense regions contribute more candidate neighbors. Increasing \(k\) can strengthen this effect. Possible responses include class-weighted voting, stratified evaluation, resampling inside the training fold, or choosing a class from estimated local probabilities using application-specific error costs instead of taking the largest count automatically.

These interventions answer different questions. Class weighting changes the decision rule; resampling changes the empirical neighborhood density; adjusting a probability threshold changes how estimated risk becomes an action. Their effects should not be treated as interchangeable.

The Curse of Dimensionality

Locality becomes difficult in high dimensions. If points are spread through a unit \(n\)-dimensional cube, a neighborhood containing a fixed fraction \(f\) of uniformly distributed data needs a characteristic linear scale proportional to \(f^{1/n}\). For \(f=0.01\), this scale is \(0.1\) in two dimensions but about \(0.794\) in twenty dimensions. A region containing only one percent of the volume is no longer narrow in each coordinate.

Distances also tend to become less contrasted as irrelevant dimensions accumulate. The nearest observation may then be only marginally closer than a typical observation, undermining the assumption that the selected points are genuinely local. Feature selection, dimensionality reduction, domain-specific representations, and much larger samples can help; simply changing the search data structure cannot repair uninformative geometry.

Training and Query Cost

kNN is often called a lazy learner. Training largely consists of storing \(m\) feature vectors, requiring \(O(mn)\) memory. A direct query computes all distances in \(O(mn)\) time. Selecting the smallest \(k\) values can be done in \(O(m)\) expected time or maintained with a size-\(k\) heap in \(O(m\log k)\) time; fully sorting all \(m\) distances costs \(O(m\log m)\) and is unnecessary.

Spatial indexes such as k-d trees or ball trees can prune exact searches in low and moderate dimensions. Approximate nearest-neighbor indexes trade exactness for speed and memory on large collections. Their benefit depends strongly on dimension, metric, and data distribution, so query latency and recall should be measured on representative data rather than inferred from asymptotic notation alone.

Probabilistic Interpretation

kNN is discriminative: it estimates the conditional behavior of \(Y\) near a given \(\mathbf x\) without specifying a generative distribution for the features. The neighborhood acts as a data-dependent window. For classification, the class fraction estimates a conditional probability; for regression, the local average estimates the conditional mean

\[ m(\mathbf x)=\mathbb E[Y\mid\mathbf X=\mathbf x]. \]

Consistency requires the neighborhood to become locally smaller while still containing more observations as the sample grows. A standard asymptotic regime is

\[ k\to\infty, \qquad \frac{k}{m}\to0 \qquad\text{as }m\to\infty. \]

The first condition averages away local sampling noise; the second prevents the neighborhood from retaining a fixed fraction of the entire population. Under suitable regularity assumptions, these competing limits allow kNN estimates to approach the underlying conditional quantities.

Implementation Outline

fit(trainingFeatures, trainingTargets):
    scaler = fitScaler(trainingFeatures)
    storedFeatures = scaler.transform(trainingFeatures)
    storedTargets = trainingTargets

predict(query, k):
    transformedQuery = scaler.transform(query)
    distances = distanceToEveryStoredPoint(transformedQuery)
    neighbors = selectKSmallest(distances, k)

    if any neighbor has distance zero:
        neighbors = all zero-distance neighbors

    return vote(neighbors)       // classification
    return average(neighbors)    // regression

Production code should additionally define missing-value behavior, validate \(1\le k\le m\), use a stable rule for equal distances and equal votes, keep all preprocessing inside the fitted pipeline, and return enough diagnostic information to inspect the selected neighbors when predictions are surprising.

When kNN Is a Good Fit

• The sample is moderate in size and predictions need not have extremely low latency.
• A meaningful distance or similarity is available.
• The decision boundary or response function is locally structured and need not follow a simple global formula.
• Local examples are useful explanations for individual predictions.

kNN is less attractive when most features are irrelevant, dimensionality is high relative to sample size, storage is constrained, or queries must be answered faster than exact or approximate neighbor retrieval permits. It also does not extrapolate naturally: regression outside the observed feature region returns averages of distant boundary points rather than continuing a learned trend.

References

• [Fix1951]Evelyn Fix and Joseph L. Hodges Jr., Discriminatory Analysis: Nonparametric Discrimination: Consistency Properties, USAF School of Aviation Medicine, 1951.
• [Cover1967]Thomas M. Cover and Peter E. Hart, Nearest Neighbor Pattern Classification, IEEE Transactions on Information Theory 13(1), 21–27, 1967.
• [Stone1977]Charles J. Stone, Consistent Nonparametric Regression, The Annals of Statistics 5(4), 595–620, 1977.
• [Bentley1975]Jon Louis Bentley, Multidimensional Binary Search Trees Used for Associative Searching, Communications of the ACM 18(9), 509–517, 1975.