Gain d'information

L'entropie mesure l'incertitude d'un ensemble d'étiquettes : H(S) = -Σ pₖ × log₂(pₖ), où pₖ est la proportion d'étiquettes de la classe k. Le gain d'information est la baisse d'entropie obtenue en divisant l'ensemble selon une variable :

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

où Sᵥ contient les étiquettes des exemples dont la variable vaut v. Les arbres de décision choisissent la variable au gain le plus élevé.

Implémentez information_gain(feature, labels).

Entrée

feature : la valeur de la variable pour chaque exemple.

labels : l'étiquette de classe de chaque exemple (même longueur).

Sortie

Renvoyez le gain d'information en bits, sous forme de nombre décimal.

Contraintes

1 ≤ longueur ≤ 10 000

Chaque valeur et étiquette compte de 1 à 20 caractères

Exemples

Entrée :
labels = ["no", "no", "yes", "yes"]
feature = ["sunny", "sunny", "rain", "rain"]

Sortie attendue :
expected = 1.0

Entrée :
std::vector<std::string> labels = {"no", "no", "yes", "yes"};
std::vector<std::string> feature = {"sunny", "sunny", "rain", "rain"};

Sortie attendue :
double expected = 1.0;

Entrée :
string[] labels = new string[] {"no", "no", "yes", "yes"};
string[] feature = new string[] {"sunny", "sunny", "rain", "rain"};

Sortie attendue :
double expected = 1.0;

Entrée :
labels = ["yes", "yes", "no", "no"]
feature = ["a", "b", "a", "b"]

Sortie attendue :
expected = 0.0

Entrée :
std::vector<std::string> labels = {"yes", "yes", "no", "no"};
std::vector<std::string> feature = {"a", "b", "a", "b"};

Sortie attendue :
double expected = 0.0;

Entrée :
string[] labels = new string[] {"yes", "yes", "no", "no"};
string[] feature = new string[] {"a", "b", "a", "b"};

Sortie attendue :
double expected = 0.0;

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

• scikit-learn, Decision trees: mathematical formulation
• Stanford CS229 Machine Learning, lecture notes