L'erreur d'entraînement de $1$-NN

La démonstration tient en une phrase. Soit $x_i$ un point d'entraînement. Parmi les données, son plus proche voisin est $x_i$ lui-même, à distance $0$ ; aucun autre point ne peut faire mieux. L'algorithme lui rend donc son propre label, qui est le bon. L'erreur d'entraînement est nulle, quelles que soient les données — même purement aléatoires.

Ce qu'on en conclut : rien du tout sur la qualité. Un chiffre qu'un modèle obtient par construction ne mesure rien. Mesuré sur $200$ points tirés d'une règle « $y=1$ si $x>0,5$ » bruitée à $10\%$, et évalué sur $2000$ points nouveaux :

La colonne d'entraînement place $k=1$ en tête, et de loin ; sur le test, c'est le plus mauvais de tous les $k$ inférieurs à $n$. C'est la règle du cours prise en flagrant délit d'utilité : on n'évalue jamais un modèle sur les données qui ont servi à l'entraîner.

Le chiffre $0,198$ n'est pas un hasard. Avec $10\%$ de bruit, $1$-NN se trompe quand le point de test est bruité et son voisin ne l'est pas, ou l'inverse : environ $2\times 0,1\times 0,9=0,18$, du même ordre que la valeur mesurée $0,198$. Le meilleur possible est $0,10$ — le bruit lui-même —, atteint presque exactement par $k=5$. Et pour $k=199\approx n$, le vote porte sur toutes les données : la prédiction est constante et l'erreur remonte à $0,5$.