Arbres de décision — entropie, Gini et forêt aléatoire

Un arbre de décision prédit en posant une suite de questions comme « quiz d’entraînement terminé ? » ou « revenu supérieur à $50{,}000$ ? ». Dans un arbre de classification, la meilleure question est généralement celle qui rend les nœuds enfants moins mélangés que le nœud parent. C’est là qu’interviennent l’entropie et l’impureté de Gini.

Les forêts aléatoires utilisent la même idée de base, mais elles font la moyenne de nombreux arbres au lieu de faire confiance à un seul arbre isolé. Si vous ne retenez que l’essentiel, souvenez-vous de ceci : l’entropie et Gini aident un arbre à choisir ses divisions, et une forêt aléatoire aide à réduire l’instabilité d’un arbre unique.

Entropie et Gini dans les arbres de décision : ce qu’elles mesurent

L’entropie et l’impureté de Gini sont deux façons d’évaluer à quel point un nœud de classification est mélangé.

Si un nœud contient des probabilités de classe $p_1, p_2, \dots, p_k$, alors une formule courante pour l’entropie est

$$H = -\sum_{i=1}^k p_i \log_2 p_i$$

Cette formule est utilisée pour les arbres de classification. La base du logarithme change l’échelle, mais elle ne change pas le classement des meilleures divisions.

L’impureté de Gini est

$$G = 1 - \sum_{i=1}^k p_i^2$$

Les deux scores valent $0$ lorsqu’un nœud est parfaitement pur. Les deux augmentent lorsque les classes sont davantage mélangées.

En pratique, l’entropie et Gini classent souvent les divisions candidates de manière similaire. L’entropie a une interprétation directe en théorie de l’information, tandis que Gini est légèrement plus simple à calculer.

Comment un arbre de décision choisit une division

Pour l’entropie, une règle courante est le gain d’information :

$$\text{Information Gain} = H(\text{parent}) - \sum_j \frac{n_j}{n} H(\text{child}_j)$$

Ici, $n$ est le nombre d’exemples dans le nœud parent et $n_j$ est le nombre d’exemples dans le nœud enfant $j$.

Pour Gini, l’idée est parallèle : on calcule l’impureté pondérée des nœuds enfants et on préfère la division qui la réduit le plus.

La condition est importante : l’entropie et Gini sont standards pour les arbres de classification. Un arbre de régression utilise généralement une autre règle, comme la réduction de variance, car la cible est numérique plutôt que catégorielle.

Exemple détaillé : entropie et Gini pour une division

Supposons qu’un nœud contienne $6$ exemples d’entraînement pour une prédiction réussite/échec :

• $3$ sont Réussite
• $3$ sont Échec

Le nœud parent est donc parfaitement équilibré.

Son entropie est

$$H_{\text{parent}} = -\frac{3}{6}\log_2\left(\frac{3}{6}\right) - \frac{3}{6}\log_2\left(\frac{3}{6}\right) = 1$$

Son impureté de Gini est

$$G_{\text{parent}} = 1 - \left(\frac{3}{6}\right)^2 - \left(\frac{3}{6}\right)^2 = 0.5$$

Testons maintenant la division « quiz d’entraînement terminé ? »

• Branche Oui : $4$ exemples, avec $3$ Réussite et $1$ Échec
• Branche Non : $2$ exemples, avec $0$ Réussite et $2$ Échec

Pour la branche Oui,

$$H_{\text{yes}} = -\frac{3}{4}\log_2\left(\frac{3}{4}\right) - \frac{1}{4}\log_2\left(\frac{1}{4}\right) \approx 0.811$$

et

$$G_{\text{yes}} = 1 - \left(\frac{3}{4}\right)^2 - \left(\frac{1}{4}\right)^2 = 0.375$$

Pour la branche Non, le nœud est pur, donc

$$H_{\text{no}} = 0, \qquad G_{\text{no}} = 0$$

L’entropie pondérée après la division est

$$\frac{4}{6}(0.811) + \frac{2}{6}(0) \approx 0.541$$

Le gain d’information est donc

$$1 - 0.541 \approx 0.459$$

L’impureté de Gini pondérée après la division est

$$\frac{4}{6}(0.375) + \frac{2}{6}(0) = 0.25$$

La diminution de Gini est donc

$$0.5 - 0.25 = 0.25$$

Les deux mesures indiquent que cette division est meilleure que de laisser le nœud parent non divisé, car l’impureté pondérée diminue dans les deux cas.

Pourquoi les arbres de décision sont intuitifs

Un arbre est facile à lire parce qu’il reflète la manière dont les gens expliquent souvent une décision : « si ceci est vrai, aller à gauche ; sinon, aller à droite ». Cela rend les arbres utiles lorsque vous avez besoin d’un modèle que l’on peut inspecter, expliquer ou transformer en règles lisibles par un humain.

Ils sont aussi flexibles. Un arbre peut capturer des relations non linéaires et des interactions entre variables sans imposer une seule équation globale à l’ensemble du jeu de données.

Pourquoi les forêts aléatoires fonctionnent souvent mieux

Un arbre unique est facile à interpréter, mais il peut être instable. Une petite modification des données peut produire un arbre sensiblement différent.

Une forêt aléatoire réduit cette instabilité en construisant de nombreux arbres au lieu d’un seul. La recette habituelle est :

• échantillonner les données d’entraînement avec remise pour chaque arbre
• ne considérer qu’un sous-ensemble aléatoire de variables à chaque division
• combiner les prédictions de tous les arbres

Pour la classification, la forêt prédit généralement par vote majoritaire. Pour la régression, elle fait généralement la moyenne des sorties des arbres.

Le compromis est simple. Une forêt aléatoire est souvent plus précise et plus stable qu’un arbre unique, mais elle est plus difficile à expliquer comme un ensemble unique de règles claires.

Erreurs fréquentes avec les arbres de décision

Considérer l’entropie et Gini comme deux types de prédiction différents

Ce sont des critères de division, pas des familles de modèles distinctes. Dans les deux cas, le modèle reste un arbre de décision.

Oublier la condition de classification

L’entropie et Gini sont standards pour les arbres de classification. Si la cible est numérique, l’arbre utilise généralement à la place une règle fondée sur la variance ou sur l’erreur.

Chercher une pureté parfaite trop profondément

Si vous continuez à diviser jusqu’à ce que chaque feuille soit presque parfaite sur l’ensemble d’entraînement, l’arbre peut surapprendre. Les limites de profondeur, les tailles minimales de feuille ou l’élagage existent pour une bonne raison.

Supposer qu’une forêt aléatoire s’explique d’elle-même

Une forêt prédit souvent mieux, mais elle est moins transparente qu’un arbre unique. Si l’interprétabilité est la contrainte principale, un arbre unique soigneusement contrôlé peut rester le meilleur outil.

Quand utiliser un arbre de décision ou une forêt aléatoire

Les arbres de décision apparaissent dans des tâches de classification et de régression en finance, en médecine, en opérations, en marketing et dans bien d’autres contextes appliqués. Ils sont utiles lorsque la relation entre les entrées et les sorties n’est pas bien décrite par un modèle linéaire et lorsque des explications sous forme de règles sont importantes.

Utilisez un arbre unique lorsque l’interprétabilité compte le plus et que vous devez examiner le chemin de décision. Utilisez une forêt aléatoire lorsque la qualité de prédiction et la stabilité comptent davantage que le fait d’avoir un seul arbre compact lisible ligne par ligne.

Essayez un problème similaire

Prenez un petit jeu de données étiqueté avec deux classes et testez deux premières divisions possibles. Calculez les proportions de classes dans chaque nœud enfant, puis comparez l’entropie pondérée ou le Gini pondéré. Résoudre un petit cas à la main est souvent la manière la plus rapide de bien comprendre la logique des divisions.