TP – Apprentissage et algorithme des plus proches voisins.

Avant de commencer ce TP, vous devez avoir fait la petite introduction à matplotlib

Introduction

L’algorithme des k plus proches voisins appartient à la famille des algorithmes d’apprentissage automatique (machine learning).

L’idée d’apprentissage automatique ne date pas d’hier, puisque le terme de machine learning a été utilisé pour la première fois par l’informaticien américain Arthur Samuel en 1959.

Les algorithmes d’apprentissage automatique ont connu un fort regain d’intérêt
au début des années 2000 notamment grâce à la quantité de données disponibles sur internet.

L’algorithme des k plus proches voisins est un algorithme d’apprentissage supervisé, il est nécessaire d’avoir des données labellisées.

À partir d’un ensemble E de données labellisées, il sera possible de classer (déterminer le label) d’une nouvelle donnée (donnée n’appartenant pas à E).

Commencez par télécharger le fichier suivant :

Icône

iris.csv

1 fichier·s 1.50 KB
Télécharger

Enregistrez le dans un dossier qui s’appelle TP_knn

iris setosa

iris versicolor

iris virginica

Le fichier téléchargé précédemment contient les données de plusieurs dizaines d’iris. Et pour chaque iris :

  • la longueur des pétales
  • la largeur des pétales
  • l’espèce de l’iris (au lieu d’utiliser les noms des espèces, on utilisera des chiffres : 0 pour « iris setosa », 1 pour « iris virginica » et 2 pour « iris versicolor »)

Jouons un peu avec ce jeu de données.

Nous aurons besoin de pandas, donc pip install pandas

Ici, une petite introduction à pandas : http://www.python-simple.com/python-pandas/panda-intro.php

Affichons une représentation graphique de ces données à l’aide du script suivant :

import pandas as pd
import matplotlib.pyplot as plt

iris = pd.read_csv("iris.csv")

x = iris.loc[:, "petal_length"]
y = iris.loc[:, "petal_width"]
lab = iris.loc[:, "species"]

plt.scatter(x[lab == 0], y[lab == 0], color='blue', label='setosa')
plt.scatter(x[lab == 1], y[lab == 1], color='lightsteelblue', label='virginica')
plt.scatter(x[lab == 2], y[lab == 2], color='blueviolet', label='versicolor')

# lable des axes
plt.xlabel('longueur des pétales')
plt.ylabel('largeur des pétales')

# Affichage du graphe
plt.legend()
plt.show()

Le résultat :

Déjà, quel est le problème ?

Et bien un ami trouve un iris, nous indique la longueur et la largeur des pétales. On place ce nouvel iris sur notre graphe.

Sans prendre trop de risque je peux affirmer à mon ami qu’il s’agit vraisemblablement d’un iris versicolor.

Quelque jours plus tard il trouve encore un nouvel iris ! Je l’ajoute :

Là, le point noir étant « proche » du nuage de point bleu, je peux raisonnablement penser qu’il s’agit d’un iris setosa

Dés le lendemain il trouve un nouvel iris. Comme les fois précédentes je place le point :

C’est tout de suite moins évident ! Voilà le problème : Comment décider du label du nouvel iris ?

Il nous faudrait  un critère de décision :

  • moins subjectif qu’un « dans un nuage » ou un « très proche »,
  • algorithmique pour qu’une machine puisse décider.

L’algorithme « k-NN » des k plus proches voisins

« k – NN » car en anglais, il s’appelle « k–nearest neighbors algorithm ».

Article wikipédia sur la recherche des k plus proches voisins : https://fr.wikipedia.org/wiki/Recherche_des_plus_proches_voisins

Les plus proches ?

On voit bien dans le décompte des voisins que le choix du nombre k est important ! Ça fait partie des « leviers » de tous les spécialistes du « deep learning ».

Influence de k. Pour :

  • k == 1 on dirait que le nouveau devrait avoir le label versicolor car on a 1 voisin bleu et 0 voisin vert,
  • k == 2 on ne saurait dire quel label devrait avoir le nouveau car on a 1 voisin bleu et 1 voisin vert,
  • k == 3 on dirait que le nouveau devrait avoir le label setosa car on a 1 voisin bleu et 2 voisins vert,
  • etc.

Passons au code !

