k plus proches voisins

1 - Présentation de la méthodes

⇩ ⇧ ⤊

• 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
  
  1. On considère une population dont on connait la classe et les caractéristiques.
  2. On introduit un nouvel élément dont on ne connait que les caractèristiques et on cherche à lui attribuer une classe.
  3. 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.
  4. On lui attribue alors la classe des voisins majoritaires.
     

Un exemple

Nous allons travailler sur un ensemble de données.

Elles ont été reconstituées à partir des données tirées de la coupe du monde 2018.

Le fichier complet se trouve ici mais nous n'allons utiliser qu'une version tronquée : celle ne contenant que les joueurs des 4 premières équipes, à savoir la France, la Croatie, la Belgique et l'Angleterre.

Nous voudrions voir s'il est possible d'associer un type de joueur (attaquant, milieu de terrain, défenseur ou gardien) en fonction de sa taille et de son poids.
Pour cela, pas besoin de sortir Python dans premier temps : les tableurs comme celui d'OpenOffice peuvent ouvrir le fichier CSV et il ne reste qu'à créer des graphiques.

Voici le résultat :

Bon... Pas de catégorie caractérisée par un type unique de carrure. Mais il y a bien quelques schémas visibles.

Et c'est maintenant que nous allons devoir sortir l'algorithmique : ce n'est pas intuitif mais il existe un moyen de prédire (ici approximativement, on reste sur de l'humain).

Imaginons que vous ayez un joueur à placer. Ici représenté par le point noir (70 kg, 180 cm):

Alors, on lui donne quel rôle à celui là ?

Ici, c'est facile et cela va vous permettre de comprendre le principe de l'algorithme de k plus proches voisins.

Imaginons qu'on parte avec un algorithme des 9 plus proches voisins.

Voici le résultat graphique :

Si on compte, on obtient donc :

• 5 voisins milieux de terrain
• 2 voisins défenseurs
• 2 voisins attaquants

Nous aurions donc tendance à dire que notre joueur a plutôt un profil de milieu de terrain, non  ?

Voici donc le principe de l'algorithme des k plus proches voisins : on regarde quelles sont les catégories des k enregistrements les plus proches de celui qu'on étudie et on pourra répondre. L'algorithme répond en fournissant la catégorie (ou les catégories en cas d'égalité) la plus représentée.

Attention néanmoins à la qualité de vos données : c'est là l'une des plus grandes difficultés des techniques d'intelligence artificielle : ne pas biaiser le résultat en fournissant des données incorrectes !

La première critique qu'on peut avoir sur notre jeu de données (les joueurs des 4 premières équipes) est qu'il n'y a pas le même nombre de joueurs dans chaque catégorie alors que les catégories ne sont pas clairement marquées par une zone. Du coup, celle qui apparaît le plus souvent à statistiquement un avantage certain.

Nous allons donc remédier à cela en rajoutant des joueurs dans les catégories les moins fournies.

Notre collection de base contient :

• 23 attaquants
• 33 défenseurs
• 12 gardiens
• 24 milieux de terrain

Il faudra donc monter à au moins une trentaine de joueurs par catégorie.

Du coup, j'ai récupéré également certains attaquants, gardiens de but et milieu de terrain dans les équipes suivantes dans le classement.

Ensuite, j'ai créé deux jeux de données de façon aléatoire :

• 75% des joueurs par catégorie pour créer le jeu d'apprentissage ou d’entraînement.
• Les 25% restants vont servir à créer le jeu de tests : nous allons tenter de comparer le poste réel des joueurs de ce jeu avec le poste que l'algorithme donne.

Voici les rendus graphiques de la nouvelle collection d'entraînement :

Le but est d'avoir une collection de données fiables qui donne à chaque enregistrement un descripteur ou attribut précis.

Notre collection est initialement stockée dans un fichier CSV.

A titre d'exemples, voici les trois premières lignes du fichier CSV :

Une vidédo expliquant le problème

2 - 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.