Qu’est-ce que K-Nearest Neighbors (KNN) ?

Qu’est-ce que K-Nearest Neighbors (KNN) ?

K-Nearest Neighbors est une technique et un algorithme d’apprentissage automatique qui peut être utilisé à la fois pour les tâches de régression et de classification. K-Nearest Neighbors examine les étiquettes d’un nombre choisi de points de données entourant un point de données cible, afin de faire une prédiction sur la classe à laquelle le point de données appartient. K-Nearest Neighbors (KNN) est un algorithme conceptuellement simple mais très puissant, et pour ces raisons, c’est l’un des algorithmes d’apprentissage automatique les plus populaires. Essayons de nous plonger dans l’algorithme KNN et de voir exactement comment il fonctionne. Avoir une bonne compréhension de la façon dont KNN fonctionne nous permettra d’apprécier les meilleures et les pires utilisations de KNN.

Vue d’ensemble de K-Nearest Neighbors (KNN)

Photo: Antti Ajanki AnAj via Wikimedia Commons, CC BY SA 3.0 (https://commons.wikimedia.org/wiki/File:KnnClassification.svg)

Visualisons un jeu de données sur un plan 2D. Imaginez un ensemble de points de données sur un graphique, répartis sur le graphique en petits groupes. KNN examine la distribution des points de données et, en fonction des arguments donnés au modèle, il sépare les points de données en groupes. Ces groupes sont ensuite attribués une étiquette. La principale hypothèse qu’un modèle KNN fait est que les points de données/instances qui existent à proximité les uns des autres sont très similaires, tandis que si un point de données est loin d’un autre groupe, il est dissimilar à ces points de données.

Un modèle KNN calcule la similarité en utilisant la distance entre deux points sur un graphique. La plus grande distance entre les points, moins ils sont similaires. Il existe plusieurs façons de calculer la distance entre les points, mais la métrique de distance la plus couramment utilisée est simplement la distance euclidienne (la distance entre deux points en ligne droite).

KNN est un algorithme d’apprentissage supervisé, ce qui signifie que les exemples du jeu de données doivent avoir des étiquettes attribuées. Il y a deux autres choses importantes à savoir sur KNN. Premièrement, KNN est un algorithme non paramétrique. Cela signifie que aucune hypothèse sur le jeu de données n’est faite lorsque le modèle est utilisé. Plutôt, le modèle est construit entièrement à partir des données fournies. Deuxièmement, il n’y a pas de division du jeu de données en ensembles d’entraînement et de test lors de l’utilisation de KNN. KNN ne fait aucune généralisation entre un ensemble d’entraînement et un ensemble de test, donc toutes les données d’entraînement sont également utilisées lorsque le modèle est invité à faire des prédictions.

Comment fonctionne un algorithme KNN

Un algorithme KNN passe par trois phases principales lorsqu’il est exécuté:

1. La définition de K sur le nombre de voisins choisi.
2. Le calcul de la distance entre un exemple/test fourni et les exemples du jeu de données.
3. Le tri des distances calculées.
4. L’obtention des étiquettes des K premières entrées.
5. La restitution d’une prédiction sur l’exemple de test.

Dans la première étape, K est choisi par l’utilisateur et il indique à l’algorithme combien de voisins (combien de points de données entourants) doivent être pris en compte lors de la prise d’une décision sur le groupe auquel le point de données cible appartient. Dans la deuxième étape, notez que le modèle vérifie la distance entre l’exemple cible et chaque exemple du jeu de données. Les distances sont ensuite ajoutées à une liste et triées. Ensuite, la liste triée est vérifiée et les étiquettes des K premiers éléments sont restituées. En d’autres termes, si K est défini sur 5, le modèle vérifie les étiquettes des 5 points de données les plus proches du point de données cible. Lors de la prise d’une décision sur le point de données cible, cela compte si la tâche est une régression ou une classification. Pour une tâche de régression, la moyenne des K premières étiquettes est utilisée, tandis que le mode des K premières étiquettes est utilisé dans le cas d’une classification.

Les opérations mathématiques exactes utilisées pour exécuter KNN diffèrent en fonction de la métrique de distance choisie. Si vous souhaitez en savoir plus sur la façon dont les métriques sont calculées, vous pouvez lire sur certaines des métriques de distance les plus courantes, telles que Euclidienne, Manhattan et Minkowski.

Pourquoi la valeur de K compte

La principale limitation lors de l’utilisation de KNN est que si une valeur incorrecte de K (le mauvais nombre de voisins à prendre en compte) est choisie, les prédictions qui sont restituées peuvent être très éloignées. Il est très important que, lors de l’utilisation d’un algorithme KNN, la valeur correcte pour K soit choisie. Vous souhaitez choisir une valeur pour K qui maximise la capacité du modèle à faire des prédictions sur des données non vues tout en réduisant le nombre d’erreurs qu’il fait.

Photo: Agor153 via Wikimedia Commons, CC BY SA 3.0 (https://en.wikipedia.org/wiki/File:Map1NN.png)

Les valeurs plus faibles de K signifient que les prédictions restituées par KNN sont moins stables et fiables. Pour avoir une idée de pourquoi c’est le cas, considérons un cas où nous avons 7 voisins autour d’un point de données cible. Supposons que le modèle KNN fonctionne avec une valeur K de 2 (nous lui demandons de regarder les deux voisins les plus proches pour faire une prédiction). Si la grande majorité des voisins (cinq sur sept) appartiennent à la classe Bleue, mais que les deux voisins les plus proches se trouvent être Rouges, le modèle prédira que l’exemple de requête est Rouge. Malgré la prédiction du modèle, dans un tel scénario, Bleu serait une meilleure supposition.

Si c’est le cas, pourquoi ne pas simplement choisir la valeur K la plus élevée possible ? C’est parce que dire au modèle de prendre en compte trop de voisins réduira également la précision. Au fur et à mesure que le rayon que le modèle KNN considère augmente, il finira par prendre en compte des points de données qui sont plus proches d’autres groupes que du point de données cible et la mauvaise classification commencera à se produire. Par exemple, même si le point qui a été initialement choisi se trouvait dans l’une des régions rouges ci-dessus, si K était défini trop haut, le modèle atteindrait d’autres régions pour considérer des points. Lors de l’utilisation d’un modèle KNN, différentes valeurs de K sont essayées pour voir quelle valeur donne au modèle les meilleures performances.

Avantages et inconvénients de KNN

Examinons quelques-uns des avantages et des inconvénients du modèle KNN.

Avantages:

KNN peut être utilisé à la fois pour les tâches de régression et de classification, contrairement à d’autres algorithmes d’apprentissage supervisé.

KNN est très précis et simple à utiliser. Il est facile à interpréter, à comprendre et à mettre en œuvre.

KNN ne fait aucune hypothèse sur les données, ce qui signifie qu’il peut être utilisé pour une grande variété de problèmes.

Inconvénients:

KNN stocke la plupart ou la totalité des données, ce qui signifie que le modèle nécessite beaucoup de mémoire et qu’il est coûteux en termes de calcul. Les grands jeux de données peuvent également causer des prédictions à prendre du temps.

KNN s’avère très sensible à l’échelle du jeu de données et il peut être facilement déstabilisé par des fonctionnalités non pertinentes par rapport à d’autres modèles.

Résumé de K-Nearest Neighbors (KNN)

K-Nearest Neighbors est l’un des algorithmes d’apprentissage automatique les plus simples. Malgré sa simplicité, KNN est également un algorithme puissant qui donne une précision assez élevée sur la plupart des problèmes. Lorsque vous utilisez KNN, assurez-vous d’expérimenter avec différentes valeurs de K afin de trouver le nombre qui donne la plus grande précision.