Beslutningstreregresjon fra bunnen av: Teori og praksis

Home » Python » Beslutningstreregresjon fra bunnen av: Teori og praksis

Beslutningstre-regresjon fra bunnen av er en av de mest øyeåpnende øvelsene du kan gjøre hvis du virkelig vil forstå hvordan trebaserte modeller tenker og hvorfor de er så populære innen maskinlæring. I stedet for å behandle treet som en mystisk svart boks, vil du se hvordan hver deling velges, hvordan urenhet måles og hvordan numeriske prediksjoner produseres ved bladene, både for regresjons- og klassifiseringsproblemer.

I denne veiledningen skal vi gå gjennom kjerneideene bak beslutningstrær, kostnadsfunksjonene de bruker, hvordan de søker etter de beste delingene, og hvordan man koder et grunnleggende tre som støtter både regresjon og klassifisering, ved kun å bruke grunnleggende konsepter som løkker, betingelser og enkel statistikk. Underveis vil vi sammenligne regresjons- vs. klassifiseringstrær, koble teorien til praktiske implementeringer i verktøy som Python og R (for eksempel med rpart og tree), og kort plassere beslutningstrær i større ensembler som tilfeldige skoger.

Hva er et beslutningstre, og hvorfor er det så intuitivt?

Et beslutningstre er i hovedsak en flyt av ja/nei-spørsmål (eller enkle regler) som veileder deg fra en rotbeslutning ned til en endelig prediksjon i en bladnode. I en typisk veiledet læringssituasjon er målet å forutsi en målvariabel Y ved hjelp av flere prediktorer (funksjoner, kovariater), og treet lærer en sekvens av spørsmål som «er vekt ≤ 103?» eller «er landet i {USA, Storbritannia, CA}?» som gradvis deler dataene inn i mer homogene grupper.

For å få litt intuisjon, tenk deg at du vil forutsi om noen er overvektig ved kun å bruke høyde og vekt, og du har et merket datasett som forteller deg hvem som er overvektig og hvem som ikke er det. Et tre kan oppdage en regel som «hvis vekt > 100 kg, forutsi fedme», men den regelen vil ikke være perfekt: noen personer over 100 kg vil ikke være fedme, og noen under denne terskelen vil være det. Treet fortsetter deretter å legge til flere spørsmål (underoppdelinger), for eksempel om høyde eller en raffinert vektterskel, for å «finjustere» de første grove forutsigelsene.

Hver interne node i treet tilsvarer en beslutningsregel, hver gren tilsvarer ett utfall av den regelen, og hver bladnode tilsvarer et område av funksjonsrommet der prediksjonene er konstante. I klassifisering returnerer et blad en klasseetikett (eller sannsynlighetsfordeling over etiketter); i regresjon returnerer et blad vanligvis gjennomsnittet av målverdiene som faller innenfor det området.

En av hovedstyrkene til beslutningstrær er at de håndterer både regresjon og klassifisering naturlig, de er enkle å tolke, og de fungerer med både kvantitative og kvalitative (kategoriske) prediktorer uten behov for tung forbehandling. Du trenger ikke å anta noen spesifikk fordeling for funksjonene eller målet ditt, noe som gjør trær svært attraktive i virkelige scenarier der klassiske lineære antagelser ofte brytes.

Klassifisering vs. regresjonstrær

Selv om strukturen til klassifiserings- og regresjonstrær er den samme, er naturen til responsvariabelen Y og kostnadsfunksjonen som brukes til oppdeling forskjellig mellom disse to typene. Når Y er kvantitativ (for eksempel salg, forventet levealder, drivstofforbruk), snakker vi om et regresjonstre; når Y er kvalitativ eller kategorisk (for eksempel overlevd vs. ikke overlevd, overvektig vs. ikke overvektig), snakker vi om et klassifiseringstre.

I et regresjonstre er det vanlige målet å dele opp funksjonsrommet i områder der responsen kan tilnærmes med en konstant, ofte gjennomsnittet av observasjonene i det området. Typiske beslutningsregler har formen «er x»_k ≤ c?”, hvor x_k er en av kovariatene og c er en terskel; disse reglene deler rommet gjentatte ganger inn i hyperrektangler, og alle punkter i samme hyperrektangel deler samme predikerte verdi ŷ.

