Aller au contenu
Data science

Les k plus proches voisins

⏱ 45 min

Prérequis : Encoder et mettre à l'échelle · Mesurer une classification

À la fin de ce chapitre, vous saurez :
  • décrire l'algorithme des k plus proches voisins ;
  • expliquer l'effet de k sur la frontière et sur le surapprentissage ;
  • choisir une distance et justifier la mise à l'échelle ;
  • citer les forces et les faiblesses du kNN (coût de prédiction, fléau de la dimension).

L’algorithme des k plus proches voisins (k-nearest neighbors, kNN) est sans doute le plus intuitif de tous. Pour classer un nouveau point :

  1. on calcule sa distance à tous les exemples d’entraînement ;
  2. on garde les k plus proches ;
  3. ils votent : la classe majoritaire l’emporte.

Pour une régression, on fait la moyenne des valeurs des k voisins au lieu d’un vote (voir Les modèles non linéaires en régression).

Particularité : il n’y a pas d’entraînement. fit() se contente de mémoriser les exemples ; tout le travail a lieu au moment de prédire. On parle d’apprentissage paresseux (lazy learning).

Cliquez pour ajouter des points (choisissez leur couleur), et faites varier k. Le fond montre la classe prédite en chaque endroit :

  • k = 1 : la frontière contourne chaque point ; un seul point « intrus » crée sa propre île. 100 % sur les points d’entraînement, mais c’est du surapprentissage.
  • k plus grand : chaque prédiction est un vote plus large, la frontière s’adoucit, les points isolés perdent leur influence.
  • k très grand (proche du nombre de points) : tout le monde vote ; la classe majoritaire envahit tout. C’est du sous-apprentissage.

Attention au sens : pour le kNN, la complexité du modèle diminue quand k augmente. Le widget affiche aussi une précision « sans tricher » : chaque point est retiré puis prédit par les autres (validation leave-one-out). C’est elle qu’il faut regarder pour choisir k.

La distance la plus courante est la distance euclidienne (à vol d’oiseau) : d(x,x′)=∑j(xj−xj′)2d(x, x') = \sqrt{\sum_j (x_j - x'_j)^2}. La distance de Manhattan additionne les écarts sur chaque variable (comme un trajet dans un quartier aux rues perpendiculaires) : ∑j∣xj−xj′∣\sum_j |x_j - x'_j|.

Dans tous les cas, les variables doivent être à la même échelle, sinon celle qui a les plus grandes valeurs décide seule des voisins (voir Encoder et mettre à l’échelle).

On peut aussi pondérer le vote par l’inverse de la distance : un voisin très proche compte plus qu’un voisin lointain (weights="distance").

🔬Le kNN dans le simulateur

Cliquez sur la carte pour voir les voisins d’un point s’allumer un à un et voter. Puis tracez la courbe de complexité en fonction de k.

→
Forces Faiblesses
simple à comprendre et à expliquer (« ces 5 clients vous ressemblent ») prédiction lente : il faut calculer la distance à tous les exemples
aucune hypothèse sur la forme de la frontière doit garder tout le jeu d’entraînement en mémoire
s’adapte immédiatement à de nouveaux exemples (on les ajoute) sensible à l’échelle et aux variables inutiles
fonctionne en classification et en régression souffre du fléau de la dimension
🎓 Pour aller plus loin : le fléau de la dimension

En grande dimension, la notion même de « proche » perd son sens. Tirons des points au hasard dans un hypercube [0,1]p[0, 1]^p. Pour capturer une fraction ff des points dans un petit cube autour d’un point, il faut un cube de côté f1/pf^{1/p}. Avec f=1 %f = 1\,\% :

dimension pp côté du cube nécessaire
1 0,01
2 0,10
10 0,63
100 0,955

En dimension 100, les « voisins » d’un point occupent presque toute la largeur de chaque variable : ils ne sont pas proches du tout. Plus précisément, le rapport entre la distance au plus proche et au plus lointain voisin tend vers 1 quand pp augmente : toutes les distances se ressemblent.

C’est pourquoi le kNN se dégrade quand on ajoute des variables inutiles (essayez l’expérience « Variables inutiles » dans la page Comparer), et pourquoi on réduit souvent la dimension (ACP, partie 4) avant de l’utiliser. Pour accélérer la recherche des voisins, scikit-learn utilise des structures d’arbres (KD-tree, Ball-tree) qui évitent de calculer toutes les distances, efficaces en petite dimension.

from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
modele = make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=7, weights="distance"))
modele.fit(X_train, y_train) # mémorise les exemples (et apprend la mise à l'échelle)
modele.predict(X_test) # calcule les distances et fait voter les voisins

✅ Vérifiez vos acquis

1. Que fait la méthode fit() d'un KNeighborsClassifier ?
2. Avec k = 1, la précision sur les données d'entraînement est…
3. Quand k augmente, la frontière de décision devient…
4. Pourquoi le kNN est-il lent en prédiction sur un grand jeu de données ?
5. On ajoute 50 variables de bruit à un problème à 2 variables utiles. Le kNN…