TP – Apprentissage et algorithme des plus proches voisins.
Avant de commencer ce TP, vous devez avoir fait la petite introduction à matplotlib
Introduction
L’algorithme des k plus proches voisins appartient à la famille des algorithmes d’apprentissage automatique (machine learning).
L’idée d’apprentissage automatique ne date pas d’hier, puisque le terme de machine learning a été utilisé pour la première fois par l’informaticien américain Arthur Samuel en 1959.
Les algorithmes d’apprentissage automatique ont connu un fort regain d’intérêt
au début des années 2000 notamment grâce à la quantité de données disponibles sur internet.L’algorithme des k plus proches voisins est un algorithme d’apprentissage supervisé, il est nécessaire d’avoir des données labellisées.
À partir d’un ensemble E de données labellisées, il sera possible de classer (déterminer le label) d’une nouvelle donnée (donnée n’appartenant pas à E).
Commencez par télécharger le fichier suivant :
iris.csv
Enregistrez le dans un dossier qui s’appelle TP_knn

iris setosa
iris versicolor

iris virginica
Le fichier téléchargé précédemment contient les données de plusieurs dizaines d’iris. Et pour chaque iris :
- la longueur des pétales
- la largeur des pétales
- l’espèce de l’iris (au lieu d’utiliser les noms des espèces, on utilisera des chiffres : 0 pour « iris setosa », 1 pour « iris virginica » et 2 pour « iris versicolor »)
Jouons un peu avec ce jeu de données.
Nous aurons besoin de pandas, donc pip install pandas
Ici, une petite introduction à pandas : http://www.python-simple.com/python-pandas/panda-intro.php
Affichons une représentation graphique de ces données à l’aide du script suivant :
Le résultat :
Déjà, quel est le problème ?
Et bien un ami trouve un iris, nous indique la longueur et la largeur des pétales. On place ce nouvel iris sur notre graphe.
Sans prendre trop de risque je peux affirmer à mon ami qu’il s’agit vraisemblablement d’un iris versicolor.
Quelque jours plus tard il trouve encore un nouvel iris ! Je l’ajoute :
Là, le point noir étant « proche » du nuage de point bleu, je peux raisonnablement penser qu’il s’agit d’un iris setosa
Dés le lendemain il trouve un nouvel iris. Comme les fois précédentes je place le point :
C’est tout de suite moins évident ! Voilà le problème : Comment décider du label du nouvel iris ?
Il nous faudrait un critère de décision :
- moins subjectif qu’un « dans un nuage » ou un « très proche »,
- algorithmique pour qu’une machine puisse décider.
L’algorithme « k-NN » des k plus proches voisins
« k – NN » car en anglais, il s’appelle « k–nearest neighbors algorithm ».
Article wikipédia sur la recherche des k plus proches voisins : https://fr.wikipedia.org/wiki/Recherche_des_plus_proches_voisins
Les plus proches ?
On voit bien dans le décompte des voisins que le choix du nombre
k
est important ! Ça fait partie des « leviers » de tous les spécialistes du « deep learning ».
Influence de
k
. Pour :
-
k == 1
on dirait que le nouveau devrait avoir le label versicolorcar on a 1 voisin bleu et 0 voisin vert, -
k == 2
on ne saurait dire quel label devrait avoir le nouveau car on a 1 voisin bleu et 1 voisin vert, -
k == 3
on dirait que le nouveau devrait avoir le label setosa car on a 1 voisin bleu et 2voisins vert, - etc.
Passons au code !
Voici le principe de l’algorithme de k plus proches voisins :
- Il nous faut une distance. Écrire une fonction
distance(x1, y1, x2, y2)
qui calcule et renvoie la distance entre deux points de coordonnées(x1, y1)
et(x2, y2)
dans un repère orthonormé (formule de seconde).
Exercice
Codez la fonction distanceSolution
Reamarque : J’utilise numpy pour la racine plutôt que math , c’est pour faciliter le travail avec pandas. (Donc… Pip install numpy)
- On calcule les distances entre le
nouveau
et chaque donnée de notre fichier csv à l’aide de la fonction programmé
Rappelons :
Nous donne :
petal_length petal_width species 0 1.4 0.2 0 1 1.4 0.2 0 2 1.3 0.2 0 3 1.5 0.2 0 4 1.4 0.2 0
On peut accéder à un élément précis du dataframe de la façon suivante :
Pour visualiser sur le dataframe :
petal_length petal_width species 0 1.4 0.2 0 1 1.4 0.2 0 2 1.3 0.2 0 3 1.5 0.2 0 4 1.4 0.2 0
Il suffit d’indiquer l’étiquette d’une ligne et d’une colonne pour accéder à un élément.
Maintenant que vous pouvez accéder aux éléments, vous pouvez calculer chaque distance.
Mais, nous pouvons aussi utiliser la puissance des dataframes de pandas ! On peut facilement ajouter une nouvelle colonne et cette nouvelle colonne peut être exprimée en fonction des deux autres… Par exemple, ajoutons une colonne qui est la somme de la longueur des pétales et de la largeur des pétales :
Notre dataframe devient :
petal_length petal_width species somme 0 1.4 0.2 0 1.6 1 1.4 0.2 0 1.6 2 1.3 0.2 0 1.5 3 1.5 0.2 0 1.7 4 1.4 0.2 0 1.6
N’est-ce pas merveilleux ?
à vous de jouer !
Exercice
Rajouter une colonne 'dis' qui contient la distance entre l'iris et le nouvel irisSolution
petal_length petal_width species dist 0 1.4 0.2 0 1.229837 1 1.4 0.2 0 1.229837 2 1.3 0.2 0 1.320038 3 1.5 0.2 0 1.141271 4 1.4 0.2 0 1.229837
- On retient les
k
données du jeu de données les plus proches denouveau
Pour trier le dataframe :
dataframe.sort_values(by = ‘C’) retourne un dataframe avec les lignes triées de telle sorte que la colonne ‘C’ soit dans l’ordre croissant.
Exercice
trier le dataframe suivant une distance au nouveau croissante.Solution
petal_length petal_width species dist 98 3.0 1.1 1 0.610328 44 1.9 0.4 0 0.694622 24 1.9 0.2 0 0.813941 93 3.3 1.0 1 0.838153 57 3.3 1.0 1 0.838153
- On attribue à
nouveau
la classe qui est la plus fréquente parmi lesk
données les plus proches.
Allons-y : à vous !
Dans l'exercice final de ce TP vous aller coder la fonction k_plus_proches_voisins(x_new, y_new, k)
Cette fonction doit retourner la classe contenant le plus de voisin pour notre nouveau.
Ces trois appels de ma fonction
k_plus_proches_voisins
avec notre couple
x_new, y_new = 2.5, 0.75
k_plus_proches_voisins(x_new, y_new, 3) setosa k_plus_proches_voisins(x_new, y_new, 5) versicolor k_plus_proches_voisins(x_new, y_new, 42) setosa
Exercice
Codez la fonction k_plus_proches_voisins(x_new, y_new, k)Solution
Pour comprendre ce corrigé il faut avoir une certaine habitude à utiliser la bibliothèque pandas.
Je vous laisse admirer la puissance de pandas.
Et sans Pandas, cela donne quoi ?
Voici une version n’utilisant que la bibliothèque standard. (Pas de pip install)