I et klassifiseringstre er delingene fortsatt «funksjon ≤ terskel?» eller «kategori i sett S?», men kvaliteten på en deling måles etter hvor rene de resulterende barnnodene er når det gjelder klasseetiketter. Bladprediksjonen er vanligvis majoritetsklassen inne i den noden, og modellen prøver å lage blader som er så nærme som mulig å inneholde bare én enkelt klasse.

Til tross for disse forskjellene i måltypen, kan du fra et kodeperspektiv implementere en enkelt generisk trestruktur og ganske enkelt plugge inn forskjellige urenhets- eller tapsmål avhengig av om du bruker regresjon eller klassifisering. Senere, når vi beregner informasjonsforsterkning, vil du se at formlene for klassifisering (basert på entropi) og regresjon (basert på varians) er parallelle i ånden.

Urenhets- og kostnadsfunksjoner i beslutningstrær

I kjernen av enhver beslutningstrealgoritme ligger en kostnadsfunksjon som evaluerer hvor god en bestemt deling er til å separere dataene i meningsfulle grupper. Denne kostnadsfunksjonen uttrykkes i form av urenhet: en node anses som ren hvis alle dens prøver tilhører samme klasse (for klassifisering) eller har nesten samme numeriske verdi (for regresjon).

Når du velger en kandidatdeling på en funksjon, ser algoritmen på barnnodene den produserer og spør: «hvor blandede er etikettene (eller verdiene) i hvert barn?» En god deling er en som produserer undernoder som er mye mindre urene enn foreldrenoden, noe som betyr at dataene i hvert undernode er mer homogene med hensyn til målet.

I klassifiseringstrær måles urenhet vanligvis ved hjelp av kriterier som Gini-indeksen eller entropi, som begge fanger opp hvor sannsynlig det er at en tilfeldig valgt observasjon i den noden ville bli feilklassifisert hvis vi bare forutså majoritetsklassen. I regresjonstrær måles urenhet vanligvis med kvadratisk feil eller varians, som gjenspeiler hvor spredt målverdiene er innenfor noden.

Gini-indeks: måling av urenhet i klassifiseringstrær

Gini-indeksen er et av de mest brukte urenhetsmålene for klassifiseringstrær fordi den er enkel å beregne og fungerer bra i praksis. Konseptuelt måler den sannsynligheten for at en tilfeldig valgt observasjon fra noden ville bli feilklassifisert dersom etiketten ble forutsagt i henhold til etikettfordelingen i den noden.

Hvis en node inneholder klasser med sannsynligheter P₁, P₂, …, P_n, Gini-indeksen beregnes som Gini = 1 − Σ (P_i)². Når en node er helt ren (alle observasjoner tilhører samme klasse), er én av sannsynlighetene 1 og resten er 0, så summen av kvadratene er 1 og Gini-indeksen er 0, noe som indikerer full renhet.

På den annen side når Gini-indeksen sitt maksimum når klasser er jevnt blandet inne i noden, for eksempel i et binært problem med P₁ = P₂ = 0.5, som gir Gini = 1 − (0.5² + 0.5²) = 0.5. I den situasjonen er det så ille som det kan bli å forutsi majoritetsklassen for den fordelingen fordi noden inneholder halvparten av hver klasse.

Når du implementerer Gini i kode, tar du vanligvis labelvektoren for noden, beregner frekvensen til hver klasse, konverterer frekvenser til sannsynligheter og bruker deretter formelen 1 − Σ p². Hvis du gjør dette for flere kandidatdelinger, kan du sammenligne hvilken deling som gir barn med lavere vektet gjennomsnittlig Gini-urenhet, som er akkurat det treet trenger for å bestemme seg for den beste partisjonen.

Entropi: et annet syn på klassifiseringsurhet

Entropi er et alternativt urenhetsmål som er mye brukt i informasjonsteori og i tidlige trealgoritmer som ID3 og C4.5, og det fanger opp mengden tilfeldighet eller usikkerhet i nodens klassefordeling. Mens Gini fokuserer på sannsynlighet for feilklassifisering, kvantifiserer entropi «overraskelsen» forbundet med å observere en bestemt klasse når fordelingen er blandet.

Gitt klassesannsynligheter p₁, …, s._c For en node S er entropien definert som E(S) = − Σ p_i log₂(p_i). Hvis noden er ren, er én av sannsynlighetene 1 og alle andre er 0, noe som gjør summen til null (fordi log₂(1) = 0), så entropien er 0, noe som indikerer ingen usikkerhet.

