NSI1_25a_knn_Intro-Correction.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"width:100%;border-collapse:separate;border:solid 2px;border-radius:14px;\">\n",
    "    <div style=\"display:flex;\">\n",
    "        <div style=\"display:inline;width:5%;\"></div>\n",
    "        <div style=\"display:inline;width:15%;\">NSI1</div>\n",
    "        <div style=\"display:inline;width:15%;\">25a</div>\n",
    "        <div style=\"display:inline;width:70%;text-align:right;\"><b>Algorithmique</b></div>\n",
    "        <div style=\"display:inline;width:5%;\"></div>\n",
    "    </div>\n",
    "    <div  style=\"display: flex;background-color:#EEE\">\n",
    "        <p style=\"width:100%;text-align:center;\">Algorithme des k plus proches voisins</p>\n",
    "    </div>\n",
    "    <div  style=\"display: flex;\">\n",
    "        <p style=\"width:100%;text-align:center;\">Introduction au k-nn</p>\n",
    "    </div>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class = \"alert alert-success\">\n",
    "    \n",
    "**Objectifs de la séquence:**  \n",
    "Initiation à un algorithme d'apprentissage: Une approche de l'intelligence artificelle.    \n",
    "Prédire la classe d’un élément."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class = \"alert alert-info\">\n",
    "    \n",
    "**Sommaire :**\n",
    "\n",
    "- <a href=#Experimentation>Expérimentation</a> \n",
    "- <a href=#Distance_euclidienne>Calcul de distance euclidienne</a> \n",
    "- <a href=#Suite>A suivre</a> "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "![Starting block](https://github.com/ebuonocore/NSI1_25_knn/blob/master/images/NSI1_25_prairie_2.jpg?raw=true)\n",
    "<span style=\"font-family:Comic Sans MS; color:gray; font-size: x-small;float:right \">Source: \n",
    "<a href =\"https://pxhere.com/fr/photo/490090\">pxhere.com</a></span> \n",
    "\n",
    "<div id=\"Experimentation\"></div>\n",
    "\n",
    "# Expérimentation\n",
    "\n",
    "<div class = \"alert alert-success\">\n",
    "\n",
    "**Prédire l'avenir d'une fleur:**  \n",
    "Dans une prairie colonisée par des coquelicots et des bleuets, on se demande qu'elle va être la nature d'une fleur qui doit éclore.  \n",
    "Rendez-vous sur le site http://link.dgpad.net/XHHH  \n",
    "Vous allez répondre à une série de 10 questions.  \n",
    "Faites les 5 premières intuitivement, puis essayez de vous demander sur quoi vous vous basez pour faire votre choix.   \n",
    "    \n",
    "Est-ce que votre choix répond à des critères, un algorithme?  </div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q1.** Dans la case ci-dessous, expliquez comment vous procédez pour faire votre choix."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Je me base sur la couleur des fleurs voisines.  \n",
    "Si je suis dans une zone où il y a une majorité de coquelicot, je choisit un coquelicot."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q2.** Votre stratégie est elle infaillible ? Pourquoi ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Non, j'ai fait une erreur à la question 7.  Mais ce bleuet était vraiment perdu au milieu d'un tas de coquelicots. La probabilité paraissait très faible, mais il faut reconnaître que cela restait possible. (Pas de chance)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class = \"alert alert-success\">\n",
    "    \n",
    "k désigne un entier.\n",
    "L'idée de l'algorithme des k plus proches, aussi appelé **k-nn** pour k-nearest neighbors, consiste à estimer la nature d'un élément en tenant compte de la classe la plus représentée parmi les k voisins connus.</div> \n",
    "\n",
    "Par exemple, l'algorithme des 5-nn consiste à choisir la nature de la fleur en fonction des 5 plus proches voisines: Si, parmi les 5 voisines, il y a une majorité de coquelicots, on va postuler pour un coquelicot.\n",
    "\n",
    "![Exemple 5-nn](https://github.com/ebuonocore/NSI1_25_knn/blob/master/images/NSI1_25_exemple1_5nn.jpg?raw=true)\n",
    "\n",
    "<div id=\"Calcul de distance euclidienne\"></div>\n",
    "\n",
    "# Calcul de distance euclidienne\n",
    "\n",
    "Il est donc nécessaire de savoir calculer les distances entre des points pour réaliser cet algorithme.\n",
    "\n",
    "**Q4.** Soit A et B, deux p-uplets de flottants représentants les coordonnées de deux points: A(xa,ya) et B(xb,yb).\n",
    "La fonction **distance(A,B)** renvoie la distance euclidienne entre ces deux points.\n",
    "$$\\sqrt{(xb-xa)^2 + (yb-ya)^2}$$\n",
    "\n",
    "Donnez le programme de cette fonction:\n",
    "\n",
    "Remarque: Nous avions déjà programmé cette fonction dans l'activité 16 sur les p-uplets:\n",
    "https://mybinder.org/v2/gh/ebuonocore/NSI1_16_Tuples/master"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import sqrt\n",
    "def distance (A,B):\n",
    "    \"\"\" tuple * tuple -> float\n",
    "    Préconditions: A et B sont des couples de flottants représentants les coordonnées des points\n",
    "    Renvoie la distance entre A et B\n",
    "    \"\"\"\n",
    "    xa = A [0] # xa et ya prennent les valeurs de l'abscisse et de l'ordonéne de A\n",
    "    ya = A [1] \n",
    "    xb = B [0]\n",
    "    yb = B [1]\n",
    "    return sqrt((xb-xa)**2+(yb-ya)**2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre définition de la fonction distance() doit passer les assertions suivantes\n",
    "assert (distance((0,0),(0,2)) == 2.0)\n",
    "assert (distance((0,0),(-1,0)) == 1.0)\n",
    "assert (distance((0,0),(3,4)) == 5.0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div id=\"Suite\"></div>\n",
    "\n",
    "# A suivre  \n",
    "\n",
    "La prochaine fois, il nous restera à:  \n",
    "- trier tous les voisins en fonction de leur distance par rapport au point de référence.  \n",
    "- trouver la classe majoritaire parmi les k plus proches voisins.  \n",
    "\n",
    "Nous verrons ensuite quels applications nous pouvons faire de cette approche que l'on peut ranger dans le domaine des algorithmes d'apprentissage en intelligence artificielle."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "<p style=\"font-family:Comic Sans MS; text-align: center; color:gray; font-size: x-small; \">- Eric Buonocore. Mai 2020 -</p>\n",
    "\n",
    "![Licence CC BY NC SA](https://licensebuttons.net/l/by-nc-sa/3.0/88x31.png)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}