Definition
k-Nearest Neighbors (kNN) is a supervised learning algorithm that classifies a new data point by looking at the k training examples closest to it and taking a majority vote of their labels. Its defining and slightly surprising property is that it never builds a model: it memorises the entire training set and defers every calculation to prediction time, which is why it is called a lazy learner (or an instance-based method).
That one design choice explains most of kNN's behaviour. Because nothing is learned in advance, there are only two things you can actually tune — the number of neighbours k, and the distance metric that decides what "closest" means — and the whole training set has to be carried around forever. The same procedure does regression too: instead of voting on a label, you average the numeric values of the k nearest neighbours. kNN is one of the oldest and most intuitive algorithms in machine learning precisely because there is no training step to obscure what it is doing.
How It Works
To classify a query point, kNN runs the same four steps every time:
- Measure the distance from the query to every point in the stored training set.
- Sort those points by distance and keep the k smallest.
- Read off the labels of those k neighbours.
- Output whichever label appears most often (for regression, output their average).
There is no step 0 that happens earlier — no weights fitted, no tree grown, no boundary computed. The model is the data. This is the trade at the heart of kNN: an eager learner such as a decision tree spends effort up front to build a compact model and then predicts almost for free, while kNN spends nothing up front and pays the full price on every prediction. A brute-force query over N stored points in d dimensions costs on the order of N times d arithmetic operations, because it computes a d-dimensional distance to each of the N points. A million-row training set means a million distance computations for a single prediction.
The distance metric is the algorithm
Because "nearest" is the only thing kNN knows, the distance metric is not a detail — it defines the classifier. The usual default is Euclidean (L2) distance, the straight-line distance you would measure with a ruler: the square root of the summed squared differences across features. Manhattan (L1) distance sums the absolute differences instead, as if you could only travel along grid streets, and it is often steadier when features are noisy. Both are special cases of the Minkowski distance with parameter p (p = 2 is Euclidean, p = 1 is Manhattan). For text or high-dimensional sparse vectors, cosine distance compares direction rather than magnitude, and for categorical attributes Hamming distance counts how many fields differ. Change the metric and you can change every prediction the model makes.
Feature scaling is not optional
Euclidean distance adds up the squared difference of each feature, so a feature that spans a large numeric range silently drowns out the others. Suppose two customers differ by 10,000 in annual salary (measured in dollars) and by 50 in age (measured in years). The salary term contributes 10,000² = 100,000,000 to the squared distance; the age term contributes 50² = 2,500. Age is roughly forty-thousand times smaller and might as well not be in the data. This is why kNN almost always requires feature scaling (standardising each feature to a comparable range) before distances mean anything — a step covered by the feature-scaling concept, and one whose absence is the most common reason a kNN model quietly fails.
A worked example: the same point, two answers
Distances alone do not classify anything; k does. Take a query point at the origin (0, 0) and seven training points described by two features, each labelled A or B. Sorting all seven by Euclidean distance gives:
rank 1: point (1, 0) dist=1.000 class A
rank 2: point (1, 1) dist=1.414 class A
rank 3: point (2, 0) dist=2.000 class B
rank 4: point (2, 1) dist=2.236 class B
rank 5: point (2, 2) dist=2.828 class B
rank 6: point (3, 0) dist=3.000 class A
rank 7: point (3, 1) dist=3.162 class B
With k = 3, the ballot is the three closest points — two A's and one B — so the prediction is A. With k = 7, the ballot widens to all seven points: three A's (ranks 1, 2, 6) against four B's, so the prediction flips to B. Nothing about the data changed; only the size of the neighbourhood did. The two nearest points are A, but the region as a whole is mostly B, and k decides which of those facts wins. That flip is not a quirk of a contrived example — it is the central tension of the whole algorithm.
Real-World Applications
kNN and its nearest-neighbour relatives show up wherever "find the most similar past examples" is the natural question:
- Recommender systems. Item-based collaborative filtering — the approach Amazon described in its item-to-item recommendation work (Linden, Smith and York, IEEE Internet Computing, 2003) — recommends products by finding the items nearest to what you already bought, using co-purchase vectors as the feature space. At its core this is nearest-neighbour retrieval.
- Missing-value imputation. kNN imputation fills a missing field by copying from the k most similar complete rows. It is a standard option in scikit-learn (
KNNImputer) and was introduced for DNA microarray data by Troyanskaya and colleagues (Bioinformatics, 2001), where it outperformed simply substituting column averages. - Anomaly and outlier detection. The distance to a point's k-th nearest neighbour is a natural anomaly score: genuine outliers sit far from everything. The Local Outlier Factor method (Breunig et al., 2000) builds directly on this idea, comparing a point's neighbourhood density to that of its neighbours.
- Handwritten digit recognition. kNN is the classic baseline on the MNIST digit benchmark, reaching low single-digit percentage error with nothing more than pixel-wise Euclidean distance — a striking result for an algorithm with no training and often the first number a new method has to beat.
If you cannot describe a task as "the answer for a new case resembles the answers for the cases most like it," kNN is probably the wrong tool.
Key Concepts
k is a bias/variance dial
The single most important choice in kNN is k, and it behaves as a direct control on the bias/variance tradeoff. At k = 1, the model simply hands each query the label of its single closest point. Training error is zero — every training point is its own nearest neighbour — and the decision boundary fragments into a mosaic of cells (a Voronoi tessellation) that wraps tightly around every individual point. That is minimum bias and maximum variance: a single mislabelled or noisy example creates a small wrong island in the map, and the model overfits.
As k grows, the boundary smooths out because each prediction is averaged over more neighbours, trading variance for bias. Push it to the extreme — k = N, the whole training set — and every query gets the same answer: the global majority class, regardless of where the query actually sits. That is maximum bias, and the model has stopped looking at the input at all. The useful setting is somewhere in between, and it depends on the data, which is why k is chosen by measuring error on held-out data rather than by a formula. A frequently quoted rule of thumb is k near the square root of the number of training points, and for two-class problems an odd k avoids tied votes — but both are starting points to validate, not laws.
The curse of dimensionality
kNN rests entirely on the idea that "near" means "similar." In high-dimensional spaces that idea quietly breaks, and the failure is geometric rather than a matter of tuning. Two durable calculations show why.
First, volume floods to the edges. Consider points inside a unit ball and ask what fraction of the volume lies in the outer shell between radius 0.9 and radius 1.0. That fraction is 1 − 0.9^d, where d is the number of dimensions. In 1 dimension it is just 0.1. In 10 dimensions it is 1 − 0.9¹⁰ = 1 − 0.349 = 0.651 — already two-thirds. In 100 dimensions it is 1 − 0.9¹⁰⁰ ≈ 0.99997: essentially all the volume is crammed against the surface, so every point is far from the centre and far from the others.
Second, the data you would need to stay dense grows exponentially. If keeping ten samples along each feature axis is enough in 1 dimension, then covering the space at the same density in 10 dimensions needs 10¹⁰ — ten billion — points. No real dataset is that large, so in high dimensions your points are sparse no matter how many you have, and the "nearest" neighbour is not actually near. A well-known theoretical result (Beyer et al., 1999) makes this precise: under broad conditions the distances to the nearest and the farthest points converge as dimensionality rises, so the ratio between them approaches one and "nearest neighbour" loses its meaning. This is the main reason practitioners apply dimensionality reduction, or careful feature selection, before reaching for kNN.
Challenges
kNN's simplicity is real, but it comes with failure modes that are specific to how the algorithm works — and most of them get worse exactly when you most want the model to scale:
- Prediction is expensive and grows with the data. Because it is a lazy learner, every prediction re-scans the entire training set. Spatial index structures such as KD-trees and ball trees speed this up in low dimensions, but they degrade toward brute-force scanning as the number of features rises, so the very setting that makes kNN slow (many rows) often coincides with the one that makes the indexes useless (many columns). Approximate methods like locality-sensitive hashing trade exactness for speed.
- Irrelevant features actively hurt. Adding a feature that carries no signal is not neutral: it still contributes to every distance, pushing genuinely similar points apart. Unlike a decision tree, kNN cannot ignore a useless feature on its own.
- One unscaled feature becomes the only feature. As the salary-versus-age example showed, forgetting to standardise silently reduces a rich dataset to whichever column has the largest raw numbers.
- Imbalanced classes bias the vote. If one class makes up the large majority of the data, the k nearest neighbours will tend to be that class almost regardless of the query, and the minority class is rarely predicted. This is the class-imbalance problem, usually addressed with distance-weighted voting (closer neighbours count more) or by resampling the training set.
- Vote fractions are crude probabilities. The share of neighbours voting for a class is a rough confidence estimate at best — with k = 5 it can only ever be 0, 0.2, 0.4, and so on — so kNN outputs generally need calibration before they can be treated as trustworthy probabilities.
- Memory. The whole training set must be kept in memory to make any prediction at all, which can be prohibitive for large datasets.
Code Example
The implementation below is the entire algorithm — measure distances, sort, vote — with no training step, reproducing the k = 3 versus k = 7 example above. The printed output is the actual result of running this code.
import numpy as np
from collections import Counter
# Seven training points, two features each, labelled A or B
X = np.array([[1, 0], [1, 1], [2, 0], [2, 1], [2, 2], [3, 0], [3, 1]])
y = ["A", "A", "B", "B", "B", "A", "B"]
q = np.array([0, 0]) # the point we want to classify
dist = np.sqrt(((X - q) ** 2).sum(axis=1)) # Euclidean distance to each point
order = np.argsort(dist) # indices, nearest first
for rank, i in enumerate(order, 1):
print(f"rank {rank}: point {tuple(int(v) for v in X[i])} "
f"dist={dist[i]:.3f} class {y[i]}")
for k in (3, 7):
votes = Counter(y[i] for i in order[:k])
winner = votes.most_common(1)[0][0]
print(f"k={k}: {dict(votes)} -> predict {winner}")
Output:
rank 1: point (1, 0) dist=1.000 class A
rank 2: point (1, 1) dist=1.414 class A
rank 3: point (2, 0) dist=2.000 class B
rank 4: point (2, 1) dist=2.236 class B
rank 5: point (2, 2) dist=2.828 class B
rank 6: point (3, 0) dist=3.000 class A
rank 7: point (3, 1) dist=3.162 class B
k=3: {'A': 2, 'B': 1} -> predict A
k=7: {'A': 3, 'B': 4} -> predict B
The fit step every other classifier has is missing on purpose: the array X is the model. In practice you would reach for scikit-learn's KNeighborsClassifier, which wraps this same logic behind KD-tree and ball-tree indexes so that finding the k nearest points does not require scanning every row on every call.