Introductie
Beslissingsbomen (DT's) zijn een niet-parametrische leermethode onder toezicht die wordt gebruikt voor classificatie en regressie. Het doel is om een model te creëren dat de waarde van een doelvariabele voorspelt door eenvoudige beslissingsregels te leren die zijn afgeleid van de gegevenskenmerken.
Entropie
Het doel van de training is om de beste splitsingen in de knooppunten te vinden om zo de meest optimale boom te vinden. De splitsingen worden gedaan met behulp van enkele criteria, zoals: Entropie.
Er bestaan veel definities van entropie, zoals:
-
Entropie komt overeen met de hoeveelheid informatie die een informatiebron bevat.
-
Entropie kan ook worden gezien als de willekeur of het meten van verrassing in een set.
-
Entropie is een maatstaf die de onvoorspelbaarheid of onzuiverheid in het systeem meet.
In beslissingsbomen zullen we entropie beschouwen als de maatstaf voor de zuiverheid binnen een knooppunt. Het doel van het beslissingsboommodel is om de entropie van de knooppunten bij elke splitsing te verminderen:
We willen dus het verschil tussen de entropie van het ouderknooppunt en de entropie van de onderliggende knooppunten maximaliseren. Dit verschil wordt de Informatiewinst genoemd.
De entropie $H$ van een verzameling $X$ wordt wiskundig als volgt geformuleerd:
$$ H(X) = - \sum\limits_{x \in X} p(x) \log p(x) $$
Informatiewinst
Informatiewinst is het verschil tussen de entropie van het ouderknooppunt en de gewogen som van de entropieën van de onderliggende knooppunten, en kan dus als volgt worden geformuleerd:
$$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 de entropie.
-
$Y$ is de populatie vóór de splitsing, het vertegenwoordigt het bovenliggende knooppunt.
-
$X$ is de variabele die we willen gebruiken voor de splitsing.
-
$x$ is een unieke waarde van X.
-
$Y[X==x]$ is een gesplitste lijst met alleen $x$ waarden.
laten we een goed voorbeeld nemen:
We gaan de informatiewinst berekenen als we het bovenliggende knooppunt delen door de waarden van X te gebruiken:
$$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$$
\
Eerst berekenen we de entropie van het ouderknooppunt:
$$ 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 $$
\
Vervolgens gaan we de interne waarschijnlijkheid van elk kindknooppunt na de splitsing berekenen door de unieke waarden van X te gebruiken:
$$ 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) $$
Zoals:
-
$H(Y | X = Square)$: vertegenwoordigt de entropie van het eerste onderliggende knooppunt.
-
$H(Y | X = Circle)$: vertegenwoordigt de entropie van het tweede kindknooppunt.
\
We beginnen met het eerste onderliggende knooppunt:
$$ 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 het tweede kindknooppunt:
$$ 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 $$
\
Ten slotte vervangen we de entropieën in de Information Gain-formule:
$$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 $$
\
\
Zoals eerder vermeld, is het doel van een knooppuntsplitsing het maximaliseren van de informatiewinst, en dus het minimaliseren van de entropie in het resulterende onderliggende knooppunt. Om dit te doen, moeten we proberen het knooppunt te splitsen met verschillende sets invoer $ X_1, X_2, \ldots, Xn $ en we behouden alleen de splitsing die de informatiewinst maximaliseert:
$$ X^{*} = \underset{X_i}{\operatorname{argmax}} IG(Y, X_i) $$
Wanneer moet je stoppen met splitsen?
De knooppuntsplitsing in beslissingsbomen is recursief, dus er moeten criteria zijn die we kunnen gebruiken om de splitsing te stoppen. Dit zijn enkele van de meest geïmplementeerde criteria:
-
Als het knooppunt puur is: H(knooppunt) = 0. Het heeft geen zin om het knooppunt verder te splitsen.
-
Maximumaantal diepte: We kunnen een maximale diepte instellen die het model kan bereiken, dit betekent dat zelfs als het knooppunt niet zuiver is, het splitsen wordt gestopt.
-
Minimaal aantal monsters per knooppunt: We kunnen ook een minimumaantal $N$ aan monsters per knooppunt instellen. Als het aantal monsters per knooppunt gelijk is aan $N$, stoppen we met splitsen, zelfs als het knooppunt niet zuiver is.
Aan het einde van de training (het splitsen) wordt elk knooppunt dat afhankelijk is van het einde van de beslissingsboom een "Blad" genoemd, omdat het geen wortel is van een subboom. Elk blad vertegenwoordigt de klasse met de meeste monsters.
Conclusie
Beslissingsboom is een van de bekendste machine learning-algoritmen vanwege de efficiëntie, intuïtieve achtergrond en eenvoudige implementatie. Dit algoritme kan verder worden gebruikt met numerieke onafhankelijke variabelen (Gaussiaanse beslissingsboom), en kan worden uitgebreid om ook regressietaken op te lossen.
