Aller au contenu

Chapitre 4.7 - Algorithme des KNN⚓︎

image

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.

banquise

Lancer l'animation sur la banquise. L'animal inconnu est-il un ours ou un phoque ?

La vie sur la banquise

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"

choix pokemon

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ée cible.
  • 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 \((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

Python
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 : 25
  • cible_2 : points de vie : 75 et valeur d'attaque : 80
  • cible_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 : Fichier pokemons.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 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.

Par exemple

Python Console Session
>>> 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

Python Console Session
>>> 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

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

ENCRYPTION_TOKEN

Solution

🐍 Proposition de correction
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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

ENCRYPTION_TOKEN

Solution
Python
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