II. L'algorithme des k plus proches voisins¶

Cours¶

L'intelligence artificielle est un domaine vaste de l'informatique, dans lequel on utilise des algorithmes pour faire des prédictions sur des données. Nous allons voir un exemple d'un tel algorithme.

Introduction¶

Imaginons que l'on veuille déterminer l'espèce d'un animal, en ayant à notre disposition sa masse et sa taille.

Quelles autres informations peuvent nous aider à prédire son espèce - sans pouvoir avoir une autre de ses caractéristiques - ?

Si l'on a la masse, la taille et l'espèce associées à d'autres animaux, on peut avoir une idée des ordres de grandeur correspondant aux différentes espèces.

Comment, alors, faire la prédiction ?

On peut trouver un animal dont le masse et la taille sont les plus proches de ceux de notre animal, et en déduire qu'ils sont de la même espèce. Ou mieux encore, on peut se baser sur l'ensemble des animaux les plus proches.

Définition

Les algorithmes qui se basent sur des données disponibles pour en déduire des informations sur de nouvelles données sont appelés des algorithmes d'apprentissage. Ces algorithmes apprennent sur des données existantes, pour prédire des informations sur des données nouvelles.

A. Calculer la distance entre des données¶

A.I. Placer le jeu de données dans un repère¶

Pour trouver les animaux les plus proches du nouvel animal, on place les informations dont on dispose dans un repère, avec la masse en abscisse et la taille en ordonnée,

On représente ici avec la couleur l'espèce de chaque animal : c'est-à-dire sa classification.

A.II. La nouvelle donnée¶

La nouvelle donnée, sur laquelle on veut faire une prédiction, doit être comparée à toutes les autres. On peut la placer sur le graphe fait précédemment.

La classification de celle-ci n'est pas connue, on se base sur la classification des données du jeu de données pour attribuer une espèce à cette nouvelle donnée.

B. Classifier une nouvelle donnée¶

B.I. Mesure de distance¶

Pour estimer si deux animaux \(a_{1}\) et \(a_{2}\) ayant les caractéristiques respectives \(m_{1}\), \(t_{1}\) et \(m_{2}\), \(t_{2}\) sont "proches", on utilise la formule suivante calculant leur distance \(d\) :
\(d = \sqrt{ (t_{1}-t_{2})^2 + (m_{1}-m_{2})^2 }\)

N.B.: Les points qui sont proches sont identifiables facilement sur le graphe, mais la distance doit être quantifiable par l'ordinateur.

On calcule donc la distance entre la nouvelle donnée, et tous les autres points.

B.II. Les k plus proches voisins¶

L'algorithme des k plus proches voisins sélectionne ensuite les \(k\) points les plus proches de notre donnée.

Graphiquement, on peut assez facilement identifier ces points.

Comment le faire automatiquement, dans un programme ?

On peut le faire en triant les distances entre la nouvelle donnée et tous les autres points, et en sélectionnant les k points dont la distance est la plus faible.

Sur l'exemple, sélectionner les 4 plus proches voisins de la données à classifier :

B.III. Classification¶

Ces \(k\) voisins sont associés à une espèce. On regarde ensuite quelle est l'espèce la plus présente parmi ceux-ci, et c'est avec celle-ci que l'on classe la nouvelle donnée.

Comment classifier la nouvelle donnée, sur l'exemple ?

En appliquant l'algorithme, on trouve que la nouvelle donnée correspond à un chat.

Quels algorithmes faut-il appliquer sur les \(k\) plus proches voisins pour obtenir l'information qui nous intéresse ?

Il faut compter les occurrences des différentes espèces parmi ces k voisins, puis en sélectionner le maximum.

Quel type de donnée faut-il utiliser ?

Il faut utiliser un dictionnaire avec l'espèce comme clé, et le nombre d'occurrences comme valeur.

Conclusion¶

On peut utiliser cet algorithme pour classifier n'importe quelles données, en fonctions de caractéristiques disponibles (au nombre de 2, ou bien plus !).

Plus le jeu de test contient de données, meilleure sera la prédiction. Ce type d'algorithme est largement utilisé par les GAFAM et autres entreprises du numérique, qui disposent de très grandes bases de données pour construire des modèles plus précis.

TP : Implémentation¶

Nous allons implémenter un algorithme d'apprentissage, permettant de faire des prédictions sur des données. On veut identifier l'espèce d'un animal à partir de sa masse et de sa taille, en se basant sur un jeu de données disponibles : les données d'autres animaux, pour lesquels on connaît la masse, la taille, et l'espèce.

Télécharger le fichier TP_KVoisins.py. Il contient du code à compléter, correspondant aux différentes parties du TP.

A. Représentation des données¶

Les données sont stockées dans une variable donnees_animaux.

Quel est son type ? (soyez précis)
Quelle instruction permet d'accéder à la taille de l'animal d'indice 1 ?

Note

