Aufteilen der Knoten

Während des Trainings müssen wir den besten Split an jedem Entscheidungsnode finden. Wenn wir die Daten in zwei Nodes aufteilen, möchten wir, dass verschiedene Klassen in anderen Nodes sind.

• Bestes Szenario: Alle Datenpunkte in einem Knoten gehören zur gleichen Klasse;
• Schlechtestes Szenario: Gleiche Anzahl von Datenpunkten für jede Klasse.

Um zu messen, wie gut eine Aufteilung ist, können wir die Gini-Unreinheit berechnen.
Es ist die Wahrscheinlichkeit, dass, wenn wir zufällig zwei Punkte aus einem Knoten (mit Zurücklegen) nehmen, sie unterschiedlichen Klassen angehören. Je geringer diese Wahrscheinlichkeit (Unreinheit), desto besser die Aufteilung.

Sie können die Gini-Unreinheit für die binäre Klassifikation mit der folgenden Formel berechnen:

Und für die Mehrklassenklassifikation lautet die Formel:

Wir können messen, wie gut die Aufteilung ist, indem wir die gewichtete Summe der Gini-Werte für beide Knoten, die aus einer Aufteilung resultieren, berechnen. Das ist der Wert, den wir minimieren möchten.
Um einen Entscheidungs-Knoten zu teilen, müssen wir ein Merkmal finden, nach dem wir teilen können, und den Schwellenwert.

An einem Entscheidungs-Knoten findet der Algorithmus gierig den besten Schwellenwert für jedes Merkmal. Dann wählt er die Aufteilung mit der geringsten Gini-Unreinheit aus allen Merkmalen (bei Gleichstand wird zufällig gewählt).