Todos os desafios
Fácil 0 resolvidos 0% de aceitação

Impureza de Gini

Meça o quanto os rótulos de um grupo estão misturados, a pontuação que as árvores de decisão usam para escolher divisões.

O que você vai aprender

  • Medir o quanto um grupo de rótulos está misturado
  • Contar as proporções de cada classe
  • Entender como as árvores escolhem divisões

Problema

Ver original (inglês)

Árvores de decisão dividem os dados em grupos o mais puros possível. A impureza de Gini mede o quanto os rótulos de um grupo estão misturados:

Gini = 1 - Σ pₖ²

onde pₖ é a fração de rótulos da classe k. Um grupo com uma só classe tem impureza 0; uma mistura igual de duas classes tem impureza 0.5.

Implemente gini_impurity(labels).

Entrada

labels: Os rótulos de classe do grupo.

Saída

Retorne a impureza de Gini como número decimal.

Restrições

1 ≤ tamanho ≤ 10.000

Cada rótulo tem de 1 a 20 caracteres

Exemplos

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

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

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

Saída esperada:
double expected = 0.5;

Explicação

Metade é yes e metade é no: 1 - (0.5² + 0.5²) = 1 - 0.5 = 0.5, o máximo de mistura para um grupo de duas classes.

Exemplo 2
Entrada:
labels = ["cat", "cat", "cat"]

Saída esperada:
expected = 0.0
Entrada:
std::vector<std::string> labels = {"cat", "cat", "cat"};

Saída esperada:
double expected = 0.0;
Entrada:
string[] labels = new string[] {"cat", "cat", "cat"};

Saída esperada:
double expected = 0.0;

Explicação

Uma só classe: 1 - 1² = 0. O grupo é puro.

Como abordar

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

Dica 1

Conte quantas vezes cada rótulo aparece, porque a impureza depende só da distribuição dos rótulos.

Dica 2

Converta as contagens em frações do grupo inteiro e depois meça o quão longe o grupo está de ser puro.

Dica 3

Um grupo com um único rótulo deve dar zero, enquanto uma mistura equilibrada deve dar um valor maior.

Complexidade esperada

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

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.