Une introduction aux arbres de décisionStéphane Caron |
Les arbres de décision sont l’une des structures de données majeures de l’apprentissage statistique. Leur fonctionnement repose sur des heuristiques qui, tout en satisfaisant l’intuition, donnent des résultats remarquables en pratique (notamment lorsqu’ils sont utilisés en « forêts aléatoires »). Leur structure arborescente les rend également lisibles par un être humain, contrairement à d’autres approches où le prédicteur construit est une « boîte noire ».
L’introduction que nous proposons ici décrit les bases de leur fonctionnement tout en apportant quelques justifications théoriques. Nous aborderons aussi (brièvement) l’extension aux Random Forests. On supposera le lecteur familier avec le contexte général de l’apprentissage supervisé.1
Suivez le lien pour la version PDF.
Un arbre de décision modélise une hiérarchie de tests sur les valeurs d’un ensemble de variables appelées attributs. À l’issue de ces tests, le prédicteur produit une valeur numérique ou choisit un élément dans un ensemble discret de conclusions. On parle de régression dans le premier cas et de classification dans le second. Par exemple, l’arbre de la figure 1 ci-dessus décide une réponse booléenne (classification dans l’ensemble {oui, non}) en fonction des valeurs discrètes des attributs {difficile, durée, motivation, surprenant}.
Un ensemble de valeurs pour les différents attributs est appelé une « instance », que l’on note généralement (x, y) où y est la valeur de l’attribut que l’on souhaite prédire et x = x1, …, xm désignent les valeurs des m autres attributs. L’apprentissage d’un arbre de décision se fait sur un ensemble d’instances T = {(x, y)} appelé « ensemble d’entraînement ».
date motivation durée (h) difficile surprenant température (K) 11/03 oui 1 non oui 271 14/04 oui 4 oui oui 293 03/01 non 3 oui non 297 25/12 oui 2 oui non 2911 ⋮ ⋮ ⋮ ⋮ ⋮ ⋮
Tableau 1: Exemple d’ensemble d’entraînement pour l’arbre de la figure 1
À partir d’un ensemble d’observations T = {(x, y)}, on souhaite construire un arbre de décision prédisant l’attribut y en fonction de nouvelles instances x. Pour ce faire, il existe essentiellement deux familles d’algorithmes à ce jour : les arbres de Quinlan [10, 7] et les arbres CART [2]. Les deux approches suivent le paradigme diviser-pour-régner, que l’on peut schématiser (dans le cas d’attributs à valeurs discrètes) par le pseudo-code suivant :
1: ArbreDecision(T) 2: si "condition d'arret" 3: retourner feuille(T) 4: sinon 5: choisir le "meilleur" attribut i entre 1 et m 6: pour chaque valeur v de l'attribut i 7: T[v] = {(x, y) de T tels que x_i = v} 8: t[v] = ArbreDecision(T[v]) 9: fin pour 10: retourner noeud(i, {v -> t[v]}) 11: fin si
Figure 2: Constructeur pour des attributs à valeurs discrètes
Où noeud(i, {v → tv}) désigne le constructeur d’un nœud qui teste l’attribut i et possède un descendant tv pour chaque valeur v possible. Les parties entre guillemets correspondent à des choix heuristiques propres à chaque algorithme :
Lorsque l’attribut xi est à valeurs réelles, on adapte l’algorithme ci-dessus en choisissant une valeur de partage (split value) v et en effectuant le test xi ≤ v. On notera « noeud(i, v, t≤, t>) » le constructeur associé. En particulier, si tous les attributs sont réels, l’arbre de décision obtenu est binaire.
Considérons dans un premier temps le cas de la régression, i.e. lorsque la valeur à prédire est un nombre réel. Une fois l’arbre construit, la régression d’une nouvelle instance x explore l’une de ses branches comme suit :
1: Regresser(x, t) 2: si t = feuille(Tf) 3: retourner la moyenne des y de Tf 4: sinon si t = noeud(i, v, t_left, t_right) 5: si x[i] <= v 6: retourner Regresser(x, t_left) 7: sinon, x[i] > v 8: retourner Regresser(x, t_right) 9: sinon, t = noeud(i, {v -> t[v]}) 10: retourner Regresser(x, t[x[i]]) 11: fin si
L’exploration aboutit à une feuille f construite sur un ensemble d’entraînement Tf. Notons Yf := { y | ∃ (x, y) ∈ Tf }. La valeur prédite est la moyenne y de Yf, prédiction qui sera d’autant meilleure que la distribution des y ∈ Yf est concentrée autour de y. De manière équivalente, plus la dispersion des y ∈ Yf est grande, plus la prédiction sera mauvaise. Dans des solutions comme CART [2], on utilise la variance σ2 des y ∈ Yf pour mesurer cette dispersion, et par ce biais estimer la « qualité » de la feuille f.
CART utilise également ce critère de variance pour choisir le meilleur attribut de partage à la ligne 4 du constructeur 1. Un attribut i produit une partition T = ∪vi Tvi, chaque sous-ensemble ayant sa propre variance V(Tvi). La variance attendue après un branchement sur l’attribut i (pour une instance (x, y) tirée uniformément au hasard dans T) est alors
| Vi = |
|
| V(Tvi), |
et l’attribut i* qui minimise cette valeur est alors considéré (heuristiquement) comme le meilleur choix possible.
Nous allons voir dans la section suivante que ce choix de minimiser la variance n’est pas seulement heuristique : il est également intrinsèquement lié à la minimisation de l’erreur quadratique de prédiction.
L’une des principales hypothèses faites dans les travaux de Machine Learning est que les instances (x, y) sont toutes tirées indépendamment selon une même loi de probabilité P inconnue. On peut alors voir les (x, y) ∈ T comme les réalisations i.i.d. de variables aléatoires X et Y (éventuellement corrélées). De même, les y ∈ Yf sont des réalisations i.i.d. d’une certaine variable aléatoire Yf, qui n’est autre que Y conditionnée par les événements {Xi ≤ ou > v} testés le long de la branche menant à f.
Dans ce contexte, y est un estimateur de E(Yf) et l’erreur quadratique commise en prédisant y pour une nouvelle instance de Yf s’écrit
|
(y et E(Yf) sont ici constantes.) Le second terme de cette erreur n’est autre que la variance σ2 de Yf, dont σ2 est un estimateur. Minimiser σ pour la feuille f vise donc à minimiser ce second terme, mais également le premier. En effet, y étant une moyenne emprique y = 1/k ∑i=1n Yf(i) de réalisations de Yf, on a ET(y) = E(Yf) et VT(y) = 1/n σ2.2 L’inégalité de Markov s’écrit alors
| PT [( |
| − E(Yf))2 > x] < |
| , |
et l’on voit que réduire σ a pour effet de concentrer la distribution de (y − E(Yf)) en zéro.
Le raisonnement pour classifier une instance est similaire à la régression :
1: Classifier(x, t) 2: si t = feuille(Tf) 3: retourner la classe majoritaire de Tf 4: sinon si t = noeud(i, v, t_left, t_right) 5: si x[i] <= v 6: retourner Classifier(x, t_left) 7: sinon, x[i] > v 8: retourner Classifier(x, t_right) 9: sinon, t = noeud(i, {v -> t[v]}) 10: retourner Classifier(x, t[x[i]]) 11: fin si
Figure 3: Constructeur pour des attributs à valeurs discrètes
Si toutes ou la grande majorité des instances de Tf ont la même classe c ∈ { 1, …, C }, c apparaît comme la meilleure prédiction possible, et la fraction des instances de classe c dans Tf est un indicateur de la « sûreté » de cette prédiction. Dans le cas contraire, prédire la classe la plus fréquente reste une option, mais la sûreté de la prédiction n’en sera que moins bonne.
Les observations précédentes soulignent qu’un arbre de classification est d’autant meilleur que (les instances de) ses feuilles sont de classes homogènes. On souhaite alors définir une mesure de l’hétérogénéité d’une feuille qui jouera le même rôle que la variance dans le cas de la régression. Soient p1, …, pC les fréquences relatives des classes 1, …, C dans Tf, et c* la classe la plus fréquente. Voici trois mesures fréquemment rencontrées dans la littérature :
La mesure d’erreur est utilisée de même pour choisir le meilleur attribut de partage : si un attribut i partitionne T en T = ∪vi Tvi, chaque ensemble Tvi a sa propre erreur e(Tvi) et l’erreur attendue après un branchement sur cet attribut (pour un élément tiré uniformément au hasard de T) est
| ei = |
|
| e(Tvi). |
L’attribut qui minimise cette erreur est (heuristiquement) considéré comme le meilleur choix possible.
Les arbres tels que nous venons de les aborder présentent plusieurs limitations :
Il existe des solutions à ces problèmes qui travaillent directement sur les arbres, notamment l’élaguage [7, 5]. En pratique, on choisit souvent de « bagger » (voir ci-après) les arbres plutôt que de les utiliser comme prédicteurs individuels, un contexte dans lequel le surapprentissage et la sous-optimalité dû aux heuristiques posent moins de problèmes.
Le « bagging », acronyme pour « bootstrap aggregating », est un méta-algorithme qui combine les deux techniques sus-acronymées :
Le bagging corrige plusieurs défauts des arbres de décision, notamment leur instabilité (de petites modifications dans l’ensemble d’apprentissage peuvent entraîner des arbres très différents) et leur tendance à surapprendre. La contrepartie à payer est une perte de lisibilité : les prédictions d’une forêts d’arbres « baggés » ne sont plus le fruit d’un raisonnement, mais un consensus de raisonnements potentiellement très différents.
L’analyse théorique du bagging demeure incomplète à ce jour : plusieurs arguments aident à comprendre son impact et suggèrent des conditions dans lesquelles il améliore les prédictions, mais l’élaboration d’un modèle dans lequel cet impact est compris et mesurable reste un sujet de recherche.
Proposées en 2002 par Leo Breiman et Adele Cutler [1], les forêts aléatoires (Random Forests) modifient l’algorithme 1 pour que les arbres construits soient adaptés au bagging. Les principales modifications sont les suivantes :
Pour une description plus approfondie des forêts aléatoires et des outils qui les accompagnent, voir [1, 5].
Vous trouverez un exemple d’implémentation en Python/SQLite de l’intégralité de ces notions dans la bibliothèque PyDTL [3], open source et disponible sous licence LGPL. Celle-ci s’inspire aussi bien de CART [2] que de C4.5 [10, 7] tout en adaptant la construction aux forêts aléatoires. Certains logiciels intègrent également des modules pour les arbres de décision, notamment Weka [9], milk [4] et Orange [8].
Ici ce termine notre introduction à l’apprentissage d’arbres de décision. Il y a sans doute de nombreux points à améliorer, et je serais enchanté d’y remédier si vous trouvez le temps de m’écrire pour me les signaler. Pour une étude plus approfondie de ces techniques, ou plus généralement de l’apprentissage supervisé et du Data Mining, je vous recommande vivement la lecture des Elements of Statistical Learning de Hastie et al. [5].
Ce document a été traduit de LATEX par HEVEA
