{"id":256,"date":"2022-05-16T17:56:59","date_gmt":"2022-05-16T15:56:59","guid":{"rendered":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/?p=256"},"modified":"2022-05-16T17:56:59","modified_gmt":"2022-05-16T15:56:59","slug":"algorithmes-k-nn","status":"publish","type":"post","link":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/?p=256","title":{"rendered":"Algorithmes k-nn."},"content":{"rendered":"\n<p>Le<strong> k-NN<\/strong> est le diminutif de <strong><em>k Nearest Neighbors<\/em><\/strong>. Le<strong> k-NN<\/strong> est un algorithme servant autant pour la classification que pour la r\u00e9gression. <strong><em>Nearest Neighbors<\/em><\/strong> signifie en fran\u00e7ais \u00ab\u00a0plus proches voisins, voisins les plus proches\u00a0\u00bb car le principe de ce mod\u00e8le consiste en effet \u00e0 choisir les<strong> k<\/strong> donn\u00e9es les plus proches du point \u00e9tudi\u00e9 afin d&rsquo;en pr\u00e9dire sa valeur.<\/p>\n\n\n\n<p>Exemple du fonctionnement de cet algorithme :<\/p>\n\n\n\n<p>Ci-dessous est  repr\u00e9sent\u00e9 un jeu de donn\u00e9es d\u2019entra\u00eenement avec deux classes, la classe rouge et la classe bleu. L&rsquo;<strong><em>input<\/em> <\/strong><em>(entr\u00e9e, saisie)\u00a0<\/em>est donc\u00a0<strong><em>bidimensionnel<\/em> <\/strong><em>(\u00e0 deux dimensions)\u00a0<\/em>ici, et la\u00a0<em><strong>target<\/strong><\/em> <em>(cible)<\/em>\u00a0est la couleur \u00e0 classer.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" width=\"567\" height=\"382\" src=\"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/wp-content\/uploads\/sites\/16\/2022\/05\/image-5.png\" alt=\"\" class=\"wp-image-257\" srcset=\"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/wp-content\/uploads\/sites\/16\/2022\/05\/image-5.png 567w, http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/wp-content\/uploads\/sites\/16\/2022\/05\/image-5-300x202.png 300w\" sizes=\"(max-width: 567px) 100vw, 567px\" \/><\/figure>\n\n\n\n<p>Si l&rsquo;on a une nouvelle entr\u00e9e dont on veut pr\u00e9dire la classe, comment pourrait-on faire ?<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" width=\"518\" height=\"381\" src=\"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/wp-content\/uploads\/sites\/16\/2022\/05\/image-6.png\" alt=\"\" class=\"wp-image-258\" srcset=\"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/wp-content\/uploads\/sites\/16\/2022\/05\/image-6.png 518w, http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/wp-content\/uploads\/sites\/16\/2022\/05\/image-6-300x221.png 300w\" sizes=\"(max-width: 518px) 100vw, 518px\" \/><\/figure>\n\n\n\n<p>Il suffit simplement de regarder les\u00a0<strong>k<\/strong>\u00a0voisins (ici, les points) les plus proches du point \u00e9tudi\u00e9 et de regarder quelle classe constitue la majorit\u00e9 de ces points, afin d&rsquo;en d\u00e9duire la classe (rouge ou bleu) du nouveau point. Par exemple, ici, si on utilise le 5-NN, on peut pr\u00e9dire que le nouveau point appartient \u00e0 la classe\u00a0<strong>rouge<\/strong>\u00a0puisqu&rsquo;elle poss\u00e8de 3 points rouges et 2  points bleus\u00a0dans son entourage.\u00a0<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" width=\"521\" height=\"385\" src=\"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/wp-content\/uploads\/sites\/16\/2022\/05\/image-7.png\" alt=\"\" class=\"wp-image-259\" srcset=\"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/wp-content\/uploads\/sites\/16\/2022\/05\/image-7.png 521w, http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/wp-content\/uploads\/sites\/16\/2022\/05\/image-7-300x222.png 300w\" sizes=\"(max-width: 521px) 100vw, 521px\" \/><\/figure>\n\n\n\n<p id=\"r-4090363\">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 (voir ci-dessous).<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" width=\"566\" height=\"416\" src=\"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/wp-content\/uploads\/sites\/16\/2022\/05\/image-8.png\" alt=\"\" class=\"wp-image-260\" srcset=\"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/wp-content\/uploads\/sites\/16\/2022\/05\/image-8.png 566w, http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/wp-content\/uploads\/sites\/16\/2022\/05\/image-8-300x220.png 300w\" sizes=\"(max-width: 566px) 100vw, 566px\" \/><\/figure>\n\n\n\n<p>Utilisation de<strong> k-NN<\/strong> sur un jeu de donn\u00e9es.<\/p>\n\n\n\n<p>Premi\u00e8rement, voici une br\u00e8ve explication du jeu de donn\u00e9es utilis\u00e9 : ce jeu est un <em><strong>dataset<\/strong><\/em>\u00a0tr\u00e8s c\u00e9l\u00e8bre, appel\u00e9 <strong>MNIST<\/strong>.\u00a0Il est constitu\u00e9 d&rsquo;un ensemble de 70000\u00a0images 28&#215;28 pixels en noir et blanc annot\u00e9es du chiffre correspondant (entre 0\u00a0et 9). L&rsquo;objectif de ce jeu de donn\u00e9es \u00e9tait de permettre \u00e0 un ordinateur d&rsquo;apprendre \u00e0 reconna\u00eetre des nombres manuscrits automatiquement (pour lire des ch\u00e8ques par exemple). Ce <strong><em>dataset<\/em><\/strong> utilise des donn\u00e9es r\u00e9elles qui ont d\u00e9j\u00e0 \u00e9t\u00e9 pr\u00e9trait\u00e9es afin d&rsquo;\u00eatre plus facilement utilisables par un algorithme.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" width=\"491\" height=\"421\" src=\"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/wp-content\/uploads\/sites\/16\/2022\/05\/image-9.png\" alt=\"\" class=\"wp-image-261\" srcset=\"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/wp-content\/uploads\/sites\/16\/2022\/05\/image-9.png 491w, http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/wp-content\/uploads\/sites\/16\/2022\/05\/image-9-300x257.png 300w\" sizes=\"(max-width: 491px) 100vw, 491px\" \/><\/figure>\n\n\n\n<p>L&rsquo;objectif est donc d&rsquo;entra\u00eener un mod\u00e8le qui est capable de reconna\u00eetre les chiffres pr\u00e9sent sur ce type d&rsquo;images. Par chance, ce jeu de donn\u00e9es est t\u00e9l\u00e9chargeable directement \u00e0 partir d&rsquo;une fonction<strong><em> scikit-learn<\/em><\/strong>. \ud83d\ude07 On peut donc directement obtenir\u00a0ce <strong><em>dataset<\/em><\/strong> via un appel de fonction :<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" width=\"738\" height=\"53\" src=\"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/wp-content\/uploads\/sites\/16\/2022\/05\/image-10.png\" alt=\"\" class=\"wp-image-262\" srcset=\"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/wp-content\/uploads\/sites\/16\/2022\/05\/image-10.png 738w, http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/wp-content\/uploads\/sites\/16\/2022\/05\/image-10-300x22.png 300w\" sizes=\"(max-width: 738px) 100vw, 738px\" \/><\/figure>\n\n\n\n<p>Voici le code permettant d&rsquo;atteindre cet objectif :<\/p>\n\n\n\n<p><a href=\"https:\/\/colab.research.google.com\/drive\/1UVVeA-xdnacW80bJA5zRzck9ehOjN6Y-?usp=sharing\">https:\/\/colab.research.google.com\/drive\/1UVVeA-xdnacW80bJA5zRzck9ehOjN6Y-?usp=sharing<\/a><\/p>\n\n\n\n<p> <\/p>\n","protected":false},"excerpt":{"rendered":"<p>Le k-NN est le diminutif de k Nearest Neighbors. Le k-NN est un algorithme servant autant pour la classification que pour la r\u00e9gression. Nearest Neighbors signifie en fran\u00e7ais \u00ab\u00a0plus proches voisins, voisins les plus proches\u00a0\u00bb car le principe de ce mod\u00e8le consiste en effet \u00e0 choisir les k donn\u00e9es les plus proches du point \u00e9tudi\u00e9 [&hellip;]<\/p>\n","protected":false},"author":16,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/index.php?rest_route=\/wp\/v2\/posts\/256"}],"collection":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/index.php?rest_route=\/wp\/v2\/users\/16"}],"replies":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=256"}],"version-history":[{"count":1,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/index.php?rest_route=\/wp\/v2\/posts\/256\/revisions"}],"predecessor-version":[{"id":263,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/index.php?rest_route=\/wp\/v2\/posts\/256\/revisions\/263"}],"wp:attachment":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=256"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=256"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=256"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}