Lēmumu koka klasifikācija

Ievads

Lēmumu koki (DT) ir neparametriska uzraudzīta mācību metode, ko izmanto klasifikācijai un regresijai. Mērķis ir izveidot modeli, kas prognozē mērķa mainīgā vērtību, apgūstot vienkāršus lēmumu pieņemšanas noteikumus, kas izriet no datu iezīmēm.

Entropija

Apmācības mērķis ir atrast labākos sadalījumus mezglos, lai atrastu optimālāko koku. Sadalīšana tiek veikta, izmantojot dažus kritērijus, piemēram: Entropija.

Ir daudz entropijas definīciju, piemēram:

Entropija atbilst informācijas apjomam, ko satur informācijas avots.
Entropiju var uzskatīt arī par nejaušību vai pārsteiguma mērīšanu komplektā.
Entropija ir metrika, kas mēra sistēmas neparedzamību vai piemaisījumu.

Lēmumu kokos entropiju uzskatīsim par mezgla iekšpuses tīrības mēru. Lēmumu koka modeļa mērķis ir samazināt mezglu entropiju katrā sadalījumā:

Tādējādi mēs vēlamies palielināt atšķirību starp vecākmezgla entropiju un pakārtoto mezglu entropiju. Šo atšķirību sauc par Informācijas pieaugumu.

Kopas $X$ entropija $H$ ir matemātiski formulēta šādi:

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

Informācijas iegūšana

Informācijas ieguvums ir atšķirība starp sākotnējā mezgla entropiju un chlid mezglu entropiju svērto summu, un tādējādi to var formulēt šādi:

$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(.)$ ir entropija.
$Y$ ir populācija pirms sadalīšanas, tā apzīmē vecāku mezglu.
$X$ ir mainīgais, ko mēs vēlamies izmantot sadalīšanai.
$x$ ir unikāla X vērtība.
$Y[X==x]$ ir sadalīts saraksts ar tikai $x$ vērtībām.

ņemsim atbilstošu piemēru:

Mēs aprēķināsim informācijas pieaugumu, sadalot vecāku mezglu, izmantojot X vērtības:

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

Pirmkārt, mēs aprēķinām vecākmezgla entropiju:

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

Pēc tam mēs aprēķināsim katra bērna mezgla iekšējo varbūtību pēc sadalīšanas, izmantojot unikālās X vērtības:

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

Piemēram:

$H(Y | X = kvadrāts)$ : attēlo pirmā atvasinātā mezgla entropiju.
$H(Y | X = Circle)$ : attēlo otrā pakārtotā mezgla entropiju.

Mēs sākam ar pirmo bērna mezglu:

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

Un tad otrais bērna mezgls:

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

Visbeidzot, informācijas iegūšanas formulā mēs aizstājam 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$

Kā minēts iepriekš, mezgla sadalīšanas mērķis ir maksimāli palielināt informācijas ieguvi un tādējādi samazināt entropiju iegūtajā bērnu mezglā. Lai to izdarītu, mums ir jāmēģina sadalīt mezglu ar dažādām ievades kopām $X_1, X_2, \ldots, Xn$ , un mēs saglabājam tikai sadalījumu, kas palielina informācijas ieguvi:

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

Kad pārtraukt šķelšanos

Mezgla sadalīšana lēmumu kokos ir rekursīva, tāpēc ir jābūt kritērijiem, kurus mēs varam izmantot, lai pārtrauktu sadalīšanu. Šie ir daži no visvairāk ieviestajiem kritērijiem:

Kad mezgls ir tīrs: H(mezgls) = 0. Nav jēgas tālāk sadalīt mezglu.
Maksimālais dziļuma skaits: Mēs varam iestatīt maksimālo dziļumu, ko modelis var sasniegt, tas nozīmē, ka pat tad, ja mezgls nav tīrs, sadalīšana tiek apturēta.
Minimālais paraugu skaits mezglā: Mēs varam arī iestatīt minimālo paraugu skaitu $N$ vienam mezglam. Ja paraugu skaits vienā mezglā ir vienāds ar $N$ , mēs pārtraucam sadalīšanu pat tad, ja mezgls nav tīrs.

Apmācības beigās (sadalīšana) katrs mezgls, kas balstās uz lēmumu koka beigām, tiek saukts par "lapu", jo tā nav neviena apakškoka sakne. Katra lapa pārstāvēs ražas klasi ar visvairāk paraugu.

Secinājums

Lēmumu koks ir viens no slavenākajiem mašīnmācīšanās algoritmiem, pateicoties tā efektivitātei, intuitīvajam fonam un vienkāršai ieviešanai. Šo algoritmu var izmantot arī ar skaitliski neatkarīgiem mainīgajiem ( Gausa lēmumu koks ), un to var paplašināt, lai atrisinātu arī regresijas uzdevumus.