Arbre de décision

Un arbre de décision est un outil d'aide à la décision ainsi qu'à l'exploration de données. Il sert à modéliser simplement, graphiquement et rapidement un phénomène mesuré plus ou moins complexe.



Catégories :

Décision - Statistiques - Métaheuristique - Apprentissage automatique

Recherche sur Google Images :


Source image : albinlix.fr
Cette image est un résultat de recherche de Google Image. Elle est peut-être réduite par rapport à l'originale et/ou protégée par des droits d'auteur.

Définitions :

  • Outil de modélisation graphique utilisé en Data Mining. C'est un arbre dont chaque nœud correspond à un choix, les fils étant les ... (source : francedecision)

Un arbre de décision est un outil d'aide à la décision ainsi qu'à l'exploration de données. Il sert à modéliser simplement, graphiquement et rapidement un phénomène mesuré plus ou moins complexe. Sa lisibilité, sa rapidité d'exécution et le peu d'hypothèses nécessaires a priori expliquent sa popularité actuelle.

Introduction

Dans le domaine de l'aide à la décision (informatique décisionnelle et entrepôt de données) et du data mining, certains algorithmes produisent des arbres de décision, utilisés pour répartir une population d'individus (de clients par exemple) en groupes homogènes, selon un ensemble de variables discriminantes (l'âge, la catégorie socio-professionnelle, ... ) en fonction d'un objectif fixé et connu (chiffres d'affaires, réponse à un mailing, ... ). À ce titre, cette technique fait partie des méthodes d'apprentissage supervisé. Il s'agit de prédire avec le plus de précision envisageable les valeurs prises par la variable à prédire (objectif, variable cible, variable d'intérêt, attribut classe, variable de sortie, ... ) à partir d'un ensemble de descripteurs (variables prédictives, variables discriminantes, variables d'entrées, ... ).

Cette technique est tout autant populaire en statistique qu'en apprentissage automatique. Son succès réside en grande partie à ses caractéristiques :

Exemple didactique

Pour mieux appréhender l'induction des arbres de décision, nous allons reprendre un exemple décrit dans l'ouvrage de Quinlan (1993). Il s'agit de prédire le comportement de sportifs (Jouer ; variable à prédire) selon données météo (Ensoleillement, Température, Humidité, Vent ; variables prédictives).

Tableau de données Weather (Quinlan, 1993)

L'algorithme d'apprentissage cherche à produire des groupes d'individus le plus homogène envisageable du point de vue de la variable à prédire à partir des variables de météo. Le partitionnement est décrit avec un arbre de décision.

Arbre de décision sur les données Weather

Sur chaque sommet de l'arbre est décrit la distribution de la variable à prédire. Dans le cas du premier sommet, la racine de l'arbre, nous constatons qu'il y a 14 observations dans notre fichier, 9 d'entre eux ont décidé de jouer (Jouer = oui), 5 ont décidé le contraire (Jouer = non).

Ce premier sommet est segmenté avec la variable Ensoleillement, 3 sous-groupes ont été produits. Le premier groupe à gauche (Ensoleillement = Soleil) comporte 5 observations, 2 d'entre eux correspondent à Jouer = oui, 3 à Jouer = non.

Chaque sommet est ainsi itérativement traité jusqu'à ce qu'on obtienne des groupes suffisamment homogènes. Elles correspondent aux feuilles de l'arbre, des sommets qui ne sont plus segmentés.

La lecture d'un arbre de décision est particulièrement intuitive, c'est ce qui fait son succès. L'arbre peut être traduit en base de règles sans pertes d'informations. Si on considère la feuille la plus à gauche, nous pouvons facilement lire la règle d'affectation suivante : «Si ensoleillement = soleil et humidité < 77.5% alors jouer = oui».

Construction d'un arbre de décision

Pour construire un arbre de décision, nous devons répondre aux 4 questions suivantes :

Critère de segmentation

