TP12 - Algorithme KNN.ipynb

{"cells":[{"metadata":{},"cell_type":"markdown","source":"<h1 style=\"font-size: 30px; text-align: center;\">TP12 - Algorithme des k plus proches voisins</h1>"},{"metadata":{},"cell_type":"markdown","source":"> Abrégé **kppv** en français. En anglais, on dit *k nearest neighbors* souvent abrégé **knn**.\n\nL’**algorithme des k plus proches voisins** appartient à la famille des algorithmes d’*apprentissage automatique* (machine learning) qui constituent le poumon de l'intelligence artificielle actuellement.\n\nPour simplifier, l'apprentissage automatique part souvent de données (data) et essaye de dire quelque chose des données qui n'ont pas encore été vues : il s'agit de *généraliser*, de *prédire*.\n\nOn va utiliser l'algorithme des k plus proches voisins pour résoudre un *problème de classification* : prédire la classe d'une donnée *inconnue* à partir de la classe des données connues.\n\nAvant de décrire cet algorithme, introduisons la situation et le problème."},{"metadata":{},"cell_type":"markdown","source":"# Présentation d'un problème de classification\n\n## Le jeu de données sur les Pokémons\n\n<img src=\"https://cdn.pixabay.com/photo/2020/07/21/16/10/pokemon-5426712_960_720.png\" alt=\"pokeball\" width=\"125\">\n\nOn dispose de données sur 34 Pokémons : leur type (Psy ou Eau), leur points de vie et la valeur de leurs attaques.\n\nCes données sont stockées dans le fichier CSV `pokemons.csv` que l'on s'empresse d'importer dans un tableau de dictionnaires appelé `pokemons`:"},{"metadata":{"trusted":false},"cell_type":"code","source":"import csv\nfichier = open('pokemons.csv', 'r', encoding = 'UTF-8')\nt = csv.DictReader(fichier, delimiter=';')\npokemons = [dict(ligne) for ligne in t]  # création et construction du tableau par compréhension\nfichier.close()\n\npokemons  # pour voir les données importées","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"On peut représenter ces données graphiquement dans un repère orthonormé, avec les valeurs d'attaque en abscisses et les points de vie en ordonnées. Les Pokémons de type \"Eau\" sont représentés pas les triangles bleus, et ceux de type \"Psy\" par les points rouges.\n\n![graphique](https://github.com/profvdd/PremNSI2021/blob/main/pokemons.png?raw=true)\n\n>C'est ce que vous allez faire par la suite !"},{"metadata":{},"cell_type":"markdown","source":"## Problème : peut-on prédire le type d'un nouveau Pokémon inconnu ?\n\nOn considère maintenant que l'on possède des données sur un nouveau Pokémon inconnu et on aimerait prédire s'il s'agit d'un Pokémon de type \"Eau\" ou de type \"Psy\".\n\n\n![graphique](https://github.com/profvdd/PremNSI2021/blob/main/methodeKPPV.png?raw=true)\n\nCe problème, qui demande à prédire à quelle catégorie, ou *classe*, appartient ce nouvel élément donné, est appelé *problème de classification*. L'algorithme des k plus proches voisins permet de trouver les k voisins les plus proches de ce nouvel élément dans le but de lui associer une *classe* plausible (Psy ou Eau, dans cet exemple). Par exemple, si k = 5 va chercher les 5 voisins les plus proches."},{"metadata":{},"cell_type":"markdown","source":"# Algorithme des knn\n\n## Énoncé et spécification\n\nÀ partir d'un jeu de données `donnees` (par exemple, les données sur nos 34 Pokémons) et d'une donnée cible `cible` (le nouveau Pokemon à classifier), l'algorithme de $k$ plus proches voisins doit déterminer les $k$ données les plus proches de la cible.\n\nPlus précisément, la spécification de l'algorithme des kppv est la suivante :\n\n- **Entrées** : \n    - une table `donnees` de taille n contenant les données et leurs classes\n    - une donnée cible : `cible`\n    - un nombre `k`\n    - une règle permettant de calculer la *distance* entre deux données\n- **Sortie** : une table `k_plus_proches_voisins`\n- **Rôle** : trouver les `k` données les plus proches de `cible` parmi celles de la table `donnees` (\"plus proches\" au sens de la distance définie au départ) \n- **Précondition** : $n \\geq 1$ et $k <= n$.\n- **Postcondition** : `k_plus_proches_voisins` contient les k plus proches voisins de `cible` parmi les données de la table `donnees`\n\n## Algorithme\n\nL'algorithme *naif* des *knn* s'exprime de manière simple :\n\n1. Créer une table `distances_voisins` contenant les éléments de la table `donnees` et leurs distances avec la donnée `cible`.  \n2. Trier les données de la table `distances_voisins` selon la distance croissante avec la donnée `cible`\n3. Renvoyer les `k` premiers éléments de cette table triée (`k_plus_proches_voisins`)"},{"metadata":{},"cell_type":"markdown","source":"# Implémentation de l'algorithme\n\nL'algorithme des plus proches voisins repose presque entièrement sur la *distance* entre deux données. Il faut donc commencer par définir une distance entre deux données.\n\n## Étape 0 : Choix et implémentation de la distance\n\nDans la suite, on va choisir la distance \"naturelle\", c'est-à-dire celle \"à vol d'oiseau\". On parle de *distance euclidienne*.\n\nDans un repère orthonormé, si $A$ et $B$ ont pour coordonnées respectives $(x_A, y_A)$ et $(x_B, y_B)$ alors la distance (euclidienne) entre ces deux points est donnée par la formule :\n\n$$\\text{distance}(A, B) = \\sqrt{(x_B-x_A)^2 + (y_B-y_A)^2}.$$ \n\n>**Important**: Sachez cependant qu'il existe d'autres distances possibles et que le choix de la distance n'est pas anodin car ce choix peut aboutir à trouver des voisins les plus proches différents et donc conduire à des prédictions différentes."},{"metadata":{},"cell_type":"markdown","source":"Dans notre cas, chaque Pokémon possède une abscisse égale à sa valeur d'attaque et une ordonnée égale à ses points de vie. Ainsi, la formule de la distance entre deux pokémons `d1` et `d2` se traduit ainsi :\n\n$$\\text{distance}(\\text{d1}, \\text{d2}) = \\sqrt{(\\text{valeur d'attaque de d2}-\\text{valeur d'attaque de d1})^2 + (\\text{points de vie de d2}-\\text{points de vie de d1})^2}.$$ \n\n✍️ **Question 1** : Calculez à la main la distance entre les deux Pokémons suivants.\n\n```python\np1 = {'Nom': 'Aligatueur', 'Type': 'Eau', 'Points de vie': '85', 'Attaque': '105'}\np2 = {'Nom': 'Bargantua', 'Type': 'Eau', 'Points de vie': '70', 'Attaque': '92'}\n```"},{"metadata":{},"cell_type":"markdown","source":"Votre réponse ici :"},{"metadata":{},"cell_type":"markdown","source":"💻 **Question 2** : Écrivez les instructions permettant d'accéder :\n- à la valeur d'attaque de `p1`\n- au points de vie de `p2`"},{"metadata":{"trusted":false},"cell_type":"code","source":"p1 = {'Nom': 'Aligatueur', 'Type': 'Eau', 'Points de vie': '85', 'Attaque': '105'}\np2 = {'Nom': 'inconnu', 'Type': 'inconnu', 'Points de vie': '92', 'Attaque': '127'}","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"# Instruction pour obtenir la valeur d'attaque de p1 :\n","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"# Instruction pour obtenir les points de vie de p2 :\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"💻 **Question 3** : Complétez la fonction `distance_euclidienne(d1, d2)` suivante qui renvoie la distance euclidienne entre deux Pokémons `d1` et `d2`. \n\n>⚠️ Il faut bien veiller à convertir les valeurs d'attaque et les points de vie en des nombres pour faire les calculs !"},{"metadata":{"trusted":false},"cell_type":"code","source":"# à vous de jouer !\nfrom math import sqrt  # pour utiliser la racine carrée\n\ndef distance_euclidienne(d1, d2):\n    x1 = ...  # abscisse de la donnée 1\n    y1 = ...  # ordonnée de la donnée 1\n    x2 = ...  # abscisse de la donnée 2\n    y2 = ...  # ordonnée de la donnée 2\n    return sqrt(...)  # formule donnant la distance euclidienne","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"💻 **Question 4** : Appelez cette fonction pour vérifier votre réponse à la question 1."},{"metadata":{"trusted":false},"cell_type":"code","source":"# à vous de jouer !\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## Étape 1 : Création de la table avec les distances\n\nMaintenant que notre distance est définie, on peut passer à l'implémentation de l'algorithme. On va donc commencer par créer la table `distances_voisins` contenant les distances entre toutes nos données et la donnée `cible`.\n\nOn choisit de reprendre les dictionnaires de la table `pokemons` en leur ajoutant une clé correspondant à la distance avec la cible. Par exemple, le premier élément de `distances_voisins` sera un dictionnaire de la forme\n\n```python\n{'Nom': 'Aligatueur', 'Type': 'Eau', 'Points de vie': '85', 'Attaque': '105', 'distance': dist}\n```\n\ndans lequel `dist` est la distance à calculer entre le Pokémon  `'Aligatueur'` et la cible.\n\n💻 **Question 5** : Écrivez une fonction `table_avec_distances(donnees, cible)` qui renvoie la table `distances_voisins` contenant les éléments de la table `donnees` auxquels on a ajouté la clé `distance` dont la valeur est leur distance avec la donnée `cible`.\n\n*Exemple*: Si `cible = {'Nom': 'inconnu', 'Type': 'inconnu', 'Points de vie': '92', 'Attaque': '127'}` alors l'appel `table_avec_distances(pokemons, cible)` renvoie le tableau dont le début est le suivant :\n\n```python\n[{'Nom': 'Aligatueur',\n  'Type': 'Eau',\n  'Points de vie': '85',\n  'Attaque': '105',\n  'distance': 23.08679276123039},\n {'Nom': 'Bargantua',\n  'Type': 'Eau',\n  'Points de vie': '70',\n  'Attaque': '92',\n  'distance': 41.340053217188775},\n ...\n]\n```\n"},{"metadata":{"trusted":false},"cell_type":"code","source":"def table_avec_distances(donnees, cible):\n    # à vous de jouer !\n    \n\n\n\n# ESSAI\ncible = {'Nom': 'inconnu', 'Type': 'inconnu', 'Points de vie': '92', 'Attaque': '127'}\ndistances_voisins = table_avec_distances(pokemons, cible)\ndistances_voisins","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## Étape 2 : Tri de la table selon la distance croissante\n\nOn va maintenant trier notre table de la plus petite à la plus grande distance avec notre cible, soit du plus proche au plus éloigné des voisins. Pour cela, on va utiliser la fonction `sorted` .  \nOn rappelle pour cela l'aide ainsi qu'un exemple d'utilisation :"},{"metadata":{"trusted":false},"cell_type":"code","source":"help(sorted)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"Création d'une fonction qui renvoie le nombre de Points de vie d'un pokemon"},{"metadata":{"trusted":false},"cell_type":"code","source":"def ptsdevie(pokemon):\n    \"\"\"pokemon est un dictionnaire possédant une clé \"Points de vie\".\"\"\"\n    return int(pokemon[\"Points de vie\"])","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"Puis on applique `sorted()` pour trier la liste par ordre croissant des points de vie"},{"metadata":{"trusted":false},"cell_type":"code","source":"pokemons_ordre_alphabetique = sorted(pokemons, key=ptsdevie)\npokemons_ordre_alphabetique","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"💻 **Question 6** : Créer d'abord une fonction `tri_distance(d)` qui servira de clé à notre tri."},{"metadata":{"trusted":false},"cell_type":"code","source":"# à vous de jouer !\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"💻 **Question 7** : Utilisez maintenant la fonction `sorted` pour créer une *nouvelle table* `distances_voisins_triee` contenant les données de `distances_voisins` triés par ordre croissant de distance."},{"metadata":{"trusted":false},"cell_type":"code","source":"cible = {'Nom': 'inconnu', 'Type': 'inconnu', 'Points de vie': '92', 'Attaque': '127'}\ndistances_voisins = table_avec_distances(pokemons, cible)\n\n# à vous de jouer !\n\n\n\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## Étape 3 : Détermination des k plus proches voisins\n\nLe plus dur est fait, il ne reste plus qu'à construire la table `k_plus_proches_voisins` contenant les k plus proches voisins. Comme la table `distances_voisins_triee` contient les voisins du plus proches au plus éloigné, il suffit de conserver les k premiers éléments de cette table !\n\n💻 **Question 8** : Écrivez une fonction `conserve_k_premiers(k, table)` qui renvoie une nouvelle table contenant les `k` premiers éléments de la table `table` (où `k` est un entier positif inférieur ou égale à `len(table)`)."},{"metadata":{"trusted":false},"cell_type":"code","source":"# à vous de jouer !\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"💻 **Question 9** : Vérifiez qu'en appelant cette fonction avec k = 3 et `table` = `distances_voisins_triee` vous obtenez bien les 3 premiers éléments de `distances_voisins_triee`."},{"metadata":{"trusted":false},"cell_type":"code","source":"# à vous de jouer !\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## Bilan\n\nOn peut maintenant regrouper tout ce qui vient d'être fait pour chaque étape pour écrire une fonction `kppv(donnees, cible, k)` qui renvoie les `k` plus proches voisins de `cible` dans `donnees`.\n\n💻 **Question 10** : Complétez la fonction `kppv(donnees, cible, k)` suivante qui renvoie les `k` plus proches voisins de `cible` dans `donnees`."},{"metadata":{"trusted":false},"cell_type":"code","source":"# RECOPIE DES FONCTIONS UTILES :\n\nfrom math import sqrt\n# Calcul de la distance\ndef distance_euclidienne(d1, d2):\n    # recopiez le code écrit à la question 3\n    pass\n\n# Fonction qui calcule et ajoute la distance entre la cible et chacune des données\ndef table_avec_distances(donnees, cible):\n    # recopiez le code écrit à la question 5\n    pass\n\n# Clé du tri\ndef tri_distance(d):\n    # recopiez le code écrit à la question 6\n    pass\n    \n\n    \n# À COMPLÉTER :\n\ndef kppv(donnees, cible, k):    \n    # étape 1 : création de la table avec les distances\n    distances_voisins = ...\n    \n    # étape 2 : tri par distance croissante\n    distances_voisins_triee = ...\n    \n    # étape 3 : récupération de k plus proches voisins\n    k_plus_proches_voisins = ...\n    \n    return ...\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"💻 **Question 11** : Appelez la fonction la fonction `kppv` pour connaître les 3 plus proches voisins de notre cible `{'Nom': 'inconnu', 'Type': 'inconnu', 'Points de vie': '92', 'Attaque': '127'}`. "},{"metadata":{"trusted":false},"cell_type":"code","source":"cible = {'Nom': 'inconnu', 'Type': 'inconnu', 'Points de vie': '92', 'Attaque': '127'}\n# à vous de jouer !\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"💻 **Question 12** : Même question pour les 5 plus proches voisins puis pour les 9 plus proches voisins."},{"metadata":{"trusted":false},"cell_type":"code","source":"# à vous de jouer !\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Et notre prédiction alors ?\n\n\n![boule_data](https://github.com/profvdd/PremNSI2021/blob/main/bigdata300.png?raw=true)\n\nL'algorithmes des knn en lui-même n'apporte pas la réponse à notre problème de classification puisqu'il ne fournit que les k plus proches voisins (et leurs classes) de notre donnée cible. Il reste donc une dernière étape pour prédire la classe de notre nouvel élément : pour cela, on choisit la *classe majoritaire* (la plus présente) dans les k plus proches voisins.\n\n> On est content si k est impair car il ne peut pas y avoir d'ex-aequo !"},{"metadata":{},"cell_type":"markdown","source":"✍️ **Question 13** : Donnez la classe majoritaire parmi les plus proches voisins lorsque k = 3, 5 puis 9. Pour chaque valeur de k, quelle serait la prédiction pour notre Pokémon cible inconnu ?"},{"metadata":{},"cell_type":"raw","source":"Réponse : \n"},{"metadata":{},"cell_type":"markdown","source":">**Moralité** : La valeur du paramètre `k` est importante car elle a une influence forte sur la prédiction. En pratique, elle doit être judicieusement choisie."},{"metadata":{},"cell_type":"markdown","source":"# Visualisation graphique\n\nOn peut utiliser le module `matplotlib` pour représenter graphiquement nos Pokémons, et observer graphiquement les plus proches voisins selon la valeur de `k` choisies.\n\nPour créer une nuage de points, il suffit d'utiliser la fonction `plot` qui prend en paramètres deux tableaux contenant respectivement la liste des abscisses et la liste des ordonnées des points à construire, ainsi qu'un paramètre permettant de définir le type de points et leur couleur :"},{"metadata":{"trusted":false},"cell_type":"code","source":"import matplotlib.pyplot as plt\n\nliste_abscisses = [0, 2, 5, 9, 7]  # tableau avec les abscisses\nliste_ordonnees = [5, 7, 12, 3, 8]  # tableau avec les ordonnées\n\nplt.plot(liste_abscisses, liste_ordonnees,'ro')  # r pour red, o pour un cercle\n\nplt.xlim(-2, 12)  # pour définir la fenêtre en abscisse\nplt.ylim(0, 14)  # pour définir la fenêtre en ordonnée\nplt.gca().set_aspect('equal', adjustable='box')  # pour que le repère soit orthonormé (même unité sur chaque axe)\n\nplt.show()  # affichage du graphique","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"Pour représenter nos Pokémons sous forme de nuages de points (valeur d'attaque en abscisse et points de vie en ordonnée), il suffit alors de créer un tableau contenant les abscisses (valeur d'attaque) et un tableau contenant les ordonnées (points de vie) puis d'utiliser la fonction `plot` pour construire les points.\n\nPour bien visualiser les deux classes, on va créer un nuage de points pour chaque classe : les Pokémons de type \"Eau\" seront représentés par des points bleus et les Pokémons \"Psy\" par des points rouges. On crée aussi le point correspondant à notre Pokémon cible en cyan :"},{"metadata":{"trusted":false},"cell_type":"code","source":"import matplotlib.pyplot as plt\n\n# construction des Pokémons de type 'Eau'\nvaleur_attaque_eau = [int(p['Attaque']) for p in pokemons if p['Type'] == 'Eau']  # tableau des abscisses\npoints_de_vie_eau = [int(p['Points de vie']) for p in pokemons if p['Type'] == 'Eau']  # tableau des orodonnées\nplt.plot(valeur_attaque_eau, points_de_vie_eau, 'bv')  # construction du graphique avec des triangles bleus\n\n# construction des Pokémons de type 'Psy'\nvaleur_attaque_psy = [int(p['Attaque']) for p in pokemons if p['Type'] == 'Psy']\npoints_de_vie_psy = [int(p['Points de vie']) for p in pokemons if p['Type'] == 'Psy']\nplt.plot(valeur_attaque_psy, points_de_vie_psy, 'ro')  # construction du graphique avec des cercles rouges\n\n# construction du Pokémon cible\ncible = {'Nom': 'inconnu', 'Type': 'inconnu', 'Points de vie': '92', 'Attaque': '127'}\nvaleur_attaque_cible = int(cible['Attaque'])\npoints_de_vie_cible = int(cible['Points de vie'])\nplt.plot(valeur_attaque_cible, points_de_vie_cible, 'cD')\n\n\n# Pour définir le titre, noms de axes et la légende\nplt.title(\"Pokémons\")\nplt.xlabel(\"Valeur d'attaque\")\nplt.ylabel(\"Points de vie\")\nplt.legend([\"Type Eau\", \"Type Psy\"], loc='upper center', bbox_to_anchor=(1.2, 0.8))\n\nplt.xlim(0, 200)\nplt.ylim(40, 120)\nplt.gca().set_aspect('equal', adjustable='box')\n\nplt.show()","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"💻 **Question 14** : Complétez ci-dessous le programme précédent pour construire également le nuage de points correspondant aux k plus plus proches voisins déterminés par notre algorithme. Vérifiez ensuite graphiquement pour différentes valeurs de k que les plus proches voisins sont les bons."},{"metadata":{"trusted":false},"cell_type":"code","source":"import matplotlib.pyplot as plt\n\n# construction des Pokémons de type 'Eau'\nvaleur_attaque_eau = [int(p['Attaque']) for p in pokemons if p['Type'] == 'Eau']  # tableau des abscisses\npoints_de_vie_eau = [int(p['Points de vie']) for p in pokemons if p['Type'] == 'Eau']  # tableau des orodonnées\nplt.plot(valeur_attaque_eau, points_de_vie_eau, 'bv')  # construction du graphique avec des triangles bleus\n\n# construction des Pokémons de type 'Psy'\nvaleur_attaque_psy = [int(p['Attaque']) for p in pokemons if p['Type'] == 'Psy']\npoints_de_vie_psy = [int(p['Points de vie']) for p in pokemons if p['Type'] == 'Psy']\nplt.plot(valeur_attaque_psy, points_de_vie_psy, 'ro')  # construction du graphique avec des cercles rouges\n\n# construction du Pokémon cible\ncible = {'Nom': 'inconnu', 'Type': 'inconnu', 'Points de vie': '92', 'Attaque': '127'}\nvaleur_attaque_cible = int(cible['Attaque'])\npoints_de_vie_cible = int(cible['Points de vie'])\nplt.plot(valeur_attaque_cible, points_de_vie_cible, 'cD')\n\n\n# construction des KPPV\n# À COMPLÉTER :\n\n\n\n\n\n# Pour définir le titre, noms de axes et la légende\nplt.title(\"Pokémons\")\nplt.xlabel(\"Valeur d'attaque\")\nplt.ylabel(\"Points de vie\")\nplt.legend([\"Type Eau\", \"Type Psy\"], loc='upper center', bbox_to_anchor=(1.2, 0.8))\n\nplt.xlim(0, 200)\nplt.ylim(40, 120)\nplt.gca().set_aspect('equal', adjustable='box')\n\nplt.show()","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Et si on change de distance ?\n\nOn a utilisé la distance euclidienne pour mesurer la distance entre nos données et la cible. C'est la distance \"naturelle\" mais il existe d'autres distances. Par exemple, la **distance de Manhattan** entre deux données $d_1(x_1, y_1)$ et $d_2(x_2, y_2)$ est définie ainsi $\\text{distance_manhattan}(d_1, d_2) = |x_2-x_1| + |y_2-y_1|$.\n\n>Article Wikipédia : [Distance de Manhattan](https://fr.wikipedia.org/wiki/Distance_de_Manhattan)\n\nOn peut modifier notre programme simplement en définissant et en utilisant cette nouvelle distance :"},{"metadata":{"trusted":false},"cell_type":"code","source":"# définition de la distance utilisée\ndef distance_manhattan(d1, d2):\n    x1 = float(d1['Attaque'])\n    y1 = float(d1['Points de vie'])\n    x2 = float(d2['Attaque'])\n    y2 = float(d2['Points de vie'])\n    return abs(x2-x1) + abs(y2-y1)  # abs est la fonction valeur absolue\n\ndef table_avec_distances(donnees, cible):\n    distances_voisins = [d for d in donnees]\n    for d in distances_voisins:\n        distance = distance_manhattan(d, cible)  # CHANGEMENT DE DISTANCE\n        d['distance'] = distance\n    return distances_voisins\n\ndef tri_distance(d):\n    return d['distance']\n\ndef kppv(donnees, cible, k):    \n    # étape 1 : création de la table avec les distances\n    distances_voisins = table_avec_distances(donnees, cible)    \n    # étape 2 : tri par distance croissante\n    distances_voisins_triee = sorted(distances_voisins, key=tri_distance)    \n    # étape 3 : récupération de k plus proches voisins\n    k_plus_proches_voisins = conserve_k_premiers(k, distances_voisins_triee)\n    \n    return k_plus_proches_voisins\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"En déterminant les 3 plus proches voisins on obtient :"},{"metadata":{"trusted":false},"cell_type":"code","source":"cible = {'Nom': 'inconnu', 'Type': 'inconnu', 'Points de vie': '92', 'Attaque': '127'}\nkppv(pokemons, cible, 3)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"Dans ce cas, pour k = 3, on prédirait que notre Pokémon inconnu est de type \"Eau\" (2 \"Eau\" contre 1 \"Psy\") et la prédiction serait l'inverse de celle utilisant la distance euclidienne !\n\n>**Moralité** : La distance utilisée a également toute son importance puisque son choix peut aboutir à des prédictions différentes. De plus, nous n'avons parlé ici que de distances *géométriques* s'appliquant à des données chiffrées. Toutes les données ne sont pas adaptées à ce type de distance : si on veut comparer la distance entre deux chaînes de caractères (dans le but de prédire la langue d'origine de certains mots par exemple) d'autres types de distances sont à considérer : *la distance de Hamming* ou la *distance d'édition* qui seront abordées en Terminale (uniquement pour ceux qui ont fait le bon choix de la NSI en terminale !)"},{"metadata":{},"cell_type":"markdown","source":"# EXERCICES \n\n## Exercice 1\n\nOn donne des points dans un repère orthonormé. Chaque point possède une classe : Rouge ou Bleue. Dans cette exercice, on utilise la **distance euclidienne** (naturelle) pour l'algorithme des $k$ plus proches voisins.\n\n![figure](https://github.com/profvdd/PremNSI2021/blob/main/ex1.png?raw=true)\n\n✍️ **Question 1** : On considère le point $M(1, 3)$. Appliquez l'algorithme des 3 plus proches voisins à ce point puis donnez une prédiction quant à sa classe.\n\n✍️ **Question 2** : Même question avec le point $N(4, 4)$.\n\n✍️ **Question 3** : Donnez une valeur de $k$ qui donnerait la prédiction \"Bleue\" pour le point $N$ après avoir appliqué l'algorithme des $k$ plus proches voisins.\n"},{"metadata":{},"cell_type":"markdown","source":"## Exercice 2\n\nOn peut ainsi représenter l'ensemble des points de l'exercice 1 dans un tableau `donnees` comme ci-dessous :"},{"metadata":{"trusted":false},"cell_type":"code","source":"A = {'nom': 'A', 'abs': 1, 'ord': 1, 'classe': 'Bleu'}\nB = {'nom': 'B', 'abs': 2, 'ord': 2, 'classe': 'Bleu'}\nC = {'nom': 'C', 'abs': 4, 'ord': 2, 'classe': 'Bleu'}\nD = {'nom': 'D', 'abs': 2, 'ord': 3, 'classe': 'Rouge'}\nE = {'nom': 'E', 'abs': 4, 'ord': 3, 'classe': 'Bleu'}\nF = {'nom': 'F', 'abs': 3, 'ord': 5, 'classe': 'Rouge'}\nG = {'nom': 'G', 'abs': 2, 'ord': 5, 'classe': 'Rouge'}\nH = {'nom': 'H', 'abs': 6, 'ord': 4, 'classe': 'Bleu'}\nI = {'nom': 'I', 'abs': 5, 'ord': 5, 'classe': 'Rouge'}\n\ndonnees = [A, B, C, D, E, F, G, H, I]\ndonnees","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"💻 **Question** : Utilisez la fonction `kppv` définie dans le TP sur l'algorithme des k plus proches voisins (question 10) pour vérifier vos réponses aux questions de la partie A. *Vous utiliserez la distance euclidienne qu'il faudra bien sûr légèrement adapter au format de nos données*."},{"metadata":{"trusted":false},"cell_type":"code","source":"# à vous de jouer !\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## Exercice 3 : Top 14\n\nLe fichier `top14.csv` contient des données sur tous les joueurs du top 14 de rugby. On peut représenter ces données de la façon suivante.\n\n![top14](https://github.com/profvdd/PremNSI2021/blob/main/top14_v2.png?raw=true)\n\n💻 **Question** : Vous rencontrez une personne souhaitant jouer au rugby. Elle vous donne sa taille (180 cm) et son poids (100 kg). Vous allez utiliser l'algorithme des k plus proches voisins pour lui indiquer quel poste est le plus proche de ses caractéristiques physiques. *Essayez plusieurs valeurs de k et n'hésitez pas à représenter graphiquement les données comme sur l'image au-dessus.*\n"},{"metadata":{"trusted":false},"cell_type":"code","source":"# à vous de jouer !\n","execution_count":null,"outputs":[]}],"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.10"}},"nbformat":4,"nbformat_minor":2}