Machine Learning 📂 Supervised Learning · 14 of 19 213 min read

K-Nearest Neighbors

Learn how KNN classifies new data by finding the K most similar training examples, explore Euclidean and Manhattan distance, the critical importance of feature scaling, how to choose K, and why this elegant lazy learner still powers real production systems.

🌐 Language
▶️
This Tutorial Has Eight Simulators

Look for the interactive boxes: Ask the Neighbours (Section 01), Distance Metrics (03), Hand Calculator (04), KNN Regression (05), Choosing K (06), Scaling Matters (07), The Curse of Dimensionality (08) and How a KD-Tree Finds Neighbours (11). Every neighbour search in them runs live in your browser.

Section 01

The Story That Explains KNN

📖 Real-World Analogy
You Are Who Your Neighbours Are
You move to a new city and find a flat at an unfamiliar address. You have no idea whether the area is expensive or cheap. How do you estimate a fair rent?

You do not read economic theory. You do not build a complex model. You simply ask: “What are the five nearest flats paying right now?” If four of them pay £2,000 a month and one pays £1,200, you estimate the average: £1,840 — and you are probably close.

Now a doctor wants to know if a new patient has diabetes. She looks up the five most similar patients in the hospital records — similar age, similar BMI, similar glucose. Four of the five have diabetes. Her prediction: diabetes. A majority vote. No formula needed.

That is K-Nearest Neighbors (KNN) in full: find the K most similar examples you have already seen, then let them vote (classification) or take their average (regression).
🦥
KNN Is a “Lazy Learner”

Most algorithms learn a compact model during training. KNN does the opposite: it stores the whole training set and does all the real work at prediction time. “Training” is almost instant (scikit-learn may just build a search tree, see Section 11), but predictions can be slow on big data — every new point must be compared with the stored points.

Try It — Ask the Neighbours

Click anywhere to place a new point. Watch KNN find its neighbours one by one, then count the votes. Switch to distance-weighted votes and see how close neighbours get louder votes.

🏘️ Ask the Neighbours60 points in 3 classes. Click anywhere to place a new point (★).
K (number of neighbours)
● blue   ■ red   ▲ green   ★ new point   dashed circle = reaches the K-th neighbour
Section 02

How KNN Works — Four Steps

01
Choose K and a Distance Metric
Decide how many neighbours to ask (K) and how to measure “closeness” — Euclidean, Manhattan, or another distance. Also decide how to scale the features (Section 07).
02
Compute the Distance to the Training Points
For a new point, compute its distance to the stored training points. With brute force and 10,000 training points, that is 10,000 distances for every single prediction. Search trees can skip most of them (Section 11).
03
Select the K Nearest Points
Take the K smallest distances. These are the K nearest neighbours — the training examples most similar to the new point. All other points are ignored.
04
Combine the K Labels
Classification → the class with the most votes wins. Regression → the mean (or weighted mean) of the K values. No model is updated — the stored data is the model.
Section 03

Distance Metrics — How “Closeness” Is Measured

KNN depends completely on its idea of similarity. Different distance metrics can pick different neighbours — and give different predictions.

Euclidean Distance (p = 2)
d = √Σ(xᵢ − yᵢ)²
The straight-line, “as the crow flies” distance. The default in scikit-learn. Squaring makes one big difference count a lot.
Manhattan Distance (p = 1)
d = Σ|xᵢ − yᵢ|
The sum of absolute differences along each axis — like walking a city grid. A single large difference counts less than in Euclidean, so it is a little more robust to outliers. It still needs scaled features.
Minkowski Distance (General)
d = (Σ|xᵢ − yᵢ|ᵖ)^(1/p)
The general form. p = 1 → Manhattan. p = 2 → Euclidean. p → ∞ → Chebyshev (the largest single difference). p can be tuned as a hyperparameter.
Hamming Distance
d = (1/n) × #{i : xᵢ ≠ yᵢ}
The fraction of positions where two vectors differ. For categorical or binary features — DNA letters, yes/no answers, one-hot data. Not for continuous numbers.
Metric Best For Effect of One Large Difference scikit-learn Parameter
Euclidean Continuous features, low dimensions — the default Strong — it is squared metric='euclidean'
Manhattan Continuous features, many dimensions, noisy data Weaker metric='manhattan'
Minkowski General — tune p Grows with p metric='minkowski', p=2
Hamming Categorical or binary features Each position counts 1 metric='hamming'
Cosine Text vectors — direction matters more than length Ignores vector length metric='cosine'

Try It — Distance Metrics

Slide p from 1 to ∞. The shaded shape — all points at the same distance — changes from a diamond to a circle to a square. Red-ringed points are neighbours that Euclidean distance would not have chosen.

📐 Distance MetricsThe shaded shape holds exactly the K nearest points for the chosen metric. Click to move the ★.
Minkowski p
K
● one of the K nearest   red ring = would NOT be chosen by Euclidean   ━ straight line   ┅ city-block path
Section 04

Step-by-Step Manual Calculation

Let us classify one new patient by hand, with K = 3 and Euclidean distance. We have five patients with two features — Age and Glucose — and a known diabetes label.

Patient Age Glucose Diabetes?
P12580No
P235150Yes
P345180Yes
P42070No
P550200Yes
NEW40160?
🧮 Step 1 — Euclidean Distance to Each Patient
d(NEW, P1)
√((40−25)² + (160−80)²) = √(225 + 6400) = √6625 = 81.39
d(NEW, P2)
√((40−35)² + (160−150)²) = √(25 + 100) = √125 = 11.18
d(NEW, P3)
√((40−45)² + (160−180)²) = √(25 + 400) = √425 = 20.62
d(NEW, P4)
√((40−20)² + (160−70)²) = √(400 + 8100) = √8500 = 92.20
d(NEW, P5)
√((40−50)² + (160−200)²) = √(100 + 1600) = √1700 = 41.23
🧮 Step 2 — Sort the Distances and Keep K = 3
1st
P2 — distance 11.18 — label: Yes
2nd
P3 — distance 20.62 — label: Yes
3rd
P5 — distance 41.23 — label: Yes
Ignored
P1 (81.39) and P4 (92.20) — too far, not part of the vote
🗳️ Step 3 — Majority Vote Among the 3 Neighbours
Tally
Yes: 3 votes (P2, P3, P5)  |  No: 0 votes
Result
Unanimous → Predicted: Diabetes = YES ✅
⚠️
Look at the Numbers Inside the Square Roots

Glucose ranges over 130 units (70–200), age over only 30 (20–50). After squaring, glucose differences are often dozens of times larger: for P1, 6400 comes from glucose and only 225 from age. Age barely affects which neighbours are chosen. In a real project you must scale the features first — or glucose silently overrules everything else.

Try It — Hand Calculator

Move the new patient’s age and glucose, change K, and switch the scaling. Watch the glucose share of distance² — and how the ranking changes when both features are scaled.

🧮 Hand Calculator — 5 PatientsMove the new patient. Change K and the scaling. Ticked rows are the K nearest.
new patient’s age
new patient’s glucose
K
Section 05

Classification vs Regression

🗳️ KNN Classification (Majority Vote)
NeighbourLabelDistance
Neighbour 1Spam0.12
Neighbour 2Spam0.18
Neighbour 3Ham0.25
Neighbour 4Spam0.31
Neighbour 5Ham0.40
PredictionSpam (3 vs 2 votes)
📊 KNN Regression (Average Value)
NeighbourPrice (£k)Distance
Neighbour 12950.08
Neighbour 23100.15
Neighbour 32800.22
Neighbour 43250.30
Neighbour 53000.38
Prediction£302,000 (mean)

predict_proba in a KNN classifier is simply the share of the K neighbours in each class — here Spam 3/5 = 60%, Ham 2/5 = 40%.

Try It — KNN Regression

Each prediction is the average of the K nearest training values. Click to move the query line. Small K follows the noise; large K flattens the curve.

📈 KNN Regression45 noisy points from a hidden curve (grey dashes). Click to move the query line.
K
━ KNN prediction   ● the K neighbours of the query   ● their average
Section 06

Choosing K — The Most Important Decision

📖 The Goldilocks Problem
K = 1 Memorises. K = N Ignores Everything.
K = 1: ask only the single nearest neighbour. If that one point is an outlier or mislabelled, the answer is wrong. The model copies every quirk of the training data — 100% training accuracy, but noticeably lower test accuracy. This is overfitting.

K = N (all training points): every query gets the majority class of the whole dataset — the position of the new point is ignored. This is the most extreme underfitting.

