Während des Trainings müssen wir die beste Aufteilung an jedem Entscheidungs-Knoten finden. Wenn wir die Daten in zwei Knoten aufteilen, ist das Ziel, dass unterschiedliche Klassen in getrennten Knoten landen.

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

Gini-Impurität

Um zu messen, wie gut eine Aufteilung ist, kann die Gini-Impurität berechnet werden. Sie ist die Wahrscheinlichkeit, dass bei zufälliger Auswahl von zwei Punkten aus einem Knoten (mit Zurücklegen) diese verschiedenen Klassen angehören. Je niedriger diese Wahrscheinlichkeit (Impurität), desto besser ist die Aufteilung.

Die Gini-Unreinheit für die binäre Klassifikation lässt sich mit folgender Formel berechnen:

Dabei gilt:

• $m_i$ – Anzahl der Instanzen der Klasse $i$ in einem Knoten;
• $m$ – Anzahl der Instanzen in einem Knoten;
• $p_i = \frac{m_i}{m}$ – Wahrscheinlichkeit, die Klasse $i$ auszuwählen.

Für die Multiklassen-Klassifikation lautet die Formel:

Dabei gilt:

• $C$ – Anzahl der Klassen.

Die Qualität der Aufteilung lässt sich durch die gewichtete Summe der Gini-Werte für beide durch die Aufteilung entstandenen Knoten messen. Dieser Wert soll minimiert werden.

Um einen Entscheidungs-Knoten zu teilen, müssen ein Merkmal für die Aufteilung und der Schwellenwert bestimmt werden:

An einem Entscheidungs-Knoten findet der Algorithmus gierig den besten Schwellenwert für jedes Merkmal. Anschließend wählt er die Aufteilung mit der geringsten Gini-Unreinheit unter allen Merkmalen (bei Gleichstand erfolgt die Auswahl zufällig).

Entropie

Die Entropie ist ein weiteres Maß für die Unreinheit. Für ein binäres Klassifikationsproblem wird die Entropie $H$ eines Knotens mit folgender Formel berechnet:

wobei:

• $p$ den Anteil der positiven Beispiele (Klasse 1) bezeichnet;
• $1 - p$ den Anteil der negativen Beispiele (Klasse 0) bezeichnet.

Für ein multiklassiges Klassifikationsproblem wird die Entropie $H$ eines Knotens mit folgender Formel berechnet:

wobei:

• $k$ die Anzahl der Klassen ist;
• $p_i$ den Anteil der Beispiele angibt, die im Knoten zur Klasse $i$ gehören.

Ähnlich wie bei der Gini-Unreinheit kann die Qualität einer Aufteilung gemessen werden, indem die gewichtete Summe der Entropiewerte für die durch die Aufteilung entstandenen Kindknoten berechnet wird. Dieser Wert soll minimiert werden, um den Informationsgewinn zu maximieren.