Diminution de Gini et impureté de Gini des nœuds enfants

Je travaille sur la mesure d'importance de la fonctionnalité Gini pour la forêt aléatoire. Par conséquent, je dois calculer la diminution de Gini de l'impureté du nœud. Voici la façon dont je le fais, ce qui conduit à un conflit avec la définition, suggérant que je dois me tromper quelque part ... :)

Pour un arbre binaire, et étant donné les probabilités des enfants gauche et droit, je peux calculer l'impureté de Gini d'un nœud : $n$

i (n) = 1 - p_{l}^{2} - p_{r}^{2}

$i(n) = 1 - p_l^2 - p_r^2$

Et la baisse de Gini:

Δ i (n) = i (n) - p_{l} i (n_{l}) - p_{r} i (n_{r})

$\Delta i(n) = i(n) - p_li(n_l) - p_ri(n_r)$

Donc, pour cet exemple avec 110 observations sur un nœud:

- node (110)
   - left (100)
      - left_left (60)
      - left_right (40)
   - right (10)
      - right_left (5)
      - right_right (5)

Je calculerais la diminution de Gini pour le nœud comme ceci:

\begin{aligned} je (l e F t) & = 1 - (60 / 100)^{²} - (40 / 100)^{²} & = 0,48 \\ je (r je g h t) & = 1 - (5 / dix)^{²} - (5 / dix)^{²} & = 0,50 \\ je (n o ré e) & = 1 - (100 / 110)^{²} - (dix / 110)^{²} & = 0,16 \end{aligned}

$\begin{align} i({\rm left}) &= 1 - (60/100)^² - (40/100)^²& &= 0.48 \\ i({\rm right}) &= 1 - (5/10)^² - (5/10)^²& &= 0.50 \\ i({\rm node}) &= 1 - (100/110)^² - (10/110)^²& &= 0.16 \end{align}$

Mais suivant la définition de Breiman (ou cette réponse sur CV: Comment mesurer / classer "l'importance variable" lors de l'utilisation de CART , mais je n'ai pas accès au livre référencé), le critère d'impureté du descendant doit être inférieur à celui du parent nœud:

Importance de Gini
Chaque fois qu'un fractionnement d'un nœud est effectué sur la variable m, le critère d'impureté de Gini pour les deux nœuds descendants est inférieur à celui du nœud parent. L'addition des diminutions de gini pour chaque variable individuelle sur tous les arbres de la forêt donne une importance variable rapide qui est souvent très cohérente avec la mesure de l'importance de la permutation.

Parce que sinon, cela conduit à une diminution négative de Gini ...

Δ i (n o d e) = i (n o d e) - (100 / 110) * i (l e f t) - (10 / 110) * i (r i g h t) = - 0,32

$\Delta i({\rm node}) = i({\rm node}) - (100/110)*i({\rm left}) - (10/110)*i({\rm right}) = -0.32$

Donc, si quelqu'un pouvait dire où je me trompe, je serais très reconnaissant car il semble que je manque quelque chose d'évident ici ...

feature-selection random-forest cart Rémi Mélisson
la source

Vous n'avez tout simplement pas utilisé du tout la variable de classe cible. L'impureté de Gini, comme toutes les autres fonctions d'impureté, mesure l'impureté des sorties après une séparation. Ce que vous avez fait, c'est mesurer quelque chose en utilisant uniquement la taille de l'échantillon.

J'essaie de dériver la formule de votre cas.

Supposons pour plus de simplicité que vous ayez un classificateur binaire. Notons avec l'attribut de test, avec l'attribut de classe qui ont des valeurs . $A$ $C$ $c_+, c_-$

L'index de Gini initial avant la division est donné par où est la proportion de points de données qui ont une valeur pour la classe variable.

je (UNE) = 1 - P ({UNE}_{+})^{2} - P ({UNE}_{-})^{2}

$I(A) = 1 - P(A_+)^2 - P(A_-)^2$

P (A_{+})

$P(A_+)$

c_{+}

$c_+$

Maintenant, l'impureté pour le nœud gauche serait où est la proportion de points de données du sous-ensemble gauche de qui ont la valeur dans la variable de classe, etc.

je (UNE l) = 1 - P (UNE l_{+})^{2} - P (UNE l_{-})^{2}

$I(Al) = 1 - P(Al_+)^2-P(Al_-)^2$

je (UNE r) = 1 - P (UNE r_{+})^{2} - P (UNE r_{-})^{2}

$I(Ar) = 1 - P(Ar_+)^2-P(Ar_-)^2$

P (A l_{+})

$P(Al_+)$

A

$A$

c_{+}

$c_+$

Maintenant, la formule finale pour GiniGain serait

