ID3-Algorithmus: Ein Rechenbeispiel

Dieser Artikel ist Teil 3 von 4 der Artikelserie Maschinelles Lernen mit Entscheidungsbaumverfahren und nun wollen wir einen Entscheidungsbaum aus Daten herleiten, jedoch ohne Programmierung, sondern direkt auf Papier (bzw. HTML :-).

Folgender Datensatz sei gegeben:

Zeile Kundenart Zahlungsgeschwindigkeit Kauffrequenz Herkunft Zahlungsmittel: Rechnung?
 1  Neukunde  niedrig  niedrig  Inland  false
 2  Neukunde  niedrig  niedrig  Ausland  false
 3  Stammkunde  niedrig  niedrig  Inland  true
 4  Normalkunde  mittel  niedrig  Inland  true
 5  Normalkunde  hoch  hoch  Inland  true
 6  Normalkunde  hoch  hoch  Ausland  false
 7  Stammkunde  hoch  hoch  Ausland  true
 8  Neukunde  mittel  niedrig  Inland  false
 9  Neukunde  hoch  hoch  Inland  true
 10  Normalkunde  mittel  hoch  Inland  true
 11  Neukunde  mittel  hoch  Ausland  true
 12  Stammkunde  mittel  niedrig  Ausland  true
 13  Stammkunde  niedrig  hoch  Inland  true
 14  Normalkunde  mittel  niedrig  Ausland  false

Gleich vorweg ein Disclaimer: Der Datensatz ist natürlich überaus klein, ja gerade zu winzig. Dafür würden wir in der Praxis niemals einen Machine Learning Algorithmus einsetzen. Dennoch bleiben wir besser übersichtlich und nachvollziehbar mit diesen 14 Zeilen. Das Lernziel dieser Übung ist es, ein Gefühl für die Erstellung von Entscheidungsbäumen zu erhalten.
Zu beachten ist ferner, dass dieser Datensatz bereits aggregiert ist, denn eigentlich nummerisch abbildbare Daten wurden in Klassen zusammengefasst.

Das Ziel:

Der Datensatz spielt wieder, welchem Kunden (ID) bisher die Zahlung per Rechnung erlaubt und nicht widerrufen wurde. Das Ziel soll sein, eine Vorhersage darüber zu machen zu können, wann ein Kunde per Rechnung zahlen darf und wann nicht (dann per Vorkasse).

Der Algorithmus:

Wir verwenden den ID3-Algorithmus in seiner Reinform. Der ID3-Algorithmus ist der gängigste Algorithmus zum Aufbau datengetriebener Entscheidungsbäume und es gibt mehrere Abwandlungen. Die Vorgehensweise des Algorithmus wird in dem Teil 2 der Artikelserie Entscheidungsbaum-Algorithmus ID3 erläutert.

1. Schritt: Auswählen des Attributes mit dem höchsten Informationsgewinn

Der Informationsgewinn eines Attributes (A) im Sinne des ID3-Algorithmus ist die Differenz aus der Entropie (E(S)) (siehe Teil 1 der Artikelserie Entropie, ein Maß für die Unreinheit in Daten) des gesamten Datensatzes (S) und der Summe aus den gewichteten Entropien des Attributes für jeden einzelnen Wert (Value i), der im Attribut vorkommt:
IG(S, A) = H(S) - \sum_{i=1}^n \frac{\bigl|S_i\bigl|}{\bigl|S\bigl|} \cdot H(S_i)

1.1 Gesamt-Entropie des Datensatzes berechnen

Erstmal schauen wir uns die Entropie des gesamten Datensatzes an. Die Entropie bezieht sich dabei auf das gewünschte Klassifikationsergebnis, also ist die Zahlung via Rechnung erlaubt oder nicht? Diese Frage wird entweder mit true oder false beantwortet.

H(S) = - \frac{9}{14} \cdot \log_2(\frac{9}{4}) - \frac{5}{14} \cdot \log_2(\frac{5}{4})  = 0.94

1.2 Berechnung der Informationsgewinne aller Attribute

Berechnen wir nun also die Informationsgewinne über alle Spalten.

Attribut Subset Count(true) Count(false)
Kundenart “Neukunde” 2 3
“Stammkunde” 4 0
“Normalkunde” 3 2

Wir zerlegen den gesamten Datensatz gedanklich in drei Kategorien der Kundenart und berechnen die Entropie bezogen auf das Klassifikationsziel:

H(S_{Neukunde}) = - \frac{2}{5} \cdot \log_2(\frac{2}{5}) - \frac{3}{5} \cdot \log_2(\frac{3}{5})  = 0.97

H(S_{Stammkunde}) = - \frac{4}{4} \cdot \log_2(\frac{4}{4}) - \frac{0}{4} \cdot \log_2(\frac{0}{4})  = 0.00

H(S_{Normalkunde}) = - \frac{3}{5} \cdot \log_2(\frac{3}{5}) - \frac{2}{5} \cdot \log_2(\frac{2}{5})  = 0.97

Zur Erinnerung, der Informationsgewinn (Information Gain) wird wie folgt berechnet:

    \[ IG(S, A_{Kundenart}) =  - \sum_{i=1}^n \frac{\bigl|S_i\bigl|}{\bigl|S\bigl|} \cdot H(S_i) \]

Angewendet auf das Attribut “Kundenart”…

    \[ IG(S, A_{Kundenart}) =  H(S) - \frac{\bigl|S_{Neukunde}\bigl|}{\bigl|S\bigl|} \cdot H(S_{Neukunde}) - \frac{\bigl|S_{Stammkunde}\bigl|}{\bigl|S\bigl|} \cdot H(S_{Stammkunde}) - \frac{\bigl|S_{Normalkunde}\bigl|}{\bigl|S\bigl|} \cdot H(S_{Normalkunde}) \]

… erhalten wir der Formal nach folgenden Informationsgewinn:

    \[ IG(S, A_{Kundenart}) =  0.94 - \frac{5}{14} \cdot 0.97 - \frac{4}{14} \cdot 0.00 - \frac{5}{14} \cdot 0.97 = 0.247 \]

Nun für die weiteren Spalten:

Attribut Subset Count(true) Count(false)
Zahlungsgeschwindigkeit “niedrig” 2 2
“mittel” 4 2
“schnell” 3 1

Entropien für die “Zahlungsgeschwindigkeit”:

H(S_{niedrig}) = - \frac{2}{4} \cdot \log_2(\frac{2}{4}) - \frac{2}{4} \cdot \log_2(\frac{2}{4})  = 1.00

H(S_{mittel}) = - \frac{4}{6} \cdot \log_2(\frac{4}{6}) - \frac{2}{6} \cdot \log_2(\frac{2}{6})  = 0.92

H(S_{schnell}) = - \frac{3}{4} \cdot \log_2(\frac{3}{4}) - \frac{1}{4} \cdot \log_2(\frac{1}{4})  = 0.81

So berechnen wir wieder den Informationsgewinn:

    \[ IG(S, A_{Zahlungsgeschwindigkeit}) =  H(S) - \frac{\bigl|S_{niedrig}\bigl|}{\bigl|S\bigl|} \cdot H(S_{niedrig}) - \frac{\bigl|S_{mittel}\bigl|}{\bigl|S\bigl|} \cdot H(S_{mittel}) - \frac{\bigl|S_{schnell}\bigl|}{\bigl|S\bigl|} \cdot H(S_{schnell}) \]

Einsatzen und ausrechnen:

    \[ IG(S, A_{Zahlungsgeschwindigkeit}) =  0.94 - \frac{4}{14} \cdot 1.00 - \frac{6}{14} \cdot 0.92 - \frac{4}{14} \cdot 0.81 = 0.029 \]

Und nun für die Spalte “Kauffrequenz”:

Attribut Subset Count(true) Count(false)
Kauffrequenz “niedrig” 3 4
“hoch” 6 1

Entropien:

H(S_{niedrig}) = - \frac{3}{7} \cdot \log_2(\frac{3}{7}) - \frac{4}{7} \cdot \log_2(\frac{4}{7})  = 0.99

H(S_{hoch}) = - \frac{6}{7} \cdot \log_2(\frac{6}{7}) - \frac{1}{7} \cdot \log_2(\frac{1}{7})  = 0.59

Informationsgewinn:

    \[ IG(S, A_{Kauffrequenz}) =  H(S) - \frac{\bigl|S_{niedrig}\bigl|}{\bigl|S\bigl|} \cdot H(S_{niedrig}) - \frac{\bigl|S_{hoch}\bigl|}{\bigl|S\bigl|} \cdot H(S_{hoch}) \]

Einsetzen und Ausrechnen:

    \[ IG(S, A_{Kauffrequenz}) =  0.94 - \frac{7}{14} \cdot 1.00 - \frac{7}{14} \cdot 0.59 = 0.150 \]

