Classification supervisée

Dans ce TP, on va aborder la classification supervisée en la mettant en œuvre sur le jeu de données olives. Les notions essentielles de classification supervisée ont été vues en L2. Il s'agît donc ici de rappel et surtout de mise en pratique. Si nécessaire, on pourra consulter mes notes de cours de fouille de données pour une présentation de la classification supervisée.
Les 2 TPs précédents (tableaux de données et graphiques) doivent impérativement avoir été faits.

À l'issue de ce TP, vous m'envoyez par email un compte-rendu (format odt ou pdf) indiquant la réponse aux questions qui sont posées. Vous m'envoyez également un fichier python réalisant toutes les manipulations de ce TP : je dois pouvoir exécuter ce fichier en tapant python3 nom-de-votre-fichier.py et reproduire vos résultats. Cette exécution ne doit pas provoquer d'erreur de python. Remarque : un notebook ne convient pas.

Introduction

Les olives du jeu de données proviennent chacune d'une région particulière d'Italie : sud, Sardaigne, nord. Celles-ci sont numérotées et la valeur associée à chaque olive est dans l'attribut 1 dénommé region. Chaque région est découpée en sous-régions ; cette sous-région est dans les attributs 0 et 2 ; l'attribut 2 est juste le numéro de la sous-région dont le nom est donné par l'attribut 0. La carte ci-dessous indique ces régions et certaines sous-régions.

(Cette figure est issue du livre sur ggobi.)

Chaque olive étant par ailleurs caractérisée par sa teneur en certains acides, la question que nous étudions dans ce TP est : à partir de cette composition chimique, peut-on déterminer la provenance géographique de l'olive ?
Si on arrive à déterminer la provenance à partir de la composition chimique de l'olive, on peut garantir que la provenance indiquée est la bonne et pourquoi pas, détecter ainsi des tentatives de fraudes si ce n'est pas le cas.

On va pratiquer en deux phases. Durant la première, on va explorer visuellement le jeu de données : la réponse à la question posée est-elle visible sur un ou des graphiques ? Durant la seconde, on va utiliser un algorithme d'apprentissage automatique pour essayer de répondre à la question. Les deux approches ne sont pas exclusives, bien au contraire : la première guide le choix d'une méthode à appliquer lors de la seconde.

Premiers pas : approche graphique (exploration visuelle des données)

Face à un jeu de données, la première chose à faire et de l'explorer visuellement. Dans le cas où on souhaite prédire la valeur d'un attribut, on se pose la question : la réponse à la question qui est posée saute-t-elle aux yeux ?
Donc, on commence par faire des graphiques très simples pour voir s'il est possible de prédire la région de provenance de l'olive. On commence par la région car il y a 3 régions (attribut region) qui se découpent en 8 zones (attributs et Area Name et area). Il est donc probablement plus facile de déterminer la région que la zone.
Cette exploration visuelle permet également d'orienter le choix d'un modèle pour réaliser la tâche de prédiction : si on voit des relations simples, on sait que des modèles simples pourront réaliser les prédictions voulues.

Visualisation univariée : répartition des valeurs de chaque attribut en fonction de sa classe

Par graphique très simple, on entend la visualisation de la répartition de la valeur d'un attribut (= univarié) en fonction de sa classe. Pour chaque acide, on réalise un graphique comme celui-ci pour l'attribut palmitic :

• En ordonnées, c'est le numéro de la donnée (la ligne dans le jeu de données) ;
• en abscisses, la valeur de l'attribut palmitic ;
• la couleur indique la région :
  1. sud de l'italie en bleu ;
  2. Sardaigne en rose ;
  3. nord de l'italie en jaune.

D'un coup d'œil, on voit que cet attribut ne permet pas de distinguer les olives des 3 classes. Quand on considère une valeur de l'acide palmitique supérieure à 1400, on voit que l'on peut en déduire que l'olive provient de la zone 1 : il n'y a que des points bleus pour ces abscisses : tout va bien. Par contre, si cette valeur est comprise entre 1000 et 1200, les 3 classes sont possibles : pour ces abscisses, on voit des points des 3 couleurs. Donc, si la teneur en acide palmitique est 1100, on ne peut pas déterminer la zone d'origine de l'olive.
En conclusion, l'attribut palmitic ne permet pas de déterminer la région d'origine de l'olive.

