34 - KNN: classifying by looking at neighbours (and the curse of dimensionality)

You move to a new neighbourhood and you want to know whether the restaurant on the corner is any good. You have no model: you ask the five neighbours living closest to you and follow the majority. That is K-Nearest Neighbors (KNN, "the K closest neighbours"): to classify a new point, look at the K most similar training points and let their labels vote. There is no training phase in the classical sense, no parameter to optimise: the "model" is the dataset itself.

It is the ideal algorithm for understanding three concepts that will stay with you for a long time: the choice of a distance, the trade-off between bias and variance controlled by K, and the curse of dimensionality, which explains why "more features" is not always better.

What a "distance" is

For two houses in a city you can measure the distance as the crow flies or by following the streets. For two examples with n features the situation is identical: each example is a point in an n-dimensional space, and a distance is a rule that assigns to every pair of points a non-negative number: zero only for coincident points, symmetric, and obeying the "triangle inequality" (going from A to C costs no more than going through B). The choice of distance is a modelling choice: it says what "similar" means for your problem.

The algorithm and the mathematics

Given a test point x:

1. Compute the distance between x and every training point.
2. Take the K points with the smallest distance (the set N_K(x)).
3. Classification: return the most frequent class among those K. Regression: return the mean of their values.

The cost is almost entirely in the first step, because every prediction requires the distance from every training point. Sorting and voting are cheap by comparison. Moving from classification to regression changes only the third step (vote versus mean), which is why everything that follows about distances and K holds for both tasks.

The most common distance is the Minkowski distance of order p:

d(x, z) = ( Σ_j |x_j − z_j|^p )^(1/p)

p = 2  →  Euclidean  √(Σ (x_j − z_j)²)     "as the crow flies"
p = 1  →  Manhattan  Σ |x_j − z_j|         "along grid-like streets"

The vote can be weighted: a very close neighbour counts more than one at the edge of the K. With weight w_i = 1/d(x, x_i), the score of class c is

score(c) = Σ_{i ∈ N_K(x)} w_i · [y_i = c]       ŷ = argmax_c score(c)

where [y_i = c] equals 1 if neighbour i is of class c and 0 otherwise. KNN is a lazy learner: all the work is postponed to prediction time. Cost of one prediction: O(n·d) comparisons with n training points and d features, and the whole training set must be kept in memory.

Implementation by hand

We work with the Wine dataset (178 wines, 13 chemical measurements, 3 cultivars). The delicate part is computing all the distances in vectorised form, without loops, and keeping the shapes under control:

import numpy as np
from sklearn.datasets import load_wine
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler

class KNNDaZero:
    def __init__(self, k=5, pesato=False):
        self.k, self.pesato = k, pesato

    def fit(self, X, y):
        self.X, self.y = X, y
        self.classi = np.unique(y)
        return self

    def predict(self, X):
        # X: (m, d)   self.X: (n, d)   ->  d2: (m, n)
        d2 = ((X[:, None, :] - self.X[None, :, :]) ** 2).sum(axis=2)
        idx = np.argsort(d2, axis=1)[:, :self.k]            # (m, k) indices of the k neighbours
        etichette = self.y[idx]                              # (m, k)
        dist = np.sqrt(np.take_along_axis(d2, idx, axis=1))  # (m, k)
        w = 1.0 / (dist + 1e-9) if self.pesato else np.ones_like(dist)
        punteggi = np.stack([(w * (etichette == c)).sum(axis=1) for c in self.classi], axis=1)
        return self.classi[punteggi.argmax(axis=1)]

Xw, yw = load_wine(return_X_y=True)
Xtr, Xte, ytr, yte = train_test_split(Xw, yw, test_size=0.3, stratify=yw, random_state=0)

mio = KNNDaZero(k=5).fit(Xtr, ytr)
lib = KNeighborsClassifier(n_neighbors=5).fit(Xtr, ytr)
print("without scaling  hand-made: %.3f   sklearn: %.3f" % ((mio.predict(Xte) == yte).mean(), lib.score(Xte, yte)))
print("identical predictions:", bool((mio.predict(Xte) == lib.predict(Xte)).all()))

without scaling  hand-made: 0.722   sklearn: 0.722
identical predictions: True

The drawing shows the algorithm with K = 5: the new point (green star) has 3 blue and 2 red neighbours inside the circle, so blue wins. The circle is not a fixed radius: it has the size needed to contain exactly K points.

What the code does. In the predict method the distance line uses NumPy broadcasting: X[:, None, :] has shape (m, 1, d) and self.X[None, :, :] has shape (1, n, d); subtracting them NumPy "stretches" the dimensions of length 1 and produces an (m, n, d) tensor with all the coordinate-by-coordinate differences; squaring and summing over the feature axis gives the (m, n) matrix of squared distances between every test point and every training point. The square root is not needed for sorting, because the root is increasing. np.argsort returns the indices ordered from the closest; the first K are kept. self.y[idx] retrieves the labels of the neighbours (shape (m, K)).

Finally, for each class the weights of the neighbours of that class are summed and the class with the highest score is chosen.

The predictions coincide with those of the library, but the accuracy is only 0.722. The reason is the most common KNN trap, and it is in plain sight: the scale of the features.

Trap no. 1: if the features have different scales, the biggest one wins

In the Wine dataset the feature "proline" has values in the hundreds or thousands, while others lie between 0 and 1. In the Euclidean distance the difference on "proline" dominates everything: the neighbours are chosen by looking at practically that column alone. Standardising (subtracting the mean and dividing by the standard deviation, with parameters computed on the training set only) puts all the features on the same footing:

print("range per feature (min..max) of the first 3 and of 'proline' (last):")
print(np.round(Xtr.min(axis=0)[[0, 1, 2, 12]], 2), np.round(Xtr.max(axis=0)[[0, 1, 2, 12]], 2))

scaler = StandardScaler().fit(Xtr)                  # mean and std ONLY from the training set
Ztr, Zte = scaler.transform(Xtr), scaler.transform(Xte)
mio_s = KNNDaZero(k=5).fit(Ztr, ytr)
print("with scaling     hand-made: %.3f" % (mio_s.predict(Zte) == yte).mean())

range per feature (min..max) of the first 3 and of 'proline' (last):
[ 11.41   0.74   1.7  278.  ] [  14.83    5.8     3.23 1680.  ]
with scaling     hand-made: 0.963

The first two lines of the listing print the minima and maxima of four columns, to show the difference in scale. Then StandardScaler().fit(Xtr) learns mean and standard deviation from the training set only, and transform applies the same transformation to training and test: the test set is scaled with the training parameters, never with its own, otherwise it is data leakage (if the problem is not familiar, the process of an ML project explains it).

Same algorithm, same data: the accuracy goes from 0.722 to 0.963, and the whole difference is in the scale ("proline" ranges from 278 to 1680, the second feature from 0.74 to 5.8). Distances are the heart of KNN; if they make no sense, nothing makes sense.

A = ( 3,  4)   clayey
B = ( 5,  1)   sandy
C = (-4,  2)   clayey
D = ( 1,  6)   sandy

Choosing K: the bias-variance trade-off

K controls the complexity of the model, in the opposite way to what you might expect:

• K = 1: the boundary follows every single point, including the noisy ones. High variance, low bias: overfitting. On the training set the accuracy is always 1.0, because the nearest neighbour of a training point is itself.
• Large K: the vote is averaged over wide regions and the boundary becomes smooth. Low variance, high bias: underfitting. In the extreme case K = n the most frequent class is always predicted.

The two extremes draw a U-shaped curve of the test error: on the left the model is too flexible and chases the noise, on the right it is too smooth to see the structure. The right value is in between and depends on the noise of the problem; there is no universal K. The experiment below lines up eight values of K on the same dataset so you can see the U in numbers.

The loop trains one model per K on the standardised dataset (Ztr, Zte are the already scaled training and test sets) and prints the accuracy on both. The last value, len(Ztr), is the extreme case K = n.

for k in (1, 3, 5, 9, 15, 31, 61, len(Ztr)):
    m = KNeighborsClassifier(n_neighbors=k).fit(Ztr, ytr)
    print("k=%3d  train %.3f   test %.3f" % (k, m.score(Ztr, ytr), m.score(Zte, yte)))

k=  1  train 1.000   test 1.000
k=  3  train 0.944   test 0.963
k=  5  train 0.968   test 0.963
k=  9  train 0.952   test 0.963
k= 15  train 0.952   test 0.981
k= 31  train 0.976   test 0.981
k= 61  train 0.952   test 0.963
k=124  train 0.403   test 0.389

With K = 1 the training accuracy is 1.000 by construction: looking at it tells you nothing. The last row uses K = number of training samples (124): every prediction is the vote of the whole training set, that is always the most frequent class, and the accuracy collapses (extreme underfitting). Be careful also when reading the test: there are 54 samples, so a single sample more or less moves the accuracy by 0.019. Differences of that order between one K and another (0.963 against 0.981) are noise, not a ranking. The right value is chosen with cross-validation on the training set (GridSearchCV on n_neighbors), never on the test set. For binary classification an odd K is convenient, to avoid ties in the vote.

Trap no. 2: the curse of dimensionality

KNN rests on the idea that "near" has a meaning. In many dimensions, geometry ruins it. To see it without taking my word for it, measure: generate 1000 uniform random points in d dimensions, take a reference point and compute the distance from the nearest and the farthest one.

The generator has a fixed seed (default_rng(0)), so the numbers are repeatable. The ratio (max − min)/min is the quantity of interest: if it is large, "the nearest" is much nearer than the others; if it tends to zero, the points are all almost equidistant.

rng = np.random.default_rng(0)
for d in (2, 10, 100, 1000):
    P = rng.uniform(size=(1000, d))
    q = rng.uniform(size=(1, d))
    dist = np.sqrt(((P - q) ** 2).sum(axis=1))
    print("d=%4d  nearest neighbour %.2f   farthest %.2f   (max-min)/min = %.2f" % (
        d, dist.min(), dist.max(), (dist.max() - dist.min()) / dist.min()))

d=   2  nearest neighbour 0.01   farthest 1.33   (max-min)/min = 134.62
d=  10  nearest neighbour 0.47   farthest 2.11   (max-min)/min = 3.48
d= 100  nearest neighbour 3.35   farthest 4.65   (max-min)/min = 0.39
d=1000  nearest neighbour 12.17   farthest 13.55   (max-min)/min = 0.11

With d = 2 the ratio (max − min)/min is 134.6, with d = 1000 it is 0.11: the farthest is only 11% farther than the nearest. As d grows the ratio is squashed towards zero: the nearest and the farthest point are at almost the same distance, so "the nearest" loses meaning. This phenomenon is called distance concentration. The other side of the problem is that the data become sparse: to cover a 100-dimensional space with the same density as a 2-dimensional one you would need exponential numbers of samples.

The most insidious practical effect is the addition of irrelevant features. Each noise column contributes to the distance as much as an informative one. We add columns of Gaussian noise to the Wine dataset (already standardised) and measure the test:

For each amount of noise the listing concatenates (np.hstack) to the standardised dataset as many columns of Gaussian numbers independent of the class, on both training and test, and retrains KNN with K = 5. The only thing that changes from one row to the next is the number of useless columns.

for rumore in (0, 10, 50, 200, 1000):
    r = np.random.default_rng(1)
    Atr = np.hstack([Ztr, r.normal(size=(len(Ztr), rumore))])
    Ate = np.hstack([Zte, r.normal(size=(len(Zte), rumore))])
    m = KNeighborsClassifier(n_neighbors=5).fit(Atr, ytr)
    print("noise columns added: %4d  ->  test %.3f" % (rumore, m.score(Ate, yte)))

noise columns added:    0  ->  test 0.963
noise columns added:   10  ->  test 0.944
noise columns added:   50  ->  test 0.796
noise columns added:  200  ->  test 0.648
noise columns added: 1000  ->  test 0.519

The 13 informative columns are always the same, but as the useless columns increase the accuracy falls from 0.963 to 0.944 with 10 columns, 0.796 with 50, 0.648 with 200 and down to 0.519 with 1000 (the most frequent class alone would score 0.389). Remedies: feature selection, dimensionality reduction (PCA, which you will find in dimensionality reduction), learned distances, or simply another algorithm that is less sensitive.

How to make it fast: spatial indexes

Comparing with all the points (brute force) costs O(n·d) per prediction. Structures such as the KD-tree and the ball tree organise the points so as to skip whole distant regions: in few dimensions the search drops towards O(log n), but in many dimensions the advantage vanishes for the same reason as before: the scikit-learn guide indicates the KD-tree as very fast below about 20 dimensions and, beyond that, even slower than brute force. scikit-learn chooses by itself with algorithm="auto". For millions of high-dimensional vectors, approximate nearest-neighbour search libraries are used, which give up a small part of the precision in exchange for a lot of speed.

Trade-offs

• Pros: conceptually simple, no training, arbitrarily complex boundaries, works for both classification and regression, updated by simply adding points.
• Cons: slow prediction and memory proportional to the training set; sensitive to scale and to irrelevant features; suffers in high dimensionality; with imbalanced classes the neighbours of the majority class are statistically more numerous.
• Use it as a quick baseline on small datasets with few dimensions and scaled features; avoid it with many features, many samples or tight latency requirements.

The pros and cons have a single root: KNN learns nothing and keeps the data. That is why it is simple to understand and to update, and why it is heavy at prediction time and fragile when the data are badly scaled or have useless columns. As a baseline it is hard to beat in simplicity; as a model to put into production it requires you to have checked latency and memory.

Other real traps

• Evaluating KNN on the training set with K = 1 gives 1.0: the point is its own neighbour. Always evaluate on held-out data.
• Duplicates between train and test: with KNN they are lethal, because the duplicate in the training set is the perfect neighbour and the accuracy is inflated.
• Categorical features encoded with arbitrary numbers (red = 1, green = 2, blue = 3) invent a distance that does not exist. You need one-hot encoding or dedicated distances.
• Scaler fitted on the whole dataset: the same data leakage seen in the previous lessons. The scaler belongs in the Pipeline (see the process of an ML project).
• Accuracy on imbalanced classes: with large K the vote tends towards the majority class; check recall and precision.

The five traps fall into two groups. The first three (evaluation on the training set, duplicates, scaler on the whole dataset) inflate the number you measure; the other two (categorical features, imbalance) make the distance or the vote meaningless. In both cases the model runs without errors and gives a plausible accuracy: no message warns you.

Choosing the distance: four metrics on two datasets

The distance is the only "modelling hyperparameter" of KNN: it defines what "similar" means. We compare four choices. The Euclidean (length of the segment). The Manhattan (sum of absolute differences: less sensitive to the outliers of a single feature). The Chebyshev (the maximum difference on a single feature: two points are close only if they are close on all the features). The cosine (measures the angle between the vectors, ignoring the length: typical for texts or for count vectors). To have reliable numbers we use repeated cross-validation: 5 folds repeated 3 times, hence 15 estimates per metric, of which the mean and the deviation are reported.

The listing evaluates each metric with cross_val_score on the repeated cross-validation cv, on two datasets: Wine, standardised inside the Pipeline, and Digits, whose pixels already all share the same scale. algorithm="brute" is needed because not all the metrics are supported by the trees.

from sklearn.datasets import load_digits
from sklearn.model_selection import cross_val_score, RepeatedStratifiedKFold
from sklearn.pipeline import make_pipeline

cv = RepeatedStratifiedKFold(n_splits=5, n_repeats=3, random_state=0)
X_dg, y_dg = load_digits(return_X_y=True)

print("metric       wine (standardised)      digits (raw pixels)")
for metric in ("euclidean", "manhattan", "chebyshev", "cosine"):
    wine = cross_val_score(make_pipeline(StandardScaler(), KNeighborsClassifier(5, metric=metric, algorithm="brute")), Xw, yw, cv=cv)
    digits = cross_val_score(KNeighborsClassifier(5, metric=metric, algorithm="brute"), X_dg, y_dg, cv=cv)
    print("%-11s   %.3f +- %.3f           %.3f +- %.3f" % (metric, wine.mean(), wine.std(), digits.mean(), digits.std()))

metric       wine (standardised)      digits (raw pixels)
euclidean     0.961 +- 0.017           0.986 +- 0.006
manhattan     0.966 +- 0.023           0.983 +- 0.006
chebyshev     0.927 +- 0.033           0.973 +- 0.008
cosine        0.959 +- 0.027           0.984 +- 0.005

The results (K = 5, 15 estimates per cell): on Wine Euclidean 0.961, Manhattan 0.966, cosine 0.959, Chebyshev 0.927; on Digits 0.986, 0.983, 0.984 and 0.973. The first three are indistinguishable (half-point differences are smaller than the deviations, 0.017-0.027 on Wine and 0.005-0.006 on Digits). Chebyshev is clearly worse on both datasets: it makes sense, because it looks at a single feature (the most different one) and throws away the information of the others. The practical conclusion: the Euclidean metric is a good default, Manhattan deserves a try when there are outliers or many features, cosine when the length of the vectors is irrelevant, and comparisons must be made with several repetitions.

Weights and K with repeated cross-validation

In the section on choosing K we looked at a single test of 54 samples, and we warned that differences of 0.019 are noise. Let us redo the analysis the way it should be done, with 15 estimates for each value of K and comparing the uniform vote with the vote weighted by the inverse of the distance.

The double loop computes, for each K and for the two voting schemes (weights="uniform" and "distance", the latter proportional to the inverse of the distance as in our hand-made class), the mean and deviation over 15 estimates with the same cv as before.

print("K      uniform vote         weighted vote (1/distance)")
for k in (1, 5, 15, 31, 61):
    row = []
    for weights in ("uniform", "distance"):
        s = cross_val_score(make_pipeline(StandardScaler(), KNeighborsClassifier(k, weights=weights)), Xw, yw, cv=cv)
        row.append("%.3f +- %.3f" % (s.mean(), s.std()))
    print("%-5d  %s       %s" % (k, row[0], row[1]))

K      uniform vote         weighted vote (1/distance)
1      0.953 +- 0.036       0.953 +- 0.036
5      0.961 +- 0.017       0.963 +- 0.020
15     0.966 +- 0.023       0.966 +- 0.025
31     0.979 +- 0.019       0.981 +- 0.017
61     0.949 +- 0.028       0.962 +- 0.025

With K = 1 the two columns coincide (a single neighbour: the weight does not matter) at 0.953 ± 0.036. The accuracy grows with K up to a maximum around K = 31 (0.979-0.981 ± 0.02) and then drops: with K = 61 the vote includes too many neighbours from other classes, on a dataset of 178 examples. The two columns are practically identical, because with standardised features and well-separated classes the nearest neighbours agree anyway. Compared with the single 54-sample test, the repeated validation points to a better zone towards large K; but the deviation is 0.02 and the difference between K = 15 and K = 31 (1.3 points) is still of the same order, so read it as a tendency and not as a ranking.

Speed: when spatial trees help and when they do not

Above we said that the KD-tree and the ball tree speed up the search in few dimensions and lose their advantage in many. Let us measure it: 20,000 random points, 500 queries, in 3 and in 50 dimensions, with the three algorithms.

The listing builds, for 3 and for 50 dimensions, 20,000 Gaussian points and 500 queries, creates an index for each algorithm and times only the call to kneighbors. The labels are all zero: what matters here is the neighbour search, not the classification.

import time
rng = np.random.default_rng(0)
print("dimensions   brute force   KD-tree    ball tree   (seconds for 500 queries)")
for d in (3, 50):
    X_big, queries = rng.normal(size=(20000, d)), rng.normal(size=(500, d))
    times = []
    for algorithm in ("brute", "kd_tree", "ball_tree"):
        index = KNeighborsClassifier(5, algorithm=algorithm).fit(X_big, np.zeros(len(X_big), dtype=int))
        t0 = time.time(); index.kneighbors(queries); times.append(time.time() - t0)
    print("%10d   %11.3f   %8.3f   %9.3f" % ((d,) + tuple(times)))

# Output of one run; the times change at every run
# dimensions   brute force   KD-tree    ball tree   (seconds for 500 queries)
#          3         0.127      0.003       0.021
#         50         0.301      2.049       1.625

In 3 dimensions the KD-tree is clearly the fastest (about 0.002-0.003 s against 0.007-0.033 s for brute force and 0.011-0.014 s for the ball tree): it skips whole regions of the space. In 50 dimensions the picture reverses: brute force takes 0.05-0.10 s, the KD-tree 0.56-1.6 s (10 to 20 times more) and the ball tree 0.39-0.63 s (5 to 8 times more). Those are the minima and maxima of seven runs on a PC with 12 logical threads, Python 3.14.4, scikit-learn 1.8.0; the values change between runs, the order of the columns does not. The run shown above was made while the machine was busy with other jobs, so its absolute times are larger, but the order is the same.

The scikit-learn documentation explains the mechanism: for large dimensions the cost of the KD-tree approaches that of brute force and the overhead of the structure makes it slower. It is the curse of dimensionality applied to search structures: when the distances concentrate, the tree cannot exclude any region. algorithm="auto" already chooses on the basis of the data; for millions of vectors you need approximate search libraries.

KNN for regression, and the limit of extrapolation

KNN also works for predicting a number: it returns the mean of the values of the K neighbours. The balance between bias and variance is the same: a small K chases the noise, a large K smooths too much. We see it on 200 noisy points of a sine wave, with the squared error measured against the true function (we can, because the data are synthetic). Then we query the model outside the range of the data.

The listing generates 200 points of a sine wave with Gaussian noise of deviation 0.3, trains regressors with different K and measures the mean squared error against np.sin on a fine grid, not against the noisy data. The last part asks for a prediction at x = 7 and x = 10, outside the [0, 6] range of the data.

from sklearn.neighbors import KNeighborsRegressor

x = rng.uniform(0, 6, 200)
y = np.sin(x) + rng.normal(0, 0.3, 200)                          # sine + noise (standard deviation 0.3)
x_grid = np.linspace(0, 6, 300)

print("K      mean squared error with respect to the true function")
for k in (1, 5, 20, 100):
    model = KNeighborsRegressor(k).fit(x[:, None], y)
    print("%-5d  %.3f" % (k, ((model.predict(x_grid[:, None]) - np.sin(x_grid)) ** 2).mean()))

model = KNeighborsRegressor(5).fit(x[:, None], y)
outside = np.array([[7.0], [10.0]])
print("\npredictions outside the interval (x = 7 and 10):  %s   true values sin(x): %s" % (np.round(model.predict(outside), 3), np.round(np.sin([7, 10]), 3)))

K      mean squared error with respect to the true function
1      0.106
5      0.018
20     0.006
100    0.062

predictions outside the interval (x = 7 and 10):  [-0.376 -0.376]   true values sin(x): [ 0.657 -0.544]

The "U" profile is the expected one: K = 1 gives 0.106 (it chases the noise: the noise deviation is 0.3, variance 0.09, and the model inherits almost all of it); K = 5 drops to 0.018; K = 20 reaches the minimum, 0.006; K = 100 climbs back to 0.062 because the mean over 100 neighbours, in an interval of width 6 with 200 points, covers almost a third of the domain and flattens the curve. The most important point is in the last row: outside the range of the data, KNN does not extrapolate. For x = 7 and for x = 10 the prediction is the same, −0.376: the mean of the five nearest points, which are always the last ones of the interval (around x = 6). The true values are 0.657 and −0.544. Like trees, KNN predicts "piecewise constants" and, beyond the data, a constant: it is a model of interpolation, not of extrapolation. For phenomena that continue beyond the observed range (trends, growth) you need a model with structure, such as a regression.

