Ganho de Informação, como Gini Impureza, é uma métrica usada para treinar Árvores de Decisão. Especificamente, essas métricas medem a qualidade de uma divisão. Por exemplo, digamos que temos os seguintes dados:
E se fizéssemos uma divisão em x=1,5x = 1,5x=1,5?
Esta divisão imperfeita quebra o nosso conjunto de dados nestes ramos:
- Ramo esquerdo, com 4 azuis.
- Ramo direito, com 1 azul e 5 verdes.
Está claro que esta divisão não é óptima, mas quão boa é? Como podemos quantificar a qualidade de uma divisão?
É aí que entra o Ganho de Informação.
Confuso? Não tem certeza do que são Árvores de Decisão ou como são treinadas? Leia o início da minha introdução a Florestas Aleatórias e Árvores de Decisão.
Entropia da Informação
Antes de chegarmos ao Ganho de Informação, temos de falar primeiro sobre a Entropia da Informação. No contexto do treinamento de Árvores de Decisão, a Entropia pode ser pensada, grosso modo, como a variação dos dados. Por exemplo:
- Um conjunto de dados de apenas blues teria entropia muito baixa (de fato, zero).
- Um conjunto de dados de blues, greens e vermelhos misturados teria entropia relativamente alta.
Aqui está como calculamos a entropia de informação para um conjunto de dados com classes CCC:
E=-∑iCpilog2piE = -\sum_i^C p_i \log_2 p_iE=-i∑Cpilog2pi
onde pip_ipi é a probabilidade de escolher aleatoriamente um elemento da classe iii (i.e. a proporção do conjunto de dados composto pela classe iii).
A maneira mais fácil de entender isto é com um exemplo. Considere um conjunto de dados com 1 azul, 2 verdes, e 3 vermelhos: . Então
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{alinhado}E &= -(\frac{1}{6} \Log_2({1}frac{6}) + {2}frac{6} \Log_2(2)(frac{2}{6}) + frac{3}{6} \Log_2({3}{6})) \\&=caixa (1.46) \\\E=-(61log2(61)+62log2(62)+63log2(63))=1.46
E que tal um conjunto de dados de uma cor? Considere 3 azuis como exemplo: . A entropia seria
E=-(1log21)=0E = -(1 \log_2 1) = \boxed{0}E=-(1log21)=0
Information Gain
Finalmente é hora de responder à pergunta que fizemos anteriormente: como podemos quantificar a qualidade de uma divisão?
Vamos considerar novamente esta divisão:
Antes da divisão, tínhamos 5 azuis e 5 verdes, portanto a entropia era
Ebefore=-(0.5log20.5+0.5log20.5)=1\begin{alinhado}E_{antes} &= -(0.5 \log_2 0.5 + 0.5 \log_2 0.5) \\\\\\\\\i1>= {1} \\\Antes=-(0.5log20.5+0.5log20.5)=1
Após a divisão, temos dois ramos.
Ramo esquerdo tem 4 azuis, então Eleft=0E_{esquerda} = {0}Eleft=0 porque é um conjunto de dados de uma cor.
Ramo direito tem 1 azul e 5 verdes, portanto
Eright=-(16log2(16)+56log2(56))=0.65\begin{alinhado}E_{direita} &= -(\frac{1}{6} \Log_2 (1) + Frac (6) + Frac (5) \Log_2 (5) (frac{6}) \\&=caixotado (0.65) \\\End{alinhado}Eright=-(61log2(61)+65log2(65))=0.65
Agora que temos as entropia para ambos os ramos, podemos determinar a qualidade da divisão ponderando a entropia de cada ramo pela quantidade de elementos que ele possui. Como o ramo esquerdo tem 4 elementos e o ramo direito tem 6, nós os pesamos por 0.40.40.4 e 0.60.60.6, respectivamente:
Esplit=0.4∗0+0.6∗0.65=0.39\begin{alinhado}E_{split} &= 0.4 * 0 + 0.6 * 0.65 {0.39} {0.39} \\\Fim de divisão=0.4∗0+0.6∗0.65=0.39
Comecemos com Ebefore=1E_{before} = 1Ebefore=1 entropia antes da divisão e agora estamos reduzidos a 0.390.390.39! Information Gain = quanta Entropia removemos, então
Gain=1-0.39=0.61\text{Gain} = 1 – 0.39 = \boxed{0.61}Gain=1-0.39=0.61
Isto faz sentido: higher Information Gain = mais Entropia removida, que é o que nós queremos. No caso perfeito, cada ramo conteria apenas uma cor após a divisão, que seria entropia zero!
Recapitulação
Informação A Entropia pode ser pensada como o quão imprevisível é um conjunto de dados.
- Um conjunto de apenas uma classe (digamos, azul ) é extremamente previsível: qualquer coisa nele é azul. Isto teria baixa entropia.
- Um conjunto de muitas classes mistas é imprevisível: um dado elemento pode ser de qualquer cor! Isto teria alta entropia.
A fórmula real para calcular a Entropia de Informação é:
E=-∑iCpilog2piE = -\sum_i^C p_i \log_2 p_iE=-i∑Cpilog2pi
O ganho de informação é calculado para uma divisão subtraindo as entropias ponderadas de cada ramo da entropia original. Ao treinar uma árvore de decisão usando essas métricas, a melhor divisão é escolhida maximizando o Ganho de Informação.
Quer saber mais? Confira minha explicação sobre Gini Impureza, uma métrica similar, ou meu guia detalhado Random Forests for Complete Beginners.