Erabakien Zuhaitz Sailkapena

Sarrera

Erabakien Zuhaitzak (DT) sailkatzeko eta erregresiorako erabiltzen diren gainbegiratu gabeko ikaskuntza metodo ez-parametrikoak dira. Helburua aldagai baten balioa iragartzen duen eredu bat sortzea da, datuen ezaugarrietatik ondorioztatzen diren erabaki-arau errazak ikasiz.

Entropia

Prestakuntzaren helburua nodoetan zatiketa onenak aurkitzea da, zuhaitzik onena aurkitzeko. Zatiketak irizpide batzuk erabiliz egiten dira, hala nola: Entropia.

Entropiaren definizio asko daude, hala nola:

Entropia informazio iturri batean dagoen informazio kantitateari dagokio.
Entropia multzo batean ausazkotasuna edo sorpresaren neurketa gisa ere ikus daiteke.
Entropia sistemaren ezustekoa edo ezpurutasuna neurtzen duen metrika da.

Erabaki-zuhaitzetan, entropia nodo baten barruko garbitasunaren neurritzat hartuko dugu. Erabaki zuhaitzaren ereduaren helburua zatiketa bakoitzean nodoen entropia murriztea da:

Horrela, nodo nagusiaren eta nodo semeen entropiaren arteko aldea maximizatu nahi dugu. Desberdintasun horri Informazio irabazia deitzen zaio.

$X$ multzo baten $H$ entropia matematikoki honela formulatzen da:

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

Informazio irabazia

Informazioaren irabazia nodo nagusiaren entropiaren eta umeen nodoen entropienen batura haztatua arteko diferentzia da, eta, beraz, honela formula daiteke:

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

non:

$H(.)$ entropia da.
$Y$ zatitu aurreko populazioa da, nodo nagusia adierazten du.
$X$ zatiketa egiteko erabili nahi dugun aldagaia da.
$x$ X-ren balio bakarra da.
$Y[X==x]$ $x$ balioak soilik dituen zatitutako zerrenda bat da.

har dezagun adibide egoki bat:

Nodo nagusia zatitzen dugunean Informazio-irabazia kalkulatuko dugu X-ren balioak erabiliz:

$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$

Lehenik eta behin, nodo nagusiaren entropia kalkulatuko dugu:

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

Ondoren, zatitu ondoren nodo ume bakoitzaren barne probabilitatea kalkulatuko dugu X-ren balio bakarrak erabiliz:

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

Hala nola:

$H(Y | X = Karratua)$ : lehen nodo semearen entropia adierazten du.
$H(Y | X = Zirkulua)$ : bigarren nodo semearen entropia adierazten du.

Lehenengo seme-nodoarekin hasiko gara:

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

Eta gero bigarren nodo semea:

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

Azkenik, informazio-irabaziaren formulan entropiak ordezkatzen ditugu:

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

Lehen esan bezala, nodo zatiketaren helburua Informazio-irabazia maximizatzea da, eta, horrela, ondoriozko nodo seme-alaben entropia gutxitzea. Horretarako, nodoa $X_1, X_2, \ldots, Xn$ sarrera-multzo ezberdinekin zatitzen saiatu behar dugu eta Informazio-irabazia maximizatzen duen zatiketa bakarrik mantentzen dugu:

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

Noiz utzi zatitzea

Erabaki-zuhaitzetako nodoen zatiketa errekurtsiboa da, beraz, zatiketa geldiarazteko erabili dezakegun irizpide bat egon behar da. Hauek dira gehien inplementatutako irizpideetako batzuk:

Nodoa hutsa denean: H(nodoa) = 0. Alferrik da nodoa gehiago zatitzea.
Sakonera kopuru maximoa: Ereduak lor dezakeen sakonera maximoa ezarri dezakegu, esan nahi du nodoa hutsa ez bada ere zatiketa gelditu egiten dela.
Nodo bakoitzeko gutxieneko lagin kopurua: Nodo bakoitzeko $N$ lagin gutxieneko kopurua ere ezar dezakegu. Nodo bakoitzeko lagin kopurua $N$ ren berdina bada, zatitzeari utziko diogu nodoa hutsa ez bada ere.

Entrenamenduaren amaieran ( zatiketa ), erabaki-zuhaitzaren amaieran oinarritzen den nodo bakoitzari "Hosto" deitzen zaio, ez baita inongo azpizuhaitzaren erroa. Hosto bakoitzak lagin gehien dituen klasearen etekina irudikatuko du.

Ondorioa

Erabakien zuhaitza ikaskuntza automatikoko algoritmo ospetsuenetako bat da bere eraginkortasunagatik, atzeko plano intuitiboagatik eta ezarpen sinpleagatik. Algoritmo hau zenbakizko aldagai independenteekin ere erabil daiteke ( Gaussian Decision Tree ), eta heda daiteke erregresio-zereginak ebazteko ere.