Klasifikace rozhodovacího stromu

Ú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.