Plus proches voisins : le modèle le plus simple

L’idée de modèle la plus simple est celle-ci : des cas semblables ont des réponses semblables. Pour reconnaître un nouveau manchot, cherchez les k manchots d’apprentissage qui lui ressemblent le plus et demandez-leur leur espèce. C’est la méthode des k plus proches voisins (en anglais k-nearest neighbours, kNN). Nous revenons aux manchots de la leçon 0.1, décrits cette fois par deux mesures seulement : la longueur du bec et la masse corporelle.

À vous de jouer

• Le lab démarre en unités brutes, millimètres et grammes, avec k = 1. Passez aux unités standardisées : que deviennent les frontières et le score ?
• Toujours avec k = 1, regardez les frontières entre espèces : où sont-elles déchiquetées ?
• Augmentez k. À quel k les frontières se lissent-elles, et à quel k le score au test baisse-t-il nettement ?
• Comparez la dernière ligne, la moyenne sur 20 découpages, pour k = 1 et k = 9.

Une fois vérifié dans le lab, nommons ce que vous voyez.

L’idée en quelques mots

kNN ne construit aucune règle. « Apprendre », c’est stocker les 239 manchots d’apprentissage. Tout le travail se fait quand une question arrive : pour un nouveau manchot, le modèle calcule la distance à chaque manchot stocké, prend les k plus proches et laisse la majorité décider. Le fond du lab est exactement cette réponse en chaque point du graphique.

Le nombre k règle à quel point le modèle se fie aux exemples isolés. Avec k = 1, la frontière contourne chaque manchot, y compris les exceptions placées au milieu d’une autre espèce. Avec un grand k, par exemple 101 sur 239, presque la moitié du jeu vote, les frontières deviennent lisses et l’espèce la plus rare, Chinstrap, perd des votes : dans le découpage 1, l’exactitude tombe à 83,5 %. Un bon k se situe entre les deux, et on le choisit sur des données, pas à l’œil.

Le second réglage se voit moins : les unités. La distance additionne l’écart de longueur du bec et l’écart de masse. Les becs vont de 32,1 à 59,6 mm, la masse de 2700 à 6300 g. Sans remise à l’échelle, un écart de 100 g pèse autant que 100 mm de bec, donc la masse décide presque seule qui est proche. Standardiser transforme chaque mesure en un nombre d’écarts-types par rapport à la moyenne, et les deux mesures pèsent alors autant.

Jak to policzono

• Données : Palmer Penguins (Gorman, Williams et Fraser, 2014 ; paquet palmerpenguins : Horst, Hill et Gorman, 2020), licence CC0. 342 manchots avec toutes les mesures, 3 espèces.
• Découpage : 70/30, stratifié ; le découpage 1 est train_test_split(test_size=0.3, stratify=y, random_state=1) dans scikit-learn, le même que dans la leçon 0.1. 239 manchots pour apprendre, 103 dans le test.
• Modèle : kNN avec la distance euclidienne, une voix par voisin ; une égalité va à l’espèce la première par ordre alphabétique (comme dans scikit-learn).
• Standardisation : la moyenne et l’écart-type viennent des seuls manchots d’apprentissage.

Pourquoi ça marche

kNN marche quand être proche dans les mesures veut dire se ressembler dans la réponse. Chez les manchots, c’est le cas : les espèces diffèrent par leur morphologie, donc des manchots au bec et à la masse semblables appartiennent en général à la même espèce. C’est pourquoi deux mesures donnent déjà 94,2 % contre 43,7 % en devinant « toujours Adelie ».

Un petit et un grand k abîment le résultat par deux côtés opposés. Avec k = 1, le modèle est très sensible au hasard : un manchot d’apprentissage atypique change la réponse dans tout son voisinage. Les 100 % à l’apprentissage ne disent rien ici, puisque chaque manchot se trouve lui-même. Avec un très grand k, le modèle ne voit plus la forme des données et se rapproche de « l’espèce la plus fréquente dans le coin ». C’est le même compromis entre ajustement et généralisation qui revient au module 3.

Les unités comptent autant parce que kNN ne sait pas quelle mesure est importante : il calcule seulement des distances. En unités brutes, avec k = 5, il reconnaît 77,7 % des manchots de test, après standardisation 94,2 %. Avec les quatre mesures, la masse en grammes, l’écart est encore plus grand : 76,7 % sans mise à l’échelle et 96,1 % après standardisation, et en moyenne sur 100 découpages 76,7 % et 98,9 %.

Erreur fréquente

Vrai ou faux : « Le plus petit k est le meilleur, car le modèle colle parfaitement aux données ». Faux. Avec k = 1, le modèle obtient 100 % sur les manchots d’apprentissage, car chacun est son propre voisin, mais sur de nouveaux manchots il perd en moyenne contre k = 9 : 92,2 % contre 94,2 % sur 100 découpages. Coller parfaitement aux données d’apprentissage, c’est mémoriser aussi les exceptions. Choisissez k selon le score sur des données que le modèle n’a pas vues.

Là où l’analogie a ses limites : les « voisins » de kNN ne sont pas les manchots debout à côté de vous sur la plage, mais ceux aux mesures semblables. Et qui est semblable dépend des unités que vous choisissez.

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)  # les 342 manchots avec les quatre mesures
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  # le scaler apprend moyenne et écart-type sur la seule partie d’apprentissage
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"]  # les deux mesures du lab : millimètres et grammes
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