Qu’est-ce que l’algorithme des k plus proches voisins (KNN) ?

Bien que l'algorithme k-NN puisse être utilisé à la fois pour des problèmes de régression et de classification, il est généralement employé comme algorithme de classification, en supposant que des points similaires se trouvent à proximité les uns des autres.

Pour résoudre les problèmes de classification, une étiquette de classe est attribuée à travers un vote de majorité : c’est l’étiquette la plus fréquemment représentée autour d’un point de données qui est utilisée. Bien qu’il s’agisse techniquement d’un « vote de pluralité », le terme « vote de majorité » est couramment employé dans la littérature spécialisée. Techniquement, le « vote de majorité » requiert une majorité supérieure à 50 %, atteignable en principe lorsqu’il n’y a que deux catégories. Lorsqu’il y a plusieurs classes, par exemple quatre catégories, recueillir 50 % des votes n’est pas indispensable pour tirer des conclusions à propos d’une classe. En effet, on peut attribuer une étiquette à une classe avec un vote supérieur à 25 %. L’Université du Wisconsin-Madison résume bien cette distinction dans un exemple que vous pouvez consulter ici.

Les problèmes de régression utilisent un concept similaire à la classification, mais dans ce cas, c’est la moyenne des k plus proches voisins qui est utilisée pour faire une prédiction. La principale distinction réside dans le fait que la classification concerne des valeurs discrètes, tandis que la régression porte sur des valeurs continues. Cependant, avant de pouvoir effectuer une classification, il est nécessaire de définir une distance. La distance euclidienne est la plus couramment utilisée, et nous l’examinerons plus en détail ci-dessous.

Il est également important de noter que l’algorithme k-NN fait partie de la famille des modèles d’« apprentissage paresseux », ce qui signifie qu’il stocke simplement le jeu de données d’entraînement sans passer par une étape d’entraînement. Cela signifie aussi que tous les calculs sont effectués au moment de la classification ou de la prédiction. Comme il dépend fortement de la mémoire pour stocker toutes les données d’apprentissage, on parle également d’une méthode d’apprentissage basée sur les instances ou sur la mémoire.

Evelyn Fix et Joseph Hodges sont crédités des premières idées autour du modèle k-NN dans leur publication de 1951, tandis que Thomas Cover a développé ce concept dans sa recherche « Nearest Neighbor Pattern Classification » (Classification des motifs par les plus proches voisins). Bien que cet algorithme soit moins populaire aujourd’hui, il reste l’un des premiers que l’on apprend en science des données, grâce à sa simplicité et à sa précision. Cependant, à mesure que la taille des jeux de données augmente, k-NN devient de plus en plus inefficace, ce qui nuit aux performances globales du modèle. Il est souvent utilisé pour des systèmes de recommandation simples, la reconnaissance des formes, le data mining, les prédictions sur les marchés financiers, la détection des intrusions, etc.

Pour résumer, l'objectif de l'algorithme des k plus proches voisins est d'identifier les voisins les plus proches d'un point donné, afin de pouvoir lui attribuer une étiquette de classe. Pour ce faire, le k-NN a quelques exigences :

Pour déterminer quels points de données sont les plus proches d’un point donné, il est nécessaire de calculer la distance entre ce point et les autres points de données. Ces mesures de distance aident à définir des frontières décisionnelles, qui partitionnent les points en différentes régions. Les frontières décisionnelles sont souvent représentées à l’aide de diagrammes de Voronoï.

Bien qu'il existe plusieurs mesures de distance parmi lesquelles vous pouvez choisir, cet article ne couvre que les suivantes :

Distance euclidienne (p=2) : il s’agit de la mesure de distance la plus couramment utilisée, limitée aux vecteurs réels. Elle mesure la distance en ligne droite entre le point donné et le point de référence, selon la formule ci-dessous.

Distance de Manhattan (p=1): il s'agit également d'une autre mesure de distance populaire, qui mesure la valeur absolue entre deux points. Aussi appelée distance « taxi » ou « city block » (pâté de maison), car elle est souvent représentée par une grille, illustrant la manière dont on pourrait naviguer d'une adresse à une autre en suivant les rues d'une ville.

Distance de Minkowski: cette mesure de distance est la forme généralisée des mesures de distance euclidienne et de Manhattan. Le paramètre p de la formule permet de générer d'autres mesures de distance. La distance euclidienne est obtenue lorsque p est égal à 2, et la distance de Manhattan lorsque p est égal à 1.

Distance de Hamming : cette technique est généralement utilisée avec les vecteurs booléens ou les chaînes de caractères pour identifier les points où les vecteurs ne correspondent pas. C’est pourquoi on l’appelle également « indicateur de chevauchement ». Pour la calculer, on utilise la formule suivante :

Par exemple, si vous comparez deux chaînes de caractères, la distance de Hamming serait de 2, car seules deux des valeurs diffèrent.

La valeur k dans l'algorithme k-NN détermine le nombre de voisins qui seront pris en compte pour établir la classification d'un point donné. Par exemple, si k=1, l'instance sera assignée à la même classe que son voisin le plus proche.

La définition de k est un exercice d'équilibre, car des valeurs différentes peuvent entraîner un surajustement ou un sous-ajustement. Des valeurs faibles de k peuvent entraîner une variance élevée avec un biais faible, tandis que des valeurs élevées peuvent entraîner un biais élevé avec une variance réduite. Le choix de k dépendra principalement des données d'entrée : des données comportant plus de valeurs aberrantes ou de bruit seront généralement mieux adaptées à des valeurs de k plus élevées. Il est souvent recommandé d'utiliser un nombre impair pour k afin d'éviter les égalités dans la classification. Des techniques de validation croisée peuvent également aider à déterminer la valeur optimale de k pour votre jeu de données.

Pour aller plus loin, vous pouvez explorer l’algorithme k-NN en utilisant Python et scikit-learn (également connu sous le nom de sklearn). Notre tutoriel dans Watson Studio vous guide à travers la syntaxe de base de cette bibliothèque, qui comprend également d’autres bibliothèques populaires comme NumPy, pandas et Matplotlib. Voici un exemple de code pour créer et prédire un modèle k-NN :

L’algorithme k-NN est utilisé dans diverses applications, principalement dans le cadre de la classification. Voici quelques exemples :

• Prétraitement des données : les jeux de données contiennent souvent des valeurs manquantes, mais l’algorithme k-NN peut estimer ces valeurs via un processus appelé imputation des données manquantes.
  
  
• Moteurs de recommandation : le k-NN est utilisé dans les moteurs de recommandation pour proposer automatiquement des contenus supplémentaires aux utilisateurs en fonction des données de navigation (clickstream). Une recherche montre qu’un utilisateur est assigné à un groupe spécifique, et reçoit des recommandations basées sur le comportement de ce groupe. Cependant, en raison des problèmes de mise à l’échelle, cette approche n’est pas toujours optimale pour les grands jeux de données.
  
  
• Finance : le k-NN est également utilisé dans divers cas d’utilisation en finance et en économie. Par exemple, une publication montre comment k-NN appliqué aux données de crédit peut aider les banques à évaluer les risques associés à un prêt. Il est également utilisé pour déterminer la solvabilité des demandeurs de prêt. Un autre article souligne son utilisation pour les prévisions boursières, les taux de change, les opérations à terme et les analyses de blanchiment d’argent.
  
  
• Santé : le k-NN a des applications dans le domaine de la santé, notamment pour prédire les risques d’infarctus du myocarde ou de cancer de la prostate, en calculant les expressions de gènes les plus probables.
  
  
• Reconnaissance de formes : le k-NN est également utilisé dans la reconnaissance de formes (ou de motifs), notamment pour la classification de chiffres et de textes. Il est particulièrement utile pour identifier des chiffres manuscrits sur des formulaires ou des enveloppes postales.

Comme tout algorithme de machine learning, k-NN présente des avantages et des inconvénients. En fonction du projet et de l'application, il peut être ou non le bon choix.

• Facile à mettre en œuvre : en raison de sa simplicité et de sa précision, le k-NN est l’un des premiers classificateurs appris par les débutants en science des données.
  
  
• S’adapte facilement : au fur et à mesure que de nouveaux échantillons d’entraînement sont ajoutés, l’algorithme s’ajuste pour inclure ces nouvelles données, car toutes les données d’entraînement sont conservées en mémoire.
  
  
• Peu d’hyperparamètres : k-NN ne nécessite qu’une valeur pour k et une mesure de distance, ce qui le rend relativement simple par rapport à d’autres algorithmes de machine learning.

• N’est pas très évolutif : k-NN étant un algorithme paresseux, il consomme davantage de mémoire et d’espace de stockage par rapport à d’autres classificateurs, ce qui peut s’avérer coûteux en temps et en argent. Plus de mémoire et de stockage entraînent des coûts supplémentaires pour l’entreprise, et le traitement de volumes de données plus importants peut prendre plus de temps. Bien que différentes structures de données, telles que Ball-Tree, aient été développées pour atténuer les inefficacités de calcul, un autre classificateur peut être plus adapté en fonction du problème à résoudre.
  
  
• La malédiction de la dimensionnalité : l’algorithme k-NN a tendance à être victime de la malédiction de la dimensionnalité, ce qui signifie qu’il fonctionne mal avec des données d’entrée comportant de nombreuses dimensions. Ce phénomène est parfois appelé « phénomène de pic », où, après avoir atteint un nombre optimal de caractéristiques, l’ajout de nouvelles caractéristiques augmente les erreurs de classification, en particulier avec des échantillons de petite taille.
  
  
• Tendance au sur-ajustement : en raison de cette malédiction de la dimensionnalité, le k-NN est également plus enclin au surajustement. Bien que des techniques de réduction de la dimensionnalité et de sélection des caractéristiques puissent être employées pour prévenir ce problème, la valeur de k a également un impact significatif sur le comportement du modèle. Des valeurs faibles de k peuvent entraîner un surajustement, tandis que des valeurs plus élevées ont tendance à « lisser » les prédictions en moyenne, mais si k est trop élevé, le modèle risque de sous-ajuster les données.