03 · Supervised · 5 min read · Interactive · updated 8 October 2026

How does the k-nearest neighbors algorithm work and how do you choose k?

What it is

The k-nearest neighbors method (kNN) is an algorithm that, for a new case, finds the k most similar examples in the training set and assigns it the class that dominates among those neighbours. In regression, instead of voting, it takes the mean of their values. Similarity is usually measured by Euclidean distance in feature space.

It is a "lazy" model: during training it does nothing beyond storing the data, and all the work happens at prediction time. There are no weights to learn and no formula to read off — the model is simply the training set plus a voting rule.

The intuition is everyday: to judge the price of a flat, you look at a few of the most similar listings nearby. Theoretical analysis of the method began with the work of Fix and Hodges (1951), and a well-known result by Cover and Hart (1967) states that with infinitely many data points the error of the one-nearest-neighbour rule is at most twice the smallest achievable error.

Mechanism — why it works this way

kNN rests on a single assumption: points that are close in feature space have similar responses. If that holds, the local majority is a good approximation of the class probability at that location. The model assumes no shape for the boundary, so it can fit an arbitrarily complex partition — provided it has enough data.

The parameter k controls the bias–variance trade-off. With k = 1 the model memorises every point, including mislabelled ones; the boundary is jagged and training accuracy is always 100% (each point is its own neighbour). A larger k averages over more points: the boundary smooths out and the influence of noise shrinks. With k equal to the size of the dataset the model always predicts the majority class. A good k lies somewhere in between and is chosen by cross-validation; with two classes, k is chosen odd to avoid ties.

The most important practical trap is feature scale. Euclidean distance sums squared differences, so a feature with large numbers — mass in grams, income in dollars — will dominate features measured in small units. Without standardisation, kNN effectively uses just one feature.

The second trap is dimensionality. In many dimensions, distances between points become similar to one another: the "nearest" neighbour is hardly closer than an average one. This is a manifestation of the curse of dimensionality. On top of that, every irrelevant feature adds noise to the distance, which blurs the signal from the important features. kNN cannot ignore useless features on its own — they have to be removed beforehand.

A third cost: prediction requires comparison with the whole training set. Data structures (KD-trees, ball trees) speed this up in low dimensions; with millions of vectors, approximate nearest-neighbour search is used — the same technique that powers today's vector search.

By example

Palmer Penguins: 342 penguins, four measurements (bill length and depth in mm, flipper length in mm, body mass in g), three species; training on 256, testing on 86 (stratified split, random_state=0). Without scaling, kNN with k = 5 is right in 86.0% of cases. Why so poor? Take an Adelie penguin (bill 39.1 mm long and 18.7 mm deep, flipper 181 mm, 3,750 g) and a Chinstrap (46.5 mm, 17.9 mm, 192 mm, 3,500 g). Their distance is 250.4, and almost all of it (99.7% of the sum of squares) comes from the 250 g difference in mass — while the 7.4 mm difference in bill length, which happens to be the best separator of these species, barely counts.

After standardising the features (mean 0, standard deviation 1), the same model scores 98.8%. The effect of k: for k = 1, 3 and 5 — 98.8%, for k = 11 and 25 — 97.7%, for k = 51 — 96.5%, for k = 101 — 87.2%, because the "neighbourhood" now covers half of the less numerous species. The curse of dimensionality shows up too: when random noise features are appended to the four measurements, 5-fold cross-validated accuracy falls from 98.2% to 91.8% (10 noise features), 79.8% (50) and 63.7% (200).

Try it yourself: the interactive illustration (labels in Polish for now).

In practice

• KNeighborsClassifier(n_neighbors=5) and KNeighborsRegressor; always inside a pipeline: make_pipeline(StandardScaler(), KNeighborsClassifier()).
• Choose k with GridSearchCV over kneighborsclassifier__n_neighbors; typically 3–30, less for small datasets.
• weights="distance" gives closer neighbours a bigger say — helpful when data density is uneven.
• Other metrics via metric=: "manhattan" can be more robust, "cosine" works well for text and embeddings.
• For large datasets with many dimensions, use approximate nearest-neighbour libraries (e.g. FAISS, Annoy) instead of exact search.

Frequently asked questions

How do you choose k?

By cross-validation: try several values and pick the one with the best validation score. The rule of thumb k ≈ √n can be a starting point, but it is no substitute for validation. If scores are tied, choose the larger k — it gives a smoother, more stable boundary.

Is kNN suitable for large datasets?

Training is instantaneous, but every prediction requires a neighbour search, and the whole dataset has to fit in memory. With millions of examples, approximate nearest-neighbour search is used, trading a little accuracy for a huge speed-up.

Why does kNN perform poorly with many features?

Because in high dimensions all points are roughly equally far apart, and irrelevant features add noise to every distance. The model cannot skip them on its own. Feature selection, dimensionality reduction (e.g. PCA) or learning a better representation before applying kNN all help.

Sources

See also