Nearest Neighbours
Nearest Neighbours, littéralement « plus proches voisins » en français, est un concept fondamental en apprentissage automatique et en reconnaissance de formes. Il désigne une méthode d’apprentissage supervisé non paramétrique utilisée principalement pour des tâches de classification et de régression. L’idée centrale repose sur l’intuition que des objets similaires ont tendance à appartenir à la même catégorie ou à avoir des valeurs de sortie similaires. Ainsi, pour prédire la classe ou la valeur d’un nouveau point de données, l’algorithme des plus proches voisins examine les ‘k’ points de données les plus similaires (ses plus proches voisins) dans l’ensemble d’entraînement et utilise leurs caractéristiques pour effectuer une prédiction.
Les concepts fondamentaux et les principes essentiels associés aux Nearest Neighbours sont multiples. Au cœur de la méthode se trouve la notion de « proximité » ou de « similarité » entre les points de données. Cette similarité est quantifiée à l’aide d’une mesure de distance. Les mesures de distance courantes incluent la distance Euclidienne (la distance « en ligne droite » entre deux points), la distance de Manhattan (la somme des différences absolues des coordonnées), la distance de Minkowski (une généralisation des distances Euclidienne et de Manhattan), et pour des données spécifiques, la distance de Hamming (pour les chaînes de caractères ou les vecteurs binaires) ou la similarité cosinus (pour mesurer l’orientation plutôt que la magnitude, souvent utilisée pour les données textuelles). Chaque point de données est représenté comme un vecteur dans un espace multidimensionnel appelé l’espace des caractéristiques, où chaque dimension correspond à une caractéristique de l’objet. Le nombre de voisins à considérer, noté ‘k’, est un hyperparamètre crucial. Pour la classification, la prédiction pour un nouveau point est généralement déterminée par un vote majoritaire parmi ses ‘k’ plus proches voisins : le point est assigné à la classe la plus fréquente parmi ses voisins. Pour la régression, la prédiction est souvent la moyenne ou la médiane des valeurs des ‘k’ plus proches voisins. Une caractéristique distinctive des algorithmes basés sur les Nearest Neighbours est qu’ils sont considérés comme des méthodes d’apprentissage paresseux (lazy learning) ou basés sur l’instance (instance-based learning). Cela signifie qu’ils ne construisent pas de modèle explicite pendant la phase d’entraînement ; au lieu de cela, ils mémorisent l’ensemble des données d’entraînement et effectuent tous les calculs de similarité au moment de la prédiction.
L’importance et la pertinence des Nearest Neighbours découlent de plusieurs de ses caractéristiques. Sa simplicité conceptuelle et sa facilité d’implémentation en font un excellent point de départ pour de nombreux problèmes d’apprentissage automatique. En tant qu’algorithme non paramétrique, il ne fait aucune hypothèse restrictive sur la distribution sous-jacente des données, ce qui le rend flexible et capable de s’adapter à des frontières de décision complexes et non linéaires. Son impact est significatif dans divers domaines, notamment la reconnaissance de formes, l’exploration de données, la recherche d’informations et les systèmes de recommandation, où l’identification d’éléments similaires est une tâche centrale. Malgré l’émergence d’algorithmes plus sophistiqués, la méthode des Nearest Neighbours reste une référence et est souvent utilisée comme baseline pour évaluer les performances de nouvelles techniques.
Les applications pratiques des Nearest Neighbours sont nombreuses et variées. Dans les systèmes de recommandation, il peut être utilisé pour suggérer des produits, des films ou des articles à un utilisateur en trouvant d’autres utilisateurs ayant des goûts similaires (filtrage collaboratif) ou des articles similaires à ceux que l’utilisateur a aimés (filtrage basé sur le contenu). Par exemple, si vous aimez un film A, le système pourrait rechercher les ‘k’ films les plus similaires au film A en termes de genre, d’acteurs, ou de notes d’utilisateurs, et vous les recommander. En reconnaissance d’images, il a été utilisé pour des tâches telles que la classification de chiffres manuscrits (par exemple, l’ensemble de données MNIST), où une nouvelle image de chiffre est comparée aux images de chiffres existantes dont l’identité est connue. Dans le domaine de la détection d’anomalies, un point de données qui est très éloigné de ses ‘k’ plus proches voisins peut être considéré comme une anomalie ou une valeur aberrante, ce qui est utile pour la détection de fraudes financières ou de pannes de système. En bioinformatique, il peut aider à classifier des gènes ou des protéines en fonction de leurs séquences ou de leurs profils d’expression. En traitement du langage naturel, des approches basées sur les voisins peuvent être utilisées pour la correction orthographique (en trouvant les mots corrects les plus proches d’un mot mal orthographié) ou pour la classification de documents (en assignant une catégorie à un document en fonction des catégories des documents les plus similaires).
Il existe plusieurs nuances, interprétations et variations du concept de base des Nearest Neighbours. La variation la plus connue est l’algorithme k-Nearest Neighbours (k-NN), où ‘k’ est le nombre de voisins considérés. Le choix de ‘k’ est critique : un petit ‘k’ peut rendre le modèle sensible au bruit, tandis qu’un grand ‘k’ peut lisser les frontières de décision et introduire un biais. Une autre variation concerne la pondération des voisins : au lieu d’un vote majoritaire simple, les voisins plus proches peuvent avoir une influence plus importante sur la prédiction. Cette pondération est souvent inversement proportionnelle à la distance. Pour améliorer l’efficacité de la recherche des plus proches voisins, en particulier avec de grands ensembles de données, des structures de données et des algorithmes d’accélération tels que les KD-trees (pour les données de faible dimension) et les Ball trees (pour les données de plus haute dimension) ont été développés. Des adaptations existent également pour gérer différents types de données, comme les données catégorielles (où des mesures de distance comme la distance de Hamming ou des métriques de chevauchement sont utilisées) ou les données mixtes (combinant des caractéristiques numériques et catégorielles). Enfin, dans les contextes où une recherche exacte des plus proches voisins est trop coûteuse, des algorithmes de recherche approximative des plus proches voisins (Approximate Nearest Neighbours, ANN) sont employés. Ces méthodes sacrifient une certaine précision pour gagner en vitesse, ce qui est crucial pour les applications à très grande échelle.
Plusieurs concepts sont étroitement liés aux Nearest Neighbours. Il s’agit d’une technique d’apprentissage supervisé, au même titre que la régression logistique, les machines à vecteurs de support (SVM) ou les arbres de décision, et elle peut être utilisée pour la classification ou la régression. Le concept de mesure de similarité ou de distance est central, tout comme la notion d’espace des caractéristiques. Bien qu’il soit principalement supervisé, les idées de proximité sont également fondamentales en apprentissage non supervisé, notamment dans les algorithmes de clustering (regroupement) comme k-means, où l’objectif est de regrouper des points de données similaires. La réduction de dimensionnalité, par des techniques comme l’Analyse en Composantes Principales (ACP), est souvent utilisée en prétraitement pour les algorithmes de Nearest Neighbours afin de combattre le « fléau de la dimensionnalité » et d’améliorer les performances. En termes de synonymie, k-Nearest Neighbours (k-NN) est la dénomination la plus courante de l’algorithme. On parle aussi d’apprentissage basé sur l’instance ou d’apprentissage par l’exemple. Il n’y a pas d’antonyme direct, mais on peut contraster les approches de Nearest Neighbours (apprentissage paresseux) avec les méthodes d’apprentissage impatient (eager learning), comme les réseaux de neurones ou les arbres de décision, qui construisent un modèle explicite pendant la phase d’entraînement et l’utilisent ensuite pour des prédictions rapides.
Un bref aperçu de l’origine et de l’évolution des Nearest Neighbours montre que l’idée n’est pas récente. Les fondations de la méthode ont été posées dès 1951 par Evelyn Fix et Joseph Hodges Jr. dans un rapport technique de l’U.S. Air Force School of Aviation Medicine, où ils ont introduit une méthode non paramétrique pour la classification discriminante. Cependant, l’algorithme est plus communément associé aux travaux de Thomas Cover et Peter Hart qui, en 1967, ont formalisé la règle du plus proche voisin (1-NN) et ont analysé ses propriétés, notamment en montrant que son taux d’erreur asymptotique n’est jamais supérieur à deux fois le taux d’erreur de Bayes (le taux d’erreur optimal théorique). Ils ont également étendu l’analyse à la version k-NN. Depuis lors, la recherche s’est concentrée sur l’amélioration de son efficacité computationnelle, notamment pour la recherche des voisins dans de grands ensembles de données, et sur l’adaptation de la méthode à divers types de données et de problèmes.
Le concept des Nearest Neighbours présente plusieurs avantages, inconvénients, défis et limitations. Parmi les avantages, sa simplicité de compréhension et d’implémentation est majeure. Il est non paramétrique, ce qui signifie qu’il ne fait aucune hypothèse sur la distribution sous-jacente des données et peut donc modéliser des relations complexes. Il peut souvent atteindre de bonnes performances avec peu de réglages d’hyperparamètres, en dehors du choix de ‘k’ et de la métrique de distance. Il s’adapte naturellement aux changements dans les données, car la « connaissance » est directement dans les données d’entraînement ; si les données changent, les prédictions s’adapteront si la base de données est mise à jour.
Cependant, les inconvénients sont notables. L’un des principaux est son coût computationnel lors de la phase de prédiction. Pour classer un nouveau point, il faut calculer sa distance par rapport à tous les points de l’ensemble d’entraînement, ce qui peut être très lent pour de grands ensembles de données (complexité en O(N*D) où N est le nombre d’instances d’entraînement et D le nombre de dimensions, pour une recherche naïve). Il est très sensible au « fléau de la dimensionnalité » : en haute dimension, la notion de distance devient moins significative, et les performances de k-NN se dégradent. Le choix de ‘k’ est crucial et peut nécessiter une validation croisée. De même, la performance est fortement dépendante du choix de la métrique de distance, qui doit être appropriée à la nature des données. Les caractéristiques doivent souvent être normalisées ou standardisées pour éviter que celles ayant de grandes échelles ne dominent le calcul de distance. Enfin, l’algorithme peut être affecté par la présence de caractéristiques non pertinentes ou redondantes, car toutes les caractéristiques contribuent également au calcul de la distance, à moins d’utiliser des techniques de pondération de caractéristiques ou de sélection de caractéristiques.
Les défis incluent donc la sélection optimale de ‘k’, le choix d’une métrique de distance adaptée, la gestion des données déséquilibrées (où une classe majoritaire peut dominer le vote des voisins), et surtout la scalabilité aux très grands ensembles de données et aux données de haute dimension. Des techniques comme les arbres KD ou les Ball trees tentent de pallier ce dernier problème, mais leur efficacité diminue également avec l’augmentation de la dimensionnalité.