Qu’est-ce qu’un arbre de décision ?

Comme vous pouvez le voir dans le diagramme ci-dessous, un arbre de décision commence par un nœud racine, qui n’a pas de branches entrantes. Les branches sortantes du nœud racine alimentent ensuite les nœuds internes, également appelés nœuds de décision. En fonction des fonctionnalités disponibles, les deux types de nœuds effectuent des évaluations pour former des sous-ensembles homogènes, qui sont désignés par des nœuds feuilles ou des nœuds terminaux. Les nœuds feuilles représentent tous les résultats possibles dans le jeu de données.

À titre d’exemple, imaginons que vous essayiez de déterminer si vous devez ou non aller surfer. Vous pouvez utiliser les règles de décision suivantes pour faire votre choix :

Ce type de structure d’organigramme crée également une représentation de la prise de décision, permettant aux différents groupes au sein d’une organisation de mieux comprendre pourquoi une décision a été prise.

L’apprentissage par arbre de décision emploie une stratégie de division pour régner en effectuant une recherche gloutonne pour identifier les points de division optimaux au sein d’un arbre. Ce processus de fractionnement est ensuite répété de manière descendante et récursive jusqu’à ce que tous les enregistrements, ou la majorité d’entre eux, aient été classés sous des étiquettes de classe spécifiques.

Le fait que tous les points de données soient ou non classés comme des ensembles homogènes dépend en grande partie de la complexité de l’arbre de décision. Les petits arbres peuvent plus facilement atteindre des nœuds feuille purs, c’est-à-dire des points de données dans une seule classe. Cependant, à mesure qu’un arbre grandit, il devient de plus en plus difficile de maintenir cette pureté, ce qui se traduit généralement par un nombre insuffisant de données provenant d’un sous-arbre donné. Lorsque cela se produit, on parle de fragmentation des données, et cela peut souvent conduire à un surajustement.

Par conséquent, les arbres de décision ont une préférence pour les petits arbres, ce qui est conforme au principe de parcimonie du Rasoir d’Occam ; ainsi, « les entités ne doivent pas être multipliées plus que nécessaire ». En d’autres termes, les arbres de décision ne doivent ajouter de la complexité que si nécessaire, car l’explication la plus simple est souvent la meilleure. Pour réduire la complexité et éviter le surajustement, l’élagage est généralement utilisé ; il s’agit d’un processus qui supprime les branches qui se divisent selon des fonctionnalités moins cruciales. L’ajustement du modèle peut ensuite être évalué via le processus de validation croisée.

Les arbres de décision peuvent également conserver leur précision en formant un ensemble à l’aide d’un algorithme de forêt aléatoire ; ce classificateur prédit des résultats plus précis, en particulier lorsque les arbres individuels ne sont pas corrélés les uns aux autres.

L’algorithme de Hunt, développé dans les années 1960 pour modéliser l’apprentissage humain en psychologie, est à la base de nombreux algorithmes d’arbres de décision populaires. Voici quelques exemples :

