Tous les défis
Moyen 0 résolus 0 % de réussite

Gain d'information

Calculez de combien une division selon une variable réduit l'entropie, le critère des arbres de décision ID3.

Ce que vous allez apprendre

  • Calculer l'entropie avant et après une coupure
  • Pondérer les sous-ensembles selon leur taille
  • Choisir la caractéristique la plus informative

Problème

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

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

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

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

Sortie attendue :
double expected = 1.0;

Explication

Les étiquettes sont pour moitié yes et pour moitié no, donc H = 1 bit. Diviser selon la météo donne deux groupes purs (H = 0 chacun), donc le gain vaut 1 - 0 = 1 : la variable dit tout.

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

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

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

Sortie attendue :
double expected = 0.0;

Explication

Chaque groupe a et b contient encore un yes et un no (H = 1), donc le reste vaut 0.5 × 1 + 0.5 × 1 = 1 et le gain 1 - 1 = 0 : la variable est inutile.

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

Mesure d’abord l’incertitude des labels avant toute séparation, puis compare-la à l’incertitude à l’intérieur de chaque groupe de features.

Indice 2

Regroupe les échantillons par valeur de feature, compte les labels dans chaque groupe, puis combine l’entropie de chaque groupe selon sa part des données.

Indice 3

Attention aux valeurs répétées et au cas où un groupe n’a qu’un seul label, car sa contribution à l’entropie est nulle.

Complexité attendue

temps O(n), espace supplémentaire O(n)

Références

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

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.