L’arbre de décision (Decision Tree) en Machine Learning

Temps de lecture : 7 minutes

L’arbre de décision (« decision tree » en anglais) : une méthode d’apprentissage simple, visuelle, facile d’interprétation et très utilisée dans les problèmes de classification ! C’est ce que je te propose de découvrir dans cet article.

Comme son nom le présage, c’est une méthode qui permet à partir de séquences de questions successives, de ranger une donnée en entrée dans une classe spécifique ou de prédire une valeur numérique en sortie. Si tu n’as rien compris, ce n’est pas grave 😅! Voyons comment ça marche sur un exemple concret ! Tu verras que le principe est tout simple. Prêt ? Grimpons à l’arbre (encore une blague facile, je sais) …

Cas d’étude simple : parlons séries télévisées !

Il y a quelques jours, on discutait de nos séries préférées avec des amis. Certains étaient de grands fans de « Friends » et d’autres de « How I met your mother (HIMYM) ». Puis, j’ai évoqué une série que j’ai découverte récemment : « Parks and Recreation (PR) ». Et chacun a exprimé sa position par rapport à cette dernière. Jusque-là, rien de bien particulier, n’est-ce-pas ? Je ne fais que raconter ma vie 😛! Sauf qu’en bon data scientist ambulant, je voulais savoir si on pouvait prédire si une personne aimerait PR en fonction de ses goûts pour Friends et HIMYM ! Là, ça devient intéressant ! Disons que les données que j’ai recueillies ressemblent à ceci :

L'arbre de décision en Machine Learning : données du cas d'étude
Description rapide des données

Comme tu peux le voir, j’ai 6 amis (ne me juge pas, c’est beaucoup 6 🙄!). Ils ont des goûts variés pour Friends et HIMYM et au final, 4 aiment PR et 2 n’aiment pas PR. Rappelle-toi, ce que nous voulons prédire ici, c’est « aime PR » ou « n’aime pas PR » à partir des deux informations que nous avons sur Friends et HIMYM.  Donc en récapitulatif, on a :

  • Variables d’entrée : « Aime Friends » (1 ou 0) et « Aime HIMYM » (1 ou 0) – pour rappel 1, c’est quand on aime et 0 c’est quand on n’aime pas.
  • Variable de sortie (ce qu’on veut prédire) : « Aime PR » (1 ou 0)
Principe de l’arbre de décision

C’est assez intuitif ! Pour répartir mes amis en les deux classes de PR, on va commencer par regarder par exemple si ceux qui aiment Friends aiment systématiquement PR ou non. Puis, quand on aura fait une première séparation à partir de cette question, on regardera comment la question « aime HIMYM » permet de séparer les nouveaux groupes… et ainsi de suite. Ici, nous n’avons que 2 variables en entrée, toutes de type catégoriel (0 ou 1) , ce qui fait que nous n’avons que 2 questions à poser. Mais le principe reste le même en présence de plusieurs variables. On aurait pu rajouter « aime Brooklyn 99 », « aime New Girl » … (c’est aussi des séries au cas où tu serais perdu.e 😉). Jusque-là, c’est plutôt simple, non ?

De fait, le plus difficile c’est de trouver la bonne séquence de questions i.e. est-ce qu’on commence par poser la question « aime Friends ? » ou « aime HIMYM » pour séparer les données ? Pas de panique 🙂! Il y a une règle générale à l’exercice : « on commence par la question qui sépare le mieux les données. Dans le jargon, c’est celle qui réduit le plus l’entropie ou l’impureté ». Pour faire simple, si j’ai une question qui me permet d’avoir un nouveau groupe où 100% des individus aiment PR et 0% n’aime pas PR et une autre question qui résulte en un 50% – 50%, je privilégie la première… Normal, c’est celle qui donne le groupe le plus pur ! Et pour respecter la terminologie du milieu, on désigne généralement le « groupe » plutôt par « feuille » (« leaf » en anglais).

En pratique, il existe plusieurs mesures mathématiques pour évaluer l’impureté d’une feuille. Mais la plus utilisée s’appelle l’indice de Gini. Mais ne perdons pas plus de temps sur la théorie ! Voyons comment la règle s’applique à notre cas d’étude.

Implémentation de l’arbre de décision

Ok, là, nous sommes au sommet de notre arbre (nœud principal). On peut effectuer la première segmentation en se basant soit sur la question « aime Friends ? » soit sur la question « aime HIMYM ?». En fonction de l’une ou l’autre, on aura les séparations suivantes (avec les effectifs respectifs) :

L'arbre de décision en Machine Learning : première question

Laquelle choisir pour commencer, 1 ou 2 ? C’est ici que rentre en jeu l’indice de Gini qui évalue l’impureté de chaque feuille. Pour une feuille i, l’indice de Gini est donné par :

Gini_i = 1 - {P_{oui}}^2 - {P_{non}}^2

P_{oui} est la probabilité d’avoir un oui et P_{non} est la probabilité d’avoir un non dans la feuille. En fait, quand tu analyses bien la formule, l’idée est simple. Quand tu n’as que des « non » ou que des « oui » dans la feuille (cas de la feuille 12 par exemple), l’indice de Gini est nul (feuille pure, sans mélange) et quand tu as 50% – 50% (feuille impure) ton indice est élevé et égal à 0.5.

Indice de Gini des feuilles

Maintenant que tu es familier avec l’indice de Gini, calculons-le pour chacune des 4 feuilles de nos arbres précédents :

  • Feuille 11 : Gini_{11} = 1 - {\frac{2}{4}}^2 - {\frac{2}{4}}^2 = 0.5
  • Feuille 12 : Gini_{12} = 1 - {\frac{2}{2}}^2 - {\frac{0}{2}}^2 = 0
  • Feuille 21 : Gini_{21} = 1 - {\frac{3}{4}}^2 - {\frac{1}{4}}^2 = 0.375
  • Feuille 22 : Gini_{11} = 1 - {\frac{1}{2}}^2 - {\frac{1}{2}}^2 = 0.5

Là, nous venons de calculer l’indice de Gini pour chacune des feuilles. Mais souviens-toi que ce qui nous intéresse, c’est l’impureté générée par chacune des questions de base pour pouvoir en choisir une.

Indice de Gini pour les questions

L’indice de Gini pour chacune des questions n’est en effet que la somme pondérée des indices de Gini des feuilles qu’elles ont générées. Ainsi on a :

  • Question 1 (« aime Friends ? ») : Gini_{1} = \frac{4}{6}Gini_{11} + \frac{2}{6}Gini_{12} = 0.33
  • Question 2 (« aime HIMYM ? ») : Gini_{2} = \frac{4}{6}Gini_{21} + \frac{2}{6}Gini_{22} = 0.42

On obtient l’impureté la plus faible pour la question « Aime Friends ? ». Elle sera donc notre première question ! Bingo 😀. A cette étape de l’analyse, notre arbre est donc :

L'arbre de décision en Machine Learning : première partie de l'arbre

Dans la feuille 12, on a réussi à segmenter les individus en « 100% aiment PR et O% n’aime pas PR » : la feuille est dite pure. On n’a plus besoin de poser d’autres questions. On s’arrête là ! Dans la feuille 11 par contre, on peut encore poser une question pour effectuer une seconde segmentation. Et la seule question qu’il reste c’est : « aime HIMYM ? ». Si on la pose à la suite, notre nouvel arbre ressemble à ceci :

L'arbre de décision en Machine Learning : arbre complet

Nos nouvelles feuilles ne sont pas pures mais on a posé toutes les questions donc on doit s’arrêter là ! Notre arbre de décision est prêt à être exploitée, youpiii 😀! Bien sûr, si on avait eu d’autres variables, le même principe « calcul des indices Ginis – choix du Gini le plus faible » s’applique jusqu’à ce qu’on pose toutes les questions ou qu’on obtienne des feuilles pures.

