TP 3 : Arbres de décision

Introduction

Une tâche important en IA est de pouvoir classifier des objets : reconnaître des images, détecter des spams, trouver la famille d’une plante etc. Souvent, on ne sait pas vraiment définir explicitement une fonction permettant de classifier un objet. En effet, le processus que nous utilisons mentalement pour reconnaître un chat sur une image est difficile à décrire et d’autant plus à implémenter sur une machine pour laquelle une image n’est rien d’autre, au départ, qu’un tableau de nombres : on repère des formes, les yeux et la tête, on regarde la forme des oreilles etc. Autant de concepts qu’il faudrait réussir à formaliser dans un programme.

On va s’intéresser ici à l’apprentissage automatique d’une fonction de classification à partir d’exemples en utilisant une famille d’hypothèses appelées arbres de décision. On va voir comment utiliser les arbres de décision pour apprendre à classifier depuis des exemples, comment on peut mettre cet apprentissage en place avec python en utilisant la librairie scikit learn pour apprendre un arbre de décision depuis un jeu de données et comment évaluer la qualité de la fonction apprise par cross validation.

Arbres de décision

Un arbre de décision est une structure de données permettant de classifier des vecteurs de données la forme (x₁,…,x_n) ∈ D₁ × … × D_n dans des classes 𝒞 en répondant à une succession de questions. On utilise parfois leurs cousins, les flowcharts, pour expliquer le fonctionnement de certains systèmes (voir par exemple l’excellent SMBC Comics expliquant que l’IA détruira l’humanité). Les arbres de décision sont des structures de données particulièrement adaptée pour les problèmes de décision faisant intervenir des attributs qui prennent un nombre de valeur finie. Ils ont aussi l’avantage d’être facilement compréhensible par un humain : on peut exactement voir comment un arbre de décision arrive à une conclusion depuis un vecteur de données. On dit souvent qu’ils sont, en ce sens, interprétables. Cette affirmation est cependant rarement formalisée et à prendre avec des pincettes, la façon un arbre prend ses décisions a toutefois été apprise sur des données et il reste difficile d’y détecter des biais.

Formellement, un arbre de décision T est un arbre dont les noeuds internes sont étiquettés par des questions de la forme x_i = v, x_i ≤ v ou x_i ≥ v et les noeuds terminaux sont étiquetés par une classe c ∈ 𝒞. Chaque noeud a deux fils : un fils négatif, représenté à droite, et un fils positif, représenté à gauche. Étant donné un vecteur x = (x₁,…,x_n) de valeurs, T classifie x dans une classe c ∈ 𝒞 si on arrive dans une feuille étiquetée par c en suivant le processus suivant :

• On commence par la question qui se trouve à la racine de l’arbre : si la réponse à la question (de la forme x_i = v ou x_i ≤ v ou x_i ≥ v) est vrai pour le vecteur x, on descend dans le fils gauche, sinon dans le fils droit.
• On continue à répondre aux questions jusqu’à atteindre une feuille de l’arbre.
• Lorsqu’une feuille étiquetée par c est atteinte, on retourne c.

Par exemple, dans l’exemple suivant, un vecteur {"couleur": "jaune", "poids": "200g", "taille": "20cm", "diamQueue": "1cm"} sera classé en tant que banane. En effet, on commencera par descendre à droite puisque la couleur n’est pas verte, puis à gauche (la couleur est jaune) puis à droite (la taille est plus grande que 15cm). Vous pouvez passer votre souris sous l’image ci-dessous pour voir le chemin se colorer.

Classifier des iris !

Dans cette partie, on va s’intéresser à un jeu de données classique pour les arbres de décision : le jeu de données IRIS. Ce jeu de données contient des exemples d’iris classés en trois espèces : les iris setosa, versicolor et virginica. Les attributs qui sont utilisés dans le jeu de données sont : la longueur et largeur des pétales, la longeur et la largeur des sépales.

On peut trouver une version du jeu de données au format ARFF sur OpenML, ou au format CSV. Il existe de nombreux formats de fichiers pour échanger des jeux de données (ARFF, CSV, svmlight etc.). La plupart des librairies pour l’apprentissage vous permettra d’importer sans trop de problème les données depuis différents formats dans leur format local. Il faut cependant garder à l’esprit que la constitution de tels jeux de données et leur normalisation est en général un travail fastidieux mais nécessaire pour l’apprentissage. Nous utiliserons ici le fait que Scikit Learn propose déjà une fonction pour charger le jeu de données IRIS afin de faciliter la manipulation.

