Arbres de décision: Comment optimiser mon processus de prise de décision?

Imaginons que vous jouiez à Twenty Questions. Votre adversaire a secrètement choisi un sujet et vous devez déterminer ce qu'il / elle a choisi. À chaque tour, vous pouvez poser une question oui ou non, et votre adversaire doit répondre honnêtement. Comment trouvez-vous le secret dans le moins de questions possible?

Il devrait être évident que certaines questions sont meilleures que d'autres. Par exemple, demander «Peut-il voler?» Étant donné que votre première question risque d’être infructueuse, alors que demander «Est-ce qu’il est vivant?» Est un peu plus utile. Intuitivement, vous voulez que chaque question réduise de manière significative l’espace des secrets éventuels, pour aboutir à votre réponse.

C'est l'idée de base derrière les arbres de décision. À chaque étape, vous envisagez un ensemble de questions pouvant partitionner votre ensemble de données. Vous choisissez la question qui fournit le meilleur partage et vous trouvez à nouveau les meilleures questions pour les partitions. Vous vous arrêtez une fois que tous les points que vous envisagez sont de la même classe. Ensuite, la tâche de classification est facile. Vous pouvez simplement attraper un point et le jeter dans l'arbre. Les questions le guideront vers sa classe appropriée.

Termes importants

L'arbre de décision est un type d'algorithme d'apprentissage supervisé qui peut être utilisé à la fois pour des problèmes de régression et de classification. Cela fonctionne pour les variables d'entrée et de sortie catégoriques et continues.

Identifions les terminologies importantes dans l'arbre de décision, en regardant l'image ci-dessus:

  • Le nœud racine représente la totalité de la population ou de l'échantillon. Il est ensuite divisé en 2 ou plusieurs ensembles homogènes.
  • La division est un processus de division d'un nœud en 2 sous-nœuds ou plus.
  • Lorsqu'un sous-nœud se divise en plusieurs sous-nœuds, il est appelé un nœud de décision.
  • Les nœuds qui ne sont pas divisés sont appelés nœud terminal ou feuille.
  • Lorsque vous supprimez des sous-nœuds d'un nœud de décision, ce processus s'appelle l'élagage. Le contraire de la taille est la division.
  • Une sous-section d'un arbre entier s'appelle une branche.
  • Un nœud, qui est divisé en sous-nœuds est appelé un nœud parent des sous-nœuds; alors que les sous-noeuds sont appelés l'enfant du noeud parent.

Comment ça fonctionne

Ici, je ne parle que de l’arbre de classification, utilisé pour prédire une réponse qualitative. L'arbre de régression est celui utilisé pour prédire les valeurs quantitatives.

Dans un arbre de classification, nous prédisons que chaque observation appartient à la classe d'observations d'entraînement la plus courante dans la région à laquelle elle appartient. En interprétant les résultats d'un arbre de classification, nous nous intéressons souvent non seulement à la prédiction de classe correspondant à une région de nœud terminal particulière, mais également aux proportions de classe parmi les observations d'apprentissage qui entrent dans cette région. La tâche de développer un arbre de classification repose sur l’utilisation de l’une de ces 3 méthodes comme critère de création des divisions binaires:

1 - Taux d’erreur de classification: nous pouvons définir le «taux de réussite» comme la fraction des observations d’entraînement dans une région donnée qui n’appartient pas à la classe la plus répandue. L'erreur est donnée par cette équation:

E = 1 - argmax_ {c} (π̂ mc)

dans lequel π̂ mc représente la fraction des données d'apprentissage de la région R_m appartenant à la classe c.

2 - Indice de Gini: L'indice de Gini est une mesure d'erreur alternative conçue pour montrer à quel point une région est «pure». Dans ce cas, le terme «pureté» signifie combien de données de formation d’une région donnée appartiennent à une seule classe. Si une région R_m contient des données provenant pour la plupart d'une seule classe c, la valeur de l'indice de Gini sera petite:

3 - Entropie croisée: Une troisième alternative, similaire à l'indice de Gini, est appelée entropie croisée ou déviance:

L’entropie croisée prendra une valeur proche de zéro si les π̂ mc sont tous proches de 0 ou proches de 1. Par conséquent, comme l’indice de Gini, l’entropie croisée prendra une petite valeur si le m-nœud est pur. En fait, il s'avère que l'indice de Gini et l'entropie croisée sont assez similaires numériquement.

Lors de la construction d'un arbre de classification, on utilise généralement l'indice de Gini ou l'entropie croisée pour évaluer la qualité d'une scission particulière, car ils sont plus sensibles à la pureté des nœuds que le taux d'erreur de classification. Chacune de ces 3 approches peut être utilisée lors de l'élagage de l'arbre, mais le taux d'erreur de classification est préférable si l'objectif est la précision de la prédiction de l'arbre élagué final.

