Döntési fa osztályozása

osztályozás
döntési fa
előrejelzési modell

Frissítve a September 03, 2024 -en97 percek olvasása

Döntési fa osztályozása cover image

Bevezetés

A döntési fák (DT) egy nem paraméteres, felügyelt tanulási módszer, amelyet osztályozásra és regresszióra használnak. A cél egy olyan modell létrehozása, amely az adatjellemzőkből levonható egyszerű döntési szabályok megtanulásával megjósolja egy célváltozó értékét.

Entrópia

A tréning célja, hogy megtaláljuk a csomópontokban a legjobb spliteket, hogy megtaláljuk a legoptimálisabb fát. A felosztások bizonyos kritériumok alapján történnek, mint például: Entrópia.

Az entrópiának számos definíciója létezik, például:

  • Az entrópia az információforrásban található információ mennyiségének felel meg.

  • Az entrópia úgy is felfogható, mint a véletlenszerűség vagy a meglepetés mérése egy halmazban.

  • Az entrópia egy olyan mérőszám, amely a rendszer kiszámíthatatlanságát vagy szennyezettségét méri.

entropy

A döntési fákban az entrópiát a csomóponton belüli tisztaság mértékének tekintjük. A döntési fa modell célja, hogy csökkentse a csomópontok entrópiáját minden felosztásnál:

entropy_reductioin

Így szeretnénk maximalizálni a különbséget a szülő csomópont entrópiája és a gyermek csomópontok entrópiája között. Ezt a különbséget Információs nyereség-nak nevezik.

Egy XX halmaz HH entrópiája matematikailag a következőképpen van megfogalmazva:

H(X)=_xXp(x)logp(x)H(X) = - \sum\limits\_{x \in X} p(x) \log p(x)

Információszerzés

Az információnyereség a különbség a szülőcsomópont entrópiája és a chlid csomópontok entrópiáinak súlyozott összege között, így a következőképpen fogalmazható meg:

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])

ahol:

  • H(.)H(.) az entrópia.

  • YY a felosztás előtti populáció, a szülőcsomópontot jelöli.

  • XX az a változó, amelyet a felosztáshoz szeretnénk használni.

  • xx az X egyedi értéke.

  • A Y[X==x]Y[X==x] egy felosztott lista, csak xx értékekkel.

vegyünk egy megfelelő példát:

entropy_reductioin

Az információs nyereséget akkor fogjuk kiszámítani, amikor a szülőcsomópontot felosztjuk X értékeivel:

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)

\

Először kiszámítjuk a szülőcsomópont entrópiáját:

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

\

Ezután kiszámítjuk az egyes gyermekcsomópontok belső valószínűségét a felosztás után az X egyedi értékeinek felhasználásával:

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)

Mint például:

  • H(YX=neˊgyzet)H(Y | X = négyzet) : az első gyermek csomópont entrópiáját jelöli.

  • H(YX=Circle)H(Y | X = Circle) : a második gyermekcsomópont entrópiáját jelöli.

\

Kezdjük az első gyermek csomóponttal:

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

\

És akkor a második gyermek csomópont:

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

\

Végül behelyettesítjük az entrópiákat az Information Gain képletben:

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

\

\

Amint korábban említettük, a csomópont-felosztás célja az információnyereség maximalizálása, és ezáltal az entrópia minimalizálása az eredményül kapott gyermekcsomópontban. Ehhez meg kell próbálnunk felosztani a csomópontot különböző bemeneti készletekkel: X1,X2,,XnX_1, X_2, \ldots, Xn, és csak azt a felosztást tartjuk meg, amely maximalizálja az információnyereséget:

X\*=argmaxXiIG(Y,Xi)X^{\*} = \underset{X_i}{\operatorname{argmax}} IG(Y, X_i)

Mikor kell abbahagyni a felosztást

A döntési fákban a csomópont felosztása rekurzív, ezért kell lennie egy kritériumnak, amellyel megállíthatjuk a felosztást. Íme néhány a leginkább alkalmazott kritériumok közül:

  • Ha a csomópont tiszta: H(csomópont) = 0. Felesleges tovább felosztani a csomópontot.

  • Maximális mélységszám: Beállíthatunk egy maximális mélységet, amit a modell elérhet, ami azt jelenti, hogy ha a csomópont nem tiszta, akkor is megáll a hasítás.

  • Minimális mintaszám csomópontonként: Beállíthatunk egy csomópontonkénti minimális mintaszámot is, NN. Ha a minták száma csomópontonként NN, akkor leállítjuk a felosztást, még akkor is, ha a csomópont nem tiszta.

A betanítás (felosztás) végére minden csomópontot, amely a döntési fa végére támaszkodik, "Leaf"-nek nevezik, mert nem gyökere egyik részfának sem. Minden levél a legtöbb mintával rendelkező osztályt képviseli.

Következtetés

Hatékonyságának, intuitív hátterének és egyszerű megvalósításának köszönhetően a döntési fa az egyik leghíresebb gépi tanulási algoritmus. Ez az algoritmus tovább használható numerikus független változókkal (Gaussian Decision Tree), és kiterjeszthető regressziós feladatok megoldására is.

Fontolja meg a technológiai karriert - Tudjon meg többet a CLA online bootcamps -ról

Career Services background pattern

Karrier szolgáltatások

Contact Section background image

Maradjunk kapcsolatban

Code Labs Academy © 2025 Minden jog fenntartva.