k-nearest neighbors (k-NN)
k-nearest neighbors predicts by looking at the k most similar training examples. Learn distance metrics, choosing k, scaling and its role in vector search.
Overview
k-nearest neighbors, usually written k-NN, predicts by finding the k training examples most similar to a new case and using their answers. For classification it takes a vote among those neighbours; for regression it averages their values. There is no real training step. The model simply stores the data and does its work at prediction time.
Everything depends on what "similar" means. Each example is treated as a point in a space with one axis per feature, and similarity is measured by distance, most often Euclidean distance. Two customers with close ages, incomes and purchase counts are near each other; two very different customers are far apart.
An everyday picture: to guess the fair price of a used car, you look at the five most similar cars sold recently, same model, similar mileage and age, and average their prices. You did not build a formula; you trusted close examples. That is k-NN.
What it is
| Part | What it means |
|---|---|
| k | The number of neighbours consulted |
| Distance metric | How closeness is measured: Euclidean, Manhattan, cosine and others |
| Voting rule | Majority vote, or votes weighted by inverse distance |
| Feature scaling | Putting features on comparable ranges so none dominates distance |
| Index structure | A data structure that speeds up neighbour search |
| Exact search | Checking every stored point, guaranteed correct |
| Approximate search | Faster search that may miss some true neighbours |
k-NN is called a lazy or instance-based learner, because it defers all computation to prediction time. It is also non-parametric: it does not assume a fixed shape for the relationship between features and target. Its flexibility grows with the amount of data.
The same nearest-neighbour idea powers modern vector search. When a retrieval system finds documents whose embeddings are closest to a query, it is running a nearest-neighbour search, usually an approximate one built with indexes such as HNSW or libraries such as FAISS.
Where it came from
The method dates to a 1951 technical report for the US Air Force by Evelyn Fix and Joseph Hodges, statisticians at the University of California, Berkeley. They described a non-parametric approach to classification. The report was not formally published at the time.
In 1967 Thomas Cover and Peter Hart published "Nearest Neighbor Pattern Classification", which gave the method a firm theoretical footing. They showed that, with enough data, the error of the one-nearest-neighbour rule is at most about twice the lowest error any classifier could achieve. Later work added distance weighting, fuzzy variants and many metric-learning methods that learn a distance suited to the task.
Practical speed improved with spatial indexes such as k-d trees and ball trees, and later with approximate nearest-neighbour methods for very large, high-dimensional collections. Today k-NN is a teaching staple, a baseline in scikit-learn, and the conceptual core of similarity search in vector databases.
How it works
Step 1: prepare the features
Encode categories, handle missing values and scale numeric features, for example to zero mean and unit variance. Without scaling, a feature measured in thousands, such as income, swamps one measured in units, such as number of children.
Step 2: choose a distance
Euclidean distance suits dense numeric features. Manhattan distance is less sensitive to a single large difference. Cosine distance compares direction rather than length and is standard for text and embeddings. Hamming or Gower distances handle categorical or mixed data.
Step 3: find the neighbours
For a new example, compute its distance to stored examples and keep the k smallest. On small data a brute-force scan is fine. On larger data, k-d trees or ball trees help in low dimensions, and approximate indexes help in high dimensions.
Step 4: combine their answers
Take a majority vote for classification, or the mean for regression. Distance weighting gives closer neighbours more say. The share of neighbours in each class can serve as a rough probability.
Step 5: choose k by validation
Small k, such as 1, follows the data closely and is sensitive to noise. Large k smooths predictions but can blur real boundaries. Choose k with cross-validation; odd values avoid ties in two-class problems.
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
knn = make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=15, weights="distance"))
knn.fit(X_train, y_train)
Key concepts and terms
| Term | Meaning |
|---|---|
| Lazy learning | Doing the work at prediction time rather than training time |
| Euclidean distance | Straight-line distance between two points |
| Manhattan distance | Sum of absolute differences along each axis |
| Cosine similarity | Similarity of direction between two vectors |
| Distance weighting | Giving nearer neighbours more influence |
| Curse of dimensionality | In many dimensions, distances become less informative |
| k-d tree | A space-partitioning index for fast search in low dimensions |
| Ball tree | An index built from nested hyperspheres |
| Approximate nearest neighbour | Fast search that trades a little accuracy for speed |
| Metric learning | Learning a distance function suited to a task |
A worked example
This scenario is illustrative. A wine shop wants to recommend similar bottles. It has 3,000 wines described by price, alcohol, sweetness, acidity, body and grape variety, plus a customer rating. For a customer who liked a particular bottle, the shop wants the five most similar wines.
The team one-hot encodes grape variety, scales the numeric features, and gives price half the weight of the taste features so that recommendations are driven mainly by style. It uses Euclidean distance with k = 5. For a medium-bodied red at 18 euros, the five neighbours are reds between 14 and 24 euros with similar acidity and body.
To test whether the representation is sensible, the team uses k-NN regression to predict each wine's rating from its neighbours. With k = 15 and distance weighting, mean absolute error is 0.38 stars on a five-star scale, against 0.61 for always predicting the average. That suggests neighbours in this feature space genuinely share quality, so the recommendations are likely to be meaningful.
Strengths and limitations
Strengths:
- Simple to understand and to explain with real examples.
- No training time; new data can be added instantly.
- Makes no assumption about the shape of the decision boundary.
- Works for classification, regression and recommendation.
- Predictions can be justified by showing the neighbours.
Limitations:
- Prediction is slow on large datasets without an index.
- Must store the whole training set.
- Very sensitive to feature scaling and irrelevant features.
- Performs poorly in high dimensions with raw features.
- Struggles with imbalanced classes, since the majority class dominates neighbourhoods.
How it compares with alternatives
| Method | Training cost | Prediction cost | Best for |
|---|---|---|---|
| k-NN | None | High without an index | Small data, similarity, baselines |
| Logistic regression | Low | Very low | Linear boundaries, probabilities |
| Decision trees | Low | Very low | Rules, mixed features |
| Gradient boosting | Medium | Low | Highest tabular accuracy |
| Support vector machines | Medium to high | Medium | Medium-sized data with clear margins |
Practical guidance and best practices
- Scale features before computing distances.
- Remove or down-weight irrelevant features; each one adds noise to distance.
- Choose k with cross-validation and try distance weighting.
- Use cosine distance for text and embedding vectors.
- Reduce dimensions with PCA or learned embeddings before search when features are many.
- Use an approximate index when the dataset or query volume is large.
- Show users the neighbours behind a prediction to build trust.
Common mistakes
- Forgetting to scale, so one large-valued feature decides everything.
- Using k = 1 and being surprised by noisy predictions.
- Fitting the scaler on all data before splitting, which leaks information.
- Applying k-NN to hundreds of raw features and expecting useful distances.
- Ignoring duplicate rows, which make neighbours look closer than they are.
Frequently asked questions
How do I choose k?
Try a range of values, such as 1 to 50, with cross-validation and pick the one with the best validation score. As a rough starting point, a value near the square root of the number of training examples is sometimes suggested, but validation should decide.
Why does k-NN struggle in high dimensions?
As the number of dimensions grows, the distances between points become more similar to one another, so the nearest point is not much nearer than the farthest. Neighbourhoods lose meaning. Reducing dimensions or using learned embeddings restores useful structure.
Is k-NN the same as vector search?
Vector search is nearest-neighbour search on embedding vectors, usually approximate for speed. Classic k-NN adds a prediction step that votes or averages over the neighbours. The underlying search problem is the same.
Can k-NN output probabilities?
Roughly. The share of neighbours in each class can serve as a probability, but with small k these values are coarse, such as 0.2 or 0.4. If you need calibrated probabilities, use a larger k or a different model.
Does k-NN work with categorical data?
Yes, with a suitable distance. One-hot encoding plus Euclidean distance works for a few categories; Hamming distance or Gower distance handles many categorical or mixed features more naturally.
Glossary
- Neighbour: a stored example close to the query point.
- k: the number of neighbours used.
- Distance metric: the rule for measuring closeness.
- Feature scaling: transforming features to comparable ranges.
- Instance-based learning: predicting directly from stored examples.
- Approximate nearest neighbour search: fast, slightly inexact neighbour search.
- Curse of dimensionality: loss of meaningful distance in many dimensions.
- Embedding: a learned vector representation where similar items lie close together.
Summary
k-nearest neighbors predicts from the k most similar stored examples, by vote or average, with no training beyond storing the data. It dates to Fix and Hodges in 1951 and was put on firm theoretical ground by Cover and Hart in 1967. It is simple, flexible and easy to explain, but slow on large data, sensitive to scaling and weak in high dimensions. Scale features, choose k by validation, reduce dimensions when needed, and use approximate indexes for scale, the same techniques that power modern vector search.
Related
It belongs to ML foundations in my stack, under Machine learning. Others in the same group: