K-Nearest Neighbours

Want to guess the price of a house? Look at similar houses nearby. Want to guess what film someone will like? Find people with similar taste. That is the whole of this algorithm. It is the simplest idea in machine learning, and it will teach us something very deep about distance.

• Look at similar examples
• The simplest idea in ML
• It teaches us about distance

Ask the neighbours

K nearest neighbours has no training step at all. It just remembers every example. When a new point arrives, it measures the distance to every stored point, finds the K closest, and lets them vote. Here, K is five. We find the five nearest, and count the colours. The majority wins. For regression, it would simply average their values.

K changes everything

The only real setting is K. A K of one trusts a single neighbour, which is jumpy and easily fooled. A huge K averages over almost everything, and misses all the detail. We test several values. Run it. The score peaks in the middle, and falls away at the extremes. That is overfitting and underfitting again, the same trade-off. Now look at the last line, the same model without scaling. The score drops, because distance is dominated by the largest features.

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

X, y = load_breast_cancer(return_X_y=True)

for k in [1, 5, 15, 51, 201]:
    scaled = make_pipeline(StandardScaler(), KNeighborsClassifier(k))
    print(f"k = {k:<4} accuracy {cross_val_score(scaled, X, y, cv=5).mean():.3f}")

raw = KNeighborsClassifier(5)
print(f"k = 5 without scaling {cross_val_score(raw, X, y, cv=5).mean():.3f}")

k = 1    accuracy 0.954
k = 5    accuracy 0.965
k = 15   accuracy 0.961
k = 51   accuracy 0.951
k = 201  accuracy 0.879
k = 5 without scaling 0.928

Strengths and weaknesses

K N N is easy to explain, needs no training, and handles curved boundaries well. But prediction is slow, because every new point must be compared to all stored data. It needs scaling. And it suffers from the curse of dimensionality. With hundreds of features, everything becomes roughly the same distance from everything else, and nearest loses all meaning.

Summary