Information Gain is, net als Gini Impurity, een metriek die wordt gebruikt om Decision Trees te trainen. In het bijzonder meten deze metrieken de kwaliteit van een splitsing. Stel dat we de volgende gegevens hebben:
Wat als we een splitsing maken bij x=1,5x = 1,5x=1,5?
Deze onvolmaakte splitsing verdeelt onze dataset in de volgende takken:
- Linkertak, met 4 blues.
- Rechtertak, met 1 blauw en 5 groenen.
Het is duidelijk dat deze splitsing niet optimaal is, maar hoe goed is het? Hoe kunnen we de kwaliteit van een splitsing kwantificeren?
Daar komt de informatiewinst om de hoek kijken.
Verbaasd? Weet u niet zeker wat beslisbomen zijn of hoe ze worden getraind? Lees het begin van mijn inleiding tot Random Forests en beslissingsbomen.
Informatie-entropie
Voordat we bij de informatiewinst komen, moeten we het eerst hebben over informatie-entropie. In de context van het trainen van beslissingsbomen, kan Entropie ruwweg worden gezien als hoeveel variantie de gegevens hebben. Bijvoorbeeld:
- Een dataset van alleen maar blauwen zou een zeer lage (in feite nul) entropie hebben.
- Een dataset van gemengde blauwen, groenen en roden zou een relatief hoge entropie hebben.
Hier ziet u hoe we de informatie-entropie berekenen voor een dataset met CCC-klassen:
E=-∑iCpilog2piE = -sum_i^C p_i \log_2 p_iE=-i∑Cpilog2pi
waarbij pip_ipi de waarschijnlijkheid is van het willekeurig kiezen van een element van klasse iii (i.d.w.z. het aandeel van de dataset dat uit klasse iii bestaat).
Het gemakkelijkst te begrijpen is dit met een voorbeeld. Beschouw een dataset met 1 blauw, 2 groenen en 3 roden: . Dan
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.46begin{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})) \\Hoe zit het met een dataset van allemaal één kleur? Neem 3 blauwen als voorbeeld: . De entropie zou E=-(1log21)=0E = -(1 \log_2 1) = \boxed{0}E=-(1log21)=0
Informatiewinst
Het is nu eindelijk tijd om de vraag te beantwoorden die we eerder stelden: hoe kunnen we de kwaliteit van een splitsing kwantificeren?
Laten we deze splitsing nog eens bekijken:
Vóór de splitsing hadden we 5 blauwen en 5 groenen, dus de entropie was
Ebefore=-(0,5log20,5+0,5log20,5)=1E_{before} &= -(0.5 log_2 0.5 + 0.5 log_2 0.5) \&= \boxed{1} \\\Ebefore=-(0.5log20.5+0.5log20.5)=1
Na de splitsing hebben we twee takken.
Linkertak heeft 4 blauwen, dus Eleft=0E_{left} = \boxed{0}Eleft=0 want het is een dataset van allemaal één kleur.
Rechtertak heeft 1 blauw en 5 groenen, dus
Eright=-(16log2(16)+56log2(56))=0.65E_{right} &= -(\frac{1}{6} \log_2 (\frac{1}{6}) + \frac{5}{6} \log_2 (\frac{5}{6})) &= 0,65} \\\Rechts=-(61log2(61)+65log2(65))=0.65
Nu we de entropieën voor beide takken hebben, kunnen we de kwaliteit van de splitsing bepalen door de entropie van elke tak te wegen met het aantal elementen dat hij heeft. Aangezien de linkertak 4 elementen heeft en de rechtertak 6, wegen we ze met respectievelijk 0.40.40.4 en 0.60.60.6:
Esplit=0.4∗0+0.6∗0.65=0.39begin{aligned}E_{split} &= 0.4 * 0 + 0.6 * 0.65 \&= \boxed{0.39} \\\E{split=0,4∗0+0,6∗0,65=0,39
We begonnen met Ebefore=1E_{before} = 1Ebefore=1 entropie voor de splitsing en zitten nu op 0,390.390.39! Information Gain = hoeveel Entropie we verwijderd hebben, dus
Gain=1-0.39=0.61{Gain} = 1 – 0.39 = \boxed{0.61}Gain=1-0.39=0.61
Dit is logisch: hogere Information Gain = meer Entropie verwijderd, en dat is wat we willen. In het perfecte geval zou elke tak slechts één kleur bevatten na de splitsing, wat een entropie van nul zou betekenen!
Recap
Informatie-entropie kan worden gezien als hoe onvoorspelbaar een dataset is.
- Een set van slechts één klasse (zeg, blauw) is extreem voorspelbaar: alles erin is blauw. Dit zou een lage entropie hebben.
- Een verzameling van vele gemengde klassen is onvoorspelbaar: een gegeven element kan elke kleur hebben! Dit zou een hoge entropie hebben.
De eigenlijke formule voor het berekenen van de informatie-entropie is:
E=-∑iCpilog2piE = -sum_i^C p_i \log_2 p_iE=-i∑Cpilog2pi
De informatie-winst wordt voor een splitsing berekend door de gewogen entropieën van elke tak af te trekken van de oorspronkelijke entropie. Bij het trainen van een beslisboom met behulp van deze metriek wordt de beste splitsing gekozen door de informatiewinst te maximaliseren.
Wilt u meer weten? Bekijk mijn uitleg van Gini Onzuiverheid, een vergelijkbare metriek, of mijn diepgaande gids Random Forests voor complete beginners.