Tutte le sfide
Media 0 risolte 0% di accettazione

Guadagno di informazione

Calcola quanto la divisione secondo una variabile riduce l'entropia, il criterio degli alberi decisionali ID3.

Cosa imparerai

  • Calcolare l'entropia prima e dopo una divisione
  • Pesare i sottoinsiemi in base alla dimensione
  • Scegliere la feature più informativa

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

Esempio 1
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.

Esempio 2
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.

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

Ancora nessuna soluzione superata. Risolvila e prendi il primo posto.

Impara dagli altri

Soluzioni della community

Nessuna soluzione pubblicata. Risolvi questa sfida per condividere la prima.