Arbres de décision (conditionnels) avec R
Journée MAD — Réseau SO-MATE
Frédéric Santos
frederic.santos@u-bordeaux.fr
6 janvier 2026
1. Programme de la matinée
- Principe général d’un arbre de décision
- Les différents algorithmes classiques (CART, CHAID, …)
- Les arbres d’inférence conditionnelle
- Forêts d’arbres décisionnels
2. Arbres de décision : principes généraux
L’arbre de décision est un outil relativement récent (1984 pour l’algorithme le plus utilisé, CART) d’exploration des données et de prédiction.
Il peut servir à expliquer une variable qualitative (on parle alors d’arbre de classification) ou quantitative (arbre de régression).
2.1. Avantages
Par rapport à d’autres méthodes classiques (SVM, analyse factorielle discriminante, réseau de neurones, etc.), l’arbre de décision possède de nombreux avantages :
- un arbre de décision est très simple à interpréter, et fournit une représentation graphique parlante ;
- les données d’entrée peuvent être de types mixtes ;
- gestion efficace de la non-linéarité et des interactions complexes entre variables ;
- la sélection des meilleures variables est au coeur de l’algorithme (donc très adapté au cas \(p > n\)) ;
- les données manquantes sont gérées nativement.
2.2. Inconvénients
Il y a néanmoins quelques désavantages :
- en présence de données « idéales », moindres capacités prédictives que des méthodes d’apprentissage classiques ;
- instabilité et manque de robustesse, notamment dans le cas de petits effectifs ;
- lorsque la relation entre la variable réponse et les variables explicatives est très simple (e.g., une combinaison linéaire, sans interactions complexes), un arbre de régression est souvent moins performant et moins réaliste qu’une simple régression linéaire.
En pratique, un arbre de décision est donc surtout un outil exploratoire ou descriptif, ou un outil décisionnel « tout-terrain » lorsqu’on doit faire de la prévision avec des données de mauvaise qualité (ou de très grande dimension).
3. L’algorithme CART
Figure 1 : Un exemple d’arbre de décision avec R
3.1. Comment faire pousser un arbre ?
Quelques éléments de notation pour ce qui suit :
- Supposons que nous avons \(n\) individus décrits par \(p\) variables.
- \(Y\) est la variable à expliquer, et les variables explicatives sont notées \(X_1, \dots, X_p\).
3.1.1. Idée générale
L’algorithme CART (Breiman et al., 1984) fonctionne selon un principe de partitionnement binaire récursif : le but est d’obtenir des groupes d’individus aussi homogènes que possible (par rapport à \(Y\)), en posant une succession de questions binaires (oui / non) relatives aux variables explicatives.
Une fois ces groupes (ce partitionnement) obtenus, un modèle simple est construit à l’intérieur de chacun d’entre eux.
3.1.2. Formulation informelle de l’algorithme
- Un arbre part de sa racine, qui contient tous les individus.
- Une première question portant sur l’une des variables \(X_i\) sépare les individus en deux groupes : cette question est choisie de façon à obtenir les groupes les plus « purs » (i.e., homogènes en leur sein, et bien différents l’un de l’autre).
- Chacun de ces deux groupes peut à son tour être séparé en deux, en choisissant la meilleure question possible pour chacun d’entre eux. Le processus est répété récursivement.
- Lorsque certains critères d’arrêt sont atteints, le processus se termine, et les groupes finaux obtenus constituent les feuilles de l’arbre.
- Un modèle simple est construit pour chacune de ces feuilles afin d’expliquer \(Y\).
3.1.3. Des questions en suspens
Ce descriptif de l’algorithme laisse pour l’instant trois grandes questions en suspens :
- Comment sont choisies, à chaque noeud, les « meilleures questions possibles » créant deux nouveaux sous-groupes d’individus ?
- Quand et comment l’algorithme s’arrête-t-il ?
- Une fois les groupes d’individus constitués, que contiennent les feuilles terminales ?
3.2. Arbres de régression
3.2.1. Exemple introductif : présentation des données
Supposons que l’on veuille expliquer le prix d’une voiture (variable continue exprimée en milliers de dollars) en fonction de deux variables continues : sa puissance exprimée en chevaux (HP, horsepower), et le diamètre des roues exprimé en pouces (Wheel.base).
library(dplyr)
library(rpart)
data(car90)
head(select(car90, Price, HP, Wheel.base))
| Price | HP | Wheel.base | |
|---|---|---|---|
| Acura Integra | 11950 | 130 | 102 |
| Acura Legend | 24760 | 160 | 109 |
| Audi 100 | 26900 | 130 | 106 |
| Audi 80 | 18900 | 108 | 100 |
| BMW 325i | 24650 | 168 | 101 |
| BMW 535i | 33200 | 208 | 109 |
3.2.2. Une première exploration des données
On représente ci-dessous le lien entre le prix des voitures et ces deux variables :
## Représentation du prix en fonction des caractéristiques :
library(ggplot2)
ggplot(car90, aes(x=HP, y=Wheel.base, size=Price, color=Price)) +
geom_point() +
theme_bw(base_size = 16) +
guides(size = "none")
Figure 2 : Représentation du lien entre les caractéristiques et le prix des voitures.
3.2.3. L’arbre de régression pour les données car90
L’arbre va créer une partition constituée de paquets de véhicules homogènes :
library(rpart.plot)
arbre1 <- rpart(Price ~ HP + Wheel.base, data = car90)
rpart.plot(arbre1, digits = -1, extra = 1)
Figure 3 : Arbre de régression (non élagué, obtenu par défaut).
3.2.4. Le partionnement récursif : deux points de vue équivalents
L’arbre de régression opère en fait le découpage suivant sur le nuage de points :
Figure 4 : Un point de vue équivalent à la Figure 3.
Mais la représentation par un arbre se généralise aisément à une situation où l’on dispose de très nombreuses variables explicatives, alors qu’il ne sera pas possible de généraliser la représentation ci-dessus si on travaille en dimension supérieure à 2.
3.3. Détails algorithmiques
3.3.1. Que contiennent les feuilles terminales ?
Supposons que l’arbre a été construit et fixé à une taille convenable. Quelle valeur peut-on attribuer à chaque feuille ?
Comme les feuilles sont supposées homogènes (en termes de la variable réponse \(Y\)), on fait généralement le choix d’un simple ajustement par une constante, qui est la moyenne de la variable réponse pour les individus appartenant à cette feuille.
Cette stratégie est mathématiquement optimale si on souhaite affecter une valeur constante à chaque feuille (au sens où la moyenne est la constante qui minimise l’erreur du modèle au sein de chaque feuille).
3.3.2. Comment sont créés les noeuds ? (1)
Lorsqu’on se place à un certain noeud de l’arbre, la séparation en deux branches en fonction d’une certaine variable \(X_j\) est de la forme suivante :
- si \(X_j\) est numérique : le critère porte sur un certain seuil \(s\). Les individus vérifiant \(X_j < s\) sont envoyés à gauche, et les individus vérifiant \(X_j \geq s\) sont envoyés à droite ;
- si \(X_j\) est qualitative : le critère porte sur un certain sous-ensemble \(\mathcal{I}\) des modalités de cette variable. Les individus possédant l’une des modalités présentes dans \(\mathcal{I}\) sont envoyés à gauche, les autres à droite.
3.3.3. Comment sont créés les noeuds ? (2)
Critère mathématique
L’idée est de trouver la variable \(X_j\) et le seuil \(s\) qui permettent de maximiser la variance inter-groupes lors de cette séparation en deux branches (et donc de minimiser la variance intra-groupe, cf. théorème de Huygens).
Lorsqu’on sépare un noeud \(t\) en deux noeuds \(t_L\) et \(t_R\), on souhaite donc maximiser la quantité suivante (Genuer & Poggi, 2020) :
\[ V(t) - \left( \frac{\# t_L}{\# t} \, V(t_L) + \frac{\# t_R}{\# t} \, V(t_R) \right) \]
où pour un noeud \(t\), on note \(V(t) = \frac{1}{\# t} \sum_{i : x_i \in t} (y_i - \bar{y_t})^2\) la variance de la variable réponse pour les observations appartenant à ce noeud.
3.3.4. Comment sont créés les noeuds ? (3)
Mais comment trouver la bonne variable \(X_j\) et le bon seuil \(s\) ?
Pour cela, l’algorithme procède par force brute : il teste toutes les séparations possibles (i.e., tous les seuils \(s\) possibles pour toutes les variables numériques, et tous les sous-ensembles \(I\) pour toutes les variables qualitatives).
À l’issue de cette exploration exhaustive des séparations possibles, l’algorithme retient la séparation offrant le meilleur gain d’information.
3.3.5. Élagage d’un arbre (1)
À quel moment le processus récursif s’arrête-t-il ? Un arbre doit être arrêté lorsqu’il atteint une taille optimale :
- un arbre comportant trop de feuilles serait victime de surajustement ;
- un arbre comportant trop peu de feuilles manquerait de pouvoir explicatif et prédictif.
Il faut donc rechercher le nombre de feuilles réalisant le meilleur compromis entre ces deux extrêmes.
3.3.6. Élagage d’un arbre (2)
Quelques critères d’arrêt possibles :
- Obliger chaque feuille terminale à contenir un nombre minimal d’individus (si une division supplémentaire doit entraîner l’obtention de feuilles contenant trop peu d’individus, le processus s’arrête).
- Variante : ne plus tenter de division supplémentaire lorsqu’un noeud contient moins d’un certain nombre d’individus.
- Interrompre le processus lorsqu’une division supplémentaire n’aboutirait pas à une diminution « sensible » (p. ex. fixée à l’avance) de l’erreur du modèle.
- Retenir le nombre de feuilles permettant de minimiser l’erreur de prédiction en validation croisée (sur un autre jeu de données de validation, ou en leave-one-out cross validation dans les données d’apprentissage).
Le principe général est souvent de donner, pour les critères 1 à 2, des valeurs aboutissant à un arbre contenant probablement un peu trop de feuilles. Ce sera alors le critère 4 (la sélection selon la capacité prédictive estimée en validation croisée) qui permettra l’élagage de l’arbre à la taille optimale.
3.3.7. Application avec R (1)
On commence usuellement par construire un arbre volontairement trop grand :
## Construire un arbre basique pour expliquer le prix :
arbre1 <- rpart(Price ~ HP + Wheel.base, data = car90, cp = 0)
rpart.plot(arbre1, digits = -3, extra = 1)
Figure 5 : Arbre de régression (quasi-) maximal, à élaguer.
3.3.8. Application avec R (2)
On procède ensuite à l’élagage de l’arbre maximal par validation croisée :
## Recherche de la taille optimale par LOOCV :
arbre2 <- rpart(
formula = Price ~ HP + Wheel.base,
data = car90,
cp = 0,
xval = nrow(car90) # effectuer une LOOCV
)
plotcp(arbre2)
Figure 6 : Erreur obtenue en fonction de la taille de l’arbre.
3.3.9. Application avec R (3)
Lors de l’élagage, on recherche par LOOCV (l’argument argument xval doit alors être égal au nombre d’individus) la coupure optimale que l’on peut effectuer sur l’arbre1 (i.e., l’arbre « maximal »).
La fonction plotcp() trace un graphique de complexité (Fig. 6), donnant l’erreur relative commise en fonction du nombre de feuilles terminales.
3.3.10. Application avec R (4)
On peut alors construire l’arbre optimal. On élague l’arbre2 avec prune() :
## Élagage de l'arbre à une taille optimale :
arbre3 <- prune(arbre2, cp = 0.045)
rpart.plot(arbre3, extra = 1, digits = -3)
Figure 7 : Arbre optimal (au sens de la LOOCV).
Cet arbre diffère légèrement de l’arbre obtenu avec les paramètres par défaut (arbre1), qui possédait 6 feuilles terminales.
3.4. Gestion des données manquantes
Quand une variable \(Z\) a été retenue pour créer un noeud, on opère une partition (en deux groupes) des individus en fonction des valeurs qu’ils prennent pour cette variable.
Si une autre variable \(Z_1\) du jeu de données permet de définir sensiblement la même partition (i.e., les deux mêmes sous-groupes), on dit alors que \(Z_1\) est une variable substitut à \(Z\).
Ainsi, pour chaque noeud de l’arbre, on forme une liste des meilleures variables substituts. Si un individu donné (notamment s’il s’agit d’un nouvel individu à prédire) possède une valeur manquante pour une variable apparaissant sur l’arbre, on utilise alors à la place une variable substitut.
3.5. Arbre de classification
Tout ce qui précède reste vrai si la variable réponse \(Y\) est catégorielle. On a uniquement deux adaptations :
- Critère mathématique pour trouver la meilleure partition à chaque noeud : au lieu de minimiser la variance intra-groupe (qui n’aurait pas de sens ici), on utilise en général plutôt l’indice de Gini.
- Élagage : on cherche en général à minimiser le taux de mauvais classement en LOOCV.
4. Autres algorithmes
4.1. CHAID
Une alternative populaire lorsque l’on travaille essentiellement avec des données catégorielles est CHAID, basée sur des tests du \(\chi^2\). Deux grandes différences avec CART :
- Le partitionnement n’est plus binaire : chaque noeud peut donner naissance à une division en trois nouvelles feuilles, ou encore davantage !
- La meilleure variable pour chaque noeud est choisie en calculant des statistiques du \(\chi^2\) entre chacun des prédicteurs et la variable réponse. La variable avec la p-valeur la plus faible l’emporte.
4.2. Encore beaucoup d’alternatives !
Il existe de nombreux autres algorithmes : C4.5, QUEST, CRUISE, CTREE, etc.
Ils peuvent donner des résultats très différents pour un même problème, comme on peut le voir ci-dessous (image extraite de Loh (2014)).
Figure 8 : Différents algorithmes d’arbre appliqués au même jeu de données.
5. Arbres d’inférence conditionnelle
5.1. Une alternative importante
Les CIT (conditional inference trees) sont une alternative intéressante à l’algorithme historique CART. Les points communs restent nombreux :
- partitionnement récursif binaire ;
- données mixtes autorisées ;
- très bien adaptés aux situations « \(p \geq n\) » et à l’inter-corrélation des prédicteurs ;
- pas d’hypothèses sur la distribution des variables.
Pour une bonne introduction, voir par exemple Levshina (2020).
5.2. Un algorithme basé sur des p-valeurs
5.2.1. Idée générale
Un peu comme pour l’algorithme CHAID, les CIT sont basés sur une série de tests d’hypothèses.
- Pour chaque variable explicative \(X\), l’hypothèse nulle est que la distribution (marginale) \(D(Y)\) de la variable réponse est identique à la distribution conditionnelle \(D(Y|X)\).
- En globalité, l’hypothèse nulle totale est que cette indépendance est vraie pour toutes les variables.
Pour tester ces hypothèses, on effectue des permutations de la variable réponse \(Y\).
- Si l’hypothèse nulle est vraie, alors cela « ne doit rien changer » : l’association entre \(X\) et \(Y\) sera du même ordre de grandeur avant et après permutation.
- Au contraire, si la mesure d’association chute drastiquement après permutation, on a alors mis un lien en évidence entre \(X\) et \(Y\).
5.2.2. Quelques détails
- La mesure d’association par défaut est notée \(c_\text{quad}\), et elle est mathématiquement assez complexe. Pour des détails techniques, voir Hothorn et al. (2006).
- Plutôt que de retenir la meilleure variable en fonction de la valeur de \(c_\text{quad}\), on les trie en fonction de la p-valeur associée.
- Avantage très conséquent : lorsque plus aucune p-valeur n’est significative, l’algorithme s’arrête et l’arbre ne « pousse » plus. Il n’y a plus besoin d’élagage !
5.2.3. Autres différences notables avec CART
Outre les différences déjà signalées, l’algorithme des CIT se distingue de CART par un point important :
- CIT sélectionne d’abord la meilleure variable grâce à une p-valeur, puis sélectionne ensuite le seuil \(s\) ou le sous-ensemble de modalités \(I\) dans un second temps pour créer la meilleure division à partir de cette variable.
- Au contraire, CART ne sépare pas ces deux étapes, mais les effectue simultanément, en parcourant tout à la fois les combinaisons de variables et de seuils. Cela peut introduire une « différence de traitement » entre les variables : les variables ayant beaucoup de valeurs différentes sont donc regardées « plus souvent » que celles en ayant peu. Ce n’est pas le cas pour les CIT.
5.3. Mise en pratique avec R
library(palmerpenguins)
library(partykit)
cit <- ctree(species ~ ., data = penguins)
plot(cit)
Figure 9 : Exemple d’arbre d’inférence conditionnel.
Pour changer un peu : voici l’arbre de classification obtenu pour prédire l’espèce des manchots dans le jeu de données penguins.
6. Forêts aléatoires
Figure 10 : Principe d’une forêt aléatoire. [Source
6.1. Principe général
6.1.1. Agrégation de plusieurs arbres
Une forêt aléatoire est construite à partir de nombreux arbres de décision (généralement quelques centaines), et fournit un résultat moyenné à partir de tous ces arbres : c’est une forme de model averaging.
Mais dans la mesure où la construction d’un arbre est purement déterministe, comment fait-on pour obtenir un forêt d’arbres différents les uns des autres ?
6.1.2. Aperçu de l’algorithme
- Pour chaque arbre de la forêt, on n’utilise qu’une fraction d’individus (par exemple 1/5 ou 1/4, si le nombre total d’individus est élevé) piochée aléatoirement dans les données.
- Pour chaque noeud des arbres, on peut également n’utiliser qu’une fraction (par exemple 1/3) des variables possibles. Ce paramètre est à optimiser.
- Les arbres sont généralement construits sans élagage, ou du moins, de façon à être volontairement un peu sur-ajustés : leur construction se poursuit simplement tant que les feuilles terminales ne sont « pas trop petites » (par exemple, au moins 5 individus par feuille).
- La prédiction finale à l’issue de la procédure est obtenue (dans le cas d’un arbre de régression) en moyennant les prédictions de tous les arbres de la forêt, ou bien (dans le cas d’un arbre de classification) en retenant la prédiction la plus fréquente.
6.1.3. Points de vigilance
- L’algorithme initial des forêts aléatoires ne tolère pas la présence de valeurs manquantes : une imputation doit être réalisée en amont de l’analyse.
- Dans le cas d’une forêt de classification (prédisant une variable qualitative), avoir des classes très déséquilibrées dans la variable réponse peut poser problème. Des solutions existent toutefois (Chen et al., 2004), et doivent impérativement être appliquées dans un tel cas.
6.2. Exemple d’application
6.2.1. Construire une forêt
En partant du classique jeu de données iris, on peut construire une forêt aléatoire (constituée d’arbres de classification) avec l’instruction suivante :
library(randomForest)
foret <- randomForest(
Species ~ .,
data = iris,
ntree = 999,
importance = TRUE
)
print(foret) # résumé des résultats de la forêt aléatoire
Call:
randomForest(formula = Species ~ ., data = iris, ntree = 999, importance = TRUE)
Type of random forest: classification
Number of trees: 999
No. of variables tried at each split: 2
OOB estimate of error rate: 4.67%
Confusion matrix:
setosa versicolor virginica class.error
setosa 50 0 0 0.00
versicolor 0 47 3 0.06
virginica 0 4 46 0.08
6.2.2. Optimiser les paramètres de la forêt
- En faisant un simple
plot()du modèle, on obtient un graphique donnant l’évolution de l’erreur de prédiction en fonction du nombre d’arbre de la forêt. - La fonction
tuneRF()permet quant à elle d’optimiser un paramètre important : le nombre de variables considérées à chaque split.
6.2.3. Importance des variables (1)
Les modèles de forêt aléatoire sont partiellement des « boîtes noires », mais offrent des outils d’interprétation. En particulier, on peut identifier facilement les variables contribuant le plus fortement au modèle.
Pour cela, on calcule un score d’importance pour chaque variable, basé sur une idée astucieuse. On permute aléatoirement les valeurs d’une variable explicative, et si elle est importante dans le modèle, cela doit alors faire fortement décroître la précision des résultats.
Les variables les plus importantes sont donc celles qui occasionnent la plus forte baisse de précision (MeanDecreaseAccuracy) lorsqu’elles sont perturbées aléatoirement.
6.2.4. Importance des variables (2)
## Afficher les scores d'importance :
print(foret$importance)
On voit qu’ici, ce sont les deux variables relatives aux pétales qui sont les plus importantes dans le modèle.
7. Forêts d’arbres d’inférence conditionnelle
Une forêt d’arbres d’inférence conditionnelle est l’équivalent des forêts aléatoires « classiques », appliquées aux arbres d’inférence conditionnelle.
7.0.1. Pratique avec R (1) : Construire la forêt
On peut utiliser par exemple la fonction cforest() du package {partykit} :
library(partykit)
cforet <- cforest(species ~ bill_length_mm + bill_depth_mm +
flipper_length_mm + body_mass_g + sex,
data = penguins)
Puis on peut comparer les valeurs prédites et les classes réelles, par exemple avec :
table(Réel = penguins$species,
Prédit = cforet$fitted$"(response)")
Prédit
Réel Adelie Chinstrap Gentoo
Adelie 152 0 0
Chinstrap 0 68 0
Gentoo 0 0 124
7.0.2. Importance des variables (1)
Les forêts aléatoires conditionnelles reprennent globalement la logique des scores d’importance des forêts aléatoires « traditionnelles ».
Seule une légère modification est apportée au calcul des scores d’importance (Strobl et al., 2008). Par exemple, dans le cas de deux prédicteurs qualitatifs \(X_1\) et \(X_2\), les permutations aléatoires effectuées pour \(X_1\) sont effectuées conditionnellement à \(X_2\) : les valeurs de \(X_1\) sont permutées aléatoirement à l’intérieur de chaque niveau de \(X_2\), plutôt que globalement.
7.0.3. Importance des variables (2)
## Scores d'importance conditionnels :
varimp(cforet, conditional = TRUE)
bill_length_mm bill_depth_mm flipper_length_mm body_mass_g sex
2.7618525 0.3880622 0.3009558 0.1675204 0.1004135
Références
Créé par Frédéric Santos