K-Nearest Neighbors (k-NN) est un algorithme d'apprentissage supervisé non paramétrique utilisé à la fois pour la classification et la régression. En classification, un nouveau point de données se voit attribuer la classe la plus fréquente parmi ses k plus proches voisins dans l'espace des caractéristiques, déterminée par une métrique de distance. En régression, la sortie est la moyenne (ou la moyenne pondérée) des valeurs de ces voisins. L'algorithme est basé sur les instances, ce qui signifie qu'il stocke l'ensemble du jeu de données d'entraînement et n'effectue des calculs que lorsqu'une prédiction est requise, différant toute généralisation jusqu'au moment de la requête.
La méthode a été développée pour la première fois par Evelyn Fix et Joseph Hodges en 1951, puis étendue par Thomas Cover. C'est l'un des algorithmes d'apprentissage automatique les plus simples, mais il peut atteindre une précision compétitive dans de nombreux domaines, en particulier lorsque la frontière de décision est irrégulière. Ses performances dépendent fortement du choix de k, de la métrique de distance et de la mise à l'échelle des caractéristiques.
Développement historique
Les origines du k-NN remontent à 1951, lorsque Evelyn Fix et Joseph Hodges, travaillant à l'US Air Force School of Aviation Medicine, ont introduit une méthode de classification non paramétrique basée sur les plus proches voisins. Leurs travaux étaient motivés par la nécessité de classer des observations sans supposer une distribution statistique spécifique. En 1967, Thomas Cover et Peter Hart ont publié un article fondateur qui a formalisé les propriétés de l'algorithme, y compris des bornes sur son taux d'erreur par rapport au classificateur optimal de Bayes. Cela a établi le k-NN comme une approche théoriquement fondée en reconnaissance de formes. L'algorithme a gagné en popularité dans les années 1960 et 1970 avec l'essor de l'informatique, car il nécessitait un temps d'entraînement minimal mais un stockage substantiel. Des développements ultérieurs, tels que l'introduction du vote pondéré et de l'apprentissage de la métrique de distance, ont remédié à certaines de ses limitations.
Aperçu de l'algorithme
En classification k-NN, l'entrée consiste en un ensemble d'entraînement d'exemples étiquetés, chacun représenté par un vecteur de caractéristiques dans un espace multidimensionnel. L'algorithme stocke ces vecteurs et leurs étiquettes. Lorsqu'un point de requête est présenté, il calcule la distance entre la requête et tous les points d'entraînement, sélectionne les k plus proches, et attribue la classe qui apparaît le plus fréquemment parmi eux. Pour k=1, la requête est simplement attribuée à la classe de son plus proche voisin. Le choix de k est critique : un petit k peut entraîner une variance élevée et une sensibilité au bruit, tandis qu'un grand k peut trop lisser la frontière de décision et inclure des points d'autres classes.
Pour la régression, la sortie est la moyenne des valeurs cibles des k plus proches voisins. C'est ce qu'on appelle le lissage par plus proches voisins. Si k=1, cela devient une interpolation par plus proche voisin, où la valeur prédite est exactement celle du point d'entraînement le plus proche. Les variantes pondérées attribuent une influence plus élevée aux voisins plus proches, souvent en utilisant des poids proportionnels à l'inverse de la distance (1/d).
Métriques de distance et mise à l'échelle des caractéristiques
Le choix de la métrique de distance est crucial. Pour les caractéristiques continues, la distance euclidienne est la plus courante. Pour les caractéristiques discrètes, comme dans la classification de textes, la distance de Hamming ou des métriques de chevauchement sont utilisées. Dans des domaines spécialisés comme l'analyse de l'expression génique, des coefficients de corrélation (Pearson, Spearman) ont été employés. La dépendance de l'algorithme à la distance signifie que des caractéristiques avec des unités ou des échelles différentes peuvent dominer le calcul. Par conséquent, normaliser chaque caractéristique à une échelle commune (par exemple, score z ou mise à l'échelle min-max) est essentiel pour garantir une contribution égale. Cette étape de prétraitement peut améliorer considérablement la précision.
Propriétés statistiques
D'un point de vue statistique, le k-NN est une méthode non paramétrique car elle ne suppose pas une forme fonctionnelle pour la distribution sous-jacente des données. Les données d'entraînement sont supposées être des paires (X_i, Y_i) où X_i est un vecteur de caractéristiques et Y_i est l'étiquette de classe. Pour un point de requête donné x, les points d'entraînement sont réordonnés par leur distance à x. Le taux d'erreur de l'algorithme converge vers le taux d'erreur de Bayes à mesure que la taille de l'échantillon augmente, à condition que k croisse de manière appropriée avec n et que k/n tende vers zéro. Cette propriété, établie par Cover et Hart, rend le k-NN asymptotiquement optimal. Cependant, dans des échantillons finis, l'algorithme souffre de la malédiction de la dimensionnalité : à mesure que le nombre de caractéristiques augmente, le volume de l'espace croît de manière exponentielle, et les points deviennent épars, rendant les mesures de distance moins significatives.
Avantages et inconvénients
Un avantage majeur du k-NN est sa simplicité et l'absence de phase d'entraînement. Il peut être mis à jour facilement en ajoutant de nouveaux points de données. Il est également efficace pour les problèmes multi-classes et peut capturer des frontières de décision complexes. Cependant, il présente des inconvénients notables. Le temps de prédiction est lent car il nécessite de calculer les distances à tous les points d'entraînement, ce qui le rend impraticable pour de grands ensembles de données sans optimisation (par exemple, en utilisant des KD-trees ou des ball trees). Il est sensible aux caractéristiques non pertinentes et aux données bruitées. L'algorithme est également sensible à la structure locale des données, ce qui signifie que les valeurs aberrantes ou les distributions de classes déséquilibrées peuvent fausser les résultats. Dans les distributions asymétriques, les classes majoritaires dominent car elles sont plus susceptibles d'apparaître parmi les k voisins. La pondération par distance inverse ou l'utilisation de techniques d'abstraction peuvent atténuer ce problème.
Variantes et extensions
Plusieurs variantes répondent aux limitations du k-NN. Le k-NN pondéré attribue des poids aux voisins en fonction de la distance, de sorte que les points plus proches aient plus d'influence. Les méthodes d'apprentissage de la métrique de distance, telles que le plus proche voisin à marge large et l'analyse des composantes de voisinage, apprennent une métrique de distance personnalisée pour améliorer la précision. Le k-NN édité supprime les points d'entraînement bruités ou mal classés pour améliorer la généralisation. Le k-NN condensé réduit la taille de l'ensemble d'entraînement en ne conservant que les points essentiels pour la classification. Le k-NN localement adaptatif ajuste k en fonction de la densité de la région autour du point de requête. Ces variantes ont été appliquées dans des domaines comme apprentissage automatique et intelligence artificielle pour améliorer les performances.
Applications
L'algorithme k-NN est utilisé dans divers domaines. En reconnaissance de formes, il est appliqué à la classification d'images et à la reconnaissance de l'écriture manuscrite. En médecine, il est utilisé pour le diagnostic basé sur les caractéristiques des patients. En finance, il aide à la notation de crédit et à la détection de fraude. Dans les systèmes de recommandation, il trouve des utilisateurs ou des articles similaires. En bioinformatique, il classe les données d'expression génique. Sa simplicité en fait une référence courante pour comparer des modèles plus complexes comme réseau de neurones et apprentissage profond.
Relation avec d'autres méthodes
Le k-NN est une forme d'apprentissage basé sur les instances, distinct des approches basées sur des modèles comme réseau de neurones ou machine à vecteurs de support qui construisent un modèle explicite pendant l'entraînement. Il est également lié à l'estimation de densité non paramétrique. Dans le contexte plus large de apprentissage automatique, le k-NN est souvent utilisé comme référence. Il a influencé le développement du hachage sensible à la localité et de la recherche approximative du plus proche voisin, utilisés dans les systèmes à grande échelle. Bien que des méthodes modernes comme apprentissage profond aient surpassé le k-NN dans de nombreuses tâches, le k-NN reste précieux pour les petits ensembles de données et les prédictions interprétables.
Considérations pratiques
Lors de la mise en œuvre du k-NN, plusieurs problèmes pratiques se posent. La valeur de k est généralement choisie par validation croisée. Des valeurs impaires de k sont souvent utilisées pour éviter les égalités dans la classification binaire. La mise à l'échelle des caractéristiques est essentielle. Des structures de données efficaces comme les KD-trees peuvent accélérer la recherche du plus proche voisin, mais elles se dégradent en haute dimension. Pour de très grands ensembles de données, des méthodes approximatives sont nécessaires. L'utilisation de la mémoire de l'algorithme est proportionnelle à la taille de l'ensemble d'entraînement, ce qui peut être une limitation. Dans les applications modernes, le k-NN est parfois combiné avec d'autres algorithmes, par exemple en l'utilisant comme classificateur final sur des embeddings appris à partir d'un réseau de neurones.
Voir aussi
- apprentissage automatique
- intelligence artificielle
- réseau de neurones
- apprentissage profond
- Stanford AI Lab
- MIT CSAIL
- Université Carnegie Mellon
- Berkeley AI Research
- Xerox PARC
- Thomas Dietterich
- Michael Jordan
- Daphne Koller
- Anima Anandkumar
- Samy Bengio
- Joshua Tenenbaum
- Brendan Lake
- Melanie Mitchell
- Aaron Courville
- Alexei Efros
- Ali Rahimi