NSI 1ère

L'algorithme des k plus proches voisins

L'apprentissage automatique est une branche de l'intelligence artificielle basée sur l'exploitation de jeux de données. Il consiste pour la machine à "apprendre" automatiquement, à partir d'un échantillon de cas (jeu d'apprentissage), afin de pouvoir donner des conclusions concernant d'autres cas.
L'algorithme des k plus proches voisins (k-PPV en français, k-NN en anglais pour k Nearest Neighbours) est un algorithme simple d'apprentissage automatique.

Il peut être utilisé pour faire de la classification, c'est à dire ranger des éléments par catégories.

Exemple dans un cas simple

L'exemple ci-dessous montre le cas de deux catégories d'objets (marques vertes ou violettes), qu'on a positionnés sur un axe en fonction de la valeur d'une de leurs propriétés, A.

Un algorithme de classification permet de répondre à la question "En fonction de la valeur sa propriété A, dans quelle catégorie est-il le plus judicieux de classer l'objet représenté par le triangle rouge ?".

L'ensemble des données représentées par les marques vertes et violettes constitue ici le jeu d'apprentissage .

L'algorithme des k plus proches voisins (on écrira k-PPV par la suite...) consiste à attribuer à l'objet la catégorie majoritaire parmi ses k plus proches voisins du jeu d'apprentissage.
Le fichier exemple1.csv, à télécharger et enregistrer localement, contient les données du jeu d'apprentissage de cet exemple.
Utiliser le code ci-dessous pour charger ces données dans une liste de tuples appelée jeu_app, sous la forme [(categorie, valeur de A),...], tout en convertissant les valeurs de A en type float
  1. import csv
  2. jeu_app=[]
  3. fichier=open('exemple1.csv',newline='',encoding='utf-8')
  4. lignes=csv.reader(fichier,delimiter=';')
  5. for ligne in lignes:
  6.     try:
  7.         ligne[1]=float(ligne[1])
  8.         jeu_app.append(tuple(ligne))
  9.     except:
  10.         pass
  11. fichier.close()
La catégorie est indiquée par les mots 'vert' ou 'violet'.
On considère l'objet à classer X, tel que AX=7,5.

Pour appliquer la méthode des k plus proches voisins, il faut commencer par calculer pour chaque élément Ei du jeu d'apprentissage la distance |Ai - AX| entre cet élément Ei et l'objet X à classer, en conservant chacun de ces résultats en mémoire, associés à la catégorie de l'élément concerné.

Il faut ensuite trouver les k éléments pour lesquels cette distance est la plus petite.

Enfin, il faut déterminer quelle est la catégorie majoritaire parmi ces k éléments.

Vous en savez en principe assez pour faire tout cela, à vous de jouer !

Exemple multidimensionnel

Le fichier apprentissage_mobilier_historique.csv contient des données extraites de ce fichier issu du site data.culture.gouv.fr.
Il s'agit des dimensions (hauteur h, longueur l, profondeur p), exprimées en cm, de pièces de mobilier historique, appartenant à l'une des trois catégories table, banc ou tabouret.
Les graphes ci-dessous montrent la répartition des meubles dans un espace tridimensionnel (h,l,p)
Le problème à résoudre est de faire reconnaître automatiquement par un programme la catégorie à laquelle un meuble appartient, à partir de ses dimensions, en utilisant la méthode k-PPV. Les données du fichier apprentissage_mobilier_historique.csv servent de jeu d'apprentissage.
La démarche est exactement la même que dans le premier exemple traité, mais le calcul de la distance est plus complexe dans un espace multidimensionnel. On utiise fréquemmment la distance euclidienne, qui aura ici pour expression, dans l'espace tridimensionnel (h,l,p) :
où ((hX,lX,pX) et (hi,li,pi) sont les coordonnées respectives du meuble "inconnu" X qu'on cherche à classer, et de l'élément Ei du jeu d'apprentissage.
Quelques éléments choisis aux hasard dans le fichier de données initial ont été mis de côté pour fournir des éléments "inconnus" sur lesquels tester le programme.

Leurs coordonnées (h,l,p) sont données ci-dessous :

ainsi que dans ce fichier.