Beslutningstræer: Hvordan optimerer jeg min beslutningsproces?

Lad os forestille os, at du spiller et spil Twenty Questions. Din modstander har i hemmelighed valgt et emne, og du skal finde ud af, hvad han / hun valgte. Ved hver tur kan du stille et ja-eller-nej spørgsmål, og din modstander skal svare sandt. Hvordan finder du ud af hemmeligheden i det mindste antal spørgsmål?

Det bør være indlysende, nogle spørgsmål er bedre end andre. For eksempel at spørge “Kan det flyve?”, Da dit første spørgsmål sandsynligvis er ufruktbart, mens det at spørge “Er det i live?” Er en smule mere nyttigt. Intuitivt ønsker du, at hvert spørgsmål i væsentlig grad vil indsnævre pladsen til muligvis hemmeligheder, og til sidst føre til dit svar.

Det er den grundlæggende idé bag beslutningstræer. På hvert punkt overvejer du et sæt spørgsmål, der kan opdele dit datasæt. Du vælger det spørgsmål, der giver den bedste opdeling, og finder igen de bedste spørgsmål til partitionerne. Du stopper, når alle de punkter, du overvejer, er af samme klasse. Derefter er opgaven med klassificering let. Du kan bare gribe et punkt og chuck det ned ad træet. Spørgsmålene leder den til den passende klasse.

Vigtige betingelser

Beslutningstræ er en type overvåget indlæringsalgoritme, der kan bruges i både regressions- og klassificeringsproblemer. Det fungerer til både kategoriske og kontinuerlige input- og outputvariabler.

Lad os identificere vigtige terminologier på beslutningstræet ved at se på billedet ovenfor:

  • Root Node repræsenterer hele populationen eller prøven. Det bliver yderligere opdelt i 2 eller flere homogene sæt.
  • Opdeling er en proces til opdeling af en knude i 2 eller flere undernoder.
  • Når en undernode opdeles i yderligere undernoder, kaldes det en beslutningsknudepunkt.
  • Knudepunkter, der ikke splittes, kaldes en terminalknude eller en blade.
  • Når du fjerner undernoder til en beslutningsnode, kaldes denne proces beskæring. Det modsatte af beskæring er opsplitning.
  • En underafsnit af et helt træ kaldes en gren.
  • En knude, der er opdelt i undernoder kaldes en forældreknudepunkt for undernoder; hvorimod undernoderne kaldes barnet til den overordnede knude.

Hvordan det virker

Her taler jeg kun om klassificeringstræ, der bruges til at forudsige en kvalitativ respons. Regressionstræ er det, der bruges til at forudsige kvantitative værdier.

I et klassificeringstræ forudsiger vi, at hver observation hører til den mest almindeligt forekommende klasse af træningsobservationer i den region, den tilhører. Når vi fortolker resultaterne af et klassificeringstræ, er vi ofte interesserede ikke kun i klasseforudsigelsen, der svarer til et bestemt terminalnodeområde, men også i klasseproportionerne blandt de træningsobservationer, der falder ind i den region. Opgaven med at dyrke et klassificeringstræ er afhængig af at bruge en af ​​disse 3 metoder som et kriterium til at fremstille de binære opdelinger:

1 - Klassificeringsfejlfrekvens: Vi kan definere "hit rate" som den brøkdel af træningsobservationer i en bestemt region, der ikke hører til den mest forekommende klasse. Fejlen er givet ved denne ligning:

E = 1 - argmax_ {c} (π̂ mc)

hvor π̂ mc repræsenterer brøkdelen af ​​træningsdata i region R_m, der hører til klasse c.

2 - Gini-indeks: Gini-indekset er en alternativ fejlmetrik, der er designet til at vise, hvor "ren" en region er. "Renhed" betyder i dette tilfælde, hvor meget af træningsdataene i en bestemt region tilhører en enkelt klasse. Hvis en region R_m indeholder data, der for det meste kommer fra en enkelt klasse c, vil Gini-indeksværdien være lille:

3 - Cross-Entropy: Et tredje alternativ, der ligner Gini-indekset, er kendt som Cross-Entropy eller Deviance:

Krydsantropien får en værdi i nærheden af ​​nul, hvis π̂ mc'erne alle er tæt på 0 eller i nærheden af ​​1. Derfor, som Gini-indekset, vil krydsentropien få en lille værdi, hvis den m-th node er ren. Det viser sig faktisk, at Gini-indekset og tværantropien er temmelig ens.

Når man bygger et klassificeringstræ, bruges enten Gini-indekset eller tvær-entropien typisk til at evaluere kvaliteten af ​​en bestemt opdeling, da de er mere følsomme over for nodens renhed end klassifikationsfejlfrekvensen. Enhver af disse 3 fremgangsmåder kan bruges, når træet beskæres, men klassificeringsfejlfrekvensen foretrækkes, hvis forudsigelsesnøjagtigheden af ​​det endelige beskærede træ er målet.

Implementering fra ridser

Lad os gå gennem beslutnings træbygningsalgoritmen med alle dens fine detaljer. For at opbygge et beslutningstræ er vi nødt til at tage en første beslutning om datasættet for at diktere, hvilken funktion der bruges til at opdele dataene. For at bestemme dette skal vi prøve alle funktioner og måle, hvilken opdeling der giver os de bedste resultater. Derefter vil vi opdele datasættet i undergrupper. Delsættene går derefter gennem filialerne af den første beslutningsnode. Hvis dataene på filialerne er af samme klasse, har vi klassificeret dem korrekt og behøver ikke at fortsætte med at opdele dem. Hvis dataene ikke er de samme, er vi nødt til at gentage opdelingsprocessen på denne delmængde. Beslutningen om, hvordan dette undergruppe skal opdeles, gøres på samme måde som det originale datasæt, og vi gentager denne proces, indtil vi har klassificeret alle data.

Hvordan deler vi vores datasæt? En måde at organisere denne rod er at måle informationen. Ved hjælp af informationsteori kan vi måle informationerne før og efter opdelingen. Ændringen i information før og efter opdelingen kaldes informationsgevinsten. Når vi ved, hvordan vi beregner informationsgevinsten, kan vi dele vores data på tværs af hver funktion for at se, hvilken opdeling der giver os den højeste informationsgevinst. Opdelingen med den højeste informationsgevinst er vores bedste mulighed.

For at beregne informationsgevinsten kan vi bruge Shannon Entropy, som er den forventede værdi af al informationen om alle mulige værdier i vores klasse. Lad os se Python-koden til det:

Som du kan se, beregner vi først et antal af antallet af forekomster i datasættet. Så opretter vi en ordbog, hvis nøgler er værdierne i den sidste kolonne. Hvis der ikke tidligere blev fundet en nøgle, oprettes en. For hver nøgle holder vi rede på, hvor mange gange denne etiket forekommer. Endelig bruger vi hyppigheden af ​​alle de forskellige etiketter til at beregne sandsynligheden for den etiket. Denne sandsynlighed bruges til at beregne Shannon-entropien, og vi opsummerer dette for alle etiketter.

Efter at have fundet ud af en måde at måle datasætets entropi, er vi nødt til at opdele datasættet, måle entropien på opdelte sæt og se om opdeling af det var den rigtige ting at gøre. Her er koden til at gøre det:

Denne kode tager 3 input: de data, der skal deles på, den funktion, der skal deles på, og værdien af ​​den funktion, der skal returneres. Vi opretter en ny liste i begyndelsen hver gang, fordi vi kalder denne funktion flere gange på det samme datasæt, og vi ønsker ikke, at det originale datasæt ændres. Vores datasæt er en liste over lister; som vi gentager over hvert element på listen, og hvis det indeholder den værdi, vi leder efter, tilføjer vi det til vores nyligt oprettede liste. Inde i if-udsagnet skærer vi ud den funktion, som vi har delt på.

Nu skal vi kombinere 2 funktioner: ShannonEntropy og splitDataset for at gå gennem datasættet og besluttet, hvilken funktion der er den bedste at dele på.

Lad os hurtigt undersøge koden:

  • Vi beregner Shannon-entropien for hele datasættet, inden der opstår splittelse, og tildeler værdien til variabel baseEntropy.
  • Den første for loop-loopes over alle funktioner i vores data. Vi bruger listeforståelser til at oprette en liste (featList) med alle i-th-poster i dataene eller alle de mulige værdier, der findes i dataene.
  • Dernæst opretter vi et nyt sæt fra en liste for at få de unikke værdier ud (uniqueVals).
  • Derefter gennemgår vi alle de unikke værdier for denne funktion og deler dataene for hver funktion (subData). Den nye entropi beregnes (newEntropy) og opsummeres for alle de unikke værdier for denne funktion. Informationsgevinsten (infoGain) er reduktionen i entropi (baseEntropy - newEntropy).
  • Endelig sammenligner vi informationsgevinsten mellem alle funktioner og returnerer indekset for den bedste funktion, der skal deles på (bestFeature).

Nu hvor vi kan måle, hvor organiseret et datasæt er, og vi kan dele dataene, er det tid til at sammensætte alt dette og opbygge beslutningstræet. Fra et datasæt opdeler vi det baseret på den bedste attribut til split. Når den er delt, vil dataene gå gennem træets grene til en anden knude. Denne knude opdeler derefter dataene igen. Vi vil bruge rekursion til at håndtere dette.

Vi stopper kun under følgende betingelser: (1) Det løber tør for de attributter, der skal opdeles, eller (2) alle forekomster i en gren er i samme klasse. Hvis alle forekomster har den samme klasse, opretter vi en bladknude. Alle data, der når dette bladknudepunkt, anses for at tilhøre klassen af ​​den bladknudepunkt.

Her er koden til at opbygge vores beslutningstræer:

Vores kode tager 2 input: dataene og en liste med etiketter:

  • Vi opretter først en liste over alle klassetiketter i datasættet og kalder denne klasseliste. Den første stopbetingelse er, at hvis alle klassetiketter er ens, så returnerer vi denne etiket. Den anden stoptilstand er tilfældet, når der ikke er flere funktioner, der skal opdeles. Hvis vi ikke opfylder stoppebetingelserne, bruger vi funktionen vælg BestFeatureToSplit til at vælge den bedste funktion.
  • For at oprette træet gemmer vi det i en ordbog (myTree). Så får vi alle de unikke værdier fra datasættet til vores valgte funktion (bestFeat). Den unikke værdikode bruger sæt (uniqueVals).
  • Endelig gentager vi alle de unikke værdier fra vores valgte funktion og kalder rekursivt createTree () for hver opdeling af datasættet. Denne værdi indsættes i myTree-ordbogen, så vi ender med en masse indlejrede ordbøger, der repræsenterer vores træ.

Implementering via Scikit-Learn

Nu hvor vi ved, hvordan vi implementerer algoritmen fra bunden, lad os bruge scikit-learning. Vi bruger især klassen DecisionTreeClassifier. Arbejde med iris-datasættet importerer vi først dataene og opdeler dem i en trænings- og testdel. Derefter bygger vi en model ved hjælp af standardindstillingen til fuldt ud at udvikle træet (dyrke træet, indtil alle blade er rene). Vi fikser random_staten i træet, der bruges til båndbrydning internt:

At køre modellen skal give os en testsættenøjagtighed på 95%, hvilket betyder, at modellen forudsagde klassen korrekt for 95% af prøverne i testdatasættet.

Styrker og svagheder

Den største fordel ved at bruge beslutningstræer er, at de er intuitivt meget lette at forklare. De afspejler nøje menneskelig beslutningstagning sammenlignet med andre regressions- og klassificeringsmetoder. De kan vises grafisk, og de kan let håndtere kvalitative forudsigelser uden behov for at oprette dummy-variabler.

En anden enorm fordel er sådan, at algoritmerne er fuldstændigt uoverensstemmende med skalering af dataene. Da hver funktion behandles separat, og de mulige opdelinger af dataene ikke afhænger af skalering, er der ikke behov for forbehandling som normalisering eller standardisering af funktioner til beslutningstræealgoritmer. Især fungerer beslutningstræer godt, når vi har funktioner, der er i helt forskellige skalaer, eller en blanding af binære og kontinuerlige funktioner.

Imidlertid har beslutningstræer generelt ikke det samme niveau af forudsigelsesnøjagtighed som andre tilgange, da de ikke er helt robuste. En lille ændring i dataene kan forårsage en stor ændring i det endelige estimerede træ. Selv med brugen af ​​forbeskæring har de en tendens til at overdreven og giver dårlig generaliseringsydelse. Derfor kan den forudsigelige ydelse af beslutningstræer forbedres væsentligt ved de fleste applikationer ved at samle mange beslutningstræer, bruge metoder som posning, tilfældige skove og boosting.

Referencekilder:

  • Introduktion til statistisk læring af Gareth James, Daniela Witten, Trevor Hastie og Robert Tibshirani (2014)
  • Machine Learning In Action af Peter Harrington (2012)
  • Introduktion til maskinlæring med Python af Sarah Guido og Andreas Muller (2016)

- -

Hvis du nød dette stykke, ville jeg elske det, hvis du trykker på klapknappen så andre måske snubler over det. Du kan finde min egen kode på GitHub og mere af min skrivning og projekter på https://jameskle.com/. Du kan også følge mig på Twitter, e-maile mig direkte eller finde mig på LinkedIn.