Klassifikation

Klassifikation#

Den Wald vor lauter Bäumen nicht sehen

— Christoph Martin Wieland

Die Klassifikation ist die zweite wichtige Problemstellung im Supervised Learning dessen Ziel es ist für eine Menge an Daten vorher bekannte Klassen zu lernen und diese für neue Datensätze vorherzusagen. Bei den Klassen kann es sich um binäre Daten handeln (z.B. Ja/Nein, Ein/Aus) oder kategorische Daten (z.B. Kalt, Normal, Warm). Sie können aber auch zur Vorhersage numerischer Daten genutzt werden - genauso wie Logistische Regressionsmodelle zur Vorhersage binärer Daten verwendet werden können.

Klassifikationsmodelle werden in der Praxis häufig zur Erkennung von Spam eingesetzt (Ja/Nein), Betrugserkennung, Anomalieerkennung, Kreditratings oder Allgemein für Vorhersageprobleme. Es gibt verschiedene Arten von Klassifikationsmodellen, von denen wir einige typische Ansätze diskutieren wollen.

Folien #

Entscheidungsbäume zur Klassifikation#

Entscheidungsbäume (en. Decission Trees) sind eine beliebte Methode des maschinellen Lernens zur Klassifizierung von Datenpunkten, da sie intuitiv und leicht verständlich sind. Das macht sie zu einem guten Werkzeug für Anfänger und Experten gleichermaßen. Sie können numerische und kategorische Daten als Eingangsvariablen verarbeiten.

Das Grundelement eines Entscheidungsbaum ist eine einfache Wenn-Dann-Sonst-Verzweigung (if-else), die wir aus der Programmierung kennen. Hierbei wird auf einer Eingangsgrößen eine Bedingung definiert und für die beiden Antwortvarianten werden unterschiedliche Rückgabewerte ausgegeben.

if x > 30:
  y = "Cool"
else:
  if x < 18:
    y = "Heat"
  else:
    y = "off"

Durch Verschachteln der Bedingungen entsteht eine Baumstruktur, die wir in einem Flussdiagramm darstellen können. Das Flussdiagramm besteht aus Knoten, Kanten und Blättern:

Knoten: Ein Punkt im Baum, an dem eine Entscheidung getroffen wird, basierend auf einem Eingangswert.
Kanten: Verbindungen zwischen den Knoten, die den Entscheidungsfluss darstellen.
Blätter: Endknoten des Baumes, die eine Klassifikation oder Vorhersage darstellen.

Durch diesen einfachen Aufbau ist ein Entscheidungsbaum bis zu einer gewissen Tiefe gut erklärbar, da man für jeden Eingangswert die entsprechende Entscheidungskette im Baum nachvollziehen kann. Deshalb werden Entscheidungsbäume auch beim Data Mining genutzt, um bisher unbekannte Regeln aus einem Datensatz abzuleiten.

Ferner ist der Baum bei der Vorhersage (Scoring) sehr effizient zu berechnen, da auch bei vielen Bedingungen durch die Baumstruktur nur ein kleiner Teil an relevanten Bedingungen betrachtet werden muss (log(n)-Komplexität).

Erstellen eines Entscheidungsbaums#

Sind die Regeln bekannt, kann der Entscheidungsbaum, wie im obigen Beispiel gezeigm, manuell definiert werden. Im Machine Learning besteht allerdings die Zielstellung diesen Entscheidungsbaum automatisch aus den Trainingsdaten abzuleiten. Das geschieht in drei Schritten:

Auswahl des besten Attributs zur Trennung der Daten.
Aufteilung des Datensatzes basierend auf dem ausgewählten Attribut.
Wiederholung des Prozesses für jeden Teilbaum, bis ein Abbruchkriterium erfüllt ist.

Auswahl des besten Attributes#

Die Auswahl des besten Attributs erfolgt typischerweise durch Maximierung eines Kriteriums wie dem Informationsgewinn oder der Gini-Impurity.

Informationsgewinn: Der Informationsgewinn basiert auf dem Konzept der Entropie. Die Entropie misst wie viel Zufall eine Variable enthält und ist somit ein Varianzmaß. Die Entropie \(H(S)\) einer Variable \(S\) wird wie folgt berechnet:

\[ H(S) = - \sum_{k=1}^{c} p_k \log_2(p_k) \]

wobei \(c\) die Anzahl der Klassen und \(p_k\) der Anteil der Klasse \(k\) im Datensatz \(S\) ist.

Der Informationsgewinn \(IG(T, A)\) eines Attributs \(A\) für den Datensatz \(T\) wird dann berechnet als:

\[ \overbrace{IG(T, A)}^\text{Informationsgewinn} = \overbrace{H(T)}^\text{Entropy des Knoten} - \overbrace{\sum_{v \in Values(A)} \frac{|T_v|}{|T|} H(T_v)}^\text{Entropy aller Subknoten} \]

wobei \(Values(A)\) die möglichen Werte von Attribut \(A\) sind und \(T_v\) der Teil des Datensatzes \(T\) ist, bei dem Attribut \(A\) den Wert \(v\) hat. Der Informationsgewinn misst somit wie viel Entropie ein Knoten zu dem finalen Datensatz beiträgt.

Gini-Impurity: Die Gini-Impurity eines Datensatzes \(S\) wird wie folgt berechnet:

\[ Gini(S) = 1 - \sum_{i=1}^{c} p_i^2 \]

Der Gini-Gewinn wird ähnlich wie der Informationsgewinn berechnet, wobei anstelle der Entropie die Gini-Impurity verwendet wird.

Beispiel#