Voici le principe de l’algorithme de k plus proches voisins :

  • Il nous faut une distance. Écrire une fonction distance(x1, y1, x2, y2) qui calcule et renvoie la distance entre deux points de coordonnées (x1, y1) et (x2, y2) dans un repère orthonormé (formule de seconde).
Exercice
Codez la fonction distance
Solution
from numpy import sqrt as racine

def distance(x1, y1, x2, y2):
    """
    Entrée : x1, y1 coordonnées d'un point A
             x2, y2 coordonnées d'un point B
    Sortie : retourne la distance AB
    """
    return racine((x1 - x2) ** 2 + (y1 - y2) ** 2)
Reamarque : J’utilise numpy pour la racine plutôt que math , c’est pour faciliter le travail avec pandas. (Donc… Pip install numpy)
  • On calcule les distances entre le nouveau et chaque donnée de notre fichier csv à l’aide de la fonction programmé
Rappelons :
import pandas as pd
import matplotlib.pyplot as plt

iris = pd.read_csv("iris.csv")
# head pour afficher les 5 premières lignes du dataframe
print(iris.head())
Nous donne :

   petal_length  petal_width  species
0           1.4          0.2        0
1           1.4          0.2        0
2           1.3          0.2        0
3           1.5          0.2        0
4           1.4          0.2        0
On peut accéder à un élément précis du dataframe de la façon suivante :
>>> print(iris.loc[2, "petal_length"])
1.3
Pour visualiser sur le dataframe :
   petal_length  petal_width  species
0           1.4          0.2        0
1           1.4          0.2        0
2           1.3          0.2        0
3           1.5          0.2        0
4           1.4          0.2        0
Il suffit d’indiquer l’étiquette d’une ligne et d’une colonne pour accéder à un élément.
Maintenant que vous pouvez accéder aux éléments, vous pouvez calculer chaque distance.
Mais, nous pouvons aussi utiliser la puissance des dataframes de pandas ! On peut facilement ajouter une nouvelle colonne et cette nouvelle colonne peut être exprimée en fonction des deux autres… Par exemple, ajoutons une colonne qui est la somme de la longueur des pétales et de la largeur des pétales :
iris['somme'] = iris['petal_length'] + iris['petal_width']
Notre dataframe devient :
   petal_length  petal_width  species  somme
0           1.4          0.2        0    1.6
1           1.4          0.2        0    1.6
2           1.3          0.2        0    1.5
3           1.5          0.2        0    1.7
4           1.4          0.2        0    1.6
N’est-ce pas merveilleux ?
à vous de jouer !
Exercice
Rajouter une colonne 'dis' qui contient la distance entre l'iris et le nouvel iris
Solution
# Coordonnées du nouveau :
x_new, y_new = 2.5, 0.75
iris['dist'] = distance(iris['petal_length'], iris['petal_width'], x_new, y_new )
   petal_length  petal_width  species      dist
0           1.4          0.2        0  1.229837
1           1.4          0.2        0  1.229837
2           1.3          0.2        0  1.320038
3           1.5          0.2        0  1.141271
4           1.4          0.2        0  1.229837
  • On retient les k données du jeu de données les plus proches de nouveau
Pour trier le dataframe :
dataframe.sort_values(by = ‘C’)   retourne un dataframe avec les lignes triées de telle sorte que la colonne ‘C’ soit dans l’ordre croissant.
Exercice
trier le dataframe suivant une distance au nouveau croissante.
Solution
iris = iris.sort_values(by = 'dist')
print(iris.head())
 petal_length  petal_width  species      dist
98           3.0          1.1        1  0.610328
44           1.9          0.4        0  0.694622
24           1.9          0.2        0  0.813941
93           3.3          1.0        1  0.838153
57           3.3          1.0        1  0.838153
  • On attribue à nouveau la classe qui est la plus fréquente parmi les k données les plus proches.
Allons-y : à vous !
Dans l'exercice final de ce TP vous aller coder la fonction k_plus_proches_voisins(x_new, y_new, k)
Cette fonction doit retourner la classe contenant le plus de voisin pour notre nouveau.
Ces trois appels de ma fonction k_plus_proches_voisins avec notre couple x_new, y_new = 2.5, 0.75
k_plus_proches_voisins(x_new, y_new, 3)
setosa 
k_plus_proches_voisins(x_new, y_new, 5)
versicolor
k_plus_proches_voisins(x_new, y_new, 42)
setosa
Exercice
Codez la fonction k_plus_proches_voisins(x_new, y_new, k)
Solution
Pour comprendre ce corrigé il faut avoir une certaine habitude à utiliser la bibliothèque pandas.
import pandas as pd
import matplotlib.pyplot as plt
from numpy import sqrt as racine

fichier = "iris.csv"
x_new, y_new = 2.5, 0.75

def distance(x1, y1, x2, y2):
    """ Fonction qui retourne la
    distance entre (x1; y1) et (x2; y2)"""
    return racine((x1-x2)**2 + (y1-y2)**2)

def k_plus_proches_voisins(fichier, x_new, y_new, k):
    """ Retourne le label a attribuer au nouveau"""
    iris = pd.read_csv(fichier)
    iris['dist'] = distance(iris['petal_length'], iris['petal_width'], x_new, y_new )
    iris = iris.sort_values(by = 'dist')
    s = iris.head(k)['species'].value_counts().rename({0: 'setosa', 1: 'virginica', 2: 'versicolor'})
    return s.idxmax()

print(k_plus_proches_voisins(fichier, x_new, y_new, 42))
Je vous laisse admirer la puissance de pandas. 
Et sans Pandas, cela donne quoi ?
Voici une version n’utilisant que la bibliothèque standard. (Pas de pip install)
from math import sqrt

def distance(x1, y1, x2, y2):
    """
    Entrée : x1, y1 coordonnées d'un point A
             x2, y2 coordonnées d'un point B
    Sortie : retourne la distance AB
    """
    return sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)

def charge(fichier) :
    """
    fonction qui range les données du
    csv dans une liste
    Entrée : le nom d'un fichier
    Sortie : retourne une liste avec la structure:
    liste = [
            {'espece': val,
            'longueur': val,
            'largeur': val
             ]
    """
    # initialisation : liste vide
    liste = []
    # ouverture du fichier en lecture -> 'r'
    with open(fichier, 'r') as fichier:
        # on récupère le contenu
        texte = fichier.read()
        # on le separe en lignes
        lignes = texte.split(sep = '\n')
        # on parcourt les lignes
        for elt in lignes[1:]:
            fleur = elt.split(sep = ",")
            # contact valable ? contact est une liste
            if len(fleur) == 3:
                new = {}
                if fleur[2] == '0':
                    new['espece'] = 'setosa'
                elif fleur[2] == '1':
                    new['espece'] = 'virginica'
                else:
                    new['espece'] = 'versicolor'
                new['longueur'] = float(fleur[0])
                new['largeur'] = float(fleur[1])
                liste.append(new)
    return liste


def liste_triee_par_distances_croissantes(x_new, y_new):
    liste = charge("iris.csv")

    for rang in range(len(liste)): # tri par insertion
        # calcul de la distance
        x , y = liste[rang]['longueur'], liste[rang]['largeur']
        liste[rang]['dist'] = distance(x, y, x_new, y_new)
        dico_a_ranger = liste[rang]
        # le tri lui-même
        i = rang
        while i > 0 and liste[i - 1]['dist'] > dico_a_ranger['dist']:
            liste[i] = liste[i - 1]
            i -= 1
        #insertion
        liste[i] = dico_a_ranger
    return liste

def k_plus_proches_voisins(x_new, y_new, k):
    print("\nAlgorithme des", k, "plus proches voisins.\n")
    voisins = liste_triee_par_distances_croissantes(x_new, y_new)[:k]
    dico = {'setosa' : 0, 'virginica' : 0, 'versicolor' : 0}
    print("Les", k, "plus proches voisins sont de label")
    espece_max = 'rien_du_tout'
    maximum = 0
    for fleur in voisins:
        dico[fleur['espece']] += 1
        if dico[fleur['espece']] > maximum:
            espece_max = fleur['espece']
            maximum = dico[fleur['espece']]
        print(fleur['espece'], "à la distance", fleur['dist'])
    print("\nLe label le plus représenté est", espece_max)
    print("Il a atteint le maximum,", maximum, "occurences, en premier")
    print("Notre choix est donc le label", espece_max)

# nouveau
# x_new, y_new = 6, 2       # cas 1 simplissime
# x_new, y_new = 2, 0.5    # cas 2 facile
x_new, y_new = 2.5, 0.75  # cas 3 problématique

k_plus_proches_voisins(x_new, y_new, 3)
k_plus_proches_voisins(x_new, y_new, 5)
k_plus_proches_voisins(x_new, y_new, 42)