Mise en œuvre à partir de zéro

Parcourons l’algorithme de création d’arbre de décision, avec tous ses détails les plus fins. Pour créer un arbre de décision, nous devons prendre une décision initiale sur le jeu de données afin de déterminer quelle fonctionnalité est utilisée pour fractionner les données. Pour déterminer cela, nous devons essayer chaque fonctionnalité et mesurer quelle scission nous donnera les meilleurs résultats. Ensuite, nous allons scinder l’ensemble de données en sous-ensembles. Les sous-ensembles traverseront ensuite les branches du premier noeud de décision. Si les données sur les branches appartiennent à la même classe, nous les avons correctement classées et nous n’avons pas besoin de continuer à les diviser. Si les données ne sont pas identiques, nous devons répéter le processus de fractionnement sur ce sous-ensemble. La décision sur la manière de scinder ce sous-ensemble s’effectue de la même manière que le jeu de données original et nous répétons ce processus jusqu’à ce que toutes les données soient classées.

Comment divisons-nous notre ensemble de données? Une façon d’organiser ce désordre consiste à mesurer les informations. En utilisant la théorie de l'information, nous pouvons mesurer l'information avant et après la scission. Le changement d'information avant et après la scission est appelé gain d'information. Lorsque nous savons comment calculer le gain d’information, nous pouvons répartir nos données sur chaque fonction pour voir quelle division nous donne le gain d’information le plus élevé. La division avec le gain d’information le plus élevé est notre meilleure option.

Pour calculer le gain d’information, nous pouvons utiliser l’entropie de Shannon, qui est la valeur attendue de toutes les informations de toutes les valeurs possibles de notre classe. Voyons le code Python pour cela:

Comme vous pouvez le constater, nous calculons d’abord le nombre d’instances dans le jeu de données. Ensuite, nous créons un dictionnaire dont les clés sont les valeurs de la dernière colonne. Si aucune clé n'a été rencontrée auparavant, une autre est créée. Pour chaque clé, nous gardons une trace du nombre de fois où cette étiquette se produit. Enfin, nous utilisons la fréquence de toutes les étiquettes différentes pour calculer la probabilité de cette étiquette. Cette probabilité est utilisée pour calculer l'entropie de Shannon, et nous la résumons pour toutes les étiquettes.

Après avoir trouvé un moyen de mesurer l'entropie du jeu de données, nous devons fractionner le jeu de données, mesurer l'entropie sur les jeux fractionnés et voir si le fractionnement était la bonne chose à faire. Voici le code pour le faire:

Ce code prend 3 entrées: les données à diviser, la fonctionnalité à diviser et la valeur de la fonctionnalité à renvoyer. Nous créons une nouvelle liste au début à chaque fois car nous allons appeler cette fonction plusieurs fois sur le même jeu de données et nous ne voulons pas que le jeu de données d'origine soit modifié. Notre ensemble de données est une liste de listes; Comme nous parcourons chaque élément de la liste et s'il contient la valeur recherchée, nous l'ajoutons à la liste que nous venons de créer. Dans la déclaration if, nous avons supprimé la fonctionnalité sur laquelle nous nous sommes séparés.

Nous allons maintenant combiner deux fonctions: ShannonEntropy et splitDataset pour parcourir le jeu de données et décider de la meilleure fonctionnalité à scinder.

Examinons rapidement le code:

  • Nous calculons l'entropie de Shannon de l'ensemble de données avant toute division et affectons la valeur à la variable baseEntropy.
  • Le 1er pour les boucles en boucle sur toutes les fonctionnalités de nos données. Nous utilisons les compréhensions de liste pour créer une liste (featList) de toutes les i-èmes entrées des données ou de toutes les valeurs possibles présentes dans les données.
  • Ensuite, nous créons un nouvel ensemble à partir d'une liste pour extraire les valeurs uniques (uniqueVals).
  • Ensuite, nous passons en revue toutes les valeurs uniques de cette fonctionnalité et divisons les données pour chaque fonctionnalité (subData). La nouvelle entropie est calculée (newEntropy) et résumée pour toutes les valeurs uniques de cette entité. Le gain d'information (infoGain) est la réduction de l'entropie (baseEntropy - newEntropy).
  • Enfin, nous comparons le gain d'informations entre toutes les fonctionnalités et renvoyons l'index de la meilleure fonctionnalité à diviser (bestFeature).

Maintenant que nous pouvons mesurer l’organisation d’un ensemble de données et pouvoir fractionner les données, il est temps de rassembler tout cela et de construire l’arbre de décision. À partir d'un jeu de données, nous le scindons en fonction du meilleur attribut à scinder. Une fois scindées, les données traverseront les branches de l’arbre vers un autre nœud. Ce nœud divisera à nouveau les données. Nous allons utiliser la récursivité pour gérer cela.