Betrachten wir ein einfaches Beispiel zur Veranschaulichung. Angenommen, wir haben den obigen Datensatz mit den Klassen “Apfel” und “Orange” und den Attributen “Farbe” und “Größe”. Unser Ziel ist es, einen Entscheidungsbaum zu erstellen, der die Früchte klassifiziert.

Berechnung der Entropie des gesamten Datensatzes#

Entsprechend der obigen Abbildung enthält der Datensatz 4 Äpfel und 5 Orangen. Die Entropie des gesamten Datensatzes ist folglich:

\[ H(S) = - \left( \frac{5}{9} \log_2 \frac{5}{9} + \frac{4}{9} \log_2 \frac{4}{9} \right) = 0.99 \]

Berechnung der Entropie für jedes Attribut#

Wir berechnen nun für jeden möglichen Split der Daten den resultierenden Informationsgewinn. Wir haben können den Datensatz anhand des Attributs Farbe splitten oder anhand des Attributs Größe. Splitten wir den Datensatz auf Basis der Farbe so haben wir 5 Objekte mit der Farbe “orange” und 4 mit der Farbe “rot”.

Wir berechnen die Entropie nach der Aufteilung auf Basis der Farbe:

(6)#\[\begin{align} H(Farbe=Rot) &= - \left( \frac{1}{5} \log_2 \frac{1}{5} + \frac{4}{5} \log_2 \frac{4}{5} \right) &= 0.72 \\ H(Farbe=Orange) &= - \left( \frac{4}{4} \log_2 \frac{4}{4} \right) &= 0.0 \\ IG(Farbe) &= H(S) - \frac{5}{9} H(Farbe=Rot) - \frac{4}{9} H(Farbe=Orange) \\ &= 0.99 - \frac{5}{9} 0.72 - \frac{4}{9} 0.0 &= 0.59 \end{align}\]

Jetzt berechnen wir die Entropie nach der Aufteilung auf Basis der Größe:

(7)#\[\begin{align} H(Größe=Klein) &= - \left( \frac{2}{5} \log_2 \frac{2}{5} + \frac{3}{5} \log_2 \frac{3}{5} \right) &= 0.97 \\ H(Größe=Gross) &= - \left( \frac{2}{4} \log_2 \frac{2}{4} + \frac{2}{4} \log_2 \frac{2}{4} \right) &= 1.0 \\ IG(Größe) &= H(S) - \frac{5}{9} H(Größe=Klein) - \frac{4}{9} H(Größe=Gross) \\ &= 0.99 - \frac{5}{9} 0.97 - \frac{4}{9} 1.0 &= 0.01 \end{align}\]

Es zeigt sich, dass der Informationsgewinn bei der \(Farbe\) deutlich höher ist als bei der \(Größe\), weshalb es sinnvoll ist diesen als ersten Knoten im Entscheidungsbaum zu wählen.

Entscheidungsbäume in SciKit-Learn#

Entscheidungsbäume können unter andrem mit SciKit-Learn erstellt werden. Hierfür erstellen wir wie gewohnt eine Modellklasse und können dabei auch das Kriterium angeben

from sklearn.tree import DecisionTreeClassifier

clf = DecisionTreeClassifier(criterion="entropy")

Erstellen wir uns als nächstes den Beispieldatensatz as Pandas Dataframe

import numpy as np # Import von NumPy
import pandas as pd # Import von Pandas
df=pd.DataFrame([
    ["Orange","Gross","Orange"],
    ["Rot","Gross","Orange"],
    ["Rot","Gross","Apfel"],
    ["Orange","Klein","Orange"],
    ["Orange","Klein","Orange"],
    ["Rot","Klein","Apfel"],
    ["Rot","Klein","Apfel"],
    ["Rot","Gross","Apfel"],
    ["Orange","Klein","Orange"]
],columns=["Color","Size","Typ"])
df

	Color	Size	Typ
0	Orange	Gross	Orange
1	Rot	Gross	Orange
2	Rot	Gross	Apfel
3	Orange	Klein	Orange
4	Orange	Klein	Orange
5	Rot	Klein	Apfel
6	Rot	Klein	Apfel
7	Rot	Gross	Apfel
8	Orange	Klein	Orange

Hier ist wieder zu beachten das SciKit-Learn nicht direkt auf kategorischen Spalten mit Text arbeitet, sondern binäre oder numerische Spalten erwartet. Wir können binäre Variablen mit der Methode get_dummies erzeugen:

dfD= pd.get_dummies(df,columns=["Color","Size","Typ"],drop_first=False)
dfD.head(2)

	Color_Orange	Color_Rot	Size_Gross	Size_Klein	Typ_Apfel	Typ_Orange
0	True	False	True	False	False	True
1	False	True	True	False	False	True

Oder alternativ numerische Variablen mit der Funktion pd.factorize erzeugen. Das bietet sich hier mehr an, da es eine kompaktere Darstellung ist

dfF=df.copy()
dfF["Color"], df_map_col = pd.factorize(df["Color"])
dfF["Size"], df_map_size = pd.factorize(df["Size"])
dfF["Typ"], df_map_typ = pd.factorize(df["Typ"])
dfF, df_map_col, df_map_size, df_map_typ

(   Color  Size  Typ
 0      0     0    0
 1      1     0    0
 2      1     0    1
 3      0     1    0
 4      0     1    0
 5      1     1    1
 6      1     1    1
 7      1     0    1
 8      0     1    0,
 Index(['Orange', 'Rot'], dtype='object'),
 Index(['Gross', 'Klein'], dtype='object'),
 Index(['Orange', 'Apfel'], dtype='object'))

Mit der Modellmethode fit können wir wieder das Modell trainieren, indem wir die Eingänge x und die Zielvariable y spezifizieren.

