Vad är ett beslutsträd?

Vad är ett beslutsträd?

A beslutsträd är en användbar maskininlärningsalgoritm som används för både regressions- och klassificeringsuppgifter. Namnet "beslutsträd" kommer från det faktum att algoritmen fortsätter att dela upp datasetet i mindre och mindre delar tills data har delats upp i enstaka instanser, som sedan klassificeras. Om du skulle visualisera resultatet av algoritmen, skulle sättet som kategorierna är uppdelade på likna ett träd och många löv.

Det ä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, såväl som deras användningsfall, hjälper dig att veta när du ska använda dem under dina maskininlärningsprojekt.

Format för ett beslutsträd

Ett beslutsträd är mycket som ett flödesschema. För att använda ett flödesschema börjar du vid startpunkten, eller roten, av diagrammet och baserat på hur du svarar på filtreringskriterierna för den startnoden flyttar du till en av nästa möjliga noder. Denna process upprepas tills ett slut uppnås.

Beslutsträd fungerar på i huvudsak samma sätt, där varje intern nod i trädet är någon sorts test-/filtreringskriterier. Noderna på utsidan, trädets ändpunkter, är etiketterna för den aktuella datapunkten 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 går från roten till bladen.

Algoritmer för beslutsträd

Beslutsträd fungerar på ett algoritmiskt sätt som delar upp datasetet i individuella datapunkter baserat på olika kriterier. Dessa uppdelningar görs med olika variabler, eller de olika funktionerna i datamängden. Till exempel, om målet är att avgöra om en hund eller katt beskrivs av inmatningsfunktionerna eller inte, kan variabler som data delas på vara saker som "klor" och "skäller".

Så vilka algoritmer används för att faktiskt dela upp data i grenar och blad? Det finns olika metoder som kan användas för att dela upp ett träd, men den vanligaste metoden att klyva är förmodligen en teknik som kallas "rekursiv binär split”. När du utför denna uppdelningsmetod börjar processen vid roten och antalet funktioner i datasetet representerar det möjliga antalet möjliga uppdelningar. En funktion används för att bestämma hur mycket noggrannhet varje möjlig uppdelning kommer att kosta, och uppdelningen görs med de kriterier som offrar minst noggrannhet. Denna process genomförs rekursivt och undergrupper bildas med samma allmänna strategi.

I syfte att bestämma kostnaden för uppdelningen, 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 lika svarsvärdena, eller de mest homogena grenarna. Tänk på att du vill att testdata för en viss klass ska följa vissa vägar och det är intuitivt vettigt.

När det gäller regressionskostnadsfunktionen för rekursiv binär split, är algoritmen som används för att beräkna kostnaden enligt följande:

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

Förutsägelsen för en viss grupp av datapunkter är medelvärdet av svaren från träningsdata för den gruppen. Alla datapunkter körs genom kostnadsfunktionen för att bestämma kostnaden för alla möjliga uppdelningar och uppdelningen med den lägsta kostnaden väljs.

När det gäller kostnadsfunktionen för klassificering är funktionen följande:

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

Detta är Gini-poängen, och det är ett mått på effektiviteten av en splittring, baserat på hur många instanser av olika klasser som finns i grupperna som är resultatet av splittringen. Med andra ord, det kvantifierar hur blandade grupperna är efter splittringen. En optimal split är när alla grupper som resulterar från uppdelningen endast består av indata från en klass. Om en optimal split 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 värsta uppdelningen är en där det finns en 50-50 representation av klasserna i uppdelningen, när det gäller binär klassificering. I det här fallet skulle "pk"-värdet vara 0.5 och G skulle också vara 0.5.

Uppdelningsprocessen avslutas när alla datapunkter har förvandlats till löv 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 övermontering är att ange ett minsta antal datapunkter som kommer att användas för att skapa ett löv. En annan metod att kontrollera för överanpassning är att begränsa trädet till ett visst maximalt djup, vilket styr hur länge en stig kan sträcka sig från roten till ett löv.

En annan process involverad i skapandet av beslutsträd är beskärning. Beskärning kan hjälpa till att öka prestandan hos ett beslutsträd genom att ta bort grenar som innehåller funktioner som har liten prediktiv kraft/liten betydelse för modellen. På så sätt minskar trädets komplexitet, det blir mindre sannolikt att det överpassar och modellens prediktiva användbarhet ökar.

Vid beskärning kan processen starta antingen i toppen av trädet eller i botten av trädet. Den enklaste metoden för beskärning är dock att börja med bladen och försöka tappa noden som innehåller den vanligaste klassen inom det bladet. Om modellens noggrannhet inte försämras när detta görs, så bevaras förändringen. Det finns andra tekniker som används för att utföra beskärning, men metoden som beskrivs ovan – reducerad felbeskärning – är förmodligen den vanligaste metoden för beslutsträdsbeskärning.

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

Besluts träd är ofta användbara när klassificering behöver utföras men beräkningstiden ä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 maskininlärningsalgoritmer där reglerna som används för att klassificera data kan vara svåra att tolka, kan beslutsträd göra tolkningsbara regler. Beslutsträd kan också använda sig av både kategoriska och kontinuerliga variabler vilket gör att mindre förbearbetning behövs, jämfört med algoritmer som bara kan hantera en av dessa variabeltyper.

Beslutsträd tenderar att inte fungera särskilt bra när de används för att bestämma värdena för kontinuerliga attribut. En annan begränsning av beslutsträd är att när man gör klassificering, om det finns få träningsexempel men många klasser tenderar beslutsträdet att vara felaktigt.