Und last but not least die Spalte “Herkunft”:

Attribut Subset Count(true) Count(false)
Herkunft “Inland” 6 2
“Ausland” 3 3

Entropien:

H(S_{Inland}) = - \frac{6}{8} \cdot \log_2(\frac{6}{8}) - \frac{2}{8} \cdot \log_2(\frac{2}{8})  = 0.81

H(S_{Ausland}) = - \frac{3}{6} \cdot \log_2(\frac{3}{6}) - \frac{3}{6} \cdot \log_2(\frac{3}{6})  = 1.00

Informationsgewinn:

    \[ IG(S, A_{Herkunft}) =  H(S) - \frac{\bigl|S_{Inland}\bigl|}{\bigl|S\bigl|} \cdot H(S_{Inland}) - \frac{\bigl|S_{Ausland}\bigl|}{\bigl|S\bigl|} \cdot H(S_{Ausland}) \]

Einsetzen und Ausrechnen:

    \[ IG(S, A_{Herkunft}) =  0.94 - \frac{8}{14} \cdot 0.81 - \frac{6}{14} \cdot 1.00 = 0.05 \]

2. Schritt: Anlegen des Wurzel-Knotens

Der Informationsgewinn ist für das Attribut “Kundenart” am größten, daher entscheiden wir uns im Sinne des ID3-Algorithmus für dieses Attribut als Wurzel-Knoten.

3. Schritt: Rekursive Wiederholung (!!!)

Nun stellt sich natürlich die Frage: Wie geht es weiter?

Der Algorithmus kann eigentlich nur eines: Einen Wurzelknoten finden. Diesen Vorgang müssen wir nun nur noch rekursiv wiederholen, und das tun wir wie folgt.

Der Datensatz wurde bereits aufgeteilt in die drei Kundenarten. Für jede Kundenart ergibt sich jeweils ein Subset mit den verbleibenden Attributen. Für alle drei Subsets erstellen wir dann wieder einen Wurzelknoten, so dass ein neuer Ast entsteht.

3.1 Erster Rekursionsschritt

Machen wir also weiter und bestimmen wir das nächste Attribut nach der Kundenart, für die Fälle Kundenart = “Neukunde”:

Zeile Kundenart Zahlungsgeschwindigkeit Kauffrequenz Herkunft Zahlungsmittel: Rechnung?
 1  Neukunde  niedrig  niedrig  Inland  false
 2  Neukunde  niedrig  niedrig  Ausland  false
 8  Neukunde  mittel  niedrig  Inland  false
 9  Neukunde  hoch  hoch  Inland  true
 11  Neukunde  mittel  hoch  Ausland  true

Die Entropie des Gesamtdatensatzes (ja, es ist für diesen Schritt betrachtet der gesamte Datensatz!) ist wie folgt:

H(S_{Neukunde}) = - \frac{2}{5} \cdot \log_2(\frac{2}{5}) - \frac{3}{5} \cdot \log_2(\frac{3}{5})  = 0.97

Die Entropie ist weit weg von einer bestimmten Wahrscheinlichkeit (nahe der Gleichverteilung). Daher müssen wir hier nochmal ansetzen und losrechnen:

Entropien für “Zahlungsgeschwindigkeit” bei Neukunden:

H(S_{niedrig}) = 0.00

H(S_{mittel}) = 1.00

H(S_{hoch}) = 0.00

Informationsgewinn des Attributes “Zahlungsgeschwindigkeit” bei Neukunden:

    \[ IG(S_{Neukunde},A_{Zahlungsgeschwindigkeit}) = 0.97 - \frac{3}{5} \cdot 0.00 - \frac{2}{5} \cdot 1.00 -  \frac{1}{5} \cdot 0.00 = 0.57 \]

Betrachtung der Spalte “Kauffrequenz” bei Neukunden:

Entropien für “Kauffrequenz” bei Neukunden:

H(S_{niedrig}) = 0.00

H(S_{hoch}) = 0.00

Informationsgewinn des Attributes “Kauffrequenz” bei Neukunden:

    \[ IG(S_{Neukunde},A_{Kauffrequenz}) = 0.97 - \frac{3}{5} \cdot 0.00 - \frac{2}{5} \cdot 0.00 = 0.97 \]

Betrachtung der Spalte “Herkunft” bei Neukunden:

Entropien für “Herkunft” bei Neukunden:

H(S_{Inland}) = 0.92

H(S_{hoch}) = 1.00

Informationsgewinn des Attributes “Herkunft” bei Neukunden:

    \[ IG(S_{Neukunde},A_{Herkunft}) = 0.97 - \frac{3}{5} \cdot 0.92 - \frac{2}{5} \cdot 1.00 = 0.018 \]

Wir entscheiden uns also für das Attribut “Kauffrequenz” als Ast nach der Entscheidung “Neukunde”, denn dieses Attribut bring uns den größten Informationsgewinn und trennt uns die Unterscheidung für oder gegen das Zahlungsmittel “Rechnung” eindeutig auf.

3.1 Zweiter Rekursionsschritt

Was passiert mit der Kundenart “Stammkunde”?

Zeile Kundenart Zahlungsgeschwindigkeit Kauffrequenz Herkunft Zahlungsmittel: Rechnung?
 3  Stammkunde  niedrig  niedrig  Inland  true
 7  Stammkunde  hoch  hoch  Ausland  true
 12  Stammkunde  mittel  niedrig  Ausland  true
 13  Stammkunde  niedrig  hoch  Inland  true

Die Antwort ist einfach: Nichts!
Wer ein Stammkunde ist, dem wurde stets die Zahlung per Rechnung erlaubt.

H(S_{Stammkunde}) = 0.0

3.1 Dritter Rekursionsschritt

Fehlt nun nur noch die Frage nach der Unterscheidung von Normalkunden.

Zeile Kundenart Zahlungsgeschwindigkeit Kauffrequenz Herkunft Zahlungsmittel: Rechnung?
 4  Normalkunde  mittel  niedrig  Inland  true
 5  Normalkunde  hoch  hoch  Inland  true
 6  Normalkunde  hoch  hoch  Ausland  false
 14  Normalkunde  mittel  niedrig  Ausland  false

Zwar ist die Entropie des Subsets der Normalkunden…

H(S_{Normalkunde}) = 1.0

… denkbar schlecht, da maximal. Aber wir können genauso vorgehen, wie wir es bei dem Subset der Neukunden getan haben. Ich nehme es nun aber vorweg: Wenn wir uns den Datensatz näher ansehen, erkennen wir, dass wir diese Gesamtentropie von 1.0 für das Subset “Normalkunde” nicht mit den Attributen “Kauffrequenz” oder “Herkunft” reduzieren können, da dieses auch für sich betrachtet in Entropien der Größe 1.0 erhalten werden. Das Attribut “Herkunft” hingegen teilt den Datensatz sauber in true und false auf:

Somit ist der Informationsgewinn für das Attribut “Herkunft” am größten und wir haben unseren Baum komplett und – glücklicherweise – eindeutig bestimmen können!

Ergebnis: Der Entscheidungsbaum

Somit haben wir den Entscheidungsbaum über den ID3-Algorithmus erstellt, der eine Auskunft darüber macht, ob einem Kunden die Zahlung über Rechnung (statt Vorkasse) erlaubt wird:

true = Rechnung als Zahlungsmittel erlaubt
false = Rechnung als Zahlungsmittel nicht erlaubt

Lineare Regression in Python mit Scitkit-Learn

Die lineare Regressionsanalyse ist ein häufiger Einstieg ins maschinelle Lernen um stetige Werte vorherzusagen (Prediction bzw. Prädiktion). Hinter der Regression steht oftmals die Methode der kleinsten Fehlerquadrate und die hat mehr als eine mathematische Methode zur Lösungsfindung (Gradientenverfahren und Normalengleichung). Alternativ kann auch die Maximum Likelihood-Methode zur Regression verwendet werden. Wir wollen uns in diesem Artikel nicht auf die Mathematik konzentrieren, sondern uns direkt an die Anwendung mit Python Scikit-Learn machen:

Haupt-Lernziele:

  • Einführung in Machine Learning mit Scikit-Learn
  • Lineare Regression mit Scikit-Learn

Neben-Lernziele:

  • Datenvorbereitung (Data Preparation) mit Pandas und Scikit-Learn
  • Datenvisualisierung mit der Matplotlib direkt und indirekt (über Pandas)

Was wir inhaltlich tun:

Der Versuch einer Vorhersage eines Fahrzeugpreises auf Basis einer quantitativ-messbaren Eigenschaft eines Fahrzeuges.


Die Daten als Download

Für dieses Beispiel verwende ich die Datei “Automobil_data.txt” von Kaggle.com. Die Daten lassen sich über folgenden Link downloaden, nur leider wird ein (kostenloser) Account benötigt:
https://www.kaggle.com/toramky/automobile-dataset/downloads/automobile-dataset.zip
Sollte der Download-Link unerwartet mal nicht mehr funktionieren, freue ich mich über einen Hinweis als Kommentar 🙂

