La version Notebook : 3ba1-3567078
15.1.1. Algorithme des k-plus proches voisins#
Cette 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. Pourquoi le machine learning est tant “à la mode” depuis quelques années ? Simplement parce que le nerf de la guerre dans les algorithmes de machine learning est la qualité et la quantité des données (les données qui permettront à la machine d’apprendre à résoudre un problème), or, avec le développement d’internet, il est relativement simple de trouver des données sur n’importe quel sujet (on parle de “big data”). À noter aussi l’importance des stratégies mises en place par les GAFAM (Google, Apple, Facebook, Amazon et Microsoft) afin de récupérer un grand nombre de données concernant leurs clients. Ces données sont très souvent utilisées pour “nourrir” des algorithmes de machine learning (comment, d’après vous, Amazon arrive à proposer à ces clients des “suggestions d’achats” souvent très pertinentes ?)
Nous allons étudier un algorithme d’apprentissage assez simple à appréhender : l’algorithme des “k plus proches voisins” (en anglais “k nearest neighbors” : knn)
Afin de travailler sur un exemple, nous allons utiliser un jeu de données relativement connu dans le monde du machine learning : le jeu de données “iris”.
En 1936, Edgar Anderson a collecté des données sur 3 espèces d’iris : “iris setosa”, “iris virginica” et “iris versicolor”
On peut trouver une collection de 50 de ces iris dans le fichier iris.csv
import requests
r = requests.get('https://pixees.fr/informatiquelycee/n_site/asset/iris.csv')
with open('iris.csv','w') as f:
f.write(r.content.decode('utf-8'))
15.1.1.1. Activités#
15.1.1.1.1. Activité 1#
Lire le fichier précédent sous la forme d’une liste.
import csv
with open('iris.csv','r') as f:
lignes = csv.reader(f)
iris = []
for ligne in lignes:
iris.append(ligne)
iris[0:5]
[['petal_length', 'petal_width', 'species'],
['1.4', '0.2', '0'],
['1.4', '0.2', '0'],
['1.3', '0.2', '0'],
['1.5', '0.2', '0']]
15.1.1.1.2. Activité 2#
Expliquer le code suivant :
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()
Nous obtenons des “nuages” de points, on remarque ces points sont regroupés par espèces d’iris (pour “iris virginica” et “iris versicolor”, les points ont un peu tendance à se mélanger).
Imaginez maintenant qu’au cours d’une promenade vous trouviez un iris, n’étant pas un spécialiste, il ne vous est pas vraiment possible de déterminer l’espèce. En revanche, vous êtes capables de mesurer la longueur et la largeur des pétales de cet iris. Partons du principe qu’un pétale fasse 0,5 cm de large et 2 cm de long. Plaçons cette nouvelle donnée sur notre graphique (il nous suffit d’ajouter la ligne “plt.scatter(2.0, 0.5, color=‘k’)”, le nouveau point va apparaitre en noir (color=‘k’)) :
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.scatter(2.0, 0.5, color='k')
plt.legend()
plt.show()
Je pense que le résultat est sans appel : il y a de fortes chances que votre iris soit de l’espèce “iris setosa”.
Il est possible de rencontrer des cas plus difficiles, par exemple : largeur du pétale = 0,75 cm ; longueur du pétale = 2,5 cm :
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.scatter(2.5, 0.75, color='k')
circle1 = plt.Circle((2.5, 0.75), 0.8, color='k',fill=False)
ax = plt.gca()
ax.add_artist(circle1)
plt.arrow(2.5,0.75,0.37,0.25,ec="k",head_width=0.05, head_length=0.1)
plt.arrow(2.5,0.75,-0.42,-0.29,ec="k",head_width=0.05, head_length=0.1)
plt.legend()
plt.show()
Dans ce genre de cas, il peut être intéressant d’utiliser l’algorithme des “k plus proches voisins”, en quoi consiste cet algorithme :
on calcule la distance entre notre point (largeur du pétale = 0,75 cm ; longueur du pétale = 2,5 cm) et chaque point issu du jeu de données “iris” (à chaque fois c’est un calcul de distance entre 2 points tout ce qu’il y a de plus classique)
on sélectionne uniquement les k distances les plus petites (les k plus proches voisins) parmi les k plus proches voisins, on détermine quelle est l’espèce majoritaire. On associe à notre “iris mystère” cette “espèce majoritaire parmi les k plus proches voisins”
Prenons k = 3
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.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.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+"versicolor"
if prediction[0]==2:
txt=txt+"virginica"
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()
---------------------------------------------------------------------------
ModuleNotFoundError Traceback (most recent call last)
Cell In[6], line 3
1 import pandas
2 import matplotlib.pyplot as plt
----> 3 from sklearn.neighbors import KNeighborsClassifier
5 #traitement CSV
6 iris=pandas.read_csv("iris.csv")
ModuleNotFoundError: No module named 'sklearn'
15.1.1.1.3. Activité 3#
Reprendre le code précédent, en faisant varier \(k\) ou la largeur et la longueur des pétales de l’iris. Analyser et commenter les résultats obtenus.
15.1.1.2. Mise en œuvre de l’algorithme par vos soins#
On va chercher à mettre en œuvre l’algorithme par nos propres soins.
15.1.1.2.1. Activité 4#
Écrire une fonction qui calcule la distance entre deux iris (on utilise le formule classique \(\sqrt{(x - x_c)^2 + (y - y_c)^2}\)).
from math import sqrt
def distance(f1: list,f2: list) -> float:
return sqrt((f1[0] - f2[0])**2 + (f1[1] - f2[1])**2)
15.1.1.2.2. Exercice 5#
Écrire une fonction qui renvoie le plus proche voisin (au sens de la distance précédente)
def plus_proche_voisin(element, liste):
voisin = liste[0]
for voisin_suivant in liste[1:]:
if distance(element,voisin) > distance(element,voisin_suivant):
voisin = voisin_suivant
return voisin
15.1.1.2.3. Activité 6#
Écrire une fonction qui renvoie les \(k\) plus proches voisins.
def k_plus_proches_voisins(k, element, liste):
return liste_voisins