Classifier un objet

Classifier un objet dans une table de données classifiées

Étude d’un cas

Intéressons nous pour changer aux pokemons … décidément très envahissants !

On se propose de déterminer si le pokemon ci-dessous est légendaire ou pas (sans rechercher la réponse sur Internet !).

Pokemon mystère

Alors il est ou pas ? … N’êtes vous pas devenus des experts des pokemons depuis le temps ? Non ? Et bien moi non plus ! Mais alors comment peut on malgré tout estimer la réponse de manière rationnelle plutôt que de laisser faire le hasard ? Et si on apprenait à l’ordinateur à reconnaître un pokemon légendaire ?

On va s’intéresser à un algorithme d’apprentissage qu’est l'algorithme k-nn (k-nearest neighbors en anglais/k plus proches voisins en français).

Étant donné une table de données classifiées, pour un nouvel objet (dont on cherche à classifier) et une fonction distance donnée, l’algorithme des k-plus proches voisins consiste dans cet ordre
(1) à déterminer les k objets de cette table les plus proches de cet objet donné,
(2) à retourner la classe la plus représentée parmi ces k objets.

Par exemple, supposons que l’on dispose d’une table des données regroupant quelques centaines de pokemons dont on connaît leur Id, leur Name, leur ATK, leur SP.ATK ainsi que leur classification légendaire.

… graphiquement

On place ces pokemons, ainsi que le pokemon mystère (représenté par un triangle vert) dans un plan muni d’un repère. On obtient ainsi la représentation graphique ci-dessous.

Bokeh Plot

À faire

En utilisant les outils fournis (la barre verticale à droite du premier graphique et des boutons sous celui-ci), répondre aux questions suivantes:
a) Quel est le nom du pokemon le plus proche du pokemon mystère ? Quelle est sa classe (légendaire ou normal)?
b) Quels sont les noms des 5 pokemons les plus proches du pokemon mystère ? Quels sont leurs classes respectives ? Quelle est la classe majoritaire ?

Solutions ?

Interprétation pour l’algorithme k-nn:

  • Pour \(k=1\), l’algorithme 1-nn pour la distance euclidienne (mais aussi pour les deux autres distances) retourne la classe normale et permet donc de classifier le pokemon mystère parmi les pokemons de classe normale (non légendaire).

  • Pour \(k=5\), l’algorithme 5-nn pour la distance euclidienne (mais aussi pour les deux autres distances) retourne la classe légendaire et permet par conséquent de classifier le pokemon mystère en tant que pokemon légendaire.

a) La distance euclidienne est définie dans un repère orthonormé.
Dans le plan, la distance euclidienne entre \(A(x_A; y_A)\) et \(B(x_B; y_B)\) est \[d_2(A,B)=\sqrt{(x_B-x_A)^2 + (y_B-y_A)^2}\].
b) La distance de Tchebychev est définie dans tout repère.
Dans le plan, la distance de Tchebychev entre \(A(x_A; y_A)\) et \(B(x_B; y_B)\) est \[d_{\infty}(A,B)=\max(|x_B-x_A|; |y_B-y_A|)\].
c) La distance de Manhattan est définie dans tout repère.
Dans le plan, la distance de Manhattan entre \(A(x_A; y_A)\) et \(B(x_B; y_B)\) est \[d_1(A,B)=|x_B-x_A|+|y_B-y_A|\].

Exemple:

  • La distance euclidienne entre Hydreigon et le pokemon msytère est égale à \(\sqrt{8}\) soit approximativement \(2.8\).

  • La distance de Tchebychev entre Hydreigon et le pokemon msytère est égale à \(2\).

  • La distance de Manhattan entre Hydreigon et le pokemon msytère est égale à \(4\).

Conclusion: il est indispensable de choisir judicieusement le \(k\) ainsi que la distance. La classe que retourne l’algorithme k-nn peut différer suivant le choix fait.



Et si on pouvait se passer du graphique en travaillant directement sur les données présentes dans le fichier csv (avec le tableur: formules et filtres) ou la table en Python (avec un script en utilisant les fonctions vues dans le cours précédent (4.3)) ?

… avec usage d’un tableur

Dans la suite, on va procéder ainsi:
(1) on choisit la distance à calculer ;
(2) on ajoute une colonne dans le tableau afin d’y calculer la distance entre chaque pokemon et le pokemon mystère ;
(3) on les trie dans l’ordre croissant des distances à l’aide d’un filtre mis à notre disposition ;
(4) on détermine les effectifs de chacune des classes présentes dans ces \(k\) premières lignes ;
(5) on attribue la classe majoritaire au pokemon mystère.

