Informationsgevinst er ligesom Gini-urhed en måleenhed, der bruges til at træne beslutningstræer. Specifikt måler disse metrikker kvaliteten af en opdeling. Lad os f.eks. sige, at vi har følgende data:
Hvad nu hvis vi lavede en opdeling ved x=1,5x = 1,5x=1,5?
Denne ufuldkomne opdeling opdeler vores datasæt i disse grene:
- Venstre gren, med 4 blues.
- Højre gren, med 1 blå og 5 grønne.
Det er klart, at denne opdeling ikke er optimal, men hvor god er den? Hvordan kan vi kvantificere kvaliteten af en opdeling?
Det er her, informationsgevinsten kommer ind i billedet.
Forvirret? Er du ikke sikker på, hvad beslutningstræer er, eller hvordan de trænes? Læs begyndelsen af min introduktion til Random Forests og Decision Trees.
Informationsentropi
Hvor vi kommer til Informationsgevinst, skal vi først tale om Informationsentropi. I forbindelse med træning af beslutningstræer kan entropi groft sagt opfattes som det omfang af varians, som dataene har. For eksempel:
- Et datasæt bestående udelukkende af blå farver ville have en meget lav (faktisk nul) entropi.
- Et datasæt bestående af blandede blå, grønne og røde farver ville have en relativt høj entropi.
Sådan beregner vi informationsentropi for et datasæt med CCC-klasser:
E=-∑iCpilog2piE = -\sum_i^C p_i \log_2 p_iE=-i∑Cpilog2pi
hvor pip_ipi er sandsynligheden for tilfældigt at vælge et element af klasse iii (i.dvs. andelen af datasættet, der består af klasse iii).
Den nemmeste måde at forstå dette på er med et eksempel. Betragt et datasæt med 1 blå, 2 grønne og 3 røde: . Så
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}{6}))) \\&= \boxed{1.46} \\\end{aligned}E=-(61log2(61)+62log2(62)+63log2(63))=1,46
Hvad med et datasæt med alle én farve? Tag 3 blå farver som et eksempel: . Entropien ville være
E=-(1log21)=0E = -(1 \log_2 1) = \boxed{0}E=-(1log21)=0 Informationsgevinst
Det er endelig tid til at besvare det spørgsmål, vi stillede tidligere: Hvordan kan vi kvantificere kvaliteten af en opdeling?
Lad os betragte dette split igen:
For splitten havde vi 5 blå og 5 grønne, så entropien var
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} \\\end{aligned}Ebefore=-(0.5log20.5+0.5log20.5)=1
Efter opdelingen har vi to grene.
Venstre gren har 4 blå farver, så Eleft=0E_{left} = \boxed{0}Eleft=0, fordi det er et datasæt af alle én farve.
Den højre gren har 1 blå og 5 grønne, så
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}{6}))) \\&= \boxed{0.65} \\\end{aligned}Eright=-(61log2(61)+65log2(65))=0.65
Nu da vi har entropierne for begge grene, kan vi bestemme kvaliteten af opdelingen ved at vægte entropien for hver gren med hvor mange elementer den har. Da venstre gren har 4 elementer og højre gren har 6, vægter vi dem med henholdsvis 0,40,40,4 og 0,60,60,6:
Esplit=0,4∗0∗0+0,6∗0,65=0,39\begin{aligned}E_{split} &= 0,4 * 0 + 0,6 * 0,65 \\&= \boxed{0,39} \\\end{aligned}Esplit=0.4∗0+0.6∗0.65=0.39=0.39
Vi startede med Ebefore=1E_{before} = 1Ebefore=1 entropi før opsplitningen og er nu nede på 0.390.390.39! Informationsgevinst = hvor meget entropi vi har fjernet, så
Gain=1-0.39=0.61\text{Gain} = 1 – 0.39 = \boxed{0.61}Gain=1-0.39=0.61
Dette giver mening: højere informationsgevinst = mere entropi fjernet, hvilket er det, vi ønsker. I det perfekte tilfælde ville hver gren kun indeholde én farve efter opdelingen, hvilket ville være nul entropi!
Recap
Informationsentropi kan opfattes som hvor uforudsigeligt et datasæt er.
- Et sæt med kun én klasse (f.eks. blå ) er ekstremt forudsigeligt: alt i det er blåt. Dette ville have en lav entropi.
- Et sæt med mange blandede klasser er uforudsigeligt: Et givet element kan være af en hvilken som helst farve! Dette ville have høj entropi.
Den egentlige formel for beregning af informationsentropi er:
E=-∑iCpilog2piE = -\sum_i^C p_i \log_2 p_iE=-i∑Cpilog2pi
Informationsgevinsten beregnes for en opdeling ved at trække de vægtede entropier for hver gren fra den oprindelige entropi. Når man træner et beslutningstræ ved hjælp af disse målinger, vælges den bedste opdeling ved at maksimere informationsgevinsten.
Vil du lære mere? Tjek min forklaring af Gini Impurity, en lignende metrik, eller min dybdegående guide Random Forests for Complete Beginners.