{
 "metadata": {
  "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-final"
  },
  "orig_nbformat": 2,
  "kernelspec": {
   "name": "python37364bit201329ed7ee849b4a43ad7bb610f5989",
   "display_name": "Python 3.7.3 64-bit"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2,
 "cells": [
  {
   "source": [
    "# Algorithme des k plus proches voisins (KNN) : application aux Pokemons\n",
    "\n",
    "Ce notebook fait suite à la présentation **\"5- Apprentissage : l'algorithme des k plus  proches voisins\"** du cours d'algorithmique de 1ère NSI\n",
    "\n",
    "Dans le dossier *images*, il y a le fichier **'pokemons_knn.csv'** qui contient une série de pokemons de type 'Eau' ou de type 'Psy' ayant chacun des points de vie ou d'attaque spécifiques.\n",
    "\n",
    "On va reprendre le principe d'ouverture de fichier csv vu au paragraphe **\"2- Cas d'un fichier CSV\"** dans le cours de première NSI : **\"Traitement de données en tables\"**.\n",
    "\n",
    "Ce notebook va nous faire retravailler les **dictionnaires** (avoir son cours **\"Types construits\"** de première à portée de main pourra être utile...)\n",
    "\n",
    "**Travail préalable :**\n",
    "Pour pouvoir réaliser ce travail correctement, il est nécessaire de **connaître le délimiteur** ( ','  ';'  ':' ...) qui sépare les données dans ce fichier csv. Relire le document cité puis déterminer le délimiteur utilisé dans le fichier des pokemons.\n",
    "\n",
    "## 1 - **Fonction d'extraction des données :**\n",
    "La cellule ci-dessous permet de définir une fonction qui renvoie sous la forme d'une **liste de dictionnaires** l'ensemble des données présentes dans un fichier csv :\n",
    "\n"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import csv\n",
    "import os\n",
    "\n",
    "def extraction_csv(nom_fichier, delimiteur):\n",
    "    \"\"\" fonction qui extrait les données d'un fichier csv dans une liste de dictionnaires.\n",
    "    Chaque dictionnaire correspond à un \"enregistrement \"(=une ligne de données) du fichier csv\n",
    "    :param nom_fichier: (str) le nom du fichier (avec son chemin) à extraire\n",
    "    :param delimiteur: (str) le délimiteur \n",
    "    :return: (list) les données dans une liste de dictionnaires\n",
    "    \"\"\"\n",
    "\n",
    "    fichier = open(???, 'r') # ouverture du fichier en lecture\n",
    "\n",
    "    lecteur = list(csv.DictReader(fichier, delimiter=';'))\n",
    "    fichier.close()\n",
    "\n",
    "    liste_data = []                  # création d'une liste vide\n",
    "    for ligne in lecteur:          \n",
    "        liste_data.append(dict(ligne))    # ajout \" à la volée\" des dictionnaires représentant les      enregistrements de la table\n",
    "    return liste_data\n",
    "\n",
    "\n",
    "# on aura besoin régulièrement d'afficher notre jeu de données pour vérifier l'effet du code\n",
    "# on pourra utiliser la fonction définie ci-dessous :\n",
    "\n",
    "def affiche_data(jeu_data):\n",
    "    for elt in jeu_data:\n",
    "        print(elt)\n",
    "    print('*'*100)\n",
    "\n",
    "liste_pokemons = extraction_csv(???, ???)\n",
    "affiche_data(???)"
   ]
  },
  {
   "source": [
    "## 2 - Préparation des données récupérées :\n",
    "\n",
    "### 2.1- Analyser le type des données :\n",
    "\n",
    "L'affichage obtenu nous permet de \"visualiser\" le type des données **points de vie** ou **valeurs attaque**.\n",
    "Vérifier le type de **points de vie** ou de **valeurs attaque** en utilisant l'instruction qui convient  :"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# récupération du type de 'points de vie'\n",
    "print('type de la variable points de vie : ', type(liste_pokemons[0][???]))\n",
    "\n",
    "# récupération du type de 'valeur attaque'\n",
    "print('type de la variable valeur attaque : ', type(liste_pokemons[0][???]))\n"
   ]
  },
  {
   "source": [
    "### 2.2- Conversion des données en nommbre\n",
    "\n",
    "Pour faciliter le travail ultérieur sur les données, on va convertir les données  **points de vie** ou **valeurs attaque** en un format numérique adapté (int) puisque tous ces points de vie ou d'attaque sont des entiers.\n",
    "Remarque : la liste **liste_pokemons** sera modifiée (on ne recrée pas une nouvelle liste)"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for elt in liste_pokemons :\n",
    "    elt['points de vie'] = ???\n",
    "    elt['valeurs attaque'] = ???\n",
    "# vérifications :\n",
    "# récupération du type de 'points de vie'\n",
    "print('type de la variable points de vie : ', ???)\n",
    "\n",
    "# récupération du type de 'valeur attaque'\n",
    "print('type de la variable valeur attaque : ', ???)\n",
    "\n"
   ]
  },
  {
   "source": [
    "## 3 - Fonctions pour calculer la **\"distance\"** entre deux données\n",
    "\n",
    "### 3.1 - Distance euclidienne :\n",
    "\n",
    "\n",
    "\n"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math    # module nécessaire pour le calcul de la racine carrée\n",
    "\n",
    "def distance_euclidienne( pt1, pt2):\n",
    "    \"\"\" fonction qui renvoie la distance euclidienne entre deux points du plan\n",
    "    :param pt1: (tuple) un tuple de coordonnées '(x1, y1)' définissant le point pt1\n",
    "    :param pt2: (tuple) un tuple de coordonnées '(x2, y2)' définissant le point pt2\n",
    "    :return: (float) la distance euclidienne entre pt1 et pt2\n",
    "    Exemple :\n",
    "    >>> A = (2, 5)\n",
    "    >>> B = (3, 7)\n",
    "    >>> distance_euclidienne(A, B)\n",
    "    >>> 2.23606797749979\n",
    "    \"\"\"\n",
    "    return ???\n",
    "\n",
    "#test de la fonction :\n",
    "A = (2, 5)\n",
    "B = (3, 7)\n",
    "distance_euclidienne(???, ???)\n",
    "\n",
    "\n"
   ]
  },
  {
   "source": [
    "### 3.2 - Distance de Manhattan\n",
    "\n",
    "\n"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def distance_manhattan( pt1, pt2):\n",
    "    \"\"\" fonction qui renvoie la distance de Manhattan entre deux points du plan\n",
    "    :param pt1: (tuple) un tuple de coordonnées '(x1, y1)' définissant le point pt1\n",
    "    :param pt2: (tuple) un tuple de coordonnées '(x2, y2)' définissant le point pt2\n",
    "    :return: (int ou float) la distance euclidienne entre pt1 et pt2 (si les coordonnées de pt1 et pt2\n",
    "    sont de type int alors la fonction renvoie un int)\n",
    "    Exemple :\n",
    "    >>> A = (2, 5)\n",
    "    >>> B = (3, 7)\n",
    "    >>> distance_manhattan(A, B)\n",
    "    >>> 3\n",
    "    \"\"\"\n",
    "    return ???\n",
    "\n",
    "# test de la fonction\n",
    "A = (2, 5)\n",
    "B = (3, 7)\n",
    "distance_manhattan(???, ???)"
   ]
  },
  {
   "source": [
    "### 3.3 - Application aux Pokemons :\n",
    "\n",
    "On donne les deux dictionnaires correspondant à deux Pokemons :\n",
    "\n",
    "**{'nom': 'Poissoroy', 'points de vie': '80', 'valeurs attaque': '92', 'type': 'Eau'}**\n",
    "\n",
    "**{'nom': 'Clamiral', 'points de vie': '95', 'valeurs attaque': '100', 'type': 'Eau'}**\n",
    "\n",
    "On souhaite calculer la distance euclidienne puis la distance de Manhattan qui les sépare.\n",
    "On va dans un premier temps créer une fonction pour extraire d'un dictionnaire deux valeurs numériques :"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def extrait_coordo(dico, cle1, cle2):\n",
    "    \"\"\" fonction qui renvoie sous forme d'un tuple de coordonnées les deux valeurs numériques associées aux clés cle1 et cle2 du dictionnaire dico\n",
    "    :param dico: (dict) le dictionnaire\n",
    "    :param cle1: (str) une clé du dictionaire associée à une valeur numérique\n",
    "    :param cle2: (str) une clé du dictionaire associée à une valeur numérique\n",
    "    :return: (tuple) valeur1, valeur2 associées à cle1 et cle2\n",
    "    :CU: on suppose que les valeurs numériques sont des entiers (int)\n",
    "    Exemple :\n",
    "    >>> pk1 =  {'nom': 'Poissoroy', 'points de vie': 80, 'valeurs attaque': 92, 'type': 'Eau'}\n",
    "    >>> extrait_coordo(pk1, 'points de vie', 'valeurs attaque')\n",
    "    >>> (80, 92)\n",
    "    \"\"\"\n",
    "    return (???, ???)\n",
    "\n",
    "# test de la fonction :\n",
    "pk1 = {'nom': 'Poissoroy', 'points de vie': 80, 'valeurs attaque': 92, 'type': 'Eau'}\n",
    "print(extrait_coordo(???, ???, ???'))\n",
    "\n"
   ]
  },
  {
   "source": [
    "On peut maintenant utiliser les fonctions **extrait_coordo()**, **distance_euclidienne()** et **distance_manhattan()** pour calculer les deux types de \"distances\" qui séparent les deux Pokemons pris en exemple :"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pk1 = {'nom': 'Poissoroy', 'points de vie': 80, 'valeurs attaque': 92, 'type': 'Eau'}\n",
    "pk2 = {'nom': 'Clamiral', 'points de vie': 95, 'valeurs attaque': 100, 'type': 'Eau'}\n",
    "\n",
    "print('distance euclidienne entre pk1 et pk2 :', distance_euclidienne(extrait_coordo(pk1, 'points de vie', 'valeurs attaque'), extrait_coordo(pk2, 'points de vie', 'valeurs attaque')))\n",
    "print('')\n",
    "print('distance de Manhattan entre pk1 et pk2 :', distance_manhattan(extrait_coordo(pk1, 'points de vie', 'valeurs attaque'), extrait_coordo(pk2, 'points de vie', 'valeurs attaque')))"
   ]
  },
  {
   "source": [
    "## 4 - Mise en oeuvre de l'algorithme KNN\n",
    "\n",
    "\n",
    "Un Pokémon inconnu vient d’être découvert : il a 65 points de vie et 60 points d’attaque. On l’appellera pokemon_mystere : ce sera la donnée cible dont on devra estimer l'attribut **type** par algorithme).\n",
    "\n",
    "### 4.1 - Calcul de la distance euclidienne entre le pokemon mystere et chacun des pokemons connus\n",
    "\n",
    "Dans un premier temps, on va devoir ajouter **à chacun** des dictionnaires de la liste **liste_pokemons** un couple **clé / valeur** donnant la \"distance\" existant entre ce pokemon et le pokemon mystere (la donnée cible). La clé sera nommée : 'distance_cible'. \n",
    "La valeur associée à cette clé sera la distance calculée par la fonction **distance_euclidienne()**\n",
    "\n",
    "Exemple de résultat d'affichage obtenu pour un pokemon :\n",
    "\n",
    "{'nom': 'Ecayon', 'points de vie': 49, 'valeurs attaque': 49, 'type': 'Eau', **'distance_cible': 19.4164878389476**}\n",
    "\n",
    "\n"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pokemon_mystere = {'points de vie': 65, 'valeurs attaque': 60}\n",
    "for elt in liste_pokemons:\n",
    "    # ajout dans le dictionnaire de l'entrée distance cible calculée avec la distance euclidienne :\n",
    "    elt['distance_cible'] = distance_euclidienne(???, ???)\n",
    "\n",
    "# vérification par affichage du jeu de données complet que chaque dictionnaire\n",
    "# a bien un nouveau couple clé/valeur :\n",
    "affiche_data(liste_pokemons)"
   ]
  },
  {
   "source": [
    "### 4.2 - Estimation \"manuelle\" du type du pokemon mystère :\n",
    "\n",
    "On propose :\n",
    "\n",
    " 1- de trier la liste **liste_pokemons** par **ordre croissant** de la valeur **distance_cible** calculée : **on réutilisera la fonction de tri par sélection** écrite dans le cours d'algorithmique de première NSI, mais en **l'adaptant pour qu'elle puisse s'appliquer sur une liste de dictionnaires dont l'une des paires clé/valeur servira de critère de tri !** \n",
    "\n",
    " 2- de choisir une valeur arbitraire k du nombre de voisins les plus proches du pokemon mystère\n",
    "\n",
    " 3- d'en déduire par simple observation le type le plus probable \n",
    "\n"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Remarque : la cellule précédente doit avoir été exécutée pour que les données de distance soient présentes dans les dictionnaires !\n",
    "def tri_select(jeu_data, cle):\n",
    "    \"\"\" réalise le tri par sélection de la liste de dictionnaires 'jeu_data'  sur le critère 'cle'\n",
    "    :param jeu_data: (list) la liste à trier\n",
    "    :param cle: (str) la clé du dictionnaire dont la valeur associée sert comme critère de tri\n",
    "    :return: la fonction ne renvoie rien : la liste est triée 'en place'\n",
    "    \"\"\"\n",
    "    for i in range(len(???)):\n",
    "        i_max = 0    # i_max:indice de la valeur maximum que l'on repère\n",
    "        #recherche du maximum dans le reste de la liste :\n",
    "        for j in range(1,len(???) -i):\n",
    "            if jeu_data[j][???] > jeu_data[???][cle]:\n",
    "                i_max = ???\n",
    "        # permutation(\"à la mode Python\"):\n",
    "        jeu_data[len(jeu_data)-i-1], jeu_data[i_max] =  ???\n",
    "    \n",
    "# test de la fonction de tri du jeu de données pokemons sur le critère 'distance_cible' :\n",
    "tri_select(???, ???)\n",
    "affiche_data(???)\n"
   ]
  },
  {
   "source": [
    "### 4.3 - Estimation automatique du type du pokemon mystère :\n",
    "\n",
    "Notre liste de pokemons étant triée, du voisin le plus \"proche\" au voisin le plus \"éloigné\" de notre pokemon mystère, on va devoir faire un travail statistique sur le type de ces plus proches voisins pour en déduire l'estimation la plus probable du type du pokemon mystère. \n",
    "On devra fournir au programme la valeur du nombre k de voisins sur lequel on veut faire notre travail statisitique.\n",
    "\n"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def type_cible(k, jeu_data, cle):\n",
    "    \"\"\" fonction qui renvoie l'estimation la plus probable pour la donné cible\n",
    "    :param k: (int) le nombre de voisins proches\n",
    "    :param jeu_data: (list) la liste ordonnée des dictionnaires de données\n",
    "    :param cle: (str) la clé associée à la valeur donnant le type de la donnée cible\n",
    "    :return: (tuple) type, probabilité (en %) de l'estimation de la donnée cible\n",
    "    le dictionnaire 'analyse' est local à cette fonction.\n",
    "    Exemple de résultat pour ce dictionnaire : {'Psy': 4, 'Eau': 2} (ici k = 6)\n",
    "    Le type 'Psy' est majoritaire : c'est alors le type estimé pour le pokemon mystère\n",
    "    La fonction renvoie sur cet exemple le tuple : ('Psy', 66,67)\n",
    "    \"\"\"\n",
    "    analyse = {}        # création d'un dictionnaire pour accueillir les résultats\n",
    "    for i in range(k):\n",
    "        if jeu_data[i][???] not in analyse:  \n",
    "            analyse[jeu_data[i][???]] = 1   \n",
    "        else:\n",
    "            analyse[jeu_data[i][???]] += 1\n",
    "    # on crée une liste des clés et une liste des valeurs associées du dictionnaire 'analyse' :\n",
    "    cles = list(analyse.???)         # exemple de résultat : ['Psy', 'Eau']\n",
    "    valeurs = list(analyse.???)    # exemple de résultat: [2, 4]\n",
    "\n",
    "   return cles[valeurs.index(max(valeurs))], '{:.2f}'.format(max(???)/ ??? *100)\n",
    "\n",
    "     \n",
    "k = ???\n",
    "print(\"k = \", k, \"  \", type_cible(???, ???, ???))\n",
    "\n",
    "# proposer un code qui permet de travailler sur une gamme de différentes valeurs de k\n",
    "# et affiche le résultat de l'estimation de type avec le % de fiabilité :\n",
    "\n",
    "\n"
   ]
  },
  {
   "source": [
    "# 5- Ecriture du programme complet :\n",
    "\n",
    "Rassembler les éléments de programmation nécessaires à l'application de l'algorithme KNN sur un jeu de données présent dans un fichier csv.\n",
    "\n",
    "## Application de la distance euclidienne sur le jeu de données :\n",
    "\n",
    "Faire l'application sur les données pokemons en utilisant **la distance euclidienne** :\n"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# importations :\n",
    "???\n",
    "\n",
    "# définitions des fonctions utiles :\n",
    "????\n",
    "\n",
    "# code de l'application\n",
    "???\n"
   ]
  },
  {
   "source": [
    "## 5.2 - Application de la distance de Manhattan\n",
    "\n",
    "On souhaite reprendre cette estimation du type du pokemon mystère en appliquant cette fois **la distance de Manhattan** pour évaluer la \"distance\" entre le pokemon mystère et les autres pokemons connus.\n",
    "\n",
    "Dans la cellule ci-dessous reprendre en modifiant ce qui est nécessaire les codes des cellules précédentes :"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "???\n"
   ]
  },
  {
   "source": [
    "# 6- Prolongements possibles :\n",
    "\n",
    "Les deux applications précédentes sur le pokemon mystère  {'points de vie': 65, 'valeurs attaque': 60} avec un nombre de **plus proches voisins** égal à 6 donnent deux estimations différentes sur le type que pourrait avoir ce pokemon :\n",
    " - 66,7% de chance d'être de type 'Eau' avec la distance euclidienne\n",
    " - 66,7% de chance d'être de type 'Psy' avec la distance de Manhattan !!!\n",
    "\n",
    " On se trouve donc confronté au problème du **choix du modèle** pour le **calcul de distance** et au **choix du nombre k de voisins** pour faire la **\"meilleure estimation possible\"**.\n",
    "\n",
    " Le prolongement de cette activité consisterait à réaliser des jeux de tests de l'algoritthme KNN sur les pokemons existants (car on connaît leur type) et de chercher quel est le meilleur choix :\n",
    "  - pour k \n",
    "  - et pour le calcul de distance\n",
    "\n",
    "  choix qui aboutirait alors à une estimation qui redonnerait (le plus souvent possible) un **type estimé identique au type réel** du pokemon\n",
    "\n",
    "  Autre prolongement de type projet :\n",
    "   - une interface graphique qui permet d'aller chercher un fichier csv en un endroit quelconque du disque dur\n",
    "   - des widgets d'entrée pour définir les données à analyser, les données cibles..., et widget(s) de sortie pour afficher le résultat de l'estimation\n",
    "   \n",
    "\n",
    " "
   ],
   "cell_type": "markdown",
   "metadata": {}
  }
 ]
}