Pour choisir la variable de segmentation sur un sommet, l'algorithme s'appuie sur une technique particulièrement fruste : il teste l'ensemble des variables potentielles et choisit celle qui maximise un critère donné. Il faut par conséquent que le critère utilisé caractérise la pureté (ou le gain en pureté) lors du passage du sommet à segmenter vers les feuilles produites par la segmentation. Il existe la plupart de critères informationnels ou statistiques, les plus utilisés sont l'entropie de Shannon et le cœfficient de Gini et leurs variantes.

Une autre manière de caractériser la segmentation est de mesurer le lien ou la causalité entre la variable candidate et la variable à prédire. Dans ce cas, le critère le plus utilisé est le lien du KHI-2 et ses dérivés.

Certains critères permettent de prendre en compte la nature ordinale de la cible, et ce, en utilisant des mesures ou des heuristiques[1] appropriées.

Au final, ces critères, pour peu qu'ils permettent de faire tendre le partitionnement vers la constitution de groupes purs, jouent peu sur les performances des algorithmes.

Chaque valeur de la variable de segmentation sert à produire une feuille (cf. 3 valeurs d'ensoleillement produit 3 sommets), c'est le cas de l'algorithme C4.5 par exemple. Les algorithmes d'apprentissage peuvent différer sur ce point. Certains tels que CART produisent toujours des arbres binaires, il cherche par conséquent lors de la segmentation le regroupement binaire qui optimise le critère de segmentation. D'autres tels que CHAID cherchent à effectuer les regroupements les plus pertinents en s'appuyant sur des critères statistiques. Selon la technique, nous obtiendrons des arbres plus ou moins larges, l'idée est d'éviter de fractionner exagérément les données pour ne pas produire des groupes d'effectifs trop faibles, ne correspondant à aucune réalité statistique.

Traitement des variables continues

Le traitement des variables continues doit être en accord avec l'utilisation du critère de segmentation. Dans la grande majorité des cas, le principe de segmentation des variables continues est particulièrement simple : trier les données selon la variable à traiter, tester l'ensemble des points de coupure envisageables localisés entre deux points successifs et évaluer la valeur du critère dans chaque cas. Le point de coupure optimal correspond tout simplement à celui qui maximise le critère de segmentation.

Dans notre exemple, l'algorithme a par conséquent évalué les points de coupure localisés à mi-distance des observations 1 à 5 correspondants aux valeurs {70, 75, 80, 85, 95} de Humidité.

Définir la bonne taille de l'arbre

L'objectif étant de produire des groupes homogènes, il paraît naturel de fixer comme règle d'arrêt de construction de l'arbre la constitution de groupes purs du point de vue de la variable à prédire. C'est le cas dans notre exemple ci-dessus, aucune des feuilles de l'arbre ne comporte de contre-exemples. Souhaitable en principe, cette attitude n'est pas tenable dans la pratique.

En effet, nous travaillons fréquemment sur un échantillon qu'on espère représentatif d'une population. Tout l'enjeu est par conséquent de trouver la bonne mesure entre capter l'information utile, correspondant réellement à une relation dans la population, et ingérer les spécificités du fichier sur lequel nous sommes en train de travailler (l'échantillon dit d'apprentissage), correspondant en fait à un artefact statistique. Autement dit, il ne faut jamais oublier que la performance de l'arbre est évaluée sur les données mêmes qui ont servi à sa construction : plus le modèle est complexe (plus l'arbre est grand, plus il a de branches, plus il a de feuilles), plus on court le risque de voir ce modèle incapable d'être extrapolé à de nouvelles données, c'est-à-dire de rendre compte de la réalité que nous essayons précisément d'appréhender. À la limite, et c'est spécifiquement vrai des arbres de décision, un modèle est capable de répliquer précisément n'importe quel échantillon de données, sans pour tout autant appréhender une quelconque réalité... En effet, si dans un cas extrême on décide de faire pousser notre arbre le plus loin envisageable, nous pouvons obtenir un arbre composé d'autant de feuilles que d'individus dans l'échantillon d'apprentissage. Notre arbre ne commet alors aucune erreur sur cet échantillon dans la mesure où il en épouse l'ensemble des caractéristiques : performance égale à 100%. Tant qu'on applique ce modèle sur de nouvelles données qui par nature n'ont pas l'ensemble des caractéristiques de notre échantillon d'apprentissage (il s'agit simplement d'un autre échantillon) sa performance va par conséquent se dégrader pour à la limite se rapprocher de 0%... !

