Hva er et beslutningstre?

Hva er et beslutningstre?

Et beslutningstre er et nyttig maskinlæring-algoritme som brukes til både regresjon og klassifisering oppgaver. Navnet “beslutningstre” kommer fra faktum at algoritmen deler datasett ned i mindre og mindre deler til dataene er delt inn i enkelt eksempler, som deretter klassifiseres. Hvis du skulle visualisere resultater av algoritmen, ville måten kategorier er delt på ligne et tre med mange blader.

Dette er en kort definisjon av et beslutningstre, men la oss dykke dyptere inn i hvordan beslutningstre fungerer. Å ha en bedre forståelse av hvordan beslutningstre opererer, samt deres bruksområder, vil hjelpe deg med å vite når du skal bruke dem i dine maskinlæring prosjekter.

Format for et beslutningstre

Et beslutningstre er mye likt en flytskjema. For å bruke et flytskjema starter du på startpunktet, eller roten, av skjemaet og deretter, basert på hvordan du svarer på filterkriteriene for den start noden, flytter du til en av de neste mulige nodene. Denne prosessen gjentas til en slutt er nådd.

Beslutningstre opererer på samme måte, med hver intern node i treet som noen form for test/filterkriterie. Nodene på utsiden, endepunktene av treet, er labelene for datapunktet i question og de kalles “blader”. Greinene som fører fra de interne nodene til den neste noden er trekk eller kombinasjoner av trekk. Reglene som brukes til å klassifisere datapunktene er stiene som løper fra roten til bladene.

Algoritmer for beslutningstre

Beslutningstre opererer på en algoritmsk tilnærming som deler datasett opp i enkelt data punkter basert på forskjellige kriterier. Disse delingene gjøres med forskjellige variabler, eller de forskjellige trekkene av datasett. For eksempel, hvis målet er å bestemme om det er en hund eller en katt som beskrives av inndata trekkene, kan variablene dataene deles på være ting som “klør” og “bjeffer”.

Så hva algoritmer brukes til å faktisk dele dataene inn i greiner og blader? Det finnes flere metoder som kan brukes til å dele et tre opp, men den vanligste metoden for deling er kanskje en teknikk kjent som “rekursiv binær deling”. Når denne metoden for deling utføres, starter prosessen ved roten og antallet trekk i datasett representerer det mulige antallet mulige delinger. En funksjon brukes til å bestemme hvor mye nøyaktighet hver mulig deling vil koste, og delingen gjøres ved hjelp av kriteriet som ofrer minst nøyaktighet. Denne prosessen utføres rekursivt og undergrupper dannes ved hjelp av samme generelle strategi.

For å bestemme kostnaden av delingen, brukes en kostnadsfunksjon. En annen kostnadsfunksjon brukes for regresjon oppgaver og klassifisering oppgaver. Målet med begge kostnadsfunksjoner er å bestemme hvilke greiner som har de mest like svarverdier, eller de mest homogene greinene. Overvei at du ønsker testdata av en bestemt klasse å følge bestemte stier og dette har intuitivt mening.

I forhold til regresjon kostnadsfunksjonen for rekursiv binær deling, er algoritmen som brukes til å beregne kostnaden som følger:

sum(y – prediksjon)^2

Prediksjonen for en bestemt gruppe data punkter er gjennomsnittet av svarene til trening dataene for den gruppen. Alle data punktene kjøres gjennom kostnadsfunksjonen for å bestemme kostnaden for alle mulige delinger og delingen med den laveste kostnaden velges.

Med hensyn til kostnadsfunksjonen for klassifisering, er funksjonen som følger:

G = sum(pk * (1 – pk))

Dette er Gini-scoren, og det er et mål på effektiviteten av en deling, basert på hvor mange eksempler av forskjellige klasser som er i gruppene som resulterer fra delingen. Med andre ord, det kvantifiserer hvor blandet gruppene er etter delingen. En optimal deling er når alle gruppene som resulterer fra delingen består bare av inndata fra en klasse. Hvis en optimal deling er opprettet, vil “pk”-verdien være enten 0 eller 1 og G vil være lik 0. Du kan kanskje gjette at den verste delingen er en der det er en 50-50 representasjon av klassene i delingen, i tilfelle binær klassifisering. I dette tilfellet vil “pk”-verdien være 0,5 og G vil også være 0,5.

Delingsprosessen avsluttes når alle data punktene er omdannet til blader og klassifisert. Imidlertid kan du ønske å stoppe veksten av treet tidlig. Store komplekse tre er utsatt for overfitting, men flere forskjellige metoder kan brukes til å bekjempe dette. En metode for å redusere overfitting er å angi et minimum antall data punkter som vil brukes til å opprette et blad. En annen metode for å kontrollere overfitting er å begrense treet til en bestemt maksimal dybde, som kontrollerer hvor lang en sti kan strekke seg fra roten til et blad.

En annen prosess som er involvert i opprettelsen av beslutningstre er beskjæring. Beskjæring kan hjelpe med å øke ytelsen av et beslutningstre ved å fjerne greiner som inneholder trekk som har liten prediktiv kraft/liten viktighet for modellen. På denne måten reduseres kompleksiteten av treet, det blir mindre sannsynlig å overfitte, og den prediktive nytten av modellen øker.

Når beskjæring utføres, kan prosessen starte enten fra toppen av treet eller bunnen av treet. Imidlertid er den enkleste metoden for beskjæring å starte med bladene og prøve å fjerne noden som inneholder den vanligste klassen i det bladet. Hvis nøyaktigheten av modellen ikke forverres når dette gjøres, så beholdes endringen. Det finnes andre teknikker som brukes til å utføre beskjæring, men metoden som er beskrevet ovenfor – reduksjon av feil beskjæring – er kanskje den vanligste metoden for beslutningstre beskjæring.

Overveielser for å bruke beslutningstre

Beslutningstre er ofte nyttige når klassifisering må utføres, men beregnings tid er en stor begrensning. Beslutningstre kan gjøre det klart hvilke trekk i de valgte datasett som har mest prediktiv kraft. I tillegg, i motsetning til mange maskinlæring algoritmer hvor reglene som brukes til å klassifisere dataene kan være vanskelige å tolke, kan beslutningstre gi tolkbare regler. Beslutningstre er også i stand til å bruke både kategoriske og kontinuerlige variabler, noe som betyr at mindre forarbeiding er nødvendig, sammenlignet med algoritmer som bare kan håndtere en av disse variabel typene.

Beslutningstre tenderer ikke til å fungere svært godt når de brukes til å bestemme verdiene av kontinuerlige attributter. En annen begrensning av beslutningstre er at, når klassifisering utføres, hvis det er få treningseksempler men mange klasser, tenderer beslutningstreet å være upresist.