La librairie Scikit Learn

La libriaire Scikit Learn en python vous permet de mettre facilement en place des solutions utilisant l’apprentissage. Cette librairie est très riche et nous l’utiliserons plusieurs fois dans ce cours. Nous proposons ici de découvrir certaines de ses nombreuses fonctionnalités.

On va charger le jeu de données. Ce jeu de données est très populaire et on peut donc le charger directement depuis la librairiescikit-learn. En général, on dispose du jeu de données dans un fichier externe qu’on doit charger. Nous n’aborderons pas cet aspect aujourd’hui.

Pour importer la fonction dont on a besoin et charger le jeu de données, on écrira au début de notre fichier :

from sklearn.datasets import load_iris

iris = load_iris()

On remarque que iris.data et iris.target ont le même nombre de lignes. Ce qu’il faut donc comprendre c’est que iris.data[i] contient tous les attributs d’un vecteur exemple et iris.target[i] contient sa classe. On remarque que ces tableaux ne contiennent que des chiffres et qu’on ne voit pas à quoi ils correspondent. On trouvera les détails dans les tableaux iris.feature_names et iris.target_names.

Ce qu’il faut comprendre c’est que la classe qui a le numéro i a le nom iris.target_names[i]. Pareillement, l’attribut en position i a le nom iris.feature_names[i]. Par exemple :

print(iris.feature_names)
>>> ['sepal length (cm)', 'sepal width (cm)', 'petal length (cm)', 'petal width (cm)']

print(iris.data[0])
>>> [5.1 3.5 1.4 0.2]

Cela nous indique que la première ligne du jeu de données (iris.data[0]) contient un exemple d’iris dont la longueur des sépales est 5.1cm, la largeur des sépales est 3.5cm, la longueur des pétales est 1.4cm et la largeur des pétales est 0.2cm. De plus :

print(iris.target[0])
>>> 0

print(iris.target_names)
>>> ['setosa' 'versicolor' 'virginica']

Cela nous indique que la classe de la première ligne du jeu de donnée (iris.target[0]) est de classe 0, c’est-à-dire, "setosa".

On va essayer de visualiser les données. Pour cela, nous allons utiliser la librairie python matplotlib.

On va regarder la répartition de la longueur des sépales en fonction de la largeur des sépales :

ax = plt.subplot() # nécessaire pour tracer des points

# On trace des points dont l'absisse est la longueur des sépales, l'ordonnée la largeur
scatter = ax.scatter(iris.data[:,0], iris.data[:,1], c=iris.target) 

#     - iris.data[:,0] veut dire le premier élément de chaque 
#       tableau de iris.data, soit la longueur des sépales
#     - iris.data[:,1] veut dire le deuxième élément de chaque 
#       tableau de iris.data soit la largeur des sépales
#     - c=iris.target force la couleur en fonction de la classe (iris.target)

# On met en forme le diagramme
ax.set(xlabel="Longeur des sépales", ylabel="Largeur des sépales") # nom des axes
ax.legend(scatter.legend_elements()[0], iris.target_names, loc="lower right", title="Classes") # légende
plt.show() # on affiche !

On obtient :

Si vous souhaitez sauvegarder une image, vous pouvez remplacer plt.show() par plt.savefig("nom.png").

Vous devriez générer l’image suivante :

Apprendre un arbre de décision

