Un arbre de décision est une approche d’apprentissage supervisé non paramétrique et peuvent être appliqués à la fois aux problèmes de régression et de classification. Conformément à l’analogie avec l’arbre, les arbres de décision mettent en œuvre un processus de décision séquentiel. À partir du nœud racine, une fonctionnalité est évaluée et l’un des deux nœuds (branches) est sélectionné.
Chaque nœud de l’arborescence est essentiellement une règle de décision. Cette procédure est répétée jusqu’à ce qu’une feuille finale soit atteinte, qui représente normalement la cible. Les arbres de décision sont également des modèles attrayants si l’on se soucie de l’interprétabilité.
Algoritmes usuels
Il existe des algorithmes pour créer des arbres de décision :
- ID3 (Iterative Dichotomiser 3) a été développé en 1986 par Ross Quinlan. L’algorithme crée un arbre multidirectionnel, trouvant pour chaque nœud (c’est-à-dire de manière gourmande) la caractéristique catégorielle qui produira le plus grand gain d’informations pour les cibles catégorielles. Les arbres poussent jusqu’à leur taille maximale, puis une étape d’élagage est généralement appliquée pour améliorer la capacité de l’arbre à généraliser à des données invisibles.
- C4.5 a été développé en 1993 par Ross Quinlan, est le successeur de ID3 et a supprimé la restriction selon laquelle les caractéristiques doivent être catégoriques en définissant dynamiquement un attribut discret (basé sur des variables numériques) qui divise la valeur de l’attribut continu en un ensemble discret d’intervalles. C4.5 convertit les arbres entraînés (c’est-à-dire la sortie de l’algorithme ID3) en ensembles de règles si-alors. L’exactitude de chaque règle est ensuite évaluée pour déterminer l’ordre dans lequel elles doivent être appliquées. L’élagage est effectué en supprimant la condition préalable d’une règle si la précision de la règle s’améliore sans elle.
- C5.0 est la dernière version de Quinlan sous licence propriétaire. Il utilise moins de mémoire et crée des ensembles de règles plus petits que C4.5 tout en étant plus précis.
- CART (arbres de classification et de régression) est très similaire à C4.5, mais il diffère en ce qu’il prend en charge les variables cibles numériques (régression) et ne calcule pas d’ensembles de règles. CART construit des arbres binaires en utilisant la fonctionnalité et le seuil qui génèrent le plus grand gain d’informations sur chaque nœud.
scikit-learn utilise une version optimisée de l’algorithme CART
Terminologie
Conformément à l’analogie avec l’arbre, la terminologie a été adoptée à partir de la terminologie de l’arbre.
- Nœud racine : est le premier nœud des arbres de décision
- Fractionnement : est un processus de division du nœud en deux ou plusieurs sous-nœuds, en commençant par le nœud racine.
- Nœud : diviser les résultats du nœud racine en sous-nœuds et diviser les sous-nœuds en d’autres sous-nœuds.
- Nœud feuille ou terminal : fin d’un nœud, puisque le nœud ne peut plus être divisé
- Élagage : est une technique permettant de réduire la taille de l’arbre de décision en supprimant les sous-nœuds de l’arbre de décision. L’objectif est de réduire la complexité pour améliorer la précision prédictive et éviter le surajustement
- Branche / Sous-Arbre : Une sous-section de l’arbre entier est appelée branche ou sous-arbre.
- Nœud parent et enfant : un nœud divisé en sous-nœuds est appelé nœud parent des sous-nœuds, tandis que les sous-nœuds sont l’enfant du nœud parent.
Fonctionnement général
Considérons l’exemple suivant où un arbre de décision permet de prédire le salaire d’un joueur de baseball :
Nous utilisons l’ensemble de données Hitters pour prédire le salaire d’un joueur de baseball (salaire moyen) en fonction des années (le nombre d’années pendant lesquelles il a joué dans les ligues majeures) et des coups sûrs (le nombre de coups sûrs qu’il a réalisés l’année précédente).
Sur la base des fonctionnalités, le modèle d’arbre de décision apprend une série de règles de fractionnement, en commençant par le sommet de l’arbre (nœud racine).
- Le nœud racine est divisé en sous-nœuds avec une règle d’observation ayant des années <4,5 vers la branche gauche, ce qui signifie que les joueurs de l’ensemble de données avec des années <4,5 ayant un salaire journal moyen est de 5,107 et nous faisons une prédiction de 5,107 milliers de dollars, c’est-à-dire 165 174 $ pour ces joueurs.
- Les joueurs avec des années> = 4,5 sont affectés à la branche de droite, puis ce groupe est subdivisé en hits <177,5 avec une perte de salaire moyenne de 6.
- Les joueurs avec des années >= 4,5 sont affectés à la branche de droite, puis ce groupe est subdivisé par Hits >= 177,5 avec une perte de salaire moyenne de 6,74.
Dans ce cas, on peut voir que l’arbre de décision forme un segment en trois régions où cette région détermine les salaires des joueurs de baseball et on peut dire que la région est une frontière de décision.
Ces trois régions peuvent s’écrire
- R1 ={X | Années<4,5 }
- R2 ={X | Années>=4,5, Hits<117,5 }
- R3 ={X | Années>=4,5 , Clics>=117,5 }.
À partir de cette intuition, il existe un processus qui consiste à diviser un arbre de décision pour former une région capable de prédire le salaire des joueurs de baseball.
Fractionnement / splitting
Afin de diviser les nœuds au niveau des fonctionnalités les plus informatives à l’aide de l’algorithme de décision, nous commençons par la racine de l’arbre et divisons les données sur la fonctionnalité qui entraîne le plus grand gain d’informations (IG). Ici, la fonction objectif est de maximiser le gain d’information (IG) à chaque fractionnement, que nous définissons comme suit :
f est la fonctionnalité permettant d’effectuer la division, Dp et Dj sont l’ensemble de données du nœud parent, j-ième enfant, I est notre mesure d’impureté, Np est le nombre total d’échantillons au niveau du nœud parent et Nj est le nombre d’échantillons. dans le j-ème nœud enfant.
Comme nous pouvons le voir, le gain d’information est simplement la différence entre l’impureté du nœud parent et la somme des impuretés du nœud enfant : plus l’impureté des nœuds enfants est faible, plus le gain d’information est important. cependant, par souci de simplicité et pour réduire l’espace de recherche combinatoire, la plupart des bibliothèques (y compris scikit-learn) implémentent des arbres de décision binaires. Cela signifie que chaque nœud parent est divisé en deux nœuds enfants, D-left et D-right.
La mesure d’impureté implémente des arbres de décision binaires et les trois mesures d’impuretés ou critères de fractionnement qui sont couramment utilisés dans les arbres de décision binaires sont l’impureté de Gini (IG), l’entropie (IH) et l’erreur de classification (IE).
