Loading AI tools
méthode basée sur l'utilisation d'un arbre de décision comme modèle prédictif De Wikipédia, l'encyclopédie libre
L’apprentissage par arbre de décision désigne une méthode basée sur l'utilisation d'un arbre de décision comme modèle prédictif. On l'utilise notamment en fouille de données et en apprentissage automatique.
| Problème lié | |
|---|---|
| Structure des données |
Dans ces structures d'arbre, les feuilles représentent les valeurs de la variable-cible et les embranchements correspondent à des combinaisons de variables d'entrée qui mènent à ces valeurs. En analyse de décision, un arbre de décision peut être utilisé pour représenter de manière explicite les décisions réalisées et les processus qui les amènent. En apprentissage et en fouille de données, un arbre de décision décrit les données mais pas les décisions elles-mêmes, l'arbre serait utilisé comme point de départ au processus de décision.
C'est une technique d'apprentissage supervisé : on utilise un ensemble de données pour lesquelles on connaît la valeur de la variable-cible afin de construire l'arbre (données dites étiquetées), puis on extrapole les résultats à l'ensemble des données de test. Les arbres de décision font partie des algorithmes les plus populaires en apprentissage automatique[1],[2].
L'apprentissage par arbre de décision est une méthode classique en apprentissage automatique [3]. Son but est de créer un modèle qui prédit la valeur d'une variable-cible depuis la valeur de plusieurs variables d'entrée.
Une des variables d'entrée est sélectionnée à chaque nœud intérieur (ou interne, nœud qui n'est pas terminal) de l'arbre selon une méthode qui dépend de l'algorithme et qui sera discutée plus loin. Chaque arête vers un nœud-fils correspond à un ensemble de valeurs d'une variable d'entrée, de manière que l'ensemble des arêtes vers les nœuds-fils couvrent toutes les valeurs possibles de la variable d'entrée.
Chaque feuille (ou nœud terminal de l'arbre) représente soit une valeur de la variable-cible, soit une distribution de probabilité des diverses valeurs possibles de la variable-cible. La combinaison des valeurs des variables d'entrée est représentée par le chemin de la racine jusqu'à la feuille.
L'arbre est en général construit en séparant l'ensemble des données en sous-ensembles en fonction de la valeur d'une caractéristique d'entrée. Ce processus est répété sur chaque sous-ensemble obtenu de manière récursive, il s'agit donc d'un partitionnement récursif.
La récursion est achevée à un nœud soit lorsque tous les sous-ensembles ont la même valeur de la caractéristique-cible, ou lorsque la séparation n'améliore plus la prédiction. Ce processus est appelé induction descendante d'arbres de décision (top-down induction of decision trees ou TDIDT)[4], c'est un algorithme glouton puisqu'on recherche à chaque nœud de l'arbre le partage optimal, dans le but d'obtenir le meilleur partage possible sur l'ensemble de l'arbre de décision. C'est la stratégie la plus commune pour apprendre les arbres de décision depuis les données.
En fouille de données, les arbres de décision peuvent aider à la description, la catégorisation ou la généralisation d'un jeu de données fixé.
L'ensemble d'apprentissage est généralement fourni sous la forme d'enregistrements du type :
La variable désigne la variable-cible que l'on cherche à prédire, classer ou généraliser. Le vecteur est constitué des variables d'entrée etc. qui sont utilisées dans ce but.
Il existe deux principaux types d'arbre de décision en fouille de données :
Le terme d'analyse d'arbre de classification et de régression (CART, d'après l'acronyme anglais) est un terme générique se référant aux procédures décrites précédemment et introduites par Breiman et al.[5]. Les arbres utilisés dans le cas de la régression et dans le cas de la classification présentent des similarités mais aussi des différences, en particulier en ce qui concerne la procédure utilisée pour déterminer les séparations des branches.
L'apprentissage par arbre de décision consiste à construire un arbre depuis un ensemble d'apprentissage constitué de n-uplets étiquetés. Un arbre de décision peut être décrit comme un diagramme de flux de données (ou flowchart) où chaque nœud interne décrit un test sur une variable d'apprentissage, chaque branche représente un résultat du test, et chaque feuille contient la valeur de la variable cible (une étiquette de classe pour les arbres de classification, une valeur numérique pour les arbres de régression).
Usuellement, les algorithmes pour construire les arbres de décision sont construits en divisant l'arbre du sommet vers les feuilles en choisissant à chaque étape une variable d'entrée qui réalise le meilleur partage de l'ensemble d'objets, comme décrit précédemment[6]. Pour choisir la variable de séparation sur un nœud, les algorithmes testent les différentes variables d'entrée possibles et sélectionnent celle qui maximise un critère donné.
Dans le cas des arbres de classification, il s'agit d'un problème de classification automatique. Le critère d’évaluation des partitions caractérise l'homogénéité (ou le gain en homogénéité) des sous-ensembles obtenus par division de l'ensemble. Ces métriques sont appliquées à chaque sous-ensemble candidat et les résultats sont combinés (par exemple, moyennés) pour produire une mesure de la qualité de la séparation.
Il existe un grand nombre de critères de ce type, les plus utilisés sont l’entropie de Shannon, l'indice de diversité de Gini et leurs variantes.
Dans le cas des arbres de régression, le même schéma de séparation peut être appliqué, mais au lieu de minimiser le taux d’erreur de classification, on cherche à maximiser la variance inter-classes (avoir des sous-ensembles dont les valeurs de la variable-cible soient les plus dispersées possibles). En général, le critère utilise le test du chi carré.
Certains critères permettent de prendre en compte le fait que la variable-cible prend des valeurs ordonnées, en utilisant des mesures ou des heuristiques appropriées[7].
Chaque ensemble de valeurs de la variable de segmentation permet de produire un nœud-fils. Les algorithmes d’apprentissage peuvent différer sur le nombre de nœud-fils produits : certains (tels que CART) produisent systématiquement des arbres binaires, et cherchent donc la partition binaire qui optimise le critère de segmentation. D’autres (comme 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. Pour que la méthode soit efficace, il faut é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.
Dans le cas de variables de segmentation continues, le critère de segmentation choisi doit être adéquat. En général, on trie les données selon la variable à traiter, puis on teste les différents points de coupure possibles en évaluant le critère pour chaque cas, le point de coupure optimal sera celui qui maximise le critère de segmentation.
Il n'est pas toujours souhaitable en pratique de construire un arbre dont les feuilles correspondent à des sous-ensembles parfaitement homogènes du point de vue de la variable-cible. En effet, l'apprentissage est réalisé sur un échantillon que l'on espère représentatif d’une population. L'enjeu de toute technique d'apprentissage est d'arriver à saisir l'information utile sur la structure statistique de la population, en excluant les caractéristiques spécifiques au jeu de données étudié. Plus le modèle est complexe (plus l'arbre est grand, plus il a de branches, plus il a de feuilles), plus l'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 l'on cherche à appréhender.
En particulier, dans le cas extrême où l'arbre a autant de feuilles qu'il y a d'individus dans la population (d'enregistrements dans le jeu de données), l'arbre ne commet alors aucune erreur sur cet échantillon puisqu'il en épouse toutes les caractéristiques, mais il n'est pas généralisable à un autre échantillon. Ce problème, nommé surapprentissage ou surajustement (overfitting), est un sujet classique de l'apprentissage automatique et de la fouille de données.
On cherche donc à construire un arbre qui soit le plus petit possible en assurant la meilleure performance possible. Suivant le principe de parcimonie, plus un arbre sera petit, plus il sera stable dans ses prévisions futures. Il faut réaliser un arbitrage entre performance et complexité dans les modèles utilisés. À performance comparable, on préférera toujours le modèle le plus simple, si l'on souhaite pouvoir utiliser ce modèle sur de nouveaux échantillons.
Pour réaliser l'arbitrage performance/complexité des modèles utilisés, on évalue 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 un ou plusieurs échantillons de validation : des données étiquetées à disposition mais que l'on décide volontairement de ne pas utiliser dans la construction des modèles.
Ces données sont traitées comme les données de test, la stabilité de la performance des modèles sur ces deux types d'échantillons permettra de juger de son surajustement et donc de sa capacité à être utilisé avec un risque d'erreur maîtrisé dans des conditions réelles où les données ne sont pas connues à l'avance.
Dans le graphique ci-contre, nous observons l’évolution de l’erreur d’ajustement d'un arbre de décision en fonction du nombre de feuilles de l’arbre (qui mesure ici la complexité). Nous constatons que si l’erreur décroît constamment sur l’échantillon d’apprentissage, à partir d'un certain niveau de complexité, le modèle s'éloigne de la réalité, réalité que l’on cherche à estimer sur l'échantillon de validation (appelé échantillon de test dans le graphique).
Dans le cas des arbres de décisions, plusieurs types de solutions algorithmiques ont été envisagées pour tenter d'éviter autant que possible le surapprentissage des modèles : les techniques de pré- ou de post-élagage des arbres.
Certaines théories statistiques cherchent à 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 (ou SRM), utilise une variable appelée dimension VC, pour déterminer l’optimum d’un modèle. Elle est utilisable par conséquent pour générer des modèles qui assurent le meilleur compromis entre qualité et robustesse du modèle.
Ces solutions algorithmiques sont complémentaires des analyses de performances comparées et de stabilité effectuées sur les échantillons d'apprentissage et de validation.
La première stratégie utilisable pour éviter un surapprentissage 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. Lorsque le groupe est d’effectif trop faible, ou lorsque l'homogénéité d'un sous-ensemble a atteint un niveau suffisant, on considère qu’il n’est plus nécessaire de séparer l'échantillon. Un autre critère souvent rencontré dans ce cadre est l’utilisation d’un test statistique pour évaluer si la segmentation introduit un apport d’informations significatif pour la prédiction de la variable-cible.
La seconde stratégie consiste à construire l’arbre en deux temps : on produit d'abord l’arbre dont les feuilles sont le plus homogènes possibles 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, appelé en anglais growing set pour lever l'ambiguïté), puis on réduit l’arbre, en s’appuyant sur une autre fraction des données de manière à optimiser les performances de l’arbre, c’est la phase de post-élagage. Selon les cas, 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 d'échantillon d’élagage permet de le désigner sans ambiguïté, c'est la traduction directe de l’appellation anglaise pruning set.
Les données à disposition sont souvent incomplètes, dans le sens où l'on ne dispose que d'une partie des variables d'entrée pour un enregistrement. Plusieurs possibilités sont envisageables dans ce cas :
Dans le cas des arbres de classification, il faut préciser la règle d’affectation dans les feuilles une fois l’arbre construit. Si les feuilles sont homogènes, il n'y a pas d'ambiguïté. Si ce n’est pas le cas, une règle simple consiste à décider de la classe de la feuille en fonction de la classe majoritaire, celle qui est la plus représentée.
Cette technique très simple est optimale dans le cas où les données sont issues d’un tirage aléatoire non-biasé dans la population ; la matrice des coûts de mauvaise affectation est unitaire (symétrique) : affecter à bon escient à un coût nul, et affecter à tort coûte 1 quel que soit le cas de figure. En dehors de ce cadre, la règle de la majorité n’est pas nécessairement justifiée mais est facile à utiliser dans la pratique.
Certaines techniques, appelées méthodes d'ensembles (ensemble methods), améliorent la qualité ou la fiabilité de la prédiction en construisant plusieurs arbres de décision depuis les données :
Les arbres de décision sont parfois combinés entre eux ou à d'autres techniques d'apprentissage : analyse discriminante, régressions logistiques, régressions linéaires, réseaux de neurones (perceptron multicouche, radial basis function network) ou autres.
Des procédures d'agrégation des performances des différents modèles utilisés (telles que les décisions par consensus), sont mises en place pour obtenir une performance maximale, tout en contrôlant le niveau de complexité des modèles utilisés.
Comparativement à d'autres méthodes de fouille de données, les arbres de décision présentent plusieurs avantages :
En revanche, elle présente certains inconvénients :
Dans un arbre de décision, tous les chemins depuis la racine jusqu'aux feuilles utilisent le connecteur AND. Dans un graphe de décision, on peut également utiliser le connecteur OR pour connecter plusieurs chemins à l'aide du Minimum message length (MML)[20]. En général les graphes de décision produisent des graphes avec moins de feuilles que les arbres de décision.
Des algorithmes évolutionnistes sont utilisés pour éviter les séparations amenant à des optimum locaux[21],[22].
On peut également échantillonner l'arbre en utilisant des méthodes MCMC dans un paradigme bayésien[23].
L'arbre peut être construit par une approche ascendante (du bas vers le haut)[24].
On dénombre plusieurs algorithmes pour construire des arbres de décision, parmi lesquels :
ID3 et CART ont été inventées de manière indépendante dans les décennies 1970-1980, mais utilisent des approches similaires pour apprendre des arbres de décision depuis l'ensemble d'apprentissage.
Tous ces algorithmes se distinguent par le ou les critères de segmentation utilisés, par les méthodes d'élagages implémentées, par leur manière de gérer les données manquantes dans les prédicteurs.
Beaucoup de logiciels de fouille de données proposent des bibliothèques permettant d'implémenter un ou plusieurs algorithmes d'apprentissage par arbre de décision. Par exemple, le logiciel Open Source R contient plusieurs implémentations de CART, telles que rpart, party et randomForest, les logiciels libres Weka et Orange (et son module orngTree) ou encore la bibliothèque libre Python scikit-learn ; mais également Salford Systems CART, IBM SPSS Modeler, RapidMiner, SAS Enterprise Miner, KNIME, Microsoft SQL Server .
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
