Aller au contenu

24 Exos Algorithme K NN

Contexte⚓︎

La police scientifique vient étudier une scène de crime au milieu de la forêt. Sur les vêtements, on retrouve quelques morceaux de verre. Identifier la provenance du verre permettrait d’orienter les recherches.

On récupère une base de données de classification du verre, qui classe des échantillons de verre en fonction de leur usage : fenêtre de bâtiment, fenêtre de véhicule, bocaux, verre de table, ampoules.

Pour chaque échantillon, on a mesuré sa teneur en Aluminum, Barium et Sodium (modèle simplifié de la base de données de B. German et V. Spiehler, 1987).

Question 0⚓︎

  1. Récupérez le fichier Base-Donnees-verre.csv. C’est la base de données de composition d’échantillons de verre. Ouvrez-la avec un éditeur de texte (Notepad++ par exemple) ou un tableur pour observer comment elle est construite.
  2. Récupérez le fichier TP-KNN-verre.py, c’est le programme Python qu’il faudra compléter.
  3. Sauvegardez les deux fichiers dans un même répertoire.

Remarque. Le fichier « TP-KNN-verre.py » contient déjà des fonctions pour vous permettre de récupérer la base sauvegardée dans le fichier « Base-Donnees-verre.csv », d’extraire des échantillons de la base de données pour les utiliser comme tests, de chercher le meilleur k. Il y a aussi des fonctions de tests pour vérifier vos fonctions des quatre premières questions.

La partie TP à réaliser commence après tout cela.

Question 1⚓︎

Commencez par écrire une fonction distance(a,b), qui, pour tout couple d’échantillons a et b, calcule la distance entre les valeurs de a et celles de b.

La distance utilisée est la distance euclidienne entre deux points à partir de leurs coordonnées, en constatant que chaque échantillon a 3 coordonnées.

Par exemple :

  • a = [1.12,0,12.79,'fenetre de batiment'] ou a = [1.12,0,12.79]
  • b = [1.35,0,12.16,'fenetre de vehicule'] ou b = [1.35,0,12.16]

On doit avoir :

\(\text{distance}(a,b)=\sqrt{{({1,12 - 1,35})}^{2} + {({0 - 0})}^{2} + {({12,79 - 12,16})}^{2}}\).

Remarque 1. On rappelle que la racine carrée en Python s’appelle en ayant importé la bibliothèque math, avec la fonction sqrt :

from math import sqrt

Remarque 2. Pour tester votre fonction distance, à la fin de la question 1, enlever le # devant :

tester_votre_fonction_distance(nom_fichier)

et faites exécuter votre script. Il testera alors des valeurs pré-calculées et vous indiquera si votre fonction renvoie les bons résultats.

indication

Les points ont pour coordonnées x, y, z les valeurs a[0], a[1], a[2].

Question 2⚓︎

Ecrivez une fonction plus_proche_voisin(donnee,nom_base) qui recherche dans la base de données nom_base le plus proche voisin de donnee au sens de la distance définie à la question 1, et renvoie son indice dans nom_base.

Remarque 1. Il faut trouver le plus proche, mais la distance ne doit pas non plus être nulle...

Remarque 2. Pour tester votre fonction plus_proche_voisin, enlever le # devant :

tester_votre_fonction_plus_proche_voisin(nom_fichier)

Question 3⚓︎

On veut écrire une fonction k_plus_proches_voisins(k, donnee, nom_base) qui recherche dans la base de données nom_base les k plus proches voisins de donnee en utilisant la fonction distance précédente et renvoie la liste de leurs k indices dans nom_base

Les distances ne doivent pas être nulles.

  1. Quelle serait la complexité minimale d’un tri de toute la liste des distances pour en récupérer les k plus petits ?
  2. Quelle est la complexité de la recherche d’un minimum ?
  3. Quelle est alors la complexité de la recherche de k minimums ?
  4. Ecrivez la fonction k_plus_proches_voisins(k, donnee, nom_base) en utilisant un algorithme en \(O(k\times n)\). Il suffit par exemple, à k reprises, de parcourir la liste des distances, et de récupérer le minimum qui n’a pas déjà été récupéré précédemment.
indication

Vous devez commencer par récupérer la liste des distances.

On peut utiliser par exemple :

🐍 Script Python
listedist = [distance(element, donnee) for element in nom_base]

Question 4⚓︎

Ecrivez une fonction prediction_classe(k, donnee, nom_base) qui renvoie la classe (ici le type de verre) correspondant à la classe majoritaire des k plus proches voisins de donnee dans la base nom_base.

La classe (type de verre) est toujours stockée en dernière colonne de la base nom_base.

  • Vous utiliserez la fonction k_plus_proches_voisins(k, donnee, nom_base) pour récupérer les indices des k plus proches voisins sous forme d’une liste.

  • Vous devez comptabiliser le nombres d’occurrences de chaque classe, et trouver celle qui apparaît le plus souvent. En cas d’égalité, on prend n’importe laquelle, par exemple la première.

  • au besoin, on peut utiliser le fait qu’il n’existe dans ce cas que cinq classes différentes : fenetre de batiment, fenetre de vehicule, bocaux, verre de table, ampoules.

indication

On peut utiliser une liste pour comptabiliser les occurrences.

Et on fait correspondre les classes (= types de verres) à des nombres de 0 à 4.

Question 5⚓︎

On veut maintenant savoir si cette méthode est fiable pour prédire la classe (type de verre) d’un échantillon. On va donc, de multiples fois, extraire l’un des échantillons de la base : le récupérer séparément comme une « donnée » et l’enlever de la base. Et on comparera le résultat donné par la fonction prediction_classe, avec la vraie classe de l’échantillon.

Ecrivez une fonction déterminer_taux_bonne_classification_k(nom_base,k, nb_essais) qui prend en entrée le nom de la base, la valeur de k choisie, et le nombre d’essais à réaliser.

On répètera nb_essais fois :

  • extraire 1 donnée de la base : vous utiliserez la fonction

separer_base_donnees_tests(nom_base, taille_tests) déjà implémentée, qui sélectionne taille_tests éléments de la base de données nom_base, les extraire de la base, et les sauvegarder dans une liste de donnees_test.

  • tester si la fonction prediction_classe donne la bonne réponse.

  • comptabiliser le nombre de réponses correctes.

La fonction retourne le taux total de réponses correctes.

chercher_meilleur_k_classification(base_verre,5000) permet de déterminer le meilleur k dans cette analyse, et son taux d’erreur.

Question 6⚓︎

Utilisez les fonctions déjà implémentées pour compléter le rapport à destination des enquêteurs :

Rapport d’analyse - Fragment de verre n°1

Composition : Aluminium : 2,09 ; Barium : 1,04 ; Sodium : 14,46

Il est probable que le morceau de verre provienne de ............................

Le taux d’erreur de cette analyse est de ........ %