Un exemple d’algorithme d’apprentissage : algorithme des k plus proches voisins

L’exercice pour aujourd’hui préparait la suite, on commence par le corriger.

Figure_1

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

Stop ! Arrêtez le jargon !

Ok, vous savez ce qu’est la reconnaissance faciale sur un téléphone ? Un « Captcha » ? Ou vous avez entendu parler d’une voiture qui détecterait toute seule les passages pour piétons ?

Bienvenue dans le monde du « machine learning » ou « apprentissage automatique ».

En gros, on va donner une belle quantité de données à une machine, en disant « ça c’est tel label » ou « ceci tel autre label »pour qu’elle décide si une nouvelle donnée est d’un certain « label » ou pas.

Ah ok. Et comment on va s’y prendre ?

Comme dans le TP pour aujourd’hui. Et après, on découvre un nouvel algorithme … au programme … qu’on programme !

Dans le vif du sujet : nos données

Le TP que je propose est une version simplifiée d’un TP proposé par de nombreuses sources, officielles ou pas.
C’est une histoire de classification de fleurs, des iris, avec des labels. Ne vous étonnez pas d’en voir partout.

On a déjà travaillé avec des fichiers csv. Celui du jour est .

On va utiliser le même code que pour le « mignon » pour représenter graphiquement nos données.

Exemple 1 :

En gros, pour bien poser la problématique : le nouvel élément représenté en noir ci-dessous, avec le label « nouveau » mérite-t-il

  • le label « setosa »,
  • le label « virginica »,
  • le label « versicolor » ?

Figure_1

Sans hésitation, le point noir étant dans un nuage de points rouges, nous tranchons : le label « virginica ».

Exemple 2 :

Et là ?

Figure_2

Oh, et bien, le point noir étant « très proche » du nuage de points verts, nous tranchons : le label « setosa ».

Comment ça « dans un nuage » ou « très proche » ?

Pour nous, c’est instantané et très visuel avec une telle représentation graphique, mais comment un ordinateur peut-il être programmé pour ça ?

D’autant plus que même pour nous, ce n’est pas toujours évident 😦

Exemple 3 :

Figure_3

Programmons !

Je vous mets à nouveau à disposition un fichier csv, téléchargeable ici (bouton droit, enregistrer sous, iris_3col.csv). A l’aide de ce fichier, réaliser les graphiques ci-dessus :

Il faut placer le nouveau avec :

# 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
plt.scatter([x_new], [y_new], color = 'black', label = 'nouveau')

Correction à la fin du billet en cliquant sur « lire la suite ».

Comment décider du label du « nouveau » ?

Ok, il faut 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 « knearest neighbors algorithm ».

Les plus proches ?

cm 2020-04-06 knn_à_la_recherche_d_une_idee

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 0 voisin vert,
  • etc.

Programmons !

Voici le principe de l’algorithme des 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).
    Pendant le cours, on a écrit :

    from math import sqrt
    
    def distance(x1, y1, x2, y2):
        sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
  • On calcule les distances entre le nouveau et chaque donnée de notre fichier csv à l’aide de la fonction programmée
  • On retient les k données du jeu de données les plus proches de nouveau.
    Pendant le cours, on a proposé :

    • de trier la liste en prenant cette distance comme critère, par ordre croissant,
    • de garder les k premier éléments de cette liste.
  • On attribue à nouveau la classe qui est la plus fréquente parmi les k données les plus proches.

Allons-y : à vous ! Je ne proposerai pas de correction ici mais accompagnerai toutes celles et tous ceux qui voudront aller au bout de ce travail, un peu comme un « devoir maison » pendant ces congés à venir… Mercredi, on reprend avec des pages web 😀

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)
k_plus_proches_voisins(x_new, y_new, 5)
k_plus_proches_voisins(x_new, y_new, 42)

donnent :

Algorithme des 3 plus proches voisins.

Les 3 plus proches voisins sont de label
versicolor à la distance 0.6103277807866851
setosa à la distance 0.6946221994724903
setosa à la distance 0.8139410298049854

Le label le plus représenté est setosa
Il a atteint le maximum, 2 occurences, en premier
Notre choix est donc le label setosa

Algorithme des 5 plus proches voisins.

Les 5 plus proches voisins sont de label
versicolor à la distance 0.6103277807866851
setosa à la distance 0.6946221994724903
setosa à la distance 0.8139410298049854
versicolor à la distance 0.8381527307120104
versicolor à la distance 0.8381527307120104

Le label le plus représenté est versicolor
Il a atteint le maximum, 3 occurences, en premier
Notre choix est donc le label versicolor

Algorithme des 42 plus proches voisins.

Les 42 plus proches voisins sont de label
versicolor à la distance 0.6103277807866851
setosa à la distance 0.6946221994724903
setosa à la distance 0.8139410298049854
versicolor à la distance 0.8381527307120104
versicolor à la distance 0.8381527307120104
setosa à la distance 0.8381527307120106
setosa à la distance 0.873212459828649
...
setosa à la distance 1.2298373876248845
setosa à la distance 1.2298373876248845

Le label le plus représenté est setosa
Il a atteint le maximum, 36 occurences, en premier
Notre choix est donc le label setosa
>>>

Pendant le cours, on a écrit, comme corrigé de la première partie graphique avec matplotlib :

def lecture(nom_du_fichier) :
    # initialisation : liste vide
    liste = []

    # ouverture du fichier en lecture -> 'r'
    with open(nom_du_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 la liste des lignes sauf la première
        for phrase in lignes[1:]:

            # on découpe la phrase en trois morceaux dans une liste
            # attention dans ce csv le séparateur
            # est un virgule , et pas un ;
            liste_de_trois = phrase.split(sep = ',')

            if len(liste_de_trois) == 3:
                # un nouveau dico vide appelé new
                new = {}

                new['espece'] = liste_de_trois[2]

                # attention : à convertir en flottants
                # le premier élément de la liste
                new['abscisse'] = float(liste_de_trois[0])

                # le deuxième élément de la liste
                new['ordonnee'] = float(liste_de_trois[1])

                # on rajoute new à la liste
                liste.append(new) # ou liste += [new]

        # on ferme le fichier ouvert
        fichier.close()

    # on renvoie la liste remplie
    return liste

liste = lecture("iris_3col.csv")
# print(liste)

import matplotlib.pyplot as plt 

tuning = [('setosa', 'g'),
          ('versicolor', 'b'),
          ('virginica','r')]

for espece, couleur in tuning:
    # données
    x=[]
    y=[]
    for f in liste :
        if f['espece'] == espece:
            x.append(f['abscisse'])
            y.append(f['ordonnee'])
    plt.scatter(x, y, color = couleur, label = espece, marker = 'o')

# 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
plt.scatter([x_new], [y_new], color = 'black', label = 'nouveau')

# graphique
plt.legend()
plt.show()

 

2 réflexions au sujet de « Un exemple d’algorithme d’apprentissage : algorithme des k plus proches voisins »

  1. Si ça vous intéresse, on a exactement ce sujet dans nos TP python d’Intelligence Artificielle pour classer les iris en L3 x)

Répondre à M. Marchant Annuler la réponse.

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l’aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l’aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l’aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l’aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur la façon dont les données de vos commentaires sont traitées.