34 - Algorithme K-NN

Cours associé : 25 - Intelligence artificielle .

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 (Spyder ou VS Code 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.

def distance(a, b):
    somme = (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2 + ...
    return sqrt(...)

Correction publiée après la séance.

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)

def plus_proche_voisin(donnee, nom_base):
    indice_min = -1
    dist_min = 0
    for i in range(len(nom_base)):
        d = distance(donnee, nom_base[i])
        if 0 < d and (indice_min == -1 or d < ...):
            dist_min = ...
            indice_min = ...
    return indice_min

Correction publiée après la séance.

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 ?

   Indice

   Les tris par sélection et par insertion vus en classe sont quadratiques, mais un tri efficace, comme celui de sorted, fait mieux : le cours sur les algorithmes gloutons donne son coût.

2. Quelle est la complexité de la recherche d’un minimum ?

   Indice

   Combien de fois chaque distance est-elle examinée lors d’un parcours de la liste ?

3. Quelle est alors la complexité de la recherche de k minimums ?

   Indice

   Rechercher k minimums, c’est recommencer k fois la recherche d’un minimum.

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.

def k_plus_proches_voisins(k, donnee, nom_base):
    distances = []
    for e in nom_base:
        distances.append(distance(donnee, e))
    voisins = []
    for _ in range(k):
        indice_min = -1
        dist_min = 0
        for i in range(len(nom_base)):
            if 0 < distances[i] and (indice_min == -1 or distances[i] < ...):
                dist_min = ...
                indice_min = ...
        voisins.append(...)
        distances[indice_min] = 0
    return voisins

Correction publiée après la séance.

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, ampoule.

def prediction_classe(k, donnee, nom_base):
    voisins = k_plus_proches_voisins(k, donnee, nom_base)
    effectifs = {}
    for i in voisins:
        classe = nom_base[i][-1]
        if classe in effectifs:
            effectifs[classe] = ...
        else:
            effectifs[classe] = ...
    classe_majoritaire = None
    maximum = 0
    for classe in effectifs:
        if effectifs[classe] > ...:
            maximum = ...
            classe_majoritaire = ...
    return classe_majoritaire

Correction publiée après la séance.

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 determiner_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.

def determiner_taux_bonne_classification_k(nom_base, k, nb_essais):
    corrects = 0
    for _ in range(nb_essais):
        base_reduite, donnees_test = separer_base_donnees_tests(nom_base, 1)
        donnee = donnees_test[0]
        if prediction_classe(k, donnee, base_reduite) == ...:
            corrects = ...
    return ...

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

Correction publiée après la séance.

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 …….. %

Correction publiée après la séance.