Qu'est-ce qu'un KNN (K-Nearest Neighbours) ?

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

K-Nearest Neighbours est une technique et un algorithme d'apprentissage automatique qui peut être utilisé pour les tâches de régression et de classification. Les voisins les plus proches 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 appartient le point de données. 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. Plongeons en profondeur dans l'algorithme KNN et voyons exactement comment cela fonctionne. Avoir une bonne compréhension du fonctionnement de KNN vous permettra d'apprécier les meilleurs et les pires cas d'utilisation 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)

Visualisons un jeu de données sur un plan 2D. Imaginez un groupe de points de données sur un graphique, répartis le long du 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 reçoivent ensuite une étiquette. L'hypothèse principale d'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 éloigné d'un autre groupe, il est différent de 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 mesure de distance la plus courante est simplement la distance euclidienne (la distance entre deux points sur une ligne droite).

KNN est un algorithme d'apprentissage supervisé, ce qui signifie que les exemples de l'ensemble de données doivent avoir des étiquettes qui leur sont attribuées/leurs classes doivent être connues. Il y a deux autres choses importantes à savoir sur KNN. Premièrement, KNN est un algorithme non paramétrique. Cela signifie qu'aucune hypothèse sur l'ensemble de données n'est faite lorsque le modèle est utilisé. Au contraire, le modèle est entièrement construit à partir des données fournies. Deuxièmement, il n'y a pas de division de l'ensemble de données en ensembles d'apprentissage et de test lors de l'utilisation de KNN. KNN ne fait aucune généralisation entre un ensemble d'entraînement et de test, de sorte que 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 lors de son exécution :

1. Fixer K au nombre de voisins choisi.
2. Calcul de la distance entre un exemple fourni/de test et les exemples de jeux de données.
3. Tri des distances calculées.
4. Obtenir les étiquettes des entrées K supérieures.
5. Renvoie 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 environnants) doivent être pris en compte lors du rendu d'un jugement sur le groupe auquel appartient l'exemple cible. 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 dans une liste et triées. Ensuite, la liste triée est vérifiée et les étiquettes des K éléments supérieurs sont renvoyées. En d'autres termes, si K est défini sur 5, le modèle vérifie les étiquettes des 5 premiers points de données les plus proches du point de données cible. Lors du rendu d'une prédiction sur le point de données cible, il importe que la tâche soit une régression or classification tâche. Pour une tâche de régression, la moyenne des K étiquettes supérieures est utilisée, tandis que le mode des K étiquettes supérieures est utilisé dans le cas de la classification.

Les opérations mathématiques exactes utilisées pour effectuer 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 en savoir plus sur certaines des métriques de distance les plus courantes, telles que Euclidienne, Manhattanet Minkowski.

Pourquoi la valeur de K est importante

La principale limitation lors de l'utilisation de KNN est qu'une valeur incorrecte de K (le mauvais nombre de voisins à prendre en compte) peut être choisie. Si cela se produit, les prédictions renvoyées peuvent être considérablement erronées. Il est très important que, lors de l'utilisation d'un algorithme KNN, la valeur appropriée 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 invisibles 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 plus faibles de K signifient que les prédictions rendues par le KNN sont moins stables et fiables. Pour avoir une intuition de la raison pour laquelle il en 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 sont rouges, le modèle prédira que l'exemple de requête est rouge. Malgré la supposition du modèle, dans un tel scénario, Bleu serait une meilleure supposition.

Si tel est le cas, pourquoi ne pas simplement choisir la valeur K la plus élevée possible ? En effet, dire au modèle de prendre en compte trop de voisins réduira également la précision. Au fur et à mesure que le rayon pris en compte par le modèle KNN augmente, il commencera éventuellement à considérer des points de données plus proches d'autres groupes qu'ils ne le sont du point de données cible et une mauvaise classification commencera à se produire. Par exemple, même si le point initialement choisi se trouvait dans l'une des régions rouges ci-dessus, si K était trop élevé, le modèle atteindrait les autres régions pour prendre en compte les 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 des tâches de régression et de classification, contrairement à certains 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'elles peuvent être utilisées 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 calculs. Les ensembles de données volumineux peuvent également faire en sorte que les prédictions prennent beaucoup de temps.

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

Résumé des K-plus proches voisins (KNN)

K-Nearest Neighbors est l'un des algorithmes d'apprentissage automatique les plus simples. Malgré la simplicité de KNN, dans son concept, c'est aussi 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 différentes valeurs de K afin de trouver le nombre qui offre la plus grande précision.