Todos los desafíos
Intermedio 0 resueltos 0% de aceptación

Ganancia de información

Calcula cuánto reduce la entropía dividir por una variable, el criterio de los árboles de decisión ID3.

Lo que aprenderás

  • Calcular la entropía antes y después de dividir
  • Ponderar subconjuntos por su tamaño
  • Elegir la característica más informativa

Problema

Ver original (inglés)

La entropía mide la incertidumbre de un conjunto de etiquetas: H(S) = -Σ pₖ × log₂(pₖ), donde pₖ es la proporción de etiquetas de la clase k. La ganancia de información es cuánto baja la entropía al dividir el conjunto por una variable:

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

donde Sᵥ contiene las etiquetas de los ejemplos cuya variable vale v. Los árboles de decisión eligen la variable con la mayor ganancia.

Implementa information_gain(feature, labels).

Entrada

feature: El valor de la variable de cada ejemplo.

labels: La etiqueta de clase de cada ejemplo (misma longitud).

Salida

Devuelve la ganancia de información en bits, como número decimal.

Restricciones

1 ≤ longitud ≤ 10 000

Cada valor y etiqueta tiene de 1 a 20 caracteres

Ejemplos

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

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

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

Salida esperada:
double expected = 1.0;

Explicación

Las etiquetas son mitad yes y mitad no, así que H = 1 bit. Dividir por el clima da dos grupos puros (H = 0 cada uno), así que la ganancia es 1 - 0 = 1: la variable lo dice todo.

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

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

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

Salida esperada:
double expected = 0.0;

Explicación

Cada grupo a y b sigue teniendo un yes y un no (H = 1), así que el resto es 0.5 × 1 + 0.5 × 1 = 1 y la ganancia es 1 - 1 = 0: la variable no sirve.

Cómo abordarlo

Inténtalo primero por tu cuenta y luego abre las pistas una a una.

Pista 1

Primero mide la incertidumbre de la etiqueta antes de cualquier división y compárala con la incertidumbre dentro de cada grupo de la característica.

Pista 2

Agrupa las muestras por valor de la característica, cuenta las etiquetas en cada grupo y combina la entropía de cada grupo según su proporción de datos.

Pista 3

Cuidado con valores repetidos y con el caso de un grupo con una sola etiqueta, porque su aporte de entropía es cero.

Complejidad esperada

tiempo O(n), espacio extra O(n)

Referencias

Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

Aún no hay soluciones aprobadas. Resuélvelo y quédate el primer puesto.

Aprende de otros

Soluciones de la comunidad

Aún no hay soluciones publicadas. Resuelve este reto para compartir la primera.