Guadagno di informazione

L'entropia misura l'incertezza di un insieme di etichette: H(S) = -Σ pₖ × log₂(pₖ), dove pₖ è la frazione di etichette della classe k. Il guadagno di informazione è quanto diminuisce l'entropia dividendo l'insieme secondo una variabile:

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

dove Sᵥ contiene le etichette degli esempi la cui variabile vale v. Gli alberi decisionali scelgono la variabile con il guadagno più alto.

Implementa information_gain(feature, labels).

Input

feature: Il valore della variabile per ogni esempio.

labels: L'etichetta di classe di ogni esempio (stessa lunghezza).

Output

Restituisci il guadagno di informazione in bit, come numero decimale.

Vincoli

1 ≤ lunghezza ≤ 10.000

Ogni valore ed etichetta ha da 1 a 20 caratteri

Esempi

Input:
labels = ["no", "no", "yes", "yes"]
feature = ["sunny", "sunny", "rain", "rain"]

Output atteso:
expected = 1.0

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

Output atteso:
double expected = 1.0;

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

Output atteso:
double expected = 1.0;

Input:
labels = ["yes", "yes", "no", "no"]
feature = ["a", "b", "a", "b"]

Output atteso:
expected = 0.0

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

Output atteso:
double expected = 0.0;

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

Output atteso:
double expected = 0.0;

Riferimenti

Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.

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