[PYTHON] Maschinelles Lernen: Überwacht - Entscheidungsbaum
Ziel
Verstehe den Entscheidungsbaum und probiere ihn mit scicit-learn aus.
Theorie
Der Entscheidungsbaum wird klassifiziert, indem eine Baumstruktur erstellt wird, indem Schwellenwerte für die Merkmale festgelegt werden, die für die Klassifizierung wichtig sind.
Der Entscheidungsbaum ist ein hochsemantisch interpretierbares Klassifizierungsmodell, mit dem Sie durch Visualisierung der Baumstruktur erkennen können, welche Merkmalsmenge für die Klassifizierung wichtig ist und welche an welchem Schwellenwert klassifiziert wird. Es kann auch zur Regression verwendet werden.
Entscheidungsbaum
Es gibt verschiedene Arten von Entscheidungsbaumalgorithmen, aber hier folgen wir dem von scikit-learn verwendeten CART-Algorithmus.
Entscheidungsbaumkonzept
In der Baumstruktur wird der Anfang des Baums als Wurzelknoten und das Ende des Baums als Blattknoten bezeichnet, wie in der folgenden Abbildung gezeigt. In jedem Knoten wird der obige als übergeordneter Knoten und der untere als untergeordneter Knoten bezeichnet.
In CART wird ausgehend vom Wurzelknoten ein Schwellenwert festgelegt und durch den Merkmalsbetrag geteilt, der den Informationsgewinn maximiert. Teilen Sie dies, bis die Blattknoten rein sind, dh alle in den Blattknoten enthaltenen Kategorien sind gleich.
Das Aufteilen der Blattknoten, bis sie rein sind, führt jedoch zu einem Überlernen, das durch Beschneiden gemindert werden kann.
Den Entscheidungsbaum lernen
Das Lernen des Entscheidungsbaums erfolgt durch Maximieren des Informationsgewinns $ IG $ in der folgenden Formel.
IG(D_{parent}, f) = I(D_{parent}) - \frac{N_{left}}{N_{parent}} I(D_{left}) - \frac{N_{right}}{N_{parent}} I(D_{right})
Hier ist $ f $ der zu teilende Merkmalsbetrag, $ D_ {parent} $ sind die im übergeordneten Knoten enthaltenen Daten, $ D_ {left}, D_ {right} $ sind die Daten des linken und rechten untergeordneten Knotens, $ N_ { parent} $ ist die Anzahl der Daten im übergeordneten Knoten, $ N_ {left}, N_ {right} $ ist die Anzahl der Daten im linken und rechten untergeordneten Knoten und $ I $ ist die unten beschriebene Unreinheit.
Während des Trainings ist der Informationsgewinn umso größer, je kleiner die Reinheit des linken und rechten untergeordneten Knotens in jedem Merkmal ist, und das Merkmal wird basierend auf dem festgelegten Schwellenwert aufgeteilt.
Die folgenden drei sind typische Indikatoren für die Bewertung der Reinheit. Hier ist $ C_i (i = 1, 2, .., K) $ die Kategorie $ K $, $ t $ ist der Knoten und $ P (C_i | t) $ sind Daten dieser Kategorie in einem Knoten. Repräsentiert die Wahrscheinlichkeit des Seins
Der Klassifizierungsfehler $ I_E $ reagiert nicht auf Änderungen in Knoten und wird wie unten beschrieben zum Beschneiden von Bäumen verwendet.
I_E = 1 - \max_i P(C_i | t)
Die Entropie $ I_H $ ist 0, wenn alle im Knoten enthaltenen Daten zur gleichen Kategorie gehören.
I_H = -\sum^K_{i=1} P(C_i | t) \ln P(C_i | t)
Gini $ I_G $ kann als Indikator interpretiert werden, der die Wahrscheinlichkeit einer Fehlklassifizierung minimiert. Diese ist 0, wenn alle im Knoten enthaltenen Daten zur gleichen Kategorie gehören, ähnlich wie bei der Entropie.
I_G = 1 - \sum^K_{i=1} P^2 (C_i | t)
Jede Funktion ist wie unten gezeigt und Gini ist die Standardeinstellung beim Scikit-Lernen.
Bestimmen des Baumschnittes
Während des Trainings wird der Baum vertieft, bis die Blattknoten rein sind. Wenn er jedoch unverändert bleibt, wird er überlernt, sodass ein Schnitt durchgeführt wird, um dies zu mildern.
Definieren Sie die Neuzuweisungsfehlerrate bei der erneuten Eingabe von Trainingsdaten als Bewertungskriterium für das Beschneiden von Bäumen. Die Neuzuweisungsfehlerrate $ R (t) $ an einem Knoten $ t $ wird durch die folgende Gleichung unter Verwendung des Klassifizierungsfehlers $ I_E $ und der Grenzwahrscheinlichkeit $ P (t) $ des Knotens $ t $ ausgedrückt.
R(t) = \left( 1 - \max_i P(C_i | t) \right) \times P(t) \\
P(t) = \frac{N(t)}{N}
Wobei $ N (t) $ die Anzahl der im Knoten $ t $ enthaltenen Daten darstellt und $ N $ die Gesamtzahl der Trainingsdaten darstellt.
Durch das Beschneiden von Bäumen werden Äste basierend auf dieser Neuzuweisungsfehlerrate entfernt. Mit scikit-learn kann das Argument max_leaf_nodes verwendet werden, um die erforderliche Anzahl von Knoten zu beschneiden und zu sichern.
Implementierung
Ausführungsumgebung
Hardware-
・ CPU Intel (R) Core (TM) i7-6700K 4,00 GHz
Software
・ Windows 10 Pro 1909 ・ Python 3.6.6 ・ Matplotlib 3.3.1 ・ Numpy 1.19.2 ・ Scikit-Learn 0.23.2
Programm zum Ausführen
Das implementierte Programm wird auf [GitHub] veröffentlicht (https://github.com/sho-watari/MachineLearning/blob/master/Supervised).
decision_tree_clf.py
decision_tree_reg.py
Ergebnis
Klassifizierung nach Entscheidungsbaum
Ich habe den Entscheidungsbaum auf den Brustkrebs-Datensatz angewendet, den ich bisher verwendet habe. Im Entscheidungsbaum wird der Schwellenwert für jede Merkmalsmenge festgelegt, sodass es nicht erforderlich ist, die Merkmalsmenge als Vorverarbeitung zu standardisieren.
Accuracy 97.37%
Precision, Positive predictive value(PPV) 97.06%
Recall, Sensitivity, True positive rate(TPR) 98.51%
Specificity, True negative rate(TNR) 95.74%
Negative predictive value(NPV) 97.83%
F-Score 97.78%
Visualisierung und Interpretierbarkeit von Entscheidungsbäumen
scikit-learn bietet eine plot_tree-Funktion, die den Entscheidungsbaum visualisiert und es einfach macht, die Baumstruktur des trainierten Modells zu sehen.
Sie können die Kriterien für die Beurteilung auch an jedem Knoten des trainierten Modells in der Befehlszeile wie folgt anzeigen.
The binary tree structure has 9 nodes and has the following tree structure:
node=0 test node: go to node 1 if X[:, 27] <= 0.1423499956727028 else to node 2.
node=1 test node: go to node 3 if X[:, 23] <= 957.4500122070312 else to node 4.
node=2 test node: go to node 5 if X[:, 23] <= 729.5499877929688 else to node 6.
node=3 leaf node.
node=4 leaf node.
node=5 test node: go to node 7 if X[:, 4] <= 0.10830000042915344 else to node 8.
node=6 leaf node.
node=7 leaf node.
node=8 leaf node.
Rules used to predict sample 0:
decision id node 0 : (X_test[0, 27](= 0.2051) > 0.1423499956727028)
decision id node 2 : (X_test[0, 23](= 844.4) > 729.5499877929688)
The following samples [0, 1] share the node [0] in the tree
It is 11.11%% of all nodes.
Die folgende Abbildung zeigt die Diskriminanzgrenzen bei der Durchführung einer Mehrfachklassifizierung für einen Iris-Datensatz.
Rückkehr per Entscheidungsbaum
Für die Daten des Regressionsproblems wurde der Sinuswelle eine Zufallszahl hinzugefügt. Es ist ersichtlich, dass die Vertiefung des Baumes die Ausdruckskraft verbessert.
Die folgende Abbildung ist ein Beispiel für ein Regressionsproblem mit mehreren Ausgaben.
Referenz
- Yuzo Hirai. "Erste Mustererkennung", Morikita Publishing, 2012.
Recommended Posts