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

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

A arbre de décision est un algorithme d'apprentissage automatique utile utilisé à la fois pour les tâches de régression et de classification. Le nom « arbre de décision » vient du fait que l'algorithme continue de diviser l'ensemble de données en parties de plus en plus petites jusqu'à ce que les données soient divisées en instances uniques, qui sont ensuite classées. Si vous deviez visualiser les résultats de l’algorithme, la façon dont les catégories sont divisées ressemblerait à un arbre et de nombreuses feuilles.

C'est une définition rapide d'un arbre de décision, mais approfondissons le fonctionnement des arbres de décision. Une meilleure compréhension du fonctionnement des arbres de décision, ainsi que de leurs cas d'utilisation, vous aidera à savoir quand les utiliser lors de vos projets d'apprentissage automatique.

Format d'un arbre de décision

Un arbre de décision est un peu comme un organigramme. Pour utiliser un organigramme, vous commencez au point de départ, ou racine, du diagramme, puis en fonction de la façon dont vous répondez aux critères de filtrage de ce nœud de départ, vous vous déplacez vers l'un des prochains nœuds possibles. Ce processus est répété jusqu'à ce qu'une fin soit atteinte.

Les arbres de décision fonctionnent essentiellement de la même manière, chaque nœud interne de l'arbre étant une sorte de critère de test/filtrage. Les nœuds à l'extérieur, les extrémités de l'arbre, sont les étiquettes du point de données en question et sont appelés "feuilles". Les branches qui mènent des nœuds internes au nœud suivant sont des caractéristiques ou des conjonctions de caractéristiques. Les règles utilisées pour classer les points de données sont les chemins qui vont de la racine aux feuilles.

Algorithmes pour les arbres de décision

Les arbres de décision fonctionnent selon une approche algorithmique qui divise l'ensemble de données en points de données individuels en fonction de différents critères. Ces divisions sont effectuées avec différentes variables ou les différentes caractéristiques de l'ensemble de données. Par exemple, si l'objectif est de déterminer si un chien ou un chat est décrit ou non par les caractéristiques d'entrée, les variables sur lesquelles les données sont divisées peuvent être des éléments tels que "griffes" et "aboiements".

Alors, quels algorithmes sont utilisés pour diviser réellement les données en branches et en feuilles ? Il existe différentes méthodes qui peuvent être utilisées pour diviser un arbre, mais la méthode de division la plus courante est probablement une technique appelée "fractionnement binaire récursif”. Lors de l'exécution de cette méthode de fractionnement, le processus commence à la racine et le nombre d'entités dans l'ensemble de données représente le nombre possible de fractionnements possibles. Une fonction est utilisée pour déterminer le degré de précision que coûtera chaque division possible, et la division est effectuée en utilisant les critères qui sacrifient le moins de précision. Ce processus est effectué de manière récursive et des sous-groupes sont formés en utilisant la même stratégie générale.

Pour déterminer le coût de la division, une fonction de coût est utilisée. Une fonction de coût différente est utilisée pour les tâches de régression et de classification. L'objectif de ces deux fonctions de coût est de déterminer les branches présentant les valeurs de réponse les plus similaires, ou les branches les plus homogènes. Imaginons que vous souhaitiez que les données de test d'une certaine classe suivent certains chemins, ce qui paraît logique.

En termes de fonction de coût de régression pour la division binaire récursive, l'algorithme utilisé pour calculer le coût est le suivant :

somme(y – prédiction)^2

La prédiction pour un groupe particulier de points de données est la moyenne des réponses des données d'apprentissage pour ce groupe. Tous les points de données sont passés par la fonction de coût pour déterminer le coût de toutes les divisions possibles et la division avec le coût le plus bas est sélectionnée.

En ce qui concerne la fonction de coût pour la classification, la fonction est la suivante :

G = somme(pk * (1 – pk))

Il s'agit du score de Gini, et c'est une mesure de l'efficacité d'une scission, basée sur le nombre d'instances de différentes classes dans les groupes résultant de la scission. En d'autres termes, il quantifie le degré de mixité des groupes après la scission. Une scission optimale est lorsque tous les groupes résultant de la scission se composent uniquement d'entrées d'une classe. Si une répartition optimale a été créée, la valeur "pk" sera soit 0 soit 1 et G sera égal à zéro. Vous pourriez être en mesure de deviner que la répartition dans le pire des cas est celle où il existe une représentation 50-50 des classes dans la répartition, dans le cas d'une classification binaire. Dans ce cas, la valeur « pk » serait de 0.5 et G serait également de 0.5.

Le processus de fractionnement est terminé lorsque tous les points de données ont été transformés en feuilles et classés. Cependant, vous voudrez peut-être arrêter la croissance de l'arbre tôt. Les grands arbres complexes sont sujets au surajustement, mais plusieurs méthodes différentes peuvent être utilisées pour lutter contre cela. Une méthode pour réduire le surajustement consiste à spécifier un nombre minimum de points de données qui seront utilisés pour créer une feuille. Une autre méthode de contrôle du surajustement consiste à limiter l'arbre à une certaine profondeur maximale, qui contrôle la longueur d'un chemin pouvant s'étendre de la racine à une feuille.

Un autre processus impliqué dans la création d'arbres de décision est la taille. L'élagage peut aider à augmenter les performances d'un arbre de décision en supprimant les branches contenant des caractéristiques qui ont peu de pouvoir prédictif/peu d'importance pour le modèle. De cette façon, la complexité de l'arbre est réduite, il devient moins susceptible de sur-ajuster et l'utilité prédictive du modèle est augmentée.

Lors de l'élagage, le processus peut commencer soit au sommet de l'arbre, soit au bas de l'arbre. Cependant, la méthode d'élagage la plus simple consiste à commencer par les feuilles et à tenter de supprimer le nœud qui contient la classe la plus courante dans cette feuille. Si la précision du modèle ne se détériore pas lorsque cela est fait, alors le changement est conservé. Il existe d'autres techniques utilisées pour effectuer l'élagage, mais la méthode décrite ci-dessus - élagage à erreur réduite - est probablement la méthode la plus courante d'élagage d'arbre de décision.

Considérations relatives à l'utilisation des arbres de décision

Arbres de décision sont souvent utiles lorsqu'une classification doit être effectuée mais que le temps de calcul est une contrainte majeure. Les arbres de décision peuvent indiquer clairement quelles caractéristiques des ensembles de données choisis ont le pouvoir prédictif le plus élevé. De plus, contrairement à de nombreux algorithmes d'apprentissage automatique où les règles utilisées pour classer les données peuvent être difficiles à interpréter, les arbres de décision peuvent rendre des règles interprétables. Les arbres de décision sont également capables d'utiliser à la fois des variables catégorielles et continues, ce qui signifie que moins de prétraitement est nécessaire, par rapport aux algorithmes qui ne peuvent gérer qu'un seul de ces types de variables.

Les arbres de décision ont tendance à ne pas fonctionner très bien lorsqu'ils sont utilisés pour déterminer les valeurs d'attributs continus. Une autre limitation des arbres de décision est que, lors de la classification, s'il y a peu d'exemples de formation mais de nombreuses classes, l'arbre de décision a tendance à être inexact.