Arbre de décision, comment ça marche?

L’arbre de décision (decision tree en anglais) c’est un algorithme de machine learning facile et interprétable, idéal quand on débute en Data Science. Nous allons voir quels sont ses avantages et inconvénients, quand l’utiliser avec des explications simples sur son fonctionnement.

 

Qu’est ce qu’un arbre de décision ?

Les algorithmes de Decision tree, que l’on appelle également arbres de décision font partie de la catégorie des algorithmes supervisés, ils permettent de prédire une valeur (prédiction) ou une catégorie (classement).

C’est une méthode très populaire en Data Science et qui a donné naissance à d’autres algorithmes plus puissants tels que Random Forest ou XGBoost par exemple. Comme son nom l’indique, cet algorithme se base sur la construction d’un arbre ce qui rend la méthode assez simple à expliquer et plus facile à interpréter.

Quels sont les avantages et les inconvénients des decision trees ?

Avantages :

• Facile à comprendre : Le 1^er avantage de cet algorithme c’est qu’il est intuitif. Comme vous pourrez le voir dans les explications de son fonctionnement il est vraiment simple à comprendre. Et naturellement on a toujours tendance à préférer utiliser quelque chose que l’on comprend et que l’on maitrise.
• Facile à interpréter : Son 2^e avantage c’est qu’il est facile à interpréter. Les résultats peuvent être présentés à des équipes métier et les règles de décision produites par l’arbre sont faciles à comprendre.

• Temps d’exécution raisonnable. Enfin un dernier avantage qui peut avoir son importance, c’est un algorithme assez simple qui n’est pas très coûteux en temps de calcul.

Inconvénients :

• Faible performance. Le principal inconvénient des arbres de décision pour moi est le manque de performance par rapport à d’autres algorithmes. Mais il est parfois nécessaire de faire un choix entre performance et interprétabilité.
• Risque de sur-apprentissage : Deuxième inconvénient ou en tout cas un piège dans lequel il ne faut pas tomber… L’overfitting c’est-à-dire le sur-apprentissage (l’algorithme apprend avec tellement de précision les données d’entrainement qu’il ne parvient pas à généraliser un résultat satisfaisant sur de nouvelles données). Pour éviter cela il est important de bien élaguer son arbre de décision.

Quand utiliser un arbre de décision ?

Vous avez un projet de Data Science ou plus simplement d’analyse de données et vous vous demandez naturellement si vous pourriez utiliser cet algorithme ? Et oui comme je te comprends, les arbres de décision peuvent vraiment être une très bonne solution si vous êtes dans un des cas suivant :

• Utiliser un arbre de décision quand on est débutant. Pour construire un premier algorithme de classement, je recommanderais vraiment de commencer par celui. D’autant plus qu’il est nécessaire de d’abord bien le comprendre avant de passer à des méthodes plus complexes
• Utiliser un arbre de décision quand l’interprétabilité des résultats est plus importante que la performance. Dans certains cas les utilisateurs de l’algorithme veulent vraiment maitriser les règles qui permettent à l’algorithme de faire un choix. Par exemple dans le cas d’une segmentation client, il est souvent préférable d’avoir quelques règles de décision simples. Elles permettent aux équipes marketing de comprendre qui sont les clients qui composent chaque groupe. Par exemple si le client a fait plus de 3 achats avec un panier moyen supérieur à 100€ alors il appartient au segment Premium.
• Utiliser un arbre de décision quand l’algorithme ne peut pas être industrialisé tel quel. Certains outils et certaines infrastructures data (c’est de plus en plus rares heureusement) ne permettent pas d’industrialiser directement des algorithmes codés en Python, R (ou autres langages). Dans ce cas l’arbre de décision peut être converti en règles de décision qui pourront à leur tour être codées en sql.  

L’algorithme C4.5 basé sur l’entropie 

Apprentissage : Construction d’un arbre

Allez passons aux choses sérieuses, comment fonctionne un arbre de décision ?

Prenons un petit exemple… celui du Titanic pour lequel nous allons chercher à prédire la survie des passagers. C’est un classique et vous pouvez retrouver les données et vous entrainer sur Kaggle.

L’objectif de notre arbre de décision est donc de classer les passagers en 2 classes en fonction de leur survie (Survived=1) ou non (Survived=0).

