Klassifikation af beslutningstræ

Introduktion

Decision Trees (DT'er) er en ikke-parametrisk overvåget læringsmetode, der bruges til klassificering og regression. Målet er at skabe en model, der forudsiger værdien af en målvariabel ved at lære simple beslutningsregler udledt af datafunktionerne.

Entropi

Målet med træningen er at finde de bedste spalter i noderne for at finde det mest optimale træ. Opdelingerne udføres ved hjælp af nogle kriterier såsom: Entropi.

Der findes mange definitioner af entropi såsom:

Entropi svarer til mængden af information indeholdt i en informationskilde.
Entropi kan også ses som tilfældigheden eller måling af overraskelse i et sæt.
Entropi er en metrik, der måler uforudsigeligheden eller urenheden i systemet.

I beslutningstræer vil vi betragte entropi som et mål for renheden inde i en knude. Målet med beslutningstræmodellen er at reducere nodernes entropi ved hver opdeling:

Vi ønsker således at maksimere forskellen mellem entropien af den overordnede node og entropien af de underordnede noder. Denne forskel kaldes Informationsgevinsten.

Entropien $H$ af et sæt $X$ er matematisk formuleret som følger:

H(X) = - \sum\limits\_{x \in X} p(x) \log p(x)

Informationsgevinst

Informationsgevinst er forskellen mellem entropien af moderknuden og den vægtede sum af entropierne af chlidknuderne, og den kan derfor formuleres som følger:

$IG(Y, X) = H(Y) - \sum_{x \in unique(X)} P(x|X) \times H(Y | X = x)$

$= H(Y) - \sum_{x \in unique(X)} \frac{X.count(x)}{len(X)} \times H(Y[X == x])$

hvor:

$H(.)$ er entropien.
$Y$ er populationen før opdelingen, den repræsenterer den overordnede node.
$X$ er den variabel, vi ønsker at bruge til opdelingen.
$x$ er en unik værdi af X.
$Y[X==x]$ er en opdelt liste med kun $x$ værdier.

lad os tage et ordentligt eksempel:

Vi skal beregne informationsforstærkningen, når vi dividerer den overordnede node ved at bruge værdierne af X:

$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$

Først beregner vi entropien af moderknuden:

$H(parent) = - P(Y=Blue) \times \log P(Y=Blue) - P(Y=Yellow) \times \log P(Y=Yellow)$

$= - \frac{11}{21} \times \log(\frac{11}{21}) - \frac{10}{21} \times \log(\frac{10}{21}) = 0.3$

Derefter skal vi beregne den interne sandsynlighed for hver underordnet node efter opdelingen ved at bruge de unikke værdier af X:

$unique(X) = [Circle, Square]$

$\sum\_{x \in unique(X)} P(x|X) \times H(Y | X = x) = P(Square|X) \times H(Y | X = Square)$

$+ P(Circle|X) \times H(Y | X = Circle)$

$= \frac{9}{21} \times H(Y | X = Square) + \frac{12}{21} \times H(Y | X = Circle)$

Såsom:

$H(Y | X = Square)$ : repræsenterer entropien af den første underordnede node.
$H(Y | X = Circle)$ : repræsenterer entropien af den anden underknude.

Vi starter med den første børneknude:

$H(Y | X = Square) = - P(Y=Blue | X = Square) \times \log P(Y=Blue| X = Square)$

$- P(Y=Yellow| X = Square) \times \log P(Y=Yellow| X = Square)$

$= - \frac{7}{9} \times \log\frac{7}{9} - \frac{2}{9} \times \log\frac{2}{9} = 0.23$

Og så den anden børneknude:

$H(Y | X = Circle) = - P(Y=Blue | X = Circle) \times \log P(Y=Blue| X = Circle)$

$- P(Y=Yellow| X = Circle) \times \log P(Y=Yellow| X = Circle)$

$= - \frac{4}{12} \times \log\frac{4}{12} - \frac{8}{12} \times \log\frac{8}{12} = 0.28$

Til sidst erstatter vi entropierne i formlen for informationsforøgelse:

$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$

$= 0.3 - \frac{9}{21} \times 0.23 - \frac{12}{21} \times 0.28 = 0.041$

Som nævnt før er formålet med en nodeopdeling at maksimere informationsforstærkningen og dermed minimere entropien i den resulterende børneknude. For at gøre dette skal vi prøve at opdele noden med forskellige sæt af input $X_1, X_2, \ldots, Xn$ , og vi beholder kun den opdeling, der maksimerer informationsgevinsten:

$X^{\*} = \underset{X_i}{\operatorname{argmax}} IG(Y, X_i)$

Hvornår skal man stoppe opdelingen

Nodeopdelingen i beslutningstræer er rekursiv, så der skal være et kriterium, som vi kan bruge for at stoppe opdelingen. Disse nogle af de mest implementerede kriterier:

Når noden er ren: H(node) = 0. Det er meningsløst at opdele noden yderligere.
Maksimalt antal dybder: Vi kan indstille en maksimal dybde, som modellen kan nå, det betyder, at selvom knudepunktet ikke er rent, stoppes opdelingen.
Minimum antal prøver pr. node: Vi kan også indstille et minimumsantal $N$ af prøver pr. node. Hvis antallet af samples pr. node er lig med $N$ , stopper vi opdelingen, selvom noden ikke er ren.

Ved slutningen af træningen (opdelingen) kaldes hver knude, der er afhængig af enden af beslutningstræet, et "blad", fordi det ikke er en rod til noget undertræ. Hvert blad repræsenterer udbyttet for klassen med flest prøver.

Konklusion

Decision tree er en af de mest berømte maskinlæringsalgoritmer på grund af dens effektivitet, intuitive baggrund og enkle implementering. Denne algoritme kan yderligere bruges med numeriske uafhængige variable (Gaussian Decision Tree), og den kan udvides til også at løse regressionsopgaver.