NSI - Numérique et Sciences Informatiques
Méthode des k plus proches voisins
Prérequis au TD
- Il est conseillé d'avoir traité le TD d' Algorithmique - Projet 2 : GPS et distances.
- Python : Notion de distance euclidienne, liste, parcours de listes et surtout le TD sur les dictionnaires (disponible ici ) .
- Fichiers CSV : avoir traité le TD sur la gestion des fichiers CSV sous Python pour le projet d'application.
Disponible ici avec la correction.
Présentation de la méthode des k plus proches voisins
- En intelligence artificielle, la méthode des k plus proches voisins est une méthode d’apprentissage supervisé. En abrégé k-NN ou KNN, de l'anglais k-nearest neighbors.
- Dans une méthode d'apprentisssage supervisé, on a des exemples que l'on sait classer et qui sont déjà classés. L'ordinateur apprend avec les exemples et leur réponse, puis teste.
- Par exemple pour distinguer si l'on a une photo de chat ou de chien, l'ordinateur va analyser des centaines de photos dont il a la réponse, et apprendre.
- Le terme machine learning vient de l’informaticien américain Arthur Samuel en 1959.
Notre problème est assez simple
- On relève sur des objets de différentes classes (chien ou chat ... ) des paramètres (longueur, largeur, couleur, poids, qualité 1, qualité 2 ..) qui vont permettre de les distinguer.
- On sait donc que pour tel objet de telle classe, on a tels paramètres.
- Par exemple la classe chat (taille, poids, couleur)
- et la classe chien (taille, poids, couleur)
- L'objectif est de pouvoir prévoir à quelle classe appartient un nouvel objet uniquement à l'aide de ses paramètres.
Il s'agit clairement d'un apprentissage supervisé.
- L'algorithme des k plus proches voisine - Idée générale
- On considère une population dont on connait la classe et les caractéristiques.
- On introduit un nouvel élément dont on ne connait que les caractèristiques et on cherche à lui attribuer une classe.
- Ayant choisi une distance adaptée, on compte les k voisins les plus proches de l'élément à classer.
On verra que le choix de k est crucial. - On lui attribue alors la classe des voisins majoritaires.
La méthode des k plus proche voisins - (k nearest neighbors)
Algorithme des k plus proche voisins - k nearest neighbors
Soit un ensemble E contenant \(n\) données labellisées.
- Soit une donnée C qui n’appartient pas à E et qui est uniquement caractérisée par des caractéristiques (taille, poids, couleur, caractéristique 1, ...).
- Soit \(d\) une fonction qui renvoie la distance entre la donnée C et une donnée quelconque appartenant à E.
- Soit un entier \(k\) inférieur ou égal à \(n\) : le choix du paramètre \(k\)est crucial.
Voici le principe de l’algorithme de k plus proches voisins :
- On calcule les distances entre la donnée C et chaque donnée appartenant à E à l’aide de la fonction \(d\).
- On retient les \(k\) éléments de E les plus proches de C.
- On attribue à C la classe qui est la plus fréquente parmi les \(k\) données les plus proches (selon la distance choisie).
- Il étant entendu que tout dépend du paramètre \(k\) qui est choisi.
Algorithme des k plus proche voisins - Etude d'un exemple
Description : Iris de Fisher
Nous allons ici appliquer l'algorithme des k plus proches voisins sur un exemple concret.
Ce jeu de données Iris connu aussi sous le nom de Iris de Fisher est un jeu de données multivariées présenté en 1936 par Ronald Fisher dans son papier "The use of multiple measurements in taxonomic problems".
Le jeu de données comprend 50 échantillons de chacune des trois espèces d'iris (Iris setosa, Iris virginica et Iris versicolor).
Quatre caractéristiques ont été mesurées à partir de chaque échantillon : la longueur et la largeur des sépales et des pétales, en centimètres.
Sur la base de la combinaison de ces quatre variables, Fisher a élaboré un modèle d'analyse permettant de distinguer les espèces les unes des autres.
Il est possible de télécharger ces données au format csv : Iris_de_Fisher.csv.
- Voici le TD qui comporte 6 exercices : TD - K plus proches voisins.