Sprendimų medžio klasifikacija

Įvadas

Sprendimų medžiai (DT) yra neparametrinis prižiūrimas mokymosi metodas, naudojamas klasifikavimui ir regresijai. Tikslas yra sukurti modelį, kuris numatytų tikslinio kintamojo vertę, išmokus paprastas sprendimo taisykles, nustatytas iš duomenų ypatybių.

Entropija

Mokymų tikslas – surasti geriausius mazgų skilimus, siekiant rasti optimaliausią medį. Padalijimai atliekami naudojant kai kuriuos kriterijus, tokius kaip: Entropija.

Yra daug entropijos apibrėžimų, tokių kaip:

Entropija atitinka informacijos kiekį, esantį informacijos šaltinyje.
Entropija taip pat gali būti vertinama kaip atsitiktinumas arba netikėtumo matavimas rinkinyje.
Entropija yra metrika, kuri matuoja sistemos nenuspėjamumą ar priemaišas.

Sprendimų medžiuose entropiją laikysime mazgo grynumo matu. Sprendimų medžio modelio tikslas yra sumažinti mazgų entropiją kiekvieno padalijimo metu:

Taigi, mes norime maksimaliai padidinti skirtumą tarp pirminio mazgo ir antrinių mazgų entropijos. Šis skirtumas vadinamas Informacijos padidėjimu.

Aibės $X$ entropija $H$ matematiškai suformuluota taip:

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

Informacijos gavimas

Informacijos padidėjimas yra skirtumas tarp pirminio mazgo entropijos ir svertinės sumos chlid mazgų entropijų, todėl jį galima suformuluoti taip:

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

kur:

$H(.)$ yra entropija.
$Y$ yra populiacija prieš padalijimą, ji reiškia pirminį mazgą.
$X$ yra kintamasis, kurį norime naudoti padalijimui.
$x$ yra unikali X reikšmė.
$Y[X==x]$ yra išskaidytas sąrašas, kuriame yra tik $x$ reikšmės.

paimkime tinkamą pavyzdį:

Mes apskaičiuosime informacijos padidėjimą, kai padalysime pirminį mazgą naudodami X reikšmes:

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

Pirmiausia apskaičiuojame pirminio mazgo entropiją:

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

Tada mes apskaičiuosime kiekvieno antrinio mazgo vidinę tikimybę po padalijimo, naudodami unikalias X reikšmes:

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

Tokie kaip:

$H(Y | X = kvadratas)$ : reiškia pirmojo antrinio mazgo entropiją.
$H(Y | X = apskritimas)$ : reiškia antrojo antrinio mazgo entropiją.

Pradedame nuo pirmojo antrinio mazgo:

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

Ir tada antrasis vaiko mazgas:

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

Galiausiai informacijos gavimo formulėje pakeičiame entropijas:

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

Kaip minėta anksčiau, mazgo padalijimo tikslas yra maksimaliai padidinti informacijos gavimą ir taip sumažinti entropiją gautame antriniame mazge. Norėdami tai padaryti, turime pabandyti padalinti mazgą su skirtingais įvesties rinkiniais $X_1, X_2, \ldots, Xn$ ir pasiliksime tik tą padalijimą, kuris maksimaliai padidina informacijos gavimą:

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

Kada nustoti skaidytis

Mazgo padalijimas sprendimų medžiuose yra rekursyvus, todėl turi būti kriterijai, kuriuos galėtume naudoti, kad sustabdytume skaidymą. Štai keli dažniausiai taikomi kriterijai:

Kai mazgas yra grynas: H(mazgas) = 0. Beprasmiška mazgą skaidyti toliau.
Maksimalus gylio skaičius: Galime nustatyti maksimalų gylį, kurį modelis gali pasiekti, tai reiškia, kad net jei mazgas nėra grynas, skilimas sustabdomas.
Minimalus mėginių skaičius viename mazge: Taip pat galime nustatyti minimalų $N$ mėginių skaičių viename mazge. Jei pavyzdžių skaičius viename mazge yra lygus $N$ , mes nustojame skaidyti, net jei mazgas nėra grynas.

Treniruotės pabaigoje (skilimas) kiekvienas mazgas, kuris remiasi sprendimų medžio pabaiga, vadinamas „lapu“, nes jis nėra jokio pomedžio šaknis. Kiekvienas lapas parodys daugiausiai mėginių turinčią klasę.

Išvada

Sprendimų medis yra vienas žinomiausių mašininio mokymosi algoritmų dėl savo efektyvumo, intuityvaus pagrindo ir paprasto įgyvendinimo. Šis algoritmas gali būti toliau naudojamas su skaitiniais nepriklausomais kintamaisiais (Gauso sprendimų medis) ir gali būti išplėstas sprendžiant regresijos užduotis.