00-Introduction.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Machine Learning Background\n",
    "\n",
    "## Einleitung \n",
    "In diesem Dokument bereiten wir unsere beim Münster Hack 2017 entwickelte Lösung zur Vorhersage von Busverspätungen auf. Im ersten Teil des Dokuments erläutern wir die theoretischen Grundlagen von Machine Learning allgemein sowie den von uns verwendeten Ansätzen im Speziellen. Im zweiten Teil des Dokuments findet sich der kommentierte und ausführbare Code unserer beim Hackathon entwickelten Lösung. \n",
    "\n",
    "## Was ist Machine Learning?\n",
    "Der Begriff Machine Learning fasst eine breite Klasse von Algorithmen zusammen die mit zunehmender Erfahrung ihre Leistungen hinsichtlich einer bestimmten Aufgabe verbessern. Die Grundidee ist dabei komplexe Zusammenhänge nicht explizit durch fehleranfällige Regeln zu modellieren, sondern sie automatisiert aus Daten zu lernen. Dieser Ansatz erfreut sich aufgrund gestiegener Rechenleistung und großen zur Verfügung stehenden Datenmengen wachsender Beliebtheit. \n",
    "\n",
    "## Wie finde ich das richtige Modell?\n",
    "Es gibt eine Vielzahl unterschiedlicher Machine Learning Modelle und wiederum unzählige Möglichkeiten diese zu optimieren. In diesem Abschnitt stellen wir etwas Terminologie vor, die es erlaubt über verschiedenste Modelle in einem gemeinsamen Rahmen nachzudenken und so den Überblick zu bewahren.\n",
    "\n",
    "### Modelle, Parameter und Hyperparameter\n",
    "Was ist überhaupt ein Machine Learning Modell? Ein Modell ist nichts weiter als eine mathematische Abbildung. Sie bildet in der Regel einen Feature Vektor $x$, auf das gewünschte Target $y$ ab. Ein Feature Vektor bezeichnet hierbei eine geordnete Liste von Merkmalen, in unserem Fall z.B. die ID der Haltestelle, die Uhrzeit, das Wetter, etc. Das Target wäre die erwartete Verspätung. Besagte Funktion ist dabei nicht allein durch den Feature Vektor $x$, sondern ebenfalls durch weitere Parameter $\\theta$ bestimmt. Die Abbildung lässt sich also als $f(x, \\theta) = y$ zusammenfassen. Diese Parameter werden jedoch nicht wie das Modell manuell spezifiziert, sondern durch einen Trainingsalgorithmus gelernt. Man wählt häufig Modelle, die relativ anpassungsfähig sind und lässt sich die Parameter auf sein spezielles Problem anpassen. Durch diese Grundidee bietet Machine Learning eine allgemeine Lösung für viele verschiedene Probleme. \n",
    "Zusätzlich zu der Menge der automatisch angepassten Parameter, gibt es die Menge der Hyperparameter, die manuell angepasst werden müssen. Sie betreffen in der Regel den Trainingsalgorithmus, z.B. wie stark werden die Parameter in jedem Schritt angepasst. Sie können jedoch ebenfalls die genaue Definition des Modells betreffen, z.B. wie viele Bäume hat ein Random Forest. Da der gemeinsame Suchraum der möglichen Hyperparameter sehr groß ist, empfiehlt es sich die Suche nach geeigneten Hyperparameter ebenfalls zu automatisieren z.B. durch eine Grid Search oder mithilfe von modellbasierten Ansätzen wie [Bayesian Optimization](https://automl.github.io/HpBandSter/build/html/index.html). \n",
    "\n",
    "### Evaluation\n",
    "Anders als in der klassischen Statistik wo die Güte geschätzter Parameter durch ihre Unsicherheit quantifiziert wird, werden im Machine Learning geschätzte Parameter durch ihre Performance auf ungesehenen Daten evaluiert. Diese Art der Evaluation ist für den Anwendungsbereich naheliegender, da sie direkte Rückschlüsse auf die Performance eines Modells in der Produktion zulässt. \n",
    "\n",
    "### Training-, Validation- und Testset\n",
    "Vor dem Training wird der Datensatz aus dem gelernt werden soll in ein sogenanntes Trainings- und ein Testset aufgespalten. Das Trainingsset wird dann zum Lernen der Parameter des Modells genutzt. Anschließend wird die Performance des Modells auf dem Testset evaluiert. Zusätzlich kann ein sogenanntes Validierungsset abgespalten werden, das zur Suche der Hyperparameter verwendet wird. Wichtig ist jedoch, dass das Testset welches zur finalen Evaluation des Modells genutzt wird zu keiner Zeit Einfluss auf das Training des Modells hat. In unserem Beispiel würden wir die Verspätungen einiger Zeiträume zurückhaltend und nach dem Training die absolute Differenz zwischen den geschätzten Verspätungen und den tatsächlich beobachteten Verspätungen im Testset zur Evaluation nutzen. \n",
    "\n",
    "### Bias-Variance Tradeoff\n",
    "Welches Modell ist das richtige für mein Problem? Diese Frage lässt sich abschließend nur durch Ausprobieren klären. Grundsätzlich gibt es zwei Gründe, die für die schlechte Performance eines Modells verantwortlich sein können. Zum einen kann die Klasse von Funktionen, die durch das Modell repräsentiert wird eine zu geringe Ausdrucksstärke bzw. Kapazität besitzen. Das bedeutet, dass die Funktion zu simpel ist um die Interaktionen und Zusammenhänge zwischen den Variablen zu modellieren. Dieses Phänomen wird als Underfitting bezeichnet. Zum anderen kann die repräsentierte Klasse von Funktionen jedoch auch zu ausdrucksstark sein, sodass sie sich an Besonderheiten des Trainingssets zu genau anpasst und auf ungesehenen Daten nicht ausreichend generalisiert. In diesem Fall ist die Performance auf dem Trainingsset besser als auf dem Testset und man spricht von Overfitting. Das Abwägen zwischen zu geringer Kapazität und zu hoher Flexibilität wird als Bias-Variance Tradeoff bezeichnet. Der Zusammenhang ist noch einmal in der folgenden Abbildung illustriert. Jedoch lassen sich weder die Komplexität des Datensatzes noch die Kapazität des Modells genau quantifizieren, sodass am Ende verschiedene Modelle ausprobiert werden müssen. Dabei geben beobachtetes Over- bzw. Underfitting Hinweise ob eher Modelle mit größerer oder kleinerer Kapazität verwendet werden müssen. \n",
    "\n",
    "![Bias Variance Tradeoff Illustration](figures/bias_variance_tradeoff.png)\n",
    "\n",
    "### Regression und Klassifikation\n",
    "Die beiden am häufigsten durch Machine Learning gelösten Problemstellungen sind Regression und Klassifikation. Bei einer Regression geht es darum aus einem gegebenen Feature Vektor eine reelle Zahl vorherzusagen. Das entspricht auch dem Ansatz unserer Busverspätungsvorhersage. Bei der Klassifikation geht es hingegen darum einen Feature Vektor einer Klasse aus einer vorher definierten Menge an Klassen zuzuordnen, also z.B. ob ein Bus verspätet, zu früh oder pünktlich sein wird.\n",
    "\n",
    "\n",
    "## Machine Learning Tools\n",
    "Mittlerweile gibt es zahlreiche Projekte, die die Anwendung von Machine Learning erleichtern. Wir konzentrieren uns hier hauptsächlich auf Tools aus dem Python Ökosystem. Dabei werden wir zuerst auf Tools eingehen die sich allgemein mit der Verarbeitung und Visualisierung von Daten beschäftigen und dann speziell auf Machine Learning Libraries. \n",
    "\n",
    "### NumPy\n",
    "NumPy (http://www.numpy.org/) stellt die Grundlage für die Verarbeitung größerer Datenmengen in Python dar. Es stellt getypte n-dimensionale Datenstrukturen, sowie effiziente mathematische Operationen auf diesen bereit. Durch eine intuitive Semantik vektorisierter Operationen erlaubt es auch komplexe Berechnung mit wenig Code auszudrücken. Des Weiteren sind die nativen Datentypen der dynamischen Programmiersprache Python schlichtweg zu ineffizient um größere Datenmengen zu verarbeiten. Alle weiteren genannten Libraries benutzen NumPy im Hintergrund auf die eine oder andere Weise.\n",
    "\n",
    "### matplotlib\n",
    "matplotlib (https://matplotlib.org/) ist die am weitesten verbreitete Plotting Library. Es erlaubt alle denkbaren Anpassung und kann Grafiken in vielen verschiedenen Formaten erzeugen. matplotlib eignet sich besonders um Plots den eigenen Wünschen anzupassen. Folgt man jedoch bereits der Tidy Data Semantik, können andere Libraries wie altair (https://altair-viz.github.io/), plotnine (https://plotnine.readthedocs.io/en/stable/), seaborn (https://seaborn.pydata.org/) oder plotly (https://plot.ly/python/) einfacher zu benutzen sein. Das gilt besonders für die Erstellung interaktiver Plots, die mit matplotlib eher schwierig umzusetzen sind.\n",
    "Allgemein sind Visualisierungen ein unerlässliches Werkzeug, um die eigenen Daten zu verstehen. Eine explorative Datenanalyse durch geeignete Visualisierungen sollte gründlich durchgeführt werden, **bevor** mit dem Trainieren von Modellen begonnen wird.\n",
    "\n",
    "### Pandas\n",
    "Die Pandas Library stellt den Dataframe Datentyp bereit. Dataframes kombinieren die Semantik von SQL Tabellen mit der mathematischen Flexibilität von NumPy Arrays. Im wesentlichen stellt ein Dataframe tabellarische Daten mit einem Zeilenindex und benannten Spalten dar. Auch aus SQL bekannte Operationen wie Indizierung, JOINs und GROUP BY werden unterstützt. Besonders für die Verarbeitung von Zeitreihen bietet Pandas eigene nützliche Operationen. \n",
    "Pandas hat sich als Tool für die Datenanalyse in Python fest etabliert.\n",
    "\n",
    "### Scikit Learn\n",
    "Eine der wohl umfangreichsten Machine Learning Libraries überhaupt ist scikit-learn. Neben einer Vielzahl von Machine Learning Modellen für supervised und unsupervised Learning, bietet es nützliche Funktionen für die Vorverarbeitung von Daten und die Evaluation von Modellen. Scikit-learn sollte vor allem dann verwendet werden, wenn es darum geht die Performance von Standard Machine Learning Modellen zu evaluieren. Für die Definition maßgeschneiderter Lösungen, speziell für Deep Learning, werden jedoch andere Libraries benötigt.\n",
    "\n",
    "#### Keras\n",
    "Die Keras Library, mittlerweile Teil von Googles TensorFlow (https://www.tensorflow.org/guide/keras), stellt ein high-level Interface für die Erstellung von Deep Learning Modellen bereit. Mithilfe von Keras lassen sich Deep Learning Modelle mit wenig Code erstellen, serialisieren und trainieren. Durch die Integration mit TensorFlow lassen sie bei Bedarf auch low-level Konstrukte (z.B. Matrixmultiplikation) zwischen die high-level Konstrukte (z.B. convolutional layer) einbauen.\n",
    "\n",
    "### H2O   \n",
    "\n",
    "H2O ist eine open source Machine Learning Plattform mit extensivem community support und ausführlicher Dokumentation (http://docs.h2o.ai/). Besonders für Machine Learning Einsteiger bietet die einfache Benutzeroberfläche Möglichkeiten ohne viel Vorwissen eigene Machine Learning Lösungen umzusetzen. Dafür kann H2O entweder graphisch im Webbrowser oder über die entsprechenden Schnittstellen mit R oder Python benutzt werden. Die innovativen features von H2O sind die AutoML Funktion und die Hyperparameter-Suchfunktion. Mit AutoML werden automatisch die wichtigsten Machine Learning Algorithmen für ein bestimmtes Datenset ausprobiert und der passendste Algorithmus gefunden werden. Für diesen Algorithmus können dann mit der Hyperparametersuche innerhalb eines gewissen Rahmens alle Hyperparameter Kombinationen ausprobiert werden um das beste Modell zu finden.\n",
    "Vorteilhaft ist auch das einfache Deployment der fertigen Modelle. Diese können als Java Objekte exportiert und direkt verwendet werden. \n",
    "\n",
    "\n",
    "## Tidy Data\n",
    "Ob nun im maschinellen Lernen oder in der Statistik, es gibt für beide Disziplinen Module, die die gängigsten Algorithmen bereits implementiert haben. Und obwohl Datensätze höchst unterschiedlich sein können, müssen diese Standardalgorithmen immer anwendbar sein. Um dies zu ermöglichen verlangen sie ein Standard-Datenformat. Dieses Format folgt dem *Tidy Data* Prinzip und macht Analysen auf den Daten besonders einfach. Daher ist es unser Ziel vorhandene Daten vor einer Analyse erstmal in das Tidy Data Format zu überführen. Im besten Fall können wir bereits bei der Erzeugung von den Daten festlegen, dass diese in dem gewünschten Format angelegt werden. \n",
    "\n",
    "Daten sind in einem Dataframe hinterlegt und haben immer Zeilen und Spalten. Dabei hat sich durchgesetzt für den Aufbau eines Dataframes zwischen Variablen und Beobachtungen zu unterscheiden. Eine Beobachtung enthält alle Variablen im System. In dem unteren Beispiel ist das Einfahren eines Busses in eine Station eine Beobachtung. Bei dieser Beobachtung hinterlegen wir die Variablen Datum, Soll-, Ist- Abfahrtszeit und weitere Variablen.\n",
    "\n",
    "![Dataframe Beispiel](figures/dataframe_example.png)\n",
    "\n",
    "Für den Dataframe und für Tidy Data ist es nicht so wichtig, ob wir nun mit Uhrzeiten (kontinuierlichen Daten), Haltestellen (diskrete Daten) oder Pünktlichkeiten (Bool´schen Daten) arbeiten. Selbst wenn Daten fehlen, sollte dies mit einem not-available-Objekt angegeben werden, da auch diese für verschiedene Analysen berücksichtigt werden. \n",
    "Diese Form der Anordnung erlaubt es verschiedene Beobachtungen/Zeilen intuitiv zu vergleichen. Wenn man einen Eintrag am Nachmittag mit dem am frühen Abend vergleichen möchte, vergleichen wir einfach die verschiedenen Zeilen. Wenn man die Differenz der Verspätung zweier Zeilen berechnet, kann man die Zuverlässigkeit der Touren vergleichen. “Zu welcher Uhrzeit kommt es besonders häufig zu Verspätungen?”. Entsprechend kann man festhalten, dass Beobachtungen immer in die Zeilen und Variablen in die Spalten eines Dataframes eingetragen werden sollten. \n",
    "\n",
    "Dabei sollte jeder Typ von Beobachtungen eine eigene Tabelle bekommen. Analysen werden unnötig kompliziert, wenn wir nun auch noch die Menge an Passagieren an den verschiedenen Haltestellen an diese Tabelle anhängen würden. Dies sollte als eine andere und eigenständige Analyse betrachtet werden. Jede Tabelle wird am besten in einer Form gespeichert, sodass diese einzeln abrufbar ist. Sehr unbeliebt und ineffizient sind Excel Tabellen in denen pro Sheet mehrere Tabellen mit Text und Beschreibung abgespeichert werden. Der Dataframe muss so gestaltet sein, dass zusätzliche Beschreibungen zum verstehen der Tabelle nicht notwendig sind. Am besten eignen sich relationale Datenbanken, die, wenn richtig konstruiert, bereits dem Tidy Data Prinzip folgen und hilfreiche Informationen über Datentypen liefern. Häufig werden auch CSVs verwendet, die einen einfachen Austausch von Daten ermöglichen und weniger Raum bieten Unordnung in die Daten zu bringen.\n",
    "\n",
    "Auch wenn hiermit das wichtigste aus Tidy Data erwähnt wurde, kann man je nach Fragestellungen die Lesbarkeit der Tabelle weiter erhöhen. Zum Beispiel könnte man eine bestimmte Reihenfolge für die Variablen/Spalten wählen. Hier ist eine intuitive Anordnung gewählt worden, bei der Datum und Wochentag beisammen stehen, sowieso alle Soll-, Ist-Zeiten. Es kann auch für die statistische Analyse interessant sein abhängige Variablen ganz nach links zu setzten und die unabhängigen Variablen daneben einzutragen, um Übersicht zu schaffen und das Ziel der Analyse immer im Augen zu behalten. Generell ist eine logische Anordnung der Spalten ein empfehlenswerter Schritt, da man auch manchmal manuell durch die Daten schauen muss. Je kohärenter der Aufbau der Tabelle zur Fragestellung ist, desto einfacher fällt es die Tabelle zu verstehen.\n",
    "\n",
    "Sollten wir Antworten zu all den Vorgaben für eine Tidy Data Tabelle beantwortet haben, können wir uns nun den eigentlichen Analysen zuwenden. Die wiederholten Operationen und Analysen nehmen sehr viel Zeit ein, wenn auf einem “Messy” Dataframe gearbeitet wird und nicht jedoch mit Tidy Data. Eine Ausnahme kann jedoch sein, wenn das Tidy Data schwer lesbar wird. Angenommen wir sollen an verschiedenen Straßen in der Innenstadt und im Randbezirk die Menge an Fahrradfahrer von 8:00 bis 9:00 Uhr zählen. Jeder Zählende bekommt eine Straße zugewiesen. Das ganze soll für einen Monat gehen. Die Zählerdaten werden dann in einer Tabelle eingetragen. Dafür sucht jeder Beteiligte dann in der Tabelle seine/ihre Straße und trägt unter dem aktuellen Tag die Menge an gezählten Fahrrädern ein. \n",
    "\n",
    "![Messy Data Beispiel](figures/messy_example.png)\n",
    "\n",
    "Dies wäre nicht Tidy Data konform, da das Konzept von Variable und Beobachtung verletzt wird. Eigentlich ist jeder Eintrag eines Zählenden an einem Tag eine Beobachtung des Straßennetzes einer Stadt. Da man aber schon weiß welches Datenformat uns erwartet und welches wir dann für die Analyse brauchen, können wir ein Skript vorbereiten, dass diese Tabelle dann in das Tidy Data Format überführt die wie folgt aussehen sollte:\n",
    "\n",
    "![Tidy Data Beispiel](figures/tidy_example.png)\n",
    "\n",
    "Jede Messung von einer Person an einem Tag ist eine Beobachtung. An welchem Tag und für welche Straße gemessen wurde, sind die Variablen. Das Transformieren der Daten ist leichter, und erlaubt den Zählern ein einfaches und weniger fehleranfälliges Befüllen der Tabelle. Messy-Daten zu erstellen kann manchmal strategisch klüger sein.\n",
    "Für mehr Informationen verweisen wir auf http://vita.had.co.nz/papers/tidy-data.html\n",
    "\n",
    "\n",
    "## Preprocessing\n",
    "Sind die erforderlichen Daten bereits im Tidy Data Format, fehlt noch mindestens ein Schritt, bevor man mit der Datenanalyse beginnen kann. Die Daten müssen bereinigt und maschinenlesbar gemacht werden, was man auch Preprocessing nennt. Dies beinhaltet verschiedene Schritte. Wir beschränken uns hier auf die zwei wichtigsten davon. \n",
    "Einmal müssen unsere Daten aus der für den menschlichen Nutzer verständlichen Darstellung in eine maschinen interpretierbare Form übersetzt werden. Geordnete Variablen wie das Verkehrsaufkommen (”kaum Verkehr”, ”normaler Verkehr”, “starker Verkehr”) könnte z.B. in Zahlen wie 1, 2, 3, übersetzt werden, wobei die Höhe der Zahl die Stärke des Verkehrsaufkommens beschreibt. Kategorische Daten, wie an die Haltestelle an der die Verspätung beobachtet wurde, müssen aber im sogenannten One-Hot-Encoding dargestellt werden. Jeder Datenpunkt wird mit einem Vektor dargestellt, dessen Länge der Menge an Kategorien entspricht. Die Kategorie ist dann ein Eintrag mit der Nummer 1 in einer bestimmten Reihe des Vektors und der Rest des Vektors bekommt den Eintrag 0. Eine Variable mit drei Kategorien würde man also als Vektor (1,0,0), (0,1,0) und (0,0,1) darstellen. Das ist nötig, da alle Kategorien als unabhängig anzusehen sind. Würde man sie stattdessen mit natürlichen Zahlen, also 1, 2, 3, kodieren, würde man eine Geordnetheit der Kategorien implizieren, die ein Algorithmus versuchen könnte auszunutzen.\n",
    "Zweitens müssen wir unsere Daten in eine Form überführen, die unsere Analyse verlangt. Das ist wichtig, denn die meisten Algorithmen und statistischen Methoden sind allgemein(gültig) formuliert und nicht fallspezifisch.\n",
    "\n",
    "Betrachten wir zum Beispiel Clustering, als einen Algorithmus der problemunabhängig auf einer abstrakten Darstellung von Daten arbeitet. Man kann eine Clusteranalyse durchführen, wenn man beispielsweise wissen möchte, ob es typische Altersgruppen für die verschiedenen Formen der öffentlichen Verkehrsmittel gibt. “Nutzen Schüler den Bus öfter, und sind Berufstätige eher auf die S-Bahn angewiesen?” Clustering kann man aber auch auf Bilddaten anwenden, um herauszufinden welche Farben die wichtigsten sind, um dann ein hochauflösendes Bild, nur noch mit einem Dutzend Farben darzustellen ohne das Bild zu stark zu verändern. Beide Clustering-Verfahren nutzen den selben Algorithmus, die Daten sind aber grundverschiedenen. In unserer Altersgruppen-Analyse haben wir kategorische Daten (z.B. 0-18 Jährige, 18-40 Jährige etc.). In der Bildanalyse haben wir Pixelwerte (z.B. 90 als Pixelwert für ein Schwarz-Weiß-Bild, oder (13,51,67) als Pixelwert für die drei Grundfarben im RGB-Farbraum). Um nun unsere Daten maschinenlesbar zu machen, müssen wir unserem Algorithmus explizit sagen, welche (modifizierten) Daten er nutzen soll, um dann zu clustern. Diese Modifikationen können daher rühren, dass der Algorithmus nur eine einzelne Zahl als Input haben möchte. In unserem Farbfoto-Beispiel müssten wir dann pro Farbe im dreidimensionalen RGB-Raum clustern.\n",
    "\n",
    "Es kann aber auch komplexer werden, wenn unsere Analysen auf Daten stattfinden sollen, die noch stärker vom Format unseres Algorithmus abweichen. Ein solches Problem taucht auf, wenn wir in einer Zeitreihe nach Stoßzeiten für Busnutzung clustern wollen. Angenommen wir hätten 20 Attribute, von denen wir glauben, dass sie die Busnutzung beeinflussen und die Busse einer Buslinien Strecke sind zwölf Stunden auf der Strecke, dann hätten wir eine Matrix mit über 800.000 Einträgen pro Busline, wenn wir sekündlich die Nutzung von Bussen messen würden. Wir sollten nicht jede Sekunde als Datenpunkt nehmen, da diese Datenmenge es aufwendig machen Cluster zu finden, wenn viele dieser Einträge auch noch sehr ähnlich sind. Es wäre besser die Zeitreihe zu analysieren und in größere, sinnvolle Zeiteinheiten zu reduzieren. Eventuell reicht es die Busnutzung auf 30 Minuten zu mitteln, bzw. verbessert sogar die Analyse.\n",
    "\n",
    "Manchmal ist es nicht die Datenmenge, die einem Schwierigkeiten bereitet, oder das finden von verlässlichen Attributen für die Vorhersage. Manchmal muss man Kreativität und Expertise bezüglich der Daten mitbringen, um eine erfolgreiche Analyse durchzuführen. Wir betrachten mal etwas außerhalb des Stadtwerke Universums. Wenn intelligente Assistenten wie Siri einen Sprachbefehl bekommen, haben wir auch eine Zeitreihe, die aus der Amplitude für tausende von Frequenzen pro Bruchteil einer Sekunde besteht. Das sind unvorstellbar viele Datenpunkte, und ein Großteil davon ist für die Analyse gar nicht wichtig. Man könnte aus dem Befehl an Siri, der wenige Sekunden dauert, naiverweise einfach exemplarisch 100 Datenpunkte (Amplitude) mit gleichmäßigem Abstand nehmen. Wenn man jedoch Pech hat, erwischt man Stellen, an denen die Stimme sehr unbrauchbare Informationen liefert. Das können bestimmte Phoneme (die kleinste bedeutungsunterscheidende Einheit der gesprochenen Sprache) sein, die statistisch betrachtet sehr häufig in der Sprache vorkommen und so kaum Information über das gesagt Wort übermitteln - oder einfach das kurze Ertönen einer Autohupe im Hintergrund. Man muss die Eigenschaft von Sprache gut kennen, um zu wissen, dass nur wenige Frequenzen wirklich relevant für die Kommunikation sind. Man kann mit diesem Wissen diese extrahieren und reduziert die Datenmenge drastisch auf den wirklich essentiellen Teil. Daher kann dieser Teil der Datenanalyse Kreativität und datenbezogenes Fachwissen erfordern.\n",
    "\n",
    "\n",
    "## Supervised vs. Unsupervised Learning\n",
    "Klassifikations- und Regressionsprobleme sind häufig Fälle für *Supervised Learning*, was bedeutet, dass zu jedem Datenpunkt im Datenset zusätzlich auch der Wert, den der Machine Learning Algorithmus herausfinden soll, schon bekannt ist. Es gibt also *Label* oder *Target*-Werte, die die zugehörige Klasse repräsentieren bzw. die Zielvariable bei Regression ausmachen. Der Algorithmus gibt zu jedem Datenpunkt seine Prognose ab, vergleicht seinen Wert mit der tatsächlichen Lösung, und lernt dann daraus, was beim nächsten Mal besser gemacht werden muss. Deswegen führen größere Datenmengen in der Regel zu einem besseren Endergebnis.\n",
    "Falls die Label bei einem Datenset nicht bereits vorhanden sind, können Supervised Learning Methoden nur mit signifikantem Aufwand verbunden sein, da diese sonst von Hand erstellt werden müssen.\n",
    "Das Ziel bei *Unsupervised Learning* ist oft auch Klassifikation, allerdings sind in diesem Fall die Klassen dem ML-Ingenieur selbst nicht bekannt. Aufgabe des Algorithmus ist es, diese zu finden. Eine klassische Methode dafür ist *k-Means Clustering*, bei dem das Datenset von dem Algorithmus anhand der inherenten Struktur der Daten in $k$ viele Gruppen eingeteilt wird. Problematisch ist dabei, dass es für den Menschen nicht nachvollziehbar ist, inwiefern die Einteilung zu relevanten Eigenschaften der Daten in der echten Welt korrespondieren. Auf die Methode des Clusterings wird im nächsten Abschnitt detaillierter eingegangen.\n",
    "Alternative Aufgabe von Unsupervised Learning Algorithmen ist die „Vereinfachung“ des Datensets. Es sollen also Information entnommen werden, ohne dass die grundlegende Struktur verändert wird. Ein Beispiel dafür ist die *Principal Component Analysis*, die eine Repräsentation der Daten findet, bei der die einzelnen Komponenten linear unabhängig voneinander sind. Dies kann auch ein wichtiger Preprocessing Schritt für viele andere Machine Learning Algorithmen sein.\n",
    "\n",
    "### Clustering\n",
    "Datensets können grundlegend auf zwei verschiedenen Arten in Gruppen eingeteilt werden: Beim *Partional Clustering* werden die einzelnen Datenpunkte nicht überlappenden Gruppen zugewiesen. Der k-Means Algorithmus ist ein Beispiel für diese Art des Clusterings. Möchte man hingegen Unsicherheit über die Zuordnung repräsentieren, oder explizit eine graduelle Zugehörigkeit ausdrücken, bietet probabilistisches Clustering die Möglichkeit, der Zuordnung eines Datenpunkts zu einer Gruppe ein Gewicht zu geben. Ein Beispiel hierfür sind die sogenannten *Gaussian Mixture Models*. In diesem Modell wird angenommen, dass die Datenpunkte von $n$ verschiedenen Gauss’schen Verteilungen erzeugt wurden, die jeweils ein Cluster repräsentieren. Ziel des Algorithmus ist es, die Parameter dieser Gauss-Verteilungen zu finden um für jeden Datenpunkt eine Aussage treffen zu können, wie hoch die Wahrscheinlichkeit ist, dass er zu Cluster 1, Cluster 2, …, Cluster n gehört.\n",
    "Wie weiter oben beschrieben, lässt sich die Qualität eines Clusterings nicht ohne weitere Informationen von einem Menschen bewerten. Eine quantitative Aussage darüber, wie gut ein Datenset eingeteilt wurde, lässt sich mit dem *Silhouette Coefficient* treffen. Diese Zahl ist ein Maß dafür, wie eng Datenpunkte innerhalb eine Clusters beieinander liegen (Kohäsion), im Verhältnis dazu, wie weit die Clusters voneinander entfernt sind (Separation). Ist dieser Koeffizient für alle Datenpunkte nah bei 1, sind die Cluster klar voneinander getrennt, was für eine gute Qualität spricht.\n",
    "\n",
    "## Explorative Datenanalyse\n",
    "Der erste Schritt eines Data Science Projekts ist immer die explorative Datenanalyse. Diese erste Untersuchung der Daten mit statistischen und graphischen Methoden, dient dazu, bestimmte Muster oder Anomalien zu entdecken, und eigene Hypothesen und Annahmen über die Daten zu prüfen. Erste Punkte, die überprüft werden sollte, ist offensichtlich die Größe des Datensets. Wie viele Beobachtungen und wie viele Variablen beinhaltet es? Sehr große Datensets oder hohe Dimensionalität, also eine hohe Anzahl von Variablen, kann schon bestimmte Methoden ausschließen, oder verlangt die Anwendung von diversen Preprocessing Techniken.\n",
    "Der nächste Schritt ist die Untersuchung der Datentypen und Datenqualität. Liegen alle Daten in einem verwertbaren Format vor oder müssen sie erst konvertiert werden? Ist das Datenset komplett oder gibt es viele fehlende Werte, mit denen irgendwie umgegangen werden muss. Eine wichtige Vorbereitung für das Preprocessing ist das Finden von Ausreißern in den Daten und eine statistische Analyse der einzelnen Variablen. Nützlich ist es herauszufinden, wie die Variablen verteilt sind und welche Variablen miteinander korrelieren. Aufgabe des Preprocessing wird es unter anderem sein, korrelierende Variablen herauszufiltern. Eine Möglichkeit dafür ist die oben erwähnte *Principal Component Analysis*.\n",
    "\n",
    "### Daten Visualisierung\n",
    "\n",
    "Ein wichtiger Teil der explorativen Datenanalyse ist es, die Daten mit eigenen Augen zu sehen. In diesem Abschnitt werden deshalb verschiedene Möglichkeiten für die Visualisierung einzelner Aspekte eines Datensatzes vorgestellt.\n",
    "\n",
    "![Boxplot: Eine einfache Methoden, um Ausreißer in Daten zu finden, sind Visualisierungen mit Boxplots.](figures/boxplot.png)\n",
    "\n",
    "![Histogramm: Histogramme visualisieren zusätzlich die Verteilung der Variable.](figures/histogram.png)\n",
    "\n",
    "![Korrelations-Matrix: Korrelationen zwischen Variablen können auf einen Blick mit einer Korrelations-Matrix dargestellt werden](figures/correlation_matrix.png)\n",
    "\n",
    "![Scatterplot: Um die Korrelation zwischen zwei bestimmten Variablen näher zu Untersuchen eignen sich besonders gut Scatterplots: ](figures/scatterplot.png)\n",
    "\n",
    "## Deep Learning\n",
    "Deep Learning ist eines der Wörter, die im Zusammenhang mit künstlicher Intelligenz am häufigsten fallen. Dabei handelt es sich um Neuronale Netze, die in den letzten Jahren eine bemerkenswerte Renaissance erleben. Die Idee ist es Neuronen miteinander zu verknüpfen, die ähnlich ihrer biologischen Vorlage ein Alles-oder-nichts-Prinzip umsetzen. Wann ein Neuron feuern sollte, um einen gewünschte Output zu erzeugen wird dann mit annotierten Daten (Supervised Learning) trainiert, so wie auch im lebenden Organismus. Lange konnten sich Neuronalen Netze nicht durchsetzen, bis ein originelles Modell mit Hilfe von Grafikkarten und einer Menge an Daten in Rekordzeit trainiert wurde und dann auch Spitzenleistung in der Klassifizierung von Bildern hinlegte. Inzwischen ist die Rechenleistung generell höher und verschiedenste Formen dieser Neuronalen Netze sind für verschiedene Aufgaben im Einsatz. Das “Deep” im Namen geht auf die Menge an Schichten von Neuronen zurück, die inzwischen sehr tief sein können.\n",
    "Aber was macht Deep Learning so interessant? Eine Schwierigkeit im maschinellem Lernen ist, dass wir unsere Daten stark bearbeiten müssen, um diese unseren Algorithmen zugänglich zu machen. Das kann aber schwer werden, wenn die Daten, die wir beschreiben müssen sich in einer Dimension befinden, die wir als Menschen nicht bewusst wahrnehmen. “Welche Kombination aus Frequenzen in welcher Reihenfolge bedeutet das Wort “Stadtwerke?” oder “Auf welche Pixel muss ich achten, um einen Hund von einer Katze unterscheiden zu können?”. \n",
    "\n",
    "Im Beispiel von Spracherkennung, das im Teil Preprocessing angesprochen wurde, müssen wir zum Verständnis von gesprochener Sprache nicht nur für Sprache wichtige Frequenzen ermitteln, um aus einer Audiodatei einen für Menschen lessbare Zeichenkette zu erstellen, sondern wir müssen herausfinden wie diese in Bezug zueinander stehen (Semantik). Da wir eine Zeitreihe haben bedeutet das, dass wir herausfinden müssen welche Signale in unsere Audiodatei ein ganzer Satz sind, was davon die einzelne Worte sind, und welche grammatikalische Funktion sie besitzen. Dafür müssen wir zum Teil Wissen aus vorherigen Sätzen mit einbeziehen. Was wir in unserer Muttersprache beinah mühelos meistern, bedeutet für den Computer einen sinnvollen Zusammenhang in einem beinah unendlich großem Feld von möglichen Zusammenhängen zu finden. Ein relativ einfach zu findender Zusammenhang kann sein, dass ein Satz eine Frage ist, wenn die Stimme am Ende eines Satzes hochgeht. Oder das der zeitliche Abstand zwischen zwei Wörtern, der zum Ende eines Satzes und den Anfang eines anderen Satze gehören größer ist, als Wörter die innerhalb eines Satzes gesprochen werden. Es gibt aber viel mehr Regeln, die Sprachverständnis ausmachen. Was früher tatsächlich mit einer Schar von Regeln, Ausnahmen und fundiertem linguistischen Wissen gelöst wurde, kann automatisch in den Daten gefunden werden. Es müssen nur genug davon zur Verfügung stehen, was das Problem von Deep Learning darstellt.\n",
    "\n",
    "Es gibt eine Handvoll von Modellen, die in verschiedensten Ausführungen immer wieder im Deep Learning Sektor gefunden werden können. Die wichtigsten drei für die Industrie im Stadtwerke Kosmos sind:\n",
    "\n",
    "***Convolutional Neural Networks***: Hierbei handelt es sich um Neuronen, die eine Faltung im mathematischen Sinn durchführen. Sie werden hauptsächlich für Bildanalysen verwendet. Im groben werden Funktionen gelernt, die Nachbarschaften von Pixel als Input nehmen und nach bestimmten Mustern suchen. Jedes Bild erzeugt ein ganz bestimmtes Muster von diesen Faltungen, mit dem dann ein Bild klassifiziert wird.\n",
    "***Recurrent Neural Networks/LSTMS***: Diese Netzwerke leiten Signale an tiefer liegende Neuronen weiter, schicken aber auch Signale zurück an Neuronen, von denen sie direkt oder indirekt bereits Signale bekommen haben. Es entstehen Feedback Schleifen, die wichtig für die Analyse von Zeitreihen sind. Das Feedback nimmt die Rolle eines Gedächtnisses des Netzwerkes ein. Eine besonders aufwendige Form dieser Netzwerke sind die Long Short Term Memory Netzwerke (LSTMs), die Feedbacks auf mehreren zeitlichen Ebenen aufrechterhalten. \n",
    "Ebenso interessant sind ***Generative Adversarial Networks*** in denen zwei Netzwerke miteinander konkurrieren. Eines kann z.B. Katzen erkennen, dass andere versucht Bilder zu erstellen, um das andere Netzwerk glauben zu lassen ein Bild von einer Katze zu sehen. Das Ergebnis sind synthetisch erzeugte Katzenbilder. Außerdem gibt es noch ***Deep Reinforcement Learning***. Hier begibt sich ein Agent auf die Suche nach der optimalen Strategie, um ein Problem zu lösen. Dies wird am häufigsten für KIs in Spielen genutzt, die zum Teil durch den Menschen nicht mehr besiegbar sind.\n",
    "\n",
    "Es ist zu beachten, dass die jeweiligen Modelle aber auch für ganz andere Aufgaben genutzt werden können und Deep Learning noch Teil intensiver Forschung ist. Python ist auch hier die Programmiersprache der Wahl, da es für sie Frameworks gibt, mit denen man bis auf das Neuron genau ein Netzwerk bauen kann und selber aussuchen kann, wie sie sich verhalten, wenn ein Signal bei ihnen eingeht (z.B. Tensorflow). Das Alles-oder-nichts-Prinzip ist längst nicht mehr die erste Wahl und auch sonst gibt es sehr viele Modifikationen, die man vornehmen kann. Wenn man aber nur bereits existierende Modelle nutzen möchte, gibt es Frameworks, die gängige Netzwerke bereits implementiert haben (z.B. Keras). \n",
    "\n",
    "## Random Forest Regression\n",
    "Für unser finales Modell auf dem MünsterHack 2017 haben wir eine sogenannte *Random Forest Regression* genutzt. Dieses Modell werden wir im folgenden kurz theoretisch erläutern. \n",
    "\n",
    "Eine Random Forest Regression ist ein sogenanntes *Ensemble* aus *Decision Tree Regressionen*. Das bedeutet, dass viele einzelne Decision Tree Regressionen separat trainiert und ihre Vorhersagen dann kombiniert werden. Da die einzelnen Bäume so trainiert werden, dass sie unterschiedliche und unkorrelierte Fehler machen, ist die kombinierte Vorhersage besser als die Vorhersage jeder einzelnen Regression. \n",
    "Wir gehen nun zuerst auf den Trainingsalgorithmus eines Decision Trees ein. Danach erläutern wir die Besonderheiten, die bei der Erweiterung auf Random Forests zu beachten sind.\n",
    "\n",
    "Ein Decision Tree ist im Prinzip ein Binärbaum. Das bedeutet jeder Knoten hat entweder zwei Kindknoten oder ist bereits ein Blatt. Jeder Knoten stellt einen Test auf einen Wert eines Features dar, jedes Blatt enthält einen Wert für die Vorhersage. Soll nun eine durch einen Feature Vektor repräsentierte Instanz einem Vorhersagewert zugeordnet werden geht man folgendermaßen vor. Beginnend beim obersten Knoten wird geprüft, ob der Feature Vektor den Wert des Tests für das entsprechende Feature erfüllt oder nicht. Dementsprechend wird die Instanz in den linken oder rechten Teil des Baumes sortiert, wo der nächste Test durchgeführt werden kann. Dies wird solange wiederholt, bis die Instanz in einem Blatt angekommen ist und so einem Vohersagewert zugeordnet ist. \n",
    "\n",
    "\n",
    "![Einfache Decision Tree Regression](figures/tree.png)\n",
    "\n",
    "Bei der Konstruktion eines Decision Trees geht man in ähnlicher Weise rekursiv vor. Für den ersten Knoten werden alle möglichen Features und Featurewerte daraufhin evaluiert wie stark die Reduktion der Varianz durch den erzeugten Split in den Trainingsdaten ist. Es wird also die Varianz aller Targets in den gesamten Trainingsdaten mit der gewichteten Summe der Varianzen der durch den Split erzeugten Gruppen verglichen. Der Featurewert mit der stärksten Reduktion wird dann gewählt. Mit den beiden erzeugten Gruppen wird nun genauso verfahren. Das geschieht solange bis eine minimale Gruppengröße oder Varianz in einem Knoten erreicht ist. Dann wird der Knoten zum Blatt erklärt und die Vorhersage als Mittelwert der im Knoten vorhandenen Trainingsbeispiele festgelegt.\n",
    "\n",
    "Decision Trees neigen häufig zu Overfitting, da sie Trainingsdaten zu stark zerteilen und zu tief werden. Um diesem Problem entgegenzutreten wurden Random Forests eingeführt. Wie bereits erwähnt ist ein Random Forest die gemittelte Vorhersage einzelner Decision Trees. Zusätzlich wird jedoch etwas Zufälligkeit in den Trainingsalgorithmus der Decision Trees eingebaut, die zur Unkorreliertheit der Fehler der einzelnen Trees führt. \n",
    "Jeder Decision Tree wird auf etwas anderen Beispielen und auf anderen Features trainiert. Das führt dazu, dass jeder Tree zwar auf ungefähr, aber nicht genau auf den gleichen Daten trainiert wird. Daraus folgt, dass jeder Tree am Ende etwas andere Fehler macht und die Kombination der Bäume deutlich besser wird als jeder alleine. Für die Daten wird sogenanntes *Bagging* angewandt. Das heißt aus dem ursprünglichen Satz Trainingsdaten wird für jeden Baum ein neuer künstlicher Datensatz erzeugt. Es wird aus dem Originaldatensatz mit zurücklegen gezogen, bis jeder neu erstellte Datensatz so groß ist wie der ursprüngliche Datensatz. Auf diesem künstlich erzeugten Datensatz wird dann der Decision Tree trainiert. Auch wenn es nun natürlich zu Doppelungen in jedem Datensatz kommt, sorgt dieses Vorgehen dafür, dass jeder Baum sich auf einen anderen Teil der Daten konzentriert. \n",
    "Zusätzlich wird der beste Featurewert zur Erzeugung eines Knotens nicht aus allen möglichen Features, sondern aus einer zufälligen Teilmenge von Features gewählt. \n",
    "Diese beiden Änderungen im Trainingsalgorithmus sind ausreichend, um Fehler der einzelnen Bäume weitgehend unkorreliert zu machen.\n",
    "\n",
    "Ein weiterer Vorteil von Random Forests ist, dass sich die Wichtigkeit einzelner Features berechnen lässt. Dies lässt sich aus der Fehlerreduktion eines Features über alle Bäume ermitteln und lässt Rückschlüsse darüber zu, ob ein Feature überhaupt zur Vorhersage verwendet werden sollte.\n",
    "\n",
    "Natürlich lässt sich argumentieren, dass ein Random Forest nicht zur Beschreibung von Zeitreihen, wie Busverspätungen, eignet. Zeitreihen sind durch Trend, Saisonalität und  Autoregressivität gekennzeichnet. Auch wenn Random Forests Trend und Saisonalität nicht explizit modellieren, sind sie doch flexibel genug sich diesen Phänomenen anzupassen. Autoregressivität, also die Abhängigkeit eines Werts von vorherigen Werten, wird in unserem Modell nicht berücksichtigt, da wir jedoch Verspätungen mehrere Stunden in der Zukunft vorhersagen wollen, spielt sie eine untergeordnete Rolle, da die Daten zum Zeitpunkt der Vorhersage noch gar nicht vorliegen. \n",
    "\n",
    "\n",
    "\n",
    "## Kurzfassung unseres Ansatzes\n",
    "Im zweiten Teil unseres Dokuments findet sich der kommentierte Code unserer Verspätungsvorhersage vom MünsterHack 2017. Auch wenn der Code weitgehend selbsterklärend sein sollte, führen wir hier einmal die allgemeinen Schritte auf:\n",
    "Die aufgezeichneten Busdaten werden geladen, bereinigt und Verspätungen extrahiert.\n",
    "Wetterdaten, die in den Daten der Fahrradzählstelle Münster enthalten sind werden geladen und mit den Verspätungsdaten kombiniert. Da die Wetterdaten ausschließlich für 2016 vorliegen, die Verspätungsdaten aber bis in das Jahr 2017 hineinreichen, werden die Wetterdaten in das nächste Jahr kopiert. Die Annahme, dass im Jahr 2017 das genau das gleiche Wetter herrschte wie 2016 ist natürlich gewagt, für den Demonstrationszweck aber ausreichend.\n",
    "Feriendaten werden aus dem Internet gescraped und mit den Verspätungsdaten kombiniert.\n",
    "Die Daten werden normalisiert und für die Nutzung durch Machine Learning Algorithmen vorbereitet.\n",
    "Verschiedene einfache Machine Learning Modelle werden getestet und evaluiert. Die Random Forest Regression hat hierbei den kleinsten Fehler. Haltestelle, Wetter und Wochentag haben dabei den größten Einfluss auf die Vorhersage.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}