Classez par voisinage avec les k plus proches voisins

Vous trouvez en forêt une fleur que vous ne connaissez pas. Le réflexe le plus naturel consiste à ouvrir un guide et à chercher les photos qui lui ressemblent le plus. Si elles montrent presque toutes la même espèce, vous tenez votre réponse. Ce raisonnement, « dis-moi qui sont tes voisins, je te dirai qui tu es », est exactement celui des k plus proches voisins (k-nearest neighbors, ou k-NN).

C’est sans doute l’algorithme le plus simple de ce cours, et il cache pourtant les questions essentielles : qu’est-ce qu’être « proche » ? Combien de voisins consulter ? Et pourquoi la méthode s’effondre-t-elle quand les caractéristiques sont très nombreuses ? Notre fil rouge : les fleurs d’iris, que nous avons classées en TP.

Le principe : voter entre voisins

Le jeu d’iris décrit 150 fleurs de trois espèces (setosa, versicolor, virginica) par quatre mesures : longueur et largeur des sépales, longueur et largeur des pétales, en centimètres. Pour classer une nouvelle fleur $x$, l’algorithme est le suivant :

1. calculer la distance entre $x$ et chacune des fleurs du jeu d’apprentissage ;
2. garder les $k$ fleurs les plus proches ;
3. prédire l’espèce majoritaire parmi ces $k$ voisins (en régression, on prendrait la moyenne de leurs valeurs).

Remarquez qu’il n’y a pas vraiment de phase d’apprentissage : le « modèle », c’est le jeu de données lui-même. On dit que les k-NN sont un algorithme paresseux (lazy) et non paramétrique (chapitre 1). Tout le travail a lieu au moment de la prédiction.

Exemple

Une nouvelle fleur a des pétales de 4,9 cm de long et 1,7 cm de large. Voici cinq fleurs connues (on ne garde que les pétales pour simplifier), avec leur distance euclidienne à la nouvelle fleur :

Fleur	Pétale (long. ; larg.)	Espèce	Distance
A	5,0 ; 1,8	virginica	0,141
B	4,9 ; 1,5	versicolor	0,200
C	5,1 ; 1,9	virginica	0,283
D	4,7 ; 1,4	versicolor	0,361
E	4,5 ; 1,5	versicolor	0,447

Par exemple, pour A : $\sqrt{(5{,}0 - 4{,}9)^2 + (1{,}8 - 1{,}7)^2} = \sqrt{0{,}02} \approx 0{,}141$.

• Avec $k = 1$ : le plus proche est A, on prédit virginica.
• Avec $k = 3$ : A, B, C, soit 2 virginica contre 1 versicolor, on prédit virginica.
• Avec $k = 5$ : 3 versicolor contre 2 virginica, on prédit versicolor.

La réponse dépend de $k$ ! Cette fleur se trouve à la frontière entre deux espèces, justement là où versicolor et virginica se mélangent.

Le voisinage grandit avec k. Le cercle de k = 1 n'atteint que A (virginica) ; celui de k = 5 englobe les trois versicolor B, D et E, qui l'emportent. La fleur est à la frontière des deux espèces.

Qu’est-ce qu’être proche ? Distances et normalisation

Choisir une distance

La distance la plus courante est la distance euclidienne, celle de la règle graduée :

$$d(x, x') = \sqrt{\sum_{j=1}^{d} (x_j - x'_j)^2}$$

où $x_j$ et $x'_j$ sont les valeurs de la caractéristique $j$ pour les deux exemples, et $d$ le nombre de caractéristiques. On utilise aussi la distance de Manhattan, $\sum_j \lvert x_j - x'_j \rvert$ (la distance « en suivant les rues »), moins sensible à un écart isolé très grand. Les deux sont des cas particuliers de la distance de Minkowski, $\left(\sum_j \lvert x_j - x'_j \rvert^p\right)^{1/p}$, avec $p = 2$ et $p = 1$. Pour des variables catégorielles, on peut compter le nombre de caractéristiques qui diffèrent (distance de Hamming).

Le choix de la distance est le biais inductif des k-NN : c’est lui qui décide ce que « se ressembler » veut dire.

Normaliser les variables

Pour les iris, toutes les mesures sont en centimètres et du même ordre de grandeur. Mais imaginez des patients décrits par leur âge (de 0 à 100) et leur revenu mensuel (de 0 à 10 000 €). Un écart de 1 000 € domine complètement un écart de 30 ans dans la distance : le modèle ne regarde plus que le revenu, sans que personne l’ait décidé.

La solution est de mettre toutes les variables à la même échelle avant de calculer les distances. La méthode la plus courante est la standardisation (centrer-réduire) :

$$z_j = \frac{x_j - \mu_j}{\sigma_j}$$

où $\mu_j$ et $\sigma_j$ sont la moyenne et l’écart-type de la caractéristique $j$ calculés sur le jeu d’apprentissage. Chaque variable a alors une moyenne de 0 et un écart-type de 1. Une alternative est la mise à l’échelle entre 0 et 1 (min-max).

Les patients de l'exercice « L'effet de la normalisation ». En euros, l'écart de revenu écrase tout et C paraît voisin de A malgré 30 ans d'écart ; une fois chaque variable mesurée en écarts-types, c'est B le plus proche.

Piège

Oublier de normaliser est l’erreur la plus fréquente avec les k-NN (et avec les SVM et les réseaux de neurones). Dans le projet de l’étude de cas du chapitre 10, des dates converties en secondes (de l’ordre du milliard) côtoyaient des âges et des variables binaires : sans normalisation, la distance ne voyait presque que les dates.

Choisir k : le compromis biais-variance en action

Mais alors, comment choisir $k$ ? Bonne question ! C’est l’hyperparamètre principal, et il règle directement le compromis du chapitre 2 :

• $k$ petit (à l’extrême $k = 1$) : la prédiction dépend d’un seul voisin, donc du moindre exemple bruité ou mal étiqueté. La frontière est très irrégulière (pour $k = 1$, elle suit les cellules de Voronoï autour de chaque exemple). Variance élevée : c’est le surapprentissage. Avec $k = 1$, l’erreur sur les données d’apprentissage est d’ailleurs nulle, puisque chaque point est son propre voisin.
• $k$ grand : le vote porte sur une large région, la frontière devient lisse, puis trop lisse. À l’extrême, $k = m$ prédit toujours la classe majoritaire du jeu entier. Biais élevé : c’est le sous-apprentissage, avec une tendance à favoriser la classe la plus fréquente.

Sur les pétales des iris : k = 1 dessine des îlots autour de chaque fleur atypique (exactitude d'apprentissage flatteuse), k = 100 vote sur les deux tiers du jeu et n'a plus rien de local.

Une règle empirique donne un ordre de grandeur, $k \approx \sqrt{m / C}$ où $m$ est le nombre d’exemples et $C$ le nombre de classes (environ 7 pour les iris). Mais en pratique, on choisit $k$ par validation croisée, en testant une grille de valeurs. Quelques réglages complètent le choix :

• en classification binaire, un $k$ impair évite les égalités ;
• un vote pondéré par la distance (chaque voisin $x_i$ reçoit le poids $1/d(x, x_i)$) donne plus d’influence aux voisins les plus proches et règle aussi les égalités.

En TP, un classifieur à $k = 15$ sur les quatre mesures des iris a atteint une exactitude moyenne de 0,973 en validation croisée à 10 plis. Sur ce jeu, les pétales séparent très bien setosa des deux autres espèces ; les confusions portent surtout sur versicolor et virginica, qui se chevauchent, comme dans l’exemple ci-dessus. Nous l’avions d’ailleurs pressenti en TP en traçant les sépales seuls, où ces deux espèces se mélangent largement.

from sklearn.datasets import load_iris
from sklearn.model_selection import GridSearchCV, StratifiedKFold
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

X, y = load_iris(return_X_y=True)

# La normalisation fait partie du pipeline : elle est réapprise dans chaque pli
pipe = make_pipeline(StandardScaler(), KNeighborsClassifier())
grille = {
    "kneighborsclassifier__n_neighbors": list(range(1, 31, 2)),   # k impairs de 1 à 29
    "kneighborsclassifier__weights": ["uniform", "distance"],
}
cv = StratifiedKFold(n_splits=10, shuffle=True, random_state=0)
recherche = GridSearchCV(pipe, grille, cv=cv).fit(X, y)
print(recherche.best_params_, round(recherche.best_score_, 3))

Attention

Le best_score_ d’une recherche sur grille est optimiste, puisqu’il a servi à choisir les hyperparamètres (chapitre 3). Pour annoncer une performance, évaluez le modèle retenu sur un jeu de test mis de côté avant la recherche.

Pourquoi une méthode aussi simple fonctionne-t-elle ? Parmi les $k$ voisins de $x$, la proportion $k_i / k$ de ceux qui appartiennent à la classe $i$ est une estimation locale de $P(\omega_i \mid x)$. Voter pour la classe majoritaire revient donc à appliquer la règle MAP du chapitre 5 avec des probabilités estimées sur le voisinage. On montre que, lorsque le nombre d’exemples tend vers l’infini (avec $k$ qui grandit, mais beaucoup moins vite que $m$), l’erreur des k-NN tend vers l’erreur de Bayes. Même le simple 1-NN a, asymptotiquement, une erreur au plus double de l’erreur de Bayes.

Le fléau de la dimension

Les k-NN ont deux faiblesses. La première est leur coût de prédiction : comparer chaque nouvel exemple à tous les exemples d’apprentissage devient lourd avec des millions de lignes (des structures comme les arbres k-d accélèrent la recherche en faible dimension). La seconde, plus profonde, est le fléau de la dimension (curse of dimensionality).

Imaginez des points répartis uniformément dans un cube de côté 1. Pour capturer 10 % des points autour d’un exemple, il faut un petit cube de côté $0{,}1^{1/d}$ :

Dimension $d$	Côté du cube qui contient 10 % des points
1	0,10
2	0,32
10	0,79
100	0,98

En dimension 100, le « voisinage » qui contient 10 % des données couvre 98 % de l’étendue de chaque variable : il n’a plus rien de local ! Plus généralement, quand $d$ grandit, les distances entre points se ressemblent toutes, l’écart entre le plus proche et le plus lointain voisin se réduit, et la notion même de « plus proche » perd son sens. Les méthodes à base de distance en souffrent en premier.

À gauche, les valeurs du tableau : le voisinage cesse vite d'être local. À droite, en dimension 100, même le plus proche voisin est à 70 % de la distance du plus lointain : toutes les distances se ressemblent.

Les remèdes : réduire le nombre de caractéristiques (sélection de variables, analyse en composantes principales), apprendre une meilleure représentation, ou préférer un modèle moins sensible à la dimension.

Piège

Ne confondez pas k-NN et k-means : seul le « k » est commun.

• k-NN (k plus proches voisins) est une méthode supervisée de classification ou de régression ; $k$ est le nombre de voisins consultés.
• k-means (k-moyennes) est une méthode non supervisée de partitionnement ; $k$ est le nombre de groupes à former, et l’algorithme déplace $k$ centres jusqu’à ce que chaque point soit rattaché au centre le plus proche.

À retenir

Les k-NN classent un exemple par vote de ses $k$ voisins les plus proches. Trois réglages décident de tout : la distance, la normalisation des variables (indispensable) et la valeur de $k$, choisie par validation croisée. La méthode souffre du fléau de la dimension.

En entretien

« Les k-NN ne construisent pas de modèle : ils gardent les exemples et votent entre les $k$ plus proches. Un petit $k$ surapprend, un grand $k$ lisse trop ; on le règle en validation croisée, après avoir normalisé les variables. »

En résumé

• Les k plus proches voisins prédisent la classe majoritaire (ou la moyenne) des $k$ exemples les plus proches ; c’est une méthode paresseuse et non paramétrique.
• La distance (euclidienne, Manhattan, Hamming) définit ce que « se ressembler » veut dire : c’est le biais inductif de la méthode.
• Il faut normaliser les variables, avec des paramètres calculés sur l’apprentissage seul, sinon la variable de plus grande échelle domine.
• $k$ petit : surapprentissage ; $k$ grand : sous-apprentissage. On choisit $k$ par validation croisée, éventuellement avec un vote pondéré par la distance.
• La proportion de voisins de chaque classe estime $P(\omega \mid x)$ ; asymptotiquement, l’erreur tend vers l’erreur de Bayes.
• En grande dimension, les distances perdent leur sens : c’est le fléau de la dimension.

Exercices

Exercice · Voter avec différents k

facile

Une nouvelle fleur a des pétales de 4,8 cm sur 1,6 cm. Avec les cinq fleurs A à E de l’exemple, calculez les distances euclidiennes et donnez la prédiction pour $k = 1$, $k = 3$ et $k = 5$.

Voir la solution

Distances à (4,8 ; 1,6) :

• A (5,0 ; 1,8) : $\sqrt{0{,}04 + 0{,}04} \approx 0{,}283$ (virginica) ;
• B (4,9 ; 1,5) : $\sqrt{0{,}01 + 0{,}01} \approx 0{,}141$ (versicolor) ;
• C (5,1 ; 1,9) : $\sqrt{0{,}09 + 0{,}09} \approx 0{,}424$ (virginica) ;
• D (4,7 ; 1,4) : $\sqrt{0{,}01 + 0{,}04} \approx 0{,}224$ (versicolor) ;
• E (4,5 ; 1,5) : $\sqrt{0{,}09 + 0{,}01} \approx 0{,}316$ (versicolor).

Classement : B, D, A, E, C.

• $k = 1$ : B, versicolor.
• $k = 3$ : B, D, A, soit 2 versicolor contre 1 virginica, versicolor.
• $k = 5$ : 3 versicolor contre 2 virginica, versicolor.

Cette fleur est un peu plus « à l’intérieur » de la zone versicolor : tous les $k$ s’accordent.

En code

Python

import numpy as np
from collections import Counter

noms = np.array(list("ABCDE"))
fleurs = np.array([[5.0, 1.8], [4.9, 1.5], [5.1, 1.9], [4.7, 1.4], [4.5, 1.5]])
especes = np.array(["virginica", "versicolor", "virginica", "versicolor", "versicolor"])
nouvelle = np.array([4.8, 1.6])

distances = np.sqrt(((fleurs - nouvelle) ** 2).sum(axis=1))
print(distances.round(3))                   # [0.283 0.141 0.424 0.224 0.316]
ordre = np.argsort(distances)
print(noms[ordre])                          # ['B' 'D' 'A' 'E' 'C']

for k in [1, 3, 5]:
    vote = Counter(especes[ordre[:k]]).most_common(1)[0][0]   # espèce majoritaire
    print(k, vote)                          # versicolor pour k = 1, 3 et 5

R

fleurs <- data.frame(
  longueur = c(5.0, 4.9, 5.1, 4.7, 4.5), largeur = c(1.8, 1.5, 1.9, 1.4, 1.5),
  espece = c("virginica", "versicolor", "virginica", "versicolor", "versicolor"),
  row.names = c("A", "B", "C", "D", "E")
)
nouvelle <- c(4.8, 1.6)

distances <- sqrt((fleurs$longueur - nouvelle[1])^2 + (fleurs$largeur - nouvelle[2])^2)
names(distances) <- rownames(fleurs)
round(sort(distances), 3)           # B 0.141, D 0.224, A 0.283, E 0.316, C 0.424

ordre <- order(distances)
for (k in c(1, 3, 5)) {
  votes <- table(fleurs$espece[ordre[1:k]])
  cat(k, names(which.max(votes)), "\n")      # versicolor pour k = 1, 3 et 5
}

Exercice · L'effet de la normalisation

moyen

Trois patients sont décrits par (âge, revenu mensuel en euros) : A = (30 ; 2 000), B = (32 ; 3 500), C = (60 ; 2 100).

1. Sans normalisation, quel patient est le plus proche de A (distance euclidienne) ?
2. On standardise avec, sur le jeu d’apprentissage, un âge moyen de 40 ans (écart-type 12) et un revenu moyen de 2 500 € (écart-type 800 €). Même question.
3. Commentez.

Voir la solution

1. Sans normalisation : $d(A, B) = \sqrt{2^2 + 1500^2} \approx 1500$ et $d(A, C) = \sqrt{30^2 + 100^2} \approx 104$. C est le plus proche.
2. Après standardisation : A devient $(-0{,}83 ; -0{,}63)$, B devient $(-0{,}67 ; 1{,}25)$ et C devient $(1{,}67 ; -0{,}50)$. Alors $d(A, B) \approx \sqrt{0{,}17^2 + 1{,}88^2} \approx 1{,}88$ et $d(A, C) \approx \sqrt{2{,}50^2 + 0{,}13^2} \approx 2{,}50$. B est le plus proche.
3. Sans normalisation, le revenu (des milliers d’euros) écrase l’âge (des dizaines d’années) : un écart de 30 ans compte moins qu’un écart de 1 500 €. Après standardisation, chaque variable est mesurée en « nombre d’écarts-types », et l’écart d’âge entre A et C redevient important. Le voisin choisi, et donc la prédiction, change complètement.

En code

Python

import numpy as np

patients = {"A": np.array([30, 2000]), "B": np.array([32, 3500]), "C": np.array([60, 2100])}
moyenne, ecart_type = np.array([40, 2500]), np.array([12, 800])   # appris sur l'apprentissage

def distances(p):
    return {n: round(float(np.linalg.norm(p[n] - p["A"])), 2) for n in ["B", "C"]}

print(distances(patients))                    # {'B': 1500.0, 'C': 104.4} : C le plus proche
standardises = {n: (x - moyenne) / ecart_type for n, x in patients.items()}
print({n: z.round(3) for n, z in standardises.items()})  # A (-0.833, -0.625), B (-0.667, 1.25), C (1.667, -0.5)
print(distances(standardises))                # {'B': 1.88, 'C': 2.5} : B le plus proche

R

patients <- rbind(A = c(30, 2000), B = c(32, 3500), C = c(60, 2100))
colnames(patients) <- c("age", "revenu")
moyenne <- c(40, 2500); ecart_type <- c(12, 800)       # appris sur l'apprentissage

round(as.matrix(dist(patients))["A", ], 1)             # B 1500.0, C 104.4 : C le plus proche

# Standardisation : (x - moyenne) / écart-type, colonne par colonne
z <- sweep(sweep(patients, 2, moyenne), 2, ecart_type, "/")
round(z, 3)                  # A (-0.833 ; -0.625), B (-0.667 ; 1.25), C (1.667 ; -0.5)
round(as.matrix(dist(z))["A", ], 2)                    # B 1.88, C 2.50 : B le plus proche

Exercice · Mesurer le fléau de la dimension

difficile

Des points sont répartis uniformément dans un hypercube de côté 1 en dimension $d$. On veut que le voisinage d’un point (un petit hypercube de côté $c$) contienne 1 % des points.

1. Exprimez $c$ en fonction de $d$.
2. Calculez $c$ pour $d = 2$ et $d = 10$.
3. Qu’en concluez-vous pour les k-NN sur des données de grande dimension ?

Voir la solution

1. Le volume du petit hypercube est $c^d$, et il doit valoir 1 % du volume total (qui vaut 1). Donc $c^d = 0{,}01$, soit $c = 0{,}01^{1/d}$.
2. Pour $d = 2$ : $c = 0{,}01^{1/2} = 0{,}1$. Pour $d = 10$ : $c = 0{,}01^{1/10} \approx 0{,}63$.
3. En dimension 10, un voisinage qui ne contient que 1 % des points doit couvrir 63 % de l’étendue de chaque variable : les « voisins » d’un point ne lui ressemblent plus vraiment. Pour garder des voisinages réellement locaux, il faudrait un nombre d’exemples qui croît exponentiellement avec la dimension. En pratique, il faut réduire la dimension (sélection de variables, ACP) avant d’utiliser les k-NN, ou choisir un autre modèle.

En code

Python

import numpy as np

# Côté du petit hypercube qui contient 1 % du volume : c = 0,01^(1/d)
for d in [2, 10, 100]:
    print(d, round(0.01 ** (1 / d), 3))          # 0.1, 0.631, 0.955

# Vérification par simulation en dimension 10
rng = np.random.default_rng(0)
d, c = 10, 0.01 ** (1 / 10)
points = rng.random((200_000, d))
centre = np.full(d, 0.5)
dans_le_cube = np.all(np.abs(points - centre) <= c / 2, axis=1)
print(dans_le_cube.mean())                       # 0.00977, proche de 0,01

R

# Côté du petit hypercube qui contient 1 % du volume : c = 0,01^(1/d)
d <- c(2, 10, 100)
round(0.01^(1 / d), 3)                    # 0.1, 0.631, 0.955

# Vérification par simulation en dimension 10
set.seed(0)
c10 <- 0.01^(1 / 10)
points <- matrix(runif(200000 * 10), ncol = 10)
dans_le_cube <- apply(abs(points - 0.5) <= c10 / 2, 1, all)
mean(dans_le_cube)                        # 0.0102, proche de 0,01