Qu'est-ce que les k plus proches voisins (kNN) ?

Définition

L’algorithme des k plus proches voisins (kNN) est une méthode d’apprentissage supervisé qui classe un point selon la classe majoritaire de ses k points stockés les plus proches.

Le kNN n’a pas d’étape d’entraînement explicite. Il stocke les exemples étiquetés et effectue ses calculs à l’arrivée d’une requête. Scikit-learn parle d’apprentissage basé sur les instances, non généralisant.

Fonctionnement

1. Choisissez k et une mesure de distance. La distance euclidienne est le choix le plus courant.
2. Trouvez les k points stockés les plus proches du point de requête.
3. Attribuez au point de requête la classe la plus fréquente parmi ces k points.

Par défaut, chaque voisin dispose d’une voix. Dans le kNN pondéré, les voisins les plus proches comptent davantage, par exemple avec un poids de 1/d, où d est la distance au voisin.

Choisir k

La meilleure valeur de k dépend des données. Un k plus grand atténue le bruit, mais rend les frontières entre classes moins nettes. La validation croisée permet de trouver une bonne valeur de k à partir des données. Pour deux classes, un k impair évite les égalités de vote.

Limites

• Si les variables ont des unités ou des échelles différentes, normaliser chaque variable peut améliorer nettement la précision.
• Une recherche par force brute compare la requête à chaque point stocké. Cela devient impraticable lorsque le nombre de points augmente.
• La recherche par arbre, comme l’arbre KD, n’est rapide qu’en faible dimension (en dessous d’environ 20). En grande dimension, la distance euclidienne est aussi moins utile, car tous les vecteurs sont presque à égale distance de la requête.
• Des bibliothèques comme Faiss recherchent dans de grands ensembles de vecteurs. Elles proposent une recherche exacte et des index compressés. Les index compressés donnent une recherche moins précise.

Histoire

Evelyn Fix et Joseph Hodges ont d’abord développé la méthode en 1951, dans un rapport pour la USAF School of Aviation Medicine. Thomas Cover et Hart ont publié « Nearest neighbor pattern classification » en 1967. Avec des données d’entraînement illimitées, le taux d’erreur de la règle du plus proche voisin (1-NN) n’est pas supérieur au double du taux d’erreur de Bayes.