Klasifikace rozhodovacího stromu

klasifikace
rozhodovací strom
predikční model

Aktualizováno na September 03, 202497 minuty čte

Klasifikace rozhodovacího stromu cover image

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

entropy

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í:

entropy_reductioin

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 HH množiny XX je matematicky formulována takto:

H(X)=_xXp(x)logp(x)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)xunique(X)P(xX)×H(YX=x)IG(Y, X) = H(Y) - \sum_{x \in unique(X)} P(x|X) \times H(Y | X = x)

=H(Y)xunique(X)X.count(x)len(X)×H(Y[X==x])= H(Y) - \sum_{x \in unique(X)} \frac{X.count(x)}{len(X)} \times H(Y[X == x])

kde:

  • H(.)H(.) je entropie.

  • YY je populace před rozdělením, představuje nadřazený uzel.

  • XX je proměnná, kterou chceme použít pro rozdělení.

  • xx je jedinečná hodnota X.

  • Y[X==x]Y[X==x] je rozdělený seznam pouze s hodnotami xx.

vezměme si správný příklad:

entropy_reductioin

Budeme vypočítat informační zisk, když rozdělíme nadřazený uzel pomocí hodnot X:

IG(parent,X)=H(parent)xunique(X)P(xX)×H(parentX=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)×logP(Y=Blue)P(Y=Yellow)×logP(Y=Yellow)H(parent) = - P(Y=Blue) \times \log P(Y=Blue) - P(Y=Yellow) \times \log P(Y=Yellow)

=1121×log(1121)1021×log(1021)=0.3= - \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]unique(X) = [Circle, Square]

_xunique(X)P(xX)×H(YX=x)=P(SquareX)×H(YX=Square)\sum\_{x \in unique(X)} P(x|X) \times H(Y | X = x) = P(Square|X) \times H(Y | X = Square)

+P(CircleX)×H(YX=Circle)+ P(Circle|X) \times H(Y | X = Circle)

=921×H(YX=Square)+1221×H(YX=Circle)= \frac{9}{21} \times H(Y | X = Square) + \frac{12}{21} \times H(Y | X = Circle)

Jako:

  • H(YX=cˇtverec)H(Y | X = čtverec) : představuje entropii prvního podřízeného uzlu.

  • H(YX=Kruh)H(Y | X = Kruh) : představuje entropii druhého podřízeného uzlu.

\

Začneme prvním podřízeným uzlem:

H(YX=Square)=P(Y=BlueX=Square)×logP(Y=BlueX=Square)H(Y | X = Square) = - P(Y=Blue | X = Square) \times \log P(Y=Blue| X = Square)

P(Y=YellowX=Square)×logP(Y=YellowX=Square)- P(Y=Yellow| X = Square) \times \log P(Y=Yellow| X = Square)

=79×log7929×log29=0.23= - \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(YX=Circle)=P(Y=BlueX=Circle)×logP(Y=BlueX=Circle)H(Y | X = Circle) = - P(Y=Blue | X = Circle) \times \log P(Y=Blue| X = Circle)

P(Y=YellowX=Circle)×logP(Y=YellowX=Circle)- P(Y=Yellow| X = Circle) \times \log P(Y=Yellow| X = Circle)

=412×log412812×log812=0.28= - \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)xunique(X)P(xX)×H(parentX=x)IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)

=0.3921×0.231221×0.28=0.041= 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ů X1,X2,,XnX_1, X_2, \ldots, Xn a ponecháme pouze rozdělení, které maximalizuje zisk informací:

X\*=argmaxXiIG(Y,Xi)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 NN vzorků na uzel. Pokud je počet vzorků na uzel roven NN, 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.

Zvažte technickou kariéru - dozvědět se více o online bootcampech CLA

Career Services background pattern

Kariérní služby

Contact Section background image

Zůstaňme v kontaktu

Code Labs Academy © 2025 Všechna práva vyhrazena.