Start learning

K Nearest Neighbours (KNN)

Lesson 28. About 6 minutes.

KNN classifies a new point by looking at the K training points closest to it and taking a vote. There's no real training step: the model is the data.

Your Path Through This Lesson

0 of 5 done

By the End of This Lesson You Can
  • Classify a point by hand with KNN.
  • Compute Euclidean and Manhattan distances.
  • Choose K and understand why scaling matters so much.

The Idea

"Tell me who your neighbours are, and I'll tell you who you are." To classify a new student, find the K most similar students in the training data and go with the majority.

  1. Choose K (say 3).
  2. Measure the distance from the new point to every training point.
  3. Take the K closest.
  4. Classification: majority vote. Regression: average their values.

Measuring Distance

For two points and :

Distance Formula Picture
Euclidean Straight line, "as the crow flies"
Manhattan Walking along city blocks

Between (2, 3) and (5, 7): Euclidean ; Manhattan .

A Worked Example

Six students, with hours studied and classes attended out of 10, and whether they passed:

Student Hours Attendance Result
Noman 1 3 Fail
Lamia 2 4 Fail
Rafi 3 2 Fail
Tanvir 6 7 Pass
Arif 7 8 Pass
Mitu 8 6 Pass

A new student studied 5 hours and attended 6 classes. Euclidean distances from (5, 6):

Student Distance
Tanvir (6, 7) nearest
Arif (7, 8) 2nd
Mitu (8, 6) 3rd
Lamia (2, 4)
Rafi (3, 2)
Noman (1, 3)

With K = 3, the neighbours are Tanvir, Arif and Mitu: three passes. Prediction: pass.

python
import numpy as np
from sklearn.neighbors import KNeighborsClassifier

X = np.array([[1, 3], [2, 4], [3, 2], [6, 7], [7, 8], [8, 6]])
y = np.array(["Fail", "Fail", "Fail", "Pass", "Pass", "Pass"])

knn = KNeighborsClassifier(n_neighbors=3).fit(X, y)
dist, idx = knn.kneighbors([[5, 6]])
print("nearest distances:", dist.round(2))
print("prediction       :", knn.predict([[5, 6]]))
Output
nearest distances: [[1.41 2.83 3.  ]]
prediction       : ['Pass']

Choosing K

K Behaviour
Very small (1) Follows every noisy point: overfitting, high variance
Moderate (5–15) Usually a good balance
Very large Averages over too much, ignoring local patterns: underfitting

Use an odd K for two classes so votes can't tie, and choose it with cross-validation.

Scaling Is Essential

KNN uses raw distances, so a feature measured in big numbers drowns out the rest. If one feature is income (0–100,000) and another is age (0–100), distance is basically just income. Always scale features before KNN.

python
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import cross_val_score
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

Xc, yc = load_breast_cancer(return_X_y=True)

raw = cross_val_score(KNeighborsClassifier(5), Xc, yc, cv=5).mean()
scaled = cross_val_score(make_pipeline(StandardScaler(), KNeighborsClassifier(5)), Xc, yc, cv=5).mean()
print(f"without scaling: {raw:.3f}")
print(f"with scaling   : {scaled:.3f}")

for k in [1, 3, 5, 11, 25, 75]:
    s = cross_val_score(make_pipeline(StandardScaler(), KNeighborsClassifier(k)), Xc, yc, cv=5).mean()
    print(f"k={k:>2}: CV accuracy {s:.3f}")
Output
without scaling: 0.928
with scaling   : 0.965
k= 1: CV accuracy 0.954
k= 3: CV accuracy 0.960
k= 5: CV accuracy 0.965
k=11: CV accuracy 0.965
k=25: CV accuracy 0.953
k=75: CV accuracy 0.935

Strengths and Weaknesses

Strengths Weaknesses
Simple and easy to explain Slow predictions on big datasets: every prediction scans all training points
No training time Needs scaled features
Handles any number of classes Struggles with many features (the curse of dimensionality)
Works for regression too (KNeighborsRegressor) Sensitive to irrelevant features
Note

KNN is an instance-based (or "lazy") learner: it stores the training data and does all the work at prediction time, instead of learning a formula in advance.

Try It Yourself
  1. Predict the new student with K = 5 by hand. Who are the five neighbours, and does the vote change?
  2. Try KNeighborsClassifier(5, weights="distance"), which gives closer neighbours a bigger vote, on the breast-cancer data.
The Key Idea

KNN predicts from the K closest training points. Choose K with cross-validation and always scale the features.

Summary

  • KNN: find the K closest training points, then vote (classification) or average (regression).
  • Distance: Euclidean (straight line) or Manhattan (city blocks).
  • Small K overfits, large K underfits; pick K with cross-validation.
  • Always scale features first.
  • Next part: decision trees, which ask a series of yes/no questions.