Når noden inneholder en jevn fordeling av klasser, maksimeres entropien; for et binært problem med p₁ = s₂ = 0.5, er entropien 1 bit, som er den høyeste mulige verdien for to klasser. Denne verdien tilsvarer maksimal usikkerhet, noe som betyr at noden er så uren som den kan være under den fordelingen.

Selv om Gini og entropi bruker forskjellige formler og har forskjellige numeriske områder (Gini mellom 0 og 0.5 for to klasser, entropi mellom 0 og 1), måler begge i hovedsak det samme konseptet, så de fører vanligvis til veldig like trær i praksis. Når du beregner begge på samme node, vil du oppdage at høy Gini tilsvarer høy entropi og omvendt, og det er derfor mange biblioteker lar deg velge en av dem uten å endre ytelsen drastisk.

Informasjonsinnhenting og valg av de beste splittene

For å velge den beste fordelingen blant mange kandidater, bruker trealgoritmen en beregning kalt informasjonsforsterkning, som måler hvor mye urenhet reduseres når vi deler en node inn i dens barn. Intuitivt sett har en deling høy informasjonsforsterkning hvis barna er mye renere enn forelderen, noe som betyr at regelen klarte å separere dataene i mer meningsfulle grupper.

For klassifiseringstrær som bruker entropi, er informasjonsforsterkningen for en splitt definert som IG_{klassifisering} = E(forelder) − Σ (|S_barn| / |S_forelder|) · E(S_barn). Du beregner først entropien til foreldrenoden, deretter trekker du fra den vektede gjennomsnittlige entropien til barnnodene, der vektene er deres relative størrelser.

For regresjonstrær bruker et analogt konsept varians eller gjennomsnittlig kvadratfeil som urenhetsmål, noe som gir IG_regresjon = Var(forelder) − Σ (|S_barn| / |S_forelder|) · Var(S_barn). I denne settingen er en god oppdeling en som reduserer variasjonen i målverdiene innenfor hvert barn betraktelig.

Treningsalgoritmen for trærne evaluerer denne informasjonsforsterkningen for hver mulige kandidatdeling på hver funksjon, og velger deretter delingen med høyest forsterkning, forutsatt at den overstiger en viss minimumsterskel for å unngå å skape unyttige, små forbedringer. Denne prosessen gjentas deretter rekursivt på hver barnnode inntil noen stoppkriterier er nådd.

Slik søker du etter den beste fordelingen på hver funksjon

Å finne den beste oppdelingen på en enkelt funksjon avhenger av om funksjonen er numerisk eller kategorisk, men den underliggende ideen er alltid den samme: opplist kandidatpartisjoner og beregn informasjonsforsterkningen deres. For numeriske funksjoner er en partisjon definert av en terskel; for kategoriske funksjoner er den definert ved å gruppere nivåer i delsett.

For en numerisk prediktor er den vanlige strategien å se på alle unike verdier som funksjonen tar i den gjeldende noden, sortere dem og deretter vurdere kandidatterskler mellom påfølgende verdier. For hver kandidatterskel c oppretter du to grupper (x ≤ c og x > c), beregner urenheten til hver gruppe, og beregner deretter informasjonsforsterkningen; terskelen som gir den høyeste forsterkningen er din beste numeriske fordeling på den funksjonen.

Når man har å gjøre med kategoriske prediktorer, er søkerommet mer komplekst fordi i prinsippet kan ethvert delsett av kategorier danne den ene siden av delingen, med komplementet på den andre siden. I en funksjon med K kategorier finnes det mange mulige delmengder (2^K−1 − 1 ikke-trivielle partisjoner), så i praksis begrenser implementeringer ofte dette søket eller bruker heuristikker, spesielt når K er stor.

Når du har beregnet den beste fordelinga for hver funksjon, samanliknar du informasjonsgevinstane deira og veljer funksjonen og terskelen (eller kategoridelsettet) som tilsvarer den maksimale forsterkningen. Denne valgte delingen blir avgjørelsen ved den gjeldende noden, og treningsprosessen gjentas deretter på hvert barn med det tilsvarende delsettet av observasjoner.

Kontrollere trevekst med hyperparametere

Hvis du lar et beslutningstre vokse uten noen begrensninger, vil det fortsette å dele seg til hvert blad enten er helt rent eller inneholder svært få observasjoner, noe som nesten alltid fører til alvorlig overtilpasning (overtilpasning vs. undertilpasning). For å unngå dette, angir du en samling hyperparametere som kontrollerer dybden og kompleksiteten til treet.

En vanlig hyperparameter er max_depth, som setter en grense for det maksimale antallet nivåer treet kan vokse fra roten til et hvilket som helst blad. Hvis max_depth er satt til None (eller et veldig stort tall), kan treet fortsette å vokse så lenge andre begrensninger er oppfylt. Hvis det er lite, forblir treet grunt og mer tolkbart, men det kan være undertilpasset.

En annen viktig hyperparameter er min_samples_split, som spesifiserer minimumsantallet observasjoner en node må inneholde før den kan deles. Hvis en node har færre prøver enn denne terskelen, blir den omgjort til et blad, noe som forhindrer modellen i å jage støy i svært små delsett av data.

Du kan også håndheve en minimumsinformasjonsforsterkning (min_information_gain) slik at algoritmen bare utfører en deling hvis den gir en meningsfull forbedring i reduksjonen av urenheter. Dette unngår å lage unødvendige grener som knapt endrer prediksjonene og bare kompliserer trestrukturen.

Bygge et beslutningstre fra bunnen av i kode

Å implementere et beslutningstre fra bunnen av dreier seg vanligvis om et lite sett med kjernefunksjoner som kalles rekursivt. Selv om biblioteker som scikit-learn eller rpart gjør alt dette under panseret, gjør det logikken mye tydeligere å kode disse trinnene selv (programmeringslogikk) og gir deg full kontroll over oppførselen.

Først trenger du en rutine som, gitt de nåværende dataene ved en node, evaluerer hver funksjon og hver kandidatdeling for å finne den med høyest informasjonsøkning. Denne funksjonen returnerer den valgte funksjonen, delingsregelen (terskel eller delmengde av kategorier), forsterkningsverdien og den boolske masken eller indekssettene som identifiserer hvilke prøver som skal til venstre og hvilke som skal til høyre.

For det andre trenger du en prediksjonsfunksjon for bladnoder som konverterer settet med målverdier i den noden til én enkelt prediksjon. For regresjon er dette vanligvis gjennomsnittet av y i den noden; for klassifisering bruker du vanligvis modusen (hyppigste klasse), og lagrer muligens også klassesannsynligheter hvis du vil ha sannsynlighetsutganger.

For det tredje oppretter du en rekursiv treningsfunksjon som sjekker stoppkriterier, søker etter den beste delingen hvis tillatt, og deretter bygger underordnede noder ved å kalle seg selv på venstre og høyre delmengde. Hvis betingelsene for minimum utvalgsstørrelse, maksimal dybde eller minimum forsterkning ikke er oppfylt, stopper funksjonen delingen og lagrer en bladprediksjon i stedet for ytterligere grener.

Hvordan prediksjon fungerer i et trent beslutningstre

Når treet ditt er trent og du har lagret alle delingsreglene og bladprediksjonene, er det bare å gå nedover treet fra roten til bladet å lage en prediksjon for en ny observasjon. Ved hver interne node inspiserer du den nødvendige funksjonen og tester om observasjonen tilfredsstiller nodens betingelse.

Hvis delingsregelen er numerisk, sjekker du om funksjonsverdien er mindre enn eller lik terskelen. Hvis delingsregelen er kategorisk, sjekker du om kategorien er i et bestemt delsett. Avhengig av resultatet følger du den aktuelle grenen (for eksempel «ja» til venstre, «nei» til høyre) og gjentar denne prosessen ved neste node.

Du fortsetter å gå nedover treet til du kommer til en node uten barn, som er et blad som lagrer en konstant utgangsverdi eller en klasseetikett. For et regresjonstre vil prediksjonen være et tall som en estimert forventet levetid eller drivstoffeffektivitet; for et klassifiseringstre vil utdataene være en predikert kategori som «overlevde» eller «overlevde ikke».

Hvis du tester denne tilnærmingen på de samme dataene du brukte til trening, vil du ofte se ganske høy nøyaktighet for klassifisering (for eksempel rundt 85 % i noen enkle eksempler på fedme eller Titanic-lignende data), men ytelsen kan synke på usynlige data hvis treet ditt er for dypt. Det er nettopp derfor det er så viktig å kontrollere tredybde og -størrelse, og hvorfor ensembler som tilfeldige skoger ble oppfunnet for å stabilisere trespådommer.

