[Python] Ich habe die Theorie und Implementierung des Entscheidungsbaums gründlich erklärt

Einführung

Dieses Mal werde ich die Theorie der Entscheidungsbäume zusammenfassen.

Ich würde es begrüßen, wenn Sie mit mir auskommen könnten.

Theorie

Lassen Sie uns zunächst die Theorie der Entscheidungsbäume zusammenfassen.

Umriss des Entscheidungsbaums

Die Visualisierung des Entscheidungsbaums ist wie folgt.

Dieses Mal habe ich die Klassifizierung nach Iris-Dataset mit "export_graphviz" von "scicit-learn" visualisiert.

Ein Entscheidungsbaum ist ein Algorithmus, der ein Modell der Datenklassifizierung oder -regression erstellt, indem Daten gemäß bestimmten Bedingungen geteilt werden, wie im obigen Bild gezeigt. Der Klassifizierungsbaum für die Klassifizierung und der Rückgabebaum für die Regression werden zusammen als Entscheidungsbaum bezeichnet.

Da es sich um einen relativ einfachen Algorithmus handelt, ist er tendenziell weniger genau als andere komplexe Algorithmen.

Die Interpretierbarkeit des Modells ist jedoch sehr hoch.

Es wird als Entscheidungsbaum bezeichnet, da das Modell wie in der obigen Abbildung gezeigt wie ein Baum aussieht.

Typische Algorithmen sind "CART" und "C5.0".

Den Algorithmus finden Sie im Artikel hier.

Hier werden wir uns mit dem "CART" -Algorithmus befassen, der die Niclas-Klassifizierung wiederholt.

Über die Kriterien des Entscheidungsbaums

Ich denke, Sie haben bisher einen groben Überblick über den Entscheidungsbaum.

Hier betrachten wir die Kriterien für die Verzweigung klassifizierter Bäume und Rückbäume.

Klassifizierungsbaumkriterien

Lassen Sie uns nun über die Kriterien für die Verzweigung des Klassifizierungsbaums nachdenken.

Um aus der Schlussfolgerung zu schreiben, bestimmt die Klassifizierung die Merkmalsmenge und den Schwellenwert basierend auf dem Teilungskriterium, so dass "Verunreinigung" minimiert wird.

"Verunreinigung" ist ein numerischer Wert für die Anzahl der gemischten Klassen und wird unter Verwendung von "Fehlklassifizierungsrate", "Gini-Index" und "Kreuzentropiefehler" ausgedrückt. Wenn sich auf einem Knoten eine Klasse von Beobachtungsstellen befindet, ist die Reinheit 0.

Kriterien für den Rückgabebaum

Der Regressionsbaum definiert eine Kostenfunktion, die durch den mittleren quadratischen Fehler dargestellt wird, und wählt Merkmale und Schwellenwerte aus, so dass die gewichtete Summe der Kostenfunktion minimiert wird.

Über Formeln

Klassifikationsbaum

Lassen Sie uns die Unreinheit mit einer mathematischen Formel ausdrücken. Betrachten Sie die folgende Abbildung.

Das Verhältnis der beobachteten Werte der Klasse k in der Region $ R_m $ zu den beobachteten Werten von $ N_m $ ist wie folgt definiert.

\hat{p}_{mk} = \frac{1}{N_m} \sum_{x_i\in R_m}^{}I(y_i = k)

Achten Sie auf die dritte Reihe von oben in der Abbildung. m repräsentiert die Flächennummer, m = 1 repräsentiert die Fläche von "gini = 0,168" und m = 2 repräsentiert die Fläche von "gini = 0,043". k stellt die Klassenbezeichnung dar und dieses Mal wird sie als Klasse 1, Klasse 2 und Klasse 3 links vom Teil "Wert" definiert.

Es scheint schwierig zu sein, es zu formulieren, aber die tatsächliche Berechnung ist wie folgt.

\hat{p}_{11} = \frac{0}{54} \quad \hat{p}_{12} = \frac{49}{54}  \quad \hat{p}_{13} = \frac{5}{54} 

Hast du die Bedeutung der Formel irgendwie verstanden?

Mit diesem $ \ hat {p} $ wird die Unreinheit durch die folgenden drei Funktionen ausgedrückt.

Fehlklassifizierungsrate

\frac{1}{N_m} \sum_{x_i\in R_m}^{}I(y_i \neq k(m)) = 1-\hat{p}_{mk}

Gini-Index

1 - \sum_{k=1}^{K}\hat{p}_{mk}

Kreuzentropiefehler

-\sum_{k=1}^{K}\hat{p}_{mk}log\hat{p}_{mk}

Die unreine Funktion, die standardmäßig in "sklearn" verwendet wird, ist der Gini-Index. Berechnen wir also den Gini-Index.

Berechnen Sie die Reinheit der dritten Stufe anhand des Gini-Index.

