Gini-urenhet og informasjonsgevinst

Når vi bygger et beslutningstre, må vi ved hver node velge hvilken egenskap og hvilken terskelverdi som gir den mest nyttige splitten. Målet er å opprette undernoder der observasjonene er så homogene som mulig – ideelt sett inneholder hver undernode bare én klasse. Vi trenger et matematisk mål på urenhet som forteller oss hvor blandede klassene er i en node. Lavere urenhet er bedre: En node der alle observasjonene tilhører samme klasse, har null urenhet (perfekt renhet). To mye brukte mål på urenhet er Gini-urenhet og entropi.

Gini-urenhet måler sannsynligheten for at en tilfeldig valgt observasjon fra en node ville blitt feilklassifisert dersom den ble klassifisert tilfeldig i henhold til klassefordelingen i noden. Formelen er: Gini = 1 - sum(p_i^2), der p_i er andelen av klasse i. Gini varierer fra 0 (ren) til 0,5 (lik fordeling mellom to klasser). For K klasser er maksimumsverdien 1 - 1/K. Gini-urenhet er standardkriteriet i scikit-learn sin DecisionTreeClassifier fordi det er beregningsmessig effektivt (ingen logaritmer).

Entropi er hentet fra informasjonsteorien og måler usikkerheten eller informasjonsinnholdet i en fordeling. Formel: H = -sum(p_i * log2(p_i)). En ren node har entropi 0 (ingen usikkerhet). En 50/50-fordeling har entropi 1 (én bit usikkerhet – du trenger ett spørsmål for å avgjøre klassen). Entropi og Gini produserer svært like trær i praksis. Entropi er litt tregere å beregne (krever logaritme), men kan gi bedre splitter når klassefordelingene er skjeve. Bruk criterion='entropy' i scikit-learn for å bytte.

Informasjonsgevinst måler hvor mye en splitt reduserer urenheten. Den beregnes som urenheten i den overordnede noden minus den vektede gjennomsnittlige urenheten i undernodene: IG = impurity(parent) - (N_left/N * impurity(left) + N_right/N * impurity(right)). Den beste splitten maksimerer informasjonsgevinsten: Den oppretter undernoder som er så rene som mulig, vektet etter størrelsen deres (slik at større undernoder teller mer). Trebyggeren evaluerer informasjonsgevinsten for hver egenskap og hver terskelverdi, og velger deretter kombinasjonen med høyest gevinst.

For å finne den beste splitten evaluerer algoritmen alle kandidatkombinasjoner av egenskaper og terskelverdier, og velger den som gir høyest informasjonsgevinst. For et datasett med N observasjoner og d egenskaper evaluerer treet opptil N-1 terskelverdier per egenskap (midtpunktet mellom påfølgende unike verdier), noe som gir O(N * d) splitter å evaluere per node. Her er et forenklet eksempel som viser hvordan ulike terskelverdier gir ulik informasjonsgevinst for den samme egenskapen.

Gini-urenhet og entropi produserer nesten identiske trær mesteparten av tiden. De viktigste forskjellene er subtile: Entropi har en tendens til å produsere mer balanserte trær (den straffer ubalanserte splitter hardere på grunn av logaritmen), mens Gini har en tendens til å isolere den vanligste klassen i én gren. Beregningsmessig er Gini raskere fordi den unngår beregning av logaritmen. I praksis er valget mellom dem en hyperparameter som bør finjusteres – prøv begge med kryssvalidering, og velg den som fungerer best på Deres spesifikke datasett.

Gini-urenhet utvides naturlig til flerk klasseproblemer uten endringer: Gini = 1 - sum(p_i^2) fungerer for et hvilket som helst antall klasser. Beregningen av informasjonsgevinst er også uendret – vektet urenhet i undernodene minus urenheten i den overordnede noden. I et problem med tre klasser har et perfekt rent blad (for eksempel med bare klasse 2) Gini lik 0. En node med like store andeler av tre klasser har maksimal Gini lik 2/3. Beslutningstrær er blant de få algoritmene som håndterer flerk klasseproblemer direkte uten endringer – i motsetning til logistisk regresjon, som krever utvidelser som én-mot-rest eller softmax.

Internt i scikit-learn lagrer treet urenheten før splitten og urenheten i hver undernode ved hver node. Differansen, vektet etter antall observasjoner, er reduksjonen i urenhet (informasjonsgevinsten). Denne verdien summeres per egenskap på tvers av alle noder og normaliseres for å beregne feature_importances_ – den totale reduksjonen i urenhet som tilskrives hver egenskap. Egenskaper som forekommer nær roten og håndterer mange observasjoner, har en tendens til å få høyest viktighet fordi hver splitt påvirker en stor del av dataene.

Som standard deler treet noder så lenge det finnes en reduksjon i urenhet og noden har nok utvalg. Parameteren min_impurity_decrease legger til en minimumsterskel: en deling opprettes bare hvis den reduserer urenheten med minst dette beløpet. Dette hindrer treet i å opprette trivielt små delinger som memoriserer støy. Hvis min_impurity_decrease=0.01, deler treet bare når informasjonsgevinsten overstiger 0.01. Dette er et nyttig alternativ for regularisering sammenlignet med å kontrollere dybden direkte.

Et gjennomarbeidet eksempel som viser hvordan treet velger den beste egenskapen og terskelen. Med to egenskaper og én delingsterskel for hver beregner treet informasjonsgevinsten for alle alternativene og velger vinneren. Dette illustrerer hvorfor trær naturlig utfører implisitt egenskapsutvelgelse: Egenskaper som aldri gir høy informasjonsgevinst ved noen terskel, blir aldri valgt som deleegenskaper og blir i praksis ignorert. Dette gjør beslutningstrær robuste overfor irrelevante egenskaper, i motsetning til KNN, som påvirkes negativt av dem.

Når De justerer et beslutningstre med GridSearchCV, kan De ta med parameteren criterion (gini eller entropy) i parametergridet, slik at kryssvalideringen kan velge det beste alternativet for datasettet Deres. Kombiner dette med max_depth, min_samples_split og min_samples_leaf i det samme søket. Det å søke over criterion gir minimale ekstra beregningskostnader – bare to ekstra konfigurasjoner per kombinasjon – og kan av og til gi en merkbar forbedring når klassefordelingene er svært skjeve eller datasettet har mange delinger med omtrent samme kvalitet.

I denne leksjonen lærte De at Gini-urenhet måler hvor blandede klassene er i en node (formel: 1 - sum(p_i^2)), at informasjonsgevinst måler hvor mye en deling reduserer urenheten (urenheten i foreldrenoden minus den vektede urenheten i barnenodene), og at treet alltid velger delingen som maksimerer informasjonsgevinsten på tvers av alle egenskaper og terskler. Deretter skal vi se på hvordan treets dybde kan begrenses for å forhindre overtilpasning.