Úvod
Rozhodovacie stromy (DT) sú neparametrickou kontrolovanou učebnou metódou používanou na klasifikáciu a regresiu. Cieľom je vytvoriť model, ktorý predpovedá hodnotu cieľovej premennej učením sa jednoduchých rozhodovacích pravidiel odvodených z dátových funkcií.
Entropia
Cieľom tréningu je nájsť najlepšie rozdelenia v uzloch, aby ste našli najoptimálnejší strom. Rozdelenie sa vykonáva pomocou niektorých kritérií, ako napríklad: Entropia.
Existuje mnoho definícií entropie, napr.
-
Entropia zodpovedá množstvu informácií obsiahnutých v zdroji informácií.
-
Entropiu možno vnímať aj ako náhodnosť alebo meranie prekvapenia v súbore.
-
Entropia je metrika, ktorá meria nepredvídateľnosť alebo nečistotu v systéme.
V rozhodovacích stromoch budeme entropiu považovať za mieru čistoty vo vnútri uzla. Cieľom modelu rozhodovacieho stromu je znížiť entropiu uzlov pri každom rozdelení:
Chceme teda maximalizovať rozdiel medzi entropiou rodičovského uzla a entropiou podriadených uzlov. Tento rozdiel sa nazýva Informačný zisk.
Entropia $H$ množiny $X$ je matematicky formulovaná takto:
$$ H(X) = - \sum\limits_{x \in X} p(x) \log p(x) $$
Získavanie informácií
Informačný zisk je rozdiel medzi entropiou nadradeného uzla a váženým súčtom entropií dcérskych uzlov, a preto ho možno formulovať takto:
$$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])$$
kde:
-
$H(.)$ je entropia.
-
$Y$ je populácia pred rozdelením, predstavuje nadradený uzol.
-
$X$ je premenná, ktorú chceme použiť na rozdelenie.
-
$x$ je jedinečná hodnota X.
-
$Y[X==x]$ je rozdelený zoznam iba s hodnotami $x$.
zoberme si správny príklad:
Vypočítame informačný zisk, keď rozdelíme nadradený uzol pomocou hodnôt X:
$$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$$
\
Najprv vypočítame entropiu nadradeného uzla:
$$ 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 $$
\
Potom vypočítame vnútornú pravdepodobnosť každého dcérskeho uzla po rozdelení pomocou jedinečných hodnôt 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) $$
Ako napríklad:
-
$H(Y | X = štvorec)$ : predstavuje entropiu prvého dcérskeho uzla.
-
$H(Y | X = Kruh)$ : predstavuje entropiu druhého dcérskeho uzla.
\
Začneme prvým podriadeným uzlom:
$$ 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 $$
\
A potom druhý detský uzol:
$$ 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 $$
\
Nakoniec dosadíme entropie do vzorca Information Gain:
$$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 $$
\
\
Ako už bolo uvedené, cieľom rozdelenia uzla je maximalizovať informačný zisk, a teda minimalizovať entropiu vo výslednom podradenom uzle. Aby sme to dosiahli, musíme sa pokúsiť rozdeliť uzol s rôznymi sadami vstupov $ X_1, X_2, \ldots, Xn $ a ponecháme len rozdelenie, ktoré maximalizuje zisk informácií:
$$ X^{*} = \underset{X_i}{\operatorname{argmax}} IG(Y, X_i) $$
Kedy prestať deliť
Rozdelenie uzlov v rozhodovacích stromoch je rekurzívne, takže musia existovať kritériá, ktoré môžeme použiť na zastavenie rozdelenia. Toto sú niektoré z najviac implementovaných kritérií:
-
Keď je uzol čistý: H(uzol) = 0. Je zbytočné uzol ďalej rozdeľovať.
-
Maximálny počet hĺbky: Môžeme nastaviť maximálnu hĺbku, ktorú môže model dosiahnuť, to znamená, že aj keď uzol nie je čistý, štiepanie sa zastaví.
-
Minimálny počet vzoriek na uzol: Môžeme tiež nastaviť minimálny počet $N$ vzoriek na uzol. Ak je počet vzoriek na uzol rovný $N$, potom prestaneme deliť, aj keď uzol nie je čistý.
Na konci tréningu (rozdelenie) sa každý uzol, ktorý sa spolieha na koniec rozhodovacieho stromu, nazýva "list", pretože to nie je koreň žiadneho podstromu. Každý list bude reprezentovať výnos triedy s najväčším počtom vzoriek.
Záver
Rozhodovací strom je jedným z najznámejších algoritmov strojového učenia vďaka svojej efektívnosti, intuitívnemu zázemiu a jednoduchej implementácii. Tento algoritmus možno ďalej použiť s numerickými nezávislými premennými ( Gaussov rozhodovací strom ) a možno ho rozšíriť aj na riešenie regresných úloh.