On va utiliser Scikit Learn pour générer un arbre de décision ayant appris à classifier depuis les exemples du jeux de données. On ne rentrera pas ici dans les détails de l’algorithme d’apprentissage pour nous concentrer sur la mise en pratique de la solution. On peut donner quand même une intuition du fonctionnement de ces algorithmes. L’algorithme d’apprentissage commence par construire la racine de l’arbre. Il va essayer de trouver une question x_i = v, x_i ≤ v, x_i ≥ v qui découpe le “mieux” le jeu de données, c’est-à-dire qu’on va essayer de trouver la question qui discrimine le plus les différentes classes. Pour évaluer cela, on utilise en général une méthode qui évalue le degré de mélange des classes. Il en existe principalement deux : l’entropie et la fonction de Gini. Pour un jeu de donné D ayant N exemples dont N_c éléments classé dans la classe c ∈ C et donc une proportion P_c = N/N_c éléments de classe c, on définit Gini(D) = 1 − ∑_c ∈ CP_c² et entropy(D) =  − ∑_c ∈ CP_clog (P_c). Intuitivement, ces fonctions sont maximales quand les proportions de chaque classe sont similaires. Si une classe c a une proportion plus importante que les autres, alors P_c sera proche de 1 et les autres seront proche de 0. On voit alors que Gini(D) et entropy(D) seront petites. On va essayer de privilégier les questions qui séparent le jeu de donnée en D₁ et D₂ avec un petit degré de mélange. On appliquera la construction récursivement sur D₁ et D₂ ensuite pour construire un arbre complet jusqu’à ce qu’on décide qu’une classe est suffisamment représenté pour décider que tous les éléments sont dans cette classe. Cela est résumé ci-dessous :

Si on se contente de cette méthode d’apprentissage, on risque cependant de surapprendre notre modèle sur les exemples (overfitting) ce qui donnerait des arbres de décision mauvais en pratique sur des vecteurs en dehors de l’ensemble des exemples. La plupart des algorithmes d’apprentissage des arbres de décisions passent ensuite par une phase d’élagage : certains sous-arbres qui semblent être trop spécialisés aux exemples sont enlevés afin de mieux généraliser.

Dans ce TP, nous allons faire confiance aux développeurs de Scikit Learn et utiliser leur implémentation des arbres de décisions.

On importera les fonctions nécessaires avec :

from sklearn.tree import DecisionTreeClassifier, plot_tree

On crée un arbre de décision avec

clf = DecisionTreeClassifier()

Et on l’entraînera sur les exemples avec fit. On lui passera comme argument un tableau contenant les données et un tableau contenant les classes :

clf.fit(donnees, classes)

Enfin, on affichera l’arbre calculé avec la fonction plot_tree. noms_attributs est un tableau contenant le nom des attributs et noms_classes est un tableau contenant le nom des classes, ce qui permet d’avoir un affichage un peu plus lisible :

plt.figure(figsize(20,20)) # zoom pour rendre l'arbre plus lisible 
                           # changer en fonction de la taille de votre écran.
plot_tree(clf, feature_names=noms_attributs, class_names=noms_classes, filled=True, rounded=True)
plt.show()

On peut utiliser clf.predict(t) pour trouver la classe de plusieurs point d’entrée (t est un tableau de vecteurs d’attributs, par exemple [[10,4,5,0.1], [12,1,5,1]].

Évaluation du modèle

Le problème avec l’approche précédente est que l’on a utilisé toutes les données à notre disposition pour entraîner notre modèle. On n’a donc aucun moyen de vérifier la qualité de notre modèle. L’approche la plus simple pour résoudre cela est d’utiliser une partie des données pour apprendre et une autre partie des données pour vérifier la qualité du modèle. Pour que cela ait du sens, il faut choisir la partition des données de façon aléatoire, sinon on risque de biaiser notre modèle.

Scikit Learn nous permet facilement de créer ce genre de partition. On utilisera pour cela la fonction train_test_split :

from sklearn.model_selection import train_test_split
donnees_train, donnees_test, classes_train, classes_test = train_test_split(donnees, classes, test_size=0.2, random_state=42)

Cela permet de créer une partition des données et de leur classe en une partie apprentissage et une partie entrainement. Dans l’exemple ci-dessus, on prélève 20% des données pour faire nos tests.

On peut calculer la précision d’un modèle avec la fonction suivante :

from sklearn import metrics
accuracy = metrics.accuracy_score(classe_test, classe_predites)

Aller plus loin

On a vu ici, d’un bout à l’autre, comment apprendre un arbre de décision et évaluer sa précision. Une autre approche pour évaluer sa précision serait de faire de l’évaluation croisée, pour comprendre si le modèle qu’on a choisi est un bon modèle : on entraîne le modèle sur toutes les données, mais on le valide comme suit : on partitionne les données S en k ensembles S₁, …, S_k de même taille. On entraîne k modèles T₁, …, T_k : T_i est entraîné sur les données S \ S_i et on calcule sa précision e_i en testant sur S_i. On retourne ∑_ie_i/k comme estimation de l’erreur du modèle.