Nous ne nous arrêterons que dans les conditions suivantes: (1) Manque d’attributs sur lesquels scinder ou (2) toutes les instances d’une branche appartiennent à la même classe. Si toutes les instances ont la même classe, nous allons créer un nœud feuille. Toute donnée qui atteint ce nœud feuille est réputée appartenir à la classe de ce nœud feuille.

Voici le code pour construire nos arbres de décision:

Notre code prend 2 entrées: les données et une liste d'étiquettes:

  • Nous créons d’abord une liste de toutes les étiquettes de classe de l’ensemble de données et appelons cette classe. La première condition d'arrêt est que si toutes les étiquettes de classe sont identiques, nous retournons cette étiquette. La deuxième condition d'arrêt est le cas lorsqu'il n'y a plus de fonctions à scinder. Si les conditions d’arrêt ne sont pas remplies, nous utilisons la fonction ChooseBestFeatureToSplit pour choisir la meilleure fonctionnalité.
  • Pour créer l’arbre, nous le stockons dans un dictionnaire (myTree). Ensuite, nous obtenons toutes les valeurs uniques de l'ensemble de données pour l'entité choisie (bestFeat). Le code de valeur unique utilise des ensembles (uniqueVals).
  • Enfin, nous parcourons toutes les valeurs uniques de l'entité choisie et appelons récursivement createTree () pour chaque division de l'ensemble de données. Cette valeur est insérée dans le dictionnaire myTree, nous nous retrouvons donc avec un grand nombre de dictionnaires imbriqués représentant notre arbre.

Mise en œuvre via Scikit-Learn

Maintenant que nous savons implémenter l’algorithme à partir de zéro, utilisons scikit-learn. En particulier, nous utiliserons la classe DecisionTreeClassifier. En travaillant avec le jeu de données iris, nous importons d’abord les données et les scindons en une partie formation et test. Ensuite, nous construisons un modèle en utilisant le paramètre par défaut de développement complet de l'arbre (croissance de l'arbre jusqu'à ce que toutes les feuilles soient pures). Nous corrigeons l'état random_state dans l'arborescence, qui est utilisé pour établir des liens en interne:

L'exécution du modèle devrait nous donner une précision d'ensemble de test de 95%, ce qui signifie que le modèle a correctement prédit la classe pour 95% des échantillons de l'ensemble de données de test.

Forces et faiblesses

L'avantage majeur de l'utilisation des arbres de décision est qu'ils sont intuitivement très faciles à expliquer. Elles reflètent étroitement la prise de décision humaine par rapport à d’autres approches de régression et de classification. Elles peuvent être affichées graphiquement et elles peuvent facilement gérer des prédicteurs qualitatifs sans avoir à créer de variables nominales.

Un autre avantage considérable est que les algorithmes sont complètement invariants pour la mise à l'échelle des données. Comme chaque entité est traitée séparément et que les fractionnements possibles des données ne dépendent pas de la mise à l'échelle, aucun prétraitement, tel que la normalisation ou la normalisation des entités, n'est nécessaire pour les algorithmes d'arbre de décision. En particulier, les arbres de décision fonctionnent bien lorsque nous avons des fonctionnalités à des échelles complètement différentes, ou un mélange de fonctionnalités binaires et continues.

Cependant, les arbres de décision n’ont généralement pas le même niveau de précision prédictive que les autres approches, car ils ne sont pas assez robustes. Une légère modification des données peut entraîner une modification importante de l'arborescence estimée finale. Même avec l'utilisation de la pré-taille, ils ont tendance à surajustement et à fournir de mauvaises performances de généralisation. Par conséquent, dans la plupart des applications, en agrégeant de nombreux arbres de décision, en utilisant des méthodes telles que l'ensachage, les forêts aléatoires et l'amélioration, la performance prédictive des arbres de décision peut être considérablement améliorée.

Sources de référence:

  • Introduction à l'apprentissage statistique de Gareth James, Daniela Witten, Trevor Hastie et Robert Tibshirani (2014)
  • L'apprentissage automatique en action de Peter Harrington (2012)
  • Introduction à l'apprentissage automatique en Python par Sarah Guido et Andreas Muller (2016)

- -

Si vous avez apprécié cette pièce, j’adorerais si vous appuyez sur le bouton Clap afin que d’autres personnes puissent tomber dessus. Vous pouvez trouver mon propre code sur GitHub, et plus de mes écrits et projets sur https://jameskle.com/. Vous pouvez également me suivre sur Twitter, m'envoyer un email directement ou me trouver sur LinkedIn.