Päätöspuun luokitus

Johdanto

Päätöspuut (DT) ovat ei-parametrinen ohjattu oppimismenetelmä, jota käytetään luokitukseen ja regressioon. Tavoitteena on luoda malli, joka ennustaa kohdemuuttujan arvon oppimalla dataominaisuuksista pääteltyjä yksinkertaisia päätössääntöjä.

Haje

Harjoittelun tavoitteena on löytää parhaat splitit solmuista optimaalisen puun löytämiseksi. Splitit tehdään käyttämällä joitain kriteerejä, kuten: Entropia.

Entropialle on olemassa monia määritelmiä, kuten:

Entropia vastaa tietolähteen sisältämän tiedon määrää.
Entropia voidaan nähdä myös sattumanvaraisuutena tai yllätyksen mittaamisena joukossa.
Entropia on mittari, joka mittaa järjestelmän arvaamattomuutta tai epäpuhtautta.

Päätöspuissa entropiaa pidetään solmun sisällä olevan puhtauden mittana. Päätöspuumallin tavoitteena on vähentää solmujen entropiaa jokaisessa jaossa:

Siten haluamme maksimoida eron pääsolmun ja lapsisolmun entropian välillä. Tätä eroa kutsutaan Tiedon vahvistukseksi.

Joukon $X$ entropia $H$ on matemaattisesti muotoiltu seuraavasti:

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

Tiedon saaminen

Informaatiovahvistus on ero emosolmun entropianjachlid-solmujen entropioiden****painotetun summan** välillä, joten se voidaan muotoilla seuraavasti:

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

missä:

$H(.)$ on entropia.
$Y$ on populaatio ennen jakoa, se edustaa pääsolmua.
$X$ on muuttuja, jota haluamme käyttää jakamiseen.
$x$ on X:n yksilöllinen arvo.
$Y[X==x]$ on jaettu luettelo, jossa on vain $x$ arvoja.

Otetaanpa oikea esimerkki:

Aiomme laskea tietovahvistuksen, kun jaamme pääsolmun X:n arvoilla:

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

Ensin lasketaan pääsolmun entropia:

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

Sitten aiomme laskea kunkin lapsisolmun sisäisen todennäköisyyden jaon jälkeen käyttämällä X:n yksilöllisiä arvoja:

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

Kuten:

$H(Y | X = Neliö)$ : edustaa ensimmäisen lapsisolmun entropiaa.
$H(Y | X = ympyrä)$ : edustaa toisen lapsisolmun entropiaa.

Aloitamme ensimmäisestä lapsisolmusta:

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

Ja sitten toinen lapsisolmu:

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

Lopuksi korvaamme entropiat Information Gain -kaavassa:

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

Kuten aiemmin todettiin, solmujaon tavoitteena on maksimoida tiedon vahvistus ja siten minimoida tuloksena olevan lapsisolmun entropia. Tätä varten meidän on yritettävä jakaa solmu erilaisilla tulosarjoilla $X_1, X_2, \ldots, Xn$ ja säilytetään vain jako, joka maksimoi tiedonsaannin:

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

Milloin jakaminen lopetetaan

Solmun jakaminen päätöspuissa on rekursiivinen, joten täytyy olla kriteerit, joita voimme käyttää jakamisen lopettamiseksi. Nämä ovat joitain eniten käytetyistä kriteereistä:

Kun solmu on puhdas: H(solmu) = 0. On turhaa jakaa solmua enempää.
Syvyyden maksimimäärä: Voimme asettaa suurimman syvyyden, jonka malli voi saavuttaa, se tarkoittaa, että vaikka solmu ei olisi puhdas, halkaisu pysähtyy.
Nytteiden vähimmäismäärä solmua kohti: Voimme myös asettaa näytteiden vähimmäismäärän $N$ solmua kohti. Jos näytteiden määrä solmua kohti on yhtä suuri kuin $N$ , lopetamme jakamisen, vaikka solmu ei olisi puhdas.

Harjoittelun loppuun mennessä (jakaminen) jokaista päätöspuun loppuun luottavaa solmua kutsutaan "Lehdeksi", koska se ei ole minkään alipuun juuri. Jokainen lehti edustaa sitä luokkaa, jolla on eniten näytteitä.

Johtopäätös

Päätöspuu on yksi tunnetuimmista koneoppimisalgoritmeista sen tehokkuuden, intuitiivisen taustan ja yksinkertaisen toteutuksen ansiosta. Tätä algoritmia voidaan käyttää edelleen numeeristen riippumattomien muuttujien ( Gaussin päätöspuu ) kanssa, ja sitä voidaan laajentaa ratkaisemaan myös regressiotehtäviä.