Ganho de informação nas árvores de decisão - Information gain in decision trees

Na teoria da informação e no aprendizado de máquina , ganho de informação é sinônimo de divergência de Kullback-Leibler ; a quantidade de informação obtida sobre uma variável aleatória ou sinal da observação de outra variável aleatória. No entanto, no contexto de árvores de decisão, o termo às vezes é usado como sinônimo de informação mútua , que é o valor esperado condicional da divergência de Kullback-Leibler da distribuição de probabilidade univariada de uma variável a partir da distribuição condicional desta variável dada a outra .

O ganho de informação de uma variável aleatória X obtido a partir de uma observação de uma variável aleatória Um valor de tomada é definido ${\ displaystyle A = a}$

{\ displaystyle IG_ {X, A} {(X, a)} = D _ {\ text {KL}} {\ left (P_ {X} {(x | a)} \ | P_ {X} {(x | Eu certo)},}

a divergência de Kullback-Leibler da distribuição anterior de x da distribuição posterior de x dada a .

{\ displaystyle P_ {X} {(x | I)}}

{\ displaystyle P_ {X | A} {(x | a)}}

O valor esperado do ganho de informação é a informação mútua de

x e um - ou seja, a redução da entropia de X conseguida por aprender o estado da variável aleatória Uma .

{\ displaystyle I (X; A)}

Na aprendizagem máquina, este conceito pode ser utilizada para definir uma sequência preferida de atributos para investigar a estreitar para baixo mais rapidamente o estado de X . Essa sequência (que depende do resultado da investigação dos atributos anteriores em cada estágio) é chamada de árvore de decisão e aplicada na área de aprendizado de máquina conhecido como aprendizado de árvore de decisão . Normalmente, um atributo com grande quantidade de informações mútuas deve ser preferido a outros atributos.

Definição geral

Em termos gerais, o ganho de informação esperado é a redução na entropia da informação $Η$ de um estado anterior para um estado que leva algumas informações como fornecidas:

{\ displaystyle IG (T, a) = \ mathrm {H} {(T)} - \ mathrm {H} {(T | a)},}

onde é a

entropia condicional de dado o valor do atributo .

{\ displaystyle \ mathrm {H} {(T | a)}}

{\ displaystyle T}

{\ displaystyle a}

Isso é intuitivamente plausível ao interpretar a entropia $Η$ como uma medida de incerteza de uma variável aleatória : aprendendo (ou assumindo) sobre , nossa incerteza sobre é reduzida (ou seja, é positiva), a menos que, é claro, seja independente de , nesse caso , o significado . ${\ displaystyle T}$ ${\ displaystyle a}$ ${\ displaystyle T}$ ${\ displaystyle T}$ ${\ displaystyle IG (T, a)}$ ${\ displaystyle T}$ ${\ displaystyle a}$ ${\ displaystyle H (T, a) = H (T)}$ ${\ displaystyle IG (T, a) = 0}$

Definição formal

Let denotar um

conjunto de exemplos de treino , cada um sob a forma em que é o valor do atributo ou característica de exemplo e

y

é o rótulo da classe correspondente. O ganho de informação para um atributo é definido em termos de entropia de Shannon como segue. Para um valor obtido por atributo , deixe

{\ displaystyle T}

{\ displaystyle ({\ textbf {x}}, y) = (x_ {1}, x_ {2}, x_ {3}, ..., x_ {k}, y)}

{\ displaystyle x_ {a} \ in vals (a)}

{\ displaystyle a ^ {\ text {th}}}

{\ displaystyle {\ textbf {x}}}

{\ displaystyle a}

{\ displaystyle \ mathrm {H} (-)}

{\ displaystyle v}

{\ displaystyle a}

{\ displaystyle S_ {a} {(v)} = \ {{\ textbf {x}} \ in T | x_ {a} = v \}}

ser definido como o conjunto de entradas de treinamento para as quais o atributo é igual a . Então, o ganho de informação do atributo for é a diferença entre a entropia de Shannon a priori do conjunto de treinamento e a entropia condicional .

{\ displaystyle T}

{\ displaystyle a}

{\ displaystyle v}

{\ displaystyle T}

{\ displaystyle a}

{\ displaystyle \ mathrm {H} (T)}

{\ displaystyle \ mathrm {H} {(T | a)}}

{\ displaystyle \ mathrm {H} (T | a) = \ sum _ {v \ in vals (a)} {{\ frac {| S_ {a} {(v)} |} {| T |}} \ cdot \ mathrm {H} \ left (S_ {a} {\ left (v \ right)} \ right)}.}

{\ displaystyle IG (T, a) = \ mathrm {H} (T) - \ mathrm {H} (T | a)}

A informação mútua é igual à entropia total para um atributo se para cada um dos valores de atributo uma classificação única pode ser feita para o atributo de resultado. Nesse caso, as entropias relativas subtraídas da entropia total são 0. Em particular, os valores definem uma

partição dos dados do conjunto de treinamento em subconjuntos mutuamente exclusivos e inclusivos , induzindo uma distribuição de probabilidade categórica nos valores do atributo . A distribuição é dada . Nesta representação, o ganho de informação de dado pode ser definido como a diferença entre a entropia de Shannon incondicional de e a entropia esperada de condicionado em , onde o valor esperado é tomado em relação à distribuição induzida nos valores de .

{\ displaystyle v \ in vals (a)}

{\ displaystyle T}

{\ textstyle P_ {a} {(v)}}

{\ textstyle v \ in vals (a)}

{\ displaystyle a}

{\ textstyle P_ {a} {(v)}: = {\ frac {| S_ {a} {(v)} |} {| T |}}}

{\ displaystyle T}

{\ displaystyle a}

{\ displaystyle T}

{\ displaystyle T}

{\ displaystyle a}

{\ displaystyle a}

{\ displaystyle {\ begin {alignat} {2} IG (T, a) & = \ mathrm {H} (T) - \ sum _ {v \ in vals (a)} {P_ {a} {(v) } \ mathrm {H} \ left (S_ {a} {(v)} \ right)} \\ & = \ mathrm {H} (T) - \ mathbb {E} _ {P_ {a}} {\ left [\ mathrm {H} {(S_ {a} {(v)})} \ direita]} \\ & = \ mathrm {H} (T) - \ mathrm {H} {(T | a)}. \ fim {alinhado}}}

Desvantagens

Embora o ganho de informação seja geralmente uma boa medida para decidir a relevância de um atributo, ele não é perfeito. Um problema notável ocorre quando o ganho de informação é aplicado a atributos que podem assumir um grande número de valores distintos. Por exemplo, suponha que se esteja construindo uma árvore de decisão para alguns dados que descrevem os clientes de uma empresa. O ganho de informação é frequentemente usado para decidir quais atributos são os mais relevantes, para que possam ser testados perto da raiz da árvore. Um dos atributos de entrada pode ser o número do cartão de crédito do cliente. Este atributo tem uma alta informação mútua, porque identifica exclusivamente cada cliente, mas não queremos incluí-lo na árvore de decisão: decidir como tratar um cliente com base em seu número de cartão de crédito dificilmente será generalizado para clientes que não temos visto antes ( overfitting ).

Para contornar esse problema, Ross Quinlan propôs, em vez disso, escolher o atributo com a maior razão de ganho de informação entre os atributos cujo ganho de informação é médio ou superior. Isso desvia a árvore de decisão contra a consideração de atributos com um grande número de valores distintos, ao mesmo tempo em que não dá uma vantagem injusta aos atributos com valor de informação muito baixo, pois o valor da informação é maior ou igual ao ganho da informação.

Exemplo

Vamos usar essa tabela como um conjunto de dados e usar o ganho de informações para classificar se um paciente está doente com uma doença. Os pacientes classificados como Verdadeiros (T) estão doentes e os pacientes classificados como Falso (F) não estão doentes. No momento, estamos no nó raiz da árvore e devemos considerar todas as divisões possíveis usando os dados.

Conjunto de dados de treinamento
Paciente	Sintoma A	Sintoma B	Sintoma C	Classificação
1	T	T	T	F
2	T	F	T	T
3	F	F	T	T
4	F	T	T	F
5	F	T	F	T

As divisões de candidatos são determinadas observando-se cada variável que constitui um paciente e quais podem ser seus estados. Neste exemplo, todos os sintomas podem ser True (T) ou False (F).

Divisões de candidatos
Dividir	Nós Filhos
1	Sintoma A = T, Sintoma A = F
2	Sintoma B = T, Sintoma B = F
3	Sintoma C = T, Sintoma C = F

Agora, para a divisão # 1, determinamos a entropia antes da divisão, que é encontrada usando a classificação de cada paciente.

${\ displaystyle H (T) = - 3/5 \ log _ {2} (3/5) -2/5 \ log _ {2} (2/5) = 0,971}$

A entropia condicional da divisão # 1 é determinada encontrando a entropia de cada estado do sintoma A e combinando-os.

${\ displaystyle H (T | a) = 2/5 (-1/2 \ log _ {2} (1/2) -1/2 \ log _ {2} (1/2)) + 3/5 ( -2/3 \ log _ {2} (2/3) -1/3 \ log _ {2} (1/3)) = 2/5 (1) +3/5 (0,918) = 0,951}$

O ganho de informação pode então ser determinado encontrando a diferença na entropia anterior e na entropia condicional.

${\ displaystyle IG (T, a) = H (T) -H (T | a) = 0,971-0,951 = 0,02}$

Exemplo de divisão do nó raiz

Essas etapas são repetidas para todas as divisões candidatas para obter seu ganho de informações. Todas as divisões candidatas para um nó usam o mesmo valor para . ${\ displaystyle H (T)}$

Ganhos de informações da divisão do candidato
Dividir	Ganho de informação
1	0,020
2	0,419
3	0,171

A divisão do candidato # 2 tem o maior ganho de informação, portanto, será a divisão mais favorável para o nó raiz. Dependendo da confiança das classificações dos nós filhos, o ganho de informações pode ser aplicado aos nós filhos, mas não pode usar a mesma divisão candidata.