Chapitre 7: Algorithme des KNN

Méthode du K-Nearest-Neighbours (KNN), c-à-d les k-plus-proches-voisins

La méthode KNN est une méthode simple et efficace de classification. La classification est un enjeu majeur de l'Intelligence Artificielle :

• la caméra d'une voiture autonome perçoit un panneau, mais quel est ce panneau ?
• un grain de beauté est pris en photo par un dermatologue, ce grain de beauté est-il cancéreux ?
• ...

La méthode du KNN va trouver quels sont, dans une base de données déjà bien remplie et labellée, les k-objets (les 6 objets si \(k=6\) par exemple) qui se rapprochent le plus de l'objet à classifier. En prenant ensuite la caractéristique la plus fréquente parmi ces 6 objets, on devine alors dans quelle catégorie notre objet doit se classer.

Notre objectif : Nous allons reprendre le jeu de données sur les joueurs du top14 utilisé ici

https://forge.aeif.fr/lyceemed/pnsi/-/blob/main/docs/T4_Algorithmique/Chapitre_7:_Algorithme_KNN/data/03_Pandas_eleves.ipynb

qui utilise le fichier top14.csv

Question : si on croise une personne nous disant qu'elle veut jouer en top14, et qu'elle nous donne son poids et sa taille, peut-on lui prédire à quel poste elle devrait jouer ?

Dans toute idée de classification il y a l'idée de distance. Il faut comprendre la distance comme une mesure de la différence.

Comment mesurer la différence physique entre deux joueurs de rugby ?

🐍 Script Python

import pandas as pd #import du module pandas, abrégé classiquement par "pd"

🐍 Script Python

df = pd.read_csv('top14.csv', encoding = 'utf-8')

Résultat attendu :

Il faut créer une fonction knn() qui prend en argument poids et taille , sont les caractéristiques du nouveau joueur. La fonction doit renvoyer une chaîne de caractère correspondant au poste auquel elle est susceptible de jouer.

Exemple :

🐍 Script Python

def knn(poids, taille):
  df['distance']=(df['Taille']-taille)**2+(df['Poids']-poids)**2
  newdf = df.sort_values(by='distance', ascending=True)
  newdftri = newdf.head(6) #on prend les 6 joueurs les plus proches physiquement
  sol = newdftri['Poste'].describe().top
  return sol

🐍 Script Python

knn(93,188)

🐍 Console Python

'Ailier'

Influence du paramètre \(k\)

Dans le code précédent, on a travaillé avec \(k=6\) et c'est le poste majoritaire parmi les 6 joueurs les plus proches qui a été donné par l'algorithme.
Modifions légèrement la fonction knn() afin d'observer l'influence du paramètre \(k\) sur la prédiction :

🐍 Script Python

def knn(poids, taille, k):
  df['distance']=(df['Taille']-taille)**2+(df['Poids']-poids)**2
  newdf = df.sort_values(by='distance', ascending=True)
  newdftri = newdf.head(k) #on prend les k joueurs les plus proches physiquement
  sol = newdftri['Poste'].describe().top
  return sol

for k in range(1,20):
    print(knn(93,188,k))

🐍 Console Python

Centre
Ailier
Ailier
Ailier
Ailier
Ailier
Ailier
Ailier
Ailier
Ailier
Ailier
Ailier
Ailier
Ailier
Ailier
Ailier
Ailier
Ailier
Ailier

On s'aperçoit que la prédiction est très stable... sauf si \(k=1\) !
Il se trouve qu'un joueur possède exactement ces caractéristiques physiques (Pierre-Louis BARASSI) et qu'il joue Centre :

🐍 Script Python

df['distance']=(df['Taille']-188)**2+(df['Poids']-93)**2
newdf = df.sort_values(by='distance', ascending=True)
newdf.head(10)

	Equipe	Nom	Poste	Date de naissance	Taille	Poids	distance
314	Lyon	Pierre-Louis BARASSI	Centre	22/04/1998	188	93	0
461	Pau	Vincent PINTO	Ailier	10/04/1999	187	93	1
527	Toulon	Stéphane ONAMBÉLÉ	3ème ligne	12/02/1993	188	94	1
202	Castres	Geoffrey PALIS	Arrière	08/07/1991	189	93	1
196	Castres	Armand BATLLE	Ailier	12/04/1987	188	92	1
585	Toulouse	Théo BELAN	Centre	15/11/1992	187	94	2
242	Clermont	Samuel EZEALA	Ailier	11/12/1999	187	94	2
502	Racing92	Simon ZEBO	Ailier	16/03/1990	187	94	2
133	Brive	Esteban ABADIE	3ème ligne	01/12/1997	188	95	4
369	Montpellier	Benjamin FALL	Arrière	03/03/1989	186	93	4

On peut s'apercevoir aussi que jusqu'à \(k=5\), aucun poste n'est majoritaire : la prédiction pourrait aussi bien renvoyer Centre, 3ème ligne, ou Arrière. Ce n'est que grâce à l'ordre alphabétique que la réponse renvoyée est «Ailier». Par contre, dès que \(k \geqslant 5\), le poste d'Ailier est bien majoritaire parmi les \(k\) plus proches voisins.

🐍 Script Python