Introduction à l'algorithme KNN

Introduction à KNN

• L'algorithme KNN est une méthode d'apprentissage automatique supervisée, simple et non paramétrique.
• Il est utilisé pour résoudre les problèmes de classification en prédisant la classe d'une nouvelle donnée.
• La prédiction est basée sur la classe majoritaire des K plus proches voisins dans les données d'entraînement.
• Des entreprises comme Amazon, Netflix et Spotify utilisent l'algorithme KNN pour prédire les intérêts des utilisateurs en comparant leurs données à celles d'autres clients.

Principe de l'algorithme KNN

• L'algorithme KNN est qualifié de "paresseux" car il n'apprend rien pendant la phase d'entraînement.
• L'ensemble de données d'entraînement doit contenir une ou plusieurs caractéristiques et une étiquette (label) pour chaque donnée.
• Pour prédire la classe d'une nouvelle donnée d'entrée N, l'algorithme recherche ses K voisins les plus proches en utilisant la distance euclidienne ou d'autres mesures de distance.
• La classe de la nouvelle donnée est déterminée par la classe majoritaire de ces voisins.

Exemple Illustratif du KNN

• Considérons un ensemble de n données réparties en deux catégories : A et B (étiquettes).
• Les données ont deux caractéristiques : Xi1 et Xi2 (features).
• Une nouvelle donnée N a deux caractéristiques, N1 et N2, mais sa catégorie est inconnue.
• L'objectif de l'algorithme KNN est de déterminer la catégorie de N (A ou B).
• Les étapes à suivre sont :
  • Fixer le nombre de voisins, par exemple K=3 ou K=5.
  • Calculer les distances di entre N et chaque point classifié Xi, en utilisant la distance euclidienne usuelle : di = √(Xi1 - N1)² + (Xi2 - N2)². N1 et N2 sont les caractéristiques de N, Xi1 et Xi2 sont les caractéristiques de Xi, et di est la distance entre Xi et N.
  • Sélectionner les K distances di les plus petites.
  • Attribuer à N la classe la plus fréquente parmi les K données retenues.

Choix de l'hyper-paramètre K

• Le choix de la valeur de K est important :
  • Une valeur paire peut produire des égalités (ex-aequos).
  • Une valeur trop faible rend le résultat sensible au bruit (bruit statistique : faibles variations de mesure ou de qualité).
  • Une valeur trop grande risque de mal classer les données.
• Pour choisir la valeur de K :
  • Faire varier K.
  • Calculer différentes métriques d'évaluation (matrice de confusion, taux de prédictions correctes/précision/exactitude, F-score) pour chaque valeur de K sur un ensemble de données test.
  • Choisir la valeur de K qui donne les meilleures performances.

Choix d'une distance et prétraitement des données

• Il existe de nombreuses manières de calculer la distance entre des objets.
• La distance euclidienne est l'une d'entre elles, mais on peut utiliser aussi la distance de Hamming (pour les textes) ou de Manhattan.
• La distance de Manhattan est définie par d(A, B) = |XB – XA| + |YB – YA|.
• Le type de données peut influencer le choix de la distance utilisée.
• Les caractéristiques associées aux données peuvent ne pas être du même ordre de grandeur, ce qui peut biaiser le calcul de distance.
• Pour pallier ce problème, on normalise les données en divisant toutes les données d'une même catégorie par leur valeur maximale afin de les ramener entre 0 et 1.

Implémentation pratique avec Python de KNN

• Utilisation du jeu de données iris de Fisher (fichier CSV contenant des données sur 3 espèces d'iris : iris setosa, iris virginica et iris versicolor).
• Ce jeu de données contient 150 entrées, chacune avec : 
  • La longueur des sépales (en cm).
  • La largeur des sépales (en cm).
  • La longueur des pétales (en cm).
  • La largeur des pétales (en cm).
  • L’espèce d’iris .

Identification de l’espèce d’une nouvelle donnée avec KNN

• Si on trouve un iris et qu'on souhaite déterminer son espèce, on peut utiliser l'algorithme KNN.
• Il faut mesurer la longueur et la largeur des pétales de cette iris, et placer le point correspondant dans un graphique.

Algorithme KNN avec Python

• Librairies à importer :
  • pandas
  • matplotlib.pyplot
  • sklearn.neighbors.KNeighborsClassifier

Importation du jeu de données Iris sous Python

• Importer le jeu de données Iris à partir du fichier "iris.csv" avec pandas.
• Vérifier s'il y a des valeurs nulles dans le jeu de données.

Visualisation du jeu de données:

• Visualiser les données en utilisant un scatterplot (nuage de points) avec matplotlib.pyplot.
• Utiliser différentes couleurs pour chaque espèce d'iris (setosa, virginica, versicolor).

Caractéristiques de la nouvelle Iris à classer :

• Définir les caractéristiques (longueur et largeur des pétales) de la nouvelle iris à classer.
• Entraîner le modèle KNN en spécifiant le nombre de voisins (k=3).
• Prédire l'espèce de la nouvelle iris en utilisant le modèle entraîné.
• Afficher le résultat de la prédiction.

Évaluation des performances de l'algorithme KNN

• Évaluer les performances de l'algorithme KNN avec le jeu de données iris de Fisher.
• Sélectionner la valeur d'hyper-paramètre K qui maximise les performances.
• Importer le jeu de données "Iris.csv".
• Créer deux dataframes :
  • X (Features) contenant uniquement les deux colonnes:"petal_length"et "petal_width".
  • Lab (Labels) contenant uniquement la deux colonne : "species".
• Diviser les données en jeu d’entraînement et jeu de test de taille égale.
• Visualiser les classes du jeu d’entraînement en fonction des Features
• Fixer la valeur de K=3.
• Entraîner un modèle de KNN avec le jeu d’entraînement.
• Classifier les données du jeu de test en prédisant les sorties Lab (Labels) des données X de test.
• Calculer et afficher la Matrice de confusion.
• Calculer et afficher le taux de prédictions correctes (Précision ou Accuracy)
• Faire varier K de 1 à 20 :
  • Pour chaque valeur de K, relever le taux de prédictions correctes (Précision ou Accuracy).
  • Tracer la courbe de ce taux en fonction de K.
  • En déduire la valeur de K optimum.