Diminuição de Gini e impureza de Gini nos nós filhos

Estou trabalhando na medida de importância do recurso Gini para florestas aleatórias. Portanto, preciso calcular a diminuição de Gini na impureza do nó. Aqui está a maneira como faço isso, o que leva a um conflito com a definição, sugerindo que devo estar errado em algum lugar ... :)

Para uma árvore binária, e dadas as probabilidades de filhos esquerdos e direitos, eu posso calcular a impureza Gini de um nó $n$ :

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

E o Gini diminui:

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

---

Portanto, neste exemplo, com 110 observações em um nó:

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

Eu calcularia a diminuição de Gini para o nó como este:

$$\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}$$

Mas, seguindo a definição de Breiman (ou esta resposta no CV: Como medir / classificar "importância variável" ao usar o CART , mas não tenho acesso ao livro referenciado), o critério de impureza do descendente deve ser menor que o pai nó:

Importância de Gini
Toda vez que uma divisão de um nó é feita na variável m, o critério de impureza de gini para os dois nós descendentes é menor que o nó pai. A soma das diminuições de gini para cada variável individual em todas as árvores da floresta fornece uma importância variável rápida que geralmente é muito consistente com a medida de importância da permutação.

Porque, caso contrário, leva à diminuição negativa de Gini ...

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

Então, se alguém pudesse dizer onde estou errado, ficaria muito grato porque parece que sinto falta de algo evidente aqui ...

Você simplesmente não usou a variável de classe de destino. A impureza de Gini, como todas as outras funções de impureza, mede a impureza dos resultados após uma divisão. O que você fez é medir algo usando apenas o tamanho da amostra.

Eu tento derivar a fórmula para o seu caso.

Suponha que, por simplicidade, você tenha um classificador binário. Denote com o atributo de teste, com o atributo de classe que possui valores .C c + , c $A$$C$$c_+, c_-$

O índice gini inicial antes da divisão é dado por que é a proporção de pontos de dados que têm valor para a classe variável. P ( A + ) c

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

Agora, a impureza para o nó esquerdo seria onde é a proporção de pontos de dados do subconjunto esquerdo de que têm valor na variável de classe, etc.

$$I(Al) = 1 - P(Al_+)^2-P(Al_-)^2$$ $$I(Ar) = 1 - P(Ar_+)^2-P(Ar_-)^2$$ $P(Al_+)$$A$$c_+$

Agora, a fórmula final para o GiniGain seria

$$GiniGain(A) = I(A) - p_{left}I(Al) - p_{right}I(Ar)$$ que é a proporção de instâncias para o subconjunto esquerdo ou (quantas instâncias estão em subconjunto esquerdo dividido pelo número total de instâncias de .$p_{left}$$\frac{\#|Al|}{\#|Al|+\#|Ar|}$$A$

Eu sinto que minha notação pode ser melhorada, observarei mais tarde quando tiver mais tempo.

Conclusão

Usar apenas um número de pontos de dados não é suficiente; impureza significa quão bem um recurso (recurso de teste) é capaz de reproduzir a distribuição de outro recurso (recurso de classe). A distribuição do recurso de teste produz o número que você usou (como à esquerda, como à direita), mas a distribuição do recurso de classe não é usada em suas fórmulas.

Edição posterior - prove por que diminui

Agora notei que perdi a parte que prova por que sempre o índice gini no nó filho é menor que no nó pai. Não tenho uma prova completa ou verificada, mas acho que é uma prova válida. Para outra coisa interessante relacionada ao tópico, consulte Nota técnica: algumas propriedades dos critérios de divisão - Leo Breiman . Agora seguirá minha prova.

Suponha-se que são, no caso binário, e todos os valores em um nó pode ser completamente descrita por um par com o significado de ocorrências da primeira classe, e instâncias da segunda classe. Podemos afirmar que no nó pai temos instâncias .$(a,b)$$a$$b$$(a,b)$

Para encontrar a melhor divisão, classificamos as instâncias de acordo com um recurso de teste e tentamos todas as divisões binárias possíveis. Classificadas por um determinado recurso é na verdade uma permutação de instâncias, nas quais as classes começam com uma instância da primeira ou da segunda classe. Sem perder a generalidade, suporemos que ela comece com uma instância da primeira classe (se esse não for o caso, teremos uma prova de espelho com o mesmo cálculo).

A primeira divisão a tentar está nas instâncias esquerda e direita . Como o índice gini desses possíveis candidatos para nós filhos esquerdo e direito é comparado com o nó pai? Obviamente, à esquerda, temos . Portanto, no lado esquerdo, temos um valor menor do índice gini. E o nó certo?$(1,0)$$(a-1,b)$$h(left) = 1 - (1/1)^2 - (0/1)^2 = 0$

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

Considerando que é maior ou igual a (caso contrário, como poderíamos separar uma instância da primeira classe no nó esquerdo?) E após a simplificação, é simples ver que o índice gini para o nó direito tem um valor menor do que para o nó nó pai.$a$$0$

Agora, o estágio final da prova é o de que, embora considerando todos os pontos de divisão possíveis ditados pelos dados que temos, mantemos o que possui o menor índice de gini agregado, o que significa que o melhor que escolhemos é menor ou igual ao trivial que eu provei que é menor. O que conclui que no final o índice gini diminuirá.

Como conclusão final, devemos observar que, mesmo que várias divisões possam fornecer valores maiores que o nó pai, o que escolhermos será o menor dentre eles e também menor que o valor do índice gini pai.

Espero que ajude.