Klasifikace rozhodovacího stromu
Aktualizováno na September 03, 2024 4 minuty čte

Úvod
Rozhodovací stromy (DT) jsou neparametrickou řízenou učební metodou používanou pro klasifikaci a regresi. Cílem je vytvořit model, který předpovídá hodnotu cílové proměnné učením jednoduchých rozhodovacích pravidel odvozených z datových vlastností.
Entropie
Cílem tréninku je najít nejlepší splity v uzlech za účelem nalezení nejoptimálnějšího stromu. Rozdělení se provádí pomocí některých kritérií, jako je: Entropie.
Existuje mnoho definic entropie, např.
-
Entropie odpovídá množství informací obsažených ve zdroji informací.
-
Entropii lze také chápat jako náhodnost nebo měření překvapení v sadě.
-
Entropie je metrika, která měří nepředvídatelnost nebo nečistotu v systému.
V rozhodovacích stromech budeme entropii uvažovat jako míru čistoty uvnitř uzlu. Cílem modelu rozhodovacího stromu je snížit entropii uzlů při každém rozdělení:
Chceme tedy maximalizovat rozdíl mezi entropií nadřazeného uzlu a entropií podřízených uzlů. Tento rozdíl se nazývá Informační zisk.
Entropie $H$ množiny $X$ je matematicky formulována takto:
$$ H(X) = - \sum\limits_{x \in X} p(x) \log p(x) $$
Informační zisk
Informační zisk je rozdíl mezi entropií nadřazeného uzlu a váženým součtem entropií chlidových uzlů, a lze jej tedy formulovat následovně:
$$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 entropie.
-
$Y$ je populace před rozdělením, představuje nadřazený uzel.
-
$X$ je proměnná, kterou chceme použít pro rozdělení.
-
$x$ je jedinečná hodnota X.
-
$Y[X==x]$ je rozdělený seznam pouze s hodnotami $x$.
vezměme si správný příklad:
Budeme vypočítat informační zisk, když rozdělíme nadřazený uzel pomocí hodnot X:
$$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$$
\
Nejprve vypočítáme entropii nadřazeného uzlu:
$$ 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 $$
\
Poté vypočítáme vnitřní pravděpodobnost každého podřízeného uzlu po rozdělení pomocí jedinečných hodnot 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) $$
Jako:
-
$H(Y | X = čtverec)$ : představuje entropii prvního podřízeného uzlu.
-
$H(Y | X = Kruh)$ : představuje entropii druhého podřízeného uzlu.
\
Začneme prvním podřízeným uzlem:
$$ 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 pak druhý podřízený uzel:
$$ 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 $$
\
Nakonec dosadíme entropie do vzorce 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 $$
\
\
Jak bylo uvedeno dříve, cílem rozdělení uzlů je maximalizovat informační zisk, a tím minimalizovat entropii ve výsledném podřízeném uzlu. Abychom to udělali, musíme zkusit rozdělit uzel různými sadami vstupů $ X_1, X_2, \ldots, Xn $ a ponecháme pouze rozdělení, které maximalizuje zisk informací:
$$ X^{*} = \underset{X_i}{\operatorname{argmax}} IG(Y, X_i) $$
Kdy přestat rozdělovat
Dělení uzlů v rozhodovacích stromech je rekurzivní, takže musí existovat kritéria, která můžeme použít, abychom rozdělení zastavili. Toto jsou některá z nejvíce implementovaných kritérií:
-
Když je uzel čistý: H(uzel) = 0. Nemá smysl uzel dále dělit.
-
Maximální počet hloubky: Můžeme nastavit maximální hloubku, které model může dosáhnout, to znamená, že i když uzel není čistý, dělení se zastaví.
-
Minimální počet vzorků na uzel: Můžeme také nastavit minimální počet $N$ vzorků na uzel. Pokud je počet vzorků na uzel roven $N$, přestaneme rozdělovat, i když uzel není čistý.
Na konci trénování (rozdělení) se každý uzel, který spoléhá na konec rozhodovacího stromu, nazývá „list“, protože není kořenem žádného podstromu. Každý list bude reprezentovat výnos třídy s největším počtem vzorků.
Závěr
Rozhodovací strom je jedním z nejznámějších algoritmů strojového učení díky své efektivitě, intuitivnímu pozadí a jednoduché implementaci. Tento algoritmus lze dále použít s numericky nezávislými proměnnými ( Gaussův rozhodovací strom ) a lze jej rozšířit i na řešení regresních úloh.