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.

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

Généralités L'apprentissage par arbre de décision est une méthode classique en apprentissage automatique.. 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 ( ou TDIDT)Quinlan, J. R., (1986). Induction of Decision Trees. Machine Learning 1: 81-106, Kluwer Academic Publishers., 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.

Types

Il existe deux principaux types d'arbre de décision en fouille de données :

Les arbres de classification () permettent de prédire à quelle classe la variable-cible appartient, dans ce cas la prédiction est une étiquette de classe,

Les arbres de régression () permettent de prédire une quantité réelle (par exemple, le prix d'une maison ou la durée de séjour d'un patient dans un hôpital), dans ce cas la prédiction est une valeur numérique.

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

Construction d'un arbre de décision

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 ) où ː

chaque nœud interne décrit un test sur une variable d'apprentissage ; chaque branche représente un résultat du test ; chaque feuille contient la valeur de la variable cible avec une étiquette de classe pour les arbres de classification et une valeur numérique pour les arbres de régression.

Critère de segmentation

Usuellement, les algorithmes pour construire les arbres de décision sont construits en divisant l'arbre du sommet vers les feuilles et 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..

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

Cas des arbres de classification

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.

Indice de diversité de Gini : utilisé par l'algorithme CART, il mesure avec quelle fréquence un élément aléatoire de l'ensemble serait mal classé si son étiquette était choisie aléatoirement selon la distribution des étiquettes dans le sous-ensemble. L'indice de diversité de Gini peut être calculé en sommant la probabilité pour chaque élément d'être choisi, multipliée par la probabilité qu'il soit mal classé. Il atteint sa valeur minimum (zéro) lorsque tous les éléments de l'ensemble sont dans une même classe de la variable-cible. Pratiquement, si l'on suppose que la classe prend une valeur dans l'ensemble , et si désigne la fraction des éléments de l'ensemble avec l'étiquette dans l'ensemble, on aura :

Gain d'information : utilisé par les algorithmes ID3 et C4.5, le gain d'information est basé sur le concept d'entropie de Shannon en théorie de l'information . L'entropie permet de mesurer le désordre dans un ensemble de données et est utilisée pour choisir la valeur permettant de maximiser le gain d'information. En utilisant les mêmes notations que pour l'indice de diversité de Gini, on obtient la formule suivante :

Cas des arbres de régression

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

Remarques

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éesDes heuristiques sont notamment utilisées lorsque l'on cherche à réduire la complexité de l'arbre en agrégeant les modalités des variables utilisées comme prédicteurs de la cible. Par 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 contiguës..

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.

Traitement des variables continues

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.

Définir la taille de l’arbre

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 (), 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.

Le problème du surajustement des modèles

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.