Decision tree, comment ça marche?

Decision TreeDans cet article, je vous explique simplement comment fonctionne un arbre de décision (decision tree) Quand et comment l’utiliser, c’est par ici …

Les 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).

Le principe des arbres de décision

L’arbre de décision c’est une méthode très populaire en datamining et que j’apprécie beaucoup parce qu’elle est assez intuitive et donne des résultats faciles à implémenter. Dans le cas du classement, l’algorithme permet d’affecter chaque individu à une catégorie à l’aide de règles de décision. D’un point de vue métier c’est idéal puisque les règles sont clairement identifiées et il n’y a pas d’effet boîte noire que nous pourrions avoir par exemple avec des réseaux de neurones.

Encore un point positif pour cette méthode, les résultats peuvent être représentés visuellement, justement sous forme d’arbre (arbre de décision, représentation sous forme d’arbre… logique non? ).

Comment fonctionne l’algorithme ?

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

L’objectif de notre arbre de décision est donc de classer les passagers en 2 classes en fonction de leur survie ou non. A chaque étape, l’algorithme va chercher le critère permettant de séparer au mieux ces 2 populations. Il existe plusieurs critères de séparation, dans notre exemple nous allons utiliser l’entropie qui est utilisée pour les arbres C4.5.

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.

Prenons l’exemple de la variable « Sex » qui est celle qui obtient la meilleure entropie lors de la 1ère étape. On sépare les hommes et les femmes, voilà ce que nous obtenons :

Decision Tree Etape 1
Decision Tree Etape 1

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

C’est l’entropie qui nous a permis de choisir la variable « Sex » comme critère de découpage. Vous pouvez le voir comme un critère de pureté qui cherche a isoler les survivants et les non survivants dans des feuilles différentes de l’arbre.

Calcul de l’entropie

Voici la formule de l’entropie avec comme exemple la feuille « homme »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. Dans notre cas on ferait 843/1309 * Entropie_Homme + 466/1309*Entropie_Femme.

L’algorithme va continuer ainsi à scinder les feuilles pour minimiser l’entropie.

Elagage pour éviter le sur-apprentissage

On peut réaliser une phase d’élagage pour simplifier l’arbre obtenu et limiter le risque de sur-apprentissage (l’algorithme généralise mieux le phénomène à prédire).

Affectation d’une classe à chaque feuille

Une fois l’arbre terminé, l’algorithme affecte à chaque feuille la classe la plus représentée. Il ne vous reste plus qu’à comprendre l’arbre, vérifier que tout est cohérent d’un point de vue métier. On préférera d’ailleurs un arbre qui statistiquement est moins performant s’il a plus de sens d’un point de vue métier.

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

Pour la prédiction, préférez les algorithmes de Random Forest

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 qui sont un cas particulier de Bagging appliqué à l’algorithme de decision tree.

 

 

 

 

 

 

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion /  Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion /  Changer )

w

Connexion à %s