{"id":2745,"date":"2020-09-14T16:11:03","date_gmt":"2020-09-14T14:11:03","guid":{"rendered":"https:\/\/icn-isn-boissy.yj.fr\/wp\/?p=2745"},"modified":"2024-03-06T10:02:49","modified_gmt":"2024-03-06T09:02:49","slug":"algorithme-des-k-plus-proches-voisins","status":"publish","type":"post","link":"https:\/\/icn-isn-boissy.yj.fr\/wp\/2020\/09\/14\/algorithme-des-k-plus-proches-voisins\/","title":{"rendered":"Algorithme des k plus proches voisins"},"content":{"rendered":"\n
    \n
  1. Introduction
    L\u2019algorithme des k plus proches voisins appartient \u00e0 la famille des algorithmes d\u2019apprentissage automatique (machine learning).
    L\u2019id\u00e9e d\u2019apprentissage automatique ne date pas d\u2019hier, puisque le terme de machine learning a \u00e9t\u00e9 utilis\u00e9 pour la premi\u00e8re fois par
    l\u2019informaticien am\u00e9ricain Arthur Samuel en 1959. Les algorithmes d\u2019apprentissage automatique ont connu un fort regain d\u2019int\u00e9r\u00eat
    au d\u00e9but des ann\u00e9es 2000 notamment gr\u00e2ce \u00e0 la quantit\u00e9 de donn\u00e9es disponibles sur internet.
    L\u2019algorithme des k plus proches voisins est un algorithme d\u2019apprentissage supervis\u00e9, il est n\u00e9cessaire d\u2019avoir des donn\u00e9es labellis\u00e9es. \u00c0 partir d\u2019un ensemble E de donn\u00e9es labellis\u00e9es, il sera possible de classer (d\u00e9terminer le label) d\u2019une nouvelle donn\u00e9e (donn\u00e9e n\u2019appartenant pas \u00e0 E). \u00c0 noter qu\u2019il est aussi possible d\u2019utiliser l\u2019algorithme des k plus proches voisins \u00e0 des fins de r\u00e9gression (on cherche \u00e0 d\u00e9terminer une valeur \u00e0 la place d\u2019une classe), mais cet aspect des choses ne sera pas abord\u00e9 ici. L\u2019algorithme des k plus proches voisins est une bonne introduction aux principes des algorithmes d\u2019apprentissage automatique, il est en effet relativement simple \u00e0 appr\u00e9hender (l\u2019explication donn\u00e9e aux \u00e9l\u00e8ves peut \u00eatre tr\u00e8s visuelle). Cette premi\u00e8re approche des algorithmes d\u2019apprentissage peut aussi amener les \u00e9l\u00e8ves \u00e0 r\u00e9fl\u00e9chir sur l\u2019utilisation de leurs donn\u00e9es personnelles (m\u00eame si ce sujet a d\u00e9j\u00e0 abord\u00e9 auparavant) : de nombreuses soci\u00e9t\u00e9s (exemple les GAFAM) utilisent les donn\u00e9es concernant leurs utilisateurs afin de \u201dnourrir\u201d des algorithmes de machine learning qui permettront \u00e0 ces soci\u00e9t\u00e9s d\u2019en savoir toujours plus sur nous et ainsi de mieux cern\u00e9 nos \u201dbesoins\u201d en termes de consommation.<\/li>\n<\/ol>\n\n\n\n
      \n
    1. Principe de l’algorithme
      L\u2019algorithme de k plus proches voisins ne n\u00e9cessite pas de phase d\u2019apprentissage \u00e0 proprement parler, il faut juste stocker le jeu de
      donn\u00e9es d\u2019apprentissage.
      Soit un ensemble E contenant n donn\u00e9es labellis\u00e9es : E = {(yi
      , x\u20d7i)} avec i compris entre 1 et n, o\u00f9 yi correspond \u00e0 la classe
      (le label) de la donn\u00e9e i et o\u00f9 le vecteur x\u20d7i de dimension p (x\u20d7i = (x1i
      , x2i, \u2026, xpi)) repr\u00e9sente les variables pr\u00e9dictrices de la donn\u00e9e i. Soit une donn\u00e9e u qui n\u2019appartient pas \u00e0 E et qui ne poss\u00e8de pas de label (u est uniquement caract\u00e9ris\u00e9e par un vecteur x\u20d7u de dimension p). Soit d une fonction qui renvoie la distance entre la donn\u00e9e u et une donn\u00e9e quelconque appartenant \u00e0 E. Soit un entier k inf\u00e9rieur ou \u00e9gal \u00e0 n. Voici le principe de l\u2019algorithme de k plus proches voisins :
      \u25b7 On calcule les distances entre la donn\u00e9e u et chaque donn\u00e9e appartenant \u00e0 E \u00e0 l\u2019aide de la fonction d
      \u25b7 On retient les k donn\u00e9es du jeu de donn\u00e9es E les plus proches de u
      \u25b7 On attribue \u00e0 u la classe qui est la plus fr\u00e9quente parmi les k donn\u00e9es les plus proches.<\/li>\n<\/ol>\n\n\n\n
        \n
      1. \u00c9tude d’un exemple
        3.1. Les donn\u00e9es
        Nous avons choisi ici de nous baser sur le jeu de donn\u00e9es \u201diris de Fisher\u201d (il existe de nombreuses autres possibilit\u00e9s). Ce jeu de
        donn\u00e9es est compos\u00e9 de 50 entr\u00e9es, pour chaque entr\u00e9e nous avons :
        \u25b7 la longueur des s\u00e9pales (en cm)
        \u25b7 la largeur des s\u00e9pales (en cm)
        \u25b7 la longueur des p\u00e9tales (en cm)
        \u25b7 la largeur des p\u00e9tales (en cm)
        \u25b7 l\u2019esp\u00e8ce d\u2019iris : Iris setosa, Iris virginica ou Iris versicolor (label)
        Il est possible de t\u00e9l\u00e9charger ces donn\u00e9es au format csv, par exemple sur le site GitHub Gist<\/a> ou en le t\u00e9l\u00e9chargeant ici<\/a>
        Une fois ces donn\u00e9es t\u00e9l\u00e9charg\u00e9es, Il est n\u00e9cessaire de les modifier \u00e0 l\u2019aide d\u2019un tableur :
        \u25b7 dans un souci de simplification, nous avons choisi de travailler uniquement sur la taille des p\u00e9tales, nous allons donc supprimer les colonnes \u201dsepal_length\u201d et \u201dsepal_width\u201d
        \u25b7 il est n\u00e9cessaire d\u2019encoder les esp\u00e8ces avec des chiffres : 0 pour Iris setosa, 1 pour Iris virginica et 2 pour Iris versicolor (ce
        processus d\u2019encodage des donn\u00e9es textuelles est relativement classique en apprentissage automatique).
        3.2. Biblioth\u00e8ques Python utilis\u00e9es
        Nous allons utiliser 3 biblioth\u00e8ques Python :
        \u25b7 Pandas [3] qui va nous permettre d\u2019importer les donn\u00e9es issues du fichier csv
        \u25b7 Matplotlib [4] qui va nous permettre de visualiser les donn\u00e9es (tracer des graphiques)
        \u25b7 Scikit-learn [5] qui propose une impl\u00e9mentation de l\u2019algorithme des k plus proches voisins.
        Ces biblioth\u00e8ques sont facilement installables notamment en utilisant la distribution Anaconda (ou Miniconda).
        3.3. Premi\u00e8re visualisation des donn\u00e9es
        Une fois le fichier csv modifi\u00e9, il est possible d\u2019\u00e9crire un programme permettant de visualiser les donn\u00e9es sous forme de graphique
        (abscisse : \u201dpetal_length\u201d, ordonn\u00e9e : \u201dpetal_width\u201d) :
        <\/li>\n<\/ol>\n\n\n\n
        iris<\/a>T\u00e9l\u00e9charger<\/a><\/div>\n\n\n\n
        import pandas\nimport matplotlib.pyplot as plt\niris=pandas.read_csv(\"iris.csv\")\nx=iris.loc[:,\"petal_length\"]\ny=iris.loc[:,\"petal_width\"]\nlab=iris.loc[:,\"species\"]\nplt.scatter(x[lab == 0], y[lab == 0], color='g', label='setosa')\nplt.scatter(x[lab == 1], y[lab == 1], color='r', label='virginica')\nplt.scatter(x[lab == 2], y[lab == 2], color='b', label='versicolor')\nplt.scatter(2.5, 0.75, color='k')\nplt.legend()\nplt.show()\n<\/code><\/pre>\n\n\n\n
        \"FIGURE
        FIGURE 1 \u2013 Repr\u00e9sentation graphique des donn\u00e9es<\/figcaption><\/figure>\n\n\n\n
        3.4. Utilisation de l\u2019algorithme des k plus proches voisins Le graphique ci-dessus (figure 1) montre que les 3 classes (Iris setosa, Iris virginica et Iris versicolor) sont relativement bien s\u00e9par\u00e9es. On peut alors ajouter une donn\u00e9e non labellis\u00e9e n\u2019appartenant pas \u00e0 l\u2019ensemble d\u2019origine (voir figure 2) :<\/p>\n\n\n\n
        \"\"
        FIGURE 2 \u2013 Ajout d\u2019une donn\u00e9e non labellis\u00e9e<\/figcaption><\/figure>\n\n\n\n
        Dans l\u2019exemple ci-dessus (figure 2) les \u00e9l\u00e8ves n\u2019auront aucune difficult\u00e9 \u00e0 d\u00e9terminer l\u2019esp\u00e8ce de l\u2019iris qui a \u00e9t\u00e9 ajout\u00e9 au jeu de donn\u00e9es.
        Dans certains cas (exemple : largeur p\u00e9tale = 0,75 cm ; longueur p\u00e9tale = 2,5 cm) il est un peu plus difficile de se prononcer \u201dau premier coup d\u2019oeil\u201d (voir figure 3) :<\/p>\n\n\n\n
        \"\"
        FIGURE 3 \u2013 Cas plus difficile\u2026<\/figcaption><\/figure>\n\n\n\n


        \u00c0 partir de l\u2019exemple ci-dessus (voir figure 3), il est possible de demander aux \u00e9l\u00e8ves de proposer une m\u00e9thode permettant de traiter
        ce genre de cas litigieux. L\u2019enseignant peut, gr\u00e2ce \u00e0 une s\u00e9rie de \u201dquestions-r\u00e9ponses\u201d, amener doucement les \u00e9l\u00e8ves \u00e0 la solution
        propos\u00e9e par l\u2019algorithme des k plus proches voisins :
        \u25b7 on calcule la distance entre notre point (largeur du p\u00e9tale = 0,75 cm ; longueur du p\u00e9tale = 2,5 cm) et chaque point issu du
        jeu de donn\u00e9es \u201diris\u201d (\u00e0 chaque fois c\u2019est un calcul de distance entre 2 points tout ce qu\u2019il y a de plus classique) ;
        \u25b7 on s\u00e9lectionne uniquement les k distances les plus petites (les k plus proches voisins) ;

        \u25b7 parmi les k plus proches voisins, on d\u00e9termine quelle est l\u2019esp\u00e8ce majoritaire. On associe \u00e0 notre \u201diris myst\u00e8re\u201d cette \u201desp\u00e8ce
        majoritaire parmi les k plus proches voisins\u201d.
        Dans l\u2019exemple \u00e9voqu\u00e9 ci-dessus (largeur p\u00e9tale = 0,75 cm ; longueur p\u00e9tale = 2,5 cm), pour k=3, nous obtenons graphiquement :<\/p>\n\n\n\n
        \"\"
        FIGURE 4 \u2013 3 plus proches voisins dans le cas : largeur p\u00e9tale = 0,75 cm ; longueur p\u00e9tale = 2,5 cm<\/figcaption><\/figure>\n\n\n\n
        Un iris ayant une largeur de p\u00e9tale \u00e9gale \u00e0 0,75 cm et une longueur de p\u00e9tale \u00e9gale \u00e0 2,5 cm a une \u201dforte\u201d probabilit\u00e9 (cette notion
        de probabilit\u00e9 d\u2019obtenir un r\u00e9sultat correct gr\u00e2ce \u00e0 cet algorithme, bien que tr\u00e8s int\u00e9ressante, pourra difficilement \u00eatre abord\u00e9e avec
        des \u00e9l\u00e8ves de premi\u00e8re) d\u2019appartenir \u00e0 l\u2019esp\u00e8ce setosa.<\/p>\n\n\n\n
        3.5. Utilisation de scikit-learn (\u00e0 installer si absente de votre \u00e9diteur)<\/strong><\/em>
        La biblioth\u00e8que Python scikit-learn propose un grand nombre d\u2019algorithmes li\u00e9 \u00e0 l\u2019apprentissage automatique (c\u2019est sans aucun
        doute la biblioth\u00e8que la plus utilis\u00e9e en apprentissage automatique). Parmi tous ces algorithmes, scikit-learn propose l\u2019algorithme
        des k plus proches voisins. Voici un programme Python permettant de r\u00e9soudre le probl\u00e8me \u00e9voqu\u00e9 ci-dessus (largeur p\u00e9tale = 0,75
        cm ; longueur p\u00e9tale = 2,5 cm) :<\/p>\n\n\n\n
        import pandas\nimport matplotlib.pyplot as plt\r\nfrom sklearn.neighbors import KNeighborsClassifier\r\n\r\n#traitement CSV\r\niris=pandas.read_csv(\"iris.csv\")\r\nx=iris.loc[:,\"petal_length\"]\r\ny=iris.loc[:,\"petal_width\"]\r\nlab=iris.loc[:,\"species\"]\r\n#fin traitement CSV\r\n\r\n#valeurs\r\nlongueur=2.5\r\nlargeur=0.75\r\nk=3\r\n#fin valeurs\r\n\r\n#graphique\r\nplt.scatter(x[lab == 0], y[lab == 0], color='g', label='setosa')\r\nplt.scatter(x[lab == 1], y[lab == 1], color='r', label='virginica')\r\nplt.scatter(x[lab == 2], y[lab == 2], color='b', label='versicolor')\r\nplt.scatter(longueur, largeur, color='k')\r\nplt.legend()\r\n#fin graphique\r\n\r\n#algo knn\r\nd=list(zip(x,y))\r\nmodel = KNeighborsClassifier(n_neighbors=k)\r\nmodel.fit(d,lab)\r\nprediction= model.predict([[longueur,largeur]])\r\n#fin algo knn\r\n\r\n#Affichage r\u00e9sultats\r\ntxt=\"R\u00e9sultat : \"\r\nif prediction[0]==0:\r\n    txt=txt+\"setosa\"\r\nif prediction[0]==1:\r\n    txt=txt+\"virginica\"\r\nif prediction[0]==2:\r\n    txt=txt+\"versicolor\"\r\nplt.text(3,0.5, f\"largeur : {largeur} cm longueur : {longueur} cm\", fontsize=12)\r\nplt.text(3,0.3, f\"k : {k}\", fontsize=12)\r\nplt.text(3,0.1, txt, fontsize=12)\r\n#fin affichage r\u00e9sultats\r\n\r\nplt.show()\n<\/code><\/pre>\n\n\n\n
        Nous obtenons le r\u00e9sultat suivant (voir figure 5) :<\/p>\n\n\n\n
        \"\"
        FIGURE 5 \u2013 3 plus proches voisins \u00e0 l\u2019aide de scikit-learn dans le cas : largeur p\u00e9tale = 0,75 cm ; longueur p\u00e9tale = 2,5 cm
        <\/figcaption><\/figure>\n\n\n\n
        Il est ensuite possible de demander aux \u00e9l\u00e8ves de m le programme ci-dessus afin d\u2019\u00e9tudier les changements induits par la
        modification du param\u00e8tre k (notamment pour k=5) en gardant toujours les m\u00eames valeurs de largeur et de longueur (largeur p\u00e9tale
        = 0,75 cm ; longueur p\u00e9tale = 2,5 cm).
        Pour terminer, il est aussi possible de demander aux \u00e9l\u00e8ves de travailler avec d\u2019autres valeurs de longueur et largeur.<\/p>\n\n\n\n
          \n
        1. Possibilit\u00e9 de projet
          Il est possible, dans le cadre d\u2019un projet, de faire travailler les \u00e9l\u00e8ves sur un autre jeu de donn\u00e9es, par exemple, \u201dPr\u00e9dire les survivants
          du Titanic\u201d. Le jeu de donn\u00e9es peut \u00eatre r\u00e9cup\u00e9r\u00e9 sur le site kaggle [6]. Le label est \u201dsurvivant\u201d ou \u201dd\u00e9c\u00e9d\u00e9\u201d. Il sera n\u00e9cessaire de
          retravailler les donn\u00e9es comme nous l\u2019avons fait pour le jeu de donn\u00e9es \u201dIris\u201d (supprimer des colonnes, encodage\u2026). Dans ce projet
          il sera possible de faire travailler les \u00e9l\u00e8ves sur des vecteurs d\u2019entr\u00e9e de dimension sup\u00e9rieure \u00e0 2 (le genre, l\u2019\u00e2ge, la classe occup\u00e9e
          par le passager sur le bateau, \u2026).<\/li>\n<\/ol>\n\n\n\n
          voici un lien vers le projet Titanic d\u00e9velopp\u00e9 par Benoit Fourlegnie:<\/p>\n\n\n\n
          projet titanic<\/a><\/p>\n\r\n","protected":false},"excerpt":{"rendered":"
          3.4. Utilisation de l\u2019algorithme des k plus proches voisins Le graphique ci-dessus (figure 1) montre que les 3 classes (Iris setosa, Iris virginica et Iris versicolor) sont relativement bien s\u00e9par\u00e9es. On peut alors ajouter une donn\u00e9e non labellis\u00e9e n\u2019appartenant pas \u00e0 l\u2019ensemble d\u2019origine (voir figure 2) : Dans l\u2019exemple ci-dessus (figure 2) les \u00e9l\u00e8ves n\u2019auront … Continuer la lecture de Algorithme des k plus proches voisins<\/span>  →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[57,70],"tags":[],"class_list":["post-2745","post","type-post","status-publish","format-standard","hentry","category-nsi","category-algorithmique"],"_links":{"self":[{"href":"https:\/\/icn-isn-boissy.yj.fr\/wp\/wp-json\/wp\/v2\/posts\/2745","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/icn-isn-boissy.yj.fr\/wp\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/icn-isn-boissy.yj.fr\/wp\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/icn-isn-boissy.yj.fr\/wp\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/icn-isn-boissy.yj.fr\/wp\/wp-json\/wp\/v2\/comments?post=2745"}],"version-history":[{"count":10,"href":"https:\/\/icn-isn-boissy.yj.fr\/wp\/wp-json\/wp\/v2\/posts\/2745\/revisions"}],"predecessor-version":[{"id":4166,"href":"https:\/\/icn-isn-boissy.yj.fr\/wp\/wp-json\/wp\/v2\/posts\/2745\/revisions\/4166"}],"wp:attachment":[{"href":"https:\/\/icn-isn-boissy.yj.fr\/wp\/wp-json\/wp\/v2\/media?parent=2745"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/icn-isn-boissy.yj.fr\/wp\/wp-json\/wp\/v2\/categories?post=2745"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/icn-isn-boissy.yj.fr\/wp\/wp-json\/wp\/v2\/tags?post=2745"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}