À faire : réalisez ce graphique pour chacun des 8 acides et concluez (vérifiez que vous obtenez bien le même graphique que moi pour l'acide palmitique). Y a-t-il un, ou des attributs, qui permet de déterminer la région d'origine ? ou qui peut aider ?
Remarque : pour réaliser ce graphique, j'ai ajouté une colonne numero au tableau de données olives. Cette colonne contient tout simplement le numéro de la donnée.

À faire : sans dévoiler la solution, vous devez trouver un attribut qui sépare l'une des classes des deux autres. Pour celui-ci, vous obtenez un graphique qui ressemble à celui-ci :

Ce graphique montre que la classe 1 (points bleus) est facilement identifiée grâce à cet attribut.
Quand vous l'avez trouvée, vous pouvez vous concentrer sur les 2 classes qui sont encore mélangées (jaune et rouge) et recommencer le même raisonnement en vous occupant uniquement des données de ces deux classes. Vous devez trouver un attribut qui sépare bien ces 2 classes restantes.
Quels sont ces deux attributs et comment pouvez-vous déterminer la classe à partir de ces deux attributs ?

Visualisation bivariée

« Bivariée » signifie que l'on considère deux attributs. L'idée est ici la même que précédemment, mais au lieu de chercher une relation entre un attribut et la classe, on cherche une relation entre un couple d'attributs et la classe.
Reprenons le schéma réalisé à la fin du TP précédent :

On voit que ces deux attributs ne permettent pas de déterminer la classe de manière simple : les points des 3 couleurs sont mélangés.
On peut quand même voir que pour une valeur de l'acide oléique inférieure à (environ) 7200, l'acide palmitique permet à peu près de bien prédire la classe 1 ou 3. Cela ne répond pas à notre question, mais c'est un élément d'information.

Je pourrais vous demander de chercher s'il existe une paire d'attributs qui permettent de prédire la région d'origine des olives mais je sais que cette recherche sera vaine et qu'elle vous prendra du temps. Donc vous pouvez passer à la suite, ou quand même vérifier qu'il n'y a rien à voir de simple sur aucun de ces graphiques.

Approche automatique

Il arrive que l'approche visuelle ne permette pas de voir quelque chose (c'est rare). Quoiqu'il en soit, en complément de l'exploration visuelle, nous allons essayer de prédire la région d'origine de l'olive à l'aide de méthodes qui ont pour objectif d'apprendre un modèle réalisant ce type de prédiction.

Face à un jeu de données de petite taille comme celui-ci (quelques centaines de lignes, une dizaine de colonnes, quelques classes), on commence par essayer une méthode qui généralement donne de très bons résultats, les arbres de décision. L'induction d'un arbre de décision est très souvent une méthode très efficace, très peu coûteuse en temps de calcul, qui donne de très bonnes performances pour la prédiction de la classe.

Pour cela, on va utiliser la bibliotèque scikit_learn. Pour pouvoir créer des arbres de décision, on fera : from sklearn import tree.
La documentation est là.

Induction d'un arbre de décision

Pour induire un modèle, on fait comme suit : le jeu de données est découpé en deux parties, l'une utilisée pour induire le modèle, la seconde pour estimer la probabilité qu'il commette une erreur lors d'une prédiction.
La première partie constitue les données d'entraînement, la seconde les données de test.
Il est classique d'utiliser 80% des données disponibles comme données d'entraînement, les 20% restant constituant les données de test.
La répartition entre les deux parties est faite aléatoirement. Il est important de vérifier que les données sont stratifiées, c'est-à-dire que la proportion des données de chaque classe est à peu près la même dans les deux parties.

Pour découper le jeu de données en ces deux parties, on utilise la fonction train_test_split () de la bibliothèque sklearn.model_selection.
On fera donc : from sklearn.model_selection import train_test_split.
et ensuite, pour partitionner le jeu d'exemples en 20% pour le jeu de test et 80% pour le jeu d'entraînement :

olivesX_train, olivesX_test, olivesY_train, olivesY_test = train_test_split (olives.iloc [:,3:11], olives.region, test_size = .2, random_state = 123)

Suite à cet appel, on obtient 4 objets :

• olivesX_train est un tableau de données qui contient 80% des olives. Seuls les 8 attributs numérotés 3 à 10 ont été sélectionnés, c'est-à-dire les attributs indiquant la composition chimique des olives.
• olivesX_test est un tableau de données qui contient les 20% restants des olives.
• olivesY_train est un tableau de données comprenant une seule colonne (region) qui indique la classe de chaque élément de olivesX_train.
• olivesY_test est un tableau de données comprenant une seule colonne (region) qui indique la classe de chaque élément de olivesX_test.

olivesX_train et olivesY_train constituent le jeu de données d'entraînement avec lequel on construit un modèle de prédiction de la classe.
olivesX_test et olivesY_test constituent le jeu de données de test avec lequel on mesure la qualité du modèle (est-ce que le modèle prédit bien la classe d'une donnée ? ou dit autement, quelle est la probabilité que le modèle fasse une prédiction erronnée).

Nous pouvons maintenant induire l'arbre de décision. Il faut tout d'abord importer la fonction qui induit des arbres de décision avec from sklearn import tree, puis l'induction de l'arbre se fait comme quit :

arbre = tree.DecisionTreeClassifier()
arbre = arbre.fit (olivesX_train, olivesY_train)

La première ligne crée un objet arbre de décision et l'affecte à la variable dénommée arbre. La seconde induit l'arbre en utilisant les données et étiquettes du jeu d'entraînement.

À faire :

1. créer les 4 objets olivesX_train, olivesX_test, olivesY_train et olivesY_test.
2. Vérifier que la proportion des données de chacune des 3 classes est à peu près la même dans le jeu de données initial, dans le jeu de données d'entraînement et le jeu de données de test.
3. Induire un arbre de décision à partir de olivesX_train et olivesY_train. Il y a beaucoup de paramètres qui peuvent être réglés mais nous nous en tiendrons à leur valeur par défaut dans un premier temps (cf. ci-dessus).

Une fois un arbre de décision induit, on peut l'utiliser pour prédire la classe de données en utilisant la méthode predict (). Cette méthode prend simplement un tableau de données. Par exemple, arbre.predict (olivesX_train) calcule la classe prédite par l'arbre sur les données contenues dans le tableau de données olivesX_train.

Diagnostic de l'arbre de décision

Avant même de regarder à quoi l'arbre ressemble, il est important de commencer par déterminer si cet arbre est capable de prédire la classe de manière précise. On va donc estimer la probabilité qu'il commette une erreur lorsqu'il prédit la classe d'une donnée. Pour cela, on :

• utilise les données de test que l'on a mises de côté dans olivesX_test et olivesY_test,
• on utilise l'arbre pour prédire la classe des données contenues dans olivesX_test,
• on compare la classe prédite avec la classe de la donnée qui est dans olivesY_test.
• On divise le nombre d'erreurs de prédiction par le nombre de données de test : cela nous fournit une estimation de la probabilité d'erreur.

À faire : faites ce qui vient d'être expliqué. Quelle est la valeur de cette estimation ?

Il est intéressant de mesurer ce taux d'erreur pour chaque classe.
À faire : mesurer le taux d'erreur pour chaque classe. Les 3 classes sont-elles toutes les 3 prédites correctement avec la même probabilité ?

Interprétation d'un arbre de décision

On peut obtenir une visualisation de l'arbre de décision en faisant par exemple :

import matplotlib.pyplot as plt
fig, ax = plt.subplots ()
tree.plot_tree (arbre)
fig.show ()

qui ouvre une fenêtre avec le graphique suivant :

À faire : réalisez ce graphique et le comprendre. En particulier, comprendre ce qui est affiché dans chaque nœud.

Les tests réalisés à chaque nœud sont difficiles à comprendre. Pour afficher le nom des attributs, on ajoutera feature_names = list (olives_test) dans l'appel de la méthode plot_tree(). Et on obtient :

En consultant la documentation, on peut avoir une représentation plus jolie et informative avec la classe prédite qui est indiquée dans chaque feuille, comme celle-ci :

Faites-le.

Un arbre de décision peut facilement être transformé en un ensemble de règles de décision. Ici l'arbre est très petit, c'est facile.

À faire : quelles sont ces règles ? Interprétez graphiquement ces règles. Retrouvez-vous une observation faite précédemment ?

Test de l'arbre de décision

Nous avons construit un arbre de décision qui donne de très bons résultats. Est-ce juste de la chance ou est-ce que décidément, cette tâche se résout facilement à l'aide d'un arbre de décision ?

Pour apporter des éléments de réponse à cette question, on refait plusieurs fois la construction de l'arbre de décision en découpant le jeu de données aléatoirement à chaque fois. Par exemple, on peut refaire toute cette procédure 30 fois (ou 100, ...). Pour chaque arbre induit, on estime sa probabilité d'erreur de prédiction que l'on stocke. Une fois les 30 (ou 100, ...) constructions réalisées, on vérifie que la probabilité d'erreur varie, peu, un peu, beaucoup, ... Si elle varie peu, c'est très bon signe : tous les arbres induits ont à peu près la même précision, qui est très bonne pour la prédiction de la région d'origine de l'olive.

À faire : effectuer ce qui vient d'être expliqué. Que pensez-vous du résultat ?

La manière traditionnelle d'effectuer cela se nomme une validation croisée. Une validation croisée consiste à :

1. découper le jeu d'exemples en N parties stratifiées,
2. pour chacune des parties, induire un arbre en utilisant les N-1 autres parties et mesurer son erreur de prédiction sur la partie non utilisée dans l'entraînement.
3. faire la moyenne de ces erreurs.

Il faut importer la fonction par from sklearn.model_selection import cross_val_score. Elle s'utilise ensuite de la manière suivante :

>>> cross_val_score (arbre, olives.iloc [:, 3:olives.shape[1]], olives.iloc [:,1], cv = 10)
array([1.        , 1.        , 1.        , 1.        , 1.        ,
       1.        , 0.98245614, 1.        , 1.        , 1.        ])

On a fixé le nombre de parties N à 10 via le paramètre cv. La fonction affiche les 10 taux de succès mesurées sur chacune des 10 parties.
À faire : effectuer une validation croisée et comparer le résultat (erreur estimée) avec la valeur que vous avez obtenue précédemment.

Reproductibilité

Pour construire les jeux de données d'entraînement et de test, nous avons utilisé des nombres générés pseudo-aléatoirement. Si vous effectuez ce qui a été expliqué plus haut pour l'induction d'un arbre deux fois de suite, vous obtiendrez des résultats différents (dans le cas présent, la différence est petite). Il est important de pouvoir reproduire les résultats que vous avez obtenu. Pour cela, il faut que les nombres pseudo-aléatoires qui sont générés soient les mêmes d'une exécution à la suivante. Pour obtenir ce résultat, il faut initialiser la graine du générateur de nombres pseudo-aléatoires. On fait ainsi :

graine = int ("ScienceDesDonnees", base=36)%2**31
rs = np.random.RandomState (graine)

graine est un entier. La première ligne transforme une chaîne de caractères quelconque en un entier (à la place de ce qui est écrit, vous pouvez écrire tout simplement graine = 1234567 par exemple). Ensuite, on initialise le générateur de nombres pseudo-aléatoires.
Puis, lors de l'induction de l'arbre de décision, on passe celui-ci en paramètre :

DecisionTreeClassifier (random_state = rs)

Plus haut, quand on a découpé le jeu de données en jeu d'entraînement et jeu de test, on a spécifié un paramètre rs également qui joue le même rôle pour ce découpage que le paramètre random_state pour l'induction de l'arbre de décision. Pour obtenir le même découpage, il faut que le paramètre ait la même valeur (et que le jeu de données à partitionner soit identique).

À faire : effectuer l'initialisation de cette graine et refaites toute la procédure d'induction d'arbre. Estimer sa probabiité d'erreur. Si vous effectuez cela plusieurs fois, vous devez obtenir exactement le même résultat à chaque fois.

Prédiction de l'attribut area

Chaque région est décomposée en un ensemble d'aires (attribut area). On essaie maintenant de prédire l'aire, il y en a 8.

À faire :

• Refaites le même travail pour prédire l'attribut area.
• Arrive-t-on à bien prédire toutes les classes ? Aussi bien que la région ?
  Pour répondre à cette question, vous calculez l'erreur de test pour l'ensemble des exemples mais aussi, vous calculez cette erreur pour les exemples de chacune des 3 et 8 classes respectivement.
  Qu'en pensez-vous ?

Retour sur la prédiction de l'attribut region

L'arbre de décision construit plus haut commet parfois des erreurs. Nous allons voir une manière de réduire le risque d'erreur.
C'est une méthode très générale qu'il faut absolument connaître et utiliser lorsqu'on utilise des arbres de décision.
Nous allons procéder visuellement car cette manière de faire ne s'automatise pas facilement. Alors que parfois, comme on l'a déjà dit, il y a des choses qui sautent aux yeux.

L'arbre obtenu prédit parfaitement les olives du Sud de l'Italie ; on l'avait déjà vu. Par contre, il ne sépare pas parfaitement les deux autres régions, Nord et Sardaigne. On va donc se concentrer sur les olives de ces deux régions.
Pour cela et pour se simplifier la vie, on peut créer un objet olivesPasDuSud à l'aide d'un filtre logique : lesOlivesPasDuSud = olives.loc [:,"region"] != 1.
Ensuite, on fait des scatter plots de ces olives pour chaque paire d'attributs et en utilisant une couleur indiquant la région. On regarde ces graphiques et on essaie d'en identifier où les 2 olives des deux régions sont séparées. Rappelons-nous qu'un arbre de décision (comme ceux construits par l'algorithme disponible dans scikit-learn que nous utilisons) découpe l'espace de données avec des droites parallèles aux axes, ce qui correspond à des tests du type attribut ≤ valeur. Essayons de trouver une paire d'attributs permettant de séparer les deux classes par une droite.
Avec 8 attributs, nous obtenons 8x7/2 graphiques :


