L'algorithme des k plus proches voisins appartient à la famille des algorithmes d'apprentissage automatique (machine learning). C'est un algorithme simple a appréhender, il permet apprentissage supervisé qui permet de classer de nouvelles données. Les GAFAM utilisent également les données concernant les utilisateurs afin de “nourrir” des algorithmes de machine learning qui permettrons à des sociétés d'en savoir toujours plus sur nous et ainsi de mieux cerner nos “besoins” en termes de consommation. Ce type d'algorithme sont par exemple utilisé pour classer différentes espèces d'arbres par exemple.

Voici le principe de l'algorithme de k plus proches voisins:

1. On calcule les distances entre la donnée u et chaque donnée appartenant au graphique.
2. On retient les k données du jeu de données les plus proches de u.
3. On attribue à u la classe qui est la plus fréquente parmi les k données les plus proches.

Comment savoir à quelle espèce appartient une pétale ?

Par exemple pour un jeu de donnée s'appelant “iris de Fisher” qui est composé de 50 entrées et pour chaque entrée nous avons:

1. La longueur des pétales (en cm)
2. La largeur des pétales (en cm)
3. L'espèce d'Iris

Il est possible de télécharger ces données au format csv :

Nous utiliserons 3 bibliothèques Python:

1. Pandas qui va nous permettre d'importer les données issues du fichier csv
2. Matplotlib qui va nous permettre de visualiser les données
3. Scikit-learn qui propose une implémentation de l'algorithme des k plus proches voisins

Ces bibliothèques sont facilement installables notamment en utilisant la distribution Anaconda.

Une fois que le fichier csv est modifié, il est possible d'écrire un programme permettant de visualiser les données sous la forme de graphique:

import pandas
import matplotlib.pyplot as plt
iris=pandas.read_csv("iris.csv")
x=iris.loc[:,"petal_length"]
y=iris.loc[:,"petal_width"]
lab=iris.loc[:,"species"]
plt.axis('equal')
plt.scatter(x[lab == 0], y[lab == 0], color='g', label='setosa')
plt.scatter(x[lab == 1], y[lab == 1], color='r', label='versicolor')
plt.scatter(x[lab == 2], y[lab == 2], color='b', label='virginica')
plt.legend()
plt.show()

FIGURE 1 - Représentation graphique des données

Le graphique ci-dessus (FIGURE 1) montre que les 3 classes (Iris stetosa, Iris virginica, Iris versicolor) sont relativement bien séparées. On peut ajouter une données non labellisée n'appartenant pas à l'ensemble d'origine (FIGURE 2):

FIGURE 2 - Ajout d'une donnée non labellisée

Dans l'exemple ci-dessus (FIGURE 2), nous n'aurons aucune difficultés à déterminer l'espèce d'Iris qui a été ajouté au jeu de données. Dans certains cas, il est un peu plus difficile de se prononcer “au premier coup d'oeil” (FIGURE 3):

FIGURE 3 - Cas plus difficile

A partir de l'exemple ci-dessus (FIGURE 3), il faut utiliser une méthode pour traiter ce genre de cas litigieux. Nous allons pour ce faire, utiliser l'algorithme des k plus proches voisins:

1. On calcule la distance entre nos points et chaque points issu du jeu de données “Iris”
2. On sélectionne uniquement les k distances les plus petites
3. Parmi les k plus proches voisins, on détermine quelle est l'espèce majoritaire?
4. On associe à notre “Iris mystère” cette espèce “majoritaire parmi les k plus proches voisins”

Dans l'exemple évoqué ci-dessus, nous obtenons graphiquement:

FIGURE 4 - Ici les 3 plus proches voisins

Un Iris ayant une largeur de pétale égale à 0.75 cm et une longueur de pétale égale à 2.5 cm a une “forte” probabilité d'appartenir à l'espèce setosa.

La bibliothèque Python scikit-learn propose un grand nombre d'algorithmes lié à l'apprentissage automatique. Parmi tout ces algorithmes, scikit-learn propose l'algorithme des k plus proches voisins. Voici un programme Python permettant de résoudre le problème évoqué ci-dessus:

import pandas
import matplotlib.pyplot as plt
from sklearn.neighbors import KNeighborsClassifier
 
#traitement CSV
iris=pandas.read_csv("iris.csv")
x=iris.loc[:,"petal_length"]
y=iris.loc[:,"petal_width"]
lab=iris.loc[:,"species"]
#fin traitement CSV
 
#valeurs
longueur=2.5
largeur=0.75
k=3
#fin valeurs
 
#graphique
plt.scatter(x[lab == 0], y[lab == 0], color='g', label='setosa')
plt.scatter(x[lab == 1], y[lab == 1], color='r', label='virginica')
plt.scatter(x[lab == 2], y[lab == 2], color='b', label='versicolor')
plt.scatter(longueur, largeur, color='k')
plt.legend()
#fin graphique
 
#algo knn
d=list(zip(x,y))
model = KNeighborsClassifier(n_neighbors=k)
model.fit(d,lab)
prediction= model.predict([[longueur,largeur]])
#fin algo knn
 
#Affichage résultats
txt="Résultat : "
if prediction[0]==0:
txt=txt+"setosa"
if prediction[0]==1:
txt=txt+"virginica"
if prediction[0]==2:
txt=txt+"versicolor"
plt.text(3,0.5, f"largeur : {largeur} cm longueur : {longueur} cm", fontsize=12)
plt.text(3,0.3, f"k : {k}", fontsize=12)
plt.text(3,0.1, txt, fontsize=12)
#fin affichage résultats
 
plt.show()

les éléments des tableaux x et y ayant le même indice sont regroupés dans un tuple, nous obtenons bien une liste de tuples.

“KNeighborsClassifier” est une méthode issue de la bibliothèque scikit-learn (voir plus haut le “from sklearn.neighbors import KNeighborsClassifier”), cette méthode prend ici en paramètre le nombre de “plus proches voisins” (model = KNeighborsClassifier(n_neighbors=k))

“model.fit(d, lab)” permet d'associer les tuples présents dans la liste “d” avec les labels (0 : “iris setosa”, 1 : “iris versicolor” ou 2 : “iris virginica”). Par exemple le premier tuple de la liste “d”, (1.4, 0.2) est associé au premier label de la liste lab (0), et ainsi de suite…

La ligne “prediction= model.predict(longueur,largeur)” permet d'effectuer une prédiction pour un couple [longueur, largeur] (dans l'exemple ci-dessus “longueur=2.5” et “largeur=0.75”). La variable “prediction” contient alors le label trouvé par l'algorithme knn. Attention, “predection” est une liste Python qui contient un seul élément (le label), il est donc nécessaire d'écrire “predection[0]” afin d'obtenir le label.

Nous obtenons le résultat suivant (FIGURE 5):

FIGURE 5 - A l'aide de scikit-learn

Il est également possible de modifier le programme ci-dessus afin d'étudier les changements induits par la modification du paramètre k en gardant toujours les mêmes valeurs de largeur et de longueur ou encore de changer les valeurs de longueur et de largeur.