Der Gini-Index des Knotens mit "gini = 0,168" links ist wie folgt.

1 - (\frac{0}{54})^2 - (\frac{49}{54})^2 - (\frac{5}{54})^2 = 0.168

Natürlich lautet die Antwort 0,168. Die obige Formel ist die Formel, die sklearn intern verwendet. Berechnen wir auch den Knoten auf der rechten Seite mit gini = 0.043.

1 - (\frac{0}{46})^2 - (\frac{1}{46})^2 - (\frac{45}{46})^2 = 0.043

Dies stimmte auch überein. Berechnen wir nun die Gesamtunreinheit, indem wir jede mit den Daten gewichten. Es wird die folgende Formel.

\frac{54}{100} ×0.168 + \frac{46}{100} ×0.043 = 0.111

Damit kann die Gesamtreinheit abgeleitet werden. Der Entscheidungsbaum erstellt ein Modell, indem Features und Schwellenwerte ausgewählt werden, die diese Unreinheit verringern.

Baum zurückgeben

Definieren Sie im Regressionsbaum die Kostenfunktion wie folgt.

\hat{c}_m = \frac{1}{N_m}\sum_{x_i \in R_m}^{}y_i\\
Q_m(T) = \frac{1}{N_m} \sum_{x_i \in R_m}(y_i - \hat{c}_m)^2

Die Kostenfunktion ist der mittlere quadratische Fehler, da $ \ hat {c} _m $ den Durchschnitt der in diesem Knoten enthaltenen Beobachtungen darstellt.

Da diese Kostenfunktion für jeden Knoten berechnet wird, stellen Sie die Merkmale und Schwellenwerte so ein, dass die gewichtete Summe der Kostenfunktion minimiert wird.

Implementierung

Inzwischen sollten Sie die Theorie der Klassifizierungsbäume und Rückgabebäume verstanden haben.

Lassen Sie uns nun den Entscheidungsbaum implementieren.

Implementierung des Klassifikationsbaums

Jetzt implementieren wir einen Klassifizierungsbaum.

Erstellen Sie zunächst die zu klassifizierenden Daten.

from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
from sklearn.tree import export_graphviz
from matplotlib.colors import ListedColormap
import graphviz

moons = make_moons(n_samples=300, noise=0.2, random_state=0)
X = moons[0]
Y = moons[1]
X_train, X_test, Y_train, Y_test = train_test_split(X, Y, random_state=0, stratify=Y)

plt.figure(figsize=(12, 8))
mglearn.discrete_scatter(X[:, 0], X[:, 1], Y)
plt.show()

Wir werden ein Modell erstellen, um diese Daten zu klassifizieren.

Unten ist der Code.

clf_model = DecisionTreeClassifier(max_depth=3)
clf_model.fit(X_train, Y_train)
print(clf_model.score(X_test, Y_test))

0.8933333333333333

Die Genauigkeit war angemessen.

Lassen Sie uns das Modell dieses Klassifizierungsbaums visualisieren. Unten ist der Code.

dot_data = export_graphviz(clf_model)
graph = graphviz.Source(dot_data)
graph.render('moon-tree', format='png')

Informationen zur Visualisierung mit graphviz finden Sie im Artikel hier.

Wie Sie sehen können, ist der Entscheidungsbaum im Modell sehr interpretierbar. In diesem Modell wird "max_depth = 3" gesetzt, sodass das Modell eine Tiefe von 3 hat.

Lassen Sie uns das Modell nach der Klassifizierung visualisieren. Unten ist der Code.

plt.figure(figsize=(12, 8))
_x1 = np.linspace(X[:, 0].min() - 0.5, X[:, 0].max() + 0.5, 100)
_x2 = np.linspace(X[:, 1].min() - 0.5, X[:, 1].max() + 0.5, 100)
x1, x2 = np.meshgrid(_x1, _x2)
X_stack = np.hstack((x1.ravel().reshape(-1, 1), x2.ravel().reshape(-1, 1)))
y_pred = clf_model.predict(X_stack).reshape(x1.shape)
custom_cmap = ListedColormap(['mediumblue', 'orangered'])
plt.contourf(x1, x2, y_pred, alpha=0.3, cmap=custom_cmap)
mglearn.discrete_scatter(X[:, 0], X[:, 1], Y)
plt.show()

Informationen zum Ändern der Farbe mithilfe der Rasterpunkte finden Sie im Artikel hier.

_x1 und _x2 geben die Fläche der Gitterpunkte in Richtung der x-Achse und der Richtung der y-Achse an, undx1, x2 = np.meshgrid (_x1, _x2)erstellt die Gitterpunkte.

X_stack = np.hstack ((x1.ravel (). Umformen (-1, 1), x2.ravel (). Umformen (-1, 1))) Teil ist ein eindimensionaler 100 × 100-Gitterpunkt Nach dem Wechsel zu einem Array wird es in ein zweidimensionales Array mit 10000 x 1 konvertiert und dann horizontal kombiniert, um es in Daten mit 10000 x 2 zu konvertieren.

In dem Teil von "y_pred = clf_model.predict (X_stack) .reshape (x1.shape)" werden 10000 × 2-Daten in 0- und 1-Daten konvertiert und in 100 × 100-Daten konvertiert. Eine Seite der Linie, die die Daten trennt, ist 0 und die andere ist 1.

Zeichnen Sie Konturlinien bei plt.contourf (x1, x2, y_pred, alpha = 0,3, cmap = custom_cmap). Die Farbe wird durch "cmap = custom_cmap" angegeben.

Dies ist das Ende der Implementierung des Klassifizierungsbaums.

Implementierung des Rückgabebaums

Lassen Sie uns nun den Rückgabebaum implementieren.

Bereiten wir die Daten vor und zeichnen sie.

import mglearn
from sklearn.tree import DecisionTreeRegressor
import numpy as np
import matplotlib.pyplot as plt
from sklearn.tree import export_graphviz
import graphviz

X, Y = mglearn.datasets.make_wave(n_samples=200)

plt.figure(figsize=(12, 8))
plt.plot(X, Y, 'bo', ms=15)
plt.show()

Die Daten sind so. Nun erstellen wir ein Modell.

tree_reg_model = DecisionTreeRegressor(max_depth=3)
tree_reg_model.fit(X, Y)
print(tree_reg_model.score(X, Y))

0.7755211625482443

Sie können $ R ^ 2 $ mit score anzeigen.

score(self, X, y[, sample_weight]) Returns the coefficient of determination R^2 of the prediction.

Die Genauigkeit ist nicht sehr gut.

Lassen Sie uns das Modell mit dem folgenden Code visualisieren.

dot_data = export_graphviz(tree_reg_model)
graph = graphviz.Source(dot_data)
graph.render('wave-tree', format='png')

Wie Sie sehen können, weist der Rückgabebaum (sowie der Entscheidungsbaum) eine sehr gute Modellinterpretierbarkeit auf.

Lassen Sie uns nun die Regressionslinie mit dem folgenden Code veranschaulichen.

X1 = np.linspace(X.min() - 1, X.max() + 1, 1000).reshape(-1, 1)
y_pred = tree_reg_model.predict(X1)
plt.xlabel('x', fontsize=10)
plt.ylabel('y', fontsize=10, rotation=-0)
plt.plot(X, Y, 'bo', ms=5)
plt.plot(X1, y_pred, 'r-', linewidth=3)
plt.show()

Wie Sie der Abbildung entnehmen können, ist dies nicht sehr korrekt.

Ohne Angabe der Tiefe implementiert

Lassen Sie es uns jetzt implementieren, ohne Tiefe zu implementieren.

Es ist dasselbe, außer dass Sie die Tiefe nicht angeben. Lassen Sie uns also dieselben Schritte in einer Funktion zusammenfassen.

import mglearn
from sklearn.tree import DecisionTreeRegressor
import numpy as np
import matplotlib.pyplot as plt
from sklearn.tree import export_graphviz
import graphviz

X, Y = mglearn.datasets.make_wave(n_samples=200)

tree_reg_model_2 = DecisionTreeRegressor()

tree_reg_model_2.fit(X, Y)

print(tree_reg_model_2.score(X, Y))

1.0

$ R ^ 2 $ ist jetzt 1. Was für ein Modell ist das? Lassen Sie uns den folgenden Zweig veranschaulichen.

def graph_export(model):
    dot_data = export_graphviz(model)
    graph = graphviz.Source(dot_data)
    graph.render('test', format='png')

graph_export(tree_reg_model_2)

Es war ein schrecklicher Zweig. Ich kann nicht mehr lesen, wie es sich verzweigt.

Lassen Sie uns das Modell mit dem folgenden Code veranschaulichen.

def plot_regression_predictions(tree_reg, x, y):
    x1 = np.linspace(x.min() - 1, x.max() + 1, 500).reshape(-1, 1)
    y_pred = tree_reg.predict(x1)
    plt.xlabel('x', fontsize=10)
    plt.ylabel('y', fontsize=10, rotation=-0)
    plt.plot(x, y, 'bo', ms=5)
    plt.plot(x1, y_pred, 'r-', linewidth=1)
    plt.show()


plot_regression_predictions(tree_reg_model_2, X, Y)

Wie Sie der obigen Abbildung entnehmen können, ist dies eindeutig ein Überlernen.

Dies macht es unmöglich, unbekannte Daten vorherzusagen, sodass Sie verstehen, wie wichtig es ist, die Tiefe des Baums entsprechend einzustellen.

Am Ende

Das ist alles für diese Zeit.

Vielen Dank, dass Sie bisher bei uns geblieben sind.