À faire : reproduisez ces 28 graphiques.

Il faut donc trouver un graphique où les points jaunes et les points violets peuvent être séparés par une droite quelconque. La figure ci-dessous illustre l'idée : les données des deux classes sont illustrées par les tâches colorées et on voit que l'on peut séparer les jaunes des bleus par une droite. N'étant ni horizontale ni verticale, cette droite ne peut pas être trouvée par l'algorithme de scikit-learn qui construit des arbres de décision. Par contre, cette droite nous saute aux yeux, ce qui montre encore une fois que l'être humain est bien supérieur à toutes les machines, même celles dont on prétend qu'elles sont intelligentes ;-)

Quand on a trouvé une telle paire d'attributs, on détermine l'équation d'une droite qui sépare les deux classes. Comment fait-on ? À l'œil, on détermine deux points par lesquels passent cette droite.
Son équation est de la forme : acideY = a acideX + b, où acideX est l'acide en abscisses, acideY celui en ordonnées, a et b les coefficients de la droite qu'il faut calculer.
Maintenant, on a une règle du genre : si la donnée est en dessous de la droite, alors la classe est bleue, sinon sa classe est jaune. Autrement dit, le signe de acideY - a acideX - b indique la classe.
Dès lors, il suffit d'ajouter un nouvel attribut au jeu de données qui a cette valeur (acideY - a acideX - b) et de construire un arbre de décision avec ce jeu de données augmenté. L'algorithme va utiliser cet attribut pour construire un arbre qui ne fait plus d'erreur, ou du moins, en fait moins. J'obtiens :

