Les k plus proches voisins
Prérequis : Encoder et mettre à l'échelle · Mesurer une classification
- 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).
« Dis-moi qui sont tes voisins… »
Section intitulée « « Dis-moi qui sont tes voisins… » »L’algorithme des k plus proches voisins (k-nearest neighbors, kNN) est sans doute le plus intuitif de tous. Pour classer un nouveau point :
- on calcule sa distance à tous les exemples d’entraînement ;
- on garde les k plus proches ;
- 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).
L’effet de k
Section intitulée « L’effet de k »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.
Les distances
Section intitulée « Les distances »La distance la plus courante est la distance euclidienne (à vol d’oiseau) : . La distance de Manhattan additionne les écarts sur chaque variable (comme un trajet dans un quartier aux rues perpendiculaires) : .
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").
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 et faiblesses
Section intitulée « Forces et faiblesses »| 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 . Pour capturer une fraction des points dans un petit cube autour d’un point, il faut un cube de côté . Avec :
| dimension | 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 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 KNeighborsClassifierfrom sklearn.pipeline import make_pipelinefrom 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