Exploitation de notre arbre de décision

Si on devait résumer notre arbre de décision en « langage humain », on aurait :

L'arbre de décision en Machine Learning : exploitation de l'arbre

Si je me fais désormais un nouvel ami, qui me fait part de ses positions par rapport à Friends et HIMYM, je n’aurai qu’à suivre mon arbre pour évaluer la chance qu’il a d’aimer PR ! Tu vois, je t’avais dit que c’était facile à mettre en œuvre et à exploiter 😉 !

Implémentation sur Python

Comme pour tous les sujets de Machine Learning sur lesquels j’ai écrit, Python offre une interface simple pour implémenter l’arbre de décision. On ira comme d’habitude chercher dans la librairie scikit-learn. Il faut néanmoins d’abord transformer nos « oui » en 1 et nos « non » en 0, puis utiliser la fonction DecisionTreeClassifier. Un code complet ressemblerait à :

from sklearn import tree
import numpy as np

X = np.array([[0,1],[1,0],[1,1],[0,1],[1,0],[1,1]]) # Variables d'entrée
y = np.array([1,0,1,1,1,0]) # Variable cible (sortie)

modele = tree.DecisionTreeClassifier() # Définition de l'arbre de décision
modele.fit(X,y) # Entrainement de l'arbre de décision sur nos données

# On peut désormais utiliser l'arbre pour prédire
modele.predict(np.array([[1,1]]))
Autres cas d’utilisation
Données numériques

Dans notre exemple, pour faire simple, j’ai utilisé uniquement des données en « oui » ou « non » (catégorielles). L’arbre de décision peut évidemment être appliquée sur des données numériques. Ici on aurait pu ajouter une autre variable « âge de mes amis » qui aurait un format numérique par exemple. Le principe reste le même. La seule différence c’est la façon dont on choisit la séquence des questions optimales à poser. Je pourrais écrire un autre article sur ça 😉.

Classification multi-classes

Toujours dans notre exemple, la variable de sortie est aussi quelque peu catégorielle (« aime » ou « n’aime pas »). Mais on peut avoir plus de 2 classes en sortie. Ça aurait pu être « aime », « aime modérément », « n’est pas très fan », « déteste » ! Dans tous les cas le principe reste le même et on obtient en bas de notre arbre, en sortie, les probabilités d’appartenir aux différentes classes.

Régression

Et enfin l’arbre de décision peut être utilisée pour effectuer des régressions. Au lieu de prédire des classes, on prédira donc plutôt des valeurs numériques. Les seules différences avec ce que j’ai présenté plus haut, sont la façon dont on calcule l’impureté et la façon dont on établit la valeur numérique finale. Et comme cet article est déjà suffisamment long comme ceci, la régression fera aussi l’objet d’un autre article.

Limitations de l’arbre de décision

Tu l’as vu, l’arbre de décision de par sa structure est facile d’utilisation. Les résultats sont aussi aisément interprétables. Son plus grand défaut est probablement l’overfitting c’est-à-dire qu’il est très dépendant des données sur lesquelles il a été entrainé. Quand on lui donne de nouvelles données, il peut donc avoir du mal à généraliser i.e. à prédire les bons résultats. En l’occurrence, plus l’arbre est profond (plusieurs niveaux), plus ce risque est élevé. Heureusement, il existe des solutions à ce problème notamment l’élagage de l’arbre (en anglais « pruning ») ou encore la combinaison de plusieurs arbres : c’est la forêt aléatoire (en anglais « random forest »)! Oui, je sais le nom donne des frissons dignes d’un film d’horreur 😨! Va donc chercher ton popcorn, parce qu’on aborde le sujet de la forêt aléatoire dans un autre article 😉!

Partager

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *