K plus proches voisins

L'algorithme des "k plus proches voisins" (en anglais "k nearest neighbors" : knn)

Afin de travailler sur un exemple, nous allons utiliser un jeu de données relativement connu dans le monde du machine learning : le jeu de données "iris".

En 1936, Edgar Anderson a collecté des données sur 3 espèces d'iris : "iris setosa", "iris virginica" et "iris versicolor"

Iris Setosa

Iris Virginica

Iris Versicolor

Pour chaque iris étudié, Anderson a mesuré (en cm) :

• la largeur des sépales

• la longueur des sépales

• la largeur des pétales

• la longueur des pétales

Par souci de simplification, nous nous intéresserons uniquement à la largeur et à la longueur des pétales.

Pour chaque iris mesuré, Anderson a aussi noté l'espèce ("iris setosa", "iris versicolor" ou "iris virginica")

Vous trouverez 50 de ces mesures dans le fichier iris.csv

En résumé, vous trouverez dans ce fichier :

• la longueur des pétales

• la largeur des pétales

• l'espèce de l'iris (au lieu d'utiliser les noms des espèces, on utilisera des chiffres : 0 pour "iris setosa", 1 pour "iris versicolor" et 2 pour "iris virginica")

Nous pouvons représenter les données à l'aide du module Pandas :

import pandas
import matplotlib.pyplot as plt
iris=pandas.read_csv("iris.csv")
x=iris.loc[:,"petal_length"]
y=iris.loc[:,"petal_width"]
lab=iris.loc[:,"species"]
plt.axis('equal')
plt.scatter(x[lab == 0], y[lab == 0], color='g', label='setosa')
plt.scatter(x[lab == 1], y[lab == 1], color='r', label='versicolor')
plt.scatter(x[lab == 2], y[lab == 2], color='b', label='virginica')
plt.legend()
plt.show()

Voici ce que l'on obtient :

Graphisme sans les modules pandas et csv

Pour s'entrainer, notamment avec la méthode split(',') qui sépare une chaîne de caractères à chaque virgule.

Chacune des lignes sera séparée en 3 chaînes qui seront ensuite converties en flottants.

Après avoir télécharger le fichier, complétez le code suivant pour obtenir les nuages de points.

from matplotlib import pyplot as plt

with open("iris.csv","r") as f:
    premiere_ligne = f.readline() # la première ligne est mise de côté
    x_setosa, y_setosa = [],[]
    x_versicolor, y_versicolor = [],[]
    x_virginica, y_virginica = [],[]

    contenu = f.readlines()
    for ligne in contenu:
        l,w,s = .... # en utilisant float(...)pour convertir et split(',') pour séparer les lignes.

        # en fonction de l'espère, qui est stockée dans la variable s, on ajoute aux listes x_.... et y_... correspondantes 
        if s == 0:
            ...
            ...
        elif s == 1:
            ...
            ...
        else:
            ...
            ...

plt.scatter(x_setosa, y_setosa, color = 'g') # nuage des setosa en vert
plt.scatter(.....) # nuage des versicolor en rouge
plt.scatter(....) # nuage des virginca en bleu
plt.show()

Nous obtenons des "nuages" de points, on remarque ces points sont regroupés par espèces d'iris (pour "iris virginica" et "iris versicolor", les points ont un peu tendance à se mélanger).

Imaginez maintenant qu'au cours d'une promenade vous trouviez un iris, n'étant pas un spécialiste, il ne vous est pas vraiment possible de déterminer l'espèce.

En revanche, vous êtes capables de mesurer la longueur et la largeur des pétales de cet iris. Partons du principe qu'un pétale fasse 0,5 cm de large et 2 cm de long.

Plaçons cette nouvelle donnée sur notre graphique (il nous suffit d'ajouter la ligne "plt.scatter(2.0, 0.5, color='k')", le nouveau point va apparaitre en noir (color='k')) :

Je pense que le résultat est sans appel : il y a de fortes chances que votre iris soit de l'espèce "iris setosa".

Il est possible de rencontrer des cas plus difficiles, par exemple : largeur du pétale = 0,75 cm ; longueur du pétale = 2,5 cm :

Dans ce genre de cas, il peut être intéressant d'utiliser l'algorithme des "k plus proches voisins", en quoi consiste cet algorithme :

• on calcule la distance entre notre point (largeur du pétale = 0,75 cm ; longueur du pétale = 2,5 cm) et chaque point issu du jeu de données "iris" (à chaque fois c'est un calcul de distance entre 2 points tout ce qu'il y a de plus classique)

• on sélectionne uniquement les k distances les plus petites (les k plus proches voisins)

• parmi les k plus proches voisins, on détermine quelle est l'espèce majoritaire. On associe à notre "iris mystère" cette "espèce majoritaire parmi les k plus proches voisins"

Prennons k = 3

Les 3 plus proches voisins sont signalés ci-dessus avec des flèches : nous avons deux "iris setosa" (point vert) et un "iris versicolor" (point rouge).

D'après l'algorithme des "k plus proches voisins", notre "iris mystère" appartient à l'espèce "setosa".

Importance du bon choix de k

Le choix de la bonne valeur de k est important pour de meilleurs résultats :

• Une valeur de k trop petite peu renforcer l'iportance des valeurs "anormales" de la série de référence

• Une valeur de k trop grande inclus des valeurs dont la similitude n'est plus justifiée.

On conseille de prendre k entre 3 et 10.

Code de l'algorithme KNN

On souhaite écrire le code de la fonction knn qui prend en argumant la longueur l, largeur w d'un iris inconnu ainsi que le choix du nombre de voisins k utilisé pour la détermination et qui retourne la catégorie supposée de l'iris.

On utilise la fonction annexe distance qui retourne la distance euclidienne entre deux points de coordonnées respectives (x1,y1) et (x2,y2).

Dans le code suivant on dispose d'une variable iris qui contient une liste de 150 tuples au format (l,w,s) longueur l, largeur w et espece s des 150 iris de réféence.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)

Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)

Entrer ou sortir du mode "plein écran"
(Esc)

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

.128013it3a;dv,EnT2.S5éwb*cy+14: f-up08)_j9eklohxrPè=[sà6(]/mg7050g0L0c0e0b0N0W0A0u0N0e0W0W0U010c0b0E010406050W0D0$0$0e0R0v040o0O0N0D0|0O0k050#13151719110E04051p1i1s0#1p110g0b0h0;0?0^0`0?0k0%0D0e0%0L0C0E0v0c0P1g0A0P0b0%0P0N1U0P0c0 050,0s0N0L1B0@0_011T1V1X1V0c1%1)1#0c0R1q1P0;1c0W0E0e0k0`0m011+1D010B0.0L0k0e0$0L1#2022271-2a1)2d2f0 0a0A0S0R0O0E0O0W0b1f0k0A0*1~0R0R0L0u2A1i2i0k1q0#1P2N1`1|1{1$0g2k1E0b0k2c2x1#1y1A0=1,2X2Z0k0O2%1#0E2G1q2L2N2@12212B2)282-0R160N1#0e1S2G0B0`030I0I0u2.0L1X2,0O0C0m0C0x0 0A0x1i0e2^2{102`2j2}1-2 3133350L3701393b3d3f2!3i3i3m0m3p3r223t2L2W013y0e321q340P36383a3c0*3I2-3K0d3m0d3O2K3s113S3w0`3V3X053Z3#3E3%3H2Y3J3j0y3m0y3:1j3=3u2|1C3x0O303W3A3!3C3$3G3)423+3j0p3m0p482@3?2{3T3`4i3~3F3(3e4o3h3j0Y3m0Y4u4a3@4d3_4f3z3Y3B3D4C413g3K0(3m0(4L3Q4w3v4O3U4Q4h4S4j4U404n4X3j0G3m0G4$2M4(4c2*4+4g3{3}4k3 4m4E4?0C0K3m0K4{3R4x3^504R3|4T4l4D3*4G3k0F0 0x0F5d4}4y4,525k555m4F3K0x3l045E5u4b5w514A544V4=433k255G3N0#3q3;4%5J5g4z4.4B4;575Q0x3-5G3/5V3P4|5Z4*5#5j4/5l4W5*455G475/5X5;4N4 5@534:565n5D4r5G4t60495Y632~5x5M675B580x4I5G4K6e4v5=646j5$5N5(693j0x4Z5G4#6s4M5f5?6w5^5%685C6B4^5G4`6G6g6I6v5L6x6l5{4p3k5a5G5c6T626V6i6X6L6y6N580m5q046?5I6h4e6.665`5P6#0m5F726`6,6|5i6~5A6!5o0m5S7d754)6W785z5O5)715,0m5.5W6f6+7h6-7j5_7a707c5}0m5 7r6t6{4P6}7k6z6O3i6b0m6d7E3s1t2=1i2%2Q0g1|2V5g4D2$1z1q2;0L2?7R7s1q4D7+2j0b0g0`3a2L5D3A7=7@6;5*262o0L7}6m7 2N5W7G010M0 0*0B617:4~280r3m8e6u2~0B8b0b0W0,0k0u0L8k880~040Z8v763_0 0Q3o7-8l1-8x0z8e0A8H3_0s0 0B0N0O0e0c8A7u8I0 0i8W8g3x0 0v8F2_8w0 8K7-8M880k8P048R8T8V8G8,048!8{8B3U8D5U8+908J8L8N3U8?8^8U8#3T8x8~948X8C040v937R8|8.2@8:908=8Q8S9c8 9i018x0H9d5g0O0 0C020%0c0f978;9a9v8`9h8$0`967-119x2B7|017^2{3K5S5j9Y7K6=802e829Z7~711#5/0A9@9r9y8a042G0c0D0R1h8/988x0Z8z9W4y8D8*3s9_9R019E040C9C5?92ai4 9A9L90af0t0tao9y0$0b0 9m3Qac3Taf0watada4al2~8(aaaz98afaha28;8(ay2Ma30 9BaPap0 araE3TavaxaH8Y04aW9qaMaZasaXau8n040F0n6d6ta79)0I7_3j5,9(7?9/846#3-0A81837b3,9=3q9V9Q0Aa}a 0C5}b2ba7z3K45b89-bn7m5obl60889{8ca)0`8i048Ma75!a?0M0ka1bg5gaGbGaj040NbB9z8-a#5!9N8_bT9fbWbQ0rb!bVa;ad9t8@9Ob)8}b$640 0Mb:9pab98b-2Y9P9n95aVb=28aN9H9Jc33x8?b~b_8ebfc07;b39!223K6bbmb4bb4q9,2fbt6A0Ccl9?9^980u5F030;0R0q8U0b1R2D0?0A1X8q1*0*0:3c0D0E1)0:0Z0L202H0L0i2C8p8r8t0H0A2w9 0;0P0e0u0D2BcObh0R8p2C1*cD0B0q2G8s8u9U9dbi9#4H7{ch9:5o4Ibrcrcnbod686bEcxaQ04cW0E0I1y8qc80`af0UdrbU040V0!cdd3d8bj6Dcm9*5Q4Zdc9.dG6#dEcw9@989{0B4fdv0k0 0bdv0ObD2YdUdWc^0Wccd2a|dCd50C6QdFd93K4^dJcs7Ld:dO9^dPdk1Xb:9gb{dk0rdXbPam8Zd$042ydY0 dub+a804e6a-88cz0 cB0h3W0L9 0:cI02030d0K0f0bd(dAd,7}bj6%d;b55o5ad^debu3KeGd|d}b|0 dmdoc$bTaf0nbTdV040e0E0E2c0gb:a5e!0 ece728b#eg5!8o8q228te,e.bRe1e~b(e;a*e23QeSbRejcfaFe9f39je5b:0Hfhdvem04cB0e0J0O1e2C0D1~cR1)0AcVcX8tc!dpc%0Lc)0XcK34cL0c1*eUfBeCbgd4cj6B6@eHco5pcqdKd=fRbd3teD9/bj5Ed7d_6n3leLdL5of)dheRelcA0A0lc^c`fGcKc$fK20eV8q0A130RcKcWc#e`d0cP2u8p0W22fJd)d+fOd-fQ5Rf*eMct0x25f.fYgnf=dj9seTg1fMfdae0 eZgCe#0W4fb f68|a6bMbQ0M0L0ved04efek909{0?0$0s0g0eea0Qd*gW9ye#g)gC8x0VbTa%5Gb:0!a,4af$ci0k5Db134a}eIg fWf+5*b15/cegL4xfPg~6Bblh1d8h3hfh5gp7L0xbw3qf?90fkcB0jfy1*16foc^0,eA1*21300bg70:0Mc*2Gav0L2G0:ep1)esf|cJfI1*1`0b0qg0dngBa{gkeEd.0xclhhh66#h+hlf/6af!hrg,0 3c0$0E0,1KgTgVe3c1dxg=awa@f0gCg?5tg/fcgO4 iag^fjf^h{h}erg6c+g6cT0A0d0Adm0T8tgih%fabhglhe3k6pfTdfiDh;gu6oh@gx9`8QdTe@bQixi29ydZdWbLiTb,gzh#eWicdxb`hbh_04b^i%0!i)5;g|a~h*dEh-hm6ndIb9i`5*dNhqd}iMiZ04ikh~d1iee=0 g;gGe/b:jcj91-igi.dziQ4 aCi1aL88g?aKi;h(f%h*d:i_h=6PiIhj3kd{bedBh)gm0xeGjziJeKi}jA6$iLd~hsf^9}fpa01*0Nevexez0k1y8thT34hQim0Ahy4f2z0-2GfNizhd9$fSjMjD6?jCfUj gwjTiNei8djmaIj50Oh|j7jfi50 ibjh9S0 jlg+adafc60fjp2MaAbX0 16g.kidwgNize^kakc1Jj8kB4*g:kfg@i%0zg_i:f#jvg}9$5FiFeN3j72k0iGkYk3j2dQ0 9}9 iXjq90jjiyi*9XiB9$9%j}k1gsjPgu7djSkt4*9{4Ek7kmehj6kFkei9i6jt8f9ekkgTkpkrbEf7l7h i%jgkHifi6aSldbNkkkPhaaT3Sj`kXh0iAh.7cb7k|j~h8j1j2l04 9{k*a0dvjsj^k;lDjwgm7CgojQlYgtj~hpdik4adl20/kGlUlu04lwjHlWiC7OlZk}4rl$k1cvlKk%byk)0+k+lRlrlTaT0#7/7S7*7U7%1i0c7Xmg2T2O0e1(md0#7V9V0*hB0/04.

Améliorations possibles :

• La fonction distance euclidienne peut être remplacée par la distance de Manhattan ou alors en ne calculant pas la racine carrée, on ne change pas l'ordre pour les distances

• plutôt sur de trier toute la liste des couples, on peut la parcourir et ne mémoriser à chaque itération que le k valeur les plus petites. Cela améliore la compléxité d'autant plus que le rapport k / taille de la série est faible.