K-Nearest Neighbour (KNN)

KNN classifies a new observation by looking at the k closest training examples and taking a majority vote among their labels. It is the simplest possible "learning" algorithm — it stores the training data and does all the work at prediction time.

KNN is called a lazy learner (no model is built during training) and a non-parametric, instance-based algorithm (it makes no assumption about the data's distribution).

Distance Metrics

Euclidean distance (default, L2) — straight-line distance:

   d(p, q) = √[ (p₁−q₁)² + (p₂−q₂)² + … + (pₙ−qₙ)² ]

Manhattan distance (L1) — city-block distance:

   d(p, q) = |p₁−q₁| + |p₂−q₂| + … + |pₙ−qₙ|

Minkowski distance (generalisation):

   d(p, q) = ( Σ |pᵢ−qᵢ|^m )^(1/m)
             m = 1  ->  Manhattan
             m = 2  ->  Euclidean

Hamming distance — for categorical features: count of positions that differ

Worked Example — By Hand

Training data (height in cm, weight in kg → T-shirt size):

Classify a new customer: Height = 161, Weight = 61. Use k = 3.

Euclidean distance from (161, 61):

  #1 (158,58): √[(161−158)² + (61−58)²] = √[9 + 9]   = √18   = 4.243
  #2 (158,59): √[(161−158)² + (61−59)²] = √[9 + 4]   = √13   = 3.606
  #3 (160,60): √[(161−160)² + (61−60)²] = √[1 + 1]   = √2    = 1.414
  #4 (163,61): √[(161−163)² + (61−61)²] = √[4 + 0]   = √4    = 2.000
  #5 (165,61): √[(161−165)² + (61−61)²] = √[16 + 0]  = √16   = 4.000
  #6 (168,62): √[(161−168)² + (61−62)²] = √[49 + 1]  = √50   = 7.071
  #7 (170,68): √[(161−170)² + (61−68)²] = √[81 + 49] = √130  = 11.402

Sorted:  #3 (1.414, M), #4 (2.000, M), #2 (3.606, M), #5 (4.000, L), ...

k = 3 nearest:  #3 = M,  #4 = M,  #2 = M

Majority vote:  M = 3,  L = 0

PREDICTION: Size M

Choosing k

Rules of thumb:

1. Try k ≈ √n as a starting point
2. Use an odd k for binary classification to avoid ties
3. Avoid k that is a multiple of the number of classes
4. Choose k by cross-validation — plot error vs k and pick the elbow

Feature Scaling Is Mandatory

KNN is distance-based, so a feature with a large numeric range dominates the distance entirely:

Unscaled — income overwhelms age:
   Point A: age=25, income=50000
   Point B: age=45, income=50100

   d = √[(25−45)² + (50000−50100)²] = √[400 + 10000] = 102.0
        ^ age contributes 400              ^ income contributes 10,000

   The 20-year age gap is almost invisible next to a Rs.100 income difference.

After standardisation both features contribute comparably. ALWAYS scale before KNN.

Python

import numpy as np
import pandas as pd
from sklearn.neighbors import KNeighborsClassifier

# Reproducing the T-shirt example
X = np.array([[158,58],[158,59],[160,60],[163,61],[165,61],[168,62],[170,68]])
y = np.array(["M","M","M","M","L","L","L"])

knn = KNeighborsClassifier(n_neighbors=3, metric="euclidean")
knn.fit(X, y)

new = np.array([[161, 61]])
print("Prediction:", knn.predict(new)[0])                    # M
print("Class order:", knn.classes_)
print("Probabilities:", knn.predict_proba(new))              # [[0. 1.]] -> 100% M

distances, indices = knn.kneighbors(new)
print("Neighbour indices:", indices[0])                      # [2 3 1]
print("Distances:", distances[0].round(3))                   # [1.414 2.    3.606]

# Full workflow WITH scaling — on the Iris dataset
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split, cross_val_score
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import make_pipeline
from sklearn.metrics import accuracy_score, classification_report

iris = load_iris()
X_train, X_test, y_train, y_test = train_test_split(
    iris.data, iris.target, test_size=0.3, random_state=42, stratify=iris.target
)

# Pipeline guarantees the scaler is fitted on training data only
pipe = make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=5))
pipe.fit(X_train, y_train)
pred = pipe.predict(X_test)

print(f"Accuracy: {accuracy_score(y_test, pred):.4f}")       # 0.9556
print(classification_report(y_test, pred, target_names=iris.target_names))

# Choosing k by cross-validation — the elbow plot
import matplotlib.pyplot as plt

k_range = range(1, 31)
cv_scores = []
for k in k_range:
    pipe = make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=k))
    scores = cross_val_score(pipe, iris.data, iris.target, cv=10, scoring="accuracy")
    cv_scores.append(scores.mean())

best_k = k_range[int(np.argmax(cv_scores))]
print(f"Best k = {best_k} with CV accuracy {max(cv_scores):.4f}")

plt.figure(figsize=(9, 4.5))
plt.plot(k_range, cv_scores, marker="o", color="#168B99")
plt.axvline(best_k, color="#ef4444", linestyle="--", label=f"best k = {best_k}")
plt.xlabel("k (number of neighbours)")
plt.ylabel("10-fold CV accuracy")
plt.title("Choosing k for KNN")
plt.legend(); plt.grid(alpha=0.3); plt.show()

# Demonstrating WHY scaling matters
data = pd.DataFrame({
    "age":    [25, 45, 30, 50, 28, 47],
    "income": [50000, 50100, 52000, 51000, 49500, 53000],
    "buys":   ["No", "Yes", "No", "Yes", "No", "Yes"],
})
X = data[["age", "income"]].values
y = data["buys"].values
new_customer = [[26, 51500]]

unscaled = KNeighborsClassifier(n_neighbors=3).fit(X, y)
scaled = make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=3)).fit(X, y)

print("Without scaling:", unscaled.predict(new_customer)[0])
print("With scaling:   ", scaled.predict(new_customer)[0])
# The two often disagree — the unscaled version is effectively ignoring age.

# KNN for REGRESSION — average instead of vote
from sklearn.neighbors import KNeighborsRegressor
from sklearn.metrics import mean_squared_error, r2_score

X_r = np.array([[1],[2],[3],[4],[5],[6],[7],[8]])
y_r = np.array([2.1, 4.2, 6.1, 8.3, 9.8, 12.2, 14.1, 16.0])

knr = KNeighborsRegressor(n_neighbors=3)
knr.fit(X_r, y_r)
print("Prediction for x=4.5:", knr.predict([[4.5]])[0].round(3))
# Average of the 3 nearest y values

# Distance-weighted voting — closer neighbours count more
knr_w = KNeighborsRegressor(n_neighbors=3, weights="distance").fit(X_r, y_r)
print("Distance-weighted:", knr_w.predict([[4.5]])[0].round(3))

Weighted KNN

Instead of every neighbour getting one equal vote, weight votes by 1/distance so nearer neighbours influence the result more. Set weights="distance". This reduces sensitivity to a poorly chosen k.

The Curse of Dimensionality

As the number of features grows, all points become roughly equidistant from each other — the notion of "nearest" loses meaning, and KNN degrades badly.

Advantages and Disadvantages

KNN vs K-Means — The Classic Confusion

They share only the letter k. Keep them strictly separate in exams.

Applications

Recommendation systems ("users similar to you"), handwriting and image recognition, credit-risk scoring, medical diagnosis from similar past cases, anomaly detection (a point with distant neighbours is anomalous), and missing-value imputation (KNNImputer, seen in Unit 1).

Next: the regression counterpart the syllabus names explicitly — linear regression.