Le gain d’information, comme l’impureté de Gini, est une métrique utilisée pour entraîner les arbres de décision. Plus précisément, ces métriques mesurent la qualité d’un fractionnement. Par exemple, disons que nous avons les données suivantes :
Et si nous faisions une division à x=1,5x = 1,5x=1,5 ?
Cette division imparfaite divise notre ensemble de données en ces branches :
- Branche de gauche, avec 4 bleus.
- Branche droite, avec 1 bleu et 5 verts.
Il est clair que cette division n’est pas optimale, mais quelle est sa qualité ? Comment pouvons-nous quantifier la qualité d’un fractionnement ?
C’est là que le gain d’information entre en jeu.
Confusé ? Vous ne savez pas ce que sont les arbres de décision ou comment ils sont formés ? Lisez le début de mon introduction aux forêts aléatoires et aux arbres de décision.
Entropie d’information
Avant d’en arriver au gain d’information, nous devons d’abord parler de l’entropie d’information. Dans le contexte de la formation des arbres de décision, l’entropie peut être considérée grossièrement comme la quantité de variance des données. Par exemple :
- Un jeu de données composé uniquement de bleus aurait une entropie très faible (en fait, nulle).
- Un jeu de données composé d’un mélange de bleus, de verts et de rouges aurait une entropie relativement élevée.
Voici comment on calcule l’entropie de l’information pour un ensemble de données avec des classes CCC :
E=-∑iCpilog2piE = -\sum_i^C p_i \log_2 p_iE=-i∑Cpilog2pi
où pip_ipi est la probabilité de choisir au hasard un élément de la classe iii (c’est-à-dire la proportion de la classe iii dans l’ensemble des données).C’est-à-dire la proportion de l’ensemble de données constituée de la classe iii).
La façon la plus simple de comprendre ceci est avec un exemple. Considérons un ensemble de données comportant 1 bleu, 2 verts et 3 rouges : . Alors
E=-(pblog2pb+pglog2pg+prlog2pr)E = -(p_b \log_2 p_b + p_g \log_2 p_g + p_r \log_2 p_r)E=-(pblog2pb+pglog2pg+prlog2pr) E=-(16log2(16)+26log2(26)+36log2(36))=1.46\begin{aligned}E &= -(\frac{1}{6} \log_2(\frac{1}{6}) + \frac{2}{6} \log_2(\frac{2}{6}) + \frac{3}{6} \log_2(\frac{3}{6})) \&= \boxed{1.46} \\\\\end{aligned}E=-(61log2(61)+62log2(62)+63log2(63))=1.46
Qu’en est-il d’un ensemble de données d’une seule couleur ? Prenons l’exemple de 3 bleus : . L’entropie serait
E=-(1log21)=0E = -(1 \log_2 1) = \boxed{0}E=-(1log21)=0
Gain d’information
Il est enfin temps de répondre à la question que nous avons posée précédemment : comment quantifier la qualité d’un split ?
Reprenons ce split :
Avant le split, nous avions 5 bleus et 5 verts, donc l’entropie était
Ebefore=-(0,5log20,5+0,5log20,5)=1\begin{aligned}E_{before}. &= -(0.5 \log_2 0.5 + 0.5 \log_2 0.5) \&= \boxed{1} \\\\Nend{aligned}Ebefore=-(0.5log20.5+0.5log20.5)=1
Après la séparation, nous avons deux branches.
La branche de gauche a 4 bleus, donc Eleft=0E_{left} = \boxed{0}Eleft=0 car c’est un ensemble de données d’une seule couleur.
La branche droite a 1 bleu et 5 verts, donc
Eright=-(16log2(16)+56log2(56))=0,65\begin{aligned}E_{right}. &= -(\frac{1}{6} \log_2 (\frac{1}{6}) + \frac{5}{6} \log_2 (\frac{5}{6})) \&= \boxed{0.65} \\\\\N-Extended{aligned}Eright=-(61log2(61)+65log2(65))=0.65
Maintenant que nous avons les entropies des deux branches, nous pouvons déterminer la qualité de la division en pondérant l’entropie de chaque branche par le nombre d’éléments qu’elle possède. Puisque la branche gauche a 4 éléments et la branche droite en a 6, nous les pondérons par 0,40,40,4 et 0,60,60,6, respectivement :
Esplit=0,4∗0+0,6∗0,65=0,39\begin{aligned}E_{split}. &= 0.4 * 0 + 0.6 * 0.65 \&= \boxed{0.39} \\\\Nend{aligned}Esplit=0.4∗0+0.6∗0.65=0.39
Nous avons commencé avec Ebefore=1E_{before} = 1Ebefore=1 entropie avant la séparation et maintenant nous sommes descendus à 0.390.390.39 ! Gain d’information = combien d’entropie nous avons enlevé, donc
Gain=1-0.39=0.61\text{Gain} = 1 – 0.39 = \boxed{0.61}Gain=1-0.39=0.61
Ceci est logique : un gain d’information plus élevé = plus d’entropie enlevée, ce qui est ce que nous voulons. Dans le cas parfait, chaque branche ne contiendrait qu’une seule couleur après la division, ce qui représenterait une entropie nulle !
Récapitulation
L’entropie de l’information peut être considérée comme le degré d’imprévisibilité d’un ensemble de données.
- Un ensemble d’une seule classe (disons, bleu ) est extrêmement prévisible : tout ce qu’il contient est bleu. Cela aurait une entropie faible.
- Un ensemble de nombreuses classes mélangées est imprévisible : un élément donné pourrait être de n’importe quelle couleur ! Cela aurait une entropie élevée.
La formule réelle pour calculer l’entropie d’information est :
E=-∑iCpilog2piE = -\sum_i^C p_i \log_2 p_iE=-i∑Cpilog2pi
Le gain d’information est calculé pour une division en soustrayant les entropies pondérées de chaque branche de l’entropie d’origine. Lors de la formation d’un arbre de décision à l’aide de ces métriques, la meilleure division est choisie en maximisant le gain d’information.
Vous voulez en savoir plus ? Consultez mon explication de l’impureté de Gini, une métrique similaire, ou mon guide approfondi Random Forests for Complete Beginners.