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.
