k plus proches voisins

Pour classer un point, la méthode des k plus proches voisins repère les k observations d’entraînement les plus proches, estime les probabilités de classe par les proportions parmi ces voisins, et prédit la plus fréquente. Rien n’est ajusté à l’avance : tout le jeu d’entraînement est conservé et consulté au moment de la prédiction, ce qui rend l’entraînement instantané et la prédiction coûteuse - l’inverse de la plupart des méthodes.

Le choix de k contrôle directement la flexibilité. À k = 1, chaque point d’entraînement est son propre plus proche voisin : l’erreur d’entraînement est donc exactement nulle et la frontière est déchiquetée, un ajustement à forte variance qui réagit aux observations individuelles. Quand k grandit, la frontière se lisse, la variance baisse et le biais monte, jusqu’à ce que, k approchant la taille de l’échantillon, presque tout le jeu d’entraînement vote à chaque prédiction et que le classifieur renvoie la classe majoritaire quelle que soit l’entrée.

Comme elle n’impose aucune forme à la frontière, la méthode peut approcher des régions de décision courbes ou disjointes qu’un modèle linéaire ne sait pas représenter du tout. Le prix est qu’elle n’a aucun moyen d’ignorer une variable non pertinente : chaque dimension contribue à la distance, si bien que la précision se dégrade à mesure qu’on ajoute des variables non informatives - une forme du fléau de la dimension, où les plus proches voisins en grande dimension ne sont proches en aucun sens utile.

La métrique de distance mérite une attention qu’elle reçoit rarement. La distance euclidienne sur des variables brutes laisse une variable mesurée en grandes unités dominer le calcul : les variables doivent donc être standardisées, sauf si leurs échelles relatives sont délibérément significatives. La méthode n’offre par ailleurs ni coefficients ni résumé : elle peut dire ce qu’elle prédit mais pas pourquoi, ce qui l’exclut là où le raisonnement doit être inspectable.

Sur un problème bidimensionnel dont le taux d’erreur optimal vaut 0,092708, les k plus proches voisins ajustés sur 200 points d’entraînement et évalués sur 20 000 points de test donnent une erreur de 0,138200 en k = 1, descendent à une meilleure valeur de 0,097150 en k = 15, puis remontent à 0,103550 en k = 75.

En k = 199 sur 200 points d’entraînement, l’erreur atteint 0,504850 - essentiellement l’a priori de classe, puisque presque tout l’échantillon vote à chaque prédiction. À l’autre extrémité, k = 1 a une erreur d’entraînement exactement nulle alors que son erreur de test est la pire de tous les k hormis le k = 199 dégénéré, ce qui est la démonstration la plus nette possible que l’erreur d’entraînement n’est pas une estimation de l’erreur de test.

La meilleure valeur est intérieure, et il n’en existe pas de formule. On la choisit par validation croisée, et le plancher peu marqué entre k = 9 et k = 45 est ici typique : la méthode n’est en général pas sensible à un k exactement juste, seulement à un k à peu près juste.