Problema
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:
feature = ["sunny", "sunny", "rain", "rain"]
labels = ["no", "no", "yes", "yes"]
Output atteso:
expected = 1.0
Input:
std::vector<std::string> feature = {"sunny", "sunny", "rain", "rain"};
std::vector<std::string> labels = {"no", "no", "yes", "yes"};
Output atteso:
double expected = 1.0;
Input:
string[] feature = new string[] {"sunny", "sunny", "rain", "rain"};
string[] labels = new string[] {"no", "no", "yes", "yes"};
Output atteso:
double expected = 1.0;
Spiegazione
Le etichette sono metà yes e metà no, quindi H = 1 bit. Dividere secondo il meteo dà due gruppi puri (H = 0 ciascuno), quindi il guadagno è 1 - 0 = 1: la variabile dice tutto.
Input:
feature = ["a", "b", "a", "b"]
labels = ["yes", "yes", "no", "no"]
Output atteso:
expected = 0.0
Input:
std::vector<std::string> feature = {"a", "b", "a", "b"};
std::vector<std::string> labels = {"yes", "yes", "no", "no"};
Output atteso:
double expected = 0.0;
Input:
string[] feature = new string[] {"a", "b", "a", "b"};
string[] labels = new string[] {"yes", "yes", "no", "no"};
Output atteso:
double expected = 0.0;
Spiegazione
Ogni gruppo a e b contiene ancora un yes e un no (H = 1), quindi il resto è 0.5 × 1 + 0.5 × 1 = 1 e il guadagno è 1 - 1 = 0: la variabile è inutile.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Misura prima l'incertezza delle label prima di qualsiasi split, poi confrontala con l'incertezza dentro ogni gruppo di feature.
Suggerimento 2
Raggruppa i campioni per valore della feature, conta le label in ogni gruppo e combina l'entropia di ciascun gruppo usando la sua quota dei dati.
Suggerimento 3
Fai attenzione ai valori ripetuti e al caso in cui un gruppo abbia una sola label, perché il suo contributo all'entropia è zero.
Complessità attesa
tempo O(n), spazio aggiuntivo O(n)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.