Un arbre de décisions est un algorithme d'apprentissage supervisé non paramétrique, qui est utilisé à la fois pour les tâches de classification et régression. Il a une structure hiérarchique, une structure arborescente, qui se compose d'un noeud racine, de branches, de nœuds interne et de nœuds feuille.

Comme vous pouvez le voir sur le diagramme ci-dessus, un arbre de décisions commence par un noeud racine, qui n'a pas de branches entrantes. Les branches sortant du noeud racine vont dans les noeuds internes, également connu comme nœuds de décision. Sur la base des caractéristiques disponibles, les deux types de noeud effectuent des évaluations sur des sous-ensembles homogènes, qui sont désignés comme nœuds feuille ou nœuds terminal. Les nœuds feuille représentent tous les résultats possibles au sein du fichier. A titre d' exemple, imaginons que vous essayez d'évaluer si vous devez ou non aller surfer, vous pouvez utiliser les règles de suivi de décision pour faire un choix :

Ce type de structure en organigramme crée également une représentation facile à assimiler pour la prise de décision, permettant aux différents groupes d'une organisation de mieux comprendre pourquoi une décision a été prise.

L'apprentissage par arborescence de décisions utilise une stratégie de division et de conquête en effectuant une recherche gloutonne pour identifier les points de fractionnement optimaux au sein d'une arborescence. Ce processus de fractionnement est ensuite répété de manière descendante, récursive jusqu'à ce que tous, ou la majorité des enregistrements aient été classifiés sous des étiquettes de classe spécifiques. Que tous les points de données soient ou non classifiés comme des ensembles homogènes dépend majoritairement de la complexité de l'arbre de décisions. Les arbres plus petits sont plus facilement capables d'atteindre des nœuds feuille purs, c'est-à-dire des points de données dans une classe unique. Cependant, à mesure qu'une arborescence croît en taille, il devient de plus en plus difficile de maintenir cette pureté, et il en résulte généralement trop peu de données relevant d'un sous-arbre donné. Lorsque cela se produit, on parle de fragmentation des données, et cela peut souvent aboutir à un surajustement. Par conséquent, les arbres de décisions ont une préférence pour les petits arbres, ce qui est cohérent avec le principe de parcimonie d'Occam’s Razor ; c'est-à-dire que « les entités ne doivent pas être multipliées au-delà de la nécessité ». Autrement dit, les arbres de décisions ne doivent ajouter 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 employé ; il s'agit d'un traitement, qui supprime les branches qui se fractionnent sur des éléments de basse importance. L'ajustement du modèle peut alors être évalué par le traitement de validation croisée. Une autre façon pour les arbres de décisions de maintenir leur exactitude est de former un ensemble via un algorithme de forêt aléatoire ; ce discriminant prédit des résultats plus précis, en particulier lorsque les arbres individuels ne sont pas corrélés les uns avec les autres.

Bien qu'il existe plusieurs façons de sélectionner le meilleur attribut de chaque noeud, deux méthodes, gain d'informations gain et impureté Gini, agissent comme critère de fractionnement critère pour les modèles d'arbre de décisions. Ils aident à évaluer la qualité de chaque condition de test et comment elle aide à classifier les échantillons dans une classe.  

Entropie et gain d'informations

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

• S représente le jeu de données avec lequel l'entropie est calculée 
• c représente les classes dans le jeu, 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 du jeu, S

Les valeurs d'entropie peuvent être comprises entre 0 et 1. Si tous les échantillons du jeu de données, S, appartiennent à une classe, alors l'entropie sera égale à zéro. Si la moitié des échantillons sont classifiés dans une classe et l'autre moitié dans une autre classe, l'entropie sera à son maximum de 1. Afin de sélectionner la meilleure fonction pour effectuer le fractionnement et trouver l'arbre de décisions optimal, il convient d'utiliser l'attribut avec le plus petit total d'entropie. Le gain d'informations représente la différence en entropie avant et après un fractionnement sur un attribut donné. L'attribut avec le gain d'informations le plus élevé produira le meilleur fractionnement car il fait mieux le travail de classement des données d'apprentissage selon sa classification cible. Le gain d'informations est généralement représenté par la formule suivante, où : 