KNN and imbalanced classes

With a rare class (here 5% positives), the majority vote among K neighbours penalises the minority: for a positive to be predicted, most of its K neighbours must be positive, and the positives are by definition few. We measure how recall and precision change as K grows.

The listing creates 4,000 examples with 5% positives (weights=[0.95, 0.05]), splits them in a stratified way and, for four values of K, prints accuracy, recall and precision of the rare class. The scaler is again inside the Pipeline.

from sklearn.datasets import make_classification
from sklearn.metrics import recall_score, precision_score

X_im, y_im = make_classification(n_samples=4000, n_features=6, n_informative=4, weights=[0.95, 0.05], class_sep=1.2, random_state=0)
X_im_tr, X_im_te, y_im_tr, y_im_te = train_test_split(X_im, y_im, test_size=0.3, stratify=y_im, random_state=0)

print("K     accuracy      recall   precision      (share of positives in the test set: %.3f)" % y_im_te.mean())
for k in (1, 5, 15, 45):
    m = make_pipeline(StandardScaler(), KNeighborsClassifier(k)).fit(X_im_tr, y_im_tr)
    pred = m.predict(X_im_te)
    print("%-5d %9.3f    %.3f    %.3f" % (k, m.score(X_im_te, y_im_te), recall_score(y_im_te, pred), precision_score(y_im_te, pred)))

K     accuracy      recall   precision      (share of positives in the test set: 0.055)
1         0.967    0.606    0.741
5         0.973    0.515    0.971
15        0.968    0.424    1.000
45        0.960    0.273    1.000

The accuracy stays high and almost constant (0.960-0.973), as always with imbalanced classes; it is recall and precision that tell the story. With K = 1 the recall is 0.606 and the precision 0.741. Raising K the precision rises (0.971 with K = 5, 1.000 with K = 15 and 45: every predicted positive really is one) but the recall collapses (0.515, 0.424, 0.273): with K = 45 the model finds fewer than one positive in three. The trade-off is the decision threshold, already seen, in disguise: with the majority vote the model declares positive if more than half of the K neighbours are, but this can be changed with predict_proba (the fraction of positive neighbours) and a lower threshold, for example 0.2. Another remedy is to balance the training set (oversampling of the rare class, taking care not to contaminate the validation). The message is the one of the process of an ML project: with imbalanced classes the accuracy lies, and a K chosen to maximise it leads the model towards "never finding the rare class".

Three experiments to try

Exercise 1. On the imbalanced problem use predict_proba with K = 15 and a threshold of 0.2 in place of the majority: how do recall and precision change? Exercise 2. Add ten noise columns to Wine (as in the section on the curse of dimensionality) and repeat the comparison between metrics: does Manhattan hold up better than Euclidean? Exercise 3. For regression, try weights="distance" with K = 1 and K = 5: why does nothing change with K = 1?

To practise on the agricultural-soil domain of exercise 1 there is an exercise skeleton in Python with three parts to complete: the Minkowski metrics with ties, the share of volume on the border of a hypercube and the coefficient of variation of the distances compared with a Monte Carlo check. As long as the points to complete are empty, it prints which exercises are missing.

What you can do now

You can write KNN in NumPy and recognise when its accuracy is an artefact of scale or of evaluation on the training set. You can measure the concentration of distances and the effect of useless columns, you can choose K and the metric with a repeated validation, and you can tell when a spatial index helps and when it is slower than brute force. In the next lesson, decision trees, the model becomes a sequence of yes/no questions.

Sources

Previous lesson in the course: Support Vector Machine: the maximum margin and the kernel trick. Other lessons in the series that link to this one: Clustering: K-Means and DBSCAN without labels.