K-Nearest Neighbors (KNN)

Tell me who your neighbors are, and I will tell you what you are.

Key Points

No training phase. The model stores all training data.
Prediction requires computing distances to all training points – slow for large datasets.
Choice of k matters: small k (e.g., 1) overfits (noisy), large k underfits (too smooth).
Distance metric is usually Euclidean, but can be Manhattan, Minkowski, or others.
Requires feature scaling because features with larger ranges dominate distance.

What it is

KNN is a simple algorithm that makes predictions based on the majority vote (or average) of the k closest training examples. To predict a new point, you measure its distance to every point in the training set (using something like Euclidean distance). You pick the k nearest ones. For classification, you take the most common class among those k neighbors. For regression, you average their values. There is no explicit training step – the model is just the data itself. That is why it is called a lazy learner.

Why it exists

KNN exists because sometimes the simplest idea works: similar things have similar outcomes. If you want to know if a new wine is high quality, look at the wines most similar to it in chemical composition and see what quality they had. You don't need complex equations or assumptions about linearity. KNN is intuitive, non-parametric (makes no assumptions about data distribution), and works well for many problems, especially when the decision boundary is irregular.

What it measures

KNN measures distances. The choice of k measures the bias-variance tradeoff. Distance metrics measure similarity. The algorithm's performance is measured by classification accuracy or regression error on a test set. The number of neighbors (k) is a hyperparameter you tune. For high-dimensional data, distances become less meaningful – a phenomenon called the curse of dimensionality.

Intuition

Imagine you move to a new city and want to know if a neighborhood is safe. You look at the safety ratings of the 5 houses closest to your potential new house. If 4 of them have been broken into, you might think twice. If 4 are very safe, you feel good. That is KNN with k=5. You didn't learn any general rule about what makes a neighborhood safe. You just looked at similar examples. If you only looked at the single closest house (k=1), you might be misled by one weird outlier. If you looked at 100 houses (k=100), you would be averaging across too many, losing local information.

Formulas

Euclidean distance (two dimensions)

d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}

(x₁, y₁) — coordinates of first point
(x₂, y₂) — coordinates of second point

Euclidean distance (p dimensions)

d(\mathbf{a}, \mathbf{b}) = \sqrt{\sum_{j=1}^{p} (a_j - b_j)^2}

p — number of features
aⱼ, bⱼ — value of feature j for each point

Manhattan distance

d = \sum_{j=1}^{p} |a_j - b_j|

absolute sum — sum of absolute differences – like city block distance

When to use

Use KNN when your dataset is small to medium (less than 50,000 rows) because prediction is O(n) for each new point.
Use KNN when the decision boundary is very irregular and complex. KNN can approximate any shape given enough data.
Use KNN as a baseline – simple to implement and sometimes surprisingly effective.
Use KNN for recommendation systems ('users who liked this also liked...' is a form of KNN).

When not to use

Do not use KNN for high-dimensional data (more than 20 features). The curse of dimensionality makes distances meaningless.
Do not use KNN for large datasets where prediction latency matters. Each prediction takes O(n) time. Use a model with fast inference like a tree or neural net.
Do not use KNN without scaling features. A feature with range 0-1000 will dominate a feature with range 0-1.
Do not use KNN when you have many missing values. Distance computation fails. Impute first.

Common mistakes

Forgetting to scale features. The algorithm is distance-based, so unscaled features make no sense.
Choosing k = 1 and then wondering why the model overfits. Small k is sensitive to noise.
Using Euclidean distance on categorical features. You need to convert categories to numbers (one-hot) or use a different distance (Hamming).
Thinking KNN has no hyperparameters. You need to choose k, distance metric, and weighting scheme (uniform or distance-weighted).

In practice

In scikit-learn: `from sklearn.neighbors import KNeighborsClassifier`. Use `model = KNeighborsClassifier(n_neighbors=5)`. Fit: `model.fit(X_train, y_train)`. Prediction: `model.predict(X_test)`. For regression: `KNeighborsRegressor`. Always scale features with `StandardScaler` before KNN. Use cross-validation to pick k. Weighted KNN: `weights='distance'` gives more influence to closer neighbors. For large datasets, consider approximate nearest neighbor libraries like `annoy`, `faiss`, or `nmslib`.

Was this concept helpful?

Spot an error or gap? Suggest an edit →

Related concepts

feature-scalingcurse-of-dimensionalitydistance-metrics