donnees_animaux` est une variable dite globale, c'est-à-dire que nous allons l'utiliser dans les différentes fonctions du programme, sans avoir à la mettre en paramètre des fonctions.

B. Distance entre les données¶

On veut trouver l'espèce d'un animal mystère, connaissant sa masse et sa taille. Pour cela, nous allons estimer de quels autres animaux du jeu de données est-ce qu'il est le plus proche. On calcule pour cela la distance entre les animaux à partir de leurs caractéristiques, en utilisant la mesure de distance euclidienne.

Compléter la fonction distance(donnee1, donnee2), calculant la distance euclidienne entre donnee1 et donnee2. Il faut stocker dans les variables x1 et y1 les caractéristiques de donnee1, et dans x2 et y2 celles de donnee2.

Note 1

La formule de la distance euclidienne \(d\) entre deux points \((x_1, y_1)\) et \((x_2, y_2)\) est \(d = \sqrt{ (x_{1}-x_{2})^2 + (y_{1}-y_{2})^2 }\)

Note 2

sqrt calcule la racine carrée ("root mean square"). La fonction est importée de la bibliothèque math tout en haut du programme.
On ajoute ensuite une clé distance à chaque dictionnaire de donnees_animaux, à laquelle on associe la valeur renvoyée par la fonction distance écrite dans la question 1, calculée avec la nouvelle donnée. Ceci est fait dans la fonction calcule_distance(donnee) : la compléter.
Ecrire l'appel de la fonction calcule_distance permettant d'actualiser les valeurs de donnees_animaux.

C. Tri¶

Pour déduire l'espèce de l'animal mystère, on regarde l'espèce de ses \(k\) voisins les plus proches. Il faut donc trier les voisins, en fonction de leur distance par rapport à l'animal mystère, et en retenir les \(k\) premiers.

La fonction tri trie les animaux de donnees_animaux par valeur croissante de la valeur associée à la clé distance.

Quel est l'algorithme de tri utilisé dans cette fonction ?

Compléter la fonction (les ...), pour comparer les bonnes valeurs.
Attention, donnees_animaux a été modifiée dans la partie B !
Appeler la fonction et vérifier que l'ordre de donnees_animaux a bien été modifié.

D. K plus proches voisins¶

Il reste à analyser les espèces les plus présentes dans les \(k\) plus proches voisins. Il faut :
- compter le nombre d'occurrences des différentes espèces,
- sélectionner le maximum parmi ces nombres d'occurrences.

Ecrire la fonction compte_occurrences(k), qui compte le nombre de fois que chaque espèce apparaît dans les \(k\) premiers éléments de donnees_animaux. Cela revient à faire un calcul d'occurrences sur une liste Python, sauf que ses éléments sont des dictionnaires plutôt que des types de base et que l'on ne va que jusqu'à \(k\)ème élément de la liste.

Vous avez écrit une fonction qui y ressemble dans le TP "Les résultats d'une élection" pour le dépouillement des votes.
Aide

On peut utiliser le pseudo-code suivant (sans oublier de définir la fonction et de renvoyer le résultat):
```
Entrée : l entier k
Sortie : le dictionnaire occurrences

occurrences <- dictionnaire vide
pour un indice i variant de 0 à k-1
    espece <- espèce du ième élément de donnees_animaux
    si espece est dans occurrences
        on incrémente occurrences[espece]
    sinon
        on affecte 1 à occurrences[espece]
```
Ecrire la fonction maxi_occurrence(occurrences) prenant en paramètre un dictionnaire occurrences, comme celui obtenu en sortie de compte_occurrences et renvoyant la clé de la valeur maximale d'occurrences.

Vous avez écrit une fonction qui y ressemble dans le TP "Les résultats d'une élection" pour trouver le vainqueur.
Appeler ces deux fonctions pour obtenir le résultat. Quel est-il ? ...........................................

TD : Application de l'algorithme¶

Exercice 1 : application de l'algorithme¶

Quelle affirmation, parmi A, B, C ou D, est vraie ? (une seule est vraie)

A- L'algorithme des k plus proches voisins a pour but de déterminer les k plus proches voisins d'une observation dans un ensemble de données.

B- L'algorithme des k plus proches voisins a pour but de déterminer la classe d'une observation à partir des classes de ses k plus proches voisins.

C- L'algorithme des k plus proches voisins a pour but de déterminer dans un ensemble de données le sous-ensemble à k éléments qui sont les plus proches les uns des autres.

D- L'algorithme des k plus proches voisins a pour but de déterminer les éléments d'un ensemble de données appartenant à une même classe.
Remettre dans l'ordre les étapes, notées de a à d, de cet algorithme :

a. Trier les données par distance croissante avec l'observation
b. Sélectionner les k données les plus proches
c. Calculer la distance entre l'observation et le reste des données
d. Déduire de la classe majoritaire des k voisins la classe de l'observation
On a représenté sur un quadrillage les éléments de quatre classes (chaque classe est représentée par un carré, un triangle, un losange ou un disque) ainsi qu’un nouvel élément X.

En appliquant l'algorithme des k plus proches voisins pour la distance usuelle dans le plan, avec k=3, à quelle classe (parmi celle des carrés, des triangles, des ronds ou des losanges) est affecté le nouvel élément X ?

Obtient-on la même chose pour k=5 ?

Exercice 2: distance euclidienne¶

L'algorithme des k plus proches voisins utilise une mesure de distance entre données. (Re)voyons comment calculer cette distance.

On utilise une fonction distance pour calculer la distance entre deux points. Compléter sa spécification.

from math import sqrt   # import de la fonction racine carree

def distance(point1, point2):
    """ 
    Entrées : point1, point2 sont des ............... contenant 2 entiers
    Sortie : la distance euclidienne entre point1 et point2, de type .................
    """
    return sqrt((point1[0]-point2[0])**2 + ((point1[1]-point2[1]))**2)

assert distance((1, 0), (5, 3)) == 5.0

On définit une fonction plus_courte_distance, trouvant le point le plus proche d'un point de départ, parmi un ensemble de points stockés dans un tableau. Compléter cette fonction, ainsi que l'assertion permettant de la tester :

def plus_courte_distance(tab, depart):
    """ Entrées : un tableau de points tab de type liste de tuples et depart un point de type tuple
    Sortie : un point de type tuple
    """
    point = tab[0]

    min_dist = ...........................
    for i in range (1, len(tab)):
        if distance(tab[i], depart)<min_dist:

            point = .......................
            min_dist = distance(tab[i], depart)
    return point

assert plus_courte_distance([(7, 9), (2, 5), (5, 2)], (0, 0)) == ................