À faire : Faites tout cela et calculez l'erreur de test du nouvel arbre de décision (j'obtiens 0).

Plus généralement, notre cerveau est capable de repérer des séparatrices bien plus complexes qu'une simple droite : une courbe parabolique, de degré 3, une courbe en zigzag plus généralement, etc.
En guise d'exercice, supposons qu'il n'y ait pas de paire d'attributs séparant les jaunes des bleus (les olives du Nord de celles de Sardaigne).

À faire :

1. repérez une paire d'attributs qui semblent séparer les deux classes par une courbe du 2^nd degré.
2. Une courbe du 2^nd degré possède 3 coefficients. Cela signifie que nous avons 3 inconnues à déterminer, donc il nous faut 3 points pour les déterminer. À l'œil, déterminez 3 points par lesquels passent cette courbe du 2^nd degré.
3. Posez le problème mathématique à résoudre pour trouver ces 3 inconnues à partir des coordonnées de ces 3 points.
4. Le résoudre.
5. En déduire un attribut à ajouter au jeu de données et l'ajouter.
6. Construire l'arbre de décision avec ce nouveau jeu de données augmenté (n'utilisez pas l'attribut que nous avons précédemment ajouté correspondant à la séparatrice linéaire).
7. Calculez l'erreur de test de ce nouvel arbre de décision.

Autre question

Quand on dessine un arbre de décision, chaque nœud et feuille contient une ligne indiquant gini = .... Rappel : cette valeur dépend de l'ensemble d'entraînement, elle quantifie l'hétérognéité du jeu de exemples : si tous les exemples sont de la même classe, cette valeur est nulle. Elle vaut \( \sum_{c \in Classes} p_c (1 - p_c) \) où \( p_c \) est la proportion d'exemples appartenant à la classe \( c \). Elle se nomme l'« impureté de Gini ».
À faire : Calculez cette valeur « à la main » et vérifiez que vous obtenez la même valeur. Pour un problème à 2 classes, quelle est la valeur maximale de l'impureté de Gini ? et pour un problème à C classes ?