Die Entwicklungsumgebung

Ich verwende hier die Python-Distribution Anaconda 3 und als Entwicklungs-Umgebung Spyder (in Anaconda enthalten). Genauso gut funktionieren jedoch auch Jupyter Notebook, Eclipse mit PyDev oder direkt die IPython QT-Console.


Zuerst einmal müssen wir die Daten in unsere Python-Session laden und werden einige Transformationen durchführen müssen. Wir starten zunächst mit dem Importieren von drei Bibliotheken NumPy und Pandas, deren Bedeutung ich nicht weiter erläutern werde, somit voraussetze.

Wir nutzen die Pandas-Bibliothek, um die “Automobile_data.txt” in ein pd.DataFrame zu laden.

Schauen wir uns dann die ersten fünf Zeilen in IPython via dataSet.head().

Hinweis: Der Datensatz hat viele Spalten, so dass diese in der Darstellung mit einem Backslash \ umgebrochen werden.

Gleich noch eine weitere Ausgabe dataSet.info(), die uns etwas über die Beschaffenheit der importierten Daten verrät:

Einige Spalten entsprechen hinsichtlich des Datentypes nicht der Erwartung. Für die Spalten ‘horsepower’ und ‘peak-rpm’ würde ich eine Ganzzahl (Integer) erwarten, für ‘price’ hingegen eine Fließkommazahl (Float), allerdings sind die drei Spalten als Object deklariert. Mit Trick 17 im Data Science, der Anzeige der Minimum- und Maximum-Werte einer zu untersuchenden Datenreihe, kommen wir dem Übeltäter schnell auf die Schliche:

Datenbereinigung

Für eine Regressionsanalyse benötigen wir nummerische Werte (intervall- oder ratioskaliert), diese möchten wir auch durch richtige Datentypen-Deklaration herstellen. Nun wird eine Konvertierung in den gewünschten Datentyp jedoch an den (mit ‘?’ aufgefüllten) Datenlücken scheitern.

Schauen wir uns doch einmal die Datenreihen an, in denen in der Spalte ‘peak-rpm’ Fragezeichen stehen:

Zwei Datenreihen sind vorhanden, bei denen ‘peak-rpm’ mit einem ‘?’ aufgefüllt wurde. Nun könnten wir diese Datenreihen einfach rauslöschen. Oder mit sinnvollen (im Sinne von wahrscheinlichen) Werten auffüllen. Vermutlichen haben beide Einträge – beide sind OHC-Motoren mit 4 Zylindern – eine ähnliche Drehzahl-Angabe wie vergleichbare Motoren. Mit folgendem Quellcode, gruppieren wir die Spalten ‘engine-type’ und ‘num-of-cylinders’ und bilden für diese Klassen den arithmetischen Mittelwert (.mean()) für die ‘peak-rpm’.

Und schauen wir uns das Ergebnis an:

Ein Vier-Zylinder-OHC-Motor hat demnach durchschnittlich einen Drehzahl-Peak von 5155 Umdrehungen pro Minute. Ohne nun (fahrlässigerweise) auf die Verteilung in dieser Klasse zu achten, nehmen wir einfach diesen Schätzwert, um die zwei fehlende Datenpunkte zu ersetzen.

Wir möchten jedoch die Original-Daten erhalten und legen ein neues DataSet (dataSet_c) an, in welches wir die Korrekturen vornehmen:

Nun können wir die fehlenden Peak-RPM-Einträge mit unserem Schätzwert ersetzen:

Was bei einer Drehzahl-Angabe noch funktionieren mag, ist für anderen Spalten bereits etwas schwieriger: Die beiden Spalten ‘price’ und ‘horsepower’ sind ebenfalls vom Typ Object, da sie ‘?’ enthalten. Verzichten wir einfach auf die betroffenen Zeilen:

Datenvisualisierung mit Pandas

Wir wollen uns nicht lange vom eigentlichen Ziel ablenken, dennoch nutzen wir die Visualisierungsfähigkeiten der Pandas-Library (welche die Matplotlib inkludiert), um uns dann die Anzahlen an Einträgen nach Hersteller der Fahrzeuge (Spalte ‘make’) anzeigen zu lassen:

Oder die durchschnittliche PS-Zahl nach Hersteller:

Vorbereitung der Regressionsanalyse

Nun kommen wir endlich zur Regressionsanalyse, die wir mit Scikit-Learn umsetzen möchten. Die Regressionsanalyse können wir nur mit intervall- oder ratioskalierten Datenspalten betreiben, daher beschränken wir uns auf diese. Die “price”-Spalte nehmen wir jedoch heraus und setzen sie als unsere Zielgröße fest.

Interessant ist zudem die Betrachtung vorab, wie die einzelnen nummerischen Attribute untereinander korrelieren. Dafür nehmen wir auch die ‘price’-Spalte wieder in die Betrachtung hinein und hinterlegen auch eine Farbskala mit dem Preis (höhere Preise, hellere Farben).

Die lineare Korrelation ist hier sehr interessant, da wir auch nur eine lineare Regression beabsichtigen.

Wie man in dieser Scatter-Matrix recht gut erkennen kann, scheinen einige Größen-Paare nahezu perfekt zu korrelieren, andere nicht.

Korrelation…

  • …nahezu perfekt linear: highway-mpg vs city-mpg (mpg = Miles per Gallon)
  • … eher nicht gegeben: highway-mpg vs height
  • … nicht linear, dafür aber nicht-linear: highway-mpg vs price

Nun, wir wollen den Preis eines Fahrzeuges vorhersagen, wenn wir eine andere quantitative Größe gegeben haben. Auf den Preis bezogen, erscheint mir die Motorleistung (Horsepower) einigermaßen linear zu korrelieren. Versuchen wir hier die lineare Regression und setzen somit die Spalte ‘horsepower’ als X und ‘price’ als y fest.

Die gängige Konvention ist übrigens, X groß zu schreiben, weil hier auch mehrere x-Dimensionen enthalten sein dürfen (multivariate Regression). y hingegen, ist stets nur eine Zielgröße (eine Dimension).

Die lineare Regression ist ein überwachtes Verfahren des maschinellen Lernens, somit müssen wir unsere Prädiktionsergebnisse mit Test-Daten testen, die nicht für das Training verwendet werden dürfen. Scitkit-Learn (oder kurz: sklearn) bietet hierfür eine Funktion an, die uns das Aufteilen der Daten abnimmt:

Zu beachten ist dabei, dass die Daten vor dem Aufteilen in Trainings- und Testdaten gut zu durchmischen sind. Auch dies übernimmt die train_test_split-Funktion für uns, nur sollte man im Hinterkopf behalten, dass die Ergebnisse (auf Grund der Zufallsauswahl) nach jedem Durchlauf immer wieder etwas anders aussehen.

Lineare Regression mit Scikit-Learn

Nun kommen wir zur Durchführung der linearen Regression mit Scitkit-Learn, die sich in drei Zeilen trainieren lässt:

Aber Vorsicht! Bevor wir eine Prädiktion durchführen, wollen wir festlegen, wie wir die Güte der Prädiktion bewerten wollen. Die gängigsten Messungen für eine lineare Regression sind der MSE und R².

MSE = \frac{\sum_{i=1}^n (y_i - \hat{y_i})^2}{n}

Ein großer MSE ist schlecht, ein kleiner gut.

R^2 = 1 - \frac{MSE}{Var(y)}= \frac{\frac{1}{n} \cdot \sum_{i=1}^n (y_i - \hat{y_i})^2}{\frac{1}{n} \cdot \sum_{i=1}^n (y_i - \hat{\mu_y})^2}

Ein kleines R² ist schlecht, ein großes R² gut. Ein R² = 1.0 wäre theoretisch perfekt (da der Fehler = 0.00 wäre), jedoch in der Praxis unmöglich, da dieser nur bei absolut perfekter Korrelation auftreten würde. Die Klasse LinearRegression hat eine R²-Messmethode implementiert (score(x, y)).

Die Ausgabe (ein Beispiel!):

Nach jedem Durchlauf ändert sich mit der Datenaufteilung (train_test_split()) das Modell etwas und auch R² schwankt um eine gewisse Bandbreite. Berauschend sind die Ergebnisse dabei nicht, und wenn wir uns die Regressionsgerade einmal ansehen, wird auch klar, warum:

Bei kleineren Leistungsbereichen, etwa bis 100 PS, ist die Preis-Varianz noch annehmbar gering, doch bei höheren Leistungsbereichen ist die Spannweite deutlich größer.

Egal wie wir eine Gerade in diese Punktwolke legen, wir werden keine befriedigende Fehlergröße erhalten.

