Qu’est-ce qu’un KNN (K-Plus Proches Voisins) ?

Qu’est-ce que les K-Plus Proches Voisins (KNN) ?

Les K-Plus Proches Voisins sont une technique et un algorithme d’apprentissage automatique qui peuvent être utilisés à la fois pour les tâches de régression et de classification . Les K-Plus Proches Voisins examinent 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. Les K-Plus Proches Voisins (KNN) sont un algorithme conceptuellement simple mais très puissant, et pour ces raisons, c’est l’un des algorithmes d’apprentissage automatique les plus populaires. Plongeons dans l’algorithme KNN et voyons 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 des K-Plus Proches Voisins (KNN)

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

Imaginons un ensemble de données sur un plan 2D. Représentons un ensemble de points de données sur un graphique, répartis le long du graphique en petits clusters. 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 que fait un modèle KNN 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. Plus la distance entre les points est grande, moins ils sont similaires. Il existe plusieurs façons de calculer la distance entre les points, mais la métrique de distance la plus courante 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 dans l’ensemble 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 l’ensemble de données n’est faite lorsque le modèle est utilisé. Au lieu de cela, le modèle est construit entièrement à partir des données fournies. Deuxièmement, il n’y a pas de division de l’ensemble 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 à un nombre choisi de voisins.
2. Le calcul de la distance entre un exemple fourni/test et les exemples de l’ensemble 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 considérés lorsqu’il rend un jugement sur le groupe auquel l’exemple cible appartient. Dans la deuxième étape, notez que le modèle vérifie la distance entre l’exemple cible et chaque exemple de l’ensemble de données. Les distances sont ensuite ajoutées à une liste et triées. Après cela, la liste triée est vérifiée et les étiquettes des K premiers éléments sont renvoyées. En d’autres termes, si K est défini à 5, le modèle vérifie les étiquettes des 5 points de données les plus proches de l’exemple cible. Lorsqu’il s’agit de rendre une prédiction sur l’exemple cible, cela compte si la tâche est une régression ou une classification tâche. Pour une tâche de régression, la moyenne des K étiquettes les plus proches est utilisée, tandis que le mode des K étiquettes les plus proches 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 à considérer) est choisie, les prédictions qui sont renvoyées peuvent être considérablement fausses. Il est très important que, lors de l’utilisation d’un algorithme KNN, la valeur correcte pour K soit choisie. Vous voulez 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 commet.

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

Des valeurs de K plus faibles signifient que les prédictions rendues par KNN sont moins stables et fiables. Pour avoir une intuition de pourquoi cela est ainsi, 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édit 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 considérer trop de voisins réduira également la précision. À mesure que le rayon que le modèle KNN considère augmente, il finira par considérer 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 les 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 ensembles de données peuvent également causer des prédictions à prendre du temps.

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

Résumé des K-Plus Proches Voisins (KNN)

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