Ainsi, quand on construit un arbre de décision, on risque ce qu'on nomme un surajustement du modèle : le modèle semble performant (son erreur moyenne est particulièrement faible) mais il ne l'est en réalité absolument pas ! Il va nous falloir trouver l'arbre le plus petit envisageable ayant la plus grande performance envisageable. Plus un arbre est petit et plus il sera stable dans ses prévisions futures (en statistiques, le principe de parcimonie prévaut presque toujours)  ; plus un arbre est performant, plus il est satisfaisant pour l'analyste. Il ne permet de rien de générer un modèle de très bonne qualité, si cette qualité n'est pas constante et se dégrade quand on applique ce modèle sur un nouvel ensemble de données.

C'est à dire, pour éviter un sur-ajustement de nos arbres (et c'est aussi vrai de l'ensemble des modèles mathématiques qu'on pourrait construire), il convient d'appliquer un principe de parcimonie et de réaliser des arbitrages performance/complexité des modèles utilisés. À performance identique, on préfèrera toujours le modèle le plus simple, si on souhaite pouvoir utiliser ce modèle sur de nouvelles données complètement inconnues.

Le problème du sur-ajustement des modèles

Comment réaliser cet arbitrage performance/complexité des modèles utilisés ? En premier lieu, en évaluant la performance d'un ou de plusieurs modèles sur les données qui ont servi à sa construction (le ou les échantillons d'apprentissage), mais également sur ce qu'on nomme un (ou plusieurs) échantillon de test , c'est-à-dire des données à notre disposition mais que nous décidons volontairement de ne pas utiliser dans la construction de nos modèles[2]. Tout se passe comme si ces données de test étaient de nouvelles données, la réalité. C'est surtout la stabilité de la performance de nos modèles sur ces deux types d'échantillon nous permettra de juger de son sur-ajustement potentiel et par conséquent de sa capacité à être utilisé avec un risque d'erreur maitrisé dans des conditions réelles où les données ne sont pas connues à l'avance...

Sur-ajustement d'un modèle : arbitrage performance / complexité

Dans le graphique ci-contre, nous observons l'évolution de l'erreur d'ajustement d'un arbre de décision selon le nombre de feuilles de l'arbre (complexité). Nous constatons que si l'erreur décroît constamment sur l'échantillon d'apprentissage, à partir d'un certain niveau de complexité (de particulièrement nombreuses branches et de très nombreuses feuilles) ce modèle s'éloigne de la réalité, réalité qu'on essaie de mesurer ou en tout cas d'approcher sur un second échantillon de données (échantillon test dans le graphique).

Dans le cas des arbres de décisions, plusieurs types de solutions algorithmiques ont été envisagées pour tenter d'éviterdans la mesure du possible un problème de sur-ajustement potentiel des modèles : il s'agit des techniques dites de pré ou de post élagage des arbres.

Certaines théories statistiques (voir les travaux du mathématicien russe Vladimir Vapnik) vont même jusqu'à avoir pour objet de trouver l'optimum entre l'erreur commise sur l'échantillon d'apprentissage et celle commise sur l'échantillon de test . La théorie de Vapnik Chervonenkis, «Structured Risk Minimization (SRM)», en utilisant une variable nommée «VC dimension», apporte une modélisation mathématique idéale de la détermination de l'optimum d'un modèle, utilisable donc pour générer des modèles qui assurent le meilleur compromis entre qualité et robustesse du modèle.

