Get best of the week

Entropie: comment les arbres de décision prennent des décisions

Une traduction de l'article a été préparée avant le début du cours d' apprentissage automatique .



Vous êtes un spécialiste de la science des données qui suit actuellement un parcours d'apprentissage. Et vous avez parcouru un long chemin depuis que vous avez écrit votre première ligne de code en Python ou R. Vous connaissez Scikit-Learn comme le dos de votre main. Maintenant, vous êtes plus assis sur Kaggle que sur Facebook. Vous n'êtes pas nouveau dans la création de superbes forêts aléatoires et d'autres modèles d'ensemble d'arbres de décision qui font un excellent travail. Néanmoins, vous savez que vous n'obtiendrez rien si vous ne vous développez pas complètement. Vous voulez approfondir et comprendre les subtilités et les concepts qui sous-tendent les modèles populaires d'apprentissage automatique. Et bien moi aussi.

Aujourd'hui, je parlerai du concept d'entropie - l'un des sujets les plus importants en statistique, et plus tard nous parlerons du concept de gain d'information (gain d'information) et découvrirai pourquoi ces concepts fondamentaux forment la base de la façon dont les arbres de décision sont construits à partir des données obtenues.

Bien. Maintenant, transgressons.

Qu'est-ce que l'entropie? En termes simples, l'entropie n'est rien d'autre qu'une mesure du désordre. (Cela peut aussi être considéré comme une mesure de pureté, et bientôt vous comprendrez pourquoi. Mais j'aime plus le gâchis parce qu'il semble plus frais.) La

formule mathématique de l'entropie est la suivante: l'


entropie. Elle est parfois écrite comme H.

Ici p i est la probabilité de fréquence d'un élément / classe i de nos données. Pour simplifier, supposons que nous ayons seulement deux classes: positive et négative. Ensuite, je prendrai la valeur "+" ou "-". Si nous avions un total de 100 points dans notre ensemble de données, dont 30 appartenaient à la classe positive et 70 appartenaient au négatif, alors p + serait 3/10, et p- sera 7/10. Ici, tout est simple.

Si je calcule l'entropie des classes à partir de cet exemple, voici ce que j'obtiens en utilisant la formule ci-dessus: l'



entropie est d'environ 0,88. Cette valeur est considérée comme assez élevée, c'est-à-dire que nous avons un niveau élevé d'entropie ou de trouble (c'est-à-dire une faible valeur de pureté). L'entropie est mesurée dans la plage de 0 à 1. En fonction du nombre de classes dans votre ensemble de données, la valeur de l'entropie peut s'avérer supérieure à 1, mais cela signifie la même chose car le niveau de trouble est extrêmement élevé. Pour simplifier l'explication, dans l'article d'aujourd'hui, nous aurons une entropie allant de 0 à 1.

Jetez un œil au tableau ci-dessous.



Sur l'axe X, le nombre de points de la classe positive dans chaque cercle est reflété, et sur l'axe Y, les entropies correspondantes. Vous pouvez immédiatement remarquer la forme en U inversée du graphique. L'entropie sera la plus petite aux extrémités si en principe il n'y a pas d'éléments positifs dans le cercle ou quand il n'y a que des éléments positifs. Autrement dit, lorsque les éléments sont identiques dans un cercle, le désordre sera 0. L'entropie sera la plus élevée au milieu du graphique, où les éléments positifs et négatifs seront uniformément répartis à l'intérieur du cercle. Ici, la plus grande entropie ou désordre sera atteint, car il n'y aura pas d'éléments prédominants.

Y a-t-il une raison pour laquelle l'entropie est mesurée en utilisant le logarithme en base 2, ou pourquoi l'entropie est-elle mesurée entre 0 et 1, et non dans une plage différente? Non, il n'y a aucune raison. Ceci est juste une métrique. Ce n'est pas si important de comprendre pourquoi cela se produit. Il est important de savoir comment ce que nous avons obtenu ci-dessus est calculé et comment cela fonctionne. L'entropie est une mesure de la confusion ou de l'incertitude, et l'objectif des modèles d'apprentissage automatique et des spécialistes de la science des données en général est de réduire cette incertitude.

Maintenant, nous savons comment le désordre est mesuré. Ensuite, nous avons besoin d'une valeur pour mesurer la réduction de ce trouble dans les informations supplémentaires (attributs / variables indépendantes) de la variable / classe cible. C'est là que le gain d'information ou le gain d'information entre en jeu. Du point de vue des mathématiques, cela peut s'écrire comme suit:



