Uvod
Odločitvena drevesa (DT) so neparametrična nadzorovana učna metoda, ki se uporablja za klasifikacijo in regresijo. Cilj je ustvariti model, ki napoveduje vrednost ciljne spremenljivke z učenjem preprostih pravil odločanja, izpeljanih iz podatkovnih funkcij.
Entropija
Cilj usposabljanja je najti najboljše razcepe v vozliščih, da bi našli najbolj optimalno drevo. Razdelitve se izvedejo z uporabo nekaterih meril, kot so: Entropija.
Obstaja veliko definicij entropije, kot so:
-
Entropija ustreza količini informacij, ki jih vsebuje vir informacij.
-
Entropijo lahko razumemo tudi kot naključnost ali merjenje presenečenja v nizu.
-
Entropija je metrika, ki meri nepredvidljivost ali nečistost v sistemu.
V odločitvenih drevesih bomo entropijo obravnavali kot merilo čistosti znotraj vozlišča. Cilj modela odločitvenega drevesa je zmanjšati entropijo vozlišč pri vsaki delitvi:
Tako želimo čim bolj povečati razliko med entropijo nadrejenega vozlišča in entropijo podrejenih vozlišč. Ta razlika se imenuje Informacijski dobiček.
Entropija $H$ množice $X$ je matematično formulirana na naslednji način:
$$ H(X) = - \sum\limits_{x \in X} p(x) \log p(x) $$
Pridobivanje informacij
Dobiček informacij je razlika med entropijo nadrejenega vozlišča in ponderirano vsoto entropij vozlišč chlid, zato jo je mogoče formulirati na naslednji način:
$$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])$$
kje:
-
$H(.)$ je entropija.
-
$Y$ je populacija pred delitvijo, predstavlja nadrejeno vozlišče.
-
$X$ je spremenljivka, ki jo želimo uporabiti za razdelitev.
-
$x$ je edinstvena vrednost X.
-
$Y[X==x]$ je razdeljen seznam z vrednostmi samo $x$.
vzemimo pravi primer:
Dobiček informacij bomo izračunali, ko bomo nadrejeno vozlišče razdelili z uporabo vrednosti X:
$$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$$
\
Najprej izračunamo entropijo nadrejenega vozlišča:
$$ 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 $$
\
Nato bomo izračunali notranjo verjetnost vsakega podrejenega vozlišča po razdelitvi z uporabo edinstvenih vrednosti 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) $$
Kot naprimer:
-
$H(Y | X = Square)$ : predstavlja entropijo prvega podrejenega vozlišča.
-
$H(Y | X = krog)$: predstavlja entropijo drugega podrejenega vozlišča.
\
Začnemo s prvim podrejenim vozliščem:
$$ 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 $$
\
In nato drugo podrejeno vozlišče:
$$ 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 $$
\
Nazadnje nadomestimo entropije v formuli pridobivanja informacij:
$$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 $$
\
\
Kot je bilo že omenjeno, je cilj razdelitve vozlišča povečati pridobitev informacij in tako zmanjšati entropijo v nastalem podrejenem vozlišču. Da bi to naredili, moramo poskusiti razdeliti vozlišče z različnimi nizi vhodov $ X_1, X_2, \ldots, Xn $ in obdržati samo razdelitev, ki maksimira pridobitev informacij:
$$ X^{*} = \underset{X_i}{\operatorname{argmax}} IG(Y, X_i) $$
Kdaj prenehati z delitvijo
Razcepitev vozlišč v odločitvenih drevesih je rekurzivna, zato mora obstajati kriterij, ki ga lahko uporabimo, da zaustavimo razcepitev. To je nekaj najbolj izvajanih meril:
-
Ko je vozlišče čisto: H(vozlišče) = 0. Nesmiselno je nadaljnje razdeljevanje vozlišča.
-
Največje število globin: Nastavimo lahko največjo globino, ki jo model lahko doseže, kar pomeni, da se cepljenje ustavi, tudi če vozlišče ni čisto.
-
Najmanjše število vzorcev na vozlišče: Nastavimo lahko tudi najmanjše število $N$ vzorcev na vozlišče. Če je število vzorcev na vozlišče enako $N$, prenehamo z delitvijo, tudi če vozlišče ni čisto.
Do konca usposabljanja (razcepitev) se vsako vozlišče, ki se zanaša na konec odločitvenega drevesa, imenuje "list", ker ni koren nobenega poddrevesa. Vsak list bo predstavljal razred pridelka z največ vzorci.
Zaključek
Odločitveno drevo je eden najbolj znanih algoritmov strojnega učenja zaradi svoje učinkovitosti, intuitivnega ozadja in preproste izvedbe. Ta algoritem je mogoče nadalje uporabiti z numerično neodvisnimi spremenljivkami ( Gaussovo drevo odločanja ) in ga je mogoče razširiti tudi za reševanje regresijskih nalog.
