Vad är ett beslutsträd?

Vad är ett beslutsträd?

Ett beslutsträd är ett användbart maskinlärningsalgoritm som används för både regression och klassificeringsuppgifter. Namnet “beslutsträd” kommer från det faktum att algoritmen fortsätter att dela upp datamängden i mindre och mindre delar tills datat har delats upp i enskilda instanser, som sedan klassificeras. Om du skulle visualisera resultaten av algoritmen, skulle sättet som kategorierna delas upp likna ett träd med många blad.

Detta är en snabb definition av ett beslutsträd, men låt oss ta en djupdykning i hur beslutsträd fungerar. Att ha en bättre förståelse för hur beslutsträd fungerar, samt deras användningsområden, kommer att hjälpa dig att veta när du ska använda dem under dina maskinlärningsprojekt.

Format för ett beslutsträd

Ett beslutsträd är mycket likt en flödeschema. För att använda ett flödeschema börjar du vid startpunkten, eller roten, av schemat och sedan, baserat på hur du svarar på filterkriterierna för den startnoden, flyttar du till en av de nästa möjliga noderna. Denna process upprepas tills en ände nås.

Beslutsträd fungerar på ett liknande sätt, där varje intern nod i trädet är någon form av test/filterkriterium. Noderna på utsidan, ändpunkterna för trädet, är etiketterna för datapunkten i fråga och de kallas “blad”. Grenarna som leder från de interna noderna till nästa nod är funktioner eller konjunktioner av funktioner. Reglerna som används för att klassificera datapunkterna är vägarna som löper från roten till bladen.

Algoritmer för beslutsträd

Beslutsträd fungerar på en algoritmisk approach som delar upp datamängden i enskilda datapunkter baserat på olika kriterier. Dessa delningar görs med olika variabler, eller de olika funktionerna i datamängden. Till exempel, om målet är att bestämma om en hund eller katt beskrivs av indatafunktionerna, kan variabler som datat delas på vara saker som “klor” och “skäller”.

Så vilka algoritmer används för att faktiskt dela upp datat i grenar och blad? Det finns olika metoder som kan användas för att dela upp ett träd, men den vanligaste metoden för delning är förmodligen en teknik som kallas “rekursiv binär delning“. När denna metod för delning utförs, startar processen vid roten och antalet funktioner i datamängden representerar det möjliga antalet möjliga delningar. En funktion används för att bestämma hur mycket noggrannhet varje möjlig delning kommer att kosta, och delningen görs med kriteriet som offrar minst noggrannhet. Denna process utförs rekursivt och undergrupper bildas med samma allmänna strategi.

För att bestämma kostnaden för delningen, används en kostnadsfunktion. En annan kostnadsfunktion används för regressionsuppgifter och klassificeringsuppgifter. Målet med båda kostnadsfunktionerna är att bestämma vilka grenar som har de mest liknande svars-värdena, eller de mest homogena grenarna. Tänk på att du vill att testdata av en viss klass ska följa vissa vägar och detta har intuitivt mening.

I fråga om regressionskostnadsfunktionen för rekursiv binär delning, är algoritmen som används för att beräkna kostnaden följande:

sum(y – prediction)^2

Pre diktionen för en viss grupp datapunkter är medelvärdet av svaren från utbildningsdatat för den gruppen. Alla datapunkterna körs genom kostnadsfunktionen för att bestämma kostnaden för alla möjliga delningar och delningen med den lägsta kostnaden väljs.

I fråga om kostnadsfunktionen för klassificering, är funktionen följande:

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

Detta är Gini-poängen, och det är ett mått på effektiviteten av en delning, baserat på hur många instanser av olika klasser som finns i grupperna som resulterar från delningen. Med andra ord, det kvantifierar hur blandade grupperna är efter delningen. En optimal delning är när alla grupper som resulterar från delningen består endast av ingångar från en klass. Om en optimal delning har skapats, kommer “pk”-värdet att vara antingen 0 eller 1 och G kommer att vara lika med noll. Du kanske kan gissa att den sämsta delningen är en där det finns en 50-50-representation av klasserna i delningen, i fallet med binär klassificering. I detta fall, kommer “pk”-värdet att vara 0,5 och G kommer också att vara 0,5.

Delningsprocessen avslutas när alla datapunkterna har omvandlats till blad och klassificerats. Men du kanske vill stoppa tillväxten av trädet i förväg. Stora komplexa träd är benägna att överanpassning, men flera olika metoder kan användas för att bekämpa detta. En metod för att minska överanpassning är att ange ett minimum antal datapunkter som kommer att användas för att skapa ett blad. En annan metod för att kontrollera överanpassning är att begränsa trädet till en viss maximal djup, som kontrollerar hur lång en väg kan sträcka sig från roten till ett blad.

En annan process som är involverad i skapandet av beslutsträd är beskärning. Beskärning kan hjälpa till att öka prestandan för ett beslutsträd genom att ta bort grenar som innehåller funktioner som har liten prediktiv kraft/liten betydelse för modellen. På detta sätt, minskas komplexiteten i trädet, det blir mindre benäget att överanpassa och den prediktiva nyttan av modellen ökar.

När beskärning utförs, kan processen starta antingen vid toppen av trädet eller botten av trädet. Men den enklaste metoden för beskärning är att starta med bladen och försöka ta bort noden som innehåller den vanligaste klassen inom det bladet. Om noggrannheten för modellen inte försämras när detta görs, så behålls ändringen. Det finns andra tekniker som används för att utföra beskärning, men metoden som beskrivs ovan – minskad felbeskärning – är förmodligen den vanligaste metoden för besluts-trädsbeskärning.

Överväganden för att använda besluts-träd

Besluts-träd är ofta användbara när klassificering behöver utföras men beräknings-tid är en stor begränsning. Besluts-träd kan göra det tydligt vilka funktioner i de valda datamängderna som har den mest prediktiva kraften. Dessutom, till skillnad från många maskinlärningsalgoritmer där reglerna som används för att klassificera datat kan vara svåra att tolka, kan besluts-träd ge tolkningsbara regler. Besluts-träd kan också använda både kategoriska och kontinuerliga variabler, vilket innebär att mindre förbearbetning behövs, jämfört med algoritmer som bara kan hantera en av dessa variabeltyper.

Besluts-träd tenderar inte att fungera särskilt bra när de används för att bestämma värdena på kontinuerliga attribut. En annan begränsning av besluts-träd är att, när klassificering utförs, om det finns få tränings-exempel men många klasser, tenderar besluts-trädet att vara inkorrekt.