Besluitboomklassifikasie

Inleiding

Besluitbome (DT's) is 'n nie-parametriese leermetode wat onder toesig gebruik word vir klassifikasie en regressie. Die doel is om 'n model te skep wat die waarde van 'n teikenveranderlike voorspel deur eenvoudige besluitreëls te leer wat uit die datakenmerke afgelei word.

Entropie

Die doel van die opleiding is om die beste splits in die nodusse te vind om die mees optimale boom te vind. Die verdelings word gedoen deur gebruik te maak van sekere kriteria soos: Entropie.

Daar bestaan baie definisies van entropie soos:

Entropie stem ooreen met die hoeveelheid inligting vervat in 'n bron van inligting.
Entropie kan ook gesien word as die ewekansigheid of die meting van verrassing in 'n stel.
Entropie is 'n maatstaf wat die onvoorspelbaarheid of onsuiwerheid in die stelsel meet.

In besluitbome sal ons entropie beskou as die maatstaf van die suiwerheid binne-in 'n nodus. Die doel van die besluitboommodel is om die entropie van die nodusse by elke verdeling te verminder:

Ons wil dus die verskil tussen die entropie van die ouerknoop en die entropie van die kindnodusse maksimeer. Hierdie verskil word die Inligtingswins genoem.

Die Entropie $H$ van 'n stel $X$ word wiskundig soos volg geformuleer:

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

Inligtingwins

Inligtingswins is die verskil tussen die entropie van die ouerknoop en die geweegde som van die entropieë van die chlid-nodusse, en dus kan dit soos volg geformuleer word:

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

waar:

$H(.)$ is die entropie.
$Y$ is die populasie voor die verdeling, dit verteenwoordig die ouernodus.
$X$ is die veranderlike wat ons vir die splitsing wil gebruik.
$x$ is 'n unieke waarde van X.
$Y[X==x]$ is 'n verdeelde lys met slegs $x$ waardes.

kom ons neem 'n behoorlike voorbeeld:

Ons gaan die inligtingswins bereken wanneer ons die ouernodus verdeel deur die waardes van X te gebruik:

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

Eerstens bereken ons die entropie van die ouerknoop:

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

Dan gaan ons die interne waarskynlikheid van elke kindernodus na die verdeling bereken deur die unieke waardes van X te gebruik:

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

Soos:

$H(Y | X = Vierkant)$ : verteenwoordig die entropie van die eerste kindnodus.
$H(Y | X = Sirkel)$ : verteenwoordig die entropie van die tweede kindnodus.

Ons begin met die eerste kind node:

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

En dan die tweede kind node:

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

Laastens vervang ons die entropieë in die inligtingswinsformule:

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

Soos voorheen genoem, is die doel van 'n nodusverdeling om die inligtingswins te maksimeer, en sodoende die entropie in die gevolglike kindernodus te minimaliseer. Om dit te doen, moet ons probeer om die nodus te verdeel met verskillende stelle insette $X_1, X_2, \ldots, Xn$ en ons behou net die verdeling wat die inligtingswins maksimeer:

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

Wanneer om op te hou verdeel

Die nodussplitsing in besluitnemingsbome is 'n rekursief, so daar moet 'n kriteria wees wat ons kan gebruik om die splitsing te stop. Hierdie is van die mees geïmplementeerde kriteria:

Wanneer die nodus suiwer is: H(node) = 0. Dit is sinloos om die node verder te verdeel.
Maksimum aantal diepte: Ons kan 'n maksimum diepte stel wat die model kan bereik, dit beteken dat selfs al is die nodus nie suiwer nie, word die splitsing gestop.
Minimum aantal monsters per nodus: Ons kan ook 'n minimum aantal $N$ monsters per nodus stel. As die aantal monsters per nodus gelyk is aan $N$ dan hou ons op om te verdeel, selfs al is die nodus nie suiwer nie.

Aan die einde van die opleiding (die splitsing), word elke nodus wat op die einde van die besluitboom staatmaak 'n "Blaar" genoem, want dit is nie 'n wortel vir enige subboom nie. Elke blaar sal opbrengs die klas met die meeste monsters verteenwoordig.

Gevolgtrekking

Besluitboom is een van die bekendste masjienleeralgoritmes vanweë die doeltreffendheid, intuïtiewe agtergrond en eenvoudige implementering daarvan. Hierdie algoritme kan verder gebruik word met numeriese onafhanklike veranderlikes (Gaussian Decision Tree), en dit kan uitgebrei word om ook regressietake op te los.