Nehmen wir einmal eine andere Spalte für X, bei der wir vor allem eine nicht-lineare Korrelation erkannt haben: “highway-mpg”

Wenn wir dann das Training wiederholen:

Die R²-Werte sind nicht gerade berauschend, und das erklärt sich auch leicht, wenn wir die Trainings- und Testdaten sowie die gelernte Funktionsgerade visualisieren:

Die Gerade lässt sich nicht wirklich gut durch diese Punktwolke legen, da letztere eher eine Kurve als eine Gerade bildet. Im Grunde könnte eine Gerade noch einigermaßen gut in den Bereich von 22 bis 43 mpg passen und vermutlich annehmbare Ergebnisse liefern. Die Wertebereiche darunter und darüber jedoch verzerren zu sehr und sorgen zudem dafür, dass die Gerade auch innerhalb des mittleren Bereiches zu weit nach oben verschoben ist (ggf. könnte hier eine Ridge-/Lasso-Regression helfen).

Richtig gute Vorhersagen über nicht-lineare Verhältnisse können jedoch nur mit einer nicht-linearen Regression erreicht werden.

Nicht-lineare Regression mit Scikit-Learn

Nicht-lineare Regressionsanalysen erlauben es uns, nicht-lineare korrelierende Werte-Paare als Funktion zu erlernen. Im folgenden Scatter-Plot sehen wir zum einen die gewohnte lineare Regressionsgerade (y = a * x + b) in rot, eine polinominale Regressionskurve dritten Grades (y = a * x³ + b * x² + c * x + d) in violet sowie einen Entscheidungsweg einer Entscheidungsbaum-Regression in gelb.

Nicht-lineare Regressionsanalysen passen sich dem Verlauf der Punktwolke sehr viel besser an und können somit in der Regel auch sehr gute Vorhersageergebnisse liefern. Ich ziehe hier nun jedoch einen Gedankenstrich, liefere aber den Quellcode für die lineare Regression als auch für die beiden nicht-linearen Regressionen mit:

Python Script Regression via Scikit-Learn

Weitere Anmerkungen

  • Bibliotheken wie Scitkit-Learn erlauben es, machinelle Lernverfahren schnell und unkompliziert anwenden zu können. Allerdings sollte man auch verstehen, wei diese Verfahren im Hintergrund mathematisch arbeiten. Diese Bibliotheken befreien uns also nicht gänzlich von der grauen Theorie.
  • Statt der “reinen” lineare Regression (LinearRegression()) können auch eine Ridge-Regression (Ridge()), Lasso-Regression (Lasso()) oder eine Kombination aus beiden als sogenannte ElasticNet-Regression (ElasticNet()). Bei diesen kann über Parametern gesteuert werden, wie stark Ausreißer in den Daten berücksichtigt werden sollen.
  • Vor einer Regression sollten die Werte skaliert werden, idealerweise durch Standardisierung der Werte (sklearn.preprocessing.StandardScaler()) oder durch Normierung (sklearn.preprocessing.Normalizer()).
  • Wir haben hier nur zwei-dimensional betrachtet. In der Praxis ist das jedoch selten ausreichend, auch der Fahrzeug-Preis ist weder von der Motor-Leistung, noch von dem Kraftstoffverbrauch alleine abhängig – Es nehmen viele Größen auf den Preis Einfluss, somit benötigen wir multivariate Regressionsanalysen.

Unsupervised Learning in R: K-Means Clustering

Die Clusteranalyse ist ein gruppenbildendes Verfahren, mit dem Objekte Gruppen – sogenannten Clustern zuordnet werden. Die dem Cluster zugeordneten Objekte sollen möglichst homogen sein, wohingegen die Objekte, die unterschiedlichen Clustern zugeordnet werden möglichst heterogen sein sollen. Dieses Verfahren wird z.B. im Marketing bei der Zielgruppensegmentierung, um Angebote entsprechend anzupassen oder im User Experience Bereich zur Identifikation sog. Personas.

Es gibt in der Praxis eine Vielzahl von Cluster-Verfahren, eine der bekanntesten und gebräuchlichsten Verfahren ist das K-Means Clustering, ein sog. Partitionierendes Clusterverfahren. Das Ziel dabei ist es, den Datensatz in K Cluster zu unterteilen. Dabei werden zunächst K beliebige Punkte als Anfangszentren (sog. Zentroiden) ausgewählt und jedem dieser Punkte der Punkt zugeordnet, zu dessen Zentrum er die geringste Distanz hat. K-Means ist ein „harter“ Clusteralgorithmus, d.h. jede Beobachtung wird genau einem Cluster zugeordnet. Zur Berechnung existieren verschiedene Distanzmaße. Das gebräuchlichste Distanzmaß ist die quadrierte euklidische Distanz:

D^2 = \sum_{i=1}^{v}(x_i - y_i)^2

Nachdem jede Beobachtung einem Cluster zugeordnet wurde, wird das Clusterzentrum neu berechnet und die Punkte werden den neuen Clusterzentren erneut zugeordnet. Dieser Vorgang wird so lange durchgeführt bis die Clusterzentren stabil sind oder eine vorher bestimmte Anzahl an Iterationen durchlaufen sind.
Das komplette Vorgehen wird im Folgenden anhand eines künstlich erzeugten Testdatensatzes erläutert.

Zunächst wird ein Testdatensatz mit den Variablen „Alter“ und „Einkommen“ erzeugt, der 12 Fälle enthält. Als Schritt des „Data preprocessing“ müssen zunächst beide Variablen standardisiert werden, da ansonsten die Variable „Alter“ die Clusterbildung zu stark beeinflusst.

Das Ganze geplottet:

Wie bereits eingangs erwähnt müssen Cluster innerhalb möglichst homogen und zu Objekten anderer Cluster möglichst heterogen sein. Ein Maß für die Homogenität die „Within Cluster Sums of Squares“ (WSS), ein Maß für die Heterogenität „Between Cluster Sums of Squares“ (BSS).

Diese sind beispielsweise für eine 3-Cluster-Lösung wie folgt:

Sollte man die Anzahl der Cluster nicht bereits kennen oder sind diese extern nicht vorgegeben, dann bietet es sich an, anhand des Verhältnisses von WSS und BSS die „optimale“ Clusteranzahl zu berechnen. Dafür wird zunächst ein leerer Vektor initialisiert, dessen Werte nachfolgend über die Schleife mit dem Verhältnis von WSS und WSS gefüllt werden. Dies lässt sich anschließend per „Screeplot“ visualisieren.

Die „optimale“ Anzahl der Cluster zählt sich am Knick der Linie ablesen (auch Ellbow-Kriterium genannt). Alternativ kann man sich an dem Richtwert von 0.2 orientieren. Unterschreitet das Verhältnis von WSS und BSS diesen Wert, so hat man die beste Lösung gefunden. In diesem Beispiel ist sehr deutlich, dass eine 3-Cluster-Lösung am besten ist.

Fazit: Mit K-Means Clustering lassen sich schnell und einfach Muster in Datensätzen erkennen, die, gerade wenn mehr als zwei Variablen geclustert werden, sonst verborgen blieben. K-Means ist allerdings anfällig gegenüber Ausreißern, da Ausreißer gerne als separate Cluster betrachtet werden. Ebenfalls problematisch sind Cluster, deren Struktur nicht kugelförmig ist. Dies ist vor der Durchführung der Clusteranalyse mittels explorativer Datenanalyse zu überprüfen.

R als Tool im Process Mining

Die Open Source Sprache R ermöglicht eine Vielzahl von Analysemöglichkeiten, die von einer einfachen beschreibenden Darstellung eines Prozesses bis zur umfassenden statistischen Analyse reicht. Dabei können Daten aus einem Manufacturing Execution System, kurz MES, als Basis der Prozessanalyse herangezogen werden. R ist ein Open Source Programm, welches sich für die Lösung von statischen Aufgaben im Bereich der Prozessoptimierung sehr gut eignet, erfordert jedoch auf Grund des Bedienungskonzepts als Scriptsprache, grundlegende Kenntnisse der Programmierung. Aber auch eine interaktive Bedienung lässt sich mit einer Einbindung der Statistikfunktionen in ein Dashboard erreichen. Damit können entsprechend den Anforderungen, automatisierte Analysen ohne Programmierkenntnisse realisiert werden.

Der Prozess als Spagetti Diagramm

Um einen Überblick zu erhalten, wird der Prozess in einem „process value flowchart“, ähnlich einem Spagetti‐ Diagramm dargestellt und je nach Anforderung mit Angaben zu den Key Performance Indicators ergänzt. Im konkreten Fall werden die absolute Anzahl und der relative Anteil der bearbeiteten Teile angegeben. Werden Teile wie nachfolgend dargestellt, aufgrund von festgestellten Mängel bei der Qualitätskontrolle automatisiert ausgeschleust, können darüber Kennzahlen für den Ausschuss ermittelt werden.

