Problema
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
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.
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.