Dans l'ensemble des cas, ces solutions algorithmiques sont complémentaires des analyses de performances comparées et de stabilité effectuées sur les échantillons d'apprentissage et de test .

Le pré-élagage

La première stratégie utilisable pour éviter un surajustement massif des arbres de décision consiste à proposer des critères d'arrêt lors de la phase d'expansion. C'est le principe du pré-élagage. Nous considérons par exemple qu'une segmentation n'est plus indispensable quand le groupe est d'effectif trop faible ; ou encore, quand la pureté d'un sommet a atteint un niveau suffisant, nous considérons qu'il n'est plus indispensable de le segmenter ; autre critère fréquemment rencontré dans ce cadre, l'utilisation d'un test statistique pour évaluer si la segmentation introduit un apport d'information significatif quant à la prédiction des valeurs de la variable à prédire.

Le post-élagage

La seconde stratégie consiste à construire l'arbre en deux temps : produire l'arbre le plus pur envisageable dans une phase d'expansion en utilisant une première fraction de l'échantillon de données (échantillon d'apprentissage à ne pas confondre avec la totalité de l'échantillon, en anglais «growing set» est moins ambigu)  ; puis effectuer une marche arrière pour diminuer l'arbre, c'est la phase de post-élagage, en s'appuyant sur une autre fraction des données de façon à optimiser les performances de l'arbre. Selon les logiciels, cette seconde portion des données est désignée par le terme d'échantillon de validation ou échantillon de test , introduisant une confusion avec l'échantillon utilisé pour mesurer les performances des modèles. Le terme qui sert au désigner sans ambiguïté est «échantillon d'élagage», traduction directe de l'appellation anglo-saxonne «pruning set».

Affectation de la conclusion sur chaque feuille

Une fois l'arbre construit, il faut préciser la règle d'affectation dans les feuilles. A priori, si elles sont pures, la réponse est évidente. Si ce n'est pas le cas, une règle simple est de décider comme conclusion de la feuille la classe majoritaire, celle qui est la plus représentée.

Cette technique particulièrement simple est la procédure optimale dans un cadre particulièrement précis : les données sont issues d'un tirage aléatoire simple dans la population ; la matrice des coûts de mauvaise affectation est unitaire (symétrique) c'est-à-dire affecter à bon escient ne coûte rien (coût égal à 0), et affecter à tort coûte 1 quel que soit le cas de figure. En dehors de ce canevas, la règle de la majorité n'est pas justifiée. Il reste néanmoins que c'est un référentiel facile à utiliser dans la pratique.

Les différents algorithmes envisageables

À partir de ces 4 points, il existe un très grand nombre de variantes. Certaines mettent l'accent sur tel ou tel aspect de l'algorithme de construction, mais il n'existe pas de méthode qui soit dans la pratique toujours plus performante. Voici une liste non exhaustive des algorithmes classiquement utilisés :

  • SLIQ
  • Exhaustive CHAID
  • QUEST
  • VFDT
  • UFFT
  • ...

Ces algorithmes se distinguent par l'ou les critères de segmentation utilisés, par les méthodes d'élégages implémentées... mais également par leur manière de gérer les données manquantes dans nos prédicteurs. Ce point prend toute son importance dans la pratique. En effet, les données à disposition en entreprise par exemple sont quasi toujours incomplètes. Que faire en présence de données manquantes ?

Les arbres ont connu un net regain d'intérêt quand les méthodes d'agrégation des classifieurs tels que le boosting ou le bagging ont été développées et popularisées dans la communauté de l'apprentissage automatique. Certaines des caractéristiques des arbres, surtout leur variabilité particulièrement marquée, leur permettent de tirer parti des avantages de la combinaison des prédicteurs. Des techniques spécifiques ont même été développées pour produire des arbres individuellement peu efficaces, mais quand elles sont combinées, s'avèrent particulièrement performantes, c'est le cas surtout des Random Forests (forêts d'arbres) de Breiman.

