Summary  
This chapter explains how to evaluate and choose the best split at decision nodes by computing Gini impurity or entropy and selecting the feature–threshold pair that minimizes the weighted impurity (maximizes information gain).

General domain of usage  
Classification tasks in machine learning

Während des Trainings muss **die beste Aufteilung an jedem Entscheidungs-Knoten** gefunden werden. Beim Aufteilen der Daten in zwei Knoten wird angestrebt, dass unterschiedliche Klassen in getrennten Knoten liegen.

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

## Gini-Unreinheit

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

Die Gini-Unreinheit für die **binäre Klassifikation** kann mit folgender Formel berechnet werden:
$$
\text{gini} = 1 - p_0^2 - p_1^2 = 1 - (\frac{m_0}{m})^2 - (\frac{m_1}{m})^2
$$

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.

Und für die **Multiklassen-Klassifikation** lautet die Formel:
$$
\text{gini} = 1 - \sum_{i=0}^C p_i^2 = 1 - \sum_{i=0}^C(\frac{m_i}{m})^2
$$

Dabei gilt:
- $$C$$ – Anzahl der Klassen.

Die Qualität der Aufteilung kann durch die **gewichtete Summe der Gini-Werte** für beide durch die Aufteilung entstandenen Knoten gemessen werden. Dieser Wert soll **minimiert** werden.

Um einen Entscheidungsbaumknoten zu teilen, muss ein Merkmal und ein Schwellenwert für die Aufteilung gefunden werden:

An einem Entscheidungs-Knoten sucht der Algorithmus **gierig** nach dem besten Schwellenwert für jedes Merkmal. Anschließend wählt er die Aufteilung mit der **geringsten Gini-Unreinheit** unter allen Merkmalen aus (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:

$$
H(p) = -p \log_2(p) - (1 - p) \log_2(1 - p)
$$

wobei:

- $$p$$ der Anteil der positiven Beispiele (Klasse 1) ist;
- $$1 - p$$ der Anteil der negativen Beispiele (Klasse 0) ist.

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

$$
H(p_1, p_2, \dots, p_k) = -\sum_{i=1}^{k} p_i \log_2(p_i)
$$

wobei:

- $$k$$ die Anzahl der Klassen ist;
- $$p_i$$ der Anteil der Beispiele ist, die zur Klasse $$i$$ im Knoten 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**.

Die Entropie ist **maximal**, wenn alle Klassen gleichmäßig vertreten sind. Sie ist **minimal** (0), wenn alle Beispiele zu **einer Klasse** gehören (reiner Knoten).

Hinweis

Beherrschen Sie die grundlegenden Klassifikationsalgorithmen, die moderne Machine-Learning-Anwendungen antreiben. Erforschen Sie, wie Modelle wie k-NN, logistische Regression, Entscheidungsbäume und Random Forests Vorhersagen treffen, deren Genauigkeit bewerten und verstehen, wann welches Modell eingesetzt wird. Entwickeln Sie die Fähigkeiten, Modelle zu vergleichen und das beste für Ihre Daten auszuwählen.

Erfahren Sie, wie der k-nächste-Nachbarn-Algorithmus Vorhersagen auf Basis von Ähnlichkeiten trifft. Umgang mit mehreren Merkmalen, Parametereinstellung und Anwendung von Kreuzvalidierung zur Verbesserung der Genauigkeit.

Verstehen, wie die logistische Regression Wahrscheinlichkeiten modelliert und Ergebnisse klassifiziert. Anwendung der Implementierung, Interpretation von Entscheidungsgrenzen und Einsatz von Regularisierung zur Vermeidung von Overfitting.

Erfahren Sie, wie Entscheidungsbäume Daten anhand von Merkmalswerten in sinnvolle Gruppen unterteilen. Untersuchen Sie, wie Parameter wie Baumtiefe und minimale Stichprobengröße pro Blatt die Modellleistung und Generalisierung beeinflussen.

Erkunden, wie Random Forests mehrere Entscheidungsbäume kombinieren, um Genauigkeit und Robustheit zu verbessern.
Die Rolle des Zufalls verstehen und diese Ensemble-Methode auf reale Daten anwenden.

Bewertung von Modellen anhand von Metriken wie Genauigkeit, Präzision, Recall und F1-Score. Interpretation von Konfusionsmatrizen und Vergleich mehrerer Klassifikatoren zur Identifikation des leistungsstärksten Modells.

Aufteilen der Knoten

Gini-Unreinheit

Entropie