K-Nearest Neighbours (KNN)

The idea

“Tell me who your friends are, and I’ll tell you who you are.”

K-Nearest Neighbours classifies a new example by finding the k most similar labelled examples and letting them vote:

1. Measure the distance from the new point to every training point.
2. Pick the k closest.
3. The most common class among them is the prediction.

That’s the whole algorithm. There is no training phase — KNN just remembers the data (it is a lazy learner).

In the 3D model, each point has three features, so it lives in 3D space. The ◆ is the new point; the bubble encloses its k nearest neighbours.

Measuring “close”: distance

The usual choice is Euclidean distance — the straight-line distance:

d(p, q) = √( (p₁ − q₁)² + (p₂ − q₂)² + (p₃ − q₃)² )

Other options: Manhattan distance (sum of absolute differences), or cosine similarity for text.

Scale your features!

If one feature is “salary” (thousands) and another is “age” (tens), salary dominates the distance completely. Always standardise features (subtract the mean, divide by the standard deviation) before KNN.

Choosing k

Pick k with cross-validation, and prefer an odd k for two classes to avoid ties. A common variation weights each vote by 1/distance, so closer neighbours count more.

Code

import numpy as np
from collections import Counter

def knn_predict(X_train, y_train, query, k=5):
    dists = np.linalg.norm(X_train - query, axis=1)   # distance to every point
    nearest = np.argsort(dists)[:k]                     # indexes of the k closest
    return Counter(y_train[nearest]).most_common(1)[0][0]

X = np.array([[1, 2, 1], [2, 1, 1], [1, 1, 2], [6, 5, 6], [5, 6, 5], [6, 6, 5]])
y = np.array(["A", "A", "A", "B", "B", "B"])
print(knn_predict(X, y, np.array([2, 2, 2]), k=3))   # A

With scikit-learn (including scaling):

from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier

model = make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=5)).fit(X, y)
print(model.predict([[2, 2, 2]]))

The curse of dimensionality

In very high dimensions (hundreds of features), almost all points end up roughly the same distance apart, so “nearest” stops meaning much. KNN works best with a modest number of meaningful features — often after PCA.

KNN vs K-Means

They sound alike but are different:

Where is it used?

Recommendation systems (“customers similar to you bought…”), handwriting recognition, anomaly detection, and as a quick, strong baseline for small datasets.

Common mistakes

• Not scaling features.
• Using KNN on huge datasets without an index — every prediction scans everything.
• Confusing KNN with K-Means.