Gini—Verunreinigung – ein weiteres Kriterium zum Aufteilen von Knoten in einem Entscheidungsbaum
Als einer der beliebtesten klassischen Algorithmen für maschinelles Lernen ist der Entscheidungsbaum aufgrund seiner Erklärbarkeit viel intuitiver als die anderen. In meinen vorherigen Artikeln habe ich die ID3- und C4.5-Algorithmen zum Erstellen von Entscheidungsbaummodellen vorgestellt.
- Entscheidungsbaum-Grundlagen und ID3-Algorithmus
- ID3 Nachteile und C4.5 Algorithmus
In diesem Artikel werde ich einen weiteren Algorithmus namens CART zum Erstellen eines Entscheidungsbaummodells vorstellen, der wahrscheinlich auch am häufigsten verwendet wird. Übrigens ist es der Standardalgorithmus, wenn Sie die Scikit-Learn-Bibliothek für einen Entscheidungsbaumklassifikator verwenden.
CART Algorithm ist eine Abkürzung für Classification And Regression Trees. Es wurde von Breiman et al. im Jahr 1984 .
Es ist im Allgemeinen C4 sehr ähnlich.5, aber haben die folgenden Hauptmerkmale:
- Anstelle allgemeiner Bäume, die mehrere Zweige haben könnten, verwendet CART einen Binärbaum, der nur zwei Zweige von jedem Knoten hat.
- Wir verwenden Gini-Verunreinigungen als Kriterium für die Aufteilung des Knotens, nicht für den Informationsgewinn.
- CART unterstützt numerische Zielvariablen, wodurch es zu einem Regressionsbaum wird, der kontinuierliche Werte vorhersagt.
Dieser Artikel konzentriert sich auf CART als Klassifikationsbaum.
Gini-Verunreinigung
Genau wie die ID3- und C4.5-Algorithmen, die auf Informationsgewinn als Kriterium zum Aufteilen von Knoten angewiesen sind, verwendet der CART-Algorithmus ein anderes Kriterium namens Gini, um die Knoten aufzuteilen.
Wenn Sie jemals Wirtschaft gelernt haben, müssen Sie mit dem Gini-Index vertraut sein, der die Einkommensungleichheit oder Vermögensungleichheit innerhalb einer Nation oder einer anderen Gruppe von Menschen angibt .
In diesem Algorithmus wird intuitiv der Gini-Koeffizient für einen ähnlichen Zweck verwendet. Das heißt, der größere Gini-Koeffizient bedeutet die größere Verunreinigung des Knotens. Ähnlich wie bei ID3 und C4.5, bei denen der Informationsgewinn zur Auswahl des Knotens mit größerer Unsicherheit verwendet wird, führt der Gini-Koeffizient den CART-Algorithmus dazu, den Knoten mit größerer Unsicherheit (dh Verunreinigung) zu finden und ihn dann aufzuteilen.
Die Formel des Gini-Koeffizienten ist relativ einfacher als der Informationsgewinn und das Informationsgewinnverhältnis, die wir in den beiden anderen Entscheidungsbaumalgorithmen verwendet haben. Es wird wie folgt gezeigt.
- p (Ck |t) ist die Wahrscheinlichkeit, dass ein Knoten t die Kategorie Ck ist.
- Der Gini-Koeffizient des Knotens t ist 1 minus der Summe der Wahrscheinlichkeit aller Kategorien.
Keine Angst vor der Formel. Nehmen wir ein Beispiel, um es zu demonstrieren. Ich verspreche, es ist nicht schwer zu verstehen.
Das folgende Beispiel wurde in allen anderen Artikeln verwendet, die ich über Decision Tree geschrieben habe.
Angenommen, wir möchten den Entscheidungsbaum durch Teilen mit der Funktion „Wetter“ starten. Dann müssen wir die Gini-Koeffizienten für seine Bedingungen berechnen. Konzentrieren wir uns auf das Wetterattribut und die Ergebnisse, die in den folgenden Tabellen angezeigt werden.
Es ist ziemlich einfach, die Wahrscheinlichkeit p(Ck | t) zu berechnen. Wenn wir beispielsweise das Attribut „Wetter = sonnig“ betrachten, hat es 1 „Ja“ und 2 „Nein“ von insgesamt 3 Stichproben. Daher beträgt die Wahrscheinlichkeit der Kategorie „Ja“ 1/3 und für die Kategorie „Nein“ 2/3. Wir können dann den Gini-Koeffizienten für alle wie folgt berechnen.