Arbeid med regresjonstrær i praksis

Regresjonstrær er spesielt nyttige når forholdet mellom prediktorer og responsen er sterkt ikke-lineært og involverer interaksjoner som er vanskelige å modellere med klassisk lineær regresjon. I stedet for å prøve å tilpasse en enkelt global ligning, deler treet funksjonsrommet inn i regioner og tilpasser en enkel konstant modell innenfor hver region.

I R gjør populære pakker som rpart og tree det enkelt å bygge regresjonstrær med et enkelt funksjonskall, og spesifiserer en formel som y ~ x1 + x2 + … + x11. Disse pakkene ble påvirket av den opprinnelige CART-metodikken beskrevet av Breiman og kolleger, og de implementerer mange av delings- og beskjæringsideene som er standard i moderne trebasert modellering.

Du kan for eksempel bruke rpart-pakken til å modellere et svar y basert på elleve kovariater x1 til x11, rense dataene for manglende verdier og deretter visualisere det resulterende treet med hjelpefunksjoner som prp fra rpart.plot-pakken. Terminalnodene viser den predikerte y-verdien for hvert område, som du kan bruke direkte til nye observasjoner.

Gitt et trent regresjonstre, kan du mate inn nye kovariate verdier som x9 = 70, x2 = 100 eller x9 = 60, x2 = 150 i prediksjonsfunksjonen for å få estimerte verdier ŷ (for eksempel rundt 20 eller 28 i et eksempel på drivstofforbruk). Å sammenligne disse prediksjonene mot observerte verdier, for eksempel gjennom korrelasjon mellom y og ŷ, gir deg en rask følelse av hvor godt treet fanger opp det underliggende mønsteret, selv når datasettet er ganske lite.

Fra enkeltstående trær til tilfeldige skoger

Et enkelt beslutningstre er kraftig, men også notorisk følsomt for særegenhetene ved treningsdataene, noe som kan føre til høy varians (skjevhet og varians) og overtilpasning. For å redusere dette bygger tilfeldige skoger mange trær på bootstrappede datautvalg og aggregerer prediksjonene sine, noe som produserer en mer stabil og vanligvis mer nøyaktig modell.

I en tilfeldig skog trent hvert tre på et bootstrap-utvalg, som betyr at et nytt datasett av samme størrelse hentes fra det opprinnelige treningssettet med erstatning. Denne samplingsprosessen gjør at hvert tre ser et litt forskjellig datasett, slik at feilene deres er mindre korrelerte og kan kansellere ut når de aggregeres.

I tillegg introduserer tilfeldige skoger tilfeldighet i funksjonsutvelgelsesprosessen ved å bare vurdere et tilfeldig delsett av prediktorer ved hver deling i stedet for alle prediktorer. Dette reduserer korrelasjonen mellom trær ytterligere, forbedrer mangfoldet i skogen og har en tendens til å redusere variansen uten å øke skjevheten for mye.

Kombinasjonen av bootstrapping og aggregering av prediksjoner er kjent som bagging, og i tilfeldige skoger får du også et internt estimat av modellfeil ved å evaluere hvert tre på datapunktene som ikke var inkludert i bootstrap-utvalget (de såkalte out-of-bag-observasjonene). Denne feilen «out-of-sec» gir en praktisk måte å måle ytelsen på uten behov for et separat valideringssett.

Selv om denne artikkelen fokuserer på å bygge et enkelt tre fra bunnen av, gjør det mye enklere å forstå hvordan ensembler som tilfeldige skoger, gradientforsterkning og andre trebaserte metoder bygger på de samme prinsippene for å oppnå toppmoderne resultater i mange anvendte problemer å forstå hvordan denne grunnleggende komponenten fungerer.

Ved å sette alt sammen, viser beslutningstreregresjon fra bunnen av deg hvordan et enkelt sett med regler, kostnadsfunksjoner og rekursive splittelser kan modellere komplekse sammenhenger, enten du forutsier et binært utfall som overlevelse, en kategorisk etikett som fedmestatus eller et numerisk mål som forventet levealder eller drivstofforbruk, og denne dype forståelsen blir et solid grunnlag for bruk av mer avanserte trebaserte teknikker i praksis.