K-Nearest Neighbours (KNN) Algorithm Explained with Python

You have just moved into a new flat in Vijay Nagar, Indore, and you want a daily tiffin. You don't know the area, so you ask the neighbours closest to you which thali they order. The family next door orders Punjabi. So does the one across the corridor. The flat downstairs orders Jain.

With three opinions, Punjabi wins two to one. But if you walk one more floor and ask five households, two more Jain votes tip the answer the other way.

You have just run the k-nearest neighbours algorithm, twice, with k = 3 and k = 5.

What is k-nearest neighbours (KNN)?

Map the tiffin hunt to machine learning:

• Each neighbour's home is a training row, and their thali is its label.
• You are the new row (query point) whose label is unknown.
• How far away each home is, is the distance between rows.
• How many neighbours you ask is k, a hyperparameter.
• Going with the most common answer is the majority vote.

K-nearest neighbours (KNN) is a supervised, non-parametric learning algorithm that predicts the label of a new data point from the labels of the k training points closest to it, using a majority vote for classification or an average for regression.

KNN has no training step in the usual sense. fit only stores the data; all the distance work happens in predict. That is why it's called a lazy learner, in contrast to logistic regression, which learns coefficients once and then predicts instantly. The code in this tutorial targets scikit-learn 1.7.

How does the KNN algorithm work?

Every prediction follows the same steps:

1. Choose k and a distance measure (Euclidean by default).
2. Compute the distance from the new point to every training point.
3. Sort the distances and take the k smallest.
4. Classification: return the most common label among those k. Regression: return their average value.

The same new point gets a different answer depending on k. The inner circle holds 3 neighbours, the outer circle 5.

Here are those steps in plain NumPy:

import numpy as np
from collections import Counter

# 10 neighbours: map position (km east, km north) and the tiffin thali they order
homes = np.array([[1.0, 2.0], [1.5, 1.8], [2.2, 2.6], [3.0, 1.0], [3.5, 3.5],
                  [0.5, 3.0], [2.8, 2.9], [4.0, 2.0], [1.2, 0.8], [2.0, 1.5]])
tiffin = np.array(["Jain", "Jain", "Punjabi", "Punjabi", "Punjabi",
                   "Jain", "Jain", "Punjabi", "Jain", "Punjabi"])
you = np.array([2.1, 2.1])                        # the new resident

dist = np.sqrt(((homes - you) ** 2).sum(axis=1))  # Euclidean distance to each home
order = np.argsort(dist)
for i in order[:5]:
    print(f"home {i}: {dist[i]:.2f} km away, orders {tiffin[i]}")
for k in (3, 5):
    vote = Counter(tiffin[order[:k]]).most_common(1)[0]
    print(f"k={k}: prediction = {vote[0]} ({vote[1]} of {k} votes)")

The two nearest homes, about 0.5 and 0.6 km away, order Punjabi, so k = 3 predicts Punjabi. The next three homes all order Jain, so k = 5 flips the answer. A single setting changed the prediction, which is why k must be chosen carefully.

Distance metrics

Euclidean distance is the straight-line distance: the square root of the sum of squared differences. Manhattan distance adds the absolute differences, like walking along a city grid. scikit-learn's default, metric="minkowski" with p=2, is Euclidean; set p=1 for Manhattan. For text or embeddings, cosine distance is common, as covered in linear algebra for data science.

Why does feature scaling matter for KNN?

KNN adds up differences across all features. If one feature is in lakhs of rupees and another in years, a ₹10,000 income gap swamps a 30-year age gap. The model effectively ignores every small-number column.

import numpy as np
from sklearn.model_selection import cross_val_score
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

rng = np.random.default_rng(0)
n = 400
age = rng.uniform(21, 60, n)                    # years: this is what drives the label
income = rng.uniform(2e5, 2.5e6, n)             # rupees: pure noise here, but huge numbers
buys_term_plan = (age + rng.normal(0, 5, n) > 38).astype(int)
X = np.column_stack([age, income])

raw = KNeighborsClassifier(n_neighbors=7)
scaled = make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=7))
print(f"KNN on raw units   : {cross_val_score(raw, X, buys_term_plan, cv=5).mean():.3f}")
print(f"KNN after scaling  : {cross_val_score(scaled, X, buys_term_plan, cv=5).mean():.3f}")
print("age range:", round(age.max() - age.min()), "years | income range: Rs", f"{income.max() - income.min():,.0f}")

On raw units, KNN scores about 0.59, barely better than guessing, because "nearest" really means "most similar income", and income is noise here. After StandardScaler the accuracy jumps to about 0.89. Always put the scaler inside a pipeline so each fold learns its own scaling; data preprocessing: scaling and encoding compares the scalers.

How do you choose the value of k?

k controls the bias-variance trade-off directly:

