K-Nearest Neighbours

A model that does not fit anything

K-nearest neighbours has no training step worth the name. Calling .fit() stores the data. When a prediction is needed, it finds the k rows most similar to the new one and takes a vote among their labels. That is the entire algorithm.

This makes it the clearest example of the instance-based family described in types of machine learning systems: nothing is compressed into parameters, so the whole training set must ship with the model and every prediction is a search. Training is instant and prediction is slow, which is the reverse of almost everything else in this course.

Two consequences follow, and both are more important than the algorithm itself. Similarity is measured by distance, so any column with large units dominates the result. And distance becomes meaningless as the number of columns grows, which makes this method unusually fragile on wide data.

Choosing k

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

wine = load_wine(as_frame=True)
X, y = wine.data, wine.target

for k in [1, 3, 5, 11, 25, 51]:
    s = cross_val_score(make_pipeline(StandardScaler(), KNeighborsClassifier(k)),
                        X, y, cv=5)
    print(f"k={k:<3} mean {s.mean():.3f}  sd {s.std():.3f}")
# k=1   mean 0.950  sd 0.033
# k=3   mean 0.944  sd 0.040
# k=5   mean 0.949  sd 0.038
# k=11  mean 0.955  sd 0.022
# k=25  mean 0.961  sd 0.029
# k=51  mean 0.961  sd 0.033

Read the standard deviation column alongside the mean. Every value of k from 1 to 51 lands between 0.944 and 0.961, with fold-to-fold variation of 0.022 to 0.040. On 178 rows the differences are inside the noise, so claiming that k=25 beats k=3 here would be overreading.

What k controls is still real. A small k makes the boundary follow individual points, which fits training data closely and reacts to noise. A large k smooths it towards the majority class. The usual starting point is the square root of the row count, and k=1 deserves particular suspicion: it reproduces the training labels perfectly and tells you nothing about generalisation.

Use an odd k for binary problems so votes cannot tie.

for weights in ["uniform", "distance"]:
    s = cross_val_score(make_pipeline(StandardScaler(),
                                      KNeighborsClassifier(11, weights=weights)), X, y, cv=5)
    print(f"{weights:<9} {s.mean():.3f}")
# uniform   0.955
# distance  0.961

for metric in ["euclidean", "manhattan", "chebyshev"]:
    s = cross_val_score(make_pipeline(StandardScaler(),
                                      KNeighborsClassifier(11, metric=metric)), X, y, cv=5)
    print(f"{metric:<10} {s.mean():.3f}")
# euclidean  0.955
# manhattan  0.978
# chebyshev  0.921

weights="distance" lets closer neighbours count for more, which usually helps and costs nothing. The metric choice is worth a quick sweep: Manhattan distance beat Euclidean by 0.023 here, which is a larger gap than anything k produced. Manhattan often wins on higher-dimensional data because it is less dominated by any single column’s difference.

Why k-nearest neighbours needs scaling more than anything else

Every distance is computed across all columns at once, so a column measured in hundreds contributes thousands to the squared distance while a column measured in decimals contributes fractions. The model then clusters on units rather than meaning.

Your first model in scikit-learn showed the size of this effect on exactly this dataset: 0.667 unscaled against 0.933 scaled. There is no situation in which you run this algorithm on raw columns of mixed units.

The deeper problem is that distance itself degrades as columns multiply.

rng = np.random.default_rng(4)
for d in [2, 20, 200]:
    points = rng.normal(0, 1, (500, d))
    query = rng.normal(0, 1, (1, d))
    dist = np.sqrt(((points - query) ** 2).sum(axis=1))
    print(f"dim {d:<4} nearest {dist.min():.2f}  farthest {dist.max():.2f}"
          f"  ratio {dist.max() / dist.min():.2f}")
# dim 2    nearest 0.05  farthest 3.69  ratio 70.24
# dim 20   nearest 4.05  farthest 9.90  ratio 2.44
# dim 200  nearest 17.83  farthest 22.83  ratio 1.28

In two dimensions the farthest point is 70 times further away than the nearest. In 200 dimensions it is 1.28 times further. Every point is roughly equidistant from every other, so “nearest” stops meaning anything and the vote becomes arbitrary.

That is the curse of dimensionality, and it damages this algorithm specifically:

from sklearn.linear_model import LogisticRegression
import pandas as pd

for extra in [0, 10, 50, 200]:
    Xa = X.copy()
    if extra:
        noise = pd.DataFrame(rng.normal(0, 1, (len(X), extra)),
                             columns=[f"n{i}" for i in range(extra)])
        Xa = pd.concat([Xa.reset_index(drop=True), noise], axis=1)
    knn = cross_val_score(make_pipeline(StandardScaler(), KNeighborsClassifier(5)),
                          Xa, y, cv=5).mean()
    log = cross_val_score(make_pipeline(StandardScaler(),
                                        LogisticRegression(max_iter=5000)), Xa, y, cv=5).mean()
    print(f"+{extra:<4} noise cols: knn {knn:.3f}   logistic {log:.3f}")
# +0    noise cols: knn 0.949   logistic 0.983
# +10   noise cols: knn 0.910   logistic 0.967
# +50   noise cols: knn 0.871   logistic 0.961
# +200  noise cols: knn 0.708   logistic 0.894

Two hundred irrelevant columns cost k-nearest neighbours 0.241 of accuracy and logistic regression 0.089. A linear model can set a useless coefficient near zero. A distance calculation cannot ignore a column; every irrelevant dimension adds noise to every comparison.

So the pruning methods in feature selection techniques are not a nice-to-have here. Keep the column count low, and prefer a different family when you cannot.

When to use it, and when not to

It earns its place on small datasets with few, meaningful columns, where the decision boundary is genuinely irregular, and where you want to justify a prediction by naming the five similar cases it came from. That last property is undervalued: “we charged this customer the same as these five similar customers” is an explanation a non-technical person accepts.

Avoid it when you have more than a few dozen columns, when the training set is large enough that scanning it per prediction breaks your latency budget, or when classes are badly imbalanced, since the majority class wins most votes by weight of numbers alone. Full parameter details are in the KNeighborsClassifier reference.

Frequently Asked Questions

How do you choose the value of k in KNN?

Cross-validate across a range and read the standard deviation alongside the mean, because the differences are often inside the noise. Start near the square root of your row count, use an odd number for binary problems, and treat k=1 with suspicion since it memorises the training set.

Why does KNN need feature scaling?

Distance is computed across all columns simultaneously, so a column measured in hundreds overwhelms one measured in decimals and the model effectively ignores most of your features. On the wine dataset, scaling moved accuracy from 0.667 to 0.933 with no other change.

What is the curse of dimensionality in KNN?

As columns multiply, all points become roughly equidistant and “nearest” loses meaning. With 200 random dimensions, the farthest of 500 points was only 1.28 times further than the nearest. Adding 200 noise columns cost KNN 0.241 accuracy against 0.089 for logistic regression.

Key Takeaways

• Always put a scaler before KNeighborsClassifier, since distance across mixed units measures nothing but the largest column.
• Cross-validate k and compare the spread across folds, because differences that look meaningful often sit inside fold-to-fold variation.
• Sweep the metric parameter as well as k, as Manhattan distance beat Euclidean by more than any value of k changed things here.
• Cut your column count hard before using this algorithm, given that 200 irrelevant columns cost it nearly a quarter of its accuracy.
• Choose a different family when the training set is large, because every prediction scans the stored data and latency grows with it.