k-nearest neighbors

Also known as: k-NN · KNN

On this page 8

k-nearest neighbors (k-NN) is a non-parametric, instance-based method in machine learning that predicts the label or value of a new data point from the k most similar examples in the stored training set. In classification it takes a majority vote among those neighbors, and in regression it returns their average target value.

Within artificial intelligence, k-NN is the textbook example of lazy learning: it builds no explicit model during training and defers all computation to prediction time. That simplicity makes it a strong baseline, a practical tool for recommendation and similarity search, and a clear illustration of how distance metrics, feature scaling and the curse of dimensionality shape model behavior.

How k-nearest neighbors makes a prediction

A k-NN prediction follows a fixed sequence of steps: measure distance from the query point to every stored example, select the k closest, and aggregate their targets. Training consists only of storing the labeled data, which is why the method is called memory-based or instance-based.

The result depends on three design choices rather than on learned weights. The table below summarizes each stage and the decision it requires.

StageWhat happensMain decision
StoreAll training vectors and labels are kept in memoryWhether to index the data with a tree or graph
MeasureDistance from the query to each candidate is computedWhich distance metric to use
SelectThe k smallest distances are keptThe value of k
AggregateNeighbor labels are voted or values averagedUniform or distance-weighted votes
Stages of a k-NN prediction

In distance-weighted k-NN, each neighbor contributes in proportion to the inverse of its distance, so very close examples dominate the vote. This weighting reduces the influence of the k-th neighbor when it lies far away and often resolves ties in binary classification without requiring an odd k.

Choosing k and the distance metric

The value of k controls the bias-variance tradeoff of the classifier. A small k such as 1 produces a jagged decision boundary that follows noise, while a large k smooths the boundary and can blur genuine class structure. In practice k is chosen by cross-validation, often between 3 and 25, and a common starting heuristic is the square root of the training set size.

Value of kDecision boundaryTypical risk
k = 1Highly irregular, follows single pointsOverfitting and sensitivity to label noise
Moderate k (5-15)Smooth but responsive to local structureBalanced bias and variance
Very large kNearly flat, dominated by the majority classUnderfitting and class imbalance bias
Effect of the value of k

The distance metric defines what similar means, and it must match the data type. Euclidean distance suits continuous features on comparable scales, Manhattan distance is more robust to single large deviations, and cosine similarity suits text embeddings and other vectors where direction matters more than magnitude.

MetricBest suited toCaution
Euclidean (L2)Dense numeric featuresDominated by large-scale features
Manhattan (L1)Grid-like or outlier-prone dataLess intuitive geometry
CosineEmbeddings and sparse text vectorsIgnores vector length
HammingBinary or categorical codesNeeds encoded features
MahalanobisCorrelated numeric featuresRequires a stable covariance estimate
Common distance measures for k-NN

Why feature scaling and dimensionality matter

Because k-NN relies entirely on distances, unscaled features distort similarity. A salary measured in dollars will overwhelm an age measured in years unless both are standardized or normalized, so feature scaling is mandatory, not optional, for almost every k-NN pipeline.

The curse of dimensionality is the second structural weakness. As the number of features grows into the hundreds, distances between random points become nearly equal, and the nearest neighbor is barely nearer than the farthest one. Practitioners therefore apply dimensionality reduction such as principal component analysis, or feature selection, before running k-NN on wide tabular data.

k-NN differs from most classic algorithms because it moves cost from training to inference. Logistic regression, decision trees and support vector machines compress the data into parameters, while k-NN keeps every example and searches them at query time.

MethodTraining costPrediction costInterpretability
k-nearest neighborsNear zeroHigh without an indexExplains by showing similar cases
Logistic regressionLowVery lowCoefficients per feature
Decision treeModerateVery lowReadable rules
Support vector machineHigh on large dataDepends on support vectorsLimited with kernels
k-NN and neighboring methods

It should not be confused with k-means clustering, which is an unsupervised method that groups unlabeled points around k centroids. In k-NN the letter k counts neighbors used for a supervised prediction, not clusters.

Scaling k-NN to large datasets

A brute-force search compares the query with every stored point, giving a cost of O(n·d) per prediction for n examples and d features. For large collections, spatial indexes and approximate nearest neighbor (ANN) search reduce this cost substantially.

  • KD-trees and ball trees partition space and work well up to roughly 20-30 dimensions.
  • Graph-based indexes such as HNSW deliver fast approximate search over millions of embeddings.
  • Product quantization compresses vectors to cut memory at a small cost in recall.
  • Condensed or edited k-NN removes redundant or noisy training points before deployment.

Approximate search trades a small, measurable loss of recall for large speedups, which is why it underpins vector databases and retrieval systems built on the same nearest-neighbor principle.

Limitations and common mistakes

Most k-NN failures come from data preparation errors rather than from the algorithm itself. The table below lists frequent symptoms and their remedies.

SymptomLikely causeFix
One feature drives every predictionMissing feature scalingStandardize or normalize all features
Minority class is never predictedClass imbalance with large kUse distance weighting or resampling
Accuracy drops on wide dataCurse of dimensionalityReduce dimensions or select features
Predictions are too slowBrute-force search at scaleUse a tree or ANN index
Results swing with tiny data changesk set too smallIncrease k via cross-validation
Typical k-NN problems and fixes

k-NN also handles missing values and categorical variables poorly unless they are imputed and encoded, and it has high memory requirements because the full training set must remain available at prediction time.

Stripped to the essentials

k-nearest neighbors answers a question by looking at the most similar past cases. To guess what a new item is, it finds the few stored examples that resemble it most and lets them vote.

It works much like asking the five neighbors on your street which school district you belong to: if four say one district, that is probably the right answer. The method learns nothing in advance, so it is easy to understand, but it becomes slow when there are millions of examples and confused when items are described by too many details. The key takeaway is that k-NN is only as good as its definition of similarity.

Where it is applied

A regional hospital analytics team wants a quick model that flags patients at elevated risk of readmission within 30 days. They describe each discharged patient with 12 standardized features, including age, length of stay, number of prior admissions and selected laboratory values.

The team scales every feature to zero mean and unit variance, then tests k values from 3 to 31 with five-fold cross-validation. Distance-weighted k-NN with k = 15 gives the best balance of recall and precision, and a ball-tree index keeps each prediction well under a second on a dataset of about 40,000 past discharges.

Clinicians value the result because every flag comes with the 15 most similar historical patients, which makes the reasoning easy to inspect. The model serves as a transparent baseline against which the team later evaluates a gradient boosting model.