Nearest neighbours: the simplest model

The simplest idea for a model goes like this: similar cases have similar answers. To recognise a new penguin, find the k learning penguins most similar to it and ask which species they are. That is the k-nearest neighbours method (kNN). We go back to the penguins of lesson 0.1, this time described by only two measurements: bill length and body mass.

Try this

• The lab starts in raw units, millimetres and grams, at k = 1. Switch to standardized units: what happens to the borders and to the score?
• Still at k = 1, look at the borders between species: where are they ragged?
• Raise k. At which k do the borders smooth out, and at which does the test score clearly drop?
• Compare the last line, the mean over 20 splits, for k = 1 and k = 9.

Once you have checked it in the lab, let us name what you see.

The idea in plain words

kNN builds no rule at all. “Learning” means storing the 239 learning penguins. All the work happens when a question comes: for a new penguin the model computes the distance to every stored one, takes the k nearest and lets the majority decide. The background in the lab is exactly that answer at every point of the chart.

The number k sets how much the model trusts single examples. At k = 1 the border runs around every penguin, including exceptions sitting among another species. With a large k, say 101 of 239, almost half the dataset votes, the borders become smooth and the rarest species, Chinstrap, loses votes: in split 1 accuracy falls to 83.5%. A good k lies in between, and you choose it on data, not by eye.

The second dial is less visible: the units. The distance adds the difference in bill length to the difference in body mass. Bills range from 32.1 to 59.6 mm, body mass from 2700 to 6300 g. Without rescaling a difference of 100 g weighs as much as 100 mm of bill, so mass alone almost decides who is near. Standardizing turns every measurement into a number of standard deviations from the mean, and both measurements start to weigh the same.

Jak to policzono

• Data: Palmer Penguins (Gorman, Williams and Fraser, 2014; palmerpenguins package: Horst, Hill and Gorman, 2020), licence CC0. 342 penguins with all measurements, 3 species.
• Split: 70/30, stratified; split 1 is train_test_split(test_size=0.3, stratify=y, random_state=1) in scikit-learn, the same as in lesson 0.1. 239 penguins to learn from, 103 in the test.
• Model: kNN with Euclidean distance, one vote per neighbour, a tie goes to the species first in alphabetical order (as in scikit-learn).
• Standardizing: the mean and standard deviation come from the learning penguins only.

Why it works

kNN works when being close in the measurements means being alike in the answer. For penguins that holds: the species differ in build, so penguins with a similar bill and mass usually belong to the same species. That is why two measurements already give 94.2% against 43.7% for guessing “always Adelie”.

A small and a large k spoil the result from opposite sides. At k = 1 the model is very sensitive to chance: one unusual learning penguin changes the answer in its whole neighbourhood. The learning score of 100% says nothing here, because every penguin finds itself. With a very large k the model stops seeing the shape of the data and moves towards “the most common species around”. It is the same trade-off between fitting and generalising that comes back in module 3.

The units matter so much because kNN does not know which measurement is important: it only computes distance. In raw units with k = 5 it gets 77.7% of the test penguins right, after standardizing 94.2%. On all four measurements, with mass in grams, the gap is even bigger: 76.7% without scaling and 96.1% after standardizing, and on average over 100 splits 76.7% and 98.9%.

Common mistake

True or false: “The smallest k is best, because the model fits the data perfectly”. False. At k = 1 the model scores 100% on the learning penguins, because each one is its own neighbour, but on new penguins it loses to k = 9 on average: 92.2% against 94.2% over 100 splits. A perfect fit to the learning data means memorising the exceptions too. Choose k by the score on data the model has not seen.

Where the analogy breaks down: “neighbours” in kNN are not the penguins standing next to you on the beach, but those with similar measurements. And who counts as similar depends on the units you choose.

import numpy as np
import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

df = pd.read_csv("data/raw/penguins.csv")
cols4 = ["bill_length_mm", "bill_depth_mm", "flipper_length_mm", "body_mass_g"]
d = df.dropna(subset=cols4)  # the 342 penguins with all four measurements
y = d["species"]
K = [1, 3, 5, 9, 15, 25, 51, 101]
def knn(k, scale):
    model = KNeighborsClassifier(n_neighbors=k)
    return make_pipeline(StandardScaler(), model) if scale else model  # the scaler learns mean and sd on the learning part only
def score(cols, k, scale, seed):
    Xtr, Xte, ytr, yte = train_test_split(d[cols], y, test_size=0.3, stratify=y, random_state=seed)
    m = knn(k, scale).fit(Xtr, ytr)
    return m.score(Xte, yte), m.score(Xtr, ytr)
lab = ["bill_length_mm", "body_mass_g"]  # the lab's two measurements: millimetres and grams
for scale in (False, True):
    print(("standardized:" if scale else "raw mm and g:"), " ".join(f"k={k} {score(lab, k, scale, 1)[0]:.3f}" for k in K))
print(f"k=1 on the learning penguins: {score(lab, 1, True, 1)[1]:.3f}")
runs = {k: np.array([score(lab, k, True, s)[0] for s in range(100)]) for k in (1, 9, 101)}
print(f"100 splits, standardized: k=1 {runs[1].mean():.3f}, k=9 {runs[9].mean():.3f}, k=101 {runs[101].mean():.3f}; k=9 beats k=1 in {(runs[9] > runs[1]).sum()}, loses in {(runs[9] < runs[1]).sum()}")
four = [[score(cols4, 5, scale, s)[0] for s in range(100)] for scale in (False, True)]
print(f"all 4 measurements, k=5: raw {four[0][1]:.3f}, standardized {four[1][1]:.3f} on split 1; mean of 100 splits {np.mean(four[0]):.3f} and {np.mean(four[1]):.3f}")

raw mm and g: k=1 0.835 k=3 0.748 k=5 0.777 k=9 0.757 k=15 0.777 k=25 0.748 k=51 0.738 k=101 0.738
standardized: k=1 0.942 k=3 0.922 k=5 0.942 k=9 0.942 k=15 0.942 k=25 0.942 k=51 0.942 k=101 0.835
k=1 on the learning penguins: 1.000
100 splits, standardized: k=1 0.922, k=9 0.942, k=101 0.856; k=9 beats k=1 in 78, loses in 9
all 4 measurements, k=5: raw 0.767, standardized 0.961 on split 1; mean of 100 splits 0.767 and 0.989