Gini-onzuiverheid en informatiewinst

Bij het opbouwen van een beslisboom moeten we bij elk knooppunt kiezen welk kenmerk en welke drempelwaarde de nuttigste splitsing opleveren. Het doel is kindknooppunten te maken waarin de voorbeelden zo zuiver mogelijk zijn — idealiter bevat elk kind slechts één klasse. We hebben een wiskundige maat voor onzuiverheid nodig die aangeeft hoe gemengd de klassen in een knooppunt zijn. Een lagere onzuiverheid is beter: een knooppunt waarvan alle voorbeelden tot dezelfde klasse behoren, heeft een onzuiverheid van nul (perfecte zuiverheid). Twee veelgebruikte maten voor onzuiverheid zijn Gini-onzuiverheid en entropie.

Gini-onzuiverheid meet de kans dat een willekeurig gekozen voorbeeld uit een knooppunt verkeerd zou worden gelabeld als het willekeurig wordt gelabeld volgens de klasseverdeling in dat knooppunt. De formule is: Gini = 1 - sum(p_i^2), waarbij p_i het aandeel van klasse i is. Gini loopt van 0 (zuiver) tot 0,5 (gelijke verdeling over twee klassen). Voor K klassen is het maximum 1 - 1/K. Gini-onzuiverheid is het standaardcriterium in de DecisionTreeClassifier van scikit-learn omdat het computationeel efficiënt is (er zijn geen logaritmen nodig).

Entropie komt uit de informatietheorie: het meet de onzekerheid of informatiewaarde van een verdeling. Formule: H = -sum(p_i * log2(p_i)). Een zuiver knooppunt heeft entropie 0 (geen onzekerheid). Een verdeling van 50/50 heeft entropie 1 (één bit onzekerheid — je hebt één vraag nodig om de klasse te bepalen). Entropie en Gini leveren in de praktijk zeer vergelijkbare bomen op. Entropie is iets trager te berekenen (er is een logaritme nodig), maar kan betere splitsingen opleveren wanneer klasseverdelingen scheef zijn. Gebruik criterion='entropy' in scikit-learn om over te schakelen.

Informatiewinst meet hoeveel een splitsing de onzuiverheid vermindert. Deze wordt berekend als de onzuiverheid van het ouderknooppunt min de gewogen gemiddelde onzuiverheid van de kindknooppunten: IG = impurity(parent) - (N_left/N * impurity(left) + N_right/N * impurity(right)). De beste splitsing maximaliseert de informatiewinst: deze levert kinderen op die zo zuiver mogelijk zijn, gewogen naar hun omvang (zodat grotere kinderen zwaarder meetellen). De boomopbouw evalueert elk kenmerk en elke drempelwaarde en kiest vervolgens de combinatie met de hoogste winst.

Om de beste splitsing te vinden, evalueert het algoritme alle combinaties van kandidaatkenmerken en -drempelwaarden en kiest het de combinatie met de hoogste informatiewinst. Voor een gegevensset met N voorbeelden en d kenmerken evalueert de boom per kenmerk maximaal N-1 drempelwaarden (middelpunten tussen opeenvolgende unieke waarden), wat neerkomt op O(N * d) te evalueren splitsingen per knooppunt. Hier is een vereenvoudigd voorbeeld dat laat zien hoe verschillende drempelwaarden op hetzelfde kenmerk verschillende informatiewinsten opleveren.

Gini-onzuiverheid en entropie leveren meestal vrijwel identieke bomen op. De belangrijkste verschillen zijn subtiel: entropie levert doorgaans meer uitgebalanceerde bomen op (door de logaritme worden onevenwichtige splitsingen zwaarder bestraft), terwijl Gini de meest voorkomende klasse doorgaans in één tak afzondert. Rekenkundig is Gini sneller omdat de berekening van de logaritme wordt vermeden. In de praktijk is de keuze tussen beide een hyperparameter die je moet afstemmen — probeer beide met kruisvalidatie en kies degene die beter presteert op jouw specifieke gegevensset.

Gini-onzuiverheid wordt zonder aanpassingen op natuurlijke wijze uitgebreid naar problemen met meerdere klassen: Gini = 1 - sum(p_i^2) werkt voor elk aantal klassen. Ook de berekening van de informatiewinst blijft ongewijzigd — de gewogen onzuiverheid van de kinderen min de onzuiverheid van de ouder. Bij een probleem met 3 klassen heeft een volkomen zuiver blad (bijvoorbeeld met uitsluitend klasse 2) Gini-waarde 0. Een knooppunt met gelijke aandelen van 3 klassen heeft een maximale Gini-waarde van 2/3. Beslisbomen zijn een van de weinige algoritmen die problemen met meerdere klassen zonder aanpassingen rechtstreeks verwerken — in tegenstelling tot logistische regressie, waarvoor one-vs-rest- of softmax-uitbreidingen nodig zijn.

Binnen scikit-learn slaat de boom bij elk knooppunt de onzuiverheid vóór de splitsing en de onzuiverheid van elk kind op. Het verschil, gewogen naar het aantal voorbeelden, is de onzuiverheidsreductie (informatiewinst). Deze waarde wordt per kenmerk over alle knooppunten opgeteld en genormaliseerd om feature_importances_ te berekenen — de totale onzuiverheidsreductie die aan elk kenmerk wordt toegeschreven. Kenmerken die dicht bij de wortel voorkomen en veel voorbeelden verwerken hebben doorgaans het grootste belang, omdat elke splitsing invloed heeft op een groot deel van de gegevens.

Standaard splitst de boom knopen zolang er enige afname van impuriteit is en de knoop voldoende voorbeelden bevat. De parameter min_impurity_decrease voegt een minimumdrempel toe: er wordt alleen een splitsing gemaakt als die de impuriteit met minstens deze hoeveelheid vermindert. Zo voorkom je dat de boom triviaal kleine splitsingen maakt die ruis uit het hoofd leert. Als je min_impurity_decrease=0.01 instelt, splitst de boom alleen wanneer de informatiewinst groter is dan 0.01. Dit is een nuttig alternatief voor regularisatie door de diepte rechtstreeks te beperken.

Een uitgewerkt voorbeeld dat laat zien hoe de boom het beste kenmerk en de beste drempel kiest. Gegeven twee kenmerken en voor elk één splitsingsdrempel berekent de boom de informatiewinst voor alle opties en kiest hij de beste optie. Dit laat zien waarom bomen van nature impliciete kenmerkselectie uitvoeren: kenmerken die bij geen enkele drempel een hoge informatiewinst opleveren, worden nooit als splitsingskenmerk gekozen en feitelijk genegeerd. Hierdoor zijn beslisbomen robuust voor irrelevante kenmerken, in tegenstelling tot KNN, dat daar wel nadeel van ondervindt.

Wanneer je een beslisboom afstemt met GridSearchCV, kun je de parameter criterion (gini of entropie) opnemen in het parameterrooster, zodat kruisvalidatie de beste optie voor jouw specifieke gegevensverzameling kiest. Combineer dit in dezelfde zoekopdracht met max_depth, min_samples_split en min_samples_leaf. Zoeken over het criterium brengt nauwelijks extra rekenkosten met zich mee — per combinatie zijn er slechts twee extra configuraties — en levert soms een betekenisvolle verbetering op wanneer de klassedistributies sterk scheef zijn of de gegevensverzameling veel splitsingen van vergelijkbare kwaliteit bevat.

In deze les heb je geleerd dat Gini-impuriteit meet hoe gemengd de klassen in een knoop zijn (formule: 1 - som(p_i^2)), dat informatiewinst meet hoeveel een splitsing de impuriteit vermindert (impuriteit van de bovenliggende knoop min de gewogen impuriteit van de onderliggende knopen), en dat de boom altijd de splitsing kiest die de informatiewinst maximaliseert over alle kenmerken en drempels. Hierna bekijken we hoe je de boomdiepte beperkt om overfitting te voorkomen.