L'algorithme des k plus proches voisins (k-NN) est une méthode d'apprentissage non paramétrique et basée sur les instances, utilisée pour la classification et la régression. Dans les deux cas, l'entrée est constituée des k exemples d'entraînement les plus proches dans un espace de caractéristiques. La sortie dépend de l'utilisation de k-NN pour la classification ou la régression : en classification, la sortie est une appartenance à une classe, déterminée par un vote majoritaire parmi les k voisins les plus proches ; en régression, la sortie est la moyenne (ou la moyenne pondérée) des valeurs des k voisins les plus proches. k-NN est un type d'apprentissage paresseux, où la fonction n'est approximée que localement, et tous les calculs sont différés jusqu'à l'évaluation de la fonction. En raison de sa dépendance aux calculs de distance, l'algorithme est sensible à la structure locale des données et au choix de la métrique de distance.
L'algorithme a été développé pour la première fois en 1951 par Evelyn Fix et Joseph Hodges à l'école de médecine aéronautique de l'US Air Force, à l'origine comme technique de classification non paramétrique. Il a ensuite été étendu et formalisé par Thomas Cover et Peter Hart en 1967, qui ont établi ses bornes d'erreur asymptotiques. Depuis lors, k-NN est devenu un outil fondamental dans Machine learning, la reconnaissance de formes et l'exploration de données, souvent utilisé comme référence pour des modèles plus complexes.
Comment cela fonctionne
Étant donné un point de requête, l'algorithme calcule la distance (typiquement euclidienne, Manhattan ou Minkowski) à chaque exemple d'entraînement. Il sélectionne ensuite les k exemples d'entraînement ayant les plus petites distances. Pour la classification, le label prédit est celui qui est le plus fréquent parmi ces k voisins ([majority_vote|majority_vote]]). Pour la régression, la valeur prédite est la moyenne des valeurs cibles des voisins. Le choix de k est critique : une petite valeur de k (par exemple, 1) entraîne une grande variance et une sensibilité au bruit, tandis qu'une grande valeur de k peut lisser les motifs locaux, augmentant le biais. La pratique courante consiste à sélectionner k par validation croisée, souvent en utilisant des valeurs impaires pour la classification binaire afin d'éviter les égalités.
L'algorithme nécessite également une métrique de distance. La distance euclidienne est standard pour les caractéristiques continues, mais pour les données en haute dimension ou catégorielles, d'autres métriques comme la distance de Hamming ou la similarité cosinus peuvent être utilisées. La mise à l'échelle des caractéristiques (par exemple, la normalisation ou la standardisation) est essentielle car les caractéristiques ayant de plus grandes plages dominent le calcul de la distance.
Propriétés et variantes
k-NN est non paramétrique, ce qui signifie qu'il ne fait pas d'hypothèses fortes sur la distribution sous-jacente des données. Il est également basé sur les instances, stockant l'ensemble d'entraînement entier et l'utilisant directement au moment de la prédiction. Cela rend l'entraînement trivial (essentiellement le stockage des données) mais la prédiction coûteuse en calcul, avec une complexité temporelle de O(nd) par requête, où n est le nombre d'exemples d'entraînement et d est le nombre de caractéristiques.
Plusieurs variantes pallient ces limitations. Le k-NN pondéré attribue une plus grande influence aux voisins plus proches, souvent en utilisant des distances inverses comme pondérations. La régression pondérée localement ajuste un modèle linéaire dans le voisinage. Pour les grands ensembles de données, des techniques de recherche des plus proches voisins approximatives, telles que les arbres k-d, les arbres boules ou le hachage sensible locales, réduisent le coût de recherche. Dans les dimensions élevées, la malédiction de la dimensionnalité dégrade la performance, car les distances deviennent moins [discriminatives] ; la réduction de dimensionnalité ou la sélection de caractéristiques est souvent appl