• a représente un attribut ou un libellé de classe spécifique
• Entropie(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
• Entropie(S_v) est l'entropie du jeu de données, S _v

Passons en revue un exemple pour solidifier ces concepts. Imaginons 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 recherchant la proportion de jours où « Jouer au tennis » est « Oui », soit 9/14, et la proportion de jours où « Jouer au tennis » est « Non », soit 5/14. Ensuite, ces valeurs peuvent être insérées dans la formule d'entropie ci-dessus.

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

On peut alors calculer le gain d'informations pour chacun des attributs individuellement. Par exemple, le gain d' informations pour l'attribut « Humidité » serait le suivant :

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

En guise de récapitulatif,

- 7/14 représente la proportion de valeurs où l'humidité vaut « haut » par rapport au nombre total de valeurs d'humidité. Dans ce cas, le nombre de valeurs où l'humidité vaut « haut » est le même que le nombre de valeurs où l'humidité vaut « normal ».

- 0,985 est l'entropie quand Humidité = « haut »

- 0,59 est l'entropie lorsque Humidité = « normal »

Ensuite, répétez le calcul du gain d'informations pour chaque attribut dans le tableau ci-dessus, et sélectionnez l'attribut avec le gain d'informations le plus élevé comme premier point de fractionnement dans l'arbre de décisions. Dans cette affaire cas, c'est la perspective qui produit le gain informations le plus élevé. A partir de là, le traitement est répété pour chaque sous-arborescence. 

Impureté Gini 

L'impureté Gini est la probabilité de classer in correctement un point de données aléatoire dans le jeu de données s'il était libellé sur la base de la distribution de classe du jeu de données. Semblable à l'entropie, si défini, S, est pur (c'est-à-dire qu'il appartient à une classe) alors, son impureté est zéro. Ceci est indiqué par la formule suivante : 

Bien que les arbres de décisions puissent être utilisés dans une variété de cas d' utilisation, d'autres algorithmes surpassent généralement les algorithmes d'arbre de décisions. Cela dit, les arbres de décisions sont particulièrement utiles pour les tâches de  fouille de données  et de reconnaissance du savoir. Explorons les principaux avantages et défis de l'utilisation des arbres de décisions ci-après :

- Facile à interpréter :La logique booléenne et les représentations visuelles des arbres de décisions les rendent plus faciles à comprendre et à consommer. Le nature hiérarchique d'un arbre de décisions permet également de voir facilement quels attributs sont les plus importants, ce qui n'est pas toujours clair avec d'autres algorithmes, similaires aux  réseaux neuronaux.

- Peu ou pas préparation de données nécessaire :Les arbres de décisions ont un nombre de caractéristiques, ce qui les rend plus flexibles que les autre classificateurs. Il peut traiter divers types de données, c'est-à-dire des valeurs discrètes ou continues, et les valeurs continues peuvent être converties en valeurs catégorielles grâce à l'utilisation de seuils. De plus, il peut également traiter des valeurs avec des valeurs manquantes, ce qui peut être problématique pour d'autres classificateurs, similaires à Naïve Bayes.  

- Plus flexible : Les arbres de décisions peuvent être exploités à la fois pour les tâches de classification et régression, ce qui les rend plus flexibles que certains autre algorithmes. Il est également insensible aux relations sous-jacentes entre les attributs ; cela signifie que si deux variables sont fortement corrélées, l'algorithme ne sélectionne qu'une seule des caractéristiques à fractionnement. 

- Sujet au surajustement : Les arbres décision complexes tendent à se surajuster et ne généralisent pas bien aux nouvelles données. Ce scénario peut être évité par les procédés de pré-élagage ou de post-élagage. Le pré-élagage arrête la croissance d'arbre lorsqu'il n'y a pas suffisamment de données tandis que le post-élagage supprime les sous-arbres avec des données inadéquates après la construction de l'arborescence. 

- Estimateurs à variance élevée : De petites variations dans les données peuvent produire un arbre de décisions très différent. Le bagging, ou la moyenne des estimations, peut être une méthode de réduction de la variance des arbres de décisions. Cependant, cette approche est limitée car elle peut aboutir à des prédicteurs hautement corrélés.  

- Plus coûteux : Étant donné que les arbres de décisions adoptent une approche de recherche gloutonne lors de la construction, ils peuvent être plus coûteux à entraîner par rapport à d'autres algorithmes. 

- Pas entièrement pris en charge dans scikit-learn :  Scikit-learn est une bibliothèque d'apprentissage automatique populaire basée sur Python. Bien que cette bibliothèque ait un  module Arbre de décisions (DecisionTreeClassifier, le lien réside en dehors d'  ibm.com), l'implémentation en cours ne prend pas en charge les variables catégorielles.