- ID3 : Ross Quinlan est à l’origine du développement d’ID3 ( Iterative Dichotomiser 3 . Cet algorithme utilise l’entropie et le gain d’informations comme indicateurs pour évaluer la répartition des candidats. Certaines des recherches de Quinlan sur cet algorithme datant de 1986 sont disponibles ici.

- C4.5 : cet algorithme est considéré comme une itération ultérieure d’ID3, qui a également été développé par Quinlan. Il peut utiliser le gain d’informations ou les ratios de gain pour évaluer les points de division dans les arbres de décision.

- CART : le terme CART est l’acronyme en anglais de l’expression « arbres de classification et de régression » et a été introduit par Leo Breiman. Cet algorithme utilise généralement l’impureté de Gini pour identifier l’attribut idéal sur lequel se baser. L’impureté de Gini mesure la fréquence à laquelle un attribut choisi au hasard est mal classé. Lors de l’évaluation à l’aide de l’empreinte de Gini, une valeur inférieure est plus idéale.

Bien qu’il existe plusieurs façons de sélectionner le meilleur attribut à chaque nœud, deux méthodes, le gain d’information et l’impureté de Gini, constituent des critères de division populaires pour les modèles d’arbre de décision. Ils aident à évaluer la qualité de chaque condition de test et dans quelle mesure elle sera capable de classer les échantillons dans une classe.

Il est difficile d’expliquer le gain d’information sans évoquer au préalable l’entropie. L’entropie est un concept issu de la théorie de l’information, qui mesure l’impureté des valeurs de l’échantillon. Elle est définie par la formule suivante, où :

• S représente l’ensemble de données dans lequel l’entropie est calculée 
• c représente les classes de l’ensemble, S
• p(c) représente la proportion de points de données appartenant à la classe c par rapport au nombre total de points de données dans l’ensemble, S

Les valeurs d’entropie peuvent être comprises entre 0 et 1. Si tous les échantillons de l’ensemble de données S appartiennent à une seule classe, l’entropie est égale à zéro. Si la moitié des échantillons est classée dans une classe et l’autre moitié dans une autre classe, l’entropie sera inférieure ou égale à 1. Afin de sélectionner la meilleure caractéristique à diviser et de trouver l’arbre de décision optimal, il convient d’utiliser l’attribut ayant la plus petite quantité d’entropie.

Le gain d’information représente la différence d’entropie avant et après un fractionnement sur un attribut donné. L’attribut présentant le gain d’information le plus élevé produira la meilleure répartition, car il est le plus à même de classer les données d’apprentissage en fonction de sa classification cible. Le gain d’information est généralement représenté par la formule suivante,

où :

• a représente un attribut ou une étiquette de classe spécifique
• Entropy(S) est l’entropie du jeu de données, S
• |Sv|/|S| représente la proportion des valeurs dans S_v par rapport au nombre de valeurs dans le jeu de données, S.

Prenons un exemple pour renforcer ces concepts. Imaginez que nous ayons le jeu de données arbitraire suivant :

Pour ce jeu de données, l’entropie est de 0,94. Cela peut être calculé en trouvant la proportion de jours où « Jouer au tennis » est « Oui », qui est de 9/14, et la proportion de jours où « Jouer au tennis » est « Non », qui est de 5/14. Ensuite, ces valeurs peuvent être intégrées à la formule d’entropie ci-dessus.

Entropie (tennis) = -(9/14) log2(9/14) – (5/14) log2 (5/14) = 0,94

Nous pouvons alors calculer le gain d’information pour chacun des attributs individuellement. Par exemple, le gain d’information pour l’attribut « Humidité » serait le suivant :

Gain (Tennis, Humidité) = (0,94)-(7/14)*(0,985) – (7/14)*(0,592) = 0,151

Pour rappel,

- 7/14 représente la proportion de valeurs où l’humidité est égale à « élevée » par rapport au nombre total de valeurs d’humidité. Dans ce cas, le nombre de valeurs où l’humidité est égale à « élevée » est le même que le nombre de valeurs où l’humidité est égale à « normale ».

- 0,985 est l’entropie lorsque le taux d’humidité est « élevé »

- 0,59 est l’entropie lorsque l’humidité = « normal »

Ensuite, répétez le calcul du gain d’information pour chaque attribut du tableau ci-dessus et sélectionnez l’attribut ayant le gain d’information le plus élevé comme premier point de division de l’arbre de décision. Dans ce cas, Outlook génère le gain d’informations le plus élevé. Le processus est ensuite répété pour chaque sous-arborescence.

L’impureté de Gini est la probabilité de classer incorrectement un point de données aléatoire dans le jeu de données s’il était étiqueté en fonction de la distribution de classe de ce jeu de données. Semblable à l’entropie, si elle est définie, S est pure, c’est-à-dire appartenant à une classe), alors son impureté est nulle. Ceci se retrouve dans la formule suivante :

Bien que les arbres de décision puissent être utilisés dans de nombreux cas d’utilisation, d’autres algorithmes sont généralement plus performants. Cela dit, les arbres de décision sont particulièrement utiles pour les tâches de data mining et de découverte de connaissances. Découvrons ci-dessous les principaux avantages et les principaux défis de l’utilisation des arbres de décision :

• Facilité d’interprétation : la logique booléenne et les représentations visuelles des arbres de décision facilitent leur compréhension et leur utilisation. La nature hiérarchique d’un arbre de décision permet également de voir facilement quels sont les attributs les plus importants, ce qui n’est pas toujours évident avec d’autres algorithmes, comme les réseaux neuronaux.
  
  
• Peu voire aucune préparation des données requise : les arbres de décision présentent un certain nombre de caractéristiques qui les rendent plus flexibles que les autres classificateurs. Ils peuvent gérer différents types de données, par exemple les valeurs discrètes ou continues et les valeurs continues peuvent être converties en valeurs catégorielles grâce à l’utilisation de seuils. De plus, ils peuvent gérer des valeurs avec des valeurs manquantes, ce qui peut être problématique pour d’autres classificateurs, comme la méthode de classification naïve bayésienne.
  
  
• Plus de flexibilité : les arbres de décision peuvent être utilisés à la fois pour les tâches de classification et de régression, ce qui les rend plus flexibles que certains autres algorithmes. Ils sont également insensibles aux relations sous-jacentes entre les attributs ; cela signifie que si deux variables sont hautement corrélées, l’algorithme ne choisira que l’une des fonctionnalités sur lesquelles se baser.

• Sujets au surajustement : les arbres de décision complexes ont tendance à être surdimensionnés et ne se généralisent pas correctement aux nouvelles données. Ce scénario peut être évité grâce aux processus de pré-élagage ou de post-élagage. Le pré-élagage arrête la croissance de l’arbre en cas de données insuffisantes, tandis que le post-élagage supprime les branches dont les données sont inadéquates après la construction de l’arbre.
  
  
• Estimateurs de variance élevés : de petites variations dans les données peuvent produire un arbre de décision très différent. Le bagging ou moyenne des estimations peut être une méthode permettant de réduire la variance des arbres de décision. Cependant, cette approche est limitée car elle peut conduire à des prédicteurs hautement corrélés.
  
  
• Coût plus élevé : étant donné que les arbres de décision induisent une phase de recherche exigeante pendant la construction, leur formation peut être plus coûteuse que d’autres algorithmes.