Premiere/Theme05_Algorithmique/07_Algorithme_KNN.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "emk6sw0OaVxc"
   },
   "source": [
    "# Méthode du K-Nearest-Neighbours (KNN), aka les k-plus-proches-voisins\n",
    "La méthode KNN est une méthode simple et efficace de classification. La classification est un enjeu majeur de l'Intelligence Artificielle :\n",
    "- la caméra d'une voiture autonome perçoit un panneau, mais quel est ce panneau ?\n",
    "- un grain de beauté est pris en photo par un dermatologue, ce grain de beauté est-il cancéreux ?\n",
    "- ...\n",
    "\n",
    "La méthode du KNN va trouver quels sont, dans une base de données déjà bien remplie et labellée, les k-objets (les 6 objets si $k=6$ par exemple) qui se rapprochent le plus de l'objet à classifier. En prenant ensuite la caractéristique la plus fréquente parmi ces 6 objets, on devine alors dans quelle catégorie notre objet doit se classer.\n",
    "\n",
    "\n",
    "![](data/picKNN.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "XRnszWrWYi6v"
   },
   "source": [
    "**Notre objectif :** \n",
    "Nous allons reprendre le jeu de données sur les joueurs du top14 utilisé ici https://github.com/glassus/nsi/blob/master/Premiere/Theme06_Traitement_de_donnees/03_Pandas_eleves.ipynb\n",
    "\n",
    "\n",
    "**Question :** si on croise une personne nous disant qu'elle veut jouer en top14, et qu'elle nous donne son poids et sa taille, peut-on lui prédire à quel poste elle devrait jouer ?\n",
    "\n",
    "Dans toute idée de classification il y a l'idée de **distance**. Il faut comprendre la distance comme une _mesure de la différence_. \n",
    "\n",
    "Comment mesurer la différence physique entre deux joueurs de rugby ? \n",
    "\n",
    "![](data/distAB.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "L9Yp-3USaVyY"
   },
   "outputs": [],
   "source": [
    "import pandas as pd #import du module pandas, abrégé classiquement par \"pd\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "W9JdmXZiaVzo"
   },
   "outputs": [],
   "source": [
    "df = pd.read_csv('data/top14.csv', encoding = 'utf-8')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "9CuiJUBAcIl-"
   },
   "source": [
    "### Résultat attendu :\n",
    "\n",
    "Il faut créer une fonction `knn()` qui prend en argument `poids` et `taille` , sont les caractéristiques du nouveau joueur. La fonction doit renvoyer une chaîne de caractère correspondant au poste auquel elle est susceptible de jouer.\n",
    "\n",
    "Exemple : \n",
    "\n",
    "![](data/knn2.png)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "4VCiIUUAdGqO"
   },
   "outputs": [],
   "source": [
    "def knn(poids, taille):\n",
    "  df['distance']=(df['Taille']-taille)**2+(df['Poids']-poids)**2\n",
    "  newdf = df.sort_values(by='distance', ascending=True)\n",
    "  newdftri = newdf.head(6) #on prend les 6 joueurs les plus proches physiquement\n",
    "  sol = newdftri['Poste'].describe().top\n",
    "  return sol"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 384
    },
    "colab_type": "code",
    "id": "w_Xs_ypE7aaL",
    "outputId": "192b7ce5-6d92-41a6-a9ad-33285b7fb09b"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Ailier'"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "knn(93,188)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "Ztrj7mab7cmv"
   },
   "source": [
    "## Influence du paramètre $k$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dans le code précédent, on a travaillé avec $k=6$ et c'est le poste majoritaire parmi les 6 joueurs les plus proches qui a été donné par l'algorithme.  \n",
    "Modifions légèrement la fonction `knn()` afin d'observer l'influence du paramètre $k$ sur la prédiction :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Centre\n",
      "Ailier\n",
      "Ailier\n",
      "Ailier\n",
      "Ailier\n",
      "Ailier\n",
      "Ailier\n",
      "Ailier\n",
      "Ailier\n",
      "Ailier\n",
      "Ailier\n",
      "Ailier\n",
      "Ailier\n",
      "Ailier\n",
      "Ailier\n",
      "Ailier\n",
      "Ailier\n",
      "Ailier\n",
      "Ailier\n"
     ]
    }
   ],
   "source": [
    "def knn(poids, taille, k):\n",
    "  df['distance']=(df['Taille']-taille)**2+(df['Poids']-poids)**2\n",
    "  newdf = df.sort_values(by='distance', ascending=True)\n",
    "  newdftri = newdf.head(k) #on prend les k joueurs les plus proches physiquement\n",
    "  sol = newdftri['Poste'].describe().top\n",
    "  return sol\n",
    "\n",
    "for k in range(1,20):\n",
    "    print(knn(93,188,k))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On s'aperçoit que la prédiction est très stable... sauf si $k=1$ !  \n",
    "Il se trouve qu'un joueur possède **exactement** ces caractéristiques physiques (Pierre-Louis BARASSI) et qu'il joue Centre :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Equipe</th>\n",
       "      <th>Nom</th>\n",
       "      <th>Poste</th>\n",
       "      <th>Date de naissance</th>\n",
       "      <th>Taille</th>\n",
       "      <th>Poids</th>\n",
       "      <th>distance</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>314</th>\n",
       "      <td>Lyon</td>\n",
       "      <td>Pierre-Louis BARASSI</td>\n",
       "      <td>Centre</td>\n",
       "      <td>22/04/1998</td>\n",
       "      <td>188</td>\n",
       "      <td>93</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>461</th>\n",
       "      <td>Pau</td>\n",
       "      <td>Vincent PINTO</td>\n",
       "      <td>Ailier</td>\n",
       "      <td>10/04/1999</td>\n",
       "      <td>187</td>\n",
       "      <td>93</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>527</th>\n",
       "      <td>Toulon</td>\n",
       "      <td>Stéphane ONAMBÉLÉ</td>\n",
       "      <td>3ème ligne</td>\n",
       "      <td>12/02/1993</td>\n",
       "      <td>188</td>\n",
       "      <td>94</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>202</th>\n",
       "      <td>Castres</td>\n",
       "      <td>Geoffrey PALIS</td>\n",
       "      <td>Arrière</td>\n",
       "      <td>08/07/1991</td>\n",
       "      <td>189</td>\n",
       "      <td>93</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>196</th>\n",
       "      <td>Castres</td>\n",
       "      <td>Armand BATLLE</td>\n",
       "      <td>Ailier</td>\n",
       "      <td>12/04/1987</td>\n",
       "      <td>188</td>\n",
       "      <td>92</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>585</th>\n",
       "      <td>Toulouse</td>\n",
       "      <td>Théo BELAN</td>\n",
       "      <td>Centre</td>\n",
       "      <td>15/11/1992</td>\n",
       "      <td>187</td>\n",
       "      <td>94</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>242</th>\n",
       "      <td>Clermont</td>\n",
       "      <td>Samuel EZEALA</td>\n",
       "      <td>Ailier</td>\n",
       "      <td>11/12/1999</td>\n",
       "      <td>187</td>\n",
       "      <td>94</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>502</th>\n",
       "      <td>Racing92</td>\n",
       "      <td>Simon ZEBO</td>\n",
       "      <td>Ailier</td>\n",
       "      <td>16/03/1990</td>\n",
       "      <td>187</td>\n",
       "      <td>94</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>133</th>\n",
       "      <td>Brive</td>\n",
       "      <td>Esteban ABADIE</td>\n",
       "      <td>3ème ligne</td>\n",
       "      <td>01/12/1997</td>\n",
       "      <td>188</td>\n",
       "      <td>95</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>369</th>\n",
       "      <td>Montpellier</td>\n",
       "      <td>Benjamin FALL</td>\n",
       "      <td>Arrière</td>\n",
       "      <td>03/03/1989</td>\n",
       "      <td>186</td>\n",
       "      <td>93</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "          Equipe                   Nom       Poste Date de naissance  Taille  \\\n",
       "314         Lyon  Pierre-Louis BARASSI      Centre        22/04/1998     188   \n",
       "461          Pau         Vincent PINTO      Ailier        10/04/1999     187   \n",
       "527       Toulon     Stéphane ONAMBÉLÉ  3ème ligne        12/02/1993     188   \n",
       "202      Castres        Geoffrey PALIS     Arrière        08/07/1991     189   \n",
       "196      Castres         Armand BATLLE      Ailier        12/04/1987     188   \n",
       "585     Toulouse            Théo BELAN      Centre        15/11/1992     187   \n",
       "242     Clermont         Samuel EZEALA      Ailier        11/12/1999     187   \n",
       "502     Racing92            Simon ZEBO      Ailier        16/03/1990     187   \n",
       "133        Brive        Esteban ABADIE  3ème ligne        01/12/1997     188   \n",
       "369  Montpellier         Benjamin FALL     Arrière        03/03/1989     186   \n",
       "\n",
       "     Poids  distance  \n",
       "314     93         0  \n",
       "461     93         1  \n",
       "527     94         1  \n",
       "202     93         1  \n",
       "196     92         1  \n",
       "585     94         2  \n",
       "242     94         2  \n",
       "502     94         2  \n",
       "133     95         4  \n",
       "369     93         4  "
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df['distance']=(df['Taille']-188)**2+(df['Poids']-93)**2\n",
    "newdf = df.sort_values(by='distance', ascending=True)\n",
    "newdf.head(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut s'apercevoir aussi que jusqu'à $k=5$, aucun poste n'est majoritaire : la prédiction pourrait aussi bien renvoyer Centre, 3ème ligne, ou Arrière. Ce n'est que grâce à l'ordre alphabétique que la réponse renvoyée est «Ailier». Par contre, dès que $k \\geqslant 5$, le poste d'Ailier est bien majoritaire parmi les $k$ plus proches voisins."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "PROF_KNN.ipynb",
   "provenance": []
  },
  "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.6.9"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}