Der Prozess in Tabellen und Diagrammen

Im folgenden Chart sind grundlegende Angaben zu den ausgeführten Prozessschritten, sowie deren Varianten dargestellt. Die Statistikansicht bietet eine Übersicht zu den Fällen, den sogenannte „Cases“, sowie zur Dauer und Taktzeit der einzelnen Aktivitäten. Dabei handelt es sich um eine Fertigungsline mit hohem Automatisierungsgrad, bei der jeder Fertigungsschritt im MES dokumentiert wird. Die Tabelle enthält statistische Angaben zur Zykluszeit, sowie der Prozessdauer zu den einzelnen Aktivitäten. In diesem Fall waren keine Timestamps für das Ende der Aktivität vorhanden, somit konnte die Prozessdauer nicht berechnet werden.

Die Anwendung von Six Sigma Tools

R verfügt über eine umfangreiche Sammlung von Bibliotheken zur Datendarstellung, sowie der Prozessanalyse. Darin sind auch Tools aus Six Sigma enthalten, die für die weitere Analyse der Prozesse eingesetzt werden können. In den folgenden Darstellungen wird die Möglichkeit aufgezeigt, zwei Produktionszeiträume, welche über eine einfache Datumseingabe im Dashboard abgegrenzt werden, gegenüber zu stellen. Dabei handelt es sich um die Ausbringung der Fertigung in Stundenwerten, die für jeden Prozessschritt errechnet wird. Das xbar und r Chart findet im Bereich der Qualitätssicherung häufig Anwendung zur ersten Beurteilung des Prozessoutputs.

Zwei weitere Six Sigma typische Kennzahlen zur Beurteilung der Prozessfähigkeit sind der Cp und Cpk Wert und deren Ermittlung ein Bestandteil der R Bibliotheken ist. Bei der Berechnung wird von einer Normalverteilung der Daten ausgegangen, wobei das Ergebnis aus der Überprüfung dieser Annahme im Chart durch Zahlen, als auch grafisch dargestellt wird.

Von Interesse ist auch die Antwort auf die Frage, welchem Trend folgt der Prozess? Bereits aus der Darstellung der beiden Produktionszeiträume im Box‐Whiskers‐Plot könnte man anhand der Mediane auf einen Trend zu einer Verschlechterung der Ausbringung schließen, den der Interquartilsabstand nicht widerspiegelt. Eine weitere Absicherung einer Aussage über den Trend, kann über einen statistischen Vergleichs der Mittelwerte erfolgen.

Der Modellvergleich

Besteht die Anforderung einer direkten Gegenüberstellung des geplanten, mit dem vorgefundenen, sogenannten „Discovered Model“, ist aufgrund der Komplexität beim Modellvergleich, dieser in R mit hohem Programmieraufwand verbunden. Besser geeignet sind dafür spezielle Process Miningtools. Diese ermöglichen den direkten Vergleich und unterstützen bei der Analyse der Ursachen zu den dargestellten Abweichungen. Bei Produktionsprozessen handelt es sich meist um sogenannte „Milestone Events“, die bei jedem Fertigungsschritt durch das MES dokumentiert werden und eine einfache Modellierung des Target Process ermöglichen. Weiterführende Analysen der Prozessdaten in R sind durch einen direkten Zugriff über ein API realisierbar oder es wurde vollständig integriert. Damit eröffnen sich wiederum die umfangreichen Möglichkeiten bei der statistischen Prozessanalyse, sowie der Einsatz von Six Sigma Tools aus dem Qualitätsmanagement. Die Analyse kann durch eine, den Kundenanforderungen entsprechende Darstellung in einem Dashboard vereinfacht werden, ermöglicht somit eine zeitnahe, weitgehend automatisierte Prozessanalyse auf Basis der Produktionsdaten.

Resümee

Process Mining in R ermöglicht zeitnahe Ergebnisse, die bis zur automatisierten Analyse in Echtzeit reicht. Der Einsatz beschleunigt erheblich das Process Controlling und hilft den Ressourceneinsatz bei der Datenerhebung, sowie deren Analyse zu reduzieren. Es kann als stand‐alone Lösung zur Untersuchung des „Discovered Process“ oder als Erweiterung für nachfolgende statistische Analysen eingesetzt werden. Als stand‐alone Lösung eignet es sich für Prozesse mit geringer Komplexität, wie in der automatisierten Fertigung. Besteht eine hohe Diversifikation oder sollen standortübergreifende Prozessanalysen durchgeführt werden, übersteigt der Ressourcenaufwand rasch die Kosten für den Einsatz einer Enterprise Software, von denen mittlerweile einige angeboten werden.

 

Einstieg in das Maschinelle Lernen mit Python(x,y)

Python(x,y) ist eine Python-Distribution, die speziell für wissenschaftliche Arbeiten entwickelt wurde. Es umfasst neben der Programmiersprache auch die Entwicklungsumgebung Spyder und eine Reihe integrierter Python-Bibliotheken. Mithilfe von Python(x,y) kann eine Vielzahl von Interessensbereichen bearbeitet werden. Dazu zählen unter anderem Bildverarbeitung oder auch das maschinelle Lernen. Das All-in-One-Setup für Python(x,y) ist für alle gängigen Betriebssysteme online erhältlich. Read more

R Data Frames meistern mit dplyr – Teil 2

Dieser Artikel ist Teil 2 von 2 aus der Artikelserie R Data Frames meistern mit dplyr.

Noch mehr Datenbank-Features

Im ersten Teil dieser Artikel-Serie habe ich die Parallelen zwischen Data Frames in R und Relationen in SQL herausgearbeitet und gezeigt, wie das Paket dplyr eine Reihe von SQL-analogen Operationen auf Data Frames standardisiert und optimiert. In diesem Teil möchte ich nun drei weitere Analogien aufzeigen. Es handelt sich um die

  • Window Functions in dplyr als Entsprechung zu analytischen Funktionen in SQL,
  • Joins zwischen Data Frames als Pendant zu Tabellen-Joins
  • Delegation von Data Frame-Operationen zu einer bestehenden SQL-Datenbank

Window Functions

Im letzten Teil habe ich gezeigt, wie durch die Kombination von group_by() und summarise() im Handumdrehen Aggregate entstehen. Das Verb group_by() schafft dabei, wie der Name schon sagt, eine Gruppierung der Zeilen des Data Frame anhand benannter Schlüssel, die oft ordinaler oder kategorialer Natur sind (z.B. Datum, Produkt oder Mitarbeiter).

Ersetzt man die Aggregation mit summarise() durch die Funktion mutate(), um neue Spalten zu bilden, so ist der Effekt des group_by() weiterhin nutzbar, erzeugt aber „Windows“, also Gruppen von Datensätzen des Data Frames mit gleichen Werten der Gruppierungskriterien. Auf diesen Gruppen können nun mittels mutate() beliebige R-Funktionen angewendet werden. Das Ergebnis ist im Gegensatz zu summarise() keine Verdichtung auf einen Datensatz pro Gruppe, sondern eine Erweiterung jeder einzelnen Zeile um neue Werte. Das soll folgendes Beispiel verdeutlichen:

Das group_by() unterteilt den Data Frame nach den 4 gleichen Werten von a. Innerhalb dieser Gruppen berechnen die beispielsweise eingesetzten Funktionen

  • row_number(): Die laufende Nummer in dieser Gruppe
  • n(): Die Gesamtgröße dieser Gruppe
  • n_distinct(b): Die Anzahl verschiedener Werte von b innerhalb der Gruppe
  • rank(desc(b)): Den Rang innerhalb der selben Gruppe, absteigend nach b geordnet
  • lag(b): Den Wert von b der vorherigen Zeile innerhalb derselben Gruppe
  • lead(b): Analog den Wert von b der folgenden Zeile innerhalb derselben Gruppe
  • mean(b): Den Mittelwert von b innerhalb der Gruppe
  • cumsum(b): Die kumulierte Summe der b-Werte innerhalb der Gruppe.

Wichtig ist hierbei, dass die Anwendung dieser Funktionen nicht dazu führt, dass die ursprüngliche Reihenfolge der Datensätze im Data Frame geändert wird. Hier erweist sich ein wesentlicher Unterschied zwischen Data Frames und Datenbank-Relationen von Vorteil: Die Reihenfolge von Datensätzen in Data Frames ist stabil und definiert. Sie resultiert aus der Abfolge der Elemente auf den Vektoren, die die Data Frames bilden. Im Gegensatz dazu haben Tabellen und Views keine Reihenfolge, auf die man sich beim SELECT verlassen kann. Nur mit der ORDER BY-Klausel über eindeutige Schlüsselwerte erreicht man eine definierte, stabile Reihenfolge der resultierenden Datensätze.

