Introduksjon
Decision Trees (DTs) er en ikke-parametrisk overvåket læringsmetode som brukes for klassifisering og regresjon. Målet er å lage en modell som forutsier verdien av en målvariabel ved å lære enkle beslutningsregler utledet fra datafunksjonene.
Entropi
Målet med treningen er å finne de beste splittene i nodene for å finne det mest optimale treet. Delingene gjøres ved å bruke noen kriterier som: Entropi.
Det finnes mange definisjoner av entropi, for eksempel:
-
Entropi tilsvarer mengden informasjon som finnes i en informasjonskilde.
-
Entropi kan også sees på som tilfeldigheten eller måling av overraskelse i et sett.
-
Entropi er en metrikk som måler uforutsigbarheten eller urenheten i systemet.
I beslutningstrær vil vi vurdere entropi som et mål på renheten inne i en node. Målet med beslutningstremodellen er å redusere entropien til nodene ved hver splitt:
Dermed ønsker vi å maksimere forskjellen mellom entropien til foreldrenoden og entropien til undernodene. Denne forskjellen kalles Informasjonsgevinst.
Entropien $H$ til et sett $X$ er matematisk formulert som følger:
$$ H(X) = - \sum\limits_{x \in X} p(x) \log p(x) $$
Informasjonsgevinst
Informasjonsforsterkning er forskjellen mellom entropien til den overordnede noden og den veide summen av entropiene til chlidnodene, 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 populasjonen før delingen, den representerer den overordnede noden.
-
$X$ er variabelen vi ønsker å bruke for splittingen.
-
$x$ er en unik verdi av X.
-
$Y[X==x]$ er en delt liste med bare $x$-verdier.
la oss ta et skikkelig eksempel:
Vi skal beregne informasjonsgevinsten når vi deler den overordnede noden ved å bruke verdiene til X:
$$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$$
\
Først beregner vi entropien til foreldrenoden:
$$ 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 $$
\
Deretter skal vi beregne den interne sannsynligheten for hver barnnode etter splittelsen ved å bruke de unike verdiene til 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) $$
Som for eksempel:
-
$H(Y | X = Square)$ : representerer entropien til den første underordnede noden.
-
$H(Y | X = Circle)$ : representerer entropien til den andre barnenoden.
\
Vi starter med den første barnetnoden:
$$ 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 andre barnenoden:
$$ 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 slutt erstatter vi entropiene i informasjonsforsterkningsformelen:
$$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 nevnt før, er målet med en nodedeling å maksimere informasjonsgevinsten, og dermed minimere entropien i den resulterende barnenoden. For å gjøre dette, må vi prøve å dele noden med forskjellige sett med innganger $ X_1, X_2, \ldots, Xn $ og vi beholder bare splitten som maksimerer informasjonsgevinsten:
$$ X^{*} = \underset{X_i}{\operatorname{argmax}} IG(Y, X_i) $$
Når skal du slutte å splitte
Nodedelingen i beslutningstrær er rekursiv, så det må være et kriterium som vi kan bruke for å stoppe delingen. Dette er noen av de mest implementerte kriteriene:
-
Når noden er ren: H(node) = 0. Det er meningsløst å dele noden ytterligere.
-
Maksimalt antall dybder: Vi kan sette en maksimal dybde som modellen kan nå, det betyr at selv om noden ikke er ren, stoppes splittingen.
-
Minimum antall prøver per node: Vi kan også sette et minimum antall $N$ prøver per node. Hvis antall prøver per node er lik $N$, slutter vi å splitte selv om noden ikke er ren.
Ved slutten av treningen ( splittingen ), kalles hver node som er avhengig av slutten av beslutningstreet et "blad", fordi det ikke er en rot til noe undertre. Hvert blad vil representere utbytte klassen med flest prøver.
Konklusjon
Decision tree er en av de mest kjente maskinlæringsalgoritmene på grunn av sin effektivitet, intuitive bakgrunn og enkle implementering. Denne algoritmen kan videre brukes med numeriske uavhengige variabler ( Gaussian Decision Tree ), og den kan utvides til å løse regresjonsoppgaver også.
