Entscheidungsbaum-Klassifizierung

Einführung

Entscheidungsbäume (DTs) sind eine nichtparametrische Methode des überwachten Lernens, die zur Klassifizierung und Regression verwendet wird. Das Ziel besteht darin, ein Modell zu erstellen, das den Wert einer Zielvariablen vorhersagt, indem es einfache Entscheidungsregeln lernt, die aus den Datenmerkmalen abgeleitet werden.

Entropie

Ziel des Trainings ist es, die besten Aufteilungen in den Knoten zu finden, um den optimalsten Baum zu finden. Die Aufteilungen erfolgen anhand einiger Kriterien wie zum Beispiel: Entropie.

Es gibt viele Definitionen von Entropie, wie zum Beispiel:

Entropie entspricht der Informationsmenge, die in einer Informationsquelle enthalten ist.
Entropie kann auch als Zufälligkeit oder als Maß für die Überraschung in einer Menge angesehen werden.
Entropie ist eine Metrik, die die Unvorhersehbarkeit oder Verunreinigung im System misst.

In Entscheidungsbäumen betrachten wir die Entropie als Maß für die Reinheit innerhalb eines Knotens. Das Ziel des Entscheidungsbaummodells besteht darin, die Entropie der Knoten bei jeder Teilung zu reduzieren:

Daher möchten wir den Unterschied zwischen der Entropie des übergeordneten Knotens und der Entropie der untergeordneten Knoten maximieren. Dieser Unterschied wird Informationsgewinn genannt.

Die Entropie $H$ einer Menge $X$ lässt sich mathematisch wie folgt formulieren:

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

Informationsgewinn

Der Informationsgewinn ist die Differenz zwischen der Entropie des übergeordneten Knotens und der gewichteten Summe der Entropien der untergeordneten Knoten und kann daher wie folgt formuliert werden:

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

Wo:

$H(.)$ ist die Entropie.
$Y$ ist die Population vor der Teilung und stellt den übergeordneten Knoten dar.
$X$ ist die Variable, die wir für die Aufteilung verwenden möchten.
$x$ ist ein eindeutiger Wert von X.
$Y[X==x]$ ist eine geteilte Liste mit nur $x$ -Werten.

Nehmen wir ein richtiges Beispiel:

Wir werden den Informationsgewinn berechnen, wenn wir den übergeordneten Knoten teilen, indem wir die Werte von X verwenden:

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

Zuerst berechnen wir die Entropie des übergeordneten Knotens:

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

Anschließend berechnen wir die interne Wahrscheinlichkeit jedes untergeordneten Knotens nach der Teilung mithilfe der eindeutigen Werte von X:

$unique(X) = [Kreis, Quadrat]$

$\sum\_{x \in unique(X)} P(x|X) \times H(Y | X = x) = P(Quadrat|X) \times H(Y | X = Quadrat)$

$+ P(Kreis|X) \times H(Y | X = Kreis)$

$= \frac{9}{21} \times H(Y | X = Quadrat) + \frac{12}{21} \times H(Y | X = Kreis)$

Wie zum Beispiel:

$H(Y | X = Square)$ : stellt die Entropie des ersten untergeordneten Knotens dar.
$H(Y | X = Circle)$ : stellt die Entropie des zweiten untergeordneten Knotens dar.

Wir beginnen mit dem ersten untergeordneten Knoten:

$H(Y | X = Quadrat) = - P(Y=Blau | X = Quadrat) \times \log P(Y=Blau| X = Quadrat)$

$- P(Y=Gelb| X = Quadrat) \times \log P(Y=Gelb| X = Quadrat)$

$= - \frac{7}{9} \times \log\frac{7}{9} - \frac{2}{9} \times \log\frac{2}{9} = 0,23$

Und dann der zweite untergeordnete Knoten:

$H(Y | X = Kreis) = - P(Y=Blau | X = Kreis) \times \log P(Y=Blau| X = Kreis)$

$- P(Y=Gelb| X = Kreis) \times \log P(Y=Gelb| X = Kreis)$

$= - \frac{4}{12} \times \log\frac{4}{12} - \frac{8}{12} \times \log\frac{8}{12} = 0,28$

Schließlich ersetzen wir die Entropien in der Informationsgewinnformel:

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

Wie bereits erwähnt besteht das Ziel einer Knotenaufteilung darin, den Informationsgewinn zu maximieren und somit die Entropie im resultierenden untergeordneten Knoten zu minimieren. Dazu müssen wir versuchen, den Knoten mit verschiedenen Eingabesätzen $X_1, X_2, \ldots, Xn$ aufzuteilen und behalten nur die Aufteilung bei, die den Informationsgewinn maximiert:

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

Wann mit dem Teilen aufhören soll

Die Knotenaufteilung in Entscheidungsbäumen ist rekursiv, daher muss es ein Kriterium geben, das wir verwenden können, um die Aufteilung zu stoppen. Dies sind einige der am häufigsten implementierten Kriterien:

Wenn der Knoten rein ist: H(Knoten) = 0. Es ist sinnlos, den Knoten weiter zu teilen.
Maximale Anzahl an Tiefen: Wir können eine maximale Tiefe festlegen, die das Modell erreichen kann. Dies bedeutet, dass die Aufteilung auch dann gestoppt wird, wenn der Knoten nicht rein ist.
Mindestanzahl von Samples pro Knoten: Wir können auch eine Mindestanzahl $N$ von Samples pro Knoten festlegen. Wenn die Anzahl der Stichproben pro Knoten gleich $N$ ist, hören wir mit der Aufteilung auf, auch wenn der Knoten nicht rein ist.

Am Ende des Trainings (der Aufteilung) wird jeder Knoten, der auf das Ende des Entscheidungsbaums angewiesen ist, als „Blatt“ bezeichnet, da er keine Wurzel eines Unterbaums darstellt. Jedes Blatt repräsentiert die Klasse mit den meisten Proben.

Abschluss

Der Entscheidungsbaum ist aufgrund seiner Effizienz, seines intuitiven Hintergrunds und seiner einfachen Implementierung einer der bekanntesten Algorithmen für maschinelles Lernen. Dieser Algorithmus kann weiterhin mit numerischen unabhängigen Variablen verwendet werden (Gaußscher Entscheidungsbaum) und kann auch zur Lösung von Regressionsaufgaben erweitert werden.