{"id":1748,"date":"2022-05-16T17:10:10","date_gmt":"2022-05-16T15:10:10","guid":{"rendered":"https:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/?p=1748"},"modified":"2022-05-16T17:58:04","modified_gmt":"2022-05-16T15:58:04","slug":"algorithme-des-k-plus-proches-voisins","status":"publish","type":"post","link":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/2022\/05\/16\/algorithme-des-k-plus-proches-voisins\/","title":{"rendered":"Algorithme des k plus proches voisins"},"content":{"rendered":"\n
\"SMILEY<\/a><\/figure>\n\n\n\n

<\/p>\n\n\n\n

Vid\u00e9o pour mieux comprendre l’algorithme k-NN : https:\/\/www.youtube.com\/watch?v=HVXime0nQeI<\/a><\/p>\n\n\n\n

\"Bien<\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n

Lien Openclassroom : https:\/\/openclassrooms.com\/fr\/courses\/4011851-initiez-vous-au-machine-learning\/4022441-entrainez-votre-premier-k-nn<\/a><\/p>\n\n\n\n

<\/p>\n\n\n\n

Lien des tests GoogleColab : https:\/\/colab.research.google.com\/drive\/1Gezch3iXfSzYDYiTpQSabGkbEKJkqllF<\/a><\/p>\n\n\n\n

<\/p>\n\n\n\n

Algorithme k-NN :<\/strong><\/p>\n\n\n\n

k-NN<\/strong> est le diminutif de K Nearest Neighbors<\/strong>.<\/p>\n\n\n\n

L’algorithme k-NN peut servir autant pour la classification que pour la r\u00e9gression. Il est surnomm\u00e9 \u00ab\u00a0nearest neighbors\u00a0\u00bb car le principe de ce mod\u00e8le consiste en effet \u00e0 choisir les\u00a0k<\/strong>\u00a0donn\u00e9es les plus proches du point \u00e9tudi\u00e9 afin d\u2019en pr\u00e9dire sa valeur.<\/p>\n\n\n\n

<\/p>\n\n\n\n

Comment fonctionne k-NN ?<\/strong><\/p>\n\n\n\n

Voici un petit exemple visuel afin de comprendre le fonctionnement de l’algorithme :<\/p>\n\n\n\n

Ci-dessous, un jeu de donn\u00e9es d\u2019entra\u00eenement avec deux classes, rouge et bleu. L’input<\/em>\u00a0est donc\u00a0bidimensionnel<\/em>\u00a0ici, et la\u00a0target<\/em>\u00a0est la couleur \u00e0 classer.<\/p>\n\n\n\n

\"\"
nuage de points de test<\/figcaption><\/figure>\n\n\n\n

Si l’on a une nouvelle entr\u00e9e dont on veut pr\u00e9dire la classe, comment pourrait-on faire ?<\/p>\n\n\n\n

\"\"
Le point blanc est une nouvelle entr\u00e9e.
<\/figcaption><\/figure>\n\n\n\n

On va simplement regarder les\u00a0k<\/strong>\u00a0voisins les plus proches de ce point et regarder quelle classe constitue la majorit\u00e9 de ces points, afin d’en d\u00e9duire la classe du nouveau point. Par exemple, ici, si on utilise le 5-NN, on peut pr\u00e9dire que la nouvelle donn\u00e9e appartient \u00e0 la classe\u00a0rouge<\/strong>\u00a0puisqu’elle a 3 rouges et 2 bleus\u00a0dans son entourage.\u00a0<\/p>\n\n\n\n

\"\"
Les 5 points les plus proches du point que l’on cherche \u00e0 classer
<\/figcaption><\/figure>\n\n\n\n

On peut facilement en d\u00e9duire les zone rouge et bleue, o\u00f9 les points qui se situeront dans la zone seront respectivement class\u00e9s comme rouge ou bleu.<\/p>\n\n\n\n

\"\"
Les deux zones qui s\u00e9parent l’espace pour la d\u00e9cision \u00e0 prendre sur la classification de nouvelles entr\u00e9es avec le mod\u00e8le 5-NN
<\/figcaption><\/figure>\n\n\n\n

le k-NN est un type sp\u00e9cial d\u2019algorithme qui n\u2019utilise pas de mod\u00e8le statistique. Il est \u00ab\u00a0non param\u00e9trique\u00a0\u00bb et il se base uniquement sur les donn\u00e9es d\u2019entra\u00eenement. Ce type d\u2019algorithme est appel\u00e9\u00a0memory-based<\/em>. A contrario, la r\u00e9gression lin\u00e9aire est param\u00e9trique, de param\u00e8tre\u00a0\u03b8\u00a0et ne va donc pas avoir besoin de conserver toutes les donn\u00e9es pour effectuer des pr\u00e9dictions, mais seulement\u00a0\u03b8.\u00a0<\/p>\n\n\n\n

C’est d’ailleurs un autre inconv\u00e9nient de l’algorithme k-NN, il doit conserver toutes les donn\u00e9es d’entra\u00eenement en m\u00e9moire (memory-based<\/em>) et donc convient aux probl\u00e8mes d’assez petite taille.<\/p>\n\n\n\n

Il va s’agir maintenant de choisir le bon nombre de voisins k, en fonction de\u00a0l\u2019erreur de g\u00e9n\u00e9ralisation du mod\u00e8le.<\/p>\n\n\n\n

<\/p>\n\n\n\n

Utiliser k-NN sur un vrai jeu de donn\u00e9es :<\/strong><\/p>\n\n\n\n

Les donn\u00e9es et la probl\u00e9matique<\/h4>\n\n\n\n

D’abord, parlons du jeu de donn\u00e9es que nous allons utiliser. C’est un dataset\u00a0tr\u00e8s c\u00e9l\u00e8bre, appel\u00e9 MNIST.\u00a0Il est constitu\u00e9 d’un ensemble de 70000\u00a0images 28×28 pixels en noir et blanc annot\u00e9es du chiffre correspondant (entre 0\u00a0et 9). L’objectif de ce jeu de donn\u00e9es \u00e9tait de permettre \u00e0 un ordinateur d’apprendre \u00e0 reconna\u00eetre des nombres manuscrits automatiquement (pour lire des ch\u00e8ques par exemple). Ce dataset utilise des donn\u00e9es r\u00e9elles qui ont d\u00e9j\u00e0 \u00e9t\u00e9 pr\u00e9-trait\u00e9es pour \u00eatre plus facilement utilisables par un algorithme.<\/p>\n\n\n\n

<\/p>\n\n\n\n

\"\"
Un extrait du type d’images que l’on trouve dans le dataset MNIST
<\/figcaption><\/figure>\n\n\n\n

Notre objectif sera donc d’entra\u00eener un mod\u00e8le qui sera capable de reconna\u00eetre les chiffres \u00e9crits sur ce type d’images. Par chance, ce jeu de donn\u00e9es est t\u00e9l\u00e9chargeable directement \u00e0 partir d’une fonction scikit-learn. \ud83d\ude07 On peut donc directement obtenir\u00a0ce dataset via un appel de fonction :<\/p>\n\n\n\n

from sklearn.datasets import fetch_openml\nmnist = fetch_openml('mnist_784', version=1)<\/pre>\n\n\n\n
L’objet \u00a0mnist<\/code>\u00a0contient deux entr\u00e9es principales, \u00a0data<\/code>\u00a0 et \u00a0target<\/code>. On peut les afficher :<\/p>\n\n\n\n
# Le dataset principal qui contient toutes les images\nprint (mnist.data.shape)\n\n# Le vecteur d'annotations associ\u00e9 au dataset (nombre entre 0 et 9)\nprint (mnist.target.shape)<\/pre>\n\n\n\n
\"\"<\/figure>\n\n\n\n
  • \u00a0data<\/code>\u00a0contient les images sous forme de tableaux de 28 x 28 = 784 couleurs de pixel en niveau de gris, c’est-\u00e0-dire que la couleur de chaque pixel\u00a0est repr\u00e9sent\u00e9e par un nombre entre 0 et 16 qui repr\u00e9sente si celle-ci est proche du noir ou pas (0 = blanc, 16 = noir).\u00a0<\/li>
  • \u00a0target<\/code>\u00a0qui contient les annotations (de 1 \u00e0 9) correspondant \u00e0 la valeur \u00ab\u00a0lue\u00a0\u00bb du chiffre.<\/li><\/ul>\n\n\n\n
    \u00c9chantillonner pour faciliter le travail :<\/p>\n\n\n\n
    Le dataset est relativement petit mais, pour le mod\u00e8le k-NN, il est d\u00e9j\u00e0 trop gros pour obtenir rapidement des r\u00e9sultats. On va donc effectuer un sampling et travailler sur seulement 5000 donn\u00e9es :<\/p>\n\n\n\n
    import numpy as np\nsample = np.random.randint(70000, size=5000)\ndata = mnist.data.values[sample]\ntarget = mnist.target.values[sample]<\/pre>\n\n\n\n
    Ne pas oublier import numpy as np ! \ud83d\ude46<\/p>\n\n\n\n
    S\u00e9parez training \/ testing set<\/h4>\n\n\n\n
    Une fois notre dataset charg\u00e9, comme nous l’avons vu dans le chapitre pr\u00e9c\u00e9dent, nous allons s\u00e9parer le jeu de donn\u00e9es en training set et testing set.<\/p>\n\n\n\n
    J’ai ici appel\u00e9 les images d’exemple \u00ab\u00a0X\u00a0\u00bb et les annotations cibles \u00ab\u00a0y\u00a0\u00bb :<\/p>\n\n\n\n
    from sklearn.model_selection import train_test_split\n\nxtrain, xtest, ytrain, ytest = train_test_split(data, target, train_size=0.8)<\/pre>\n\n\n\n
    On peut cr\u00e9er\u00a0un premier classifieur 3-NN, c’est-\u00e0-dire qui prend en compte les 3 plus proches voisins pour la classification. Pour cela, on va utiliser l’impl\u00e9mentation de l’algorithme qui existe dans la librairie scikit-learn\u00a0:<\/p>\n\n\n\n
    from sklearn import neighbors\n\nknn = neighbors.KNeighborsClassifier(n_neighbors=3)\nknn.fit(xtrain, ytrain)<\/pre>\n\n\n\n
    \"\"<\/figure>\n\n\n\n
    Testons \u00e0 pr\u00e9sent\u00a0l\u2019erreur de notre classifieur. La m\u00e9thode \u00a0score<\/code>\u00a0\u00a0effectue exactement \u00e7a : tester les performances de pr\u00e9diction d’un\u00a0classifieur dans lequel on passe un jeu de donn\u00e9es annot\u00e9 \u2014 dans notre cas le jeu de donn\u00e9es de test. Il renvoie ainsi le pourcentage de pr\u00e9diction v\u00e9ridique trouv\u00e9e par le classifieur.<\/p>\n\n\n\n
    error = 1 - knn.score(xtest, ytest)\nprint('Erreur: %f' % error)<\/pre>\n\n\n\n
    \"\"<\/figure>\n\n\n\n
    Optimisation du score sur les donn\u00e9es test<\/h4>\n\n\n\n
    Pour trouver le k optimal, on va simplement tester le mod\u00e8le pour tous les k de 2\u00a0\u00e0 15, mesurer l\u2019erreur test et afficher la performance en fonction de k :<\/p>\n\n\n\n
    import matplotlib.pyplot as plt\nerrors = []\nfor k in range(2,15):\n    knn = neighbors.KNeighborsClassifier(k)\n    errors.append(100*(1 - knn.fit(xtrain, ytrain).score(xtest, ytest)))\nplt.plot(range(2,15), errors, 'o-')\nplt.show()<\/pre>\n\n\n
    Ne pas oublier import matplotlib.pyplot as plt ! \ud83d\ude47<\/span><\/p>\n\n\n
    \"\"
    L’erreur en pourcentage pour les diff\u00e9rents classifieurs
    <\/figcaption><\/figure>\n\n\n\n
    Comme on peut le voir, le k-NN le plus performant est celui pour lequel k = 4. On conna\u00eet donc notre classifieur final optimal : 4-nn. Ce qui veut dire que c’est celui qui classifie le mieux les donn\u00e9es, et qui donc dans ce cas pr\u00e9cis reconna\u00eet au mieux les nombres \u00e9crits \u00e0 la main.<\/p>\n\n\n\n
    \u00c0 titre d’exemple, vous pouvez afficher les pr\u00e9dictions du classifieur sur quelques donn\u00e9es.<\/p>\n\n\n\n
    # On r\u00e9cup\u00e8re le classifieur le plus performant\nknn = neighbors.KNeighborsClassifier(4)\nknn.fit(xtrain, ytrain)\n\n# On r\u00e9cup\u00e8re les pr\u00e9dictions sur les donn\u00e9es test\npredicted = knn.predict(xtest)\n\n# On redimensionne les donn\u00e9es sous forme d'images\nimages = xtest.reshape((-1, 28, 28))\n\n# On selectionne un echantillon de 12 images au hasard\nselect = np.random.randint(images.shape[0], size=12)\n\n# On affiche les images avec la pr\u00e9diction associ\u00e9e\nfig,ax = plt.subplots(3,4)\n\nfor index, value in enumerate(select):\n    plt.subplot(3,4,index+1)\n    plt.axis('off')\n    plt.imshow(images[value],cmap=plt.cm.gray_r,interpolation=\"nearest\")\n    plt.title('Predicted: {}'.format( predicted[value]) )\n\nplt.show()<\/pre>\n\n\n\n
    \"\"
    Les pr\u00e9dictions du classifieur associ\u00e9es aux images
    <\/figcaption><\/figure>\n\n\n\n
    Pour pouvoir un peu mieux comprendre les erreurs effectu\u00e9es par le classifieur, on peut aussi afficher un extrait des pr\u00e9dictions erron\u00e9es :<\/p>\n\n\n\n
    # on r\u00e9cup\u00e8re les donn\u00e9es mal pr\u00e9dites \nmisclass = (ytest != predicted)\nmisclass_images = images[misclass,:,:]\nmisclass_predicted = predicted[misclass]\n\n# on s\u00e9lectionne un \u00e9chantillon de ces images\nselect = np.random.randint(misclass_images.shape[0], size=12)\n\n# on affiche les images et les pr\u00e9dictions (erron\u00e9es) associ\u00e9es \u00e0 ces images\nfor index, value in enumerate(select):\n    plt.subplot(3,4,index+1)\n    plt.axis('off')\n    plt.imshow(misclass_images[value],cmap=plt.cm.gray_r,interpolation=\"nearest\")\n    plt.title('Predicted: {}'.format(misclass_predicted[value]) )\n\nplt.show()<\/pre>\n\n\n\n
    \"\"
    Quelques exemples d’images mal class\u00e9es
    <\/figcaption><\/figure>\n\n\n\n
    En r\u00e9sum\u00e9 : on vient de voir sur un algorithme simple comment l’entra\u00eener sur des donn\u00e9es pour ensuite optimiser les param\u00e8tres de cet algorithme \u00e0 l\u2019aide d\u2019un jeu de donn\u00e9es test.<\/strong><\/p>\n","protected":false},"excerpt":{"rendered":"
    Vid\u00e9o pour mieux comprendre l’algorithme k-NN : https:\/\/www.youtube.com\/watch?v=HVXime0nQeI Lien Openclassroom : https:\/\/openclassrooms.com\/fr\/courses\/4011851-initiez-vous-au-machine-learning\/4022441-entrainez-votre-premier-k-nn Lien des tests GoogleColab : https:\/\/colab.research.google.com\/drive\/1Gezch3iXfSzYDYiTpQSabGkbEKJkqllF Algorithme k-NN : k-NN est le diminutif de K Nearest Neighbors. L’algorithme k-NN peut servir autant pour la classification que pour la r\u00e9gression. Il est surnomm\u00e9 \u00ab\u00a0nearest neighbors\u00a0\u00bb car le principe de ce mod\u00e8le consiste en effet […]<\/p>\n","protected":false},"author":4,"featured_media":1827,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/posts\/1748"}],"collection":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/comments?post=1748"}],"version-history":[{"count":64,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/posts\/1748\/revisions"}],"predecessor-version":[{"id":1826,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/posts\/1748\/revisions\/1826"}],"wp:featuredmedia":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/media\/1827"}],"wp:attachment":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/media?parent=1748"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/categories?post=1748"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/tags?post=1748"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}