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 (xA,yA) et (xB,yB), alors la distance entre ces deux points est donnรฉe par la formule :

AB=(xBโˆ’xA)2+(yBโˆ’yA)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

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):
...
def get_distance(donnee):
return donnee[2]
def cree_liste_triee(pokemons, cible):
distances_cibles = cree_liste(pokemons, cible)
...
def knn(pokemons, cible, k):
...
cible_1 = {'Attaque': 25, 'Points de vie' : 65}
cible_2 = {'Attaque': 80, 'Points de vie' : 75}
cible_3 = {'Attaque': 125, 'Points de vie' : 95}
knn(pokemons, cible_1, 3)
knn(pokemons, cible_1, 5)
knn(pokemons, cible_2, 3)
knn(pokemons, cible_2, 5)
knn(pokemons, cible_3, 3)
knn(pokemons, cible_3, 5)
ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
###(Dรฉs-)Active le code aprรจs la ligne # Tests (insensible ร  la casse)
(Ctrl+I)
rounded
>>> 
 
x
x
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

.128013/-8eSwkc]N_yuh1a0(f,+T*=6 ;Asot745)dmq:3pn9vib[Pgr2l050K0e0F0q0T0!0D0A0i0!0q0D0D0y010F0T0P010406050D0n0L0L0q0Y0m040f0E0!0n0^0E0Q050b0 1113150}0P04051l1e1o0b1l0}0K0T0S0-0/0;0?0/0Q0X0n0q0X0e0c0P0m0F0o1c0A0o0T0X0o0!1Q0o0F0{050(0U0!0e1x0:0=011P1R1T1R0F1Z1#1X0F0Y1m1L0-180D0P0q0Q0?0Z011%1z010t0*0e0Q0q0L0e1X1|1~231)261#292b0{0a0A0W0Y0E0P0E0D0T1b0Q0A0$1`0Y0Y0e0i2w1e2e0Q1m0b1L2J1?1^1@1Y0K2g1A0T0Q282t1X1u1w0.1(2T2V0Q0E2Z1X0P2C1m2H2J2:0~1}2x2#242)0Y120!1X0q1O2C0t0?030l0l0i2*0e1T2(0E0c0O0c0p0{0A0p1e0q2;2@0|2?2f2_1)2{2}2 310e33013537393b2W3e0c21040A0Z3l3n1~3p2H2S013u0q2~1m300o323436380$3E2)3G0O3i0O3M2G3o0}3Q3s0?3T3V053X3Z3A3#3D2U3F3f0H3i0H3.1f3:3q2^1y3t0E2|3U3w3Y3y3!3C3%403)3f0I3i0I462:3;2@3R3^4g3|3B3$3a4m3d3f0z3i0z4s483=4b3@4d3v3W3x3z4A3 3c3G0G3i0G4J3O4u3r4M3S4O4f4Q4h4S3~4l4V3f0d3i0d4!2I4$4a2$4)4e3_3{4i3}4k4C4;0c0R3i0R4_3P4v3?4~4P3`4R4j4B3(4E3g0r0{0p0r5b4{4w4*505i535k4D3G0p3h045C5s495u4 4y524T4:413g3I0p3L0b3m3/4#5H5e4x4,4z4/555O0p3+5E3-5T3N4`5X4(5Z5h4-5j4U5(435E455-5V5/4L4}5=514.545l5B4p5E4r5~475W612`5v5K655z560p4G5E4I6c4t5:626h5!5L5$673f0p4X5E4Z6q4K5d5;6u5?5#665A6z4?5E4^6E6e6G6t5J6v6j5_4n3g585E5a6R606T6g6V6J6w6L560Z5o046;5G6f4c6,645^5N6Z0Z5D706^6*6`5g6|5y6Y5m0Z3I7b5b1p2.1e2Z2M0K1^2R5e4B2Y1v1m2-0e2/3o5 1m4B7u2f0T0K0?362H5B3w7B7D6/5(222k0e7J6k7L2J5U6_0?0h0Q0{0t2q0L7w0A6s2`7X04121L7$7(1)7W0{0T0L2s0Y0F7.7U3S0{0D0M7_7w0}6d2I5H7I017E2@3G3I5h876x6M3H7M2a7O887K6 1X5-832=3Q8e0l7F3f5*8d7C8l7Q6Z3+0A7N7P793*8o7T747V0{0$0t7{8L3S0t8N0T0D0(0Q0i0e7w7/0?0`040s8#7|7*2s0h0e0L1c8+8R8(0u8Q4%620{0i0T1!8!847z4|248(0J0N828?7A8z891~3G5{8y8G6~5m438E8j9i5%6Z9g5-0A9t7%7|0h0{2C0F0n0Y1d929v8R7*7 81928$018(0s8*9K8,8}8 1#9a941)8(0V9V3R0D5D02030O0R0B0W0E2U0F0,2z0S0T0e9(9*0B9!5e8(0j9|4(0E0{0ca08|048.8:8=9Q8@0{9Zab8{249$0{9_9+9-9/9;1$9?9^9)9+a5950{0j0Jau1)a2040x0xaz0?0L0T0{5S2:0A8q7v8s9c8u8a4o7HaQ8B5m4p9m2b9o6y0c693M9u9FagaA0{0v8`9W8%0{9P8r9G9S90aF9Mada|ai04ak0B0C1/0q0M0nar9`a|9~a|aBa4afa;7}a70E8/8;9Da^a,a=04aebobhb0b2b40(b7b9atbg3R9~aybC5eaBaDa|aHaJbb0{bF6rbC8t8v0c6n9h8A8H4F8ia!bX9j3GbV8p9!bSaS0c6BbW8f564XaZ8kb;5Ob/5~9w8N3ya:4w8T040i2C0e0l1T8W91btbDa?a|8-bka90Q0DbN048_9E9L7*8~a{bG4(969892aN3O86aQbT6Ob:8m5m4?b@a#8gcC9s9u9L9x049z9Bbn3oa+bh9YbsaOa_bjblaacb9}a~cs4}bvas0B0k0E0Lb2ck0jcmaLco0{a8bmckcXcy7|c,9`0w0m0PbA9{c*av04c@c05Y8U8W1~8Zcka@cYbpbic|c$dlcV0{c^cTc`c39Tcadqcc040J9 cwb+cAb-6#cDaW3G58cHb$9p5mdIcLcMb}040t4ddd5;c{cgc}cn7|0E0g7=cS3OcU4wd!c#cic?99bRdG9e6z6=dJbY5nb!b^cE5Bd|b*d^7JbT5CaUcI6l3hdNb_6Ze97S933RcO8OdY62c21G0F0l1udg8Ydyd0ac8)ce8N1c2Vew857|cud@cbb,d`5PeadOa$5Re0eb5(8cdSd.5ecOcQ9Cen2`eB0QeDc~bKaI6?d?dEe68le88x308tdK6z8D8FeO8g5)8J3pe:9d0Q5B9ge@aVd~0p9le|ef5mfaf0cNb~8Pd%9Gc2c40ec6c80Fc61?9@eEejc(ezd93td:chcjfzbqdtd-dvcq9UfEa}dBcvbQeJd_f46za(f7eSegaYfce2fTf0a*dvet8X8Z0D37dxfDc_d(0{0ye#fAc3c5c78VfrdjeAc!fCckfG2IeWdZdwcrc%ctbOeIdzeKfS3gbVfVe}6l4Geef!ggf$dTcZf)dh0ef,fJgu0lftfof@0?aBf?fkdm0Q0U7~4dfr0Kf~fL7*gsevgvf.g2gBbi8/0mbdf=f eqesf|gtckbP48f2aReL6AeNfd5Bb?fZe_3gb{3mf%dUeZd,g4f(g(gRf-90f,gzfvcxeF4vge5BcCgig=6NeRgj5(cK3mhaejhd6zdIhggn0pdMg^f9dR8Kdmelb gFbh0Qc27Wh0fwgafyg9a6dod=fL8^gVcpdxgUhEd/040hg*fOg,fQe7b-6;g;gnh+gmg_h+eig}cZ0S9.2ucigy0Y9@f/duf;04gEf:cZfnfpf|fsh}gAhRcdgOfBbmh exdmhShXdeg7fKhNdag+5Wg-bT70h,h:edhxb%3fivh=gqgG9ygu0n0!0(7`ila1g!iM4}9Yf h^8V2Uh7iaihhbijc)ipf^0Te.i4hB7YdXiPe$04i(i.aAd*i:hJg562gIcP1~1GgNi$3@0{h!icdBdDfPgdfR8b8chth:21h/d~7bgp9tfhcP0%cRhTiG0 iJ0qiLj8cy0b7y7f7t7h7q1e0F7kjD2P2K0q902J7i830$0(0*0D04.
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