What you’ll learn

• how KNN predicts without ever “training” a model in the usual sense
• the distance formula it actually computes, worked by hand on a tiny example
• why small vs large kk trades variance for bias
• why feature scaling isn’t optional for any distance-based model
• KNN’s real costs: slow predictions and the curse of dimensionality

What KNN does

KNN predicts a label by looking at the k closest training points and taking a majority vote among their labels. There’s no cost function to minimize and no weights to learn — fit()fit() on a KNeighborsClassifierKNeighborsClassifier just stores the training data. All the actual work happens at prediction time, when it measures distances against every stored point. This makes KNN a lazy learner (also called instance-based learning), in contrast to Logistic Regression or an SVM, which are eager learners that build an explicit model during fit()fit() and then predict cheaply.

  flowchart LR
  N[New point] --> D[Compute distances to training points]
  D --> K[Pick k nearest]
  K --> V[Vote / majority class]

The distance calculation, by hand

By default, KNN measures Euclidean distance between two points. For two features, that’s just the Pythagorean theorem:

distance(a, b) = sqrt( (a_1 - b_1)^2 + (a_2 - b_2)^2 + ... )distance(a, b) = sqrt( (a_1 - b_1)^2 + (a_2 - b_2)^2 + ... )

Say you have three labeled points and one new point to classify:

• A = (1, 2)A = (1, 2), label 0
• B = (2, 3)B = (2, 3), label 0
• C = (8, 8)C = (8, 8), label 1
• new point Q = (2, 2)Q = (2, 2)

import numpy as np
 
points = {"A": (1, 2), "B": (2, 3), "C": (8, 8)}
labels = {"A": 0, "B": 0, "C": 1}
q = np.array([2, 2])
 
for name, p in points.items():
    dist = np.linalg.norm(np.array(p) - q)
    print(f"{name}: distance = {dist:.2f}, label = {labels[name]}")
 
# A: distance = 1.00, label = 0
# B: distance = 1.00, label = 0
# C: distance = 8.49, label = 1

import numpy as np
 
points = {"A": (1, 2), "B": (2, 3), "C": (8, 8)}
labels = {"A": 0, "B": 0, "C": 1}
q = np.array([2, 2])
 
for name, p in points.items():
    dist = np.linalg.norm(np.array(p) - q)
    print(f"{name}: distance = {dist:.2f}, label = {labels[name]}")
 
# A: distance = 1.00, label = 0
# B: distance = 1.00, label = 0
# C: distance = 8.49, label = 1

With k=1k=1 or k=2k=2, the two closest points (AA and BB) both vote label 0, so QQ is classified as 0. CC is far away and barely matters — that’s the entire algorithm: measure, sort, vote.

How to choose k

kk is the single most important hyperparameter, and it directly controls the bias/variance trade-off:

• small kk (e.g. k=1k=1) → the prediction depends on a single nearby point, so the decision boundary can be jagged and easily thrown off by one mislabeled or noisy point. This is high variance, low bias — the model fits the training data very closely and can overfit.
• large kk (e.g. k=50k=50 on a small dataset) → each prediction averages over many neighbors, smoothing the boundary out. This is high bias, low variance — the model can underfit, especially if kk grows so large it starts pulling in points from a completely different region.

In practice you rarely guess kk — you sweep a range of odd values (odd avoids tie votes in binary problems) with cross-validation and pick whichever scores best on held-out data:

from sklearn.model_selection import cross_val_score
from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import load_iris
 
X, y = load_iris(return_X_y=True)
 
for k in [1, 3, 5, 11, 21]:
    knn = KNeighborsClassifier(n_neighbors=k)
    scores = cross_val_score(knn, X, y, cv=5)
    print(f"k={k}: {scores.mean():.3f}")
 
# k=1: 0.960
# k=3: 0.967
# k=5: 0.973
# k=11: 0.980
# k=21: 0.967

from sklearn.model_selection import cross_val_score
from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import load_iris
 
X, y = load_iris(return_X_y=True)
 
for k in [1, 3, 5, 11, 21]:
    knn = KNeighborsClassifier(n_neighbors=k)
    scores = cross_val_score(knn, X, y, cv=5)
    print(f"k={k}: {scores.mean():.3f}")
 
# k=1: 0.960
# k=3: 0.967
# k=5: 0.973
# k=11: 0.980
# k=21: 0.967

Notice accuracy rises, peaks, then falls again as kk grows too large — the classic bias/variance curve.

Scaling is critical

KNN uses distances (Euclidean by default), and distance formulas treat every feature’s raw numbers as equally meaningful — they have no idea one column is “age in years” (0-100) and another is “income in dollars” (0-200,000).

import numpy as np
 
# feature 1: age (small range), feature 2: income (huge range)
a = np.array([30, 50_000])
b = np.array([32, 51_000])
 
print(round(np.linalg.norm(a - b), 2))
# 1000.0  -> almost entirely driven by the $1,000 income gap;
# the 2-year age difference barely registers at all