Die Wirkungsweise von Window Functions wird noch besser verständlich, wenn in obiger Abfrage das group_by(a) entfernt wird. Dann wirken alle genannten Funktionen auf der einzigen Gruppe, die existiert, nämlich dem gesamten Data Frame:

Anwendbar sind hierbei sämtliche Funktionen, die auf Vektoren wirken. Diese müssen also wie in unserem Beispiel nicht unbedingt aus dplyr stammen. Allerdings komplettiert das Package die Menge der sinnvoll anwendbaren Funktionen um einige wichtige Elemente wie cumany() oder n_distinct().

Data Frames Hand in Hand…

In relationalen Datenbanken wird häufig angestrebt, das Datenmodell zu normalisieren. Dadurch bekommt man die negativen Folgen von Datenredundanz, wie Inkonsistenzen bei Datenmanipulationen und unnötig große Datenvolumina, in den Griff. Dies geschieht unter anderem dadurch, dass tabellarische Datenbestände aufgetrennt werden Stammdaten- und Faktentabellen. Letztere beziehen sich über Fremdschlüsselspalten auf die Primärschlüssel der Stammdatentabellen. Durch Joins, also Abfragen über mehrere Tabellen und Ausnutzen der Fremdschlüsselbeziehungen, werden die normalisierten Tabellen wieder zu einem fachlich kompletten Resultat denormalisiert.

In den Data Frames von R trifft man dieses Modellierungsmuster aus verschiedenen Gründen weit seltener an als in RDBMS. Dennoch gibt es neben der Normalisierung/Denormalisierung andere Fragestellungen, die sich gut durch Joins beantworten lassen. Neben der Zusammenführung von Beobachtungen unterschiedlicher Quellen anhand charakteristischer Schlüssel sind dies bestimmte Mengenoperationen wie Schnitt- und Differenzmengenbildung.

Die traditionelle R-Funktion für den Join zweier Data Frames lautet merge(). dplyr erweitert den Funktionsumfang dieser Funktion und sorgt für sprechendere Funktionsnamen und Konsistenz mit den anderen Operationen.

Hier ein synthetisches Beispiel:

Nun gilt es, die Verkäufe aus dem Data Frame sales mit den Produkten in products zusammenzuführen und auf Basis von Produkten Bilanzen zu erstellen. Diese Denormalisierung geschieht durch das Verb inner_join() auf zweierlei Art und Weise:

Die Ergebnisse sind bis auf die Reihenfolge der Spalten und der Zeilen identisch. Außerdem ist im einen Fall der gemeinsame Schlüssel der Produkt-Id als prod_id, im anderen Fall als id enthalten. dplyr entfernt also die Spalten-Duplikate der Join-Bedingungen. Letzere wird bei Bedarf im by-Argument der Join-Funktion angegeben. R-Experten erkennen hier einen „Named Vector“, also einen Vektor, bei dem jedes Element einen Namen hat. Diese Syntax verwendet dplyr, um elegant die äquivalenten Spalten zu kennzeichnen. Wird das Argument by weggelassen, so verwendet dplyr im Sinne eines „Natural Join“ automatisch alle Spalten, deren Namen in beiden Data Frames vorkommen.

Natürlich können wir dieses Beispiel mit den anderen Verben erweitern, um z.B. eine Umsatzbilanz pro Produkt zu erreichen:

dplyr bringt insgesamt 6 verschiedene Join-Funktionen mit: Neben dem bereits verwendeten Inner Join gibt es die linksseitigen und rechtsseitigen Outer Joins und den Full Join. Diese entsprechen genau der Funktionalität von SQL-Datenbanken. Daneben gibt es die Funktion semi_join(), die in SQL etwa folgendermaßen ausgedrückt würde:

Das Gegenteil, also ein NOT EXISTS, realisiert die sechste Join-Funktion: anti_join(). Im folgenden Beispiel sollen alle Produkte ausgegeben werden, die noch nie verkauft wurden:

… und in der Datenbank

Wir schon mehrfach betont, hat dplyr eine Reihe von Analogien zu SQL-Operationen auf relationalen Datenbanken. R Data Frames entsprechen Tabellen und Views und die dplyr-Operationen den Bausteinen von SELECT-Statements. Daraus ergibt sich die Möglichkeit, dplyr-Funktionen ohne viel Zutun auf eine bestehende Datenbank und deren Relationen zu deligieren.

Mir fallen folgende Szenarien ein, wo dies sinnvoll erscheint:

  • Die zu verarbeitende Datenmenge ist zu groß für das Memory des Rechners, auf dem R läuft.
  • Die interessierenden Daten liegen bereits als Tabellen und Views auf einer Datenbank vor.
  • Die Datenbank hat Features, wie z.B. Parallelverarbeitung oder Bitmap Indexe, die R nicht hat.

In der aktuellen Version 0.5.0 kann dplyr nativ vier Datenbank-Backends ansprechen: SQLite, MySQL, PostgreSQL und Google BigQuery. Ich vermute, unter der Leserschaft des Data Science Blogs dürfte MySQL (oder der Fork MariaDB) die weiteste Verbreitung haben, weshalb ich die folgenden Beispiele darauf zeige. Allerdings muss man beachten, dass MySQL keine Window Funktionen kennt, was sich 1:1 auf die Funktionalität von dplyr auswirkt.

Im folgenden möchte ich zeigen, wie dplyr sich gegen eine bestehende MySQL-Datenbank verbindet und danach einen bestehenden R Data Frame in eine neue Datenbanktabelle wegspeichert:

Die erste Anweisung verbindet R mit einer bestehenden MySQL-Datenbank. Danach lade ich den Data Frame diamonds aus dem Paket ggplot2. Mit str() wird deutlich, dass drei darin enthaltene Variablen vom Typ Factor sind. Damit dplyr damit arbeiten kann, werden sie mit mutate() in Character-Vektoren gewandelt. Dann erzeugt die Funktion copy_to() auf der MySQL-Datenbank eine leere Tabelle namens diamonds, in die die Datensätze kopiert werden. Danach erhält die Tabelle noch drei Indexe (von dem der erste aus drei Segmenten besteht), und zum Schluß führt dplyr noch ein ANALYSE der Tabelle durch, um die Werteverteilungen auf den Spalten für kostenbasierte Optimierung zu bestimmen.

Meistens aber wird bereits eine bestehende Datenbanktabelle die interessierenden Daten enthalten. In diesem Fall lautet die Funktion zum Erstellen des Delegats tbl():

Die Rückgabewerte von copy_to() und von tbl() sind natürlich keine reinrassigen Data Frames, sondern Objekte, auf die die Operationen von dplyr wirken können, indem sie auf die Datenbank deligiert werden. Im folgenden Beispiel sollen alle Diamanten, die ein Gewicht von mindestens 1 Karat haben, pro Cut, Color und Clarity nach Anzahl und mittlerem Preis bilanziert werden:

Die Definition der Variablen bilanz geschieht dabei komplett ohne Interaktion mit der Datenbank. Erst beim Anzeigen von Daten wird das notwendige SQL ermittelt und auf der DB ausgeführt. Die ersten 10 resultierenden Datensätze werden angezeigt. Mittels der mächtigen Funktion explain() erhalten wir das erzeugte SQL-Kommando und sogar den Ausführungsplan auf der Datenbank. SQL-Kundige werden erkennen, dass die verketteten dplyr-Operationen in verschachtelte SELECT-Statements umgesetzt werden.

Zu guter Letzt sollen aber meistens die Ergebnisse der dplyr-Operationen irgendwie gesichert werden. Hier hat der Benutzer die Wahl, ob die Daten auf der Datenbank in einer neuen Tabelle gespeichert werden sollen oder ob sie komplett nach R transferiert werden sollen. Dies erfolgt mit den Funktionen compute() bzw. collect():

Durch diese beiden Operationen wurde eine neue Datenbanktabelle „t_bilanz“ erzeugt und danach der Inhalt der Bilanz als Data Frame zurück in den R-Interpreter geholt. Damit schließt sich der Kreis.

Fazit

Mit dem Paket dplyr von Hadley Wickham wird die Arbeit mit R Data Frames auf eine neue Ebene gehoben. Die Operationen sind konsistent, vollständig und performant. Durch den Verkettungs-Operator %>% erhalten sie auch bei hoher Komplexität eine intuitive Syntax. Viele Aspekte der Funktionalität lehnen sich an Relationale Datenbanken an, sodass Analysten mit SQL-Kenntnissen rasch viele Operationen auf R Data Frames übertragen können.

Zurück zu R Data Frames meistern mit dplyr – Teil 1.

 

Numerical Python – Einführung in wissenschaftliches Rechnen mit NumPy