x=dfF[['Color','Size']]
y=dfF["Typ"]

clf.fit(x, y)

DecisionTreeClassifier(criterion='entropy')

In a Jupyter environment, please rerun this cell to show the HTML representation or trust the notebook.
On GitHub, the HTML representation is unable to render, please try loading this page with nbviewer.org.

Mit der Funktion plot_tree können wir uns den Entscheidungsbaum anzeigen lassen:

from sklearn.tree import plot_tree
import matplotlib.pyplot as plt

plt.figure(figsize=(20,10))
plot_tree(clf, filled=True, feature_names=['Color','Size'], class_names=df_map_typ)
plt.show()

../_images/9f6d1885e4c1c29d42ab6e4d83a7fb697ed7ed31353ecd1b0c526482e9b65cd7.png

Mit der bekannten Methode predict können wir eine Vorhersage treffen. Also ein Objekt das Orange (0) ist und Klein (1) ist eine Orange (0).

clf.predict([[0,1]])

/Users/jploennigs/miniconda3/envs/lehre/lib/python3.11/site-packages/sklearn/base.py:493: UserWarning: X does not have valid feature names, but DecisionTreeClassifier was fitted with feature names
  warnings.warn(

array([0])

Prüfen wir das Modell einmal an dem uns bekannten Energie- und Wetterdatensatz. Wir laden den Datensatz und fügen eine Spalte für den Wochentag (gleich numerisch) hinzu und ob der EV_HT_740-Verbraucher an ist. Wir brauchen in diesem Fall die fehlenden NaN Werte nicht entfernen.

egywth = pd.read_csv("../data/UROS/Energy1D_weather_clean.csv", parse_dates=[0])
egywth["Weekday"] = egywth["Date"].dt.dayofweek
egywth["EV_HT_740_IS_ON"] = egywth.EV_HT_740==0

Wir wollen ein Modell für die Temperaturklasse und den Heiztage und Kühltage bestimmen, um zu sehen ob die originalen Grenzen aus dem Notebook zur Datenvorverarbeitung erkannt werden. Hierfür wandeln wir die Spalten zuerst in Numerische Kategorien um.

egywth["TemperaturKlasseN"], TK_map = pd.factorize(egywth["TemperaturKlasse"])
egywth["HeizKuehlTageN"], HKT_map = pd.factorize(egywth["HeizKuehlTage"])
TK_map,HKT_map

(Index(['Cold', 'Cool', 'Mild', 'Warm'], dtype='object'),
 Index(['Heizgradtag', 'Normaltag', 'Kühlgradtag'], dtype='object'))

Dann trainieren und visualisieren wir die Entscheidungsbäume.

clfTK = DecisionTreeClassifier()
clfTK.fit(egywth[['TMK']], egywth[['TemperaturKlasseN']])
clfTK.get_depth()

plt.figure(figsize=(20,10))
plot_tree(clfTK, filled=True, feature_names=['TMK'], class_names=TK_map)
plt.show()

../_images/cab9130dc536376eb91ba5b9718a689a20fe30fd1370d5026963d73d95b3c950.png

clfHKT = DecisionTreeClassifier()
clfHKT.fit(egywth[['TMK']], egywth[['HeizKuehlTageN']])
clfHKT.get_depth()

plt.figure(figsize=(20,10))
plot_tree(clfHKT, filled=True, feature_names=['TMK'], class_names=HKT_map)
plt.show()

../_images/bc888c6f287ac5aa913eb068489a3bf5ff8faf0af2df54adcb4afbe71d5ea9d9.png

Es zeigt sich, dass die originalen Grenzen und die Folge der Werte durchaus gut identifiziert werden, wenn auch nicht ganz präzise, da entsprechende Samples im Datensatz fehlen.

Trainieren wir einen Entscheidungsbaum für die Aktivität des EV_HT_740-Verbrauches, wie bei der logistischen Regression.

clfHT = DecisionTreeClassifier()
clfHT.fit(egywth[["SDK", "NM", "VPM", "TMK", "Weekday"]], egywth[['EV_HT_740_IS_ON']])
clfHT.get_depth()

plt.figure(figsize=(20,10))
plot_tree(clfHT, filled=True, feature_names=["SDK", "NM", "VPM", "TMK", "Weekday"], class_names=['Off',"On"])
plt.show()

../_images/d9cfbc54af86823a175e7051eef65a7d03cc2b2905ffe5b995d41b005291968d.png

Das resultiert in einen deutlich komplexeren Entscheidungsbaum mit einer Tiefe von 21 Knoten.

Prüfen wir einmal die Vorhersagequalität, indem wir den Trainingsdatensatz vorhersagen.

egywth["pred_DT"] = clfHT.predict(egywth[["SDK", "NM", "VPM", "TMK", "Weekday"]])

Als Vergleichsmetriken für Entscheidungsbäume die kategorische Werte vorhersagen, verwendet man die Metriken, die wir für die Logistische Regression diskutiert haben.

from sklearn.metrics import accuracy_score, f1_score

print('Accuracy: {:.2f}'.format(accuracy_score(egywth.EV_HT_740_IS_ON.values, egywth.pred_DT)))
print('F1-Score: {:.2f}'.format(f1_score(egywth.EV_HT_740_IS_ON, egywth.pred_DT)))

Accuracy: 1.00
F1-Score: 1.00

Hier zeigt sich, dass der Entscheidungsbaum den Ein/Aus-Zustand perfekt vorhersagen kann. Die Logistischen Regressionsmodelle im Vergleich erreichten nur eine Genauigkeit von 54% und 60%.

Es ist zu beachten, dass Modelle mit dieser perfekten Qualität meist nicht gewollt sind, da sie Überfitten (Overfitting) und dann nicht gut generalisieren. Generalisierung bedeutet, dass das Modell auch gut anwendbar auf neue Datensätze ist.

Overfitting, Train-Test-Split und Kreuzvalidation#

Um das Überfitting besser zu erkennen und die Generalisierbarkeit eines Modelles zu bewerten, verwendet man üblicherweise zur Bewertung und zum Vergleich von Modellen nicht einfach den Trainingsdatensatz, sondern teilt die Daten in einen Datensatz zum Trainieren und einem zum Testen (Train-Test-Split). Dabei darf der Testdatensatz keine Trainingsdaten enthalten.

Teilen wir den Datensatz einmal in einen Test- und einen Trainingsdatensatz mit jeweils 60% und 40% Daten auf und trainieren das Modell nur auf dem Trainingsdatensatz.

egywth_train=egywth.head(int(egywth.shape[0]*6/10)).copy()
egywth_test=egywth.tail(int(egywth.shape[0]*4/10)).copy()

clfHT_T = DecisionTreeClassifier()
clfHT_T.fit(egywth_train[["SDK", "NM", "VPM", "TMK", "Weekday"]], egywth_train[['EV_HT_740_IS_ON']])
clfHT_T.get_depth()

egywth_train["pred_DT"] = clfHT_T.predict(egywth_train[["SDK", "NM", "VPM", "TMK", "Weekday"]])
print('Train Accuracy: {:.2f}'.format(accuracy_score(egywth_train.EV_HT_740_IS_ON.values, egywth_train.pred_DT)))

Train Accuracy: 1.00

Wir erhalten wieder ein Modell, das zu 100% korrekt vorhersagt.

Wenden wir das Modell einmal auf dem Testdatensatz an.

egywth_test["pred_DT"] = clfHT_T.predict(egywth_test[["SDK", "NM", "VPM", "TMK", "Weekday"]])
print('Test Accuracy: {:.2f}'.format(accuracy_score(egywth_test.EV_HT_740_IS_ON.values, egywth_test.pred_DT)))

Test Accuracy: 0.16

Wir sehen jetzt, dass das Modell auf einmal sehr schlecht ist mit einer Genauigkeit von nur 16% (wir bedenken, dass eine Zufallswahl bereits 50% Genauigkeit hat). Das Modell, das also im Training perfekt war, ist im Test komplett schlecht. Das liegt zum einen daran, dass wir in der Logistischen Regression bereits gesehen haben, dass der Energieverbrauch im hinteren Bereich nahezu immer aktiv ist, also der Testdatensatz nicht dem Trainingsdatensatz gut entspricht. Dadurch lernt das Modell ein Verhalten, das im Testdatensatz gar nicht mehr vorkommt.

Dies können wir verhindern, indem wir die Trainings und Testdaten zufällig auswählen.

from sklearn.model_selection import train_test_split

egywthN=egywth.dropna()  # Wir entfernen hier wieder die NaN Werte, da einige Ensemble-Methoden keine NaN Werte unterstützen
egywth_train, egywth_test = train_test_split(egywthN, test_size=0.4)

clfHT_T = DecisionTreeClassifier()
clfHT_T.fit(egywth_train[["SDK", "NM", "VPM", "TMK", "Weekday"]], egywth_train[['EV_HT_740_IS_ON']])
clfHT_T.get_depth()

egywth_train["pred_DT"] = clfHT_T.predict(egywth_train[["SDK", "NM", "VPM", "TMK", "Weekday"]])
print('Train Accuracy: {:.2f}'.format(accuracy_score(egywth_train.EV_HT_740_IS_ON.values, egywth_train.pred_DT)))

Train Accuracy: 1.00

egywth_test["pred_DT"] = clfHT_T.predict(egywth_test[["SDK", "NM", "VPM", "TMK", "Weekday"]])
print('Test Accuracy: {:.2f}'.format(accuracy_score(egywth_test.EV_HT_740_IS_ON.values, egywth_test.pred_DT)))

Test Accuracy: 0.57

Um Abzusichern, dass man nicht zufällig ein guter Test- und Trainingsdatensatz auswählt, empfiehlt es sich das Sampling und Training mehrmals hintereinander zu wiederholen. Diese Verfahren nennt man \(k\)-Kreuzvalidation (\(k\)-Cross-Validation) wobei \(k\) die Anzahl der Wiederholungen ist. Auch hierfür bietet sklearn eine vorhandene Unterstützungsfunktion an.

from sklearn.model_selection import cross_val_score

cross_val_score(clfHT_T, egywth_train[["SDK", "NM", "VPM", "TMK", "Weekday"]], egywth_train[['EV_HT_740_IS_ON']], cv=5)

array([0.57272727, 0.59090909, 0.54545455, 0.63636364, 0.60550459])

Hier sehen, wir das trotz der Zufallsauswahl das für die Trainingsdaten ideale Modell immer noch nicht gut die Testdaten vorhersagen kann, es also nicht nur daran liegt, das nicht genug Daten verfügbar sind, sondern, das overfitted Modell einfach sich relativ schlecht generalisieren lässt. Das ist eine typische Eigenschaft von Entscheidungsbäumen.

Das Problem lässt sich reduzieren, wenn man die Tiefe der Bäume reduziert.

clfHT_T2 = DecisionTreeClassifier(max_depth=10)
clfHT_T2.fit(egywth_train[["SDK", "NM", "VPM", "TMK", "Weekday"]], egywth_train[['EV_HT_740_IS_ON']])
clfHT_T2.get_depth()

egywth_train["pred_DT2"] = clfHT_T2.predict(egywth_train[["SDK", "NM", "VPM", "TMK", "Weekday"]])
print('Train Accuracy: {:.2f}'.format(accuracy_score(egywth_train.EV_HT_740_IS_ON.values, egywth_train.pred_DT2)))

Train Accuracy: 0.77

egywth_test["pred_DT2"] = clfHT_T2.predict(egywth_test[["SDK", "NM", "VPM", "TMK", "Weekday"]])
print('Test Accuracy: {:.2f}'.format(accuracy_score(egywth_test.EV_HT_740_IS_ON.values, egywth_test.pred_DT2)))

Test Accuracy: 0.60

Dadurch wird zwar die Qualität des Modells auf dem Trainingsdatensatz schlechter, aber überraschenderweise steigt meist die Qualität auf dem Testdatensatz.

Support Vector Machines#

Support Vector Machines (SVMs) sind ein weiteres Modell, das zur Klassifikation und Regression verwendet werden kann. Sie sind besonders gut geeignet für Aufgaben, bei denen die Datenpunkte durch eine nichtlineare Entscheidungsgrenze getrennt werden können (Bei linearen Grenzen kann man logistische Modelle nutzen, bei scharfen Grenzen Entscheidungsbäume). SVM zielt darauf ab, die beste Trennlinie (oder Hyperebene in höheren Dimensionen) zu finden, die die Datenpunkte verschiedener Klassen mit maximalem Abstand trennen.

Lineare SVM#

Für ein einfaches binäres Klassifizierungsproblem mit zwei Klassen \( y_i \in \{-1, 1\} \) und Datenpunkten \( \bar{x}_i \in \mathbb{R}^n \), suchen wir eine Hyperebene, die die Daten trennt. Bei linearen SVM wir diese Hyperebene durch ein lineares Modell beschrieben:

\[ b + \bar{w} \cdot \bar{x}= 0 \]

Dabei ist \( \bar{w} \) der Normalenvektor zur Hyperebene und \(b\) ist der Bias (Verschiebungsterm). Damit sind lineare Kernel dem logistischen Regressionsmodell sehr ähnlich und zeigt eine ähnliche lineare Entscheidungsgrenze.

Der Hyperebene teilt den Raum so, dass das Vorzeichen

positiv ist mit \(b + \bar{w} \cdot \bar x_i \geq 0\) für \(y_i=1\)
negativ ist mit \(b + \bar{w} \cdot \bar x_i \lt 0\) für \(y_i=-1\)

Der Abstand zwischen den beiden nächsten Punkten beider Klassen (die als Support Vectors bezeichnet werden) und dem Hyperebene wird als Margin bezeichnet. Die SVM maximiert diese Margin, was gleichbedeutend mit der Minimierung von \(|\bar{w}|\) ist. Die Optimierungsaufgabe lautet daher:

\[ \min_{\bar{w}, b} \frac{1}{2} \|\bar{w}\|^2 \]

unter den Nebenbedingungen

\[ \quad y_i (b + \bar{w} \cdot \bar{x}_i) \geq 1, \, \forall i. \]

Der Kerneltrick bei nicht-lineare SVM#

Für nicht-lineare Probleme können wir die Datenpunkte in einen höherdimensionalen Raum transformieren, wo sie linear trennbar sind, so dass wir dort weiterhin ein Lineares Model nutzen können. Diese Transformation wird durch den sogenannten Kerneltrick erreicht. Ein Kernel ist eine Funktion \( K(\bar{x}_i, \bar{x}_j) \), die das Skalarprodukt der Datenpunkte im höherdimensionalen Raum berechnet, ohne dass die Transformation explizit durchgeführt werden muss. Beliebte Kernelfunktionen sind:

Linearkern: \( K(\bar{x}_i, \bar{x}_j) = \bar{x}_i \cdot \bar{x}_j \)
Polynomkern: \( K(\bar{x}_i, \bar{x}_j) = (\bar{x}_i \cdot \bar{x}_j + 1)^d \)
RBF-Kern (Radial Basis Function): \( K(\bar{x}_i, \bar{x}_j) = \exp(-\gamma \|\bar{x}_i - \bar{x}_j\|^2) \)

Damit ist der Kernel vom Prinzip vergleichbar mit der Transferfunktion in einem GAM-Model, mit dem Unterschied, dass der Kernel das Skalarprodukt transformiert.

Um den Kernelfunktionen Rechnung zu tragen, ändert sich das Optimierungsproblem zu:

\[ \min_{\bar{w}, b} \frac{1}{2} \|\bar{w}\|^2 + C \sum_{i=1}^n \xi_i \]

unter den Nebenbedingungen

\[ y_i (b + \bar{w} \cdot \phi( b + \bar{x}_i)) \geq 1 - \xi_i, \, \xi_i \geq 0, \, \forall i \]

Dabei ist \( \phi(\bar{x}) \) die Abbildung in den höheren dimensionsunabhängigen Raum und \( \xi_i \) sind die Schlupfvariablen. Diese sind notwendig, um bei nicht vollständig linear trennbaren Daten, die Fehlklassifikationen zu modellieren (gleich dem Fehlerterm \(\varepsilon\)).

Das Optimierungsproblems wird als Duales Problem gelöst. Die duale Formulierung ermöglicht es, die Berechnungen nur in Form von Skalarprodukten (oder Kernelfunktionen) durchzuführen:

\[ \max_{\alpha} \sum_{i=1}^n \alpha_i - \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j K(\bar{x}_i, \bar{x}_j) \]

mit den Lagrange-Multiplikatoren \( \alpha_i \) und unter den Nebenbedingungen

\[ \quad 0 \leq \alpha_i \leq C, \, \sum_{i=1}^n \alpha_i y_i = 0. \]

Die Entscheidungsfunktion im Dualraum wird durch die Lagrange-Multiplikatoren und Kernelfunktion ausgedrückt:

\[ \bar y = \text{sign}\left( b + \sum_{i=1}^n \alpha_i y_i K(\bar{x}_i, \bar{x}) \right). \]

SVM in SciKit#

Wir betrachten als illustratives Beispiel einmal ein zufällig erzeugtes Yin-Yang-Muster. Dies ist ein 2D-Datensatz, bei dem verschiedene Punkte unterschiedlich eingefärbt sind, und die Aufgabe besteht darin, die richtige Farbe basierend auf dem Punkt zu vorhersagen. Es handelt sich also um eine grundlegendes Klassifikationsproblem. Um die Aufgabe jedoch hinreichend komplex zu gestalten, führen wir die Farben in einem Spiralmuster ein. Wir erstellen die Daten wie folgt:

import plotly.express as px

np.random.seed(33)
N = 1000  # Anzahl der Punkte
X1 = np.random.normal(size=N)
X2 = np.random.normal(size=N)
X = np.column_stack((X1, X2))
y = X1 + X2 - 1.7*np.sin(1.2*(X1 - X2)) + np.random.normal(scale=0.5, size=N) > 0

fig=px.scatter(x=X1, y=X2, color=y, width=600, height=600, color_discrete_sequence=["black", "white"])
fig.update_traces(marker_line=dict(width=.3, color="black"))
fig.show()

/Users/jploennigs/miniconda3/envs/lehre/lib/python3.11/site-packages/plotly/express/_core.py:2065: FutureWarning: When grouping with a length-1 list-like, you will need to pass a length-1 tuple to get_group in a future version of pandas. Pass `(name,)` instead of `name` to silence this warning.
  sf: grouped.get_group(s if len(s) > 1 else s[0])

Das Bild zeigt weiße und schwarze Punkte, die ein unvollkommenes Yin-Yang-Muster mit einer unscharfen Grenze zwischen den Klassen bilden.

Der SVM-Klassifikator SVC ist im Paket sklearn.svm implementiert. Der Konstruktor der Klasse akzeptiert eine Anzahl von Argumenten, von denen die wichtigsten kernel sind, um verschiedene Kernel auszuwählen, sowie die entsprechenden Parameter für verschiedene Kernel, z.B. degree für den Polynomgrad und gamma für den radialen Skalierungsparameter.

Die Erstellung, das Fitting und Scoring des Modells folgen dem bekannten Muster

from sklearn.svm import SVC

m = SVC(kernel="linear")
_ = m.fit(X, y)
m.score(X, y)  # on training data

0.82

Wir erstellen uns eine Visualisierungsfunktion, um die Grenzen besser zu erkennen.

def DBPlot(m, X, y, nGrid = 100):
    x1_min, x1_max = X[:, 0].min() - 1, X[:, 0].max() + 1
    x2_min, x2_max = X[:, 1].min() - 1, X[:, 1].max() + 1
    xx1, xx2 = np.meshgrid(np.linspace(x1_min, x1_max, nGrid), 
                           np.linspace(x2_min, x2_max, nGrid))
    XX = np.column_stack((xx1.ravel(), xx2.ravel()))
    hatyy = m.predict(XX).reshape(xx1.shape)
    fig = px.imshow(hatyy, width=600, height=600)
    fig.add_scatter(x=X[:,0]/(x1_max-x1_min)*100+50, y=X[:,1]/(x2_max-x2_min)*100+50, mode="markers", 
        marker=dict(color='white', line=dict(width=.3, color="black")))
    fig.add_scatter(x=X[y,0]/(x1_max-x1_min)*100+50, y=X[y,1]/(x2_max-x2_min)*100+50, mode="markers", 
        marker=dict(color='black'))
    fig.update_coloraxes(showscale=False)
    fig.update_layout(showlegend=False)
    fig.show()

m = SVC(kernel="linear")  # linear kernel does not have important parameters
_ = m.fit(X, y)
DBPlot(m, X, y)

Das Ergebnis ist nicht zu schlecht - es erfasst den groben Unterschied der weißen und schwarzen Punkte, aber kann nicht den Kopf des Yin und Yangs modellieren.

Als nächstes wollen wir dies mit einem Polynomkern zweiten Grades probieren.

m = SVC(kernel="poly", degree=2)
_ = m.fit(X, y)
DBPlot(m, X, y)
m.score(X, y)

0.516

Wie Sie sehen können, ist der Polynomkern (2) in der Lage, ein blaues Band auf einem gelben Hintergrund darzustellen. Es ist fraglich, ob dies besser ist als das, was der lineare Kern leisten kann, aber man kann leicht erkennen, dass ein solches Band eine gute Darstellung für andere Arten von Daten wäre.

Als nächstes, repliziere das oben Genannte mit einem Grad-3-Kernel:

m = SVC(kernel="poly", degree=3)
_ = m.fit(X, y)
DBPlot(m, X, y)
m.score(X, y)

0.727

Und schließlich mit einem radialen Kernel:

m = SVC(kernel="rbf", gamma=1)
_ = m.fit(X, y)
DBPlot(m, X, y)
m.score(X, y)

0.907

Vergleichen wir diese mit den Entscheidungsbäumen und Ensamble-Modellen so sehen wir, dass diese den Trainingsdatensatz inklusiver der Ausnahmen gut erlernen, dadurch allerdings keine stetigen Grenzen erkennen.

m = DecisionTreeClassifier()
_ = m.fit(X, y)
DBPlot(m, X, y)
m.score(X, y)

1.0

m = RandomForestClassifier()
_ = m.fit(X, y)
DBPlot(m, X, y)
m.score(X, y)

1.0

Als nächstes testen wir die SVM-Modelle einmal auf der Energievorhersage.

clf_SVCL = SVC(kernel="linear")
clf_SVCL.fit(egywth_train[["SDK", "NM", "VPM", "TMK", "Weekday"]], egywth_train.EV_HT_740_IS_ON.values)

egywth_train["pred_SVCL"] = clf_SVCL.predict(egywth_train[["SDK", "NM", "VPM", "TMK", "Weekday"]])
print('Train Accuracy: {:.2f}'.format(accuracy_score(egywth_train.EV_HT_740_IS_ON.values, egywth_train.pred_SVCL)))
egywth_test["pred_SVCL"] = clf_SVCL.predict(egywth_test[["SDK", "NM", "VPM", "TMK", "Weekday"]])
print('Test Accuracy: {:.2f}'.format(accuracy_score(egywth_test.EV_HT_740_IS_ON.values, egywth_test.pred_SVCL)))

Train Accuracy: 0.59
Test Accuracy: 0.54

clf_SVCP = SVC(kernel="poly", degree=3)
clf_SVCP.fit(egywth_train[["SDK", "NM", "VPM", "TMK", "Weekday"]], egywth_train.EV_HT_740_IS_ON.values)

egywth_train["pred_SVCP"] = clf_SVCP.predict(egywth_train[["SDK", "NM", "VPM", "TMK", "Weekday"]])
print('Train Accuracy: {:.2f}'.format(accuracy_score(egywth_train.EV_HT_740_IS_ON.values, egywth_train.pred_SVCL)))
egywth_test["pred_SVCP"] = clf_SVCP.predict(egywth_test[["SDK", "NM", "VPM", "TMK", "Weekday"]])
print('Test Accuracy: {:.2f}'.format(accuracy_score(egywth_test.EV_HT_740_IS_ON.values, egywth_test.pred_SVCP)))

Train Accuracy: 0.59
Test Accuracy: 0.56

clf_SVCR = SVC(kernel="rbf", gamma=1)
clf_SVCR.fit(egywth_train[["SDK", "NM", "VPM", "TMK", "Weekday"]], egywth_train.EV_HT_740_IS_ON.values)

egywth_train["pred_SVCR"] = clf_SVCR.predict(egywth_train[["SDK", "NM", "VPM", "TMK", "Weekday"]])
print('Train Accuracy: {:.2f}'.format(accuracy_score(egywth_train.EV_HT_740_IS_ON.values, egywth_train.pred_SVCR)))
egywth_test["pred_SVCR"] = clf_SVCR.predict(egywth_test[["SDK", "NM", "VPM", "TMK", "Weekday"]])
print('Test Accuracy: {:.2f}'.format(accuracy_score(egywth_test.EV_HT_740_IS_ON.values, egywth_test.pred_SVCR)))

Train Accuracy: 0.97
Test Accuracy: 0.53

Die Vorhersagequalität dieser Modelle ist nicht sehr hoch. Das liegt daran, dass Trennlinien im Datensatz nicht gegeben sind. In solchen Fällen sind Entscheidungsbäume und Ensambles besser geeignet, obwohl sie wie gezeigt schnell zum Overfitting neigen. Dennoch gehören SVM mit zu den beliebtesten Modellen. Deshalb empfiehlt es sich immer vorher ein Scatter-Diagramm mit der Zielklasse als Farbcode zu erstellen, um zu sehen, ob sich klare Grenzen erkennen lassen.

px.scatter_matrix(egywth, dimensions=["SDK", "NM", "VPM", "TMK"], opacity=.2, color="EV_HT_740_IS_ON")

/Users/jploennigs/miniconda3/envs/lehre/lib/python3.11/site-packages/plotly/express/_core.py:2065: FutureWarning:

When grouping with a length-1 list-like, you will need to pass a length-1 tuple to get_group in a future version of pandas. Pass `(name,)` instead of `name` to silence this warning.

Regressionsbäume und Regressions-Ensemble-Modelle#

Wir können Entscheidungsbäume und Ensemble-Modelle auch als Regressionsmodell benutzen. Hierbei soll nicht eine spezifische Klasse einer kategorischen Variable vorhergesagt werden, sondern eine numerische Variable. Das Prinzip der Regressionsvarianten ist das gleiche wie beiden diskreten Modellen, nur werden die Ergebnisse nicht durch Mehrheitsabstimmung kombiniert, sondern linear addiert.

Vergleichen wir die oben genannten Varianten einmal in ihren Regressions-Varianten und sagen den Energieverbrauch ES_Lab wie bei den Regressionsmodellen voraus.

from sklearn.tree import DecisionTreeRegressor
from sklearn.ensemble import RandomForestRegressor, GradientBoostingRegressor, StackingRegressor, VotingRegressor
from sklearn.linear_model import LinearRegression
from sklearn.svm import SVR
from sklearn.metrics import mean_squared_error, root_mean_squared_error, r2_score
import time 

reg_models=[("Linear Model", LinearRegression()),
            ("Decision Tree", DecisionTreeRegressor()),
            ("Random Forest", RandomForestRegressor()),
            ("Gradient Boost", GradientBoostingRegressor()),
            ("XGBoost", xgb.XGBRegressor()),
            ("Stack", StackingRegressor(estimators=[('lm', LinearRegression()),('dt',DecisionTreeRegressor())])),
            ("Vote", VotingRegressor(estimators=[('lm', LinearRegression()),('dt',DecisionTreeRegressor())])),
            ("BoostStack", StackingRegressor(estimators=[('lm', LinearRegression()),('rf',RandomForestRegressor()),('xgb',xgb.XGBRegressor())])),
            ("SVM_l", SVR(kernel="linear")),
            ("SVM_p", SVR(kernel="poly")),
            ("SVM_r", SVR(kernel="rbf")),
            ("SVMStack", StackingRegressor(estimators=[('lm', LinearRegression()),('svm',SVR(kernel="linear")),('rf',RandomForestRegressor()),('xgb',xgb.XGBRegressor())])),]

resdf=[]
for mtype,model in reg_models:
    starttime=time.time()
    model.fit(egywth_train[["SDK", "NM", "VPM", "TMK", "Weekday"]], egywth_train.ES_Lab.values)
    fittime=time.time()
    pred_train = model.predict(egywth_train[["SDK", "NM", "VPM", "TMK", "Weekday"]])
    pred_test  = model.predict(egywth_test[["SDK", "NM", "VPM", "TMK", "Weekday"]])
    predtime=time.time()
    resdf.append({"type":mtype,
                  "train.MSE":mean_squared_error(egywth_train.ES_Lab.values, pred_train),
                  "train.RMSE":root_mean_squared_error(egywth_train.ES_Lab.values, pred_train),
                  "train.R2":r2_score(egywth_train.ES_Lab.values, pred_train),
                  "test.MSE":mean_squared_error(egywth_test.ES_Lab.values, pred_test),
                  "test.RMSE":root_mean_squared_error(egywth_test.ES_Lab.values, pred_test),
                  "test.R2":r2_score(egywth_test.ES_Lab.values, pred_test),
                  "fittime":fittime-starttime,
                  "predtime":predtime-fittime})

resdf=pd.DataFrame(resdf)
resdf

	type	train.MSE	train.RMSE	train.R2	test.MSE	test.RMSE	test.R2	fittime	predtime
0	Linear Model	152.313486	12.341535	0.874992	146.151880	12.089329	0.867139	0.001956	0.000903
1	Decision Tree	0.000000	0.000000	1.000000	245.468665	15.667440	0.776854	0.002025	0.000978
2	Random Forest	22.326007	4.725040	0.981676	134.852063	11.612582	0.877411	0.114827	0.011515
3	Gradient Boost	64.146613	8.009158	0.947353	135.826811	11.654476	0.876525	0.052310	0.002348
4	XGBoost	0.090179	0.300299	0.999926	158.962093	12.608017	0.855494	0.136693	0.002708
5	Stack	125.136616	11.186448	0.897297	141.773757	11.906879	0.871119	0.018857	0.001868
6	Vote	38.078372	6.170768	0.968748	157.582447	12.553185	0.856748	0.002605	0.001441
7	BoostStack	75.498437	8.688984	0.938036	132.088338	11.492969	0.879924	1.409700	0.013634
8	SVM_l	153.624725	12.394544	0.873916	149.441460	12.224625	0.864149	0.013319	0.005355
9	SVM_p	203.806134	14.276069	0.832731	168.219199	12.969934	0.847079	0.008967	0.005694
10	SVM_r	232.090618	15.234521	0.809517	215.019762	14.663552	0.804534	0.005978	0.018139
11	SVMStack	73.527099	8.574794	0.939654	130.004873	11.401968	0.881818	1.615750	0.019877

Hier sehen wir, wieder das Overfitten der Entscheidungsbäume im Trainingsdatensatz, aber schlechter als Regressionsmodelle abschneiden im Testdatensatz. Wir sehen auch, dass die Regressions-Ensamble-Modelle sogar besser abschneiden als die klassischen linearen Regressionsmodelle. Das liegt daran das die zugrundeliegenden Entscheidungsbäume vom Normalen linearen Verhalten abweichende Ausnahmen besser erfassen können. Die Stacking Varianten schneiden zum Teil am besten ab, aber weisen auch die größten Trainingszeiten auf.

Klassifikation

Contents

Klassifikation#

Folien #

Entscheidungsbäume zur Klassifikation#

Erstellen eines Entscheidungsbaums#

Auswahl des besten Attributes#

Beispiel#

Berechnung der Entropie des gesamten Datensatzes#

Berechnung der Entropie für jedes Attribut#

Entscheidungsbäume in SciKit-Learn#

Overfitting, Train-Test-Split und Kreuzvalidation#

Kombinationsmodelle (Ensemble Models)#

Bagging/Bootstrap - Random Forest#

Boosting#

Adaboost#

Gradient Boosting#

XGBoost#

Stacking#

Voting#

Support Vector Machines#

Lineare SVM#

Der Kerneltrick bei nicht-lineare SVM#

SVM in SciKit#

Regressionsbäume und Regressions-Ensemble-Modelle#

Klassifikation

Contents

Klassifikation#

Folien#

Entscheidungsbäume zur Klassifikation#

Erstellen eines Entscheidungsbaums#

Auswahl des besten Attributes#

Beispiel#

Berechnung der Entropie des gesamten Datensatzes#

Berechnung der Entropie für jedes Attribut#

Entscheidungsbäume in SciKit-Learn#

Overfitting, Train-Test-Split und Kreuzvalidation#

Kombinationsmodelle (Ensemble Models)#

Bagging/Bootstrap - Random Forest#

Boosting#

Adaboost#

Gradient Boosting#

XGBoost#

Stacking#

Voting#

Support Vector Machines#

Lineare SVM#

Der Kerneltrick bei nicht-lineare SVM#

SVM in SciKit#

Regressionsbäume und Regressions-Ensemble-Modelle#

Folien #