1Decision Trees & Splitting 2K-Nearest Neighbors 3Support Vector Machines 4Naive Bayes Classifier 5K-Means Clustering 6Bagging & Random Forests 7Gradient Boosting 8Ensemble Methods & Stacking

Lensa ML

K-Nearest Neighbors

Step 1 of 6: The Nearest Neighbor

Classification by proximity

x = -3x = 0.0x = 3

y = -3y = 0.3y = 3

Query

(0.0, 0.3)

Nearest

Class C

Distance

0.39

Prediction

With k=1, k-NN gives the query the class of its single nearest neighbor: here class C, at distance 0.39. Drag the sliders to move the query and watch the nearest neighbor change.

Drag the x and y sliders to move the gold query star around the 45 training points, 15 per class. With k = 1, the plane divides into cells, one around each training point, where every location is closer to that point than to any other. This partition is a Voronoi diagram, and the 1-NN boundary runs along the cell edges that separate points of different classes. Cover and Hart showed in 1967 that, as the training set grows without limit, the 1-NN error rate is at most twice the lowest error any classifier can achieve.

Step 2 of 6: Choosing k

How many neighbors to ask

Votes

k = 1k = 3k = 15

Majority

Class B

Votes

0/2/1

Confidence

67%

With k=3, the prediction is a majority vote among 3 neighbors, which keeps local detail with some smoothing.

Drag k from 1 to 15 and watch the vote tally. The query sits at (0.2, 0.5). Its single nearest neighbor is class C, but from k = 3 onward class B wins the vote outright. An even k can produce ties, which is why odd values are common for two-class problems; this demo breaks a tie in favor of the earlier class. Small k gives low bias and high variance, and large k gives the reverse. The usual way to pick k is cross-validation over a range of values.

Step 3 of 6: Distance Metrics

Euclidean vs. Manhattan

x = -3x = 0.5x = 3

y = -3y = 0.8y = 3

Metric

Euclidean

Nearest d

0.49

Farthest d

0.86

Prediction

Euclidean distance is the straight-line length √(Δx² + Δy²). Points at equal distance form a circle. Toggle to Manhattan to compare which neighbors it picks.

Click Euclidean or Manhattan, then move the query with the sliders to find spots where the two metrics pick different neighbors. Both are cases of the Minkowski distance (Σ |x_i − y_i|^p)^(1/p), with p = 2 for Euclidean and p = 1 for Manhattan. Manhattan distance does not square the differences, so one large coordinate gap has less pull. For text and embeddings, cosine distance is the usual choice because it compares direction and ignores length. With any metric, features on larger scales dominate unless the data is standardized first.

Step 4 of 6: Decision Boundaries

The Voronoi landscape

k = 1k = 1k = 15

Train acc

100%

Edges

Smoothness

Low

With k=1, the boundary hugs every point and leaves islands around the outliers. Train accuracy is 100% only because each point is its own nearest neighbor.

Drag k through the odd values from 1 to 15 and watch the islands disappear. This dataset of 58 points includes 7 outliers placed inside other classes' territory. Training accuracy falls from 100% at k = 1 to 88% at k = 3 and stays there, because from k = 3 on the vote overrules 6 of those 7 outliers. Training accuracy says little about k-NN, because at k = 1 each point is its own nearest neighbor and the score is always perfect. Judge k on held-out data instead.

Step 5 of 6: Distance Weighting

Closer neighbors matter more

Weighted vote

43%

29%

28%

uniform (0)exp = 0.0sharp (5)

Exponent

0.0

Prediction

Confidence

43%

Ratio

1:1

Uniform weighting: all 7 neighbors vote equally. The vote is a headcount, so a distant neighbor counts as much as the closest one.

Drag the exponent from 0 to 5, and click any neighbor to see its weight worked out. Each vote is weighted by 1/d^p, and the distances here run from 1 to 30. Class A already wins the uniform vote with 3 of the 7 neighbors, and weighting strengthens that result: at p = 2, A holds 89% of the vote. Weighting also helps k-NN regression, where it makes the prediction track the nearest targets more closely. In scikit-learn, the option weights="distance" uses p = 1.

Step 6 of 6: The Curse of High Dimensions

When distance loses meaning

2D2 dimensions200D

Dimensions

Nearest

0.30

Farthest

1.62

Gap

81%

In 2D, the nearest point (0.30) is much closer than the farthest (1.62), a 81% gap. k-NN can clearly tell neighbors apart.

Drag the dimensions slider from 2 to 200 and watch the gap card shrink. The 15 points are drawn uniformly from a cube in every dimension. In 2D the farthest point is about 5 times as far from the query as the nearest; by 200D the ratio is about 1.1, a 9% gap. Distances grow like √d while their spread grows much more slowly, so relative differences fade. Real data usually lies near a lower-dimensional surface, which is why k-NN still works on images or embeddings, often after a reduction such as PCA.

What is k-nearest neighbors (k-NN)?

k-nearest neighbors is a method that predicts from the k training points closest to a query. For classification it takes a majority vote of their labels, and for regression it averages their target values. There is no training step beyond storing the data, so all of the work happens at prediction time.

k-NN is a standard baseline, and the same nearest-neighbor search appears in recommendation ("users similar to you"), anomaly detection, missing-value imputation, and the vector search behind retrieval-augmented generation, where a query embedding is matched to its nearest document embeddings. Its results depend on the value of k, the distance metric, and whether the features are on comparable scales.

Key ideas

k-NN predicts from the labels of the k training points closest to the query.
It stores the training data and does all of its computation at prediction time.
Small k follows local detail and noise, while large k gives smoother, more biased boundaries.
The distance metric and the feature scaling decide which points count as neighbors.
Distance weighting gives closer neighbors stronger votes.
In high dimensions distances concentrate, and plain k-NN loses its discriminating power.

Common questions

Is k-NN supervised or unsupervised?

k-NN classification and regression are supervised, because they use labeled training points. It is often confused with k-means, an unsupervised clustering method. The k in k-means is the number of clusters, not the number of neighbors.

Why do features need to be scaled for k-NN?

A distance adds up differences across all features, so a feature measured in thousands swamps one measured in fractions. Standardizing each feature to zero mean and unit variance, or rescaling it to [0, 1], gives every feature a comparable say in who counts as a neighbor.

How does k-NN scale to large datasets?

A brute-force search compares the query with every training point, which costs O(n·d) per prediction. Tree indexes such as k-d trees and ball trees speed this up in low dimensions. For millions of high-dimensional vectors, approximate nearest-neighbor indexes such as HNSW trade a small loss in accuracy for large speedups.

Can k-NN be used for regression?

Yes. k-NN regression predicts the average target of the k nearest neighbors, optionally weighted by distance. The prediction is piecewise constant and cannot extrapolate beyond the range of targets seen in training.

Related explainers

Norms & Distance Metrics — L1, L2, cosine similarity — measuring closeness in vector spaces
Curse of Dimensionality — Why high-dimensional spaces break intuition and algorithms
Feature Scaling — Why and how to normalize features for faster convergence
K-Means Clustering — Unsupervised grouping by centroid distance
Decision Trees & Splitting — Recursive partitioning, Gini impurity, and pruning
Bias-Variance Tradeoff — Why models underfit or overfit — the fundamental decomposition

References

Last updated October 25, 2026