Nous soustrayons simplement l'entropie Y de X, de l'entropie Y, afin de calculer la diminution de l'incertitude sur Y, à condition qu'il y ait des informations sur X sur Y. Plus l'incertitude diminue, plus il est possible d'obtenir des informations de Y sur X.

Regardons un exemple simple du tableau de contingence afin que se rapprocher de la question de savoir comment les arbres de décision utilisent l'entropie et le gain d'informations pour décider sur quelle base casser les nœuds dans le processus d'apprentissage sur les données.

Exemple: Tableau de conjugaison



Ici, notre variable cible sera Responsabilité , qui ne peut prendre que deux valeurs: «Normal» et «Élevé». Nous avons également un seul signe, qui s'appelle Credit Rating, il répartit les valeurs en trois catégories: «Excellent» , «Good» et «Poor» . Au total, 14 observations ont été faites. 7 d'entre eux appartiennent à la classe Responsabilité Normale et 7 autres à la classe Haute Responsabilité . Il s'agit d'une division en soi.

Si nous regardons la somme totale des valeurs dans la première ligne, nous verrons que nous avons 4 observations avec une excellente valeur basée sur la cote de crédit . De plus, je peux même dire que ma variable cible est brisée par une notation de crédit «excellente» . Parmi les observations avec la valeur «Excellent» par attributNotation de crédit , il y en a 3 qui appartiennent à la classe de responsabilité normale et 1 qui appartient à la classe de responsabilité élevée . De même, je peux calculer des résultats similaires pour d'autres valeurs de notation de crédit à partir du tableau de contingence.

Par exemple, j'utilise le tableau de contingence ci-dessus pour calculer indépendamment l'entropie de notre variable cible, puis calculer son entropie, en tenant compte des informations supplémentaires de l'attribut de notation de crédit . Je peux donc calculer la quantité d'informations supplémentaires que la cote de crédit me donnera pour la variable cible de responsabilité .

Alors, commençons.



L'entropie de notre variable cible est 1, ce qui signifie un encombrement maximal en raison de la distribution uniforme des éléments entre «Normal» et «Haut» . L'étape suivante consiste à calculer l'entropie de la variable cible du passif , en tenant compte des informations supplémentaires de la notation de crédit . Pour ce faire, nous calculons l'entropie du passif pour chaque valeur de notation de crédit et les ajoutons en utilisant le rapport d'observation pondéré moyen pour chaque valeur. La raison pour laquelle nous utilisons la moyenne pondérée deviendra plus claire lorsque nous parlerons d'arbres de décision.



Nous avons obtenu l'entropie de notre variable cible avec l'attribut Credit Rating. Nous pouvons maintenant calculer le gain de responsabilité informationnel de la notation de crédit pour comprendre à quel point cette fonctionnalité est informative.



La connaissance de la cote de crédit nous a aidés à réduire l'incertitude de notre variable cible de passif .. N'est-ce pas un bon signe qui devrait fonctionner? Donnez-nous des informations sur la variable cible? Eh bien, pour cette raison même, les arbres de décision utilisent l'entropie et le gain informationnel. Ils déterminent selon quel critère pour briser les nœuds en branches, afin d'approcher la variable cible avec chaque partition suivante, et aussi de comprendre quand la construction de l'arbre doit être terminée! (en plus des hyperparamètres tels que la profondeur maximale, bien sûr). Voyons comment tout cela fonctionne dans l'exemple suivant en utilisant des arbres de décision.

Exemple: arbre de décision

Examinons un exemple de construction d’un arbre de décision, dans le but de prédire si le crédit d’une personne sera radié ou non. La population sera de 30 exemplaires. 16 appartiendront à la classe des radiations , et les 14 autres«Non amorti» . Nous aurons deux signes, à savoir "Balance" , qui peut prendre deux valeurs: "<50K" ou "> 50K", et "Résidence" , qui prend trois valeurs: "OWN" , "RENT" ou "OTHER" . Je vais montrer comment l'algorithme d'arbre de décision décidera quel attribut casser en premier et quel attribut sera plus informatif, c'est-à-dire qu'il élimine le mieux l'incertitude de la variable cible en utilisant le concept d'entropie et de gain d'information.

Symptôme 1: équilibre



Ici, les cercles appartiennent à la classe «radiation» et les étoiles correspondent à la classe «non radiation» . Partitionnement d'une racine parent par attributL'équilibre nous donnera 2 nœuds héritiers. Dans le nœud de gauche, il y aura 13 observations, où 12/13 (probabilité 0,92) d'observations de la classe «radiation» et seulement 1/13 (probabilité 0,08) d'observations de la classe «non radiation» . Dans le nœud de droite, il y aura 17 observations sur 30, dont 13/17 (probabilité 0,76) d'observations de la classe «radiations» et 4/17 (probabilité 0,24) d'observations de la classe «non radiations» .

Calculons l'entropie de la racine et voyons dans quelle mesure l'arbre peut réduire l'incertitude en utilisant une partition basée sur Balance .



Une répartition basée sur l' équilibre donnera un gain d'information de 0,37. Comptons la même chose pour le signe de la résidenceet comparer les résultats.

Symptôme 2: Résidence Le



fractionnement d'un arbre basé sur Résidence vous donnera 3 nœuds héritiers. Le nœud successeur gauche recevra 8 observations, où 7/8 (probabilité 0,88) d'observations de la classe des radiations et seulement 1/8 (probabilité 0,12) des observations de la classe des non radiations . Le nœud successeur moyen recevra 10 observations, dont 4/10 (probabilité 0,4) d'observations de la classe des radiations et 6/10 (probabilité 0,6) des observations de la classe des non radiations . L'héritier droit recevra 12 observations, dont 5/12 (probabilité 0,42) d'observations de la classe des radiations et 7/12 (probabilité 0,58) des observations de la classe des non radiations. Nous connaissons déjà l'entropie du nœud parent, nous calculons donc simplement l'entropie après la partition pour comprendre le gain informationnel de l'attribut Residence .



Le gain informationnel de l'attribut Balance est presque 3 fois supérieur à celui de la résidence ! Si vous regardez à nouveau les graphiques, vous verrez que le partitionnement selon Balance donnera des nœuds descendants plus propres que selon Residence . Cependant, le nœud le plus à gauche de Residence est également assez propre, mais c'est ici que la moyenne pondérée entre en jeu. Malgré le fait que le nœud soit propre, il a le moins d'observations et son résultat est perdu dans le recalcul général et le calcul de l'entropie totale selon Residence. Ceci est important car nous recherchons le contenu informatif général de l'attribut et ne voulons pas que le résultat final soit déformé par la valeur rare de l'attribut.

L'attribut Balance lui-même fournit plus d'informations sur la variable cible que Résidence . Ainsi, l'entropie de notre variable cible est réduite. L'algorithme d'arbre de décision utilise ce résultat pour effectuer la première division selon Balancepour décider plus tard sur quelle base casser les nœuds suivants. Dans le monde réel, lorsqu'il y a plus de deux fonctionnalités, la première ventilation se produit en fonction de la fonctionnalité la plus informative, puis, à chaque rupture ultérieure, le gain d'informations sera recompté pour chaque fonctionnalité supplémentaire, car il ne sera pas le même que le gain d'informations de chaque fonctionnalité individuellement. L'entropie et le gain informationnel doivent être calculés après qu'une ou plusieurs partitions se sont produites, ce qui affectera le résultat final. L'arbre de décision répétera ce processus au fur et à mesure qu'il grandit, jusqu'à ce qu'il atteigne une certaine profondeur ou qu'une sorte de fractionnement conduise à un gain d'informations plus élevé au-delà d'un certain seuil, qui peut également être spécifié comme hyperparamètre!

C'est tout! Vous savez maintenant quelle entropie, quel gain d'information et comment ils sont calculés. Vous comprenez maintenant comment l'arbre de décision, seul ou en tant qu'ensemble, prend des décisions sur le meilleur ordre de partitionnement par attributs et décide quand s'arrêter lors de l'apprentissage des données disponibles. Eh bien, si vous devez expliquer à quelqu'un comment fonctionnent les arbres de décision, j'espère que vous pourrez faire face à cette tâche de manière adéquate.

J'espère que vous avez appris quelque chose d'utile par cet article. Si j'ai raté quelque chose ou que je me suis mal exprimé, écrivez-moi. Je vous en serai très reconnaissant! Remercier.


En savoir plus sur le cours.

More articles:


All Articles