k plus proches voisins
I. Découverte⚓︎
Mon info
- Les algorithmes des k plus proches voisins est abrégé kppv en français. En anglais, k nearest neighbors souvent abrégé en knn.
- L’algorithme des k plus proches voisins appartient à la famille des algorithmes d’apprentissage automatique (machine learning) qui constituent le poumon de l'intelligence artificielle actuellement.
- Pour simplifier, l'apprentissage automatique part souvent de données (data) et essaye de dire quelque chose des données qui n'ont pas encore été vues : il s'agit de généraliser, de prédire.
Lancer l'animation sur la banquise. L'animal inconnu est-il un ours ou un phoque ?
II. Une première approche⚓︎
Des Pokémon
Après avoir téléchargé le fichier, vous pourrez le lire à partir de Basthon
🌐 TD à télécharger : Fichier knn_intro.ipynb : "Clic droit", puis "Enregistrer la cible du lien sous"
Mon info
Ce problème, qui demande à prédire à quelle catégorie, ou classe, appartient ce nouvel élément donné, est appelé problème de classification. L'algorithme des k plus proches voisins permet de trouver les k voisins les plus proches (si k = 5 on cherche les 5 voisins les plus proches) de ce nouvel élément dans le but de lui associer une classe plausible (Psy ou Eau, dans cet exemple).
III. Principe de l'algorithme⚓︎
Que fait l'algorithme des k plus proches voisins ?
A partir d'un jeu de données (par exemple, les données sur nos 34 Pokémons) et d'une donnée cible (le nouveau Pokemon à classifier), l'algorithme des k plus proches voisins détermine les k données les plus proches de la cible. (si k = 3 les 3 plus proches voisins de la cible seront pris en compte, si k = 5 les 5, ...)
Les données
- une table données de taille n contenant les données et leurs classes
- une donnée cible : cible
- un nombre k inférieur à n
- une formule permettant de calculer la distance entre deux données
Résultat
un tableau contenant les k plus proches voisins de la donnée cible.
Algorithme
- Créer une table
distances_voisinscontenant les éléments de la table données et leurs distances avec la donnéecible. - Trier les données de la table
distances_voisinsselon la distance croissante avec la donnée cible - Renvoyer les k premiers éléments de cette table triée.
Et notre prédiction alors ?
L'algorithmes des kppv en lui-même n'apporte pas la réponse à notre problème de classification puisqu'il ne fournit que les k plus proches voisins (et leurs classes) de notre donnée cible. Il reste donc une dernière étape pour prédire la classe de notre nouvel élément : pour cela, on choisit la classe majoritaire (la plus présente) dans les k plus proches voisins.
Influence de la valeur de k⚓︎
k impair
On est contents si k est impair car il ne peut pas y avoir d'ex-aequo.
Remarque
La valeur de k est très importante, elle doit être choisie judicieusement car elle a une influence forte sur la prédiction. Regardons le résultat de la prédiction pour différentes valeurs de k sur notre exemple.
k = 1
Si k = 1, cela revient à chercher la donnée la plus proche de notre élément cible.
Ici, on se rend compte que s la classe du plus proche élément est "Eau" (point bleu)
➜ on classerait le nouveau Pokémon comme étant de type "Eau".
k = 3
Si k = 3, on se rend compte que la classe majoritaire dans les 3 plus proches voisins est "Psy" (2 points rouges contre 1 point bleu) donc on classerait le Pokémon inconnu comme étant de type "Psy".
k = 9
La classe majoritaire parmi les 9 plus proches voisin est "Eau" (5 points bleus contre 4 points rouges) donc on classerait le Pokémon inconnu comme étant de type "Eau".
Remarque
Si on choisit k = 34 (le nombre total de données), alors la prédiction serait toujours "Psy" car c'est la classe majoritaire de l'échantillon. Il est donc incorrect de penser que plus la valeur de k augmente meilleure sera la prédiction, c'est plus complexe que cela. Il faudra observer les resultats.
Choix des distances⚓︎
L'algorithme des plus proches voisins repose sur la distance entre deux données. Dans les exemples vus précédemment, c'est la distance "naturelle" qui a été choisie (celle "à vol d'oiseau").
La distance euclidienne
Dans un repère orthonormé, si A et B de coordonnées \((x_{A},y_{A})\) et \((x_{B},y_{B})\), alors la distance entre ces deux points est donnée par la formule :
\(AB=\sqrt{(x_{B}-x_{A})^{2}+(y_{B}-y_{A})^{2}}\)
On parle alors de la distance euclidienne.
IV. 💻 A vous de jouer⚓︎
Dans le TP du II. Nous avons obtenu la figure suivante :
Nous allons mettre en oeuvre l'algorithme knn pour prédire le type des trois Pokémon représentés en vert, qui sont inconnus. Ce sont des "cibles"
Nous avions :
La liste de dictionnaires pokemons
pokemons = [{'Attaque': 105, 'Nom': 'Aligatueur', 'Points de vie': 85, 'Type': 'Eau'},
{'Attaque': 92, 'Nom': 'Bargantua', 'Points de vie': 70, 'Type': 'Eau'},
{'Attaque': 63, 'Nom': 'Carabaffe', 'Points de vie': 59, 'Type': 'Eau'},
... ]
Nous recherchons les types de :
cible_1: points de vie : 65 et valeur d'attaque : 25cible_2: points de vie : 75 et valeur d'attaque : 80cible_3: points de vie : 95 et valeur d'attaque : 125
Mettre en œuvre KNN
-
La liste de dictionnaires
pokemonsest déjà implémentée, mais cachée pour ne pas alourdir l'exercice. -
cibleest un dictionnaire représentant un pokémon dont on cherche à déterminer le type.
Par exemple cible_1 = {'Attaque': 25, 'Points de vie' : 65}
- La fonction
cree_listeprend en paramètre la listepokemonset le dictionnairecible.
Elle renvoie la liste des listes composées du nom des Pokémon, de leur distance à la cible, et de leur type.
Par exemple
>>> cree_liste(pokemons, cible_1)
[['Aligatueur', 'Eau', 82.46211251235322],
['Bargantua', 'Eau', 67.1863081289633],
... ]
- La fonction
cree_liste_trieeprend en paramètre la listepokemonset le dictionnairecible.
Elle renvoie la liste des listes composées du nom des Pokémon, de leur type et de leur distance à la cible triée par ordre croissant des distances.
Par exemple
>>> cree_liste_triee(pokemons, cible_1)
[['Spoink', 'Psy', 5.0],
['Munna', 'Psy', 11.0],
...]
- La fonction
knnprend en paramètre la listepokemonset le dictionnairecible. Elle renvoie la liste des k premiers éléments de la liste créée par la fonctioncree_liste_triee
👉 on peut utiliser les syntaxes de la fonction sorted de Python vues dans le chapitre des algorithmes gloutons.
Compléter le script ci-dessous
Solution
from math import sqrt
def distance(pokemon, cible):
return sqrt((cible['Points de vie']-pokemon['Points de vie'])**2 + (cible['Attaque']-pokemon['Attaque'])**2)
def cree_liste(pokemons, cible):
return [[pokemon['Nom'], pokemon['Type'], distance(pokemon, cible)] for pokemon in pokemons]
def get_distance(donnee):
return donnee[2]
def cree_liste_triee(pokemons, cible):
distances_cibles = cree_liste(pokemons, cible)
distances_cibles_triee = sorted(distances_cibles, key=get_distance)
return distances_cibles_triee
def knn(pokemons, cible, k):
voisins_tries = cree_liste_triee(pokemons, cible)
resultat = [voisins_tries[i] for i in range(k)]
return resultat