L’exercice pour aujourd’hui préparait la suite, on commence par le corriger.
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).
Stop ! Arrêtez le jargon !
Ok, vous savez ce qu’est la reconnaissance faciale sur un téléphone ? Un « Captcha » ? Ou vous avez entendu parler d’une voiture qui détecterait toute seule les passages pour piétons ?
Bienvenue dans le monde du « machine learning » ou « apprentissage automatique ».
En gros, on va donner une belle quantité de données à une machine, en disant « ça c’est tel label » ou « ceci tel autre label »pour qu’elle décide si une nouvelle donnée est d’un certain « label » ou pas.
Ah ok. Et comment on va s’y prendre ?
Comme dans le TP pour aujourd’hui. Et après, on découvre un nouvel algorithme … au programme … qu’on programme !
Dans le vif du sujet : nos données
Le TP que je propose est une version simplifiée d’un TP proposé par de nombreuses sources, officielles ou pas.
C’est une histoire de classification de fleurs, des iris, avec des labels. Ne vous étonnez pas d’en voir partout.
On a déjà travaillé avec des fichiers csv. Celui du jour est là.
On va utiliser le même code que pour le « mignon » pour représenter graphiquement nos données.
Exemple 1 :
En gros, pour bien poser la problématique : le nouvel élément représenté en noir ci-dessous, avec le label « nouveau » mérite-t-il
- le label « setosa »,
- le label « virginica »,
- le label « versicolor » ?
Sans hésitation, le point noir étant dans un nuage de points rouges, nous tranchons : le label « virginica ».
Exemple 2 :
Et là ?
Oh, et bien, le point noir étant « très proche » du nuage de points verts, nous tranchons : le label « setosa ».
Comment ça « dans un nuage » ou « très proche » ?
Pour nous, c’est instantané et très visuel avec une telle représentation graphique, mais comment un ordinateur peut-il être programmé pour ça ?
D’autant plus que même pour nous, ce n’est pas toujours évident 😦
Exemple 3 :
Programmons !
Je vous mets à nouveau à disposition un fichier csv, téléchargeable ici (bouton droit, enregistrer sous, iris_3col.csv). A l’aide de ce fichier, réaliser les graphiques ci-dessus :
Il faut placer le nouveau avec :
# nouveau # x_new, y_new = 6, 2 # cas 1 simplissime # x_new, y_new = 2, 0.5 # cas 2 facile x_new, y_new = 2.5, 0.75 # cas 3 problématique plt.scatter([x_new], [y_new], color = 'black', label = 'nouveau')
Correction à la fin du billet en cliquant sur « lire la suite ».
Comment décider du label du « nouveau » ?
Ok, il faut 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 ».
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 == 1on dirait que le nouveau devrait avoir le label versicolor car on a 1 voisin bleu et 0 voisin vert,k == 2on ne saurait dire quel label devrait avoir le nouveau car on a 1 voisin bleu et 1 voisin vert,k == 3on dirait que le nouveau devrait avoir le label setosa car on a 1 voisin bleu et 0 voisin vert,- etc.
Programmons !
Voici le principe de l’algorithme des 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).
Pendant le cours, on a écrit :from math import sqrt def distance(x1, y1, x2, y2): sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2) - On calcule les distances entre le
nouveauet chaque donnée de notre fichier csv à l’aide de la fonction programmée - On retient les
kdonnées du jeu de données les plus proches denouveau.
Pendant le cours, on a proposé :- de trier la liste en prenant cette distance comme critère, par ordre croissant,
- de garder les
kpremier éléments de cette liste.
- On attribue à
nouveaula classe qui est la plus fréquente parmi leskdonnées les plus proches.
Allons-y : à vous ! Je ne proposerai pas de correction ici mais accompagnerai toutes celles et tous ceux qui voudront aller au bout de ce travail, un peu comme un « devoir maison » pendant ces congés à venir… Mercredi, on reprend avec des pages web 😀
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) k_plus_proches_voisins(x_new, y_new, 5) k_plus_proches_voisins(x_new, y_new, 42)
donnent :
Algorithme des 3 plus proches voisins. Les 3 plus proches voisins sont de label versicolor à la distance 0.6103277807866851 setosa à la distance 0.6946221994724903 setosa à la distance 0.8139410298049854 Le label le plus représenté est setosa Il a atteint le maximum, 2 occurences, en premier Notre choix est donc le label setosa Algorithme des 5 plus proches voisins. Les 5 plus proches voisins sont de label versicolor à la distance 0.6103277807866851 setosa à la distance 0.6946221994724903 setosa à la distance 0.8139410298049854 versicolor à la distance 0.8381527307120104 versicolor à la distance 0.8381527307120104 Le label le plus représenté est versicolor Il a atteint le maximum, 3 occurences, en premier Notre choix est donc le label versicolor Algorithme des 42 plus proches voisins. Les 42 plus proches voisins sont de label versicolor à la distance 0.6103277807866851 setosa à la distance 0.6946221994724903 setosa à la distance 0.8139410298049854 versicolor à la distance 0.8381527307120104 versicolor à la distance 0.8381527307120104 setosa à la distance 0.8381527307120106 setosa à la distance 0.873212459828649 ... setosa à la distance 1.2298373876248845 setosa à la distance 1.2298373876248845 Le label le plus représenté est setosa Il a atteint le maximum, 36 occurences, en premier Notre choix est donc le label setosa >>>
Pendant le cours, on a écrit, comme corrigé de la première partie graphique avec matplotlib :
def lecture(nom_du_fichier) :
# initialisation : liste vide
liste = []
# ouverture du fichier en lecture -> 'r'
with open(nom_du_fichier , 'r') as fichier:
# on récupère le contenu
texte = fichier.read()
# on le separe en lignes
lignes = texte.split(sep = '\n')
# on parcourt la liste des lignes sauf la première
for phrase in lignes[1:]:
# on découpe la phrase en trois morceaux dans une liste
# attention dans ce csv le séparateur
# est un virgule , et pas un ;
liste_de_trois = phrase.split(sep = ',')
if len(liste_de_trois) == 3:
# un nouveau dico vide appelé new
new = {}
new['espece'] = liste_de_trois[2]
# attention : à convertir en flottants
# le premier élément de la liste
new['abscisse'] = float(liste_de_trois[0])
# le deuxième élément de la liste
new['ordonnee'] = float(liste_de_trois[1])
# on rajoute new à la liste
liste.append(new) # ou liste += [new]
# on ferme le fichier ouvert
fichier.close()
# on renvoie la liste remplie
return liste
liste = lecture("iris_3col.csv")
# print(liste)
import matplotlib.pyplot as plt
tuning = [('setosa', 'g'),
('versicolor', 'b'),
('virginica','r')]
for espece, couleur in tuning:
# données
x=[]
y=[]
for f in liste :
if f['espece'] == espece:
x.append(f['abscisse'])
y.append(f['ordonnee'])
plt.scatter(x, y, color = couleur, label = espece, marker = 'o')
# nouveau
# x_new, y_new = 6, 2 # cas 1 simplissime
# x_new, y_new = 2, 0.5 # cas 2 facile
x_new, y_new = 2.5, 0.75 # cas 3 problématique
plt.scatter([x_new], [y_new], color = 'black', label = 'nouveau')
# graphique
plt.legend()
plt.show()
Si ça vous intéresse, on a exactement ce sujet dans nos TP python d’Intelligence Artificielle pour classer les iris en L3 x)
Quand je disais que tout le monde faisait pareil 😉
Bien le bonjour !