g je n je g une je n (UNE) = je (UNE) - p_{l e F t} je (UNE l) - p_{r je g h t} je (UNE r)

$GiniGain(A) = I(A) - p_{left}I(Al) - p_{right}I(Ar)$ où est la proportion d'instances pour le sous-ensemble gauche, ou (nombre d' instances en partie gauche divisé par le nombre total de cas de .

p_{l e f t}

$p_{left}$

\frac{# | A l |}{# | A l | + # | A r |}

$\frac{\#|Al|}{\#|Al|+\#|Ar|}$

A

$A$

Je sens que ma notation pourrait être améliorée, je regarderai plus tard quand j'aurai plus de temps.

Conclusion

L'utilisation d'un nombre limité de points de données n'est pas suffisante, l'impureté signifie à quel point une entité (entité de test) est capable de reproduire la distribution d'une autre entité (entité de classe). La distribution des fonctionnalités de test produit le nombre que vous avez utilisé (comment à gauche, comment à droite), mais la distribution de la fonctionnalité de classe n'est pas utilisée dans vos formules.

Édition ultérieure - prouver pourquoi il diminue

Maintenant, j'ai remarqué que j'ai raté la partie, ce qui prouve pourquoi l'index gini du nœud enfant est toujours inférieur à celui du nœud parent. Je n'ai pas de preuve complète ou vérifiée, mais je pense que c'est une preuve valide. Pour d'autres choses intéressantes liées au sujet, vous pouvez consulter la note technique: Certaines propriétés des critères de fractionnement - Leo Breiman . Maintenant, il suivra ma preuve.

Supposons que nous soyons dans le cas binaire, et toutes les valeurs d'un nœud pourraient être complètement décrites par une paire avec la signification d' instance de la première classe et de instances de la deuxième classe. Nous pouvons dire que dans le nœud parent que nous avons $(a,b)$ $a$ $b$ $(a,b)$ instances.

Afin de trouver le meilleur fractionnement, nous trions les instances selon une fonctionnalité de test et nous essayons tous les fractionnements binaires possibles. Trié par une caractéristique donnée est en fait une permutation d'instances, dans laquelle les classes commencent par une instance de la première classe ou de la deuxième classe. Sans perdre la généralité, nous supposerons qu'elle commence par une instance de la première classe (si ce n'est pas le cas nous avons une preuve miroir avec le même calcul).

La première division à essayer est dans les instances gauche et droite . Comment l'index gini de ces candidats possibles pour les nœuds enfants gauche et droit est comparé au nœud parent? Évidemment, à gauche, nous avons . Donc, sur le côté gauche, nous avons une valeur d'indice de Gini plus petite. Et le bon nœud? $(1,0)$ $(a-1,b)$ $h(left) = 1 - (1/1)^2 - (0/1)^2 = 0$

h (p une r e n t) = 1 - (\frac{une}{une + b})^{2} - (\frac{b}{une + b})^{2}

$h(parent) = 1 - (\frac{a}{a+b})^2 - (\frac{b}{a+b})^2$

h (r je g h t) = 1 - (\frac{une - 1}{(une - 1) + b})^{2} - (\frac{b}{(une - 1) + b})^{2}

$h(right) = 1 - (\frac{a-1}{(a-1)+b})^2 - (\frac{b}{(a-1)+b})^2$

Considérant que est supérieur ou égal à (car sinon comment pourrions-nous séparer une instance de la première classe dans le nœud gauche?) Et après simplification, il est simple de voir que l'index gini pour le nœud droit a une valeur plus petite que pour le nœud parent. $a$ $0$

Maintenant, la dernière étape de la preuve consiste à nouer que, tout en considérant tous les points de partage possibles dictés par les données que nous avons, nous gardons celui qui a le plus petit indice de Gini agrégé, ce qui signifie que l'optimum que nous choisissons est inférieur ou égal au trivial que j'ai prouvé qui est plus petit. Ce qui conclut qu'à la fin l'indice de Gini va diminuer.

En conclusion finale, nous devons noter que même si diverses divisions peuvent donner des valeurs plus grandes que le nœud parent, celle que nous choisissons sera la plus petite d'entre elles et également plus petite que la valeur d'index gini parent.

J'espère que cela aide.

rapaio
la source

Merci beaucoup, vous avez déverrouillé mon cerveau ... En fait, puisque je traite des arbres de régression, l'utilisation de la variable de classe cible est apparue moins évidente que pour une tâche de classification pure. Mais cela a désormais tout son sens.

Remi Mélisson

J'ai mis à jour la réponse pour contenir les pièces manquantes.

rapaio

Diminution de Gini et impureté de Gini des nœuds enfants

Réponses: