Construisez un arbre de décision

Un médecin qui pose un diagnostic procède souvent par questions successives : « Avez-vous de la fièvre ? Oui. Depuis plus de trois jours ? Non. » Un arbre de décision fait exactement cela : il enchaîne des questions simples sur les caractéristiques jusqu’à une réponse. C’est l’un des modèles les plus lisibles qui soient, et la brique de base des forêts aléatoires et du boosting (chapitre 8).

Mais parmi toutes les questions possibles, laquelle poser en premier ? Et quand s’arrêter ? C’est ce que vous allez apprendre ici, sur un exemple minuscule que vous pourrez refaire à la main.

Le fil rouge : jouer ou ne pas jouer ?

Un club de tennis a noté, pendant 14 jours, la météo et si les membres sont venus jouer. C’est un jeu de données classique de l’apprentissage automatique, que nous avons aussi utilisé en TP (weather.nominal) :

Jour	Ciel	Température	Humidité	Vent	Jouer ?
1	ensoleillé	chaud	élevée	non	non
2	ensoleillé	chaud	élevée	oui	non
3	couvert	chaud	élevée	non	oui
4	pluvieux	doux	élevée	non	oui
5	pluvieux	frais	normale	non	oui
6	pluvieux	frais	normale	oui	non
7	couvert	frais	normale	oui	oui
8	ensoleillé	doux	élevée	non	non
9	ensoleillé	frais	normale	non	oui
10	pluvieux	doux	normale	non	oui
11	ensoleillé	doux	normale	oui	oui
12	couvert	doux	élevée	oui	oui
13	couvert	chaud	normale	non	oui
14	pluvieux	doux	élevée	oui	non

Il y a 9 « oui » et 5 « non ». L’objectif : construire un arbre qui prédit « Jouer ? » à partir des quatre caractéristiques.

Un arbre de décision se compose de nœuds internes (chacun teste une caractéristique), de branches (une par réponse possible) et de feuilles (qui donnent la classe prédite). Pour classer un nouveau jour, on part de la racine et on suit les réponses jusqu’à une feuille. Chaque chemin de la racine à une feuille se lit comme une règle : « si le ciel est ensoleillé et l’humidité élevée, alors on ne joue pas ».

Mesurer le désordre d’un nœud : l’entropie

Une bonne question est une question qui trie les exemples : après elle, chaque groupe devrait être le plus homogène possible. Pour mesurer l’hétérogénéité (on dit l’impureté) d’un groupe, on utilise l’entropie de Shannon :

$$H(Y) = -\sum_{k=1}^{K} p_k \log_2 p_k$$

• $K$ est le nombre de classes (ici 2 : oui et non) ;
• $p_k$ est la proportion d’exemples de la classe $k$ dans le groupe ;
• $\log_2$ est le logarithme en base 2, et on convient que $0 \log_2 0 = 0$.

L’entropie vaut 0 quand le groupe est pur (une seule classe) et atteint son maximum, $\log_2 K$, quand toutes les classes sont également représentées (1 pour deux classes à 50/50). Intuitivement, c’est le nombre moyen de questions oui/non qu’il faudrait poser pour deviner la classe d’un exemple tiré au hasard.

Exemple

À la racine, on a 9 « oui » et 5 « non » sur 14 jours :

$$H = -\tfrac{9}{14}\log_2 \tfrac{9}{14} - \tfrac{5}{14}\log_2 \tfrac{5}{14} \approx 0{,}410 + 0{,}530 = 0{,}940$$

Le groupe est assez mélangé (on est proche du maximum de 1).

Il existe une autre mesure d’impureté très répandue, l’indice de Gini : $G = 1 - \sum_k p_k^2$. Il vaut aussi 0 pour un groupe pur ; à la racine, $G = 1 - (9/14)^2 - (5/14)^2 \approx 0{,}459$. C’est le critère par défaut de scikit-learn (et de l’algorithme CART). En pratique, entropie et Gini choisissent presque toujours les mêmes questions.

Les deux mesures sont nulles pour un nœud pur et maximales pour un mélange 50/50. Elles ont la même forme, à un facteur près : c'est pourquoi elles choisissent presque toujours les mêmes questions.

Choisir la meilleure question : le gain d’information

Pour évaluer une question, on regarde l’impureté après la question, en moyenne sur les branches pondérées par leur taille. C’est l’entropie conditionnelle :

$$H(Y \mid A) = \sum_{v} P(A = v) \, H(Y \mid A = v)$$

où $A$ est la caractéristique testée, $v$ parcourt ses valeurs possibles, $P(A = v)$ est la proportion d’exemples qui prennent la branche $v$, et $H(Y \mid A = v)$ l’entropie du groupe dans cette branche. Le gain d’information est la baisse d’entropie apportée par la question :

$$G(A) = H(Y) - H(Y \mid A)$$

On choisit la caractéristique de gain maximal, c’est-à-dire d’entropie conditionnelle minimale.

Exemple

Calculons le gain de la caractéristique « Ciel ».

• Ensoleillé : 5 jours, 2 oui et 3 non, entropie $\approx 0{,}971$.
• Couvert : 4 jours, 4 oui, entropie $0$ (pur !).
• Pluvieux : 5 jours, 3 oui et 2 non, entropie $\approx 0{,}971$.

$$H(Y \mid \text{Ciel}) = \tfrac{5}{14} \times 0{,}971 + \tfrac{4}{14} \times 0 + \tfrac{5}{14} \times 0{,}971 \approx 0{,}694$$

Le gain vaut donc $0{,}940 - 0{,}694 \approx 0{,}247$.

En faisant le même calcul pour les quatre caractéristiques, on obtient :

Caractéristique	Répartition (oui/non) par valeur	$H(Y \mid A)$	Gain
Ciel	ensoleillé 2/3, couvert 4/0, pluvieux 3/2	0,694	0,247
Humidité	élevée 3/4, normale 6/1	0,788	0,152
Vent	non 6/2, oui 3/3	0,892	0,048
Température	chaud 2/2, doux 4/2, frais 3/1	0,911	0,029

Chaque question découpe les 14 jours en branches. La meilleure crée des branches homogènes : avec le ciel, la branche « couvert » est pure (entropie 0), ce qu'aucune autre caractéristique n'obtient.

La racine teste donc le ciel. La branche « couvert » est déjà pure : c’est une feuille « oui ». Pour les deux autres branches, on recommence le même raisonnement, mais uniquement avec les jours de la branche. Parmi les 5 jours ensoleillés, l’humidité sépare parfaitement les classes (élevée : 3 non ; normale : 2 oui), avec un gain maximal de 0,971. Parmi les 5 jours pluvieux, c’est le vent qui sépare parfaitement (vent : 2 non ; pas de vent : 3 oui). L’arbre final est :

Ciel ?
├── couvert    → jouer
├── ensoleillé → Humidité ?
│                ├── élevée  → ne pas jouer
│                └── normale → jouer
└── pluvieux   → Vent ?
                 ├── oui → ne pas jouer
                 └── non → jouer

Cinq règles lisibles, qui classent correctement les 14 jours. Remarquez que la température n’apparaît jamais : l’arbre a fait lui-même une sélection de variables.

L'arbre final avec les effectifs de chaque nœud. Toutes les feuilles sont pures ; chaque chemin de la racine à une feuille est l'une des cinq règles.

Attention

Le gain d’information favorise les caractéristiques qui ont beaucoup de valeurs. Un identifiant unique par jour aurait un gain maximal (chaque branche contient un seul jour, donc est pure), tout en étant inutile pour prédire. L’algorithme C4.5 corrige ce biais avec le rapport de gain, qui divise le gain par l’entropie de la caractéristique elle-même.

La construction récursive et ses variantes

L’algorithme général (ID3 et ses successeurs) est récursif :

1. Si tous les exemples du nœud ont la même classe, ou s’il n’y a plus de question à poser, créer une feuille portant la classe majoritaire.
2. Sinon, choisir la question de gain maximal, créer une branche par réponse, et recommencer sur chaque sous-groupe.

Les variantes se distinguent par ce qu’elles savent traiter :

• ID3 ne gère que des variables nominales.
• C4.5 accepte les variables continues et les valeurs manquantes, et utilise le rapport de gain.
• CART (utilisé par scikit-learn) ne fait que des questions binaires et utilise Gini par défaut.

Pour une variable continue comme un taux de cholestérol, l’algorithme trie les valeurs, teste chaque seuil situé entre deux valeurs consécutives (« cholestérol ≤ 240 ? ») et garde le seuil de meilleur gain. La même variable peut être réutilisée plus bas avec un autre seuil. Conséquence géométrique : les frontières d’un arbre sont faites de segments parallèles aux axes, en escalier.

Mais que se passe-t-il si l’on laisse l’algorithme aller jusqu’au bout sur de vraies données ? Il continue à découper tant qu’une feuille contient deux classes, jusqu’à isoler parfois un seul exemple. On obtient l’arbre maximal, noté $T_{max}$, dont l’erreur d’apprentissage est nulle (ou presque)… et qui a appris le bruit par cœur. C’est le surapprentissage du chapitre 2, sous sa forme la plus pure.

Des frontières faites de segments parallèles aux axes. L'arbre maximal découpe des rectangles minuscules autour des points isolés : parfait en apprentissage, moins bon sur de nouvelles données (données simulées).

Élaguer l’arbre

Il existe deux façons de limiter la croissance de l’arbre.

Le pré-élagage arrête la construction plus tôt : profondeur maximale (max_depth), nombre minimal d’exemples pour découper un nœud (min_samples_split) ou dans une feuille (min_samples_leaf), gain minimal. C’est simple, mais un peu myope : une question sans intérêt immédiat peut préparer une excellente question au niveau suivant.

Le post-élagage construit d’abord $T_{max}$, puis coupe les branches qui n’apportent pas assez. La méthode la plus utilisée, l’élagage coût-complexité (cost-complexity pruning), pénalise la taille de l’arbre :

$$R_\alpha(T) = R(T) + \alpha \, \lvert T \rvert$$

• $R(T)$ mesure l’erreur de l’arbre $T$ sur l’apprentissage (dans scikit-learn, l’impureté totale des feuilles, pondérée par leurs effectifs) ;
• $\lvert T \rvert$ est le nombre de feuilles de l’arbre ;
• $\alpha \geq 0$ est le prix d’une feuille supplémentaire.

Avec $\alpha = 0$, on garde $T_{max}$. Plus $\alpha$ augmente, plus il devient rentable de remplacer un sous-arbre par une simple feuille, jusqu’à l’arbre réduit à sa racine. On obtient ainsi une suite d’arbres emboîtés, du plus grand au plus petit, et on choisit celui dont l’erreur de validation est la plus faible.

En TP, sur le jeu heart.csv (prédire une maladie cardiaque à partir de mesures cliniques), l’arbre $T_{max}$ construit avec l’entropie découpait jusqu’à des feuilles toutes pures. La fonction cost_complexity_pruning_path a fourni 23 valeurs critiques de $\alpha$, de 0 à environ 0,19. Nous avons entraîné un arbre par valeur (avec le critère par défaut, Gini), tracé l’exactitude en apprentissage et en validation, et retenu $\alpha = 0{,}02$ : l’exactitude valait alors 0,863 en apprentissage et 0,802 en validation, contre un arbre maximal qui ne se trompait sur aucun patient d’apprentissage.

import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier

df = pd.read_csv("heart.csv")
X, y = df.drop(columns=["target"]), df["target"]
X_app, X_val, y_app, y_val = train_test_split(X, y, test_size=0.3, stratify=y, random_state=42)

# Suite des alpha critiques calculée sur l'arbre maximal
chemin = DecisionTreeClassifier(random_state=0).cost_complexity_pruning_path(X_app, y_app)

meilleur = None
for alpha in chemin.ccp_alphas[:-1]:            # la dernière valeur donne l'arbre réduit à la racine
    arbre = DecisionTreeClassifier(random_state=0, ccp_alpha=alpha).fit(X_app, y_app)
    score = arbre.score(X_val, y_val)
    if meilleur is None or score > meilleur[0]:
        meilleur = (score, alpha, arbre.get_n_leaves())

print(f"alpha retenu {meilleur[1]:.4f} : exactitude validation {meilleur[0]:.3f}, {meilleur[2]} feuilles")

À retenir

Un arbre qu’on laisse pousser jusqu’au bout ($T_{max}$) apprend le bruit par cœur. On le contraint soit avant (profondeur maximale, effectif minimal par feuille), soit après par élagage coût-complexité, en choisissant $\alpha$ sur des données de validation.

Pour finir, voici le bilan des arbres de décision :

Avantages	Limites
Très lisibles : chaque feuille est une règle	Instables : changer quelques exemples peut changer tout l’arbre (forte variance)
Peu de préparation : pas besoin de normaliser	Frontières en escalier, parallèles aux axes
Gèrent variables numériques et catégorielles	Surapprennent facilement sans élagage
Rapides à entraîner et à appliquer	Souvent moins précis qu’un ensemble d’arbres

En entretien

« Un arbre choisit à chaque nœud la question qui réduit le plus l’impureté (entropie ou Gini). Il est lisible mais instable, et il surapprend si on ne le contraint pas : on l’élague, ou on en combine beaucoup dans une forêt aléatoire. »

En résumé

• Un arbre de décision enchaîne des questions sur les caractéristiques ; chaque chemin de la racine à une feuille est une règle.
• L’entropie $H = -\sum_k p_k \log_2 p_k$ et l’indice de Gini $1 - \sum_k p_k^2$ mesurent l’impureté d’un nœud ; toutes deux valent 0 pour un nœud pur.
• On choisit la question de gain d’information maximal, $G(A) = H(Y) - H(Y \mid A)$, puis on recommence récursivement dans chaque branche.
• Le gain favorise les variables à nombreuses valeurs ; le rapport de gain (C4.5) corrige ce biais.
• L’arbre maximal $T_{max}$ surapprend ; on le limite par pré-élagage (profondeur, effectifs) ou post-élagage coût-complexité, avec $\alpha$ choisi en validation.
• Les arbres sont lisibles et simples à préparer, mais instables : c’est ce qui motive les méthodes d’ensemble.

Exercices

Exercice · Calculer une entropie et un indice de Gini

facile

Un nœud contient 8 patients : 6 malades et 2 sains. Calculez son entropie et son indice de Gini. Même question pour un nœud de 8 patients tous malades.

Voir la solution

Pour le premier nœud, $p_{\text{malade}} = 6/8 = 0{,}75$ et $p_{\text{sain}} = 0{,}25$.

• Entropie : $H = -0{,}75 \log_2 0{,}75 - 0{,}25 \log_2 0{,}25 \approx 0{,}75 \times 0{,}415 + 0{,}25 \times 2 \approx 0{,}311 + 0{,}5 = 0{,}811$.
• Gini : $G = 1 - 0{,}75^2 - 0{,}25^2 = 1 - 0{,}5625 - 0{,}0625 = 0{,}375$.

Pour le nœud pur, une seule classe est présente ($p = 1$) : $H = -1 \times \log_2 1 = 0$ et $G = 1 - 1^2 = 0$. Un nœud pur devient une feuille.

En code

Python

import numpy as np

def entropie(p):
    p = np.asarray(p, dtype=float)
    p = p[p > 0]                      # convention 0 log 0 = 0
    return -np.sum(p * np.log2(p))

def gini(p):
    p = np.asarray(p, dtype=float)
    return 1 - np.sum(p ** 2)

print(entropie([6/8, 2/8]), gini([6/8, 2/8]))   # 0.811  0.375
print(entropie([1.0]), gini([1.0]))             # 0.0  0.0

R

entropie <- function(p) {
  p <- p[p > 0]                     # convention 0 log 0 = 0
  -sum(p * log2(p))
}
gini <- function(p) 1 - sum(p^2)

entropie(c(6/8, 2/8)); gini(c(6/8, 2/8))   # 0.811  0.375
entropie(1); gini(1)                       # 0  0

Exercice · Choisir la question suivante

moyen

Dans l’arbre du fil rouge, placez-vous dans la branche « ensoleillé » (jours 1, 2, 8, 9 et 11). Calculez le gain d’information de la température et celui du vent dans cette branche, et vérifiez que l’humidité est bien le meilleur choix.

Voir la solution

Dans la branche, il y a 2 « oui » et 3 « non », donc $H = 0{,}971$.

Température : chaud = jours 1 et 2 (2 non, entropie 0) ; doux = jours 8 et 11 (1 non, 1 oui, entropie 1) ; frais = jour 9 (1 oui, entropie 0). $H(Y \mid \text{Température}) = \tfrac{2}{5} \times 0 + \tfrac{2}{5} \times 1 + \tfrac{1}{5} \times 0 = 0{,}4$, d’où un gain de $0{,}971 - 0{,}4 = 0{,}571$.

Vent : pas de vent = jours 1, 8, 9 (2 non, 1 oui, entropie $\approx 0{,}918$) ; vent = jours 2 et 11 (1 non, 1 oui, entropie 1). $H(Y \mid \text{Vent}) = \tfrac{3}{5} \times 0{,}918 + \tfrac{2}{5} \times 1 \approx 0{,}951$, d’où un gain de $0{,}020$.

Humidité : élevée = jours 1, 2, 8 (3 non) ; normale = jours 9 et 11 (2 oui). Les deux branches sont pures, l’entropie conditionnelle est nulle et le gain vaut $0{,}971$, le maximum possible. C’est bien l’humidité qu’on choisit.

En code

Python

import numpy as np
import pandas as pd

# Les 5 jours ensoleillés (jours 1, 2, 8, 9, 11)
soleil = pd.DataFrame({
    "temperature": ["chaud", "chaud", "doux", "frais", "doux"],
    "humidite":    ["élevée", "élevée", "élevée", "normale", "normale"],
    "vent":        ["non", "oui", "non", "non", "oui"],
    "jouer":       ["non", "non", "non", "oui", "oui"],
})

def entropie(y):
    p = y.value_counts(normalize=True).to_numpy()
    return -np.sum(p * np.log2(p))

def gain(df, attribut):
    # entropie conditionnelle : moyenne des entropies des branches, pondérée par leur taille
    h_cond = sum(len(g) / len(df) * entropie(g["jouer"]) for _, g in df.groupby(attribut))
    return entropie(df["jouer"]) - h_cond

print(round(entropie(soleil["jouer"]), 3))          # 0.971
for a in ["temperature", "vent", "humidite"]:
    print(a, round(gain(soleil, a), 3))             # 0.571, 0.02, 0.971

R

# Les 5 jours ensoleillés (jours 1, 2, 8, 9, 11)
soleil <- data.frame(
  temperature = c("chaud", "chaud", "doux", "frais", "doux"),
  humidite    = c("élevée", "élevée", "élevée", "normale", "normale"),
  vent        = c("non", "oui", "non", "non", "oui"),
  jouer       = c("non", "non", "non", "oui", "oui")
)

entropie <- function(y) {
  p <- table(y) / length(y)
  -sum(p * log2(p))
}
gain <- function(df, attribut) {
  # entropie conditionnelle : moyenne des entropies des branches, pondérée par leur taille
  branches <- split(df$jouer, df[[attribut]])
  h_cond <- sum(sapply(branches, function(y) length(y) / nrow(df) * entropie(y)))
  entropie(df$jouer) - h_cond
}

round(entropie(soleil$jouer), 3)                                  # 0.971
sapply(c("temperature", "vent", "humidite"), function(a) round(gain(soleil, a), 3))
# temperature 0.571, vent 0.02, humidite 0.971

Exercice · Quand élaguer un nœud ?

difficile

Dans l’élagage coût-complexité, on compare un nœud $t$ au sous-arbre $T_t$ qui pend sous lui. Le sous-arbre est remplacé par une feuille dès que $\alpha$ atteint la valeur critique

$$\alpha_{\text{eff}}(t) = \frac{R(t) - R(T_t)}{\lvert T_t \rvert - 1}$$

où $R(t)$ est l’erreur si $t$ devient une feuille, $R(T_t)$ l’erreur du sous-arbre et $\lvert T_t \rvert$ son nombre de feuilles.

Un arbre est appris sur 200 patients. Un nœud $t$ contient 40 patients avec une impureté de Gini de 0,5. Le sous-arbre sous $t$ a 3 feuilles, dont l’impureté totale pondérée vaut 0,04 (en proportion des 200 patients). Calculez $\alpha_{\text{eff}}(t)$ et dites si ce sous-arbre survit avec $\alpha = 0{,}02$, puis avec $\alpha = 0{,}05$.

Voir la solution

Si $t$ devient une feuille, son impureté pondérée par sa part des patients vaut $R(t) = \tfrac{40}{200} \times 0{,}5 = 0{,}1$. Le sous-arbre a $R(T_t) = 0{,}04$ et $\lvert T_t \rvert = 3$ feuilles. Donc :

$$\alpha_{\text{eff}}(t) = \frac{0{,}1 - 0{,}04}{3 - 1} = 0{,}03$$

Autrement dit, chacune des deux feuilles supplémentaires fait gagner 0,03 d’erreur. Avec $\alpha = 0{,}02$, une feuille « coûte » moins que ce qu’elle rapporte : le sous-arbre survit. Avec $\alpha = 0{,}05$, elle coûte plus : le sous-arbre est élagué et $t$ devient une feuille. C’est exactement ainsi que scikit-learn calcule la suite des $\alpha$ renvoyée par cost_complexity_pruning_path.

En code

Python

n_total, n_noeud, gini_noeud = 200, 40, 0.5
R_noeud = n_noeud / n_total * gini_noeud       # erreur si t devient une feuille : 0.1
R_sous_arbre, n_feuilles = 0.04, 3

alpha_eff = (R_noeud - R_sous_arbre) / (n_feuilles - 1)
print(round(R_noeud, 3), round(alpha_eff, 3))  # 0.1  0.03

for alpha in [0.02, 0.05]:
    # coût pénalisé de chaque option : erreur + alpha × nombre de feuilles
    cout_feuille = R_noeud + alpha * 1
    cout_sous_arbre = R_sous_arbre + alpha * n_feuilles
    print(alpha, "survit" if cout_sous_arbre < cout_feuille else "élagué")

R

R_noeud <- 40 / 200 * 0.5            # erreur si t devient une feuille : 0.1
R_sous_arbre <- 0.04; n_feuilles <- 3

alpha_eff <- (R_noeud - R_sous_arbre) / (n_feuilles - 1)
alpha_eff                            # 0.03

for (alpha in c(0.02, 0.05)) {
  # coût pénalisé de chaque option : erreur + alpha × nombre de feuilles
  cout_feuille <- R_noeud + alpha * 1
  cout_sous_arbre <- R_sous_arbre + alpha * n_feuilles
  cat(alpha, ifelse(cout_sous_arbre < cout_feuille, "survit", "élagué"), "\n")
}