k-Nearest Neighbors

Formally, k-NN is a non-parametric, instance-based learning method. Given a training set

where $x_i \in \mathbb{R}^d$ are feature vectors and $y_i$ are labels (discrete for classification, real-valued for regression), k-NN stores $\mathcal{D}$ verbatim. There is no parameter vector $\theta$ estimated from data — the "model" is the dataset itself, together with a chosen distance function $\text{dist}(\cdot,\cdot)$ and an integer $k \geq 1$. To predict the label of a new query point $x_q$, the algorithm finds the set $N_k(x_q) \subseteq \mathcal{D}$ of the $k$ training points closest to $x_q$ under the chosen distance. For classification, the prediction is the plurality (most frequent) class among the neighbors' labels:

For regression, the prediction is the mean (or a distance-weighted mean) of the neighbors' target values:

Because prediction depends entirely on which points happen to be nearby, k-NN implicitly assumes that similar inputs have similar outputs — a smoothness assumption on the underlying function, not a specific parametric form. This is what makes it non-parametric: the effective complexity of the decision boundary grows with the amount of data, unlike a linear model whose functional form is fixed in advance regardless of $n$.

The algorithm has two conceptual phases, though the first is nearly vacuous: 1. "Training": store the dataset $\mathcal{D}$, optionally organized in a spatial index (a k-d tree or ball tree) to speed up future queries. No parameters are fit. 2. Prediction: for each query point, compute distances to (a relevant subset of) training points, select the $k$ nearest, and aggregate their labels by vote or average. Preprocessing is not optional in practice: features must be put on comparable scales (standardization or min-max scaling), because distance metrics like Euclidean distance treat all coordinates as commensurable, and a feature measured in the thousands will dominate one measured in fractions unless rescaled. ``` ALGORITHM: k-Nearest-Neighbors (classification variant) INPUT: D = {(x_1, y_1), ..., (x_n, y_n)} # training set x_q # query point k # number of neighbors, 1 <= k <= n dist(a, b) # distance function TRAIN(D): store D # optionally build a spatial index (k-d tree, ball tree) return D PREDICT(D, x_q, k, dist): distances <- empty list for each (x_i, y_i) in D: d_i <- dist(x_q, x_i) append (d_i, y_i) to distances sort distances by d_i ascending neighbors <- first k entries of sorted distances

# classification: majority vote (break ties by nearest neighbor or smallest class index) counts <- empty map from label to integer for (d_i, y_i) in neighbors: counts[y_i] <- counts[y_i] + 1 y_hat <- label with maximum count in counts (tie-break: prefer label of the single nearest neighbor) return y_hat PREDICT_REGRESSION(D, x_q, k, dist):

# same neighbor search as above, then: neighbors <- k nearest (d_i, y_i) pairs y_hat <- (1 / k) * sum(y_i for (d_i, y_i) in neighbors) return y_hat PREDICT_WEIGHTED(D, x_q, k, dist):

# distance-weighted variant, reduces sensitivity to k neighbors <- k nearest (d_i, y_i) pairs weights <- [1 / (d_i + epsilon) for each neighbor] # epsilon avoids divide-by-zero y_hat <- sum(w_i * y_i) / sum(w_i) # regression

# for classification, sum w_i within each class and argmax return y_hat ```

Choosing $k$: $k$ is a hyperparameter selected by holding out validation data or by cross-validation, never by the training data's own error (which is minimized, misleadingly, at $k=1$). Odd values of $k$ are conventional in binary classification to avoid tied votes. Choosing the distance metric: common choices are Euclidean ($\ell_2$), Manhattan ($\ell_1$), the general Minkowski $\ell_p$ family, and cosine distance for high-dimensional sparse data such as text; the right choice depends on the geometry and scale of the features.

Time complexity. Let $n$ be the number of training points and $d$ the dimensionality of the features.

• Training: $O(1)$ with brute force (just store the array), or $O(n \log n)$ if building a k-d tree or ball tree.
• Brute-force prediction: computing distance to every point costs $O(d)$ each, over $n$ points, giving $O(nd)$ per query; selecting the $k$ smallest via a partial selection (e.g., a max-heap of size $k$) costs an additional $O(n \log k)$, so the total is $O(nd + n\log k)$ per query.
• Tree-based prediction (k-d tree, ball tree): average-case $O(d \log n)$ per query when $d$ is small relative to $n$, because the tree prunes large branches of the space that cannot contain a closer point than what's already found. This degrades toward $O(nd)$ in the worst case, and in practice toward brute force once $d$ exceeds roughly 15–20 dimensions — the geometric pruning stops helping because in high dimensions nearly every point ends up "on the boundary" of any partition.
• Space: $O(nd)$ to store the raw data, plus $O(n)$ overhead for a tree index.

There is a genuine and important asymmetry with parametric models: k-NN pushes essentially all computation from training time to prediction time. A linear or logistic regression model spends effort fitting a small parameter vector once, then predicts in $O(d)$; k-NN "trains" instantly but pays $O(nd)$ or $O(d\log n)$ on every single query, and must keep the entire dataset in memory indefinitely.

Correctness / why it works — the bias–variance view. Consider regression with squared-error loss. Suppose the true relationship is $y = f(x) + \varepsilon$ with $\varepsilon$ mean-zero noise of variance $\sigma^2$, and the $k$ neighbors of $x_q$ have approximately independent noise. The k-NN regression estimate is

Taking expectation over the noise, the bias comes from averaging $f$ over a neighborhood instead of evaluating it exactly at $x_q$:

which grows as $k$ grows, because the neighborhood radius must expand to include $k$ points, and $f$ typically varies more over a larger region (assuming $f$ is smooth, this scales with the neighborhood's spatial extent). The variance, assuming roughly independent noise across neighbors, is

which shrinks as $k$ grows, exactly as averaging more independent noisy quantities reduces variance. This is the bias–variance tradeoff made explicit: $k=1$ has zero averaging bias but variance $\sigma^2$ (as noisy as a single observation); $k=n$ (predict the global mean for every query) has minimal variance $\sigma^2/n$ but maximal bias, since it ignores $x_q$ entirely. The optimal $k$ minimizes the sum

and is found in practice by cross-validation rather than by this formula directly, since $f$ is unknown.

Consistency. A classical and reassuring theoretical result (Cover & Hart, 1967, for $k=1$; extended for general $k$) states that as $n \to \infty$ with $k \to \infty$ and $k/n \to 0$, the k-NN classifier's error rate converges to the Bayes-optimal error rate — the best possible error achievable by any classifier given the true data distribution. Intuitively: letting $k$ grow ensures the noise-averaging variance vanishes, while requiring $k/n \to 0$ ensures the neighborhood radius shrinks to zero (so the bias from averaging over a spatial region also vanishes) as more data arrives. This is a genuine asymptotic guarantee, but it says nothing about finite-sample behavior, where the curse of dimensionality (below) can make "shrinking neighborhoods" require impractically large $n$.

Consider a tiny 2-feature dataset predicting whether a loan applicant defaults (`Yes`/`No`), with features income (in $1000s) and debt ratio (percentage of income owed in debt):

Query point: $x_q = (\text{Income}=32, \text{Debt Ratio}=50)$.

Step 1 — scale features. Income ranges roughly 25–70 (span 45), debt ratio 10–60 (span 50); they're comparable here, but in general we standardize: $z = (x - \mu)/\sigma$. For this worked example we proceed with raw values for transparency, computing Euclidean distance $\text{dist}(a,b) = \sqrt{\sum_j (a_j - b_j)^2}$.

Step 2 — compute distances to $x_q = (32, 50)$:

Step 3 — sort ascending: $x_2 (5.39) < x_1 (12.21) < x_5 (12.81) < x_6 (20.22) < x_4 (36.34) < x_3 (55.17)$.

Step 4 — predict for different $k$:

All three choices of $k$ agree here — the applicant with income 32 and debt ratio 50 is predicted not to default, since the closest analogues ($x_2$, a similarly low-income, low-debt-ratio applicant) did not default. Note how $k=5$ nearly flips: two of the five neighbors are the "Yes" applicants $x_4$ and $x_5$, illustrating how increasing $k$ pulls in more distant, less relevant points and can shift or destabilize the prediction — exactly the bias increase the theory predicts. For a regression flavor of the same data (say we instead predict a continuous default risk score $y$ with values $y_1=0.1, y_2=0.15, y_3=0.05, y_4=0.8, y_5=0.7, y_6=0.2$), a $k=3$ prediction would be

again dominated by the two truly close points but nudged upward by the more distant but risky $x_5$.

k-NN's direct descendants are everywhere in industrial machine learning even when the name "k-NN" doesn't appear on the label. Recommender systems use nearest-neighbor lookups over user or item embeddings to suggest products, songs, or videos. Image and face-recognition retrieval systems embed images into vector spaces and then run (approximate) nearest-neighbor search to find matches — the same core operation as k-NN classification, but at a scale where brute force is replaced by structures like HNSW or product quantization. Anomaly detection systems flag points whose nearest neighbors are unusually far away. In bioinformatics, k-NN imputes missing gene-expression values from similar samples. Beyond direct use, k-NN is the pedagogical bridge to more advanced methods: understanding how it weights neighbors by distance leads naturally into Kernels and the Kernel Trick, where a smooth weighting function (a kernel) replaces the hard "in the k nearest or not" cutoff, and into kernel density estimation, local regression (LOESS), and Gaussian processes, all of which generalize the same "local similarity implies local averaging" principle that k-NN teaches in its simplest form. Understanding k-NN also builds direct intuition for the Bias–Variance Tradeoff and for probability concepts underlying Bayes-optimal classification, both essential for evaluating any supervised learning method.

Ask the tutor: How does replacing the hard k-nearest cutoff with a smooth distance-based weighting function turn k-NN into a kernel method?