NumPy steht für Numerical Python und ist eines der bekanntesten Pakete für alle Python-Programmierer mit wissenschaftlichen Hintergrund. Von persönlichen Kontakten erfuhr ich, dass NumPy heute in der Astrophysik fast genauso verwendet wird wie auch von sogenannten Quants im Investment-Banking. Das NumPy-Paket ist sicherlich ein Grundstein des Erfolges für Python in der Wissenschaft und für den häufigen Einsatz für die Implementierung von Algorihtmen des maschinellen Lernens in Python.

Die zentrale Datenstruktur in NumPy ist das mehrdimensionale Array. Dieses n-dimensionale Array (ndarray) ist eine sehr mächtige Datenstruktur und verwende ich beispielsweise in meinem Artikel über den k-Nächste-Nachbarn-Algorithmus. Die Besonderheit des NumPy-Arrays ist, dass es ein mehrdimensionaler Container für homogene Daten ist. Ein Datentyp gilt also für das gesamte Array, nicht nur für bestimmte Zeilen oder Spalten!

Read more

Statistical Relational Learning – Part 2

In the first part of this series onAn Introduction to Statistical Relational Learning”, I touched upon the basic Machine Learning paradigms, some background and intuition of the concepts and concluded with how the MLN template looks like. In this blog, we will dive in to get an in depth knowledge on the MLN template; again with the help of sample examples. I would then conclude by highlighting the various toolkit available and some of its differentiating features.

MLN Template – explained

A Markov logic network can be thought of as a group of formulas incorporating first-order logic and also tied with a weight. But what exactly does this weight signify?

Weight Learning

According to the definition, it is the log odds between a world where F is true and a world where F is false,

and captures the marginal distribution of the corresponding predicate.

Each formula can be associated with some weight value, that is a positive or negative real number. The higher the value of weight, the stronger the constraint represented by the formula. In contrast to classical logic, all worlds (i.e., Herbrand Interpretations) are possible with a certain probability [1]. The main idea behind this is that the probability of a world increases as the number of formulas it violates decreases.

Markov logic networks with its probabilistic approach combined to logic posit that a world is less likely if it violates formulas unlike in pure logic where a world is false if it violates even a single formula. Consider the case when a formula with high weight i.e. more significance is violated implying that it is less likely in occurrence.

Another important concept during the first phase of Weight Learning while applying an MLN template is “Grounding”. Grounding means to replace each variable/function in predicate with constants from the domain.

Weight Learning – An Example

Note: All examples are highlighted in the Alchemy MLN format

Let us consider an example where we want to identify the relationship between 2 different types of verb-noun pairs i.e noun subject and direct object.

The input predicateFormula.mln file contains

  1. The predicates nsubj(verb, subject) and dobj(verb, object) and
  2. Formula of nsubj(+ver, +s) and dobj(+ver, +o)

These predicates or rules are to learn all possible SVO combinations i.e. what is the probability of a Subject-Verb-Object combination. The + sign ensures a cross product between the domains and learns all combinations. The training database consists of the nsubj and dobj tuples i.e. relations is the evidence used to learn the weights.

When we run the above command for this set of rules against the training evidence, we learn the weights as here:

Note that the formula is now grounded by all occurrences of nsubj and dobj tuples from the training database or evidence and the weights are attached to it at the start of each such combination.

But it should be noted that there is no network yet and this is just a set of weighted first-order logic formulas. The MLN template we created so far will generate Markov networks from all of our ground formulas. Internally, it is represented as a factor graph.where each ground formula is a factor and all the ground predicates found in the ground formula are linked to the factor.

Inference

The definition goes as follows:

Estimate probability distribution encoded by a graphical model, for a given data (or observation).

Out of the many Inference algorithms, the two major ones are MAP & Marginal Inference. For example, in a MAP Inference we find the most likely state of world given evidence, where y is the query and x is the evidence.

which is in turn equivalent to this formula.

Another is the Marginal Inference which computes the conditional probability of query predicates, given some evidence. Some advanced inference algorithms are Loopy Belief Propagation, Walk-SAT, MC-SAT, etc.

The probability of a world is given by the weighted sum of all true groundings of a formula i under an exponential function, divided by the partition function Z i.e. equivalent to the sum of the values of all possible assignments. The partition function acts a normalization constant to get the probability values between 0 and 1.

Inference – An Example

Let us draw inference on the the same example as earlier.

After learning the weights we run inference (with or without partial evidence) and query the relations of interest (nsubj here), to get inferred values.

Tool-kits

Let’s look at some of the MLN tool-kits at disposal to do learning and large scale inference. I have tried to make an assorted list of all tools here and tried to highlight some of its main features & problems.

For example, BUGS i.e. Bayesian Logic uses a Swift Compiler but is Not relational! ProbLog has a Python wrapper and is based on Horn clauses but has No Learning feature. These tools were invented in the initial days, much before the present day MLN looks like.

ProbCog developed at Technical University of Munich (TUM) & the AI Lab at Bremen covers not just MLN but also Bayesian Logic Networks (BLNs), Bayesian Networks & ProLog. In fact, it is now GUI based. Thebeast gives a shell to analyze & inspect model feature weights & missing features.

Alchemy from University of Washington (UoW) was the 1st First Order (FO) probabilistic logic toolkit. RockIt from University of Mannheim has an online & rest based interface and uses only Conjunctive Normal Forms (CNF) i.e. And-Or format in its formulas.

Tuffy scales this up by using a Relational Database Management System (RDBMS) whereas Felix allows Large Scale inference! Elementary makes use of secondary storage and Deep Dive is the current state of the art. All of these tools are part of the HAZY project group at Stanford University.

Lastly, LoMRF i.e. Logical Markov Random Field (MRF) is Scala based and has a feature to analyse different hypothesis by comparing the difference in .mln files!

 

Hope you enjoyed the read. The content starts from basic concepts and ends up highlighting key tools. In the final part of this 3 part blog series I would explain an application scenario and highlight the active research and industry players. Any feedback as a comment below or through a message is more than welcome!

Back to Part I – Statistical Relational Learning

Additional Links:

[1] Knowledge base files in Logical Markov Random Fields (LoMRF)

[2] (still) nothing clever Posts categorized “Machine Learning” – Markov Logic Networks

[3] A gentle introduction to statistical relational learning: maths, code, and examples

Wahrscheinlichkeitsverteilungen – Zentralen Grenzwertsatz verstehen mit Pyhton

Wahrscheinlichkeitsverteilung sind im Data Science ein wichtiges Handwerkszeug. Während in der Mathevorlesung die Dynamik dieser Verteilungen nur durch wildes Tafelgekritzel schwierig erlebbar zu machen ist, können wir mit Programmierkenntnissen (in diesem Fall wieder mit Python) eine kleine Testumgebung für solche Verteilungen erstellen, um ein Gefühl dafür zu entwickeln, wie unterschiedlich diese auf verschiedene Wahrscheinlichkeitswerte, Varianz und Mengen an Datenpunkten reagieren und wann sie untereinander annäherungsweise ersetzbar sind – der zentrale Grenzwertsatz. Den Schwerpunkt lege ich in diesem Artikel auf die Binominal- und Normalverteilung.

Für die folgenden Beispiele werden folgende Python-Bibliotheken benötigt:

Read more

R Data Frames meistern mit dplyr – Teil 1

Dieser Artikel ist Teil 1 von 2 aus der Artikelserie R Data Frames meistern mit dplyr.

Data Frames sind das Arbeitspferd von R, wenn Daten in eine Struktur gepackt werden sollen, um sie einzulesen, zu säubern, zu transformieren, zu analysieren und zu visualisieren. Abstrakt gesprochen sind Data Frames nichts anderes als Relationen, also Mengen von Tupels, gebildet aus Elementen von geeigneten Mengen.

Dieses Konzept hat sich auch außerhalb des R-Universums bestens bewährt, umzusammengesetzte Daten, Beobachtungen oder Geschäftsobjekte zu repräsentieren. Der beste Beleg für diese Aussage sind die allgegenwärtigen Relationalen Datenbanksysteme (RDBMS). Dort werden Relationen als Tabellen (Tables) oder Sichten (Views) bezeichnet, und darauf wirkt eine mächtige, imperative Abfrage- und Manipulationssprache namens Structured Query Language, kurz:
SQL.

SQL ist in meiner Wahrnehmung die Lingua Franca der Datenverarbeitung, da sie im Kern über sehr viele Softwareprodukte gleich ist und nach erstaunlich geringem Lernaufwand mächtige Auswerte- und Manipulationsoperationen an den Daten ermöglicht. Hier eine SQL-Anweisung, um eine fiktive Tabelle aller Verkäufe (SALES) nach den Top-10-Kunden in diesem Jahr zu untersuchen:

Dieser selbsterklärliche Code aus sieben Zeilen hat einen enormen Effekt: Er fast alle Verkäufe des Jahres 2016 auf Basis der Kundennummer zusammen, berechnet dabei die Summe aller Verkaufsbeträge, zählt die Anzahl der Transaktionen und der verschiedenen vom Kunden gekauften Produkte. Nach Sortierung gemäß absteigenden Umsatzes schneidet der Code nach dem 10. Kunden ab.