• k = 1 copies the label of the single closest point. Every noisy row carves out its own little region, so the model overfits: perfect training accuracy, weaker test accuracy.
• Very large k averages over so many points that local patterns wash out, so the model underfits. At k = n it predicts the majority class for everyone.
• The best k sits in between, and you find it with cross-validation.

from sklearn.datasets import make_moons
from sklearn.model_selection import cross_validate
from sklearn.neighbors import KNeighborsClassifier

X, y = make_moons(n_samples=400, noise=0.35, random_state=0)

print("  k  | train acc | CV acc")
for k in [1, 3, 7, 15, 31, 75, 151]:
    res = cross_validate(KNeighborsClassifier(n_neighbors=k), X, y, cv=5,
                         return_train_score=True)
    print(f"{k:4d} | {res['train_score'].mean():9.3f} | {res['test_score'].mean():.3f}")

At k = 1 the training score is perfect but the CV score is the lowest of the small values. CV accuracy peaks around k = 15 to 31, then drops as k grows too large.

The numbers match the picture: k = 1 scores 1.000 on training rows and 0.830 on validation, while k = 31 scores about 0.88 on both. Two practical habits:

• For two classes, prefer odd k to avoid tied votes.
• Search k on a rough log scale (1, 3, 7, 15, 31 …) first, then refine. Hyperparameter tuning shows how to do this with GridSearchCV.

KNN for regression

For a numeric target, KNN averages the neighbours' values. Setting weights="distance" lets closer neighbours count more, which often helps when neighbours are spread unevenly.

import numpy as np
from sklearn.linear_model import LinearRegression
from sklearn.model_selection import cross_val_score
from sklearn.neighbors import KNeighborsRegressor
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

rng = np.random.default_rng(3)
n = 300
area = rng.uniform(400, 1800, n)                    # sq ft
km = rng.uniform(1, 15, n)                          # distance from city centre
rent = 3000 + 10 * area - 60 * km ** 2 + rng.normal(0, 1200, n)   # rent falls faster far out
X = np.column_stack([area, km])

models = {
    "linear regression": LinearRegression(),
    "KNN, k=10, uniform": make_pipeline(StandardScaler(), KNeighborsRegressor(10)),
    "KNN, k=10, distance": make_pipeline(StandardScaler(), KNeighborsRegressor(10, weights="distance")),
}
for name, m in models.items():
    mae = -cross_val_score(m, X, rent, cv=5, scoring="neg_mean_absolute_error").mean()
    print(f"{name:>20}: CV MAE = Rs {mae:,.0f}")

Rent here falls off along a curve with distance, which a straight line can't follow, so KNN edges ahead (MAE about ₹1,080 against ₹1,171). KNN needs no assumption about the shape of the relationship; it just trusts that similar flats have similar rents.

What is the curse of dimensionality in KNN?

KNN relies on the idea that the nearest neighbours are genuinely closer than the rest. As you add features, that stops being true: in high dimensions, every point becomes almost equally far from every other.

import numpy as np

rng = np.random.default_rng(0)
print("dims | nearest / farthest distance from a random point")
for d in [2, 10, 50, 200, 1000]:
    X = rng.random((1000, d))                       # 1,000 random points in a unit cube
    q = rng.random(d)
    dist = np.sqrt(((X - q) ** 2).sum(axis=1))
    print(f"{d:4d} | {dist.min() / dist.max():.2f}")

In 2 dimensions the nearest point is only about 1% as far away as the farthest (ratio 0.01). In 1,000 dimensions the ratio is 0.89: the "nearest" neighbour is barely nearer than the farthest one, so the vote becomes close to random. Remove useless columns with feature selection or compress them with PCA before using KNN on wide data.

KNN pros and cons

scikit-learn speeds up neighbour search with tree structures (algorithm="auto" picks between a KD-tree, a ball tree and brute force), but for millions of rows you would move to approximate nearest-neighbour libraries, the same idea behind vector databases.

Common KNN mistakes

• Forgetting to scale. The largest-unit column silently decides every prediction.
• Choosing k by training accuracy. k = 1 always wins on training data; use cross-validation.
• Feeding raw categories. Encode them first, and think about whether distances between encoded categories make sense.
• Using KNN on hundreds of features without reduction. Distances lose meaning.
• Ignoring class imbalance. With a rare class, the majority dominates most neighbourhoods; see handling imbalanced data.

KNN is quick to code but easy to misuse, so it pays to build a few projects with someone reviewing your scaling and k choices, as in the offline ML programme at Debugshala, Indore. The next topic in the series is the Naive Bayes classifier. To revise, test your KNN knowledge on Debugshala Test.

Key takeaways

• KNN predicts from the k most similar training rows: a vote for classes, an average for numbers.
• It is a lazy learner: fitting is instant, predicting is the expensive part.
• Always scale features, inside a pipeline.
• Small k overfits and large k underfits; choose k with cross-validation, odd for two classes.
• KNN suits small, low-dimensional data and degrades as features multiply.