The right K sits in between: small enough to keep the local shape, large enough to smooth out noise. Find it with cross-validation.
K Value Decision Boundary Bias Variance Risk
K = 1 Very jagged Very low Very high Overfitting — follows noise
Small K (3–7) Jagged but smoother Low Moderate–high Often good for small, clean datasets
Medium K Smooth Balanced ✅ Moderate Often best for noisy data — check with CV
Large K Very smooth High Low Underfitting — local shape lost
K = N None — one class everywhere Maximum Zero Always predicts the majority class
🔢 Practical Rules for Choosing K
①
Use cross-validation. Try odd values of K from 1 up to about √n (n = training size). Plot CV accuracy against K and pick a K where the score is high and stable.
②
Prefer odd K for two classes — with uniform votes this avoids tie votes. When a tie still happens (for example with 3+ classes), scikit-learn picks the class that comes first in its sorted class list — not the class of the closest neighbour.
③
K ≈ √n is only a rough starting point — e.g. 1,000 training samples → K ≈ 31. On small, clean data the best K is often much smaller (on Iris below it is 5).
④
Noisy or overlapping data → larger K to smooth out label noise. Clean, well-separated data → smaller K to keep the local shape.

Try It — Choosing K

Move K from 1 to 159 and watch the border change from jagged to smooth to flat. The small chart shows train and test accuracy for every K at once.

🎚️ Choosing K160 noisy two-moon points. Test accuracy is measured on 600 new points.
K (odd)
shading = predicted class (stronger = more neighbours agree)   ● on the curve = best K
accuracy for every odd K
Section 07

Feature Scaling — Essential for KNN

KNN’s core operation is measuring distance. A feature with large numbers will dominate every distance and make the other features almost invisible.

❌ Without Scaling — Distance Is Only Income
FeaturePatient APatient BDiff²
Age (years)30311
Income (£)30,00070,0001,600,000,000
BMI22.535.0156.25
Euclidean d40,000.00 — almost entirely income
✅ With StandardScaler — Every Feature Counts
FeaturePatient APatient BDiff²
Age (z-score)−0.85−0.710.0196
Income (z-score)−0.921.154.2849
BMI (z-score)−1.200.954.6225
Euclidean d2.99 — income and BMI both contribute
📏
StandardScaler
z = (x − μ) / σ
Shifts each feature to mean 0 and standard deviation 1. The most common choice for KNN. Outliers affect μ and σ — with many outliers, consider RobustScaler.
✅ Good general default
📐
MinMaxScaler
x′ = (x − min) / (max − min)
Squeezes each feature into [0, 1]. Keeps the shape of the distribution. Natural for bounded values (e.g. pixel values 0–255 → 0–1). Very sensitive to outliers — one extreme value squashes all the others.
✅ Good for bounded features
🛡️
RobustScaler
x′ = (x − median) / (Q3 − Q1)
Uses the median and the interquartile range instead of mean and standard deviation, so a few extreme values hardly change the scaling. Good for skewed data with outliers.
✅ Good when outliers are present

How Much Does Scaling Matter? A Real Test

from sklearn.datasets import load_wine
from sklearn.model_selection import cross_val_score
from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler, MinMaxScaler, RobustScaler
from sklearn.pipeline import make_pipeline

X, y = load_wine(return_X_y=True)          # 13 chemical features of 178 wines
print(f"Feature ranges: from {X.max(axis=0).min():.2f} (largest value of the smallest feature)"
      f" to {X.max(axis=0).max():.0f} (proline)")

models = {
    "No scaling":     KNeighborsClassifier(n_neighbors=5),
    "StandardScaler": make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=5)),
    "MinMaxScaler":   make_pipeline(MinMaxScaler(),   KNeighborsClassifier(n_neighbors=5)),
    "RobustScaler":   make_pipeline(RobustScaler(),   KNeighborsClassifier(n_neighbors=5)),
}
for name, model in models.items():
    print(f"{name:15s} CV accuracy = {cross_val_score(model, X, y, cv=5).mean():.4f}")
Output
Feature ranges: from 0.66 (largest value of the smallest feature) to 1680 (proline) No scaling CV accuracy = 0.6913 StandardScaler CV accuracy = 0.9494 MinMaxScaler CV accuracy = 0.9495 RobustScaler CV accuracy = 0.9384

Without scaling, KNN gets only 69% on the Wine data: the “proline” feature (values up to 1,680) controls every distance. Any of the three scalers lifts accuracy to about 94–95%.

Try It — Scaling Matters

Without scaling, the 7 “nearest” neighbours of the ★ form a thin vertical strip — near in income, but spread over many ages. Tick StandardScaler first.

📏 Scaling MattersRisk depends on income AND age. KNN with K = 7. Click to move the ★.
■ risky   ● safe   outlined = the 7 nearest neighbours of ★
Section 08

The Curse of Dimensionality

📖 Why KNN Struggles in High Dimensions
The Neighbourhood That Keeps Expanding
Imagine finding your 5 nearest neighbours on a 1D street. They are very close — perhaps 10 metres away. Now add a second dimension (a 2D city). With the same number of people, your 5 nearest neighbours are further away. Add a third dimension (a tall building) and they move further still.

In 100 dimensions, your “nearest” neighbour is almost as far away as your farthest one. When all distances are nearly the same, “nearest” carries little information and KNN loses its signal. This is the curse of dimensionality — a main reason KNN struggles on high-dimensional data.
Dimensions Points to fill a grid with 10 cells per feature Nearest vs farthest distance KNN usefulness
1D 10 Very different Excellent
2D 100 Clearly different Very good
10D 10¹⁰ Getting similar Declining
100D 10¹⁰⁰ Nearly the same Weak — unless the data really lives in fewer dimensions
1000D 10¹⁰⁰⁰ Almost identical (random data) Needs dimensionality reduction

Here is the effect measured on 1,000 random points:

import numpy as np
rng = np.random.default_rng(0)

print(f"{'dims':>5} {'nearest':>9} {'farthest':>9} {'farthest/nearest':>17}")
for d in [1, 2, 10, 100, 1000]:
    X = rng.random((1000, d))                 # 1,000 random points in a unit cube
    q = rng.random(d)                         # one random query point
    dist = np.sqrt(((X - q) ** 2).sum(axis=1))
    print(f"{d:>5} {dist.min():>9.3f} {dist.max():>9.3f} {dist.max() / dist.min():>17.1f}")
Output
dims nearest farthest farthest/nearest 1 0.000 0.986 2575.7 2 0.017 1.128 67.1 10 0.453 1.942 4.3 100 3.343 4.786 1.4 1000 12.128 13.548 1.1

In 2D the farthest point is 67 times further away than the nearest. In 1,000 dimensions it is only 1.1 times further — almost every point is “equally near”. (Real data is less extreme because its features are related, but the trend is the same.)

Useless features cause the same problem. Each one adds random noise to every distance:

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

rng = np.random.default_rng(0)
X, y = make_classification(n_samples=600, n_features=5, n_informative=5, n_redundant=0, random_state=0)
for n_noise in [0, 5, 20, 50, 200]:
    Xn = np.hstack([X, rng.normal(size=(len(X), n_noise))])   # add useless random columns
    acc = cross_val_score(make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=7)),
                          Xn, y, cv=5).mean()
    print(f"5 useful + {n_noise:3d} useless features -> CV accuracy {acc:.3f}")
Output
5 useful + 0 useless features -> CV accuracy 0.933 5 useful + 5 useless features -> CV accuracy 0.870 5 useful + 20 useless features -> CV accuracy 0.807 5 useful + 50 useless features -> CV accuracy 0.763 5 useful + 200 useless features -> CV accuracy 0.587

Try It — The Curse of Dimensionality

Increase the number of dimensions and watch the distance histogram squeeze to the right. Then switch to useless features and watch KNN accuracy fall.

🌌 The Curse of Dimensionality400 random points in a unit cube and one random query point.
dimensions
nearest ÷ farthest, for every dimension
🔧
Fighting the Curse

1. Remove useless features (feature selection) — often the biggest win.
2. Reduce dimensions with PCA inside the pipeline, and tune the number of components with cross-validation together with K. UMAP can also be used (it can transform new data); t-SNE cannot, because it has no way to map new points, so it is only for visualisation.
3. For text, use cosine distance on TF-IDF or embedding vectors.

Section 09

Python Implementation

KNN Classification — Iris Dataset

from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline
from sklearn.metrics import classification_report

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

# StandardScaler inside the Pipeline: the scaler only ever sees training data
pipe = Pipeline([
    ("scaler", StandardScaler()),
    ("knn", KNeighborsClassifier(
        n_neighbors=5,          # K - tune with cross-validation
        metric="euclidean",     # distance function
        weights="uniform",      # every neighbour gets one vote
        algorithm="auto",       # let scikit-learn pick brute / kd_tree / ball_tree
    )),
])
pipe.fit(X_train, y_train)
y_pred = pipe.predict(X_test)

print(f"Accuracy: {pipe.score(X_test, y_test):.4f}\n")
print(classification_report(y_test, y_pred, target_names=iris.target_names, digits=3))

# predict_proba = share of the K neighbours in each class
y_prob = pipe.predict_proba(X_test)
for i in range(5):
    print(f"  Sample {i+1}: {iris.target_names[y_pred[i]]:12s} ({y_prob[i].max()*100:3.0f}% of neighbours agree)")
Output
Accuracy: 0.9333 precision recall f1-score support setosa 1.000 1.000 1.000 10 versicolor 0.833 1.000 0.909 10 virginica 1.000 0.800 0.889 10 accuracy 0.933 30 macro avg 0.944 0.933 0.933 30 weighted avg 0.944 0.933 0.933 30 Sample 1: setosa (100% of neighbours agree) Sample 2: virginica ( 60% of neighbours agree) Sample 3: versicolor (100% of neighbours agree) Sample 4: versicolor (100% of neighbours agree) Sample 5: setosa (100% of neighbours agree)

93.3% on the 30 test flowers (two versicolor/virginica mix-ups). Sample 2 shows the uncertainty well: only 3 of its 5 neighbours (60%) agree.

Finding the Best K with Cross-Validation

from sklearn.model_selection import cross_val_score

k_scores = []
for k in range(1, 32, 2):                      # odd K: 1, 3, 5, ... 31
    pipe_k = Pipeline([("scaler", StandardScaler()),
                       ("knn", KNeighborsClassifier(n_neighbors=k))])
    scores = cross_val_score(pipe_k, X_train, y_train, cv=5, scoring="accuracy")
    k_scores.append((k, scores.mean(), scores.std()))

best = max(s[1] for s in k_scores)
print(f"{'K':>4} {'CV accuracy':>12} {'Std':>8}")
print("-" * 28)
for k, mean, std in k_scores:
    print(f"{k:>4} {mean:>12.4f} {std:>8.4f}{'  <- best' if mean == best else ''}")
best_k = min(k for k, m, s in k_scores if m == best)   # on ties, take the smallest K
print(f"\nSmallest K with the best CV score: {best_k}")
Output
K CV accuracy Std ---------------------------- 1 0.9417 0.0425 3 0.9583 0.0373 5 0.9667 0.0312 <- best 7 0.9583 0.0373 9 0.9583 0.0264 11 0.9583 0.0264 13 0.9500 0.0408 15 0.9583 0.0264 17 0.9583 0.0264 19 0.9417 0.0204 21 0.9333 0.0333 23 0.9250 0.0312 25 0.9000 0.0333 27 0.8917 0.0333 29 0.8917 0.0333 31 0.8917 0.0333 Smallest K with the best CV score: 5

K = 5 is best (96.7%), and K between 3 and 17 is almost as good. Above K ≈ 21 the score drops — with only about 40 flowers per class, large K starts mixing in the other species.

KNN Regression — House Prices

import pandas as pd
from sklearn.neighbors import KNeighborsRegressor
from sklearn.impute import SimpleImputer
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline
from sklearn.metrics import r2_score, mean_absolute_error

# California housing (1990 census), 20,640 districts
url = "https://raw.githubusercontent.com/ageron/handson-ml2/master/datasets/housing/housing.csv"
df = pd.read_csv(url)
X = df.drop(columns=["median_house_value", "ocean_proximity"])
y = df["median_house_value"]
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

for weights in ["uniform", "distance"]:
    knn_reg = Pipeline([
        ("impute", SimpleImputer(strategy="median")),   # KNN cannot handle missing values
        ("scaler", StandardScaler()),
        ("knn", KNeighborsRegressor(n_neighbors=10, weights=weights)),
    ])
    knn_reg.fit(X_train, y_train)
    y_pred = knn_reg.predict(X_test)
    print(f"weights={weights:8s}  R² = {r2_score(y_test, y_pred):.4f}   "
          f"MAE = ${mean_absolute_error(y_test, y_pred):,.0f}")
Output
weights=uniform R² = 0.7077 MAE = $41,753 weights=distance R² = 0.7145 MAE = $41,190

Distance weighting helps a little here (R² 0.708 → 0.715). Note the SimpleImputer: KNN cannot work with missing values, and this dataset has 207 missing total_bedrooms. A Random Forest on the same data reaches R² ≈ 0.81, so KNN is not the best model for this table.

Implementing KNN from Scratch

import numpy as np
from collections import Counter
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier

def euclidean_distance(x1, x2):
    """Straight-line distance between two points."""
    return np.sqrt(np.sum((x1 - x2) ** 2))

class KNNClassifier:
    def __init__(self, k=5):
        self.k = k

    def fit(self, X, y):
        """No real training - just remember the data."""
        self.X_train, self.y_train = X, y
        return self

    def predict(self, X):
        return np.array([self._predict_one(x) for x in X])

    def _predict_one(self, x):
        distances = [euclidean_distance(x, x_tr) for x_tr in self.X_train]  # 1. all distances
        k_idx = np.argsort(distances)[:self.k]                               # 2. K smallest
        k_labels = self.y_train[k_idx]                                       # 3. their labels
        return Counter(k_labels).most_common(1)[0][0]                        # 4. majority vote

iris = load_iris()
X_train, X_test, y_train, y_test = train_test_split(
    iris.data, iris.target, test_size=0.2, random_state=42, stratify=iris.target)
sc = StandardScaler().fit(X_train)
X_train_sc, X_test_sc = sc.transform(X_train), sc.transform(X_test)

ours = KNNClassifier(k=5).fit(X_train_sc, y_train).predict(X_test_sc)
skl  = KNeighborsClassifier(n_neighbors=5).fit(X_train_sc, y_train).predict(X_test_sc)
print(f"Scratch KNN accuracy:      {np.mean(ours == y_test):.4f}")
print(f"scikit-learn KNN accuracy: {np.mean(skl == y_test):.4f}")
print(f"Same predictions: {np.array_equal(ours, skl)}")
Output
Scratch KNN accuracy: 0.9333 scikit-learn KNN accuracy: 0.9333 Same predictions: True

Our 15-line version makes exactly the same predictions as scikit-learn. The algorithm really is that simple.

Section 10

Weighted KNN — Closer Neighbours Vote Louder

Standard KNN gives every neighbour one equal vote, whatever its distance. A neighbour at distance 0.01 counts as much as one at distance 5. Weighted KNN gives each neighbour a vote proportional to 1 / distance — closer means more influence.

Uniform Weights (Default)
weight(i) = 1
Every neighbour counts the same. Simple and stable. Can be misled when the K-th neighbour is much further away than the first.
Distance Weights
weight(i) = 1 / distance(i)
Closer neighbours count more. Use weights='distance'. Side effect: train accuracy is always 100%, because each training point is its own neighbour at distance 0 — so judge it only with cross-validation.
from sklearn.model_selection import GridSearchCV

pipe = Pipeline([("scaler", StandardScaler()), ("knn", KNeighborsClassifier())])
param_grid = {
    "knn__n_neighbors": [3, 5, 7, 9, 11, 15, 21],
    "knn__weights":     ["uniform", "distance"],
    "knn__metric":      ["euclidean", "manhattan"],
}
grid = GridSearchCV(pipe, param_grid, cv=5, scoring="accuracy", n_jobs=-1)
grid.fit(X_train, y_train)

print("Best parameters: ", grid.best_params_)
print(f"Best CV accuracy: {grid.best_score_:.4f}")
print(f"Test accuracy:    {grid.score(X_test, y_test):.4f}")
n_best = (grid.cv_results_["rank_test_score"] == 1).sum()
print(f"Settings tied for first place: {n_best} of {len(grid.cv_results_['params'])}")
Output
Best parameters: {'knn__metric': 'euclidean', 'knn__n_neighbors': 5, 'knn__weights': 'uniform'} Best CV accuracy: 0.9667 Test accuracy: 0.9333 Settings tied for first place: 7 of 28

On Iris, the simple setting wins: Euclidean, K = 5, uniform weights — and 7 of the 28 settings tie for first place. Distance weighting is worth trying, but it is not automatically better.

Section 11

Search Algorithms — How scikit-learn Finds Neighbours Fast

🔍
Brute Force
algorithm='brute'
Computes the distance to every training point: O(n × d) per query. Works with any metric, uses fast matrix operations, and is the best choice for small data, sparse data or many dimensions.
✅ Any metric; best in high dimensions
❌ Slow for very many points in low dimensions
🌲
KD-Tree
algorithm='kd_tree'
Splits the space into boxes, one feature at a time, like a binary tree. A query only opens the boxes that could contain a closer point — about O(log n) in low dimensions. Excellent in low dimensions; gets slower than brute force as dimensions grow.
✅ Very fast for low d
❌ Breaks down in high dimensions
🎯
Ball-Tree
algorithm='ball_tree'
Groups points into nested balls (hyperspheres) instead of boxes. Handles somewhat higher dimensions and clustered data better than a KD-tree, and supports more metrics. Building it takes a little longer.
✅ More robust than KD-tree
❌ Still slow in very high dimensions
⚡
algorithm='auto' — Let scikit-learn Decide

The default 'auto' uses brute force when the data is sparse, the metric is not supported by the trees, K is large compared with n, or there are more than 15 features. Otherwise it uses a KD-tree (or a ball-tree for metrics the KD-tree does not support). Override it only after a benchmark. 

import time
import numpy as np
from sklearn.neighbors import NearestNeighbors

rng = np.random.default_rng(0)
for d in [3, 50]:
    X = rng.normal(size=(100_000, d))
    Q = rng.normal(size=(2_000, d))
    for algo in ["brute", "kd_tree", "ball_tree"]:
        nn = NearestNeighbors(n_neighbors=5, algorithm=algo)
        t0 = time.perf_counter(); nn.fit(X); t_fit = time.perf_counter() - t0
        t0 = time.perf_counter(); nn.kneighbors(Q); t_q = time.perf_counter() - t0
        print(f"d={d:>2}  {algo:9s}  build: {t_fit:6.3f}s   2,000 queries: {t_q:6.3f}s")
    auto = NearestNeighbors(n_neighbors=5).fit(X)
    print(f"d={d:>2}  'auto' chose: {auto._fit_method}\n")
Output
d= 3 brute build: 0.001s 2,000 queries: 0.462s d= 3 kd_tree build: 0.063s 2,000 queries: 0.015s d= 3 ball_tree build: 0.067s 2,000 queries: 0.115s d= 3 'auto' chose: kd_tree d=50 brute build: 0.008s 2,000 queries: 0.601s d=50 kd_tree build: 0.650s 2,000 queries: 18.435s d=50 ball_tree build: 0.395s 2,000 queries: 12.294s d=50 'auto' chose: brute

In 3 dimensions the KD-tree answers 2,000 queries about 30× faster than brute force. In 50 dimensions it is about 30× slower — the boxes no longer help — and 'auto' correctly chooses brute force.

Try It — How a KD-Tree Finds Neighbours

Press Build the tree to watch the space being split. Then click anywhere: the yellow boxes are the only ones the search had to open.

🌲 How a KD-Tree Finds Neighbours300 points. The tree splits the space in half again and again. Click to move the ★.
tree depth shown
purple lines = splits (thicker = earlier)   ▭ boxes the search opened   ━ nearest neighbour
Section 12

Full Pipeline — Breast Cancer Diagnosis

A complete, honest pipeline: scaling, optional PCA, and K — all tuned together with cross-validation, then tested once.

from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split, GridSearchCV
from sklearn.preprocessing import StandardScaler
from sklearn.decomposition import PCA
from sklearn.pipeline import Pipeline
from sklearn.metrics import classification_report

cancer = load_breast_cancer()
X, y = cancer.data, cancer.target            # 30 features; 0 = malignant, 1 = benign
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42, stratify=y)

pipe = Pipeline([
    ("scaler", StandardScaler()),
    ("pca", PCA(random_state=42)),
    ("knn", KNeighborsClassifier()),
])
# Tune the number of PCA components together with K ('passthrough' = no PCA)
param_grid = {
    "pca": ["passthrough", PCA(n_components=5), PCA(n_components=10)],
    "knn__n_neighbors": [3, 5, 7, 9, 11],
    "knn__weights": ["uniform", "distance"],
}
grid = GridSearchCV(pipe, param_grid, cv=5, scoring="f1", n_jobs=-1)
grid.fit(X_train, y_train)

print("Best:", {k: str(v) for k, v in grid.best_params_.items()})
print(f"Best 5-fold CV F1: {grid.best_score_:.4f}")
print(f"Test accuracy:     {grid.best_estimator_.score(X_test, y_test):.4f}\n")
print(classification_report(y_test, grid.predict(X_test), target_names=cancer.target_names, digits=3))
Output
Best: {'knn__n_neighbors': '3', 'knn__weights': 'uniform', 'pca': 'PCA(n_components=5)'} Best 5-fold CV F1: 0.9775 Test accuracy: 0.9474 precision recall f1-score support malignant 0.950 0.905 0.927 42 benign 0.946 0.972 0.959 72 accuracy 0.947 114 macro avg 0.948 0.938 0.943 114 weighted avg 0.947 0.947 0.947 114

The best setting reduces 30 features to 5 PCA components with K = 3 (CV F1 0.978). On the 114 test patients it reaches 94.7% accuracy, but it misses 4 of 42 malignant tumours (recall 0.905). In a medical setting that recall matters more than accuracy — you might lower the decision threshold, or prefer a model with higher recall.

Section 13

When to Use KNN

✅
Low-Dimensional Data
KNN works best with a modest number of meaningful features (roughly under 20). Then distance is meaningful and neighbours are really similar.
few, relevant features
✅
Irregular Decision Boundaries
KNN can follow any boundary shape without a kernel or feature engineering. K controls how smooth the boundary is.
complex, local patterns
✅
Small to Medium Datasets
On small data KNN is fast enough and uses every example directly. It has only a few settings to tune (K, metric, weights, scaling).
up to tens of thousands of rows
✅
Quick Baseline and Similarity Search
Easy to set up with few assumptions — a good baseline. The same neighbour search powers “find similar items” features.
baseline · similar items
❌
Huge Datasets with Real-Time Needs
Exact search over millions of points per query is slow and needs all the data in memory. Use approximate nearest-neighbour (ANN) libraries such as FAISS, Annoy or ScaNN.
use FAISS / Annoy / ScaNN
❌
High-Dimensional Raw Data
Raw TF-IDF text, raw pixels and genomics data suffer from the curse of dimensionality. Reduce dimensions or use learned embeddings first — or use a linear model or SVM.
reduce dimensions first
Section 14

KNN vs Other Classifiers

Property KNN Random Forest SVM (RBF) Logistic Reg.
Training time Almost none Moderate Slow on large data Fast
Prediction time Slow — up to O(n × d) per query Moderate Moderate Fastest
Memory usage Stores all data Stores trees Stores support vectors Just coefficients
Feature scaling needed Essential No Essential Recommended
Non-linear boundaries Naturally Excellent Via kernels Only with added features
High-dimensional data Struggles — curse of dimensionality Moderate Good Good
Interpretability High — show the neighbours Feature importance Low with RBF High — coefficients
Adding new data Easy — just add points (search tree is rebuilt) Retrain Retrain Possible (SGD, partial_fit)
Section 15

Strengths vs Weaknesses

✅ Strengths
Almost no training time
Very simple to understand and explain
Handles many classes naturally
Few assumptions — only that similar points have similar labels
Non-parametric — can learn any boundary shape
New data can be added without retraining a model
Predictions are explainable — show the actual neighbours
Same idea for classification and regression
❌ Weaknesses
Slow predictions on big data
Stores the entire training set — high memory use
Feature scaling is essential — forgetting it is costly
Struggles in high dimensions — curse of dimensionality
Sensitive to irrelevant features — all features count equally
Sensitive to class imbalance — the majority class wins more votes
No built-in feature importance
Cannot handle missing values without imputation
Section 16

Real-World Applications

Recommendation Systems
🎬
  • User-based collaborative filtering
  • “Users like you also watched…”
  • Item-to-item similarity
  • Classic approach in early recommenders
Medical Decision Support
🏥
  • Find similar patient records
  • Spot unusual vital signs (anomaly detection)
  • Case-based reasoning
  • Explainable — show real cases
Search and Images
🖼️
  • MNIST digits: about 97% with plain KNN
  • Reverse image search on embeddings
  • Semantic search in vector databases
  • Face verification on face embeddings
Section 17

Golden Rules

📍 K-Nearest Neighbors — Golden Rules
1
Always scale the features before computing distances. A feature with larger numbers silently dominates every prediction. Put StandardScaler() inside a Pipeline to avoid leakage. On the Wine data this one step raised accuracy from 69% to 95%.
2
Tune K with cross-validation — never guess. Try odd values from 1 up to about √n_train, plot CV accuracy against K, and choose a K where the score is high and stable. √n is a starting point only.
3
Try both weights='uniform' and weights='distance'. Distance weights often help when neighbours are at very different distances, but not always (on Iris, uniform won). Let cross-validation decide — and ignore the 100% training accuracy that distance weights always give.
4
With many features, reduce dimensions first. Put PCA in the pipeline (scaler → PCA → KNN) and tune n_components together with K. On the breast cancer data, 5 components beat all 30 features.
5
Remove irrelevant features. KNN treats every feature as equally important, so useless features add noise to every distance. In Section 08, adding 20 useless features dropped accuracy from 93% to 81%. Use domain knowledge, SelectKBest, or feature importance from another model.
6
Handle class imbalance explicitly. Majority voting favours the larger class. KNN has no class_weight option, so oversample the minority class (e.g. SMOTE from imbalanced-learn, applied only to training data), try distance weights, or tune the decision threshold on predict_proba. Evaluate with F1, recall or AUC — not accuracy.
7
For large-scale search, use approximate nearest neighbours (ANN). With millions of points and real-time needs, exact search gets too slow. FAISS (Meta), Annoy (Spotify) and ScaNN (Google) find almost-exact neighbours in milliseconds, even in billion-point collections.
8
Use KNN’s explainability. You can always justify a prediction by showing the actual K neighbours from the training data: “We predicted diabetes because these five similar patients also had diabetes.” That is a clear, convincing explanation for doctors, managers and auditors.