SQL kann aber mit der gleichen Eleganz noch viel mehr: Beispielsweise verbinden Joins die Daten mehrerer Tabellen über Fremschlüsselbeziehungen oder analytische Funktionen bestimmen Rankings und laufende Summen. Wäre es nicht toll, wenn R ähnlich effektiv mit Data Frames analoger Struktur umgehen könnte? Natürlich! Aber schon der Versuch, obige SQL-Query auf einem R Data Frame mit den althergebrachten Bordmitteln umzusetzen (subset, aggregate, merge, …), führt zu einem unleserlichen, uneleganten Stück Code.

Genau in diese Bresche springt der von vielen anderen Bibliotheken bekannte Entwickler Hadley Wickham mit seiner Bibliothek dplyr: Sie standardisiert Operationen auf Data Frames analog zu SQL-Operationen und führt zu einer wirklich selbsterklärlichen Syntax, die noch dazu sehr performant abgearbeitet wird. Ganz analog zu ggplot2, das sich an der Grammar of Graphics orientiert, spricht Wickham bei dplyr von einer Grammar of Data Manipulation. Die Funktionen zur Manipulation nennt er folgerichtig Verben.

Dabei treten naturgemäß eine Reihe von Analogien zwischen den Teilen eines SELECT-Statements und dplyr-Funktionen auf:

SELECT-Operation dplyr-Funktion
Bildung der Spaltenliste select()
Bildung eines Ausdrucks mutate()
WHERE-Klausel filter()
GROUP BY Spaltenliste group_by()
Bildung von Aggregaten wie sum() etc. summarise()
HAVING-Klausel filter()
ORDER BY Spaltenliste arrange()
LIMIT-Klausel slice()

Die ersten Schritte

Ich möchte die Anwendung von dplyr mithilfe des Standard-Datensatzes Cars93
aus dem Paket MASS demonstrieren:

Die erste Aufgabe soll darin bestehen, aus dem Data Frame alle Autos zu selektieren, die vom Hersteller “Audi” stammen und nur Model und Anzahl Passagiere auszugeben. Hier die Lösung in Standard-R und mit dplyr:

Man sieht, dass die neue Funktion filter() der Zeilenselektion, also der Funktion subset() entspricht. Und die Auswahl der Ergebnisspalten, die in Standard-R durch Angabe einer Spaltenliste zwischen [ und ] erfolgt, hat in dplyr das Pendant in der Funktion select().

select() ist sehr mächtig in seinen Möglichkeiten, die Spaltenliste anzugeben. Beispielsweise funktioniert dies über Positionslisten, Namensmuster und ggf. das auch noch negiert:

Die obige Abfrage projiziert aus dem Data Frame sämtliche Spalten, die nicht mit “L” beginnen. Das scheint zunächst ein unscheinbares Feature zu sein, zahlt sich aber aus, wenn analytische Data Frames Dutzende oder Hunderte von Spalten haben, deren Bezeichnung sich nach einem logischen Namensschema richtet.
Soweit ist das noch nicht spektakulär. dplyr hilft uns in obigem Beispiel, als erstes bestimmte Datensätze zu selektieren und als zweites die interessierenden Spalten zu projizieren. dplyr ist aber bezüglich der Verarbeitung von Data Frames sehr intuitiv und funktional, sodass wir früher oder später viele Operationen auf unserem Data Frame verketten werden. So erreichen wir die Mächtigkeit von SQL und mehr. Die funktionale Syntax aus dem letzten Beispiel wird dann ganz schnell unleserlich, da die Verabeitungsreihenfolge (zuerst filter(), dann select()) nur durch Lesen des Codes von innen nach außen und von rechts nach links ersichtlich wird.

Daher geht dplyr einen Schritt weiter, indem es den eleganten Verkettungsoperator %>% aus dem magrittr-Paket importiert und zur Verfügung stellt. Dadurch werden die verschachtelten Ausdrücke in Sequenzen von Operationen gewandelt und somit sehr viel lesbarer und wartbarer:

Diese in meinen Augen geniale Syntax durch den neuen Operator %>% erlaubt einen sequenziellen Aufbau der Operationen auf einem Data Frame. Benutzer der Unix-Kommandozeile werden hier leicht die Analogie zu Pipes erkennen. Ganz abstrakt kann man sagen, dass damit folgende Operationen äquivalent sind:

Traditioneller Funktionsaufruf Verkettung mit %>%
f(a,b) a %>% f(b)
f(a,b,c) a %>% f(b,c)
g(f(a,b),c) a %>% f(b) %>% g(c)

Weiteres erklärt die Dokumentation zum %>%-Operator im Paket magrittr mithilfe
des Befehls ?magrittr::‘%>%‘.

Neue Variablen

Durch die Funtionen select() und filter() können wir aus Data Frames Spalten projizieren und Zeilen selektieren. Ergebnisse neuer Ausdrücke entstehen hingegen mit dem Verb mutate():

Im obigen Beispiel wird zunächst auf den Hersteller Audi selektiert und danach auf einen Streich zwei neue Spalten eingeführt, l_100km und eur. Durch Zuweisen auf eine neue Variable wird das fertige Ergebnis dauerhaft gespeichert. Hierbei handelt es sich wieder um ein natives Data Frame-Objekt. Die Operation transmute() arbeitet analog zu mutate(), verwirft aber nach Bildung der Ausdrücke alle nicht genannten Spalten. Somit können wir obiges Beispiel auch wie folgt schreiben:

Aggregate

Neben der Selektion von Zeilen und Spalten sowie der Bildung abgeleiteter Ausdrücke ist bei Datenbanktabellen die Gruppierung und Aggregation mit GROUP BY eine sehr wichtige Operation. Dies gilt auch für Data Frames in R, wenngleich hier der Funktionsumfang über diverse Funktionen wie table() oder aggregate() verteilt ist und wenig intuitiv ist.

Hier bringt dplyr ebenfalls eine großartige Verbesserung mit. Das entsprechende Verb heißt group_by(). Diese Operation wird zusammen mit einer Spaltenliste auf ein Data Frame angewendet:

Das Ergebnis von group_by() ist ein Objekt, das “mehr” ist als ein Data Frame, sondern auch noch einige spezifische Strukturinformationen von dplyr enthält. In unserem Beispiel sind dies Indizes von Zeilen, die zum gleichen Hersteller gehören. Das ursprüngliche Data Frame wird hierbei nicht kopiert, sondern nur eingebettet.

Nach Anwenden einer group_by()-Operation ist das Data Frame optimal vorbereitet für die eigentliche Aggregation mit summarise():

Das Resultat von summarise() ist wieder ein Data Frame, das neben den ursprünglichen Gruppierungskriterien nur noch die Aggregate enthält.

Daten in Reih’ und Glied

Zwischen Relationalen Datenbanken und R-Data Frames besteht ein wesentlicher konzeptioneller Unterschied: Die Ergebnisse eines SELECT-Befehls haben keine definierte Reihenfolge, so lange die Zeilen nicht mit der Klausel ORDER BY festgelegt wird. Im Gegensatz dazu haben die Zeilen von Data Frames eine konstante Reihenfolge, die sich aus der Anordnung derWerte in den Spaltenvektoren ergibt.

Dennoch ist es manchmal wünschenswert, Data Frames umzusortieren, um eine fachliche Reihenfolge abzubilden. Hierzu dient in dplyr das Verb arrange(), das im Standard-R weitgehend der Indizierung eines Data Frames mit Ergebnissen der order()-Funktion entspricht, aber syntaktisch eleganter ist:

Dieses Beispiel hat zum Ziel, die fünf PS-stärksten Autos zu selektieren. Die arrange()-Funktion sortiert hier zunächst absteigend nach der PS-Stärke, dann aufsteigend nach Herstellername. Die Selektion der 5 ersten Zeilen erfolgt mit der hilfreichen Funktion slice(), die aus einem Data Frame Zeilen anhand ihrer Reihenfolge selektiert.

Fazit und Ausblick

Mit dplyr wird die Arbeit mit Data Frames stark verbessert: Im Vergleich zu “nacktem” R bringt das Paket eine klarere Syntax, abgerundete Funktionalität und bessere Performance. In der Kürze dieses Artikels konnte ich dies nur oberflächlich anreissen. Daher verweise ich auf die vielen Hilfe-Seiten, Vignetten und Internet-Videos zum Paket. Im zweiten Teil dieses Artikels werde ich auf einige fortgeschrittene Features von dplyr eingehen, z.B. die Verknüpfung von Data Frames mit Joins, die Window-Funktionen und die Verwendung von Datenbanken als Backend.

Weiter zu R Data Frames meistern mit dplyr – Teil 2.