À faire

  • pokemons.csv (20 ko)

    • Visuel des premières lignes du fichier pokemons.csv

    Nous allons appliquer l’algorithme k-nn avec \(k=5\) et la distance euclidienne

    a) Télécharger le fichier pokemons.csv, puis ouvrez le avec un tableur.

    Prenons la colonne \(\texttt{F}\) qui est libre pour y calculer les distances désirées.

    b) Dans la cellule \(\texttt{F2}\), écrire une formule qui permette de calculer les distances désirées en étirant celle-ci vers le bas

    Comment copier une formule en étirant vers le bas à la souris

    Il existe bien d’autres méthodes de le faire. Par exemple, il est plus rapide de sélectionner la plage \(\texttt{F2:F722}\), puis appuyer sur la combinaison de touches \(\fbox{Ctrl}+\fbox{D}\).

    Comment sélectionner une plage rapidement sans usage de la souris

    c) Trier les lignes dans l’ordre croissant des distances à l’aide des filtres fournis par votre tableur.

    Comment trier des données suivant une colonne (LibreOffice)

    d) Retrouver la classe majoritaire renvoyée par l’algorithme k-nn pour \(k=5\) et la distance euclidienne.

    … avec Python

    On va suivre la même procédure que précédemment. Pour se faire, on va utiliser les fonctions vues dans le (4.3)) en travaillant avec des tables de données, c’est à dire des séquences de dictionnaires où, pour rappel, chacun des dictionnaires représente un pokemon (soit une ligne dans le tableur).

    À faire

    a) Placez vous dans le dossier contenant le fichier dans lequel se trouvent les fonctions obtenues dans le (4.3) et y déposer le fichier pokemons.csv.

    b) Dans le même dossier, créer un fichier knn.py

    Dans la suite, les fonctions seront à écrire dans ce dernier fichier.

    c) Écrire une fonction Python distance_euclidienne() de paramètres poke1 et poke2 (deux dictionnaires désigant chacun un pokemon).
    Jeu de test:

    >>> hydreigon = {'Name': 'Hydreigon', 'ATK': 105, 'SP.ATK': 125, 'Legendary': False}
>>> regigigas = {'Name': 'Regigigas', 'ATK': 160, 'SP.ATK': 80, 'Legendary': True}
>>> round(distance_euclidienne(hydreigon, regigigas), 3)
71.063

    d) Ècrire une fonction knn() de paramètres table (une table de données, c’est à dire une séquence de dictionnaires), mystere (un dictionnaire), k (un entier) et dist_choisie (la fonction distance choisie). Cette fonction doit retourner la classe majoritaire suivant la méthode k-nn.
    Indication:
    (1) prolonger la table initiale avec la clé supplémentaire 'Distance' de telle sorte que la valeur associée à cette clé correspond à la distance au pokemon mystère.
    (2) trier dans l’ordre croissant cette table suivant cette nouvelle clé 'Distance'.
    (3) extraire les k premiers dictionnaires (pokemons).
    (4) décompter le nombre de pokemons de classe légendaire.
    (5) enfin retourner la classe majoritaire.
    e) Retrouver uen nouvelle fois le résultat obtenu précédemment par la méthode k-nn avec \(k=5\) et la distance euclidienne.

    Vérifier la classification fournie par l’algorithme

    Je ne traiterai pas en détail de cet aspect. La classification de l’algorithme dépend du choix de \(k\), de la distance mais aussi et surtout des clés (choisis ou imposés) du modèle.

    Par exemple pour les pokemons, les deux attributs ATK et SP.ATK sont-ils les plus pertinents pour estimer la classe légendaire d’un pokemon ? Quelle marge d’erreur y a-t-il entre la classe effective et la classe résultante de l’application de l’algorithme k-nn avec un \(k\) et une distance choisis ?

    La validation du modèle choisi se fera en observant le taux d’erreurs entre les modèles effectif (classification donnée) et théorique (classification résultante de l’application de l’algorithme). Pour se faire, en pratique, on dispose d’une base de données déjà classifiées, puis on partage cette base en deux tables: \(\dfrac{1}{3}\) de la base de départ sera réservé afin de tester la validité du modèle et, une fois ce modèle vérifié, le restant de la base servira effectivement à classer un nouvel objet proposé (hors de la base de départ).

    Ainsi, pour l’exemple donné, avant de rechercher la classe d’un pokemon, on aurait dû s’interroger sur la pertinence du choix des deux seuls attributs ATK et SP.ATK pour classer un pokemon en testant sur une partie de la table de données de départ ce que l’on n’a pas fait.