Notre dataset compte 891 lignes et le taux de survie global est de 38%.

1ère étape : L’algorithme prend tous les individus (891 dans notre cas) et recherche la variable qui sépare le mieux les 2 populations. Pour faire son choix l’algorithme va tester chaque variable et utilise une métrique pour faire son choix (ici on utilise l’entropie et je t’explique ça plus en détail juste après).

Dans notre exemple c’est la variable « Sex » qui obtient la meilleure entropie lors de cette 1ere étape. L’arbre de décision sépare donc les hommes et les femmes et voilà ce que nous obtenons :

Au global, dans la population les chances de survie sont de 38%. En séparant les hommes et les femmes on voit déjà une différence significative. En effet les femmes ont une chance de survie de 72% tandis que les hommes ont seulement 19% de chance de s’en sortir.

Notre arbre de décision a maintenance 2 feuilles.

Itération : L’algorithme va continuer sa phase d’apprentissage en reprenant chaque feuille et en cherchant la variable qui permet de séparer au mieux les 2 classes.

Calcul de l’entropie

Vous avez compris le fonctionnement global de l’arbre de décision, regardons maintenant comment se calcule l’entropie.

Pour connaitre l’entropie d’un découpage, il suffit de faire la somme de l’entropie de chaque feuille pondérée par la proportion d’individus dans chaque feuille.

On commence par la formule de l’entropie :

Donc pour la feuille « Hommes » ça donne :

En calculant de la même manière pour la feuille « Femmes », on obtient une entropie de 0,82.

Finalement pour connaitre l’entropie du découpage par la variable Sexe on obtient : 577/891 * 0,69 + 314/891 * 0,82 = 0,73

Eviter le sur-apprentissage grâce à l’élagage de l’arbre

Comme je te le disais un peu plus haut, un des inconvénients de cette méthode c’est le risque de sur-apprentissage. On peut laisser l’algorithme se déployer au maximum pour coller parfaitement au dataset d’entrainement. Dans ce cas là la performance de l’algorithme sur les données qui ont permis de le créer sera excellente. En revanche il se généralisera très mal sur de nouvelles données. Ce n’est pas ce que nous cherchons.

Pour éviter cela il est nécessaire d’avoir un arbre par trop grand. C’est là que l’élagage intervient. Cette méthode consiste simplement à supprimer des branches et des feuilles de l’arbre.

Comment affecter une classe à chaque feuille ?

La phase d’apprentissage de l’arbre de décision est maintenant terminée. On obtient ce résultat (version simplifiée évidemment, les arbres sont rarement aussi peu profonds dans la réalité) :

 

Les feuilles ne seront presque jamais pures à 100% mais nous avons besoin qu’un choix soit fait pour chaque feuille. Pour une problématique de classement, c’est assez simple, l’algorithme affecte à chaque feuille la classe la plus représentée.

 

Bravo votre arbre de décision est terminé. Vous allez pouvoir maintenant l’appliquer sur de nouvelles données.

Comment utiliser un arbre de décision sur de nouvelles données ?

Dans la vraie vie lorsque l’on créé un algorithme c’est pour pouvoir l’appliquer ensuite sur de nouvelles données plus récentes. Dans ce cas comment fonctionne l’arbre de décision ?

Très simplement, chaque individus va suivre un certain parcours dans l’arbre jusqu’à arriver sur une feuille. La prédiction pour cet individu sera alors la classe de la feuille.

Petit exemple pour un garçon de 5 ans qui sera classé en Survived avec notre arbre de décision du Titanic :

 

Quelques conseils pour finir ?

J’utilise principalement les arbres de décision après un clustering pour affecter chaque individu à un groupe. Cela permet aussi de pouvoir implémenter facilement l’algorithme avec de simples requêtes SQL. Je les dessine toujours sur papier pour vérifier qu’ils sont assez simples, logiques et surtout compréhensibles.

L’arbre de décision est plutôt simple, il faut l’utiliser si vous avez besoin de règles de décision simple. Pour les problématiques de prédiction, on utilisera plutôt les algorithmes de Random Forest. Ils sont un cas particulier de Bagging appliqué à l’algorithme de decision tree.

Et pour aller plus loin :