En ensemble skapar bättre musik. Tusen prediktionsmodeller är bättre än en.

Människan har en tendens att strukturera sitt tänkande och sina beslut. En struktur som vi ofta använder – både medvetet och omedvetet – är hierarkier. Du skapar och använder hierarkier varje dag. Föreställ dig att du befinner dig i en butik där du försöker fatta ett beslut om att köpa en dator. För att fatta ett klokt beslut börjar du med att fråga dig: “Har jag råd att köpa en ny dator”. Om svaret på denna frågan är “nej” så avstår du troligen från att köpa datorn. Om svaret på frågan är “ja” så går du förmodligen vidare till nästa fråga: “Behöver jag en ny dator?” . Om svaret är “nej” så avstår du troligen från att köpa datorn. Om svaret är “ja” så kanske du frågar dig: “Är detta den rätta datorn för mig?” . Du har med andra ord försökt fatta ett beslut genom att ställa dig själv en rad frågor med hierarkisk struktur. Som framgår av bild X så ser denna typ av beslutsflöde ut som ett upp-och-nedvänt träd och man kallar detta för ett beslutsträd (eng. decision tree).

Beslutsträd: en briljant idé

Idag dominerar beslutsträden nästan all machine learning som berör strukturerade data (dvs data som presenteras i rader och kolumner). På Kaggle (www.kaggle.com) tävlar tusentals experter för att skapa de bästa prediktionsmodellerna och av tävlingsresultaten framgår  att beslutsträd oftast presterar bättre än någon annan modell för strukturerade data. Faktum är att du redan använder beslutsträd, varje dag, t ex när du använder Googles sökmotor, eller din e-posttjänst. Förklaringen till att beslutsträd kan användas för prediktion är enkel: i ovanstående exempel kan du använda beslutsalgoritmen på en annan dator och utvärdera om du borde köpa den istället.

Med modern machine learning skapar man beslutsträd på ett mycket sofistikerat vis. Man använder en generell inlärningsprocedur som utifrån mönstren i data skapar regler och därmed bygger trädet. Trädets struktur – och därmed prediktionsmodellen – blir således datadriven (se tidigare diskussion). Vi ska nu gå igenom exakt hur dessa träd skapas och hur de används.

I nedanstående figur presenteras samma data i tabellen och koordinatsystemet. Föreställ dig att vi ska lägga till en punkt i koordinatsystemet och punktens x-värde är 2.0. Vilken färg tror du punkten kommer ha? Sannolikt grön och därmed har du skapat och utvärderat ett beslutsträd i huvudet! Beslutsträdets struktur syns i nästa figur.

I detta beslutsträd används en enda regel baserad på x-värdet. Om x är mindre än 2 väljer vi den vänstra grenen och där förefaller värdena vara röda. Om x är 2 eller större så väljer vi den högra grenen och där förefaller observationerna vara gröna. Varje observation kommer således testas för att se om x är mindre än 2 och därefter fattas ett beslut om vilken gren som skall väljas. Denna punkt där data ska skiljas åt kallas för en nod. Själva delningen kallas split.

Detta beslutsträd kan alltså användas för att gissa vilken färg en observation kommer ha baserat på x-värdet. Vi kan alltså predicera färg baserat på en av variablerna. Man säger att beslutsträdet kan användas för att klassificera observationerna (som gröna eller röda).

I nästa koordinatsystem ser vi nu tre olika färger på observationerna. Vi provar använda vårt första beslutsträd. X-värden som är 2 eller större kommer fortfarande klassificeras som gröna men värden mindre än 2 kan inte klassificeras korrekt alla gånger eftersom vissa att observationerna är blå. Vi behöver således ytterligare en nod!

Vi skapar nu ytterligare en nod och vi skapar en ny regel baserad på y-värdet. Om y-värdet är mindre än 1 så klassificerar vi observationen som röd och annars som blå, enligt följande:

Detta är faktiskt hela principen för att skapa beslutsträd. Som framgår av denna diskussionen så kan vi nu använda vårt beslutsträd för att predicera vilken färg en ny observation kommer ha, baserat på x- och y-värdet. Trädet kan således användas som en prediktionsmodell. Du ser ett exempel på detta i nästa figur, där vi låter en helt ny observation flöda genom beslutsträdet för att slutligen gissa vilken färg observationen sannolikt har.

Machine learning med beslutsträd

Varje enskilt träd är en prediktionsmodell. Principen för att göra machine learning med beslutsträd är att skapa hundratals, eller tusentals, träd och använda deras samlade för många för att predicera. Man använder alltså en datamängd för att skapa hundratals eller tusentals träd som sedan används för att predicera. Precis som med neuronnät så måste träden tränas och utvärderas, vilket  görs efter samma principer. Efter dessa prediktionsmodeller består av många enskilda modeller dvs enskilda träd) så kallas de även ensemblemetoder (eng. ensemble methods), vilket syftar till att man använder en ensemble av prediktionsmodeller. Ibland används även termen trädbaserad metod (eng. tree-based method).

Att konstruera många träd

Som regel konstruerar man alltså flera hundra eller tusentals beslutsträd när man skapar machine learning med beslutsträd. Man skapar dessa träd utifrån samma datamängd. Om du exempelvis studerar besökare på en webbplats och har data på 1000 besökare så är detta datamängden som används för att bygga alla träden. Detta görs genom att varje träd endast får använda en liten andel (oftast en tredjedel) av den totala datamängden. Den andelen skall dessutom väljas ut helt slumpmässigt. Så det första trädet får analysera en slumpmässigt utvald tredjedel av alla besökarna. Nästa träd ges en ny, slumpmässigt utvald, tredjedel av alla besökarna och bygger trädet baserat på deras information. Samma gäller det tredje, fjärde, femte och alla efterkommande träd. Så varje träd byggs med en slumpmässigt utvald delmängd av data. På så vis blir varje träd unikt.

Att hitta optimala noder och splits

Följande koordinatsystem visar samma datamängd med olika regler för att att skilja datapunkterna. Till vänster ser vi splits som lyckas särskilja alla färgerna från varandra. Till höger ser vi att kriterierna (reglerna) inte resulterar i att punkterna kan särskiljas helt och hållet. För att trädets prediktion skall bli bra så måste den hitta regler som kan särskilja observationerna från varandra. För att lyckas med detta måste datorn utvärdera varje split. En bra split definieras av att grupperna som skapas skiljer sig åt så mycket som möjligt avseende det som studeras, vilket i detta fall är färg.

Det finns ett antal olika varianter för att göra denna utvärdering. Alla varianterna fungerar genom att beräkna hur bra olika splits kan separera färgerna från varandra. Datorn kan alltså testa sig fram för att se vilken split som ger maximal separation av observationerna avseende deras färg.

Denna metod för att hitta optimala splits är generell och kan användas på alla typer av strukturerade data, dvs data i tabellformat (kolumner och rader). Det har ingen betydelse om man studerar patienter med cancer, besökare i en webbutik, solstrålar eller bilbatterier. Beslutsträd är extremt kraftfulla och kan predicera på alla typer av strukturerade data. Förklaringen till detta är den generella inlärningsproceduren, dvs beräkningen som görs för att skapa varje split. Detta sätt att “lära sig” liknar faktiskt människans sätt att tänka och ges här en exakt matematisk funktion.