Todos os desafios
Médio 0 resolvidos 0% de aceitação

Ganho de informação

Calcule quanto a divisão por uma variável reduz a entropia, o critério por trás das árvores de decisão ID3.

O que você vai aprender

  • Calcular a entropia antes e depois de uma divisão
  • Ponderar subconjuntos pelo tamanho
  • Escolher o atributo mais informativo

Problema

Ver original (inglês)

A entropia mede a incerteza de um conjunto de rótulos: H(S) = -Σ pₖ × log₂(pₖ), onde pₖ é a fração de rótulos da classe k. O ganho de informação é quanto a entropia cai ao dividir o conjunto por uma variável:

IG = H(labels) - Σ (|Sᵥ| / |S|) × H(Sᵥ)

onde Sᵥ contém os rótulos dos exemplos cuja variável é v. As árvores de decisão escolhem a variável com o maior ganho.

Implemente information_gain(feature, labels).

Entrada

feature: O valor da variável de cada exemplo.

labels: O rótulo de classe de cada exemplo (mesmo tamanho).

Saída

Retorne o ganho de informação em bits, como número decimal.

Restrições

1 ≤ tamanho ≤ 10.000

Cada valor e rótulo tem de 1 a 20 caracteres

Exemplos

Exemplo 1
Entrada:
feature = ["sunny", "sunny", "rain", "rain"]
labels = ["no", "no", "yes", "yes"]

Saída esperada:
expected = 1.0
Entrada:
std::vector<std::string> feature = {"sunny", "sunny", "rain", "rain"};
std::vector<std::string> labels = {"no", "no", "yes", "yes"};

Saída esperada:
double expected = 1.0;
Entrada:
string[] feature = new string[] {"sunny", "sunny", "rain", "rain"};
string[] labels = new string[] {"no", "no", "yes", "yes"};

Saída esperada:
double expected = 1.0;

Explicação

Os rótulos são metade yes e metade no, então H = 1 bit. Dividir pelo clima dá dois grupos puros (H = 0 cada), então o ganho é 1 - 0 = 1: a variável diz tudo.

Exemplo 2
Entrada:
feature = ["a", "b", "a", "b"]
labels = ["yes", "yes", "no", "no"]

Saída esperada:
expected = 0.0
Entrada:
std::vector<std::string> feature = {"a", "b", "a", "b"};
std::vector<std::string> labels = {"yes", "yes", "no", "no"};

Saída esperada:
double expected = 0.0;
Entrada:
string[] feature = new string[] {"a", "b", "a", "b"};
string[] labels = new string[] {"yes", "yes", "no", "no"};

Saída esperada:
double expected = 0.0;

Explicação

Cada grupo a e b ainda tem um yes e um no (H = 1), então o restante é 0.5 × 1 + 0.5 × 1 = 1 e o ganho é 1 - 1 = 0: a variável é inútil.

Como abordar

Tente sozinho primeiro e depois abra uma dica de cada vez.

Dica 1

Primeiro meça a incerteza dos rótulos antes de qualquer split, depois compare com a incerteza dentro de cada grupo da feature.

Dica 2

Agrupe as amostras pelo valor da feature, conte os rótulos em cada grupo e combine a entropia de cada grupo usando sua fração dos dados.

Dica 3

Cuidado com valores repetidos e com o caso em que um grupo tem só um rótulo, porque a contribuição de entropia é zero.

Complexidade esperada

tempo O(n), espaço extra O(n)

Referências

Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.