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

15

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)=1pl2pr2

E o Gini diminui:

Δi(n)=i(n)pli(nl)pri(nr)

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 como este:

i(left)=1(60/100)²(40/100)²=0.48i(right)=1(5/10)²(5/10)²=0.50i(node)=1(100/110)²(10/110)²=0.16

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 ...

Δi(node)=i(node)(100/110)i(left)(10/110)i(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 ...

Remi Mélisson
fonte

Respostas:

16

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 -ACc+,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)=1P(A+)2P(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)=1P(Al+)2P(Al)2
I(Ar)=1P(Ar+)2P(Ar)2
P(Al+)Ac+

Agora, a fórmula final para o GiniGain seria

GiniGain(A)=I(A)pleftI(Al)prightI(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 .pleft#|Al|#|Al|+#|Ar|UMA

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 .(uma,b)umab(uma,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)(a1,b)h(left)=1(1/1)2(0/1)2=0

h(parent)=1(aa+b)2(ba+b)2
h(right)=1(a1(a1)+b)2(b(a1)+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.a0

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.

rapaio
fonte
Muito obrigado, você desbloqueou meu cérebro ... De fato, como estou lidando com árvores de regressão, o uso da variável de classe-alvo parecia menos óbvio do que para uma tarefa de classificação pura. Mas agora faz totalmente sentido.
Remi Mélisson
Atualizei a resposta para conter as partes ausentes.
rapaio