Aller au contenu
Data science

Les arbres de décision

⏱ 45 min

Prérequis : Mesurer une classification · Les modèles non linéaires en régression

À la fin de ce chapitre, vous saurez :
  • lire un arbre de décision et suivre le chemin d'une prédiction ;
  • expliquer comment l'arbre choisit chaque question (impureté de Gini) ;
  • relier la profondeur de l'arbre au surapprentissage ;
  • citer les forces et faiblesses des arbres.

Un arbre de décision classe un exemple en lui posant une suite de questions simples, du type « la longueur du pétale est-elle inférieure ou égale à 2,45 cm ? ». Chaque réponse oriente vers une branche ; au bout, une feuille donne la prédiction (la classe majoritaire des exemples d’entraînement arrivés là).

longueur du pétale ≤ 2,45 ?
├── oui → setosa
└── non → largeur du pétale ≤ 1,75 ?
├── oui → versicolor
└── non → virginica

C’est exactement la logique d’un questionnaire médical ou d’un guide d’identification des plantes. Un arbre se lit et s’explique : c’est l’un des rares modèles qu’un non-spécialiste peut vérifier à la main.

À chaque nœud, l’arbre essaie toutes les questions possibles : chaque variable, chaque seuil. Il garde celle qui sépare le mieux les classes, c’est-à-dire qui produit les deux groupes les plus purs (contenant le plus possible une seule classe).

La pureté se mesure par l’impureté de Gini : G=1−∑kpk2G = 1 - \sum_k p_k^2, où pkp_k est la proportion de la classe kk dans le groupe. G=0G = 0 si le groupe ne contient qu’une classe ; G=0,5G = 0{,}5 pour deux classes à parts égales (le pire). On fait la moyenne des Gini des deux groupes, pondérée par leur taille.

Déplacez le seuil, changez de variable : le Gini moyen baisse quand la coupure tombe entre les deux nuages. Le bouton 🤖 fait ce que fait l’arbre : il essaie tout et garde le minimum. L’arbre recommence ensuite dans chaque groupe, et ainsi de suite.

🎓 Pour aller plus loin : Gini, entropie, et régression

L’entropie H=−∑kpklog⁡2pkH = -\sum_k p_k \log_2 p_k est une autre mesure d’impureté (criterion="entropy"), issue de la théorie de l’information : la baisse d’entropie s’appelle le gain d’information. En pratique, Gini et entropie donnent des arbres très proches ; Gini est un peu plus rapide à calculer.

Pour une division qui envoie ngn_g exemples à gauche et ndn_d à droite, l’arbre minimise

ngn Ggauche+ndn Gdroite.\frac{n_g}{n}\,G_{\text{gauche}} + \frac{n_d}{n}\,G_{\text{droite}} .

Les seuils candidats sont les milieux entre deux valeurs consécutives de la variable : avec nn exemples et pp variables, au plus p (n−1)p\,(n-1) divisions à tester par nœud.

En régression, l’impureté devient la variance des valeurs du groupe, et la feuille prédit leur moyenne : la prédiction est une fonction en escalier (voir Les modèles non linéaires en régression).

Trouver l’arbre globalement optimal est un problème très difficile (NP-complet). L’algorithme est glouton : il choisit la meilleure question à chaque étape, sans revenir en arrière.

Laissé libre, un arbre continue de diviser jusqu’à ce que chaque feuille soit pure, quitte à créer une feuille pour un seul exemple. Il apprend alors les données par cœur, bruit compris : c’est le surapprentissage typique des arbres.

On le limite par des hyperparamètres :

  • max_depth : la profondeur maximale ;
  • min_samples_leaf : le nombre minimal d’exemples dans une feuille ;
  • min_samples_split : le nombre minimal d’exemples pour diviser un nœud ;
  • l’élagage (ccp_alpha) : on construit l’arbre complet, puis on coupe les branches qui n’apportent pas assez.
🔬Un arbre qui pousse

L’arbre se construit division par division sur les deux lunes. Cliquez sur un nœud pour voir sa courbe de Gini (« pourquoi ce seuil ? »). Comparez la profondeur illimitée et une profondeur de 3.

→
Forces Faiblesses
lisible et explicable instable : quelques exemples en plus ou en moins peuvent changer tout l’arbre
aucune mise à l’échelle nécessaire surapprend facilement
gère variables numériques et catégorielles, valeurs manquantes (selon l’implémentation) frontières en escalier, parallèles aux axes : mal adaptées à une frontière en diagonale
capture les interactions entre variables peu précis seul

L’instabilité et le manque de précision d’un arbre seul sont corrigés par les méthodes d’ensemble (chapitre suivant) : des centaines d’arbres qui votent.

from sklearn.tree import DecisionTreeClassifier, plot_tree
arbre = DecisionTreeClassifier(max_depth=3, random_state=0).fit(X_train, y_train)
plot_tree(arbre, feature_names=noms_variables, class_names=noms_classes, filled=True)
arbre.feature_importances_ # la baisse d'impureté apportée par chaque variable

✅ Vérifiez vos acquis

1. Un groupe contient 10 exemples, tous de la même classe. Son impureté de Gini vaut…
2. Comment l'arbre choisit-il la question posée à un nœud ?
3. Un arbre sans limite de profondeur obtient 100 % sur l'entraînement et 78 % sur le test. Que faire ?
4. Faut-il standardiser les variables avant un arbre de décision ?
5. Pourquoi un arbre a-t-il du mal avec une frontière en diagonale ?