Beslutningstrær og ensembles

En modell som stiller ja–nei-spørsmål

En nettbutikk vil forutsi om et besøk ender i kjøp. Et lite regelsett kan spørre «er alderen høyst 30?» og deretter «er antall tidligere besøk høyst 2?». Hvert svar sender observasjonen videre langs én gren til en konklusjon. Et beslutningstre lærer slike regler fra data i stedet for at en utvikler skriver dem for hånd.

En intern beslutningsnode tester vanligvis én feature mot en grense. Selve valget av feature og grense er en split. En terminal bladnode inneholder prediksjonen, for eksempel majoritetsklassen blant treningsobservasjonene som nådde bladet. For regresjon kan bladet i stedet inneholde gjennomsnittet av målverdiene.

For å predikere følger vi én sti fra rot til blad. Metoden trenger derfor normalt ikke standardisering: testen $x_j\le t$ gir samme inndeling hvis featureverdien skaleres lineært og terskelen skaleres tilsvarende. Trær kan fange ikke-lineære sammenhenger og interaksjoner. Ett spørsmål om alder kan få ulik betydning etter et spørsmål om antall besøk.

Denne fleksibiliteten har en pris. Et tre som får vokse til hvert blad inneholder ett eksempel, kan memorere treningsdata. Små endringer i dataene kan gi en annen første split og dermed et helt annet tre. Vi kaller dette høy varians. Begrensninger som maksimal dybde, minste antall observasjoner i bladet eller minste urenhetsreduksjon styrer kompleksiteten og må velges med validering.

Urenhet vurderer kandidatene

Treet trenger et mål for hvor blandet klassene er i en node. urenhet er lav når én klasse dominerer og høy når fordelingen er jevn. ƒgini-urenhet er null i en ren node. I et binært 50–50-blad er den $1-0,5^2-0,5^2=0,5$.

ƒentropi er et alternativ med samme hovedidé. En ren node har entropi null, mens en binær 50–50-node har entropi én bit. Gini og entropi kan rangere noen kandidater ulikt, men begge belønner barn med renere klassefordeling. Valget mellom dem er ofte mindre viktig enn dybde, datakvalitet og antall observasjoner per blad.

En vanlig eksamensoppgave gir klasseantall før og etter en mulig split. Da skal ikke urenhetene i barna bare summeres. Et stort barn må telle mer enn et lite. ƒreduksjon i urenhet trekker vektet barneurenhet fra foreldreurenheten. Den beste kandidaten har størst positiv reduksjon blant de tillatte splittene.

Anta en forelder med fire positive og fire negative. Gini er 0,5. En kandidat gir venstre barn med tre negative og én positiv og høyre barn med tre positive og én negativ. Hvert barn har Gini $1-(3/4{)}^2-(1/4{)}^2=0,375$, så reduksjonen er $0,5-0,5\cdot 0,375-0,5\cdot 0,375=0,125$. Dersom et annet forslag lager ett rent lite barn og ett stort blandet barn, kan den vektede gevinsten være mindre enn det rene barnet antyder.

1import numpy as np2 3X = np.array([1.0, 1.4, 2.1, 2.8, 3.2, 4.0, 4.4, 5.1])4y = np.array([0, 0, 0, 1, 0, 1, 1, 1])5 6def gini(labels):7    if labels.size == 0:8        return 0.09    andeler = np.bincount(labels, minlength=2) / labels.size10    return 1.0 - np.sum(andeler**2)11 12for terskel in (1.75, 2.45, 3.60, 4.70):13    venstre = y[X <= terskel]14    hoyre = y[X > terskel]15    vektet = (venstre.size * gini(venstre) + hoyre.size * gini(hoyre)) / y.size16    print(f"x <= {terskel:.2f}: vektet Gini = {vektet:.3f}")

For numeriske features sorterer algoritmen verdiene og vurderer grenser mellom naboverdier der en relevant endring kan skje. For kategorier må implementasjonen definere hvilke grupperinger som er tillatt. Manglende verdier krever også en eksplisitt strategi. Treet «forstår» ikke kategorien eller årsaken til mangelen; det utnytter bare mønsteret i treningsdata.

Fra ett ustabilt tre til bagging

bagging reduserer varians ved å trene mange modeller på ulike bootstrap-utvalg. Et bootstrap-utvalg trekker like mange rader som originalen *med tilbakelegging*. Noen rader forekommer flere ganger, mens andre ikke trekkes. Hvert tre ser dermed en litt annen versjon av treningsdataene.

Ved klassifikasjon kan ensemblet bruke ƒflertallsstemme. Hvis trestemmene er 1, 1, 0, 1 og 0, blir prediksjonen 1. Ved regresjon brukes ofte gjennomsnitt. Aggregeringen glatter ut tilfeldige utslag: ett tre kan lage en dårlig grense, men mange delvis uavhengige trær gjør sjeldnere samme feil samtidig.

1import numpy as np2 3rng = np.random.default_rng(4172)4n = 105bootstrap = [rng.integers(0, n, size=n) for _ in range(3)]6stemmer = np.array([7    [1, 0, 1, 1, 0],8    [1, 1, 1, 0, 0],9    [0, 1, 1, 1, 0],10])11ensemble = (stemmer.mean(axis=0) >= 0.5).astype(int)12 13for i, utvalg in enumerate(bootstrap, start=1):14    print(f"tre {i}, unike treningsrader:", np.unique(utvalg))15print("stemmer per tre:\n", stemmer)16print("ensemble:       ", ensemble)

Bagging hjelper mest når basismodellene har høy varians og feilene deres ikke er perfekt korrelerte. Hvis alle trær alltid er identiske, gir gjennomsnittet ingen gevinst. Hvis dataene inneholder en systematisk skjevhet som alle modellene lærer, forsvinner den heller ikke av avstemning.

Observasjoner som ikke ble trukket til et bestemt tre, kalles *out-of-bag* for det treet. De kan brukes til en intern ytelsesindikasjon uten en egen valideringsprediksjon fra akkurat dette treet. Dette erstatter ikke alltid et tidsriktig eller eksternt testsett, men utnytter bootstrapmekanismen effektivt.

Random forest dekorellerer trærne

En random forest kombinerer bootstrap med tilfeldige featureutvalg. Ved hver split får treet bare vurdere et utvalg av featurekolonnene. En svært sterk feature kan derfor ikke dominere første split i alle trær. Svakere, men nyttige mønstre får sjansen, og trærnes feil blir mindre like.

To tilfeldigheter må holdes fra hverandre. Bootstrap velger *rader* for hvert tre. Featureutvalget velger *kolonner* for hver split. Flere trær reduserer vanligvis Monte Carlo-variasjonen og overtilpasser ikke på samme måte som større dybde, men de øker minne- og beregningsbruk. Dybde og minste bladstørrelse påvirker fortsatt hvor komplekst hvert enkelt tre er.

Feature importance basert på samlet urenhetsreduksjon kan være praktisk, men er ikke en årsaksforklaring. Metrikken kan favorisere kontinuerlige features eller features med mange mulige splitpunkter. Korrelasjon kan fordele betydning vilkårlig mellom like features. Permutasjonsbasert betydning på hold-out-data svarer på et annet spørsmål: hvor mye faller modellens ytelse når én feature brytes? Også den må tolkes forsiktig når features er korrelerte.

Boosting bygger sekvensielt

gradient boosting bruker også mange små trær, men arbeidsflyten er fundamentalt annerledes. Bagging trener trær uavhengig og kan paralleliseres. Boosting bygger ett tre om gangen for å korrigere den nåværende modellens feilretning. Senere trær avhenger derfor av tidligere trær.

ƒgradient boosting viser oppdateringen. Det nye treet $h_m(x)$ skaleres med læringsraten $\eta$ og legges til ensemblet $F_{m-1}(x)$. En liten læringsrate gjør hvert steg forsiktig og krever gjerne flere trær. En stor læringsrate lærer raskere, men kan overskyte og overtilpasse.

Ved kvadratisk regresjonstap kan det nye treet tilpasses residualene. For generelle differensierbare tap passer gradient boosting et tre til retningen som reduserer tapet, ofte negative gradienter eller beslektede størrelser. Derfor er «hvert tre lærer de feilklassifiserte radene» en nyttig intuisjon, men ikke en full definisjon for alle tap og implementasjoner.

Sentrale hyperparametre virker sammen: antall trær, læringsrate, tredybde, subsampling og regularisering. Flere dype trær med høy læringsrate gir stor kapasitet. Valideringskurver og tidlig stopping kan avslutte når nytten på hold-out-data ikke lenger øker. Testsettet skal fremdeles ikke brukes til dette valget.

Velg modell etter feilmønster og rammer

Ett grunt tre er lett å følge og kan være en god baseline. Ett dypt tre er fleksibelt, men ustabilt. Random forest er robust og krever ofte mindre finjustering, mens gradient boosting kan gi svært sterk tabulær ytelse med mer følsomme hyperparametre. Ingen metode gjør dårlig representerte grupper, feil labels eller tidslekkasje ufarlige.

Når du sammenligner modeller, bruk samme datasplitt, relevante metrikker og et realistisk valideringsopplegg. Mål også inferenstid, modellstørrelse og kalibrering når produktet trenger det. Et ensemble med tusen trær kan være unødvendig hvis et lite tre oppfyller kvalitetskravet og må forklares under strenge tidsgrenser.

Undersøk stabilitet, ikke bare gjennomsnitt. Hvis ulike seeds gir svært forskjellige trær eller feature-betydninger, er forklaringen mindre robust enn én pen visualisering antyder. Sammenlign også trenings- og valideringsytelse når dybden øker. Begge lave tyder på for enkel modell, mens høy trening og svak validering tyder på overtilpasning. For et ensemble kan læringskurver vise om flere observasjoner sannsynligvis vil hjelpe, eller om feilen først og fremst skyldes features, labels eller modellantakelser.

Ved tidsdata må splitten følge kronologien. Et tilfeldig bootstrap-utvalg inne i treningsperioden er ikke i seg selv tidslekkasje, men featureverdier eller valideringsrader fra fremtiden er det. Evaluer på en senere periode når bruken er framtidig. Da tester du både generalisering og om splitreglene tåler at fordelingen flytter seg.

På eksamen bør du kunne regne urenhet, vekte barna, velge split og forklare overtilpasning. Du bør også skille ensemblemekanismene: bagging varierer data og aggregerer uavhengige modeller, random forest varierer i tillegg featurekandidater, og boosting korrigerer sekvensielt. Tegn gjerne flyten. Da blir det tydelig hva som kan paralleliseres, hvor variasjonen oppstår, og hvilke hyperparametre som styrer bias og varians.