Favicon

NSI Vaugelas - Première

Connexion

Sommaire

Algorithme des k plus proches voisins
( knn = k-nearest neighbors )

Nous allons voir dans cette partie une classe d'algorithmes permettant de classer des objets (au sens large) dans différentes catégories.
La décision prise par cet algorithme évolue au cours du temps, en fonction des choix qu'il a déjà effectué. C'est pourquoi il est classé comme un des algorithme les plus simples mettant en œuvre l'intelligence artificielle, et plus précisément, l'apprentissage automatique supervisé ( un domaine du machine learning ).

Domaines de l'IA

L'exemple historique des Iris

En 1936, le biologiste Edgar Anderson cherche à étudier la classification des Iris. Il s'intéresse plus particulièrement à 3 espèces :

Iris setosa
Iris versicolor
Iris virginica

Comme on peut le constater sur les photos ci-dessus, il n'est sûrement pas évident pour un non initié de déterminer l'espèce d'un Iris croisé dans la nature au hasard d'une promenade.

Les données

Edgar Anderson décide donc de mettre au point un test systématique permettant de différencier ces trois espèces.
Pour cela il réalise des mesures sur les pétales et les sépales des Iris; il mesure :

  • La largeur et la longueur des sépales
  • La largeur et la longueur des pétales
pétale et sépale

pour un ensemble d'Iris à la même saison, connaissant l'espèce de chaque fleur.

Pour simplifier le traitement des données nous ne prendrons en compte que les mesures des pétales.

Vous trouverez un extrait de ces données ici.
Dans ce fichier les deux premières colonnes correspondent à la largeur et la longueur du pétale, la troisième colonne contient 0, 1 ou 2 en suivant le code suivant :

Récupérez le fichier de donnée présenté ci-dessus, et visualisez ces données grâce à ce script :

import matplotlib.pyplot as plt import csv iris=[] x0,x1,x2=[],[],[] y0,y1,y2=[],[],[] esp=[] with open("iris.csv",'r',encoding='utf-8') as f: lecteur=csv.reader(f,delimiter=',') for row in lecteur: iris.append(row) for i in range (1,len(iris)): if iris[i][2]=='0': x0.append(float(iris[i][0])) y0.append(float(iris[i][1])) if iris[i][2]=='1': x1.append(float(iris[i][0])) y1.append(float(iris[i][1])) if iris[i][2]=='2': x2.append(float(iris[i][0])) y2.append(float(iris[i][1])) plt.axis('equal') plt.scatter(x0, y0, color='r', label='iris setosa') plt.scatter(x1, y1, color='g', label='iris versicolor') plt.scatter(x2, y2, color='b', label='iris virginica') plt.legend() axes = plt.gca() axes.set_xlabel('longueur des pétales') axes.set_ylabel('largeur des pétales') axes.legend() plt.show()

Ce nuage de point montre qu'il y a une forte corrélation entre longueur et largeur des pétales d'un Iris d'une part, et l'espèce à laquelle il appartient : les mesures des pétales constituent donc un critère de classification des Iris dans une espèce donnée.

Le problème

Ayant les données précédentes à notre disposition, le problème est de déterminer l'espèce d'un Iris inconnu, ne connaissant que la largeur et la longueur de ses pétales.

L'algorithme

Pour résoudre ce problème nous allons utiliser l'algorithme des k plus proches voisins.

Son principe est le suivant :

"plus proches" est à prendre au sens littéral de distance la plus petite dans le plan, entre le point représentant l'iris à classer et les iris du jeu de données.

Cet algorithme met en œuvre l'apprentissage automatique ou "machine learning". En effet Chaque nouvel élément va être associé à une espèce et donc enrichir les connaissances de l'ordinateur, qui pourra ainsi affiner ses choix par la suite.
On commence à voir apparaître une forme d'intelligence artificielle

Pour bien comprendre, illustrons l'algorithme que l'on vient de décrire.
Voici trois iris inconnus ajoutés dans le plan sous la forme d'un point noir :

Iris inconnu 1
Iris inconnu 2
Iris inconnu 3

Pour les inconnus 1 et 2, nous pouvons déterminer "à l’œil" l'espèce de l'iris. Pour l'inconnu 3 cela va être plus compliqué, il va falloir calculer les distances aux iris voisins pour choisir l'espèce de l'inconnu 3.

Mise en œuvre de l'algorithme

Structures de données utilisées

Deux structures de données seront mises en œuvre dans le code :

Structure du code

Le code sera structuré en fonctions indépendantes :

Travail à réaliser

Fonctions déjà écrites

Les deux fonctions recup_donnees et affichage_iris sont déjà données ci-dessous; appelez successivement les deux fonctions, pour mettre en mémoire le tableau iris, et pour afficher le nuage de points.

import matplotlib.pyplot as plt import csv from math import sqrt def affichage_iris(tab:list): ''' ne rien toucher à cette fonction ''' x0,x1,x2=[],[],[] y0,y1,y2=[],[],[] esp=[] for i in range (1,len(tab)): if tab[i][2]==0: x0.append(tab[i][0]) y0.append(tab[i][1]) if tab[i][2]==1: x1.append(tab[i][0]) y1.append(tab[i][1]) if tab[i][2]==2: x2.append(tab[i][0]) y2.append(tab[i][1]) plt.axis('equal') plt.scatter(x0, y0, color='r', label='iris setosa') plt.scatter(x1, y1, color='g', label='iris versicolor') plt.scatter(x2, y2, color='b', label='iris virginica') plt.legend() axes = plt.gca() axes.set_xlabel('longueur des pétales') axes.set_ylabel('largeur des pétales') axes.legend() plt.show() def recup_donnees(nomDeFichier)->list: ''' à partir du nom de fichier, cette fonction récupère les données et les renvoie sous forme de tableau de tableaux ne rien toucher à cette fonction ''' iris=[] with open(nomDeFichier,'r',encoding='utf-8') as f: f.readline() lecteur=csv.reader(f,delimiter=',') for row in lecteur: iris.append(row) iris.pop(0) for i in range (len(iris)): for j in range(2): iris[i][j]=float(iris[i][j]) iris[i][2]=int(iris[i][j]) return iris

Distance entre deux iris

Écrire une fonction distance, qui prend comme paramètres les coordonnées x et y d'un point 1 du plan et celle d'un point 2, et qui renvoie leur distance dans le plan ( au besoin, demandez à un de vos camarades de maths la formule pour faire ce calcul 🙄...)

def distance(x1, y1, x2, y2): """Renvoie la distance entre deux points d'un plan. Entrées : x1, y1 = coordonnées du premier point (float), x2, y2 = coordonnées du deuxième (float) Sortie : la distance entre les deux points (float) """ pass

SOLUTION

Tableau des distances et espèces

Écrire une fonction tableau_distances, qui prend comme paramètres le tableau de données et les mesures des pétales de l'iris à classer, et qui renvoie le tableau des distances.

def tableau_distances(donnees, long, larg): """Crée et renvoie le tableau des distances et espèces. Entrées : donnees = le tableau de données (list), long et larg = les mesures des pétales de l'iris à classer (float) Sortie : le tableau des distances (list de tuple(distance, espèce)). """ pass

SOLUTION

Recherche des k plus proches voisins

Écrire le code d'une fonction k_mini, qui prend comme paramètres le tableau des distances et un entier k, et qui renvoie le tableau des k éléments du tableau les plus proches de l'iris à classer.

Pour cela, on triera le tableau des distances dans l'ordre croissant, et on sélectionnera les k premiers éléments de ce tableau.

def k_mini(distances, k): """Détermine dans le tableau des distances les k éléments les plus proches de l'iris à classer. Entrées : distances = le tableau des distances (list), k = le nombre de voisins les plus proches (int) Sortie : le tableau des k plus proches voisins (list de tuple(distance, espèce)) """ pass

SOLUTION

La fonction principale

Compléter la fonction kppv_iris ci-dessous qui implémente l'algorithme des k plus proches voisins.

Tester ensuite le code avec un iris à classer de longueur et de largeur quelconques ( mais de valeurs réalistes...)

Pour la valeur de k, commencer avec 3, puis 5, puis expérimentez !

def kppv_iris(iris, long, larg, k): """ Recherche des k voisins les plus proches pour déterminer l'espèce de l'iris donc les pétales mesurent long x larg. Une fois l'espèce déterminée, le nouvel iris est ajouté au tableau 'iris' qui est renvoyé modifié en fin de fonction. """ # Calcul des distances à toutes les autres fleurs et stockage dans le tableau de distances distances = tableau_distances(iris, long, larg) # Recherche des k voisins les plus proches voisins = k_mini(distances, k) # Recherche de l'espèce majoritaire dans le tableau des k plus proches voisins # Rappel : 0->setosa ; 1->versicolor ; 2->virginica pass # Ajout de l'iris inconnu au tableau de données iris.append([long, larg, espece]) return iris, espece ##################################################### # Choix des valeurs long = ... larg = ... k = ... # Récupération des données iris = recup_donnees("iris.csv") # Application de l'algorithme des k plus proches voisins iris, espece = kppv_iris(iris, long, larg, k) print(espece) # Affichage des données affichage_iris(iris)

SOLUTION

Machine learning