Döntési fa osztályozása

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.

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:

Í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 $X$ halmaz $H$ entrópiája matematikailag a következőképpen van megfogalmazva:

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

ahol:

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

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

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

• $x$ az X egyedi értéke.

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

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

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) - \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) \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$

\

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

$\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)$

Mint például:

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

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

\

Kezdjük az első gyermek csomóponttal:

$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$

\

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

$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$

\

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

$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$

\

\

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: $X_1, X_2, \ldots, Xn$, és csak azt a felosztást tartjuk meg, amely maximalizálja az információnyereséget:

$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, $N$. Ha a minták száma csomópontonként $N$, 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.