9  Arbres de décision, de régression et forêts aléatoires

Les arbres de décision et de régression sont des outils simples pour l’apprentissage supervisé qui combinent

9.1 Arbres de décision (pour la classification)

Un arbre de décision implémente un modèle de prédiction où chaque nœud de l’arbre « coupe » les données en 2 paquets (ou plus) en testant une composante x_k de \boldsymbol{x}\in\mathbb{R}^d face à un seuil s : x_k \leq s\ ? puis,

  • une branche est créée pour chaque résultat possible du test
  • chaque feuille est associée à une étiquette de catégorie y
  • pour calculer la prédiction f(\boldsymbol{x}), on propage \boldsymbol{x} à travers l’arbre jusqu’à atteindre une feuille et l’étiquette correspondante

9.2 Apprentissage

L’apprentissage d’un arbre de décision vise à construire un arbre en choisissant les coupes de chaque nœud et les étiquettes à associer aux feuilles de telle sorte que le risque empirique (par ex., l’erreur de classification sur les données de la base d’apprentissage) R_{emp}(f) soit minimisé.

Cependant, il s’agit aussi de minimiser la taille de l’arbre, sans quoi une solution simple (et plutôt mauvaise) consisterait à créer une feuille pour chaque exemple (\boldsymbol{x}_i,y_i) pour assurer R_{emp}(f)=0.

L’algorithme d’apprentissage fonctionne au niveau de chaque nœud, qui a accès à un sous-ensembe des données d’apprentissage (les \boldsymbol{x}_i qui atteignent ce nœud en suivant les coupes depuis la racine).

  1. Créer la racine en lui associant toutes les données d’apprentissage
  2. Pour chaque nœud non traité :
    • Calculer l’étiquette y majoritaire sur les données du nœud et la stocker
    • Calculer le nombre d’erreurs de classification du nœud sur ses données. Si il est tolérable, marquer le nœud comme une feuille, sinon
      1. Déterminer la composante x_k et le seuil s pour couper les données
      2. Créer les nœuds fils avec leurs données associées en fonction de la coupe choisie

Dans cet algorithme, un paramètre important est la tolérance sur l’erreur dans les feuilles, qui limite le nombre de nœuds et permet d’éviter le surapprentissage.

Dans chaque nœud, x_k et s sont choisis pour minimiser l’impureté des fils : \min_{k,s} n_1 \times Impur(fils_1) + n_2 \times Impur(fils_2) avec l’impureté Impur(fils_j) du fils j associé à n_j données qui peut être définie comme

  • le taux d’erreur de classification : 1 - p_y
  • l’index de Gini : \sum_{c=1}^C p_c(1-p_c)
  • l’entropie : -\sum_{c=1}^C p_c\log p_c

où p_c est la proportion d’exemples de la catégorie c\in\{1,\dots,C\} dans le nœud et y est la catégorie majoritaire.

9.2.1 Recherche de la coupe optimale

Pour les composantes continues (x_k\in\mathbb{R}), il existe une infinité de seuils s possibles pour une coupe. Mais en réalité, il suffit de tester les m-1 valeurs de seuil : s_i = \frac{x_{i,k} + x_{i+1,k}}{2} où les kèmes composantes des données, x_{i,k}, sont triées par ordre croissant.

En effet, les autres valeurs de seuil ne donnent pas naissance à d’autres classifications des données différentes de celles obtenues avec les s_i, et donc conduiront aux même valeurs d’impureté.

À chaque itération (à chaque nœud), le nombre de couples (k,s) à tester et pour lesquelles il faut calculer l’impureté résultante est donc d(m-1).

9.2.2 Variables qualitatives

Si \boldsymbol{x} contient des composantes qualitatives (à valeurs dans un ensemble discret, par ex. x_k\in\{rouge,vert,jaune\}), l’algorithme s’adapte simplement en découpant les branches selon les modalités :

  • soit en créant une branche par valeur possible,
  • soit en coupant en deux paquets de valeurs (ou une seule vs les autres).

9.3 Partition de l’espace de représentation

Un arbre de décision (ou de régression) équivaut à une partition de \mathcal{X} en régions \mathcal{X}_j rectangulaires associées aux feuilles : f(\boldsymbol{x}) = y \quad \Leftrightarrow \quad\exists j,\quad \boldsymbol{x}\in\mathcal{X}_j \ et\ y(j) = y avec \mathcal{X}_j = [a_1, b_2] \times [a_2,b_2]\times \dots \times [a_d,b_d], les a_k, b_k déterminés par les coupes dans chaque nœud, et y(j) l’étiquette de la feuille j.

9.4 Arbres de régression

En régression, les étiquettes sont réelles : y_i\in\mathbb{R}. Dans ce cas, l’algorithme ci-dessus fonctionne avec les modifications suivantes :

  • l’étiquette y(noeud) d’un nœud est la moyenne des y_i des données affectées au nœud (d’indices \mathcal{I}(noeud)) ;
  • le modèle implémente une fonction f(\boldsymbol{x}) en escalier (constante par morceaux) ;
  • le critère à minimiser pour choisir une coupe est l’erreur quadratique moyenne : Impur(noeud) = \frac{1}{|\mathcal{I}(noeud)|}\sum_{i\in \mathcal{I}(noeud)} (y_i - y(noeud))^2 \Rightarrow\qquad \min_{k,s} \sum_{i\in \mathcal{I}(fils_1)} (y_i - y(fils_1))^2 + \sum_{i\in \mathcal{I}(fils_2)} (y_i - y(fils_2))^2

On peut aussi créer des arbres de régression avec des modèles linéaires locaux associés aux feuilles au lieu de simples constantes (le modèle devient alors une fonction linéaire par morceaux au lieu d’un escalier).

9.5 Forêts aléatoires

Les arbres de décision et de régression ont de nombreux avantages, mais sont à l’inverse très sensisbles aux données. Ainsi, on observe une grande variance pour l’apprentissage d’un arbre : quelques modifications minimales des données peuvent conduirent à des arbres très différents.

Pour limiter cet effet, les techniques de bagging et de forêts aléatoires construisent un ensemble d’arbres dont les sorties sont moyennées afin d’en réduire la variance. En effet, la variance d’une moyenne \mu de B variables aléatoires indépendantes et identiquement distribuées (i.i.d.) Z_i est divisée par B : \mu = \frac{1}{B}\sum_{i=1}^B Z_i \quad \Rightarrow \quad Var(\mu) = \frac{Var(Z_1)}{B} \tag{9.1}

Les propriétés de la variance permettent d’obtenir Var(\mu) = \frac{1}{B^2}Var\left(\sum_{i=1}^B Z_i\right) et, pour des variables i.i.d., puisque Var(Z_1 + Z_2) = Var(Z_1) + Var(Z_2), Var\left(\sum_{i=1}^B Z_i\right) = \sum_{i=1}^B Var\left( Z_i\right) et Var(\mu) = \frac{1}{B^2}\sum_{i=1}^B Var\left( Z_1\right) = \frac{B Var(Z_1)}{B^2} = \frac{Var(Z_1)}{B}

Ainsi, il suffirait d’apprendre B arbres f_j différents pour calculer des prédictions f(\boldsymbol{x}) = \frac{1}{B} \sum_{j=1}^B f_j(\boldsymbol{x}) ou, pour la classification, f(\boldsymbol{x}) = \text{catégorie majoritaire parmi les } f_j(\boldsymbol{x}), qui seraient moins sensibles aux petites modifications des données et donc potentiellement meilleures en généralisation. Cependant, pour apprendre des arbres différents, il faut des jeux de données différents.

9.5.1 Bootstrap

Le bootstrap est une techniue classique en statistique pour générer plusieurs jeux de données à partir d’un seul.

Avec n données de départ, un nouveau jeu de données peut être créé en tirant aléatoirement n' données parmi n avec remise (les mêmes données peuvant donc être choisies plusieurs fois).

Cette opération peut être répétée autant de fois que nécessaire pour générer un ensemble de variations du jeu de données initial.

9.5.2 Bagging

Le bagging (pour bootstrap aggregation) revient à apprendre B arbres sur B jeux de données générés par bootstrap avec n'=n.

Cette approche est assez simple et directe à mettre en place, et peut s’utiliser en fait avec d’autres modèles que les arbres. En règle générale, on parle de « modèles faibles » dont les performances sont améliorées par bagging.

Un inconvénient de cette méthode simple est que les différents modèles faibles (ou les arbres) ne sont pas indépendants les uns des autres. En effet, les B jeux de données étant tous générés à partir des mêmes données initiales, ils sont dépendants les uns des autres.

Cela remet en question l’intérêt de l’approche suggérée par la formule de réduction de la variance Équation 9.1, qui n’est valide que pour des variables indépendantes. Dans le cas général, la covariance s’en mêle et la formule devient : Var(\mu) = \frac{Var(Z_1)}{n} + \left(1-\frac{1}{n}\right)C,\qquad C=Cov(Z_i,Z_j) ce qui peut être bien moins intéressant si la covariance est grande.

9.5.3 Forêts aléatoires (Random forests)

Pour limiter l’impact de la covariance sur la réduction de la variance par moyennage, l’idée est de réduire la dépendance des B arbres composant le modèle global.

L’algorithme des forêts aléatoires y parvient en injectant arbitrairement de l’aléatoire dans l’apprentissage de chaque arbre. Plus précisément, à chaque création de nœud, la recherche d’une coupe optimale se limite à un sous-ensemble de p variables choisies aléatoirement parmi les d composantes de \boldsymbol{x}.

À noter cependant que ces techniques (bagging ou forêts aléatoires) ne permettent plus d’interpréter le modèle aussi facilement, puisque celui-ci est maintenant une moyenne d’un (potentiellement grand) ensemble de modèles créés aléatoirement.