Dans des processus de data mining les arbres de décision sont quelquefois combinés à des techniques plus classiques de modélisation d'un objectif fixé : analyse discriminante, régressions logisitiques (régression logistique), régressions linéaires (régression linéaire), réseaux de neurones (perceptrons multicouches, radial basis function network... )... Ils sont aussi fréquemment combinés entre eux pour tirer profit de leurs avantages respectifs. Des procédures d'agrégation des performances des différents modèles utilisés, quelquefois nommées procédures de vote, sont alors mises en place pour obtenir une performance maximale, tout en controlant et en minimisant le niveau de complexité de la totalité des modèles utilisés.

Généralisation à d'autres problématiques

Les arbres de décision telles qu'ils ont été présentés ici sont dédiés à l'apprentissage supervisé où on essaie de prédire (expliquer) les valeurs prises par une variable discrète (Etre malade ou pas, Répondre positivement à une offre promotionnelle ou pas, etc. ) à partir d'une série de variables discriminantes de type quelconque. En réalité, la démarche peut être étendue à d'autres types de problématiques.

Quand la variable cible est continue, nous nous situons dans le cadre de la régression (la méthode la plus populaire dans ce cadre est la Régression linéaire). Le même schéma d'exploration peut être appliqué, sauf qu'au lieu d'optimiser le taux d'erreur, nous optimisons l'erreur quadratique, et le critère de segmentation devient la décomposition de la variance : nous choisissons la variable qui maximise la variance inter-classes. On parle dans ce cas d'arbres de régression, la méthode CART, dans sa version RT (Regression Tree) est la plus connue.

Quand nous avons affaire à plusieurs variables cibles, nous nous situons dans un problème de classification automatique (ou de typologie). On parle dans ce cas d'arbres de classification (Clustering Tree en anglais). Le critère d'évaluation des partitions est l'inertie, qui est ni plus ni moins qu'une généralisation de la variance dans un cadre multidimensionnel. Les méthodes les plus connues sont dues à Chavent (1998, les Méthodes Divisives Monothétiques) et Blockeel (1998, Predictive Clustering Tree). Il semble que les typologies proposées par ces techniques soient aussi bonnes, en termes d'inertie expliquée, que celles produites par les approches classiques (Classification Ascendante Hiérarchique, Nuées dynamiques, etc. ), avec la lisibilité des résultats en plus.

Notes

  1. Des heuristiques sont surtout utilisées quand on cherche à diminuer la complexité de l'arbre en agrégeant les modalites des variables utilisées comme prédicteurs de la cible. A titre d'exemple, pour le cas des modalités d'une variable de classes d'âge, on ne va autoriser que des regroupements de classes d'âge contigues.
  2. Le problème du sur-ajustement des modèles n'est pas propre aux arbres de décisions mais commun à la totalité des techniques de modélisation mathématico-informatiques. Il est au centre des processus de data mining.

Références

Liens externes

Logiciels

Tous les principaux logiciels commerciaux d'analyse statistique ou de Data Mining intègrent un module de construction graphique des arbres de décision. L'offre est moins pléthorique concernant les logiciels gratuits ou libres.

Certains progiciels de gestion de campagnes marketing et/ou d'optimisation de campagnes marketing (c'est aussi le cas d'autres problématiques fonctionnelles) intègrent surtout des algorithmes de construction d'arbre de décision (ainsi fréquemment que des heuristiques fonctionnelles), de manière particulièrement transparente, et en rendent l'utilisation directement opérationnelle :

Aujourd'hui, la majorité des grands éditeurs commerciaux de bases de données relationnelles (Base de données relationnelle, Oracle (base de données) , Microsoft SQL Server... ) embarquent de nombreux algorithmes de data mining dont certains arbres de décision. L'idée est de permettre aux analystes d'exploiter toute la puissance de calcul de ces bases de données et des machines serveur sur lesquelles elles sont installées.

Recherche sur Amazone (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Arbre_de_d%C3%A9cision.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 07/04/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu