Information

Considérons un événement ayant une certaine probabilité $p$. Plus $p$ est élevée, plus l'événement est probable, et par conséquent, peu d'information (ou d'incertitude) est contenue dans la survenue de cet événement. Par exemple, l'événement « ma voiture démarre lorsque j'y monte le matin » contient une quantité d'information assez faible, car ma voiture est fiable et je m'attends à ce qu'elle démarre. Si, en revanche, elle ne démarre pas un matin, cet événement de faible probabilité serait surprenant et contiendrait beaucoup plus d'information.

L'information est généralement mesurée en bits, où un bit représente la quantité d'information nécessaire pour distinguer deux événements ou messages équiprobables. Par exemple, lorsque vous lancez une pièce équilibrée, vous gagnez un bit d'information parce que vous passez d'un état d'incertitude quant à l'issue (pile ou face) à la connaissance de l'issue (pile, par exemple). Pour mesurer le nombre de bits d'un nombre entier, on utilise le logarithme en base 2 (${\text{log}}_{2}x$) ; il n'est donc pas surprenant d'apprendre que le logarithme en base 2 joue un rôle majeur dans la mesure de l'information.

L'information d'un événement de probabilité $p$ est $-{\text{log}}_{2}p$. Rappelons que les probabilités $p$ sont toujours comprises entre 0 et 1, et si $0<p<1$, alors par les propriétés des logarithmes, nous avons ${\text{log}}_{2}p<0$. Cela explique le signe négatif qui apparaît dans la formule, puisqu'il est logique de mesurer l'information par un nombre positif.

Remarquons que l'information contenue dans un événement certain $(p=1)$ est $-{\text{log}}_{2}1=0$, tandis que l'information obtenue en apprenant qu'une pièce lancée est tombée sur pile $(p=1/2)$ est $-{\text{log}}_2\left(\frac{1}{2}\right)=-(-1)=1$, soit un bit d'information.

Supposons que la probabilité que ma voiture démarre un jour donné soit $p=255/256$, et donc que la probabilité qu'elle ne démarre pas soit $1-p=1/256$. L'information liée à l'événement « elle démarre » est $-{\text{log}}_2\left(\frac{255}{256}\right)=0.0056$, tandis que l'information liée à l'événement « elle ne démarre pas » est $-{\text{log}}_2\left(\frac{1}{256}\right)=8$. En somme, il y a 8 bits d'information dans le fait de savoir que ma voiture ne démarre pas, car cela ne se produirait qu'environ une fois tous les $2^8=256$ jours.

Entropie

L'entropie (entropy) est une mesure qui quantifie la quantité moyenne d'information, ou d'incertitude, dans une variable aléatoire ou une distribution de probabilité. Elle est étroitement liée à l'information. On peut concevoir l'entropie comme une mesure du désordre, du caractère aléatoire ou de l'imprévisibilité au sein d'un système.

Pour une variable aléatoire discrète $X$, prenant $n$ valeurs $x_i$ avec les probabilités associées $p_i$, l'entropie de $X$ est :

La notion d'entropie est fondamentale dans la création des arbres de décision, comme nous le verrons dans la section suivante.

Entraînement et test

Le modèle d'arbre de décision M que nous avons construit dans la section précédente classifie le jeu de données initial S avec une exactitude de 100 %. La raison en est très simple : nous l'y avons forcé ! En partant du nœud racine contenant tous les points, les données ont été divisées en sous-ensembles de plus en plus petits jusqu'à ce que chaque nœud feuille contienne un sous-ensemble pur (une seule et même étiquette). Toutefois, rien ne garantit que M représente fidèlement la structure sous-jacente des données. Considérez notre jeu de données S comme un échantillon aléatoire de points prélevé dans une population de points plus vaste. Il se peut que du bruit, des valeurs aberrantes et d'autres facteurs aient été présents dans notre échantillon et conduisent M à fournir des prédictions fallacieuses. Afin d'évaluer le pouvoir prédictif d'un arbre de décision, nous devons le tester sur un ensemble de test comprenant des données étiquetées supplémentaires. Nous mesurons l'exactitude du modèle à l'aide de :

Élagage, limitation de la profondeur et autres méthodes pour réduire la variance

Les arbres de décision souffrent fréquemment de surapprentissage (variance élevée), ce qui nuit à leur exactitude. Heureusement, plusieurs méthodes permettent d'atténuer ce problème.

Un arbre de décision comportant un grand nombre de nœuds internes est sujet au surapprentissage, car il peut prendre des décisions fondées sur une très petite quantité de données ou sur une différence minime entre les caractéristiques de ces données. « Couper les cheveux en quatre » est une expression courante pour souligner des détails insignifiants qui n'ont en réalité que peu d'importance. En règle générale, nous ne voulons pas que nos modèles s'attachent à des détails superflus. L'élagage (pruning) est le processus consistant à réduire la taille d'un arbre de décision en supprimant les branches qui divisent les données de manière trop fine.

Par exemple, lors de la création du modèle M, le sous-ensemble de S défini par la séquence gauche, gauche, droite — c'est-à-dire : $Y\le 13.75$, $X\le 14.55$, et $Y>8.45$ — comprend les points (7.6, 10.2, Rouge), (7.9, 10.6, Rouge), (3.2, 11, Bleu), (5.2, 12.2, Rouge), (9.4, 12.8, Bleu) et (1.9, 13, Rouge). Comme on peut le voir sur la Figure 6.20, il faut trois inégalités supplémentaires pour séparer les quatre points rouges et les deux points bleus en régions de même couleur. À l'issue de ce processus, chacun des deux points bleus et l'un des points rouges deviennent les seuls éléments de leurs sous-ensembles respectifs.

Splitting a set into singletons (one-element subsets) is generally not a great idea in machine learning, as this puts too much predictive weight on a single observation. One method of pruning is to remove branches that split the data into sets L and R in which one of L or R is a singleton (or below a predefined proportion of the original set). Then the node becomes a leaf consisting of data having multiple labels. The label of this new leaf is determined by majority vote. That is, the label that occurs most often becomes the predicted label of any data that finds itself to this node. This method is commonly called error-based (reduced-error) pruning, as it seeks to remove branches that do not significantly increase the classification error rate.

Exemple 6.10

Problème

Utilisez l'élagage pour réduire la complexité du modèle d'arbre de décision M décrit dans cette section. Reclassifiez ensuite les points de données donnés dans l'Exemple 6.8.

Solution

À partir du nœud dont le chemin est $Y\le 13.75$, $X\le 14.55$, $Y>8.45$, le modèle M s'est divisé sur l'inégalité $X\le 8.65$. Cela scinde l'ensemble en $L$ = {(7.6, 10.2, Rouge), (7.9, 10.6, Rouge), (3.2, 11, Bleu), (5.2, 12.2, Rouge), (1.9, 13, Rouge)} et $R$ = {(9.4, 12.8, Bleu)}. Puisque la division produirait un singleton, nous transformons simplement ce nœud en feuille et élaguons toutes les branches et tous les nœuds situés en dessous. Le nœud est désormais une feuille comptant quatre points de données rouges et deux points bleus ; cette feuille est donc étiquetée Rouge. L'organigramme et les régions correspondantes du plan sont présentés à la Figure 6.22 et à la Figure 6.23. Remarquez que l'arbre élagué a une profondeur de 4, ce qui est bien inférieur à la profondeur de 7 de l'arbre initial.

Figure 6.22 Organigramme de l'arbre de décision élagué de l'Exemple 6.10

Figure 6.23 Régions du plan correspondant aux nœuds purs pour l'arbre élagué. Le modèle élagué divise le plan en un nombre de régions inférieur à celui du modèle d'origine, ce qui permet vraisemblablement de mieux saisir la véritable structure sous-jacente sans tomber dans le surapprentissage.

Reclassifions maintenant les points (9.9, 2.5), (15.1, 12.6) et (3.5, 10.2) comme dans le Tableau 6.9.

$(X,Y)=(9.9,2.5)$. En partant du nœud racine, suivez la branche de gauche $(Y=2.5\le 13.75)$. Allez à nouveau à gauche $(X=9.9\le 14.55)$. Suivez encore une fois la branche de gauche $(Y=2.5\le 8.45)$, qui est une feuille bleue.

$(X,Y)=(15.1,12.6)$. En partant du nœud racine, suivez la branche de gauche $(Y=12.6\le 13.75)$. Puis allez à droite $(X=15.1>14.55)$, qui est une feuille rouge.

$(X,Y)=(3.5,10.2)$. En partant du nœud racine, suivez la branche de gauche $(Y=10.2\le 13.75)$. Allez à nouveau à gauche $(X=3.5\le 14.55)$. Suivez ensuite la branche de droite $(Y=10.2>8.45)$, qui est désormais une feuille rouge.

X	Y	Étiquette	Étiquette prédite
9.9	2.5	Bleu	Bleu
15.1	12.6	Rouge	Rouge
3.5	10.2	Rouge	Rouge

Tableau 6.9 Points de test reclassifiés

Le modèle s'avère désormais exact à 100 % sur les données de test. (Bien entendu, un modèle entraîné sur des données du monde réel comportant beaucoup plus d'observations ne peut pas atteindre une exactitude de 100 %, mais cela est possible sur de très petits jeux de données.) Remarquez que l'exactitude du modèle sur l'ensemble d'entraînement d'origine S n'est plus de 100 %. Sur S, l'arbre élagué classe par erreur deux points, (3.2, 11) et (9.4, 12.8), comme rouges alors qu'ils sont en réalité bleus ; l'exactitude sur l'ensemble d'entraînement est donc désormais de $17/19=89.5\%$. Cela reste un très bon résultat !

D'autres méthodes existent pour élaguer un arbre de décision. On distingue deux approches principales : le pré-élagage et le post-élagage. Le pré-élagage consiste à fixer d'emblée des paramètres ou des critères relatifs à la complexité de l'arbre de décision. De nouvelles branches ne sont ajoutées que si ces critères sont respectés. Le post-élagage intervient après que l'arbre complet a été construit sans restriction. Lors du post-élagage, les branches et les nœuds sont éliminés selon des règles définies par l'utilisateur, ce qui transforme des nœuds jusqu'alors internes en nœuds feuilles. L'élagage basé sur l'erreur peut être implémenté aussi bien sous forme d'algorithme de pré-élagage que de post-élagage.

• L'élagage limité par la profondeur (depth-limiting pruning), comme son nom l'indique, signifie qu'un arbre de décision ne peut pas croître au-delà d'une profondeur (ou d'un nombre de niveaux) prédéfinie. Cette technique de pré-élagage contribue à limiter le nombre de petites divisions, mais il convient de veiller à ne pas fixer la profondeur à une valeur trop basse, sous peine d'empêcher le modèle de distinguer des éléments importants.
• L'élagage limité par les feuilles (leaf-limiting pruning) impose un plafond au nombre total de feuilles. À l'instar de la limitation de profondeur, la limitation des feuilles sert à restreindre la complexité globale du modèle d'arbre de décision, mais elle peut conduire au sous-apprentissage et diminuer le pouvoir prédictif du modèle lorsque les données elles-mêmes recèlent une forte complexité qu'il est nécessaire de capturer.
• L'élagage par longueur de description minimale (MDL) (minimum description length (MDL) pruning) est une méthode de post-élagage qui vise à trouver la forme la moins complexe d'un arbre de décision offrant un niveau d'exactitude acceptable. D'une manière générale, un compromis s'impose toujours entre simplicité et exactitude dans tout algorithme d'apprentissage automatique. La démarche de la méthode MDL consiste à privilégier la simplicité. Une description détaillée de l'algorithme MDL dépasse le cadre de cet ouvrage.

Arbres de décision en Python

Le paquet Python sklearn propose des algorithmes performants pour créer et manipuler des arbres de décision. Notons que le classifieur par arbre de décision est ici limité à une profondeur maximale de 3 et que l'indice de Gini est employé à la place du gain d'information. Les données sont issues du jeu de données RedBlue.csv.

Code Python

      # Import libraries
      import pandas as pd  ## for dataset management
      from sklearn.tree import DecisionTreeClassifier 
      from sklearn import tree
      import matplotlib.pyplot as plt
      
      # Read data file
      data = pd.read_csv('RedBlue.csv')
      
      inputs = data[['X', 'Y']]
      output = data['Label']
      
      # Train Decision Tree Classifier
      clf = DecisionTreeClassifier(max_depth=3)
      clf = clf.fit(inputs,output)
      
      # Plot tree with customization
      plt.figure(figsize=(12, 8))  # Set the size of the plot
      tree.plot_tree(clf,
                     rounded=True,       # Round the edges of the box
                     fontsize=10)        # Adjust font size for clarity
      plt.show()  # Display the plot
    

Le résultat obtenu ressemble à ce qui suit :