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 och 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ändningsfall, 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 en 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, med varje intern nod i trädet som 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, variabler som datat delas på kan 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. Överväg att du vill testa data av en viss klass för att följa vissa vägar och detta är intuitivt.

Vad gäller regressionskostnadsfunktionen för rekursiv binär delning, är algoritmen som används för att beräkna kostnaden följande:

sum(y – förutsägelse)^2

Förutsägelsen 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.

Vad gäller 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 indata 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, skulle “pk”-värdet vara 0,5 och G skulle också 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 tidigt. Stora komplexa träd är benägna att överanpassa, 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, vilket 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 från 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 släppa 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 förä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 beslutsträdsbeskärning.

Överväganden för att använda beslutsträd

Beslutsträd är ofta användbara när klassificering behöver utföras men beräknings tid är en stor begränsning. Beslutsträ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 data kan vara svåra att tolka, kan beslutsträd ge tolkningsbara regler. Beslutsträ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.

Beslutsträ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 beslutsträd är att, när klassificering utförs, om det finns få träningsexempel men många klasser, tenderar beslutsträdet att vara inkorrekt.