Arbre de décision

Un article de Wikivisual, l'encyclopédie libre.

Sommaire

1 Introduction
2 Exemple introductif
3 Construction d'un arbre de décision
4 Variantes
5 Généralisation à d'autres problématiques
6 Références
7 Liens externes
8 Logiciels

[modifier] Introduction

Dans le domaine de l'aide à la décision (informatique décisionnelle et datawarehouse) 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, ...). A ce titre, cette technique fait partie des méthodes d’apprentissage supervisé. Il s’agit de prédire avec le plus de précision possible 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 autant populaire en statistique qu’en apprentissage automatique. Son succès réside en grande partie sur la lisibilité du modèle de prédiction, l’arbre de décision, qu’elle fournit. Cette caractéristique est très importante, car le travail du statisticien consiste aussi à faire comprendre ses résultats afin d’emporter l’adhésion des décideurs.

La seconde caractéristique importante des arbres de décision est sa capacité à sélectionner automatiquement les variables discriminantes dans un fichier de données contenant un très grand nombre de variables potentiellement intéressantes. En ce sens, elle constitue une technique exploratoire privilégiée pour appréhender de gros fichiers de données.

[modifier] Exemple introductif

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) en fonction de données météo (Ensoleillement, Température, Humidité, Vent ; variables prédictives).

Image:Tableau Donnees Arbre.jpg

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

Image:Arbre de decision.jpg

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é à l’aide de 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 que l’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 très intuitive, c’est ce qui fait son succès. L’arbre peut être traduit en base de règles sans pertes d’informations. Si l’on considère la feuille la plus à gauche, nous pouvons aisément lire la règle d’affectation suivante : « Si ensoleillement = soleil et humidité < 77.5% alors jouer = oui ».

[modifier] Construction d'un arbre de décision

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

Comment choisir, parmi l’ensemble des variables disponibles, la variable de segmentation d’un sommet.
Lorsque la variable est continue, c’est le cas de la variable Humidité, comment déterminer le seuil de coupure lors de la segmentation (la valeur 77.5 dans l’arbre de décision ci-dessus).
Comment déterminer la bonne taille de l’arbre, est-il souhaitable de produire absolument des feuilles pures selon la variable à prédire, même si le groupe correspondant correspond à une fraction très faible des observations.
Enfin, comment affecter la valeur de la variable à prédire dans les feuilles. Lorsque le groupe est pur la réponse est évidente, dans le cas contraire, il nous faut adopter une stratégie.

[modifier] Critère de segmentation

Pour choisir la variable de segmentation sur un sommet, l’algorithme s’appuie sur une technique très fruste : il teste toutes les variables potentielles et choisit celle qui maximise un critère donné. Il faut donc 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 un grand nombre de critères informationnels ou statistiques, les plus utilisés sont l’entropie de Shannon et le coefficient 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.

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.

Dans notre cas, chaque valeur de la variable de segmentation permet de 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 systématiquement des arbres binaires, il cherche donc 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 afin de ne pas produire des groupes d’effectifs trop faibles, ne correspondant à aucune réalité statistique.

[modifier] Traitement des variables continues

Le traitement des variables continues doit être en accord avec l’utilisant du critère de segmentation. Dans la grande majorité des cas, le principe de segmentation des variables continues est très simple : trier les données selon la variable à traiter, tester tous les points de coupure possibles situé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 donc évalué les points de coupure situés à mi-distance des observations 1 à 5 correspondants aux valeurs {70, 70, 80, 85, 95} de Humidité.

[modifier] 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 théorie, cette attitude n’est pas tenable dans la pratique. En effet, nous travaillons souvent sur un échantillon représentatif d’une population. Tout l’enjeu est donc de trouver la bonne mesure entre capter l’information utile, correspondant réellement à une causalité dans la population, et ingérer les spécificités du fichier sur lequel nous sommes en train de travailler, correspondant en fait à un artefact statistique. C’est le problème de (sur)ajustement des modèles : trouver l'arbre le plus petit possible ayant la plus grande performance possible. 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 sert à rien de générer un modèle de très bonne qualité, si cette qualité n’est pas constante et se dégrade lorsque l’on applique ce modèle sur un nouvel ensemble de données.

La première stratégie pour traiter ce problème du surajustement 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 nécessaire lorsque le groupe est d’effectif trop faible ; ou encore, lorsque la pureté d’un sommet a atteint un niveau suffisant, nous considérons qu’il n’est plus nécessaire de le segmenter ; autre critère souvent 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.

La seconde stratégie consiste à construire l’arbre en deux temps : produire l’arbre le plus pur possible 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 réduire l’arbre, c’est la phase de post-élagage, en s’appuyant sur une autre fraction des données de manière à 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 permet de le désigner sans ambiguïté est « échantillon d’élagage », traduction directe de l’appellation anglo-saxonne « pruning set ».

Dans le graphique ci-dessous, nous observons l’évolution de l’erreur d’ajustement en fonction du 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 stade il ne correspond plus à la réalité, que l’on essaie de mesurer sur un second échantillon de données (échantillon test dans le graphique).

Image:Surajustement d'un modèle 2.jpg

Certaines théories statistiques (voir les travaux du mathématicien russe Vladimir Vapnik) se proposent 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 appelée « VC dimension », fournit une modélisation mathématique parfaite de la détermination de l’optimum d’un modèle, utilisable par conséquent pour générer des modèles qui assurent le meilleur compromis entre qualité et robustesse du modèle.

[modifier] 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 très simple est la procédure optimale dans un cadre très 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àd 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.

[modifier] Variantes

A 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, en vérité il n’existe pas de méthode qui se démarque systématiquement, en termes de performances, dans la pratique. Les méthodes les plus (re)connues sont certainement ID3, CHAID, CART et C4.5, C5. D'autres méthodes sont implémentées ici ou là dans des logiciels gratuits ou commerciaux (Exhaustive CHAID, QUEST, etc.)

Les arbres ont en revanche connu un net regain d’intérêt lorsque 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, notamment leur variabilité très 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 lorsqu’elles sont combinées, s’avèrent très performantes, c’est le cas notamment des Random Forests de Breiman.

[modifier] 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ù l’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.

Lorsque 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.

Lorsque 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.

[modifier] Références

L. Breiman, J. Friedman, R. Olshen, C. Stone: CART: Classification and Regression Trees, Wadsworth International, 1984.
R. Quinlan: C4.5: Programs for Machine Learning, Morgan Kaufmann Publishers Inc., 1993.
D. Zighed, R. Rakotomalala: Graphes d'Induction -- Apprentissage et Data Mining, Hermes, 2000.
Daniel T. Larose (adaptation française T. Vallaud): Des données à la connaissance : Une introduction au data-mining (1Cédérom), Vuibert, 2005.

[modifier] Liens externes

Arbres de décision, Tutoriel en ligne, Revue MODULAD n°33.
Manuel de statistiques en ligne, (en Anglais).

[modifier] 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.

SPSS, Clementine, SAS, SAS Enterprise Miner, ALICE, SPAD, STATISTICA, SYSTAT
SIPINA, un logiciel gratuit de construction des arbres de décision.
Liens vers d'autres logiciels d’induction des arbres de décision.

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 notamment des algorithmes de construction d'arbre de décision (ainsi très souvent que des heuristiques fonctionnelles), de manière tout à fait transparente, et en rendent l'utilisation directement opérationnelle :