Förstå Random Forest – med Maskininlärning

Hur algoritmen fungerar och varför den är så effektiv

En stor del av maskininlärning är klassificering – vi vill veta vilken klass (a.k.a. grupp) en observation tillhör. Möjligheten att exakt klassificera observationer är extremt värdefull för olika affärsapplikationer som att förutsäga om en viss användare kommer att köpa en produkt eller förutsäga om ett givet lån kommer att fallera eller inte.

Datavetenskap tillhandahåller en uppsjö av klassificeringsalgoritmer som logistisk regression, stödvektormaskin, naiv Bayes-klassificerare och beslutsträd. Men nära toppen av klassificerarehierarkin finns den slumpmässiga skogsklassificeraren (det finns också den slumpmässiga skogregressorn men det är ett ämne för en annan dag).

I det här inlägget kommer vi att undersöka hur grundläggande beslutsträd fungerar, hur individuella beslutsträd kombineras för att skapa en slumpmässig skog och i slutändan upptäcka varför slumpmässiga skogar är så bra på vad de gör.

Beslutsträd

Låt oss snabbt gå igenom beslutsträd eftersom de är byggstenarna i den slumpmässiga skogsmodellen. Lyckligtvis är de ganska intuitiva. Jag skulle vara villig att slå vad om att de flesta människor har använt ett beslutsträd, medvetet eller inte, någon gång i livet.

Det är förmodligen mycket lättare att förstå hur ett beslutsträd fungerar genom ett exempel.

Föreställ dig att vår datauppsättning består av siffrorna överst i figuren till vänster. Vi har två 1:or och fem 0:or (1:or och 0:or är våra klasser) och vill separera klasserna med hjälp av deras funktioner. Funktionerna är färg (röd vs. blå) och om observationen är understruken eller inte. Så hur kan vi göra detta?

Färg verkar vara en ganska uppenbar funktion att dela efter eftersom alla utom en av nollorna är blå. Så vi kan använda frågan “Är den röd?” att dela upp vår första nod.

Du kan tänka på en nod i ett träd som den punkt där vägen delas i två – observationer som uppfyller kriterierna går ner för Ja-grenen och de som inte går ner för Nej-grenen.

Nej-grenen (the blues) är helt noll nu så vi är klara där, men vår Ja-gren kan fortfarande delas upp ytterligare. Nu kan vi använda den andra funktionen och fråga: “Är den understruken?” att göra en andra split.

De två 1:orna som är understrukna går ner i undergrenen Ja och den nolla som inte är understruken går ner till höger undergrenen och vi är alla klara. Vårt beslutsträd kunde använda de två funktionerna för att dela upp data perfekt. Seger!

Uppenbarligen kommer vår data inte att vara så ren i verkligheten, men logiken som ett beslutsträd använder förblir densamma. Vid varje nod kommer den att fråga — Vilken funktion gör att jag kan dela upp observationerna på ett sätt så att de resulterande grupperna är så olika varandra som möjligt (och medlemmarna i varje resulterande undergrupp är så lika varandra som möjligt )?

The Random Forest Classifier

Random forest, som namnet antyder, består av ett stort antal individuella beslutsträd som fungerar som en ensemble. Varje enskilt träd i den slumpmässiga skogen spottar ut en klassförutsägelse och klassen med flest röster blir vår modells förutsägelse (se figuren nedan).

Visualisering av en slumpmässig skogsmodell som gör en förutsägelse
Det grundläggande konceptet bakom random skog är en enkel men kraftfull sådan – folkmassornas visdom. I data science-speak är anledningen till att den slumpmässiga skogsmodellen fungerar så bra:

Ett stort antal relativt okorrelerade modeller (träd) som fungerar som en kommitté kommer att överträffa någon av de individuella ingående modellerna.

Den låga korrelationen mellan modellerna är nyckeln. Precis som hur investeringar med låga korrelationer (som aktier och obligationer) går samman för att bilda en portfölj som är större än summan av dess delar, kan okorrelerade modeller producera ensembleförutsägelser som är mer exakta än någon av de individuella förutsägelserna.

Anledningen till denna underbara effekt är att träden skyddar varandra från sina individuella fel (så länge de inte ständigt felar i samma riktning). Medan vissa träd kan vara fel, kommer många andra träd att vara rätt, så som en grupp kan träden röra sig i rätt riktning. Så förutsättningarna för att de slumpmässiga skogarna ska prestera bra är:

Det måste finnas någon faktisk signal i våra funktioner så att modeller som byggts med dessa funktioner klarar sig bättre än slumpmässiga gissningar.

Förutsägelserna (och därmed felen) som görs av de enskilda träden måste ha låga korrelationer med varandra.

Ett exempel på varför okorrelerade resultat är så bra

De underbara effekterna av att ha många okorrelerade modeller är ett så kritiskt koncept att jag vill visa dig ett exempel för att hjälpa det verkligen att sjunka in. Föreställ dig att vi spelar följande spel:

Jag använder en enhetligt fördelad slumptalsgenerator för att producera ett tal.

Om siffran jag genererar är större än eller lika med 40 vinner du (så att du har 60 % chans att vinna) och jag betalar dig lite pengar. Om det är under 40 vinner jag och du betalar mig lika mycket.

Du har det följande val. Vi kan antingen:
Spel 1 — spela 100 gånger, satsa $1 varje gång.
Spel 2— spela 10 gånger, satsa $10 varje gång.
Spel 3— spela en gång, satsa $100.

Vilken skulle du välja? Det förväntade värdet för varje spel är detsamma:

Förväntat värde Spel 1 = (0,601 + 0,40-1)100 = 20 Förväntat värde Spel 2= (0,6010 + 0,40-10)10 = 20
Förväntat värde Spel 3= 0,60100 + 0,40-100 = 20

Resultatfördelning av 10 000 simuleringar för varje spel

Hur är det med distributionerna? Låt oss visualisera resultaten med en Monte Carlo-simulering (vi kommer att köra 10 000 simuleringar av varje speltyp; till exempel kommer vi att simulera 10 000 gånger de 100 spelningar av spel 1).

Spel 1 (där vi spelar 100 gånger) ger den bästa chansen att tjäna lite pengar — av de 10 000 simuleringar som jag körde tjänar du pengar på 97 % av dem!

För Game 2 (där vi spelar 10 gånger) tjänar du pengar på 63% av simuleringarna, en drastisk nedgång (och en drastisk ökning av din sannolikhet att förlora pengar).

Och spel 3 spelar vi bara en gång, du tjänar pengar på 60 % av simuleringarna, som förväntat.

Så även om spelen delar samma förväntade värde är deras resultatfördelningar helt olika. Ju mer vi delar upp vår satsning på $100 i olika spel, desto mer säkra kan vi vara på att vi kommer att tjäna pengar. Som nämnts tidigare fungerar detta eftersom varje pjäs är oberoende av de andra.

Slumpmässig skog är densamma – varje träd är som ett som spelades i vårt spel tidigare. Vi såg precis hur våra chanser att tjäna pengar ökade ju fler gånger vi spelade. På samma sätt, med en slumpmässig skogsmodell, ökar våra chanser att göra korrekta förutsägelser med antalet okorrelerade träd i vår modell.

Om du vill köra koden för att simulera spelet själv kan du hitta den på min GitHub här.

Se till att modellerna diversifierar varandra

Så hur säkerställer slumpmässig skog att beteendet hos varje enskilt träd inte är alltför korrelerat med beteendet hos något av de andra träden i modellen? Den använder följande två metoder:

Bagging (Bootstrap Aggregation) — Beslutsträd är mycket känsliga för den data de tränas på — små ändringar i träningsuppsättningen kan resultera i väsentligt olika trädstrukturer.

Random forest drar fördel av detta genom att tillåta varje enskilt träd att slumpmässigt ta prov från datamängden med ersättning, vilket resulterar i olika träd. Denna process är känd som påsar.

Lägg märke till att med säckar delar vi inte in träningsdata i mindre bitar och tränar varje träd på en annan bit.

Snarare, om vi har ett urval av storlek N, matar vi fortfarande varje träd med en träningsuppsättning av storlek N (om inte annat anges). Men istället för den ursprungliga träningsdatan tar vi ett slumpmässigt urval av storlek N med ersättning. Till exempel, om vår träningsdata var [1, 2, 3, 4, 5, 6] kan vi ge ett av våra träd följande lista [1, 2, 2, 3, 6, 6].

Lägg märke till att båda listorna är av längd sex och att “2” och “6” båda upprepas i de slumpmässigt valda träningsdata vi ger till vårt träd (eftersom vi provar med ersättning).

Noddelning i en slumpmässig skogsmodell baseras på en slumpmässig delmängd av funktioner för varje träd.

Funktionsslumpmässighet — I ett normalt beslutsträd, när det är dags att dela en nod, tar vi hänsyn till alla möjliga funktioner och väljer den som ger mest åtskillnad mellan observationerna i den vänstra noden och de i den högra noden. Däremot kan varje träd i en slumpmässig skog bara välja från en slumpmässig delmängd av funktioner. Detta tvingar fram ännu mer variation bland träden i modellen och resulterar i slutändan i lägre korrelation mellan träd och mer diversifiering.

Låt oss gå igenom ett visuellt exempel – i bilden ovan kan det traditionella beslutsträdet (i blått) välja från alla fyra funktioner när man bestämmer hur noden ska delas. Den bestämmer sig för att gå med funktion 1 (svart och understruken) eftersom den delar upp data i grupper som är så separerade som möjligt.

Låt oss nu ta en titt på vår slumpmässiga skog. Vi kommer bara att undersöka två av skogens träd i detta exempel. När vi kollar in slumpmässigt skogsträd 1, finner vi att det bara kan överväga funktionerna 2 och 3 (valda slumpmässigt) för sitt noddelningsbeslut. Vi vet från vårt traditionella beslutsträd (i blått) att funktion 1 är den bästa funktionen för att dela, men träd 1 kan inte se funktion 1 så den tvingas gå med funktion 2 (svart och understruken). Träd 2, å andra sidan, kan bara se funktioner 1 och 3 så det kan välja funktion 1.
Så i vår slumpmässiga skog får vi träd som inte bara tränas på olika uppsättningar data (tack vare påsar) utan också använder olika funktioner för att fatta beslut.

Och det, min kära läsare, skapar okorrelerade träd som buffertar och skyddar varandra från deras fel.

Slutsats

Slumpmässiga skogar är en personlig favorit för mig. Från finans- och investeringsvärlden var den heliga graalen alltid att bygga ett gäng okorrelerade modeller, var och en med en positiv förväntad avkastning, och sedan sätta ihop dem i en portfölj för att tjäna massiva alfa (alfa = marknadsslående avkastning). Mycket lättare sagt än gjort!

Random forest är datavetenskapens motsvarighet till det. Låt oss recensera en sista gång. Vad är en slumpmässig skogsklassificerare?

Den slumpmässiga skogen är en klassificeringsalgoritm som består av många beslutsträd. Den använder påsar och slumpmässighet när man bygger varje enskilt träd för att försöka skapa en okorrelerad skog av träd vars förutsägelse av kommittén är mer exakt än den för något enskilt träd.

Vad behöver vi för att vår slumpmässiga skog ska kunna göra korrekta klassförutsägelser?

Vi behöver funktioner som åtminstone har en viss prediktiv kraft. När allt kommer omkring, om vi lägger in sopor så får vi ut sopor.

Skogens träd och ännu viktigare deras förutsägelser måste vara okorrelerade (eller åtminstone ha låga korrelationer med varandra).

Medan själva algoritmen via funktionsslumpmässighet försöker konstruera dessa låga korrelationer åt oss, kommer funktionerna vi väljer och hyperparametrarna vi väljer att också påverka de ultimata korrelationerna.