K-Nearest Neighbors (kNN)
K-Nearest Neighbors, souvent abrégé en kNN, est un algorithme d’apprentissage supervisé fondamental, non paramétrique et basé sur les instances, utilisé principalement pour des tâches de classification et de régression en apprentissage automatique. Sa simplicité conceptuelle et sa facilité d’implémentation en font un point de départ courant pour de nombreux problèmes et un outil pédagogique essentiel dans le domaine. Contrairement à d’autres méthodes qui construisent un modèle explicite à partir des données d’entraînement, kNN fonctionne en mémorisant l’ensemble des données d’entraînement et effectue des prédictions pour de nouvelles instances en se basant sur la similarité avec les exemples connus les plus proches.
Les concepts fondamentaux de kNN reposent sur l’idée intuitive que les points de données similaires ont tendance à exister à proximité les uns des autres dans l’espace des caractéristiques. Pour prédire la classe (classification) ou la valeur (régression) d’un nouveau point de données, l’algorithme identifie les ‘k’ points de données les plus proches (les « voisins ») dans l’ensemble d’entraînement. La proximité est généralement mesurée à l’aide d’une métrique de distance, la plus courante étant la distance euclidienne, bien que d’autres métriques comme la distance de Manhattan, la distance de Minkowski ou la distance de Hamming (pour les données catégorielles) puissent être utilisées en fonction de la nature des données. Le paramètre ‘k’, un entier positif spécifié par l’utilisateur, détermine le nombre de voisins à considérer. Pour la classification, la prédiction est souvent la classe majoritaire parmi les ‘k’ voisins. Pour la régression, la prédiction est généralement la moyenne ou la médiane des valeurs des ‘k’ voisins. kNN est qualifié de « non paramétrique » car il ne fait aucune hypothèse forte sur la distribution sous-jacente des données, contrairement aux modèles paramétriques (comme la régression linéaire) qui ont un nombre fixe de paramètres. Il est également « basé sur les instances » ou un algorithme « paresseux » (lazy learning) car il diffère l’essentiel du calcul au moment de la prédiction, sans phase d’entraînement explicite pour construire un modèle généralisé. L’apprentissage consiste simplement à stocker l’ensemble des données.
L’importance et la pertinence de kNN résident dans sa simplicité, son interprétabilité et sa capacité à capturer des relations non linéaires complexes dans les données sans nécessiter la construction d’un modèle explicite. Il sert souvent de référence (baseline) pour évaluer les performances d’algorithmes plus complexes. Bien qu’il puisse être computationnellement coûteux pour de grands ensembles de données et sensible aux dimensions non pertinentes, sa capacité à s’adapter localement aux données le rend efficace dans certains scénarios où les frontières de décision sont très irrégulières. Son impact est notable dans l’introduction aux concepts d’apprentissage basé sur la distance et l’apprentissage non paramétrique.
Les applications pratiques de kNN sont variées. En classification, il est utilisé dans la reconnaissance de formes (par exemple, la classification d’images de chiffres manuscrits où un nouveau chiffre est classé en fonction des chiffres les plus similaires dans la base de données), la détection de spam (en classant un email comme spam ou non en fonction des emails similaires connus), ou le diagnostic médical préliminaire. En régression, kNN peut être utilisé pour prédire des valeurs continues, comme l’estimation du prix d’une maison en se basant sur les prix de ‘k’ maisons similaires dans le voisinage, ou la prédiction de la consommation d’énergie basée sur des jours aux conditions météorologiques similaires. Les systèmes de recommandation utilisent souvent des approches basées sur kNN (filtrage collaboratif basé sur les utilisateurs ou les items) pour suggérer des produits, des films ou de la musique en trouvant des utilisateurs ou des items « voisins » (similaires). Il est également appliqué en détection d’anomalies, où les points de données éloignés de leurs voisins peuvent être considérés comme des anomalies.
Il existe plusieurs nuances et variations de l’algorithme kNN standard. Une variation courante est le kNN pondéré (Weighted kNN), où l’influence de chaque voisin sur la prédiction est inversement proportionnelle à sa distance par rapport au point de requête. Les voisins plus proches ont ainsi plus de poids que les voisins plus éloignés, ce qui peut améliorer la précision. Le choix de la métrique de distance est une autre nuance cruciale ; la distance euclidienne est adaptée aux caractéristiques numériques continues, mais des métriques spécifiques comme la distance de Hamming sont nécessaires pour les caractéristiques catégorielles. La gestion des données de types mixtes (numériques et catégorielles) nécessite des stratégies de distance adaptées ou des transformations de données. La performance de kNN est très sensible à ce qu’on appelle la « malédiction de la dimensionnalité » (curse of dimensionality) : en très haute dimension, la notion de proximité devient moins significative car tous les points tendent à être éloignés les uns des autres. Des techniques de réduction de dimensionnalité (comme l’Analyse en Composantes Principales – ACP) ou de sélection de caractéristiques sont souvent appliquées avant d’utiliser kNN. Des structures de données optimisées comme les arbres KD (k-dimensional trees) ou les arbres de boules (ball trees) sont utilisées pour accélérer la recherche des plus proches voisins dans de grands ensembles de données, réduisant ainsi le coût computationnel lors de la prédiction.
Plusieurs concepts sont étroitement liés à kNN. Il appartient à la famille plus large des algorithmes d’apprentissage basé sur les instances (Instance-Based Learning) et d’apprentissage paresseux (Lazy Learning). Le cas le plus simple, k=1, est appelé l’algorithme du plus proche voisin (Nearest Neighbor). Les métriques de distance sont un concept central indissociable. Il contraste avec les algorithmes d’apprentissage « avides » (eager learning) comme les arbres de décision, les machines à vecteurs de support (SVM) ou les réseaux neuronaux, qui construisent un modèle pendant une phase d’entraînement distincte. Il contraste également avec les modèles paramétriques (ex: régression logistique, analyse discriminante linéaire) qui apprennent un ensemble fixe de paramètres. Il n’y a pas d’antonyme direct, mais les modèles paramétriques ou les méthodes d’apprentissage avides représentent des approches fondamentalement différentes.
L’origine de l’algorithme kNN remonte aux années 1950. Bien que souvent attribué à Cover et Hart qui l’ont formellement décrit et analysé dans leur article de 1967 sur le « Nearest Neighbor Pattern Classification », les idées sous-jacentes ont été introduites plus tôt, notamment dans un rapport non publié de l’US Air Force School of Aviation Medicine par Fix et Hodges en 1951, qui proposait une règle de classification non paramétrique basée sur les voisins. L’algorithme a gagné en popularité avec l’augmentation de la puissance de calcul, qui a rendu sa nature computationnellement intensive plus gérable.
Les avantages de kNN incluent sa simplicité d’implémentation et de compréhension. Il est très intuitif et les résultats peuvent être facilement interprétés en examinant les voisins utilisés pour la prédiction. Il n’y a pas de phase d’entraînement longue et coûteuse, car l’algorithme stocke simplement les données. Il est naturellement adapté aux problèmes multi-classes. Sa nature non paramétrique lui permet de s’adapter à des frontières de décision arbitrairement complexes et il peut bien fonctionner lorsque les données ne suivent pas de distribution particulière.
Cependant, kNN présente aussi des inconvénients et des défis notables. Le coût computationnel de la prédiction peut être élevé, en particulier pour les grands ensembles de données, car il nécessite de calculer la distance entre le nouveau point et tous les points d’entraînement (bien que des optimisations existent). Il nécessite une quantité importante de mémoire pour stocker l’intégralité de l’ensemble d’entraînement. L’algorithme est très sensible à la présence de caractéristiques non pertinentes ou redondantes, car elles peuvent fausser les mesures de distance. La performance se dégrade considérablement avec l’augmentation du nombre de dimensions (malédiction de la dimensionnalité). Il est nécessaire de mettre à l’échelle (normaliser ou standardiser) les caractéristiques pour éviter que celles ayant de grandes plages de valeurs ne dominent la mesure de distance. Enfin, le choix de la valeur optimale de ‘k’ et de la métrique de distance appropriée est crucial et souvent déterminé empiriquement par validation croisée, ce qui peut ajouter une charge de calcul supplémentaire.