Supervisée

Arbres de décision

Steven Golovkine

07 nov. 2025

Plan

1. La théorie des arbres de décision

2. Les arbres en pratique

3. Exemple

CART

Variables : \(X_1, \ldots, X_p\) avec \(n\) observations dans \(\mathbb{R}^p\).

Classification : Prédire l’appartenance à l’un des \(K\) groupes.

Régression : Prédire une variable numérique continue \(Y\).

Objectif principal

Partitionner l’espace des observations \(\mathbb{R}^p\) en sous-ensembles homogènes.

Algorithme récursif de découpage binaire

Découper selon une variable \(X_j\) à un seuil \(s\).

Créer des sous-régions rectangulaires (hyper-rectangles).

Chaque sous-ensemble = une feuille avec une prédiction.

⚠️ Algorithme glouton: Optimisation locale, pas globale !

Prédiction par feuille

Classification : Classe majoritaire

Régression : Moyenne des \(Y\)

Algorithme

Point de départ: L’ensemble complet des observations

Pour chaque nœud:

1. Évaluer tous les couples \((X_j, s)\) possibles.

2. Calculer la réduction du critère d’homogénéité.

3. Sélectionner le couple \((X_j, s)\) qui maximise le gain.

4. Diviser le nœud selon \(X_j \leq s\) vs \(X_j > s\).

5. Répéter jusqu’au critère d’arrêt.

Critères d’homogénéité

Soit \(\widehat{p}_{jk}\) la proportion d’observations de la région \(R_j\) appartenant à la classe \(k\).

Taux d’erreur de classification

\[E_j = 1 - \max_k \widehat{p}_{jk}\]

Facile à interpréter.

Peu sensible → rarement utilisé pour la construction.

Critères d’homogénéité

Soit \(\widehat{p}_{jk}\) la proportion d’observations de la région \(R_j\) appartenant à la classe \(k\).

Indice de Gini (le plus utilisé)

\[G_j = \sum_{k=1}^{K} \widehat{p}_{jk}(1 - \widehat{p}_{jk})\]

Minimal (\(= 0\)) quand homogénéité parfaite.

On cherche un indice faible.

Critères d’homogénéité

Soit \(\widehat{p}_{jk}\) la proportion d’observations de la région \(R_j\) appartenant à la classe \(k\).

Entropie croisée (théorie de l’information)

\[D_j = -\sum_{k=1}^{K} \widehat{p}_{jk} \log(\widehat{p}_{jk})\]

Basé sur l’information de Shannon.

Minimal pour classe parfaitement prédite.

Gain d’information

Mesure de la réduction de l’hétérogénéité après division.

Objectif : Maximiser le gain d’information.

Exemple avec l’indice de Gini:

\[\Delta G = G_{\text{avant}} - \left(\frac{n_1}{n} G_1 + \frac{n_2}{n} G_2\right)\]

où:

• \(n_1, n_2\) : nombres d’observations dans les sous-ensembles

• \(n = n_1 + n_2\)

Exemple

• Code
• Print
• Plot

library(tidyverse)

carseats <- as_tibble(ISLR::Carseats)
tree_carseat <- rpart::rpart(Sales ~ ., data = carseats)

print(tree_carseat)

n= 400 

