Hvad er et beslutningstræ?

Hvad er et beslutningstræ?

Et beslutningstræ er en nyttig maskinlæringsalgoritme, der bruges til både regression og klassifikationsopgaver. Navnet “beslutningstræ” kommer fra, at algoritmen hele tiden deler datasettet op i mindre og mindre dele, indtil data er delt op i enkeltstående eksempler, som derefter klassificeres. Hvis du skulle visualisere resultaterne af algoritmen, ville måden, hvorpå kategorierne er opdelt, ligne et træ med mange blade.

Dette er en kort definition af et beslutningstræ, men lad os dykke dybere ned i, hvordan beslutningstræer fungerer. At have en bedre forståelse af, hvordan beslutningstræer fungerer, samt deres anvendelsesområder, vil hjælpe dig med at vide, hvornår du skal bruge dem i dine maskinlæringsprojekter.

Format af et beslutningstræ

Et beslutningstræ er meget lig en flowchart. For at bruge en flowchart starter du ved startpunktet eller roden af diagrammet og derefter, baseret på hvordan du besvarer filterkriterierne for det pågældende node, flytter du til en af de næste mulige noder. Denne proces gentages, indtil en afslutning nås.

Beslutningstræer fungerer på samme måde, hvor hvert internt node i træet er en slags test eller filterkriterie. Noderne på ydersiden, endepunkterne for træet, er mærkerne for datapunkterne i question og de kaldes “blade”. Grenene, der fører fra de interne noder til den næste node, er funktioner eller kombinationer af funktioner. Reglerne, der bruges til at klassificere datapunkterne, er stierne, der løber fra roden til bladene.

Algoritmer for beslutningstræer

Beslutningstræer fungerer på en algoritmesk tilgang, som splitter datasettet op i enkeltstående datapunkter baseret på forskellige kriterier. Disse splittelse sker med forskellige variabler eller de forskellige funktioner af datasettet. For eksempel, hvis målet er at bestemme, om en hund eller en kat beskrives af inputfunktionerne, kan variabler, som data er splittet på, være ting som “kløer” og “gør lyd”.

Så hvilke algoritmer bruges til at splitte data op i grene og blade? Der er forskellige metoder, der kan bruges til at splitte et træ op, men den mest almindelige metode til splitting er sandsynligvis en teknik, der kaldes “rekursiv binær split“. Når denne metode til splitting udføres, starter processen ved roden, og antallet af funktioner i datasettet repræsenterer det mulige antal mulige splittelse. En funktion bruges til at bestemme, hvor meget nøjagtighed hver mulig split vil koste, og splittelsen udføres ved hjælp af kriteriet, der ofrer den mindste nøjagtighed. Denne proces udføres rekursivt, og undergrupper dannes ved hjælp af samme generelle strategi.

For at bestemme omkostningerne ved splittelsen, bruges en omkostningsfunktion. En anden omkostningsfunktion bruges til regression og klassifikationsopgaver. Målet for begge omkostningsfunktioner er at bestemme, hvilke grene har de mest ensartede responsværdier eller de mest homogene grene. Overvej, at du ønsker testdata af en bestemt klasse at følge bestemte stier, og dette giver intuitivt mening.

I forhold til omkostningsfunktionen for rekursiv binær split, er algoritmen, der bruges til at beregne omkostningerne, følgende:

sum(y – forudsigelse)^2

Forudsigelsen for en bestemt gruppe af datapunkter er gennemsnittet af responsværdierne for træningsdata for den gruppe. Alle datapunkterne køres gennem omkostningsfunktionen for at bestemme omkostningerne for alle mulige splittelse, og splittelsen med den laveste omkostning vælges.

Med hensyn til omkostningsfunktionen for klassifikation, er funktionen følgende:

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

Dette er Gini-scoren, og det er en måling af effekten af en split, baseret på, hvor mange eksempler af forskellige klasser der er i grupperne, der resulterer fra splittelsen. Med andre ord, det kvantificerer, hvor blandet grupperne er efter splittelsen. En optimal split er, når alle grupperne, der resulterer fra splittelsen, kun består af input fra én klasse. Hvis en optimal split er oprettet, vil “pk”-værdien være enten 0 eller 1, og G vil være lig med 0. Du kan måske gætte, at den værste split er en, hvor der er en 50-50-repræsentation af klasserne i splittelsen, i tilfælde af binær klassifikation. I dette tilfælde vil “pk”-værdien være 0,5, og G vil også være 0,5.

Splittelsesprocessen afsluttes, når alle datapunkter er blevet omdannet til blade og klassificeret. Dog kan du ønske at stoppe træets vækst tidligt. Store komplekse træer er tilbøjelige til at overfitte, men flere forskellige metoder kan bruges til at bekæmpe dette. En metode til at reducere overfitning er at specificere et minimum antal datapunkter, der skal bruges til at oprette et blad. En anden metode til at kontrollere for overfitning er at begrænse træet til en bestemt maksimal dybde, som kontrollerer, hvor lang en sti kan strække sig fra roden til et blad.

En anden proces, der er involveret i oprettelsen af beslutningstræer er beskæring. Beskæring kan hjælpe med at forbedre beslutningstræets præstation ved at fjerne grene, der indeholder funktioner, der har lidt prædikativ kraft/lidt betydning for modellen. På denne måde reduceres træets kompleksitet, og det bliver mindre sandsynligt, at det overfitter, og modellens prædikative nytte øges.

Når beskæring udføres, kan processen starte enten ved toppen af træet eller bunden af træet. Dog er den letteste metode til beskæring at starte med bladene og forsøge at fjerne noden, der indeholder den mest almindelige klasse i det blad. Hvis modellens nøjagtighed ikke forringes, når dette gøres, så behandles ændringen. Der er andre teknikker, der bruges til at udføre beskæring, men metoden, der er beskrevet ovenfor – reduceret fejlbeskæring – er sandsynligvis den mest almindelige metode til beslutningstræsbeskæring.

Overvejelser for brug af beslutningstræer

Beslutningstræer er ofte nyttige, når klassifikation skal udføres, men beregnings tid er en større begrænsning. Beslutningstræer kan gøre det klart, hvilke funktioner i de valgte datasets har den mest prædikative kraft. Desuden, i modsætning til mange maskinlæringsalgoritmer, hvor reglerne, der bruges til at klassificere data, kan være svære at fortolke, kan beslutningstræer frembringe fortolkelige regler. Beslutningstræer kan også bruge både kategoriske og kontinuerte variabler, hvilket betyder, at der kræves mindre forarbejdning i forhold til algoritmer, der kun kan håndtere én af disse variabeltyper.

Beslutningstræer tenderer ikke til at fungere meget godt, når de bruges til at bestemme værdierne af kontinuerte attributter. En anden begrænsning af beslutningstræer er, at når klassifikation udføres, og der er få trænings eksempler, men mange klasser, beslutningstræet tenderer til at være upræcist.