Hva er et avgjørelsestre?

Hva er et avgjørelsestre?

A beslutningstre er en nyttig maskinlæringsalgoritme som brukes for både regresjons- og klassifiseringsoppgaver. Navnet "beslutningstre" kommer fra det faktum at algoritmen fortsetter å dele datasettet ned i mindre og mindre deler til dataene er delt inn i enkeltinstanser, som deretter klassifiseres. Hvis du skulle visualisere resultatene av algoritmen, vil måten kategoriene er delt på ligne på et tre og mange blader.

Det er en rask definisjon av et beslutningstre, men la oss ta et dypdykk i hvordan beslutningstre fungerer. Å ha en bedre forståelse av hvordan beslutningstrær fungerer, så vel som deres brukstilfeller, vil hjelpe deg med å vite når du skal bruke dem under maskinlæringsprosjektene dine.

Format for et beslutningstre

Et beslutningstre er mye som et flytskjema. For å bruke et flytskjema starter du ved startpunktet, eller roten, av diagrammet og deretter, basert på hvordan du svarer på filtreringskriteriene for den startnoden, flytter du til en av de neste mulige nodene. Denne prosessen gjentas til en avslutning er nådd.

Beslutningstrær fungerer i hovedsak på samme måte, med hver interne node i treet som en slags test-/filtreringskriterier. Nodene på utsiden, endepunktene til treet, er etikettene for det aktuelle datapunktet, og de kalles "blader". Grenene som fører fra de interne nodene til neste node er funksjoner eller konjunksjoner av funksjoner. Reglene som brukes til å klassifisere datapunktene er banene som går fra roten til bladene.

Algoritmer for beslutningstrær

Beslutningstrær opererer på en algoritmisk tilnærming som deler datasettet opp i individuelle datapunkter basert på ulike kriterier. Disse delingene gjøres med forskjellige variabler, eller de forskjellige funksjonene til datasettet. For eksempel, hvis målet er å finne ut om en hund eller katt blir beskrevet av inndatafunksjonene eller ikke, kan variabler dataene deles på være ting som "klør" og "bjeffing".

Så hvilke algoritmer brukes til å dele dataene i grener og blader? Det finnes ulike metoder som kan brukes til å splitte et tre, men den vanligste metoden for å splitte er sannsynligvis en teknikk som kalles "rekursiv binær splittelse". Når du utfører denne metoden for splitting, starter prosessen ved roten og antall funksjoner i datasettet representerer det mulige antallet mulige delinger. En funksjon brukes til å bestemme hvor mye nøyaktighet hver mulig splittelse vil koste, og delingen gjøres ved å bruke kriteriene som ofrer minst nøyaktighet. Denne prosessen utføres rekursivt og undergrupper dannes ved bruk av samme generelle strategi.

For å kunne bestemme kostnadene for delingen, brukes en kostnadsfunksjon. En annen kostnadsfunksjon brukes for regresjonsoppgaver og klassifiseringsoppgaver. Målet med begge kostnadsfunksjonene er å bestemme hvilke grener som har de mest like responsverdiene, eller de mest homogene grenene. Tenk på at du vil at testdata fra en bestemt klasse skal følge bestemte veier, og dette gir intuitivt mening.

Når det gjelder regresjonskostnadsfunksjonen for rekursiv binær splittelse, er algoritmen som brukes til å beregne kostnaden som følger:

sum(y – prediksjon)^2

Prediksjonen for en bestemt gruppe datapunkter er gjennomsnittet av responsene til treningsdataene for den gruppen. Alle datapunktene kjøres gjennom kostnadsfunksjonen for å bestemme kostnaden for alle mulige delinger, og delingen med lavest kostnad velges.

Når det gjelder kostnadsfunksjonen for klassifisering, er funksjonen som følger:

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

Dette er Gini-poengsummen, og det er et mål på effektiviteten til en splittelse, basert på hvor mange forekomster av forskjellige klasser som er i gruppene som er et resultat av splittelsen. Med andre ord, det kvantifiserer hvor blandet gruppene er etter splittelsen. En optimal splitt er når alle gruppene som resulterer fra splittelsen består kun av innganger fra én klasse. Hvis en optimal splitt er opprettet, vil "pk"-verdien være enten 0 eller 1 og G vil være lik null. Du kan kanskje gjette at splittelsen i verste fall er en der det er en 50-50 representasjon av klassene i splittelsen, i tilfelle av binær klassifisering. I dette tilfellet vil "pk"-verdien være 0.5 og G vil også være 0.5.

Splittingsprosessen avsluttes når alle datapunktene er blitt omgjort til blader og klassifisert. Det kan imidlertid være lurt å stoppe veksten av treet tidlig. Store komplekse trær er utsatt for overfitting, men flere ulike metoder kan brukes for å bekjempe dette. En metode for å redusere overtilpasning er å spesifisere et minimum antall datapunkter som skal brukes til å lage et blad. En annen metode for å kontrollere for overtilpasning er å begrense treet til en viss maksimal dybde, som styrer hvor lenge en sti kan strekke seg fra roten til et blad.

En annen prosess involvert i opprettelsen av beslutningstrær er beskjæring. Beskjæring kan bidra til å øke ytelsen til et beslutningstre ved å fjerne grener som inneholder funksjoner som har liten prediktiv kraft/liten betydning for modellen. På denne måten reduseres kompleksiteten til treet, det blir mindre sannsynlighet for overfitting, og den prediktive nytten av modellen økes.

Når du utfører beskjæring, kan prosessen starte enten på toppen av treet eller bunnen av treet. Den enkleste metoden for beskjæring er imidlertid å starte med bladene og forsøke å slippe noden som inneholder den vanligste klassen i det bladet. Hvis nøyaktigheten til modellen ikke forringes når dette gjøres, er endringen bevart. Det finnes andre teknikker som brukes for å utføre beskjæring, men metoden beskrevet ovenfor – redusert feilbeskjæring – er trolig den vanligste metoden for beslutningstrebeskjæring.

Hensyn ved bruk av beslutningstrær

Beslutningstrær er ofte nyttige når klassifisering må utføres, men beregningstiden er en stor begrensning. Beslutningstrær kan gjøre det klart hvilke funksjoner i de valgte datasettene som har mest prediktiv kraft. Videre, i motsetning til mange maskinlæringsalgoritmer der reglene som brukes til å klassifisere dataene kan være vanskelige å tolke, kan beslutningstrær gjengi tolkbare regler. Beslutningstrær er også i stand til å benytte seg av både kategoriske og kontinuerlige variabler som gjør at mindre forbehandling er nødvendig, sammenlignet med algoritmer som kun kan håndtere én av disse variabeltypene.

Beslutningstrær har en tendens til ikke å fungere veldig bra når de brukes til å bestemme verdiene til kontinuerlige attributter. En annen begrensning for beslutningstrær er at ved klassifisering, hvis det er få treningseksempler, men mange klasser, har beslutningstreet en tendens til å være unøyaktig.