Information Gain, come Gini Impurity, è una metrica usata per addestrare gli alberi decisionali. In particolare, queste metriche misurano la qualità di una divisione. Per esempio, diciamo che abbiamo i seguenti dati:
E se facessimo una divisione a x=1,5x = 1,5x=1,5?
Questa divisione imperfetta divide il nostro dataset in questi rami:
- Ramo sinistro, con 4 blu.
- Ramo destro, con 1 blu e 5 verdi.
È chiaro che questa divisione non è ottimale, ma quanto è buona? Come possiamo quantificare la qualità di una divisione?
Ecco dove entra in gioco l’Information Gain.
Confuso? Non sei sicuro di cosa siano gli alberi decisionali o di come vengono addestrati? Leggi l’inizio della mia introduzione a Foreste casuali e Alberi decisionali.
Information Entropy
Prima di arrivare a Information Gain, dobbiamo prima parlare di Information Entropy. Nel contesto dell’addestramento degli alberi decisionali, l’Entropia può essere approssimativamente pensata come quanta varianza hanno i dati. Per esempio:
- Un dataset di soli blu avrebbe un’entropia molto bassa (in effetti, zero).
- Un dataset di dati misti blu, verdi e rossi avrebbe un’entropia relativamente alta.
Ecco come calcoliamo l’Entropia dell’Informazione per un set di dati con classi CCC:
E=-∑iCpilog2piE = -\sum_i^C p_i \log_2 p_iE=-i∑Cpilog2pi
dove pip_ipi è la probabilità di scegliere a caso un elemento della classe iii (cioè la proporzione di elementi del set di dati che non sono stati scelti).Cioè la proporzione del set di dati costituito dalla classe iii).
Il modo più semplice per capire questo è con un esempio. Consideriamo un set di dati con 1 blu, 2 verdi e 3 rossi: . Allora
E=-(pblog2pb+pglog2pg+prlog2pr)E = -(p_b \log_2 p_b + p_g \log_2 p_g + p_r \log_2 p_r)E=-(pblog2pb+pglog2pg+prlog2pr) E=-(16log2(16)+26log2(26)+36log2(36))=1.46\begin{aligned}E &= -(\frac{1}{6} \log_2(\frac{1}{6}) + \frac{2}{6} \log_2(\frac{2}{6}) + \frac{3}{6} \log_2(\frac{3}{6})) \1941>= \boxed{1.46} \\\E=-(61log2(61)+62log2(62)+63log2(63))=1.46
Che dire di un set di dati di un solo colore? Consideriamo 3 blu come esempio: . L’entropia sarebbe
E=-(1log21)=0E = -(1 \log_2 1) = \boxed{0}E=-(1log21)=0
Guadagno di informazioni
E’ finalmente il momento di rispondere alla domanda che abbiamo posto prima: come possiamo quantificare la qualità di una divisione?
Consideriamo ancora questa divisione:
Prima della divisione, avevamo 5 blu e 5 verdi, quindi l’entropia era
Ebefore=-(0.5log20.5+0.5log20.5)=1\begin{aligned}E_{before} &= -(0,5 \log_2 0,5 + 0,5 \log_2 0,5) &= \boxed{1} \\\Ebefore=-(0.5log20.5+0.5log20.5)=1
Dopo la divisione, abbiamo due rami.
Il ramo di sinistra ha 4 blu, quindi Eleft=0E_{left} = \boxed{0}Eleft=0 perché è un dataset di tutti di un colore.
Ramo destro ha 1 blu e 5 verdi, quindi
Eright=-(16log2(16)+56log2(56))=0.65\begin{aligned}E_{right} &= -(\frac{1}{6} \log_2 (\frac{1}{6}) + \frac{5}{6} \log_2 (\frac{5}{6})) \1941>= \boxed{0.65} \\\Ora che abbiamo le entropie per entrambi i rami, possiamo determinare la qualità della divisione pesando l’entropia di ogni ramo per quanti elementi ha. Poiché il ramo sinistro ha 4 elementi e il ramo destro ne ha 6, li ponderiamo rispettivamente per 0,40,40,4 e 0,60,60,6: Esplit=0,4∗0+0,6∗0,65=0,39\begin{aligned}E_{split} &= 0,4 * 0 + 0,6 * 0,65 \&= \boxed{0,39} \\\E_split=0.4∗0+0.6∗0.65=0.39
Siamo partiti con Ebefore=1E_{before} = 1Ebefore=1 entropia prima della divisione e ora siamo scesi a 0.390.390.39! Information Gain = quanta entropia abbiamo rimosso, quindi
Gain=1-0.39=0.61{Gain} = 1 – 0.39 = \boxed{0.61}Gain=1-0.39=0.61
Questo ha senso: più Information Gain = più Entropia rimossa, che è quello che vogliamo. Nel caso perfetto, ogni ramo conterrebbe solo un colore dopo la divisione, che sarebbe zero entropia!
Ricapitolazione
L’entropia dell’informazione può essere pensata come quanto imprevedibile sia un set di dati.
- Un set di una sola classe (diciamo, blu) è estremamente prevedibile: qualsiasi cosa in esso è blu. Questo avrebbe bassa entropia.
- Un insieme di molte classi miste è imprevedibile: un dato elemento potrebbe essere qualsiasi colore! Questo avrebbe un’alta entropia.
La formula attuale per calcolare l’entropia di informazione è:
E=-∑iCpilog2piE = -\sum_i^C p_i \log_2 p_iE=-i∑Cpilog2pi
Il guadagno di informazione è calcolato per una divisione sottraendo le entropie pesate di ogni ramo dall’entropia originale. Quando si addestra un albero di decisione usando queste metriche, la migliore divisione viene scelta massimizzando il guadagno di informazioni.
Vuoi saperne di più? Dai un’occhiata alla mia spiegazione di Gini Impurity, una metrica simile, o alla mia guida approfondita Random Forests for Complete Beginners.