node), split, n, deviance, yval
      * denotes terminal node

 1) root 400 3182.27500  7.496325  
   2) ShelveLoc=Bad,Medium 315 1859.56000  6.762984  
     4) Price>=105.5 207  956.57240  6.018792  
       8) ShelveLoc=Bad 61  240.81970  4.722459  
        16) Population< 196.5 25   88.22930  3.767200 *
        17) Population>=196.5 36  113.93510  5.385833 *
       9) ShelveLoc=Medium 146  570.41420  6.560411  
        18) Advertising< 5.5 77  280.11340  5.902468  
          36) Price>=127 34  133.53970  4.986765 *
          37) Price< 127 43   95.52198  6.626512 *
        19) Advertising>=5.5 69  219.77110  7.294638  
          38) CompPrice< 121.5 19   40.33360  6.230000 *
          39) CompPrice>=121.5 50  149.71840  7.699200  
            78) Price>=127 28   71.99441  6.731786 *
            79) Price< 127 22   18.16730  8.930455 *
     5) Price< 105.5 108  568.61750  8.189352  
      10) Age>=54.5 65  303.05690  7.380154  
        20) Income< 105.5 56  203.03290  6.946071  
          40) ShelveLoc=Bad 20   76.96006  5.786500 *
          41) ShelveLoc=Medium 36   84.24070  7.590278 *
        21) Income>=105.5 9   23.81549 10.081110 *
      11) Age< 54.5 43  158.66040  9.412558  
        22) Income< 57.5 13   19.24283  7.987692 *
        23) Income>=57.5 30  101.58740 10.030000  
          46) ShelveLoc=Bad 9   22.75640  8.396667 *
          47) ShelveLoc=Medium 21   44.53100 10.730000 *
   3) ShelveLoc=Good 85  525.52220 10.214000  
     6) Price>=109.5 57  277.26520  9.244386  
      12) Advertising< 13.5 48  185.42030  8.742500  
        24) Price>=142.5 12   36.64722  7.152500 *
        25) Price< 142.5 36  108.32350  9.272500  
          50) Income< 40.5 9    9.82780  7.603333 *
          51) Income>=40.5 27   65.06227  9.828889 *
      13) Advertising>=13.5 9   15.27049 11.921110 *
     7) Price< 109.5 28   85.57727 12.187860 *

plot(tree_carseat)
text(tree_carseat, use.n = TRUE)

Problème de l’ajustement

Dilemme:

• Arbre trop profond → Sur-ajustement aux données d’apprentissage

• Arbre trop simple → Sous-ajustement, classification trop simpliste

Conséquence → Perte de capacité de généralisation à de nouvelles données.

Solution → Élagage (pruning)

Élagage de l’arbre

Stratégie en deux temps :

1. Croissance complète jusqu’aux feuilles pures

2. Élagage des branches peu performantes

Critère coût-complexité :

\[\sum_{j=1}^{|T|} c_j + \alpha |T|\]

où \(|T|\) est le nombre de feuilles, \(c_j\) est le coût dans la feuille \(j\) et \(\alpha\) est un paramètre de régularisation.

Choix du paramètre α

Interprétation

• \(\alpha\) élevé → Favorise les arbres simples

• \(\alpha\) faible → Arbres plus complexes

Méthode de sélection → Validation croisée pour comparer les performances sur différentes valeurs de \(\alpha\)

Exemple

• Code
• Print
• Plot

library(tidyverse)

carseats <- as_tibble(ISLR::Carseats)
tree_carseat <- rpart::rpart(Sales ~ ., data = carseats)
tree_prune <- rpart::prune(tree_carseat, cp = 0.1)

print(tree_prune)

n= 400 

node), split, n, deviance, yval
      * denotes terminal node

1) root 400 3182.2750  7.496325  
  2) ShelveLoc=Bad,Medium 315 1859.5600  6.762984  
    4) Price>=105.5 207  956.5724  6.018792 *
    5) Price< 105.5 108  568.6175  8.189352 *
  3) ShelveLoc=Good 85  525.5222 10.214000 *

plot(tree_prune)
text(tree_prune, use.n = TRUE)

Avantages des arbres

Très interprétables : Chemin explicite pour chaque prédiction.

Robustes aux valeurs extrêmes et transformations monotones.

Gestion naturelle des interactions entre variables.

Variables mixtes : Quantitatives et qualitatives.

Aucune hypothèse sur la distribution des données.

Sélection automatique des variables importantes.

Base des méthodes modernes (forêts aléatoires, boosting).

Limites des arbres

Instabilité : Sensibles aux petites modifications des données

Performance limitée seuls, surtout avec données bruitées.

Divisions rectangulaires inadaptées aux frontières non-linéaires.

Tendance au sur-ajustement sans élagage.

Sensibilité au déséquilibre des classes.

Solution : Méthodes ensemblistes (forêts, boosting).

Conclusion

Les arbres :

• Méthode de partitionnement récursif

• Algorithme glouton simple et intuitif

• Nécessitent un élagage pour éviter le sur-ajustement

Prochaine étape → Les modèles ensemblistes