import numpy as np
 
# feature 1: age (small range), feature 2: income (huge range)
a = np.array([30, 50_000])
b = np.array([32, 51_000])
 
print(round(np.linalg.norm(a - b), 2))
# 1000.0  -> almost entirely driven by the $1,000 income gap;
# the 2-year age difference barely registers at all

A 2-year age gap should matter, but it’s completely swamped by the income gap’s raw scale. StandardScalerStandardScaler (subtract mean, divide by standard deviation) puts every feature on the same footing before distances are computed:

from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
 
knn_pipeline = Pipeline([
    ("scaler", StandardScaler()),
    ("model", KNeighborsClassifier(n_neighbors=5)),
])

from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
 
knn_pipeline = Pipeline([
    ("scaler", StandardScaler()),
    ("model", KNeighborsClassifier(n_neighbors=5)),
])

Wrapping the scaler and the model in one PipelinePipeline also protects you from a subtle form of data leakage: fitting StandardScalerStandardScaler on the whole dataset before splitting would let information about the test set’s mean/variance leak into training. Fitting inside a pipeline (or inside each cross-validation fold) keeps the scaler blind to whatever it hasn’t seen yet.

Pros and cons

Pros:

• simple to understand and explain — “vote with your nearest neighbors”
• no training step at all, so adding new labeled data is instant
• naturally handles multiclass problems, and even multilabel ones (below)
• makes no assumption about the shape of the decision boundary — it can follow arbitrarily curvy class regions given enough data

Cons:

• prediction is slow on large datasets: a naive KNN has to compare a new point against every stored training point (scikit-learn speeds this up with tree-based indexes like KDTreeKDTree/BallTreeBallTree, but it’s still far from free)
• stores the entire training set in memory
• suffers from the curse of dimensionality: as the number of features grows, all points start looking roughly equidistant from each other, and “nearest” stops being a meaningful concept — KNN tends to need dimensionality reduction (PCA) or feature selection first on high-dimensional data
• sensitive to irrelevant features and to class imbalance (a locally dominant majority class can out-vote a real nearby minority-class point)

Common pitfalls

• forgetting to scale features (see above) — this alone can wreck accuracy
• picking an even kk for a binary problem, which allows tied votes (scikit-learn breaks ties by picking whichever class appears first in sorted order — not necessarily what you’d want)
• using KNN on very high-dimensional data (hundreds of raw features) without reducing dimensionality first
• forgetting that “training” a KNN pipeline is nearly instantaneous, but predicting is where all the real computational cost lives — the opposite of most other classifiers in this phase

Scikit-learn example

from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
 
knn = Pipeline(
    steps=[
        ("scaler", StandardScaler()),
        ("model", KNeighborsClassifier(n_neighbors=5)),
    ]
)

from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
 
knn = Pipeline(
    steps=[
        ("scaler", StandardScaler()),
        ("model", KNeighborsClassifier(n_neighbors=5)),
    ]
)

When KNN is a good baseline

• small to medium datasets
• when decision boundary is not too complex

Beyond a single label: multilabel classification

Géron’s book uses KNeighborsClassifierKNeighborsClassifier for a nice trick most other classifiers can’t do out of the box: multilabel classification, where each instance gets more than one label at once. His example builds two binary targets for MNIST digits — “is this digit large (7, 8, or 9)?” and “is this digit odd?” — stacks them into one array, and fits a single KNN on both:

from sklearn.neighbors import KNeighborsClassifier
import numpy as np
 
y_train_large = (y_train >= 7)
y_train_odd = (y_train % 2 == 1)
y_multilabel = np.c_[y_train_large, y_train_odd]
 
knn_clf = KNeighborsClassifier()
knn_clf.fit(X_train, y_multilabel)
 
knn_clf.predict([some_digit])
# array([[False, True]])  -> not large, and odd: correct for the digit 5

from sklearn.neighbors import KNeighborsClassifier
import numpy as np
 
y_train_large = (y_train >= 7)
y_train_odd = (y_train % 2 == 1)
y_multilabel = np.c_[y_train_large, y_train_odd]
 
knn_clf = KNeighborsClassifier()
knn_clf.fit(X_train, y_multilabel)
 
knn_clf.predict([some_digit])
# array([[False, True]])  -> not large, and odd: correct for the digit 5

Mini-checkpoint

Try k = 3, 5, 11 and compare validation performance.

Visualize it

k-NN doesn’t really “learn” — to classify a new point it just finds the kk closest known points and takes their majority vote. Here the new point (square) is connected to its 5 nearest neighbors and coloured by whichever class wins:

🧪 Try It Yourself

Exercise 1 – Train-Test Split

Exercise 2 – Fit a Linear Model

Exercise 3 – Evaluate with MSE

Exercise 4 – Classify by Majority Vote

Next

Continue to Support Vector Machines (SVM) to see a classifier that instead of voting, finds the widest possible margin between classes.