Chapitre 4.7 - Algorithme des KNNโ๏ธ
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_voisins
contenant les รฉlรฉments de la table donnรฉes et leurs distances avec la donnรฉecible
. - Trier les donnรฉes de la table
distances_voisins
selon 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
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
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
pokemons
est dรฉjร implรฉmentรฉe, mais cachรฉe pour ne pas alourdir l'exercice.
Si vous voulez la tรฉlรฉcharger pour travailler sur votre propre รฉditeur python, vous pouvez la tรฉlรฉcharger ici : Fichierpokemons.py
: "Clic droit", puis "Enregistrer la cible du lien sous" -
cible
est 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_liste
prend en paramรจtre la listepokemons
et le dictionnairecible
.
Elle renvoie la liste des listes composรฉes du nom des Pokรฉmon, de leur type, et de leur distance ร la cible.
Par exemple
>>> cree_liste(pokemons, cible_1)
[['Aligatueur', 'Eau', 82.46211251235322],
['Bargantua', 'Eau', 67.1863081289633],
... ]
๐ La fonction cree_liste_triee
prend en paramรจtre la liste pokemons
et le dictionnaire cible
.
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 knn
prend en paramรจtre la liste pokemons
et le dictionnaire cible
.
Elle renvoie la liste des k premiers รฉlรฉments de la liste crรฉรฉe par la fonction cree_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
# Tests
(insensible ร la casse)(Ctrl+I)