Wieviele Trainungsbeispiele benötigen Lernverfahren? (1/2)

Kurz nach der Jahrtausendwende begann das Zeitalter der digitalen Daten. Seitdem übertrifft die Menge der digitalen Daten die der Analogen [HL11] und dem Maschinellen Lernen stehen enorme Datenmengen zur Verfügung. Unter dem Buzzword „big data“ wird dabei meist nur das reine Volumen gesehen, andere Faktoren, wie die Frequenz mit der die Daten zu verarbeiten sind und die Variabilität der Formate werden oft vernachlässigt, obwohl auch solche Daten unter „big data“ zusammengefasst werden. Betrachtet man das Volumen dann spielen zwei Faktoren eine zentrale Rolle, die das „big“ von „big data“ ausmachen: die Anzahl der Beispieldatensätze und – und dies wird häufig übersehen – die Anzahl der Eigenschaften mit denen die Beispieldaten beschrieben werden.
Wenn von „big data“ gesprochen wird, wird dabei oft angenommen, dass genügend Datensätze vorhanden sind. Für bestimmte Anwendungen jedoch, müssen die Daten in unterschiedliche Gruppen unterschieden werden, um beim Lernen nicht Äpfel und Birnen in einen Topf zu werfen. In solchen Fällen kann es leicht passieren, dass pro Gruppe zu wenig Beispieldaten vorhanden sind und die Frage an Bedeutung gewinnt: „Reichen die Datensätze eigentlich aus, um ein Vorhersagemodel mit einer gewissen Mindestgüte zu lernen?“.
Leider gibt es bisher keine einfache Antwort auf diese Frage, da diese neben der Anzahl der Eigenschaften – der Dimensionalität – der Daten, von der Struktur des Datenraums, der Verteilung der Daten in diesem Raum, dem verwendeten Lernverfahren, der Ausdrucksfähigkeit seiner Hypothesenrepräsentation und seiner endgültigen Parametrisierung abhängt. In der “Computational Learning Theory” wurden jedoch Ansätze zur Abschätzungen von Untergrenzen erarbeitet, die, unter der Annahme idealer Lernverfahren, zu mindestens eine Aussage über die benötigte Mindestmenge an Trainingsdaten gestatten.
Ziel dieses Beitrags ist es auf möglichst anschauliche Art und Weise anhand eines praktischen Beispiels zu zeigen, welchen Einfluss die Dimensionalität der Daten auf die Abschätzung der Anzahl der benötigten Beispiele für das Erlernen von Vorhersagemodellen – genauer einfachen Klassifikationsmodellen[1] – hat und welche Methoden hierfür existieren. In diesem ersten Teil liegt das Hauptaugenmerk auf endlichen Daten- und Hypothesenräumen und wir werden sehen, dass selbst für eine kleine Anzahl von Eigenschaften – sprich Dimensionen – nützliche Aussagen nur für sehr einfache Hypothesenrepräsentationen möglich sind. Im zweiten Teil werden wir einen Abschätzungsansatz betrachten, der die „Unterscheidungsstärke“ unterschiedlicher Lernverfahren berücksichtigt und mit dem auch Abschätzungen für unendliche Daten- und Hypothesenräume möglich werden.

Anwendungsbeispiel

Betrachten wir das Beispiel eines Online-Shops, der Produkte über das Internet verkauft und dessen Produkte klassifiziert werden sollen. Wie die Produkte klassifiziert werden sollen ist für unsere Betrachtungen unerheblich, was wir aber im Kopf haben sollten: der Absatz unterschiedlicher Produkte folgt einer Potenzverteilung. Eine kleine Zahl von Produkten wird sehr häufig verkauft, so dass für sie viele Datensätze existieren (solche Produkte werden gewöhnlicher Weise in konventionellen Geschäften vertrieben, die nur begrenzte Lagerkapazitäten haben). Der Großteil der Produkte wird jedoch eher seltener umgesetzt (auch als „long tail“ bezeichnet), so dass die Anzahl ihrer Datensätze gering ist; u.U. so gering, dass für sie keine verlässlichen Vorhersagemodelle erlernbar sind.

Zur Illustration gehen wir davon aus, dass in dem Online-Shop Produkte von 500 Marken verkauft werden und diese Produkte neben ihrer Marke durch ihre Größe (10 mögliche Werte), ihre Farbe (20 mögliche Werte), die ersten drei Ebenen der Google Produktkategorien (auf der dritten Ebene 500 mögliche Werte) und ihren Preis (im Bereich 0,49 – 100 €) beschrieben werden.

In diesem Kontext besitzt die Antwort auf die Frage: „Wie viele Daten werden überhaupt für ein Lernverfahren benötigt?“ offensichtlich konkreten Nutzen,

  • da wir abschätzen können, ob für ein konkretes Produkt überhaupt ein sinnvolles Vorhersagemodell erlernbar ist,
  • da wir aus der Abschätzung auf die Dauer der Datensammlung schließen können und
  • um ggf. die Daten von selten verkauften Produkten inhaltlich oder zeitlich zu aggregieren.

Was uns vorweg klar sein sollte

Die Daten, die wir zum Erlernen von Vorhersagemodellen verwenden, werden durch Eigenschaften (normalerweise als Feature, in der Statistik auch als Variablen bezeichnet) beschrieben. Die Eigenschaften werden in beobachtete und abhängige Eigenschaften (im Maschinellen Lernen auch als Label bezeichnet) unterschieden. Die Wertebereiche der Eigenschaften können in endliche und unendliche Wertebereich unterschieden werden.

Wir können nicht erwarten, dass ein Lernverfahren ein 100%ig korrektes Modell erlernt. Lernverfahren versuchen durch einen induktiven Schluss aus Daten ein Vorhersagemodell zu ermitteln. Da die zur Verfügung stehende Datenmenge immer begrenzt sein wird und die Daten damit realistischer Weise unvollständig sein werden, Messfehler und Inkonsistenzen enthalten können, kann auch ein erlerntes Modell niemals 100%ig korrekt sein.

Viele unterschiedliche Modelle können konsistent mit den verfügbaren Daten sein. Ziel des Lernverfahrens ist es daher mit den verfügbaren Daten das bestmögliche Vorhersagemodell zu ermitteln.

Wir müssen in Kauf nehmen, dass unbekannte, zukünftige oder ungewöhnliche Daten zu fehlerhaften Vorhersagen führen. Zum Lernzeitpunkt ist nur ein Ausschnitt aller Daten verfügbar. Zukünftig erhobene Daten können Veränderungen unterliegen oder es können bisher noch nicht gesehene Fälle auftreten, auf die das erlernte Modell nicht mehr richtig passt.

Aus diesen Fakten ergibt sich die einzig realistische Annahme: ein gutes Lernverfahren soll mit großer Wahrscheinlichkeit eine gute Näherung des richtigen Vorhersagemodells erlernen.

Anzahl benötigter Trainingsfälle

Zur Abschätzung der Anzahl benötigter Trainingsfälle – als Beispielkomplexität (sample complexity) bezeichnet – wurden in der Computational Learning Theory unterschiedliche Ansätze entwickelt. Diese Ansätze beschreiben für idealisierte Lernverfahren unter welchen Bedingungen probabilistisch, approximativ, korrektes Lernen (PAC learning) effizient möglich ist. Grundlegend für die Einsetzbarkeit dieser Ansätze ist die Unterscheidung, ob das Lernen in einem endlichen oder unendlichen Hypothesenraum erfolgt, und ob das Lernverfahren konsistente Hypothesen oder nur näherungsweise Hypothesen, z.B. beim Vorliegen von Messfehlern, zu den Daten erlernen kann.

Endliche Datenräume

Sofern die Daten nur durch nominelle Eigenschaften mit endlichen Wertebereichen beschrieben werden[2], lässt sich die Größe des Datenraums relativ einfach bestimmen. Die folgende Tabelle beschreibt für die wichtigsten nominellen Eigenschaftstypen Größenfaktoren, die im Folgenden zur vereinheitlichten Darstellung verwendet werden:

Type
t
Fehlende Werte (NA) ? Größe des Wertebereichs
n
Größenfaktor g(t)
Boolean Nein 2 2
Boolean Ja 2 3
Nominal (Menge) Nein n_t n_t
Nominal (Menge) Ja n_t n_t+1

Die Größe eines endlichen d-dimensionalen Datenraums D kann allgemein mit folgender Formel bestimmt werden |D| = \prod_{i=1}^d{g(t_i)}.

Das Lernproblem besteht darin: aus einer Teilmenge von Trainingsbeispielen S  aus dem Datenraum D, i.e. S \subset D, die ein Trainer dem Lernverfahren vorgibt, um Zielkonzept c zu erlernen, eine Hypothese aus dem Hypothesenraum h \in H des Lernverfahrens zu ermitteln, welche (möglichst) alle positiven Beispiel S_p  umfasst und (möglichst) alle negativen Beispiele S_n  ausschließt.

Einfache Hypothesenrepräsentation

Die einfachste Hypothesenrepräsentation, in der Lernen, welches über einfaches Erinnern hinausgeht, sinnvoll ist, sind Disjunktionen von Bool’schen Eigenschaften. Eine Beispielanwendung für die diese Repräsentation Sinn macht, ist das Erkennen von Spam-Emails anhand des Vorliegens unterschiedlicher alternativer Eigenschaften, die Spam-Emails charakterisieren. Der Hypothesenraum dieser Sprache besitzt eine Größe von |H| = 2^d [FoDS18]. Ein Beispiel für ein verbreitetes Lernverfahren, das eine Hypothesenrepräsentation dieses Typs nutzt, ist Naive Bayes.

Beliebige nominelle Eigenschaften können durch One-Hot- oder Dummy-Encoding als Bool’sche Variablen kodiert werden. Damit ergibt sich zum Erlernen von Disjunktionen kodierter, Bool’scher Eigenschaften die Größe des Hypothesenraums als |H| = 2^{\sum_{i=1}^d{g(t_i)}}.

Um unser Produktbeispiel in dieser Sprache zu repräsentieren, müssen die Eigenschaften geeignet kodiert werden, z.B. durch One-Hot- oder Dummy-Encoding, bei dem jeder Wert einer Eigenschaft durch eine neue bool’sche Variable kodiert wird. Hieraus ergeben sich im Fall von One-Hot-Encoding 500+10+20+500+9941=10.971 und im Fall von Dummy-Encoding 499+9+19+499+9940=10.966 neue Bool’sche Eigenschaften.

Eigenschaftsvektoren (Feature-Vektoren, bzw. Konjunktionen von Eigenschaften) stellen die nächstkomplexere Repräsentationssprache dar, die, solange sie nicht um ein Konstrukt zur Verallgemeinerung erweitert wird, sehr unspektakulär ist, da Beispiele mit ihr lediglich erinnert werden. Erst wenn ein „don’t care“-Symbol, wie z.B. „?“, für beliebige Eigenschaftswerte hinzugefügt wird, wird die extremste Form von Generalisierung möglich, die von einzelnen Werten gleich auf alle Werte generalisiert [ML97]. Durch das „don’t care“-Symbol wird der Größenfaktor g um einen weiteren Wert erhöht. Für diese Repräsentation beträgt die Größe des Hypothesenraums  über rein bool‘schen Eigenschaften (inkl. „don’t care“)  |H| = 3^d und für allgemeine endliche Eigenschaften|H| = \prod_{i=1}^d{(g(t_i)+1)}. Diese Repräsentation ist sehr eingeschränkt und erlaubt es nur einzelne und keine kombinierten Konzepte zu erlernen. Sie ist daher eigentlich nur von theoretischem Interesse und wird – soweit bekannt – in keinem praktisch eingesetzten Lernverfahren genutzt.

Interessanter ist eine Verallgemeinerung dieser Repräsentationssprache, die k-CNF (konjunktive Normalform), die aus einer Konjunktion von Disjunktionen der Länge k besteht, die sowohl polynomielle Beispiel- als auch Zeitkomplexität besitzt [ML97] und für die ein effizienter Algorithmus existiert. Diese Repräsentation lässt sich auch auf einen d-dimensionalen Eigenschaftsvektor übertragen, in dem für jede Eigenschaft Generalisierungen über beliebige Teilmengen erlaubt werden. Die Größe des Hypothesenraums dieser Sprache beträgt |H| = \prod_{i=1}^d{2^{g(t_i)}} = 2^{\sum_{i=1}^d{g(t_i)}}. Mit dieser Sprache können alle Eigenschaften zwar separat auf beliebige Teilmengen generalisiert werden, Korrelationen zwischen Eigenschaften werden jedoch nicht berücksichtigt.

Für Repräsentationssprachen, die keinerlei Einschränkungen machen, besitzt der Hypothesenraum für Daten mit d bool‘schen Eigenschaften eine Größe von |H| = 2^{2^d}. Auf beliebige endliche Eigenschaften übertragen, kann diese Aussage zu |H| = 2^{|D|} = 2^{\prod_{i=1}^d{g(t_i)}} verallgemeinert werden.

Wie aus diesen Abschätzungen ersichtlich wird, hat die Dimensionalität d der Daten einen direkten Einfluss auf die Größe des Hypothesenraums und damit auf die Anzahl der von einem Lernverfahren zu berücksichtigenden Konzepte.

Realistische Hypothesenrepräsentation

Bis auf einfache Disjunktionen bool’scher Eigenschaften, sind einfache Hypothesenrepräsentationen entweder zu ausdrucksschwach, so dass nützliche Konzepte kaum ausdrückbar sind, oder zu ausdrucksstark, so dass Lernen in vertretbarer nicht-exponentieller Zeit nicht möglich ist. Die gängigen Lernverfahren, wie k-Nearest Neighbors, Naive Bayes, Decision Trees, Random Forrests, AdaBoost, XGBoost, Logistic Regression, Support Vector Machines und Neuronale Netze, etc. beschränken durch spezifische Annahmen (inductive bias) den Hypothesenraum, um so nützliche Konzepte in vernünftiger Zeit zu erlernen.

Leider lassen sich nur für wenige der real eingesetzten Verfahren Abschätzungen für die Größe des Hypothesenraums finden.

Verfahren |H| Parameter
Boolean-coded Naive Bayes 2^{\sum_{i=1}^d{g(t_i)}}
Boolean-coded Decision Trees[3] 2^{\sum_{i=1}^d{g(t_i)}}
Boolean-coded Decision Trees with limited depth [4] 2(2^k-1)(1+log_2{⁡\sum_{i=1}^d{g(t_i)}} ) +1 k = Tiefenbegrenzung

Lernen eines zu allen Trainingsdaten konsistenten Konzepts (aka Overfitting)

Unter der Annahme eines idealen Lernalgorithmus, kann die Größe des Hypothesenraums dazu verwendet werden die Anzahl der Trainingsdaten m die ein „konsistenter Lernalgorithmus“[5] benötigt, um ein beliebiges Konzept mit einem maximalen Fehler \epsilon und einer Unsicherheit \delta (bzw. einer Wahrscheinlichkeit von 1 - \delta ) zu erlernen, abgeschätzt werden mit[6]

    \[m \geq \frac{1}{\epsilon}(ln{(|H|)} + ln{(\frac{1}{\delta})})\]

Nehmen wir für unser Beispielszenario an Produkt A wird stündlich im Durchschnitt 100 mal verkauft und Produkt B wird jeden Tag im Schnitt nur 10 mal verkauft.  Zur Vereinfachung nehmen wir weiter an, die Produkte werden jeden Tag – egal ob Wochentag oder Wochenende – nur zwischen 6:00 und 20:00 Uhr verkauft. Pro Monat erhalten wir für Produkt A 42.000 Datensätze und für Produkt B 300 Datensätze.

Der Datenraum D hat eine Größe von |D| = 500*10*20*500*9941 \approx 497 Mrd. Punkten. Mit einer einfachen bool’schen Kodierung ergibt sich d = 500+10+20+500+9951 = 10.971 und |H| = 2^{10.961}.

Wollten wir Datensätze dieser Produkte mit einem Fehler \epsilon von maximal 10% und einer maximalen Unsicherheit \delta = 5% – wie auch immer – klassifizieren, so würden wir für den Einsatz von Naive Bayes oder unbegrenzten DecisionTrees mindestens 76.145 Datensätze benötigen. Weder die monatlichen Daten von Produkt A noch Produkt B würden ausreichen.

Mit einem tiefenbeschränkten Entscheidungsbaum-Verfahren mit 5 Stufen, sind, ungeachtet der Qualität des Lernergebnisses, die Daten von Produkt A und B ausreichend, um die Anforderungen an \epsilon und \delta einzuhalten, da nur mindestens 91 Datensätze benötigt werden.

Ein, dieser Abschätzung zugrundeliegender, idealer Lernalgorithmus, ist jedoch für praktische Anwendungen unrealistisch, da er zwar für die Trainingsdaten ein konsistentes Konzept ermitteln würde, welches aber bei unbekannten, neuen Daten versagen kann. Der angenommene Lernalgorithmus unterliegt der „Überanpassung“ (overfitting).

Nichts desto trotz ist diese Abschätzungsformel hilfreich, da sie eine Aussage erlaubt, wie viele Trainingsbeispiele im besten Fall ausreichen, um mit einem idealen Lernverfahren ein Konzept mit einem maximalen Fehler von \epsilon und einer Unsicherheit von höchstens \delta zu erlernen, das in der genutzten Hypothesenrepräsentation ausdrückbar ist.

Agnostisches Lernen eines Konzeptes, das möglichst gut zu den Trainingsdaten passt

Überanpassung wollen wir in der Regel vermeiden, damit die erlernten Vorhersagemodelle auch auf unbekannte, fehlerbehaftete oder teilweise inkonsistente Daten anwendbar sind. Anders ausgedrückt: das zu erlernende Konzept c kann etwas außerhalb des Hypothesenraums liegen, der durch das eingesetzte Lernverfahren erfasst wird. Dies bedeutet, dass wir im Hypothesenraum des Lernverfahrens nur eine Näherung c' erlernen können, die möglichst gut sein sollte. Solch ein – als agnostisch bezeichnetes – Lernverfahren muss daher bestrebt sein den Fehler zwischen den Trainingsdaten und dem Fehler der sich durch das Erlernen der Näherung c' ergibt möglichst klein zu halten.

Auch hierfür kann, unter der Annahme eines idealen Lernalgorithmus, die Größe des Hypothesenraums dazu verwendet werden die Anzahl der Trainingsdaten m die ein „agnostisches Lernverfahren“ benötigt, um eine gute Näherung an das zu erlernende Konzept in einem endlichen Hypothesenraum mit einem maximalen Fehler \epsilon und einer Unsicherheit \delta (bzw. einer Wahrscheinlichkeit von 1 - \delta) zu erlernen, abgeschätzt werden mit[6]

    \[m \geq \frac{1}{2\epsilon^2}(ln{(|H|)} + ln{(\frac{2}{\delta})})\]

Auf das Beispiel angewendet müsste sich – unter der Annahme gleicher Rahmenbedingungen – die Mindestzahl von Trainingsbeispielen auf m = 490 belaufen. D.h. die Daten von Produkt A könnten zum Lernen der Klassifikation verwendet werden, die Datenmenge für Produkt B wäre jedoch nicht ausreichend.

Folgerung

Mit diesem ersten Beitrag haben wir anhand eines kleinen realen Beispiels gezeigt, wie sich für einen idealen Lernalgorithmus über die Betrachtung der Größe endlicher Hypothesenräume, die Mindestanzahl der benötigten Trainingsbeispiel abschätzen lässt.

Auch wenn es sich hierbei um eine idealisierte Betrachtung handelt, erlauben solche Abschätzungen Aussagen darüber, wann Lernverfahren nur mit einem größeren Fehler behaftet einsetzbar sind.

Diese Betrachtung erstreckte sich bisher nur über endliche Eigenschaften und berücksichtigt die Komplexität der Hypothesenrepräsentation – eine der wesentlichen Eigenschaften eines Lernverfahrens – noch nicht. Dies wird Thema des zweiten Teils sein, in dem wir sehen werden, wie sich Abschätzung auf der Basis der – sogenannten – Vapnik-Chervonenkis-Dimension (VC-Dimension) für viele gängige Klassen von Lernverfahren einsetzen lassen.

Fußnoten

[1] Wir betrachten hierbei nur rein binäre, binomiale resp. Bool’sche Klassifikationsprobleme, deren Aussagen sich jedoch auch auf multinomiale Klassifikation und reell-wertige Vorhersagemodelle übertragen lassen (siehe [ESL09], Seite 238).

[2] Unendlich, überabzählbare Eigenschaften lassen sich in Abhängigkeit vom Anwendungsproblem und der erforderlichen Genauigkeit oft diskretisieren und als ordinale Daten oder Intervalle ganzer Zahlen repräsentieren, wie z.B. Alter, Körpergröße, Längen, Temperatur, und Zeitintervalle usw., wenn es ausreichend ist diese mit einer Genauigkeit von Jahren, cm, mm, Zehntelgrad oder Sekunden zu erfassen.

[3] Vollausgebaute Decision Trees unterliegen der Gefahr der „Überanpassung“ (overfitting) und werden in der Regel gestutzt, um dies zu vermeiden. Die Abschätzung stellt daher die Obergrenze dar.

[4] http://www.cs.cmu.edu/~guestrin/Class/10701/slides/learningtheory-bigpicture.pdf  und https://www.autonlab.org/_media/tutorials/pac05.pdf (Letzter Zugriff: 10.3.2018)

[5] Ein „konsistenter Lernalgorithmus“ erlernt Hypothesen, die – wann immer möglich – perfekt zu den Trainingsdaten passen [ML97].

[6] Details zur Ableitung der beschriebenen Untergrenzen finden sich u.a. in [ML97], [FoML12] oder [FoDS18].

Referenzen

[HL11] „The World’s Technological Capacity to Store, Communicate, and Compute Information“, M. Hilbert, P. López, Science 332, 60, 2011, http://www.uvm.edu/pdodds/files/papers/others/2011/hilbert2011a.pdf (letzter Zugriff: 14. März 2018)

[ESL09] “The Elements of Statistical Learning”, T. Hastie, R. Tibshirani, J. Friedman, 2nd Edition, Springer, 2009.

[ML97] „Machine Learning“, T. Mitchell, McGraw-Hill, 1997.

[FoML12] „Foundations of Machine Learning“, M. Mohri, A. Rostamizadeh, A. Talwalkar, The MIT Press, 2012.

[FoDS18] „Foundations of Data Science“, A. Blum, J. Hopcroft, R. Kannan, Cornell University, https://www.cs.cornell.edu/jeh/book.pdf, Jan. 4th, 2018 (letzter Zugriff: 14. März 2018)

Distributed Computing – MapReduce Algorithmus

Sollen große Datenmengen analysiert werden, ist die Hardware eines leistungsfähigen Computers schnell überfordert und die Analysezeiten werden zu lang. Die Lösung zur Bewältigung von Big Data Analytics sind Konzepte des verteilten Rechnens (Distributed Computing).

Vertikale Skalierung – Der Klassiker der leistungsstarken Datenverarbeitung

Die meisten Unternehmen setzen heute noch auf leistungsstarke und aufrüstbare Einzelserver. Sollten Datenmengen größer und Analysen rechenaufwändiger werden, werden Festplatten (Storage), Arbeitsspeicher (RAM) und Prozessoren (CPU) aufgerüstet oder der Server direkt durch einen leistungsstärkeren ersetzt.

Diese Form der sogenannten vertikalen Skalierung (Vergrößerung der Server-Komponenten) ist für viele Unternehmen heute noch gängige Praxis, auch weil sie leicht zu administrieren ist und sie mit nahezu jeder Software funktioniert. Jedoch sind der Erweiterbarkeit gewisse Grenzen gesetzt und auch der Wechsel zu noch leistungsfähigerer Hardware würde den Einsatz von neuester High-End-Hardware bedeuten, der Kostenanstieg wäre exponentiell. Ferner bedarf es einer durchdachten Backup-Strategie mit gespiegelten Festplatten oder einem ganzen Backup-Server.

Leistungsstarke Server sind teuer und können zwar große Datenmengen weitaus schneller auswerten als Consumer-Computer, jedoch sind auch sie eher nicht dazu in der Lage, Big Data zu verarbeiten, also beispielsweise 100 Terabyte Daten binnen Sekunden statistisch auszuwerten.

Horizontale Skalierung – Skalierbare Speicher-/Rechenleistung

Ein alternatives Konzept zur vertikalen Skalierung ist die horizontale Skalierung. Dabei werden mehrere Computer, die im Vergleich oftmals über nur mittelmäßige Leistungsmerkmale verfügen, über ein Computer-Netzwerk verbunden und parallel angesteuert.

Der große Vorteil der horizontalen Skalierung ist der kostengünstige Einstieg, denn praktisch könnte bereits mit einem einzelnen Computer (Node) begonnen werden und dann nach und nach mit weiteren Nodes die Leistungsfähigkeit des Clusters (Verbund von Nodes) linear gesteigert werden. Ungefähr linear wachsen auch die Kosten an, so dass diese weitaus besser planbar sind. Cluster können weitaus höhere Leistungen erreichen als es einzelne Server könnten, daher gibt die horizontale Skalierung als diejenige, die sich für Big Data Analytics eignet, denn sie ermöglicht verteiltes Rechnen (Distributed Computing). Mit einem ausreichend großen Cluster lassen sich auch 100 Terabyte und mehr in wenigen Augenblicken statistisch auswerten.

Ferner ermöglichen horizontale Lösungen integrierte Backup-Strategien, indem jeder Node des Clusters über ein Backup der Daten eines anderen Nodes verfügt. Verfügt ein Node sogar über mehrere Backups, lässt sich eine sehr hohe Ausfallsicherheit – Datenverfügbarkeit im Cluster – erzielen.

Jedoch gibt es auch Nachteile der horizontalen Skalierung: Die Administration eines Clusters ist weitaus herausfordernder als ein einzelner Server, egal wie leistungsstark dieser sein mag. Auch Bedarf es viel räumlichen Platz für einen (oder gar mehrere) Cluster. Die Kompatibilität der Nodes sollte auch für die nächsten Jahr gesichert sein und nicht zuletzt ist es eine große Hürde, dass die einzusetzende Software (Datenbank- und Analyse-Software) für den Einsatz auf Clustern geeignet sein muss. Verbreite Software-Lösungen für verteiltes Speichern und Rechnen kommen beispielsweise von der Apache Foundation als Open Source Software: Hadoop, Spark und Flink.

Map Reduce Processing

Damit verteiltes Rechnung funktioniert, bedarf es der richtigen Software, die wiederum Algorithmen einsetzt, die sich dafür eignen. Der bekannteste und immer noch am weitesten verbreitete Algorithmus ist MapReduce. MapReduce ist ein sehr einfacher Algorithmus und dürfte von der grundsätzlichen Vorgehensweise jedem Software-Entwickler oder Analyst vertraut sein. Das Prinzip entspricht dem folgenden SQL-Statement, dass die am häufigsten vorkommende Sprache aus dem Datensatz (Tabelle Customers) abfragt:

Es gibt eine Tabelle (es könnte eine Tabelle in einer relationalen Datenbank sein oder eine CSV-Datei), die durch eine SELECT-Query abgefragt (map), groupiert (combine) und sortiert (sort). Dieser Schritt kann vereinfacht als Map-Funktion betrachtet werden, die in einer Liste Paaren aus Schlüssel (Keys) und Werten (Values) resultiert. Ist diese Liste vorhanden, kann diese auf die gewünschten Ergebnisse entspechend einer Logik (z. B. max(), min(), mean(), sum()) auf wenige oder nur einen einzigen Wert reduziert werden (Reduce-Funktion). Zu beachten ist dabei, dass der Map-Prozess sehr viel speicher- und rechen-aufwändiger als der Reduce-Prozess ist. Führen wir diese Abfrage auf einer Maschine aus, fassen wir die beiden Abfragen als ein Statement aus:

Betrachten wir jedoch die einzelnen Schritte, können wir sie wieder zumindest in einen Map- und einen Reduce-Schritt unterteilen. Diese Aufteilung machen wir uns für das verteilte Rechnen zunutze: Wenn jeder Computer (Node; oft auch Client Node oder Data Node) einen Teil der Daten besitzt, kann jeder Node für sich einen Map-Prozess durchführen, die Ergebnisse dann an einen Master-Node (oder in Hadoop-Sprache: Name Node) senden, der den Reduce-Prozess durchführt. Der Großteil der Aufgabe findet somit auf dem Cluster statt, nur der simple Reduce-Schritt auf einem einzelnen Computer.

Oftmals reicht ein parallel ablaufender Map-Prozess auf dem Cluster nicht aus, um Daten effizient auswerten zu können. Die Maßgabe sollte stets sein, den Reduce-Aufwand so gering wie möglich zu halten und soviel Arbeit wie möglich auf den Cluster zu verlagern. Daher sollte jeder Node im Cluster soweit aggregieren wie möglich: Dafür gibt es den Combine-Schritt.

Die zuvor erwähnte SQL-Abfrage als MapReduce würde bedeuten, dass ein Node über den Datensatz verfügt (und andere Nodes über weitere Datensätze) und jeder Node für sich seine Daten über einen Map-Prozess herausarbeitet, über einen Combine-Prozess aggregiert und die Aggregationsergebnisse an den Master-Node (Name Node) sendet. Hat der Master-Node alle Ergebnisse erhalten, berechnet dieser daraus das Endergebnis (Reduce).

Zusammenfassung: Map Reduce

MapReduce ist der bekannteste Algorithmus zur verteilten Verarbeitung von Daten und eignet sich für die Durchführung von komplexen Datenanalysen. Liegen Datensätze auf mehreren Computern (Client Nodes) vor, läuft der Algorithmus in der Regel in drei Schritten ab:

  1. Map – Selektierung der Datensätze auf den Computern im gewünschten Format und Durchführung einer Berechnung, beispielsweise der Bildung einer Summe. Dieser Schritt ist ermöglich das Prinzip Schema on Read, das aus Hadoop ein Tool zur Verarbeitung von unstrukturierten Daten macht.
  2. Combine – Durchführung einer Aggregation, die ebenfalls auf jeden Client Node durchgeführt wird, zur Zusammenfassung von Map-Ergebnissen.
  3. Reduce – Aggregation aller Ergebnisse auf dem zentralen Rechner (Name Node)

MapReduce ist dazu geeignet, unstrukturierte Daten zu verarbeiten, denn das Format der Daten wird über einen Map-Algorithmus bestimmt, der sehr flexibel programmiert werden kann. MapReduce ist kein eng definierter Algorithmus, sondern eine Hülle, die mit Inhalt befüllt werden muss. So müssen MapReduce-Algorithmen individuell über eine Programmiersprache wie Java, Scala oder Python programmiert werden.

Ein Beispiel eines in Java programmierten Word-Count-Algorithmus nach der MapReduce-Logik in Hadoop findet sich hier:

MapReduce und Advanced Analytics

MapReduce spielt seine Vorteile auf Computer-Clustern aus und eignet sich sehr zur Analyse von Daten nach dem Schema on Read. Für kompliziertere Analysealgorithmen ist MapReduce jedoch nur bedingt geeignet, denn bereits einfache Join-Anweisungen benötigen mehrere MapReduce-Ketten.

Während statistische Auswertungen und Join-Anweisungen mit MapReduce noch gut möglich sind, werden Algorithmen des maschinellen Lernens schwierig bis kaum möglich, da diese viele Iterationen, z. B. zur Anpassung von Gewichten, benötigen.

Applying Data Science Techniques in Python to Evaluate Ionospheric Perturbations from Earthquakes

Multi-GNSS (Galileo, GPS, and GLONASS) Vertical Total Electron Content Estimates: Applying Data Science techniques in Python to Evaluate Ionospheric Perturbations from Earthquakes

1 Introduction

Today, Global Navigation Satellite System (GNSS) observations are routinely used to study the physical processes that occur within the Earth’s upper atmosphere. Due to the experienced satellite signal propagation effects the total electron content (TEC) in the ionosphere can be estimated and the derived Global Ionosphere Maps (GIMs) provide an important contribution to monitoring space weather. While large TEC variations are mainly associated with solar activity, small ionospheric perturbations can also be induced by physical processes such as acoustic, gravity and Rayleigh waves, often generated by large earthquakes.

In this study Ionospheric perturbations caused by four earthquake events have been observed and are subsequently used as case studies in order to validate an in-house software developed using the Python programming language. The Python libraries primarily utlised are Pandas, Scikit-Learn, Matplotlib, SciPy, NumPy, Basemap, and ObsPy. A combination of Machine Learning and Data Analysis techniques have been applied. This in-house software can parse both receiver independent exchange format (RINEX) versions 2 and 3 raw data, with particular emphasis on multi-GNSS observables from GPS, GLONASS and Galileo. BDS (BeiDou) compatibility is to be added in the near future.

Several case studies focus on four recent earthquakes measuring above a moment magnitude (MW) of 7.0 and include: the 11 March 2011 MW 9.1 Tohoku, Japan, earthquake that also generated a tsunami; the 17 November 2013 MW 7.8 South Scotia Ridge Transform (SSRT), Scotia Sea earthquake; the 19 August 2016 MW 7.4 North Scotia Ridge Transform (NSRT) earthquake; and the 13 November 2016 MW 7.8 Kaikoura, New Zealand, earthquake.

Ionospheric disturbances generated by all four earthquakes have been observed by looking at the estimated vertical TEC (VTEC) and residual VTEC values. The results generated from these case studies are similar to those of published studies and validate the integrity of the in-house software.

2 Data Cleaning and Data Processing Methodology

Determining the absolute VTEC values are useful in order to understand the background ionospheric conditions when looking at the TEC perturbations, however small-scale variations in electron density are of primary interest. Quality checking processed GNSS data, applying carrier phase leveling to the measurements, and comparing the TEC perturbations with a polynomial fit creating residual plots are discussed in this section.

Time delay and phase advance observables can be measured from dual-frequency GNSS receivers to produce TEC data. Using data retrieved from the Center of Orbit Determination in Europe (CODE) site (ftp://ftp.unibe.ch/aiub/CODE), the differential code biases are subtracted from the ionospheric observables.

2.1 Determining VTEC: Thin Shell Mapping Function

The ionospheric shell height, H, used in ionosphere modeling has been open to debate for many years and typically ranges from 300 – 400 km, which corresponds to the maximum electron density within the ionosphere. The mapping function compensates for the increased path length traversed by the signal within the ionosphere. Figure 1 demonstrates the impact of varying the IPP height on the TEC values.

Figure 1 Impact on TEC values from varying IPP heights. The height of the thin shell, H, is increased in 50km increments from 300 to 500 km.

2.2 Phase Smoothing

For dual-frequency GNSS users TEC values can be retrieved with the use of dual-frequency measurements by applying calculations. Calculation of TEC for pseudorange measurements in practice produces a noisy outcome and so the relative phase delay between two carrier frequencies – which produces a more precise representation of TEC fluctuations – is preferred. To circumvent the effect of pseudorange noise on TEC data, GNSS pseudorange measurements can be smoothed by carrier phase measurements, with the use of the carrier phase smoothing technique, which is often referred to as carrier phase leveling.

Figure 2 Phase smoothed code differential delay

2.3 Residual Determination

For the purpose of this study the monitoring of small-scale variations in ionospheric electron density from the ionospheric observables are of particular interest. Longer period variations can be associated with diurnal alterations, and changes in the receiver- satellite elevation angles. In order to remove these longer period variations in the TEC time series as well as to monitor more closely the small-scale variations in ionospheric electron density, a higher-order polynomial is fitted to the TEC time series. This higher-order polynomial fit is then subtracted from the observed TEC values resulting in the residuals. The variation of TEC due to the TID perturbation are thus represented by the residuals. For this report the polynomial order applied was typically greater than 4, and was chosen to emulate the nature of the arc for that particular time series. The order number selected is dependent on the nature of arcs displayed upon calculating the VTEC values after an initial inspection of the VTEC plots.

3 Results

3.1 Tohoku Earthquake

For this particular report, the sampled data focused on what was retrieved from the IGS station, MIZU, located at Mizusawa, Japan. The MIZU site is 39N 08′ 06.61″ and 141E 07′ 58.18″. The location of the data collection site, MIZU, and the earthquake epicenter can be seen in Figure 3.

Figure 3 MIZU IGS station and Tohoku earthquake epicenter [generated using the Python library, Basemap]

Figure 4 displays the ionospheric delay in terms of vertical TEC (VTEC), in units of TECU (1 TECU = 1016 el m-2). The plot is split into two smaller subplots, the upper section displaying the ionospheric delay (VTEC) in units of TECU, the lower displaying the residuals. The vertical grey-dashed lined corresponds to the epoch of the earthquake at 05:46:23 UT (2:46:23 PM local time) on March 11 2011. In the upper section of the plot, the blue line corresponds to the absolute VTEC value calculated from the observations, in this case L1 and L2 on GPS, whereby the carrier phase leveling technique was applied to the data set. The VTEC values are mapped from the STEC values which are calculated from the LOS between MIZU and the GPS satellite PRN18 (on Figure 4 denoted G18). For this particular data set as seen in Figure 4, a polynomial fit of  five degrees was applied, which corresponds to the red-dashed line. As an alternative to polynomial fitting, band-pass filtering can be employed when TEC perturbations are desired. However for the scope of this report polynomial fitting to the time series of TEC data was the only method used. In the lower section of Figure 4 the residuals are plotted. The residuals are simply the phase smoothed delay values (the blue line) minus the polynomial fit line (the red-dashed line). All ionosphere delay plots follow the same layout pattern and all time data is represented in UT (UT = GPS – 15 leap seconds, whereby 15 leap seconds correspond to the amount of leap seconds at the time of the seismic event). The time series shown for the ionosphere delay plots are given in terms of decimal of the hour, so that the format follows hh.hh.

Figure 4 VTEC and residual plot for G18 at MIZU on March 11 2011

3.2 South Georgia Earthquake

In the South Georgia Island region located in the North Scotia Ridge Transform (NSRT) plate boundary between the South American and Scotia plates on 19 August 2016, a magnitude of 7.4 MW earthquake struck at 7:32:22 UT. This subsection analyses the data retrieved from KEPA and KRSA. As well as computing the GPS and GLONASS TEC values, four Galileo satellites (E08, E14, E26, E28) are also analysed. Figure 5 demonstrates the TEC perturbations as computed for the Galileo L1 and L5 carrier frequencies.

Figure 5 VTEC and residual plots at KRSA on 19 August 2016. The plots are from the perspective of the GNSS receiver at KRSA, for four Galileo satellites (a) E08; (b) E14; (c) E24; (d) E26. The y-axes and x-axes in all plots do not conform with one another but are adjusted to fit the data. The y-axes for the residual section of each plot is consistent with one another.

Figure 6 Geometry of the Galileo (E08, E14, E24 and E26) satellites’ projected ground track whereby the IPP is set to 300km altitude. The orange lines correspond to tectonic plate boundaries.

4 Conclusion

The proximity of the MIZU site and magnitude of the Tohoku event has provided a remarkable – albeit a poignant – opportunity to analyse the ocean-ionospheric coupling aftermath of a deep submarine seismic event. The Tohoku event has also enabled the observation of the origin and nature of the TIDs generated by both a major earthquake and tsunami in close proximity to the epicenter. Further, the Python software developed is more than capable of providing this functionality, by drawing on its mathematical packages, such as NumPy, Pandas, SciPy, and Matplotlib, as well as employing the cartographic toolkit provided from the Basemap package, and finally by utilizing the focal mechanism generation library, Obspy.

Pre-seismic cursors have been investigated in the past and strongly advocated in particular by Kosuke Heki. The topic of pre-seismic ionospheric disturbances remains somewhat controversial. A potential future study area could be the utilization of the Python program – along with algorithmic amendments – to verify the existence of this phenomenon. Such work would heavily involve the use of Scikit-Learn in order to ascertain the existence of any pre-cursors.

Finally, the code developed is still retained privately and as of yet not launched to any particular platform, such as GitHub. More detailed information on this report can be obtained here:

Download as PDF

Self Service Data Preparation mit Microsoft Excel

Get & Transform (vormals Power Query), eine kurze Einführung

 Unter Data Preparation versteht man sinngemäß einen Prozeß der Vorbereitung / Aufbereitung von Rohdaten aus meistens unterschiedlichen Datenquellen und -formaten, verbunden mit dem Ziel, diese effektiv für verschiedene Geschäftszwecke / Analysen (Business Fragen) weiterverwenden/bereitstellen zu können. Rohdaten müssen oft vor ihrem bestimmungsgemäßen Gebrauch transformiert (Datentypen), integriert (Datenkonsistenz, referentielle Integrität), sowie zugeordnet (mapping; Quell- zu Zieldaten) werden.
An diesem neuralgischen Punkt werden bereits die Weichen für Datenqualität gestellt.

Unter Datenqualität soll hier die Beschaffenheit / Geeignetheit von Daten verstanden werden, um konkrete Fragestestellungen beantworten zu können (fitness for use):

Kriterien Datenqualität

  • Eindeutigkeit
  • Vollständigkeit
  • Widerspruchsfreiheit / Konsistenz
  • Aktualität
  • Genauigkeit
  • Verfügbarkeit

Datenqualität bestimmt im Wesentlichen die weitere zielgerichtete Verwendung der Daten in Analysen (Modelle) und Berichten (Reporting). Daten werden in entscheidungsrelevante Kennzahlen (Informationen) überführt. Eine Kennzahl ist gegenüber der Datenqualität immer blind, ihre Aussagekraft (Validität) hängt -neben der Definition – in sehr starkem Maße davon ab:

Gütekriterien von Kennzahlen

  • Objektivität := ist die Interpretation unabhängig vom Beobachter / Verwender?
  • Reliabilität := kann das Ergebnis unter sonst gleichen Bedingungen reproduziert werden ?
  • Validität := sagt die Kennzahl das aus, was sie vorgibt, auszusagen ?

Business Fragen entstehen naturgemäß in den Fachbereichen.Daher ist es nur folgerichtig, Data Preparation als einen ersten Analyseschritt innerhalb des Fachbereichs anzusiedeln (Self Service Data Preparation). Dadurch erhält der Fachbereich einen Teil seiner Autonomie zurück. Welche Teilmenge der Daten relevant für Fragestellungen ist, kann nur der Fachbereich beurteilen; der Anforderer von entscheidungsrelevanten Informationen sollte idealerweiseTeil der Entstehung wertiger Daten sein, das fördert zum einen die Akzeptanz des Ergebnisses, zum anderen wirkt es einem „not-invented-here“ Syndrom frühzeitig entgegen.

Im Folgenden wird anhand 4 Schritten skizziert, wie Microsoft Excel bei dem Thema (Self Service) Data Preparation vor allem den Fachbereich unterstützen kann. Eine Beispieldatei können Sie hier (google drive) einsehen. Sie finden die hierfür verwendete Funktionalität (Get & Transform) in Excel 2016 unter:

Reiter Daten -> Abrufen und Transformieren.

Dem interessierten Leser werden im Text vertiefende Informationen über links zu einzelnen typischen Aufgabenstellungen und Lösungswegen angeboten. Eine kurze Einführung in das Thema finden Sie in diesem Blog Beitrag.

1 Einlesen

Datenquellen anbinden (externe, interne)

Dank der neuen Funktionsgruppe „Abrufen und Transformieren“ ist es in Microsoft Excel möglich, verschiedene externe Datenquellen /-formate anzubinden. Zusätzlich können natürlich auch Tabellen der aktiven / offenen Excel Arbeitsmappe als Datenquelle dienen (interne Datenquellen). Diese Datenquellen werden anschließend als sogenannte Arbeitsmappenabfragen abgebildet.

Praxisbeispiele:

Anbindung mehrerer Dateien, welche in einem Ordner bereitgestellt werden

Anbindung von Webinhalten

2 Transformieren

Daten transformieren (Datentypen, Struktur)

Datentypen (Text, Zahl) können anschließend je Arbeitsmappenabfrage und Spalte(n) geändert werden.
Dies ist zB immer dann notwendig, wenn Abfragen über Schlüsselspalten in Beziehung gesetzt werden sollen (siehe Punkt 3). Gleicher Datentyp (Primär- und Fremdschlüssel) in beiden Tabellen ist hier notwendige Voraussetzung.

Des Weiteren wird in dieser Phase typischerweise festgelegt, welche Zeile der Abfrage die Spaltenbeschriftungen enthält.

Praxisbeispiele:

Fehlerbehandlung

Leere Zellen auffüllen

Umgang mit wechselnden Spaltenbeschriftungen

3 Zusammenführen / Anreichern

Daten zusammenführen (SVERWEIS mal anders)

Um unterschiedliche Tabellen / Abfragen über gemeinsame Schlüsselspalten zusammenzuführen, stellt der Excel Abfrage Editor eine Reihe von JOIN-Operatoren zur Verfügung, welche ohne SQL-Kenntnisse nur durch Anklicken ausgewählt werden können.

Praxisbeispiele

JOIN als Alternative zu Excel Formel SVERWEIS()

Daten anreichern (benutzerdefinierte Spalte anfügen)

Bei Bedarf können weitere Daten, welche sich nicht in der originären Struktur der Datenquelle befinden, abgeleitet werden. Die Sprache Language M stellt einen umfangreichen Katalog an Funktionen zur Verfügung. Wie Sie eine Übersicht über die verfügbaren Funktionen erhalten können erfahren Sie hier.

Praxisbeispiele

Geschäftsjahr aus Datum ableiten

Extraktion Textteil aus Text (Trunkation)

Mehrfache Fallunterscheidung, Datenbereinigung /-harmonisierung

4 Laden

Daten laden

Die einzelnen Arbeitsmappenabfragen können abschließend in eine Exceltabelle, eine Verbindung und / oder in das Power Pivot Datemodell zur weiteren Bearbeitung (Modellierung, Kennzahlenbildung) geladen werden.

Praxisbeispiele

Datenverbindung erstellen

Big Data Essentials – Intro

1. Big Data Definition

Data umfasst Nummern, Text, Bilder, Audio, Video und jede Art von Informationen die in Ihrem Computer gespeichert werden können. Big Data umfasst Datenmengen, die eine oder mehrere der folgenden Eigenschaften aufweisen: Hohes Volumen (High Volume), hohe Vielfalt (High Variety) und / oder eine notwendige hohe Geschwindigkeit (High Velocity) zur Auswertung. Diese drei Eigenschaften werden oft auch als die 3V’s von Big Data bezeichnet.

1.1. Volumen: Menge der erzeugten Daten

Volumen bezieht sich auf die Menge der generierten Daten. Traditionelle Datenanalysemodelle erfordern typischerweise Server mit großen Speicherkapazitäten, bei massiver Rechenleistung sind diese Modelle nicht gut skalierbar. Um die Rechenleistung zu erhöhen, müssen Sie weiter investieren, möglicherweise auch in teurere proprietäre Hardware. Die NASA ist eines von vielen Unternehmen, die enorme Mengen an Daten sammeln. Ende 2014 sammelte die NASA alle paar Sekunden etwa 1,73 GB an Daten. Und auch dieser Betrag der Datenansammlung steigt an, so dass die Datenerfassung entsprechend exponentiell mitwachsen muss. Es resultieren sehr hohe Datenvolumen und es kann schwierig sein, diese zu speichern.

1.2. Vielfalt: Unterschiedliche Arten von Daten

Das  traditionelle  Datenmodell (ERM)  erfordert  die  Entwicklung  eines  Schemas,  das  die  Daten in ein Korsett zwingt. Um das Schema zu erstellen, muss man das Format der Daten kennen, die gesammelt werden. Daten  können  wie  XML-Dateien  strukturiert  sein,  halb  strukturiert  wie  E-Mails oder unstrukturiert wie Videodateien.

Wikipedia – als Beispiel – enthält mehr als nur Textdaten, es enthält Hyperlinks, Bilder, Sound-Dateien und viele andere Datentypen mit mehreren verschiedenen Arten von Daten. Insbesondere unstrukturierte   Daten haben   eine   große   Vielfalt.  Es   kann   sehr   schwierig   sein, diese Vielfalt in einem Datenmodell zu beschreiben.

1.3. Geschwindigkeit: Geschwindigkeit, mit der Daten genutzt werden

Traditionelle Datenanalysemodelle wurden für die Stapelverarbeitung (batch processing) entwickelt. Sie sammeln die gesamte Datenmenge und verarbeiten sie, um sie in die Datenbank zu speichern. Erst mit einer Echtzeitanalyse der Daten kann schnell auf Informationen reagiert werden. Beispielsweise können Netzwerksensoren, die mit dem Internet der Dinge (IoT) verbunden sind, tausende von Datenpunkten pro Sekunde erzeugen. Im Gegensatz zu Wikipedia, deren Daten später verarbeitet werden können, müssen Daten von Smartphones und anderen Netzwerkteilnehmern mit entsprechender Sensorik in  Echtzeit  verarbeitet  werden.

2. Geschichte von Big Data

2.1. Google Solution

  • Google File System speichert die Daten, Bigtable organisiert die Daten und MapReduce verarbeitet es.
  • Diese Komponenten arbeiten zusammen auf einer Sammlung von Computern, die als Cluster bezeichnet werden.
  • Jeder einzelne Computer in einem Cluster wird als Knoten bezeichnet.

2.2 Google File System

Das Google File System (GFS) teilt Daten in Stücke ‚Chunks’ auf. Diese ‚Chunks’ werden verteilt und auf verschiedene Knoten in einem Cluster nachgebildet. Der Vorteil ist nicht nur die mögliche parallele Verarbeitung bei der späteren Analysen, sondern auch die Datensicherheit. Denn die Verteilung und die Nachbildung schützen vor Datenverlust.

2.3. Bigtable

Bigtable ist ein Datenbanksystem, das GFS zum Speichern und Abrufen von Daten verwendet. Trotz seines Namens ist Bigtable nicht nur eine sehr große Tabelle. Bigtable ordnet die Datenspeicher mit einem Zeilenschlüssel, einem Spaltenschlüssel und einem Zeitstempel zu. Auf diese Weise können dieselben Informationen über einen längeren Zeitraum hinweg erfasst werden, ohne dass bereits vorhandene Einträge überschrieben werden. Die Zeilen sind dann in den Untertabellen partitioniert, die über einem Cluster verteilt sind. Bigtable wurde entwickelt, um riesige Datenmengen zu bewältigen, mit der Möglichkeit, neue Einträge zum Cluster hinzuzufügen, ohne dass eine der vorhandenen Dateien neu konfiguriert werden muss.

2.4. MapReduce

Als dritter Teil des Puzzles wurde ein Parallelverarbeitungsparadigma namens MapReduce genutzt, um die bei GFS gespeicherten Daten zu verarbeiten. Der Name MapReduce wird aus den Namen von zwei Schritten im Prozess übernommen. Obwohl der Mapreduce-Prozess durch Apache Hadoop berühmt geworden ist, ist das kaum eine neue Idee. In der Tat können viele gängige Aufgaben wie Sortieren und Falten von Wäsche als Beispiele für den MapReduce- Prozess betrachtet werden.

Quadratische Funktion:

  • wendet die gleiche Logik auf jeden Wert an, jeweils einen Wert
  • gibt das Ergebnis für jeden Wert aus
    (map square'(1 2 3 4)) = (1 4 9 16)

Additionsfunktion

  • wendet die gleiche Logik auf alle Werte an, die zusammen genommen werden.
    (reduce + ‘(1 4 9 16)) = 30

Die Namen Map und Reduce können bei der Programmierung mindestens bis in die 70er-Jahre zurückverfolgt werden. In diesem Beispiel sieht man, wie die Liste das MapReduce-Modell verwendet. Zuerst benutzt man Map der Quadratfunktion auf einer Eingangsliste für die Quadratfunktion, da sie abgebildet ist, alle angelegten Eingaben und erzeugt eine einzige Ausgabe pro Eingabe, in diesem Fall (1, 4, 9 und 16). Additionsfunktion reduziert die Liste und erzeugt eine einzelne Ausgabe von 30, der die Summe aller Eingänge ist.

Google nutzte die Leistung von MapReduce, um einen Suchmaschinen-Markt zu dominieren. Das Paradigma kam in der 19. Websearch-Engine zum Einsatz und etablierte sich innerhalb weniger Jahre und ist bis heute noch relevant. Google verwendete MapReduce auf verschiedene Weise, um die Websuche zu verbessern. Es wurde verwendet, um den Seiteninhalt zu indexieren und ein Ranking über die Relevant einer Webseite zu berechnen.

Dieses  Beispiel  zeigt  uns  den MapReduce-Algorithmus, mit dem Google Wordcount auf Webseiten ausführte. Die Map-Methode verwendet als Eingabe einen Schlüssel (key) und einen Wert, wobei der Schlüssel den Namen des Dokuments darstellt  und  der  Wert  der  Kontext  dieses Dokuments ist. Die Map-Methode durchläuft jedes Wort im Dokument und gibt es als Tuple zurück, die aus dem Wort und dem Zähler 1 besteht.

Die   Reduce-Methode   nimmt   als   Eingabe auch  einen  Schlüssel  und  eine  Liste  von  Werten an, in der der Schlüssel ein Wort darstellt. Die  Liste  von  Werten  ist  die  Liste  von  Zählungen dieses Worts. In diesem Beispiel ist der Wert 1. Die Methode “Reduce” durchläuft alle Zählungen. Wenn die Schleife beendet ist, um die Methode zu reduzieren, wird sie als Tuple zurückgegeben, die aus dem Wort und seiner Gesamtanzahl besteht.

 

Shiny Web Applikationen

Jede Person, die irgendwie mit Daten arbeitet, kommt nicht herum, aus Analysen oder Modellen gezogene Erkenntnisse mit anderen zu teilen. Meist haben diese Personen keinen statistischen oder mathematischen Hintergrund. Für diese sollten die Ergebnisse nicht nur verständlich, sondern im besten Fall auch visuell ansprechend aufbereitet sein. Neben recht teuren Softwarelösungen wie Tableau oder QlikView gibt es von R-Studio auch eine (zumindest im kleinen Rahmen) kostenfreie Lösung – R-Shiny.

Shiny ist ein R Paket, mit dessen Hilfe man interaktive Webapplikationen oder Dashboards erstellen kann, bei dem man auf den vollen Funktionsumfang aller R-Pakete zugreifen kann.

Bei der Erstellung für einfache Shiny-Apps sind keine HTML, CSS oder Javascript Kenntnisse nötig. Shiny teilt sich im Prinzip in zwei Programme: Das Front-End wird in der Datei ui.r festgelegt. Alles was im Back-End passiert, wird in der Datei server.r beschrieben. R-Studio übernimmt danach das Rendern des Front- Ends und man erhält eine übliche HTML-Datei, in dessen Backend R läuft.

Die Vorteile der Einfachheit, nur mit R eine funktionale Web-App erstellen können, hat natürlich auch seine Nachteile. Shiny ist, was das Design betrifft, eher limitiert und auch die Platzierung von Inputs wie Slidern, Drop-Downs oder auch Outputs wie Grafiken oder Tabellen ist stark beschränkt.

Eine kaum bekannte und dokumentierte Funktion von R-Shiny ist die Funktion „htmlTemplate“. Mit dieser lassen sich komplett in HTML, CSS und gegebenenfalls Javascript geschriebene Websites mit der vollen Funktionalität von R im Back-End integrieren – und sehen um Längen besser aus als rein in R geschriebene Web-Apps.

Wie man auf diese Art Shiny Apps programmiert zeige ich nun anhand des Folgenden Beispiels. Die folgenden Erklärungen sind mit Absicht kurz gehalten und stellen kein Tutorial dar, sondern sollen vielmehr die Möglichkeiten der Funktion „htmlTemplate“ zeigen.

Zunächst zur ui.R:

Der Code in der ui.R Datei ist recht einfach gehalten. Es werden nur die Bibliotheken geladen, auf die R zugreifen muss. Danach wird das html Template mit dem entsprechenden Namen geladen. Ansonsten werden in dieser Datei nur Input und Output als Variablen festgelegt.

 

In der Server.R Datei wird in diesem Beispiel der bekannte und oft verwendete Datensatz Mtcars verwendet. Zunächst wird mit dem Paket dplyr und der Funktion filter ein neuer Datensatz berechnet, der auf Nutzereingaben reagiert (sliderInput, siehe ui.R). Wenn in R-Shiny in DataFrames Berechnungen durchgeführt werden, müssen diese immer in einem sog. reactive Statement stehen. Danach werden mittels ggplot2 insgesamt drei Plots zu dem Datensatz erstellt.

Plot 1 stellt einen Zusammenhang zwischen Gewicht und Benzinverbrauch mittels linearer Regression dar. Plot 2 zeigt an, wie viele Zylinder die Fahrzeuge aus dem gefilterten Datensatz haben und Plot 3 zeigt die Korrelationen zwischen den Variablen an. Diese drei Plots sollen dem Endnutzer interaktiv zur Verfügung stehen.

 

In dieser HTML Datei wird die Struktur der Web App festgelegt. Diese enthält neben reichlich HTML auch ein paar Zeilen Internal Javascript, mit dem sich die die Diagramme ein- und ausblenden lassen. Das wichtigste in dieser Datei ist jedoch die Funktionsweise, mit der die in der ui.R Datei die Variablen an das Template übergeben werden. Jede template.html muss im Kopf (<head> … /<head>) die Funktion {{ headContent() }} enthalten. Damit werden die für Shiny benötigte Depedencies beim Rendern geladen. Diese übrigen, in der ui.R Datei deklarierten Variablen, werden ebenfalls mittels zwei geschweiften Klammern an das Template übergeben.

 

Nun muss für das Styling der App nur doch eine CSS-Datei geladen werden. Wichtig ist zu beachten, dass externe CSS Dateien bei Shiny immer in einem gesonderten Ordner mit dem Namen „www“ abgespeichert werden müssen. Auf diesen Ordner wird in der HTML Datei nicht gesondert verwiesen. Es reicht der Verweis <link rel=’stylesheet’ href=’style.css’/>.

Für den Upload der Datei müssen server.R, ui.R und template.html auf einer Ebene liegen, während wie bereits erwähnt die CSS Datei in einem gesonderten Ordner namens „www“ abliegen muss.

Die Web App liegt unter folgendem Link ab: https://markuslang1987.shinyapps.io/CustomShiny/

Einiges an der App ist sicherlich Spielerei, der Artikel soll in erster Linie aber die Möglichkeiten zeigen, die man mit einem selbst erstellten HTML Template im Gegensatz zu den recht eingeschränkten Möglichkeiten der normalen Shiny Programmierung zur Verfügung hat. Außerdem möchte ich mit diesem Artikel zeigen, dass Webentwicklung und Data Science/Analytics nicht zwangsläufig komplett voneinander unabhängige Welten sind.

Aika: Ein semantisches neuronales Netzwerk

Wenn es darum geht Informationen aus natürlichsprachigen Texten zu extrahieren, stehen einem verschiedene Möglichkeiten zur Verfügung. Eine der ältesten und wohl auch am häufigsten genutzten Möglichkeiten ist die der regulären Ausdrücke. Hier werden exakte Muster definiert und in einem Textstring gematcht. Probleme bereiten diese allerdings, wenn kompliziertere semantische Muster gefunden werden sollen oder wenn verschiedene Muster aufeinander aufbauen oder miteinander interagieren sollen. Gerade das ist aber der Normalfall bei der Verarbeitung von natürlichem Text. Muster hängen voneinander ab, verstärken oder unterdrücken sich gegenseitig.
Prädestiniert um solche Beziehungen abzubilden wären eigentlich künstliche neuronale Netze. Diese haben nur das große Manko, dass sie keine strukturierten Informationen verarbeiten können. Neuronale Netze bringen von sich aus keine Möglichkeit mit, die relationalen Beziehungen zwischen Worten oder Phrasen zu verarbeiten. Ein weiteres Problem neuronaler Netze ist die Verarbeitung von Feedback-Schleifen, bei denen einzelne Neuronen von sich selbst abhängig sind. Genau diese Probleme versucht der Aika Algorithmus (www.aika-software.org) zu lösen.

Der Aika Algorithmus ist als Open Source Java-Bibliothek implementiert und dient dazu semantische Informationen in Texten zu erkennen und zu verarbeiten. Da semantische Informationen sehr häufig mehrdeutig sind, erzeugt die Bibliothek für jede dieser Bedeutungen eine eigene Interpretation und wählt zum Schluss die am höchsten gewichtete aus. Aika kombiniert dazu aktuelle Ideen und Konzepte aus den Bereichen des maschinellen Lernens und der künstlichen Intelligenz, wie etwa künstliche neuronale Netze, Frequent Pattern Mining und die auf formaler Logik basierenden Expertensysteme. Aika basiert auf der heute gängigen Architektur eines künstlichen neuronalen Netzwerks (KNN) und nutzt diese, um sprachliche Regeln und semantische Beziehungen abzubilden.

Die Knackpunkte: relationale Struktur und zyklische Abhängigkeiten

Das erste Problem: Texte haben eine von Grund auf relationale Struktur. Die einzelnen Worte stehen über ihre Reihenfolge in einer ganz bestimmten Beziehung zueinander. Gängige Methoden, um Texte für die Eingabe in ein KNN auszuflachen, sind beispielsweise Bag-of-Words oder Sliding-Window. Mittlerweile haben sich auch rekurrente neuronale Netze etabliert, die das gesamte Netz in einer Schleife für jedes Wort des Textes mehrfach hintereinander schalten. Aika geht hier allerdings einen anderen Weg. Aika propagiert die relationalen Informationen, also den Textbereich und die Wortposition, gemeinsam mit den Aktivierungen durch das Netzwerk. Die gesamte relationale Struktur des Textes bleibt also erhalten und lässt sich jederzeit zur weiteren Verarbeitung nutzen.

Das zweite Problem ist, dass bei der Verarbeitung von Text häufig nicht klar ist, in welcher Reihenfolge einzelne Informationen verarbeitet werden müssen. Wenn wir beispielsweise den Namen „August Schneider“ betrachten, können sowohl der Vor- als auch der Nachname in einem anderen Zusammenhang eine völlig andere Bedeutung annehmen. August könnte sich auch auf den Monat beziehen. Und genauso könnte Schneider eben auch den Beruf des Schneiders meinen. Einfache Regeln, um hier dennoch den Vor- und den Nachnamen zu erkennen, wären: „Wenn das nachfolgende Wort ein Nachname ist, handelt es sich bei August um einen Vornamen“ und „Wenn das vorherige Wort ein Vorname ist, dann handelt es sich bei Schneider um einen Nachnamen“. Das Problem dabei ist nur, dass unsere Regeln nun eine zyklische Abhängigkeit beinhalten. Aber ist das wirklich so schlimm? Aika erlaubt es, genau solche Feedback-Schleifen abzubilden. Wobei die Schleifen sowohl positive, als auch negative Gewichte haben können. Negative rekurrente Synapsen führen dazu, dass zwei sich gegenseitig ausschließende Interpretationen entstehen. Der Trick ist nun zunächst nur Annahmen zu treffen, also etwa dass es sich bei dem Wort „Schneider“ um den Beruf handelt und zu schauen wie das Netzwerk auf diese Annahme reagiert. Es bedarf also einer Evaluationsfunktion und einer Suche, die die Annahmen immer weiter variiert, bis schließlich eine optimale Interpretation des Textes gefunden ist. Genau wie schon der Textbereich und die Wortposition werden nun auch die Annahmen gemeinsam mit den Aktivierungen durch das Netzwerk propagiert.

Die zwei Ebenen des Aika Algorithmus

Aber wie lassen sich diese Informationen mit den Aktivierungen durch das Netzwerk propagieren, wo doch der Aktivierungswert eines Neurons für gewöhnlich nur eine Fließkommazahl ist? Genau hier liegt der Grund, weshalb Aika unter der neuronalen Ebene mit ihren Neuronen und kontinuierlich gewichteten Synapsen noch eine diskrete Ebene besitzt, in der es eine Darstellung aller Neuronen in boolscher Logik gibt. Aika verwendet als Aktivierungsfunktion die obere Hälfte der Tanh-Funktion. Alle negativen Werte werden auf 0 gesetzt und führen zu keiner Aktivierung des Neurons. Es gibt also einen klaren Schwellenwert, der zwischen aktiven und inaktiven Neuronen unterscheidet. Anhand dieses Schwellenwertes lassen sich die Gewichte der einzelnen Synapsen in boolsche Logik übersetzen und entlang der Gatter dieser Logik kann nun ein Aktivierungsobjekt mit den Informationen durch das Netzwerk propagiert werden. So verbindet Aika seine diskrete bzw. symbolische Ebene mit seiner subsymbolischen Ebene aus kontinuierlichen Synapsen-Gewichten.

Die Logik Ebene in Aika erlaubt außerdem einen enormen Effizienzgewinn im Vergleich zu einem herkömmlichen KNN, da die gewichtete Summe von Neuronen nur noch für solche Neuronen berechnet werden muss, die vorher durch die Logikebene aktiviert wurden. Im Falle eines UND-verknüpfenden Neurons bedeutet das, dass das Aktivierungsobjekt zunächst mehrere Ebenen einer Lattice-Datenstruktur aus UND-Knoten durchlaufen muss, bevor das eigentliche Neuron berechnet und aktiviert werden kann. Diese Lattice-Datenstruktur stammt aus dem Bereich des Frequent Pattern Mining und enthält in einem gerichteten azyklischen Graphen alle Teilmuster eines beliebigen größeren Musters. Ein solches Frequent Pattern Lattice kann in zwei Richtungen betrieben werden. Zum Einen können damit bereits bekannte Muster gematcht werden, und zum Anderen können auch völlig neue Muster damit erzeugt werden.

Da es schwierig ist Netze mit Millionen von Neuronen im Speicher zu halten, nutzt Aika das Provider Architekturpattern um selten verwendete Neuronen oder Logikknoten in einen externen Datenspeicher (z.B. eine Mongo DB) auszulagern, und bei Bedarf nachzuladen.

Ein Beispielneuron

Hier soll nun noch beispielhaft gezeigt werden wie ein Neuron innerhalb des semantischen Netzes angelegt werden kann. Zu beachten ist, dass Neuronen sowohl UND- als auch ODER-Verknüpfungen abbilden können. Das Verhalten hängt dabei alleine vom gewählten Bias ab. Liegt der Bias bei 0.0 oder einem nur schwach negativen Wert reicht schon die Aktivierung eines positiven Inputs aus um auch das aktuelle Neuron zu aktivieren. Es handelt sich dann um eine ODER-Verknüpfung. Liegt der Bias hingegen tiefer im negativen Bereich dann müssen mitunter mehrere positive Inputs gleichzeitig aktiviert werden damit das aktuelle Neuron dann auch aktiv wird. Jetzt handelt es sich dann um eine UND-Verknüpfung. Der Bias Wert kann der initNeuron einfach als Parameter übergeben werden. Um jedoch die Berechnung des Bias zu erleichtern bietet Aika bei den Inputs noch den Parameter BiasDelta an. Der Parameter BiasDelta nimmt einen Wert zwischen 0.0 und 1.0 entgegen. Bei 0.0 wirkt sich der Parameter gar nicht aus. Bei einem höheren Wert hingegen wird er mit dem Betrag des Synapsengewichts multipliziert und von dem Bias abgezogen. Der Gesamtbias lautet in diesem Beispiel also -55.0. Die beiden positiven Eingabesynapsen müssen also aktiviert werden und die negative Eingabesynapse darf nicht aktiviert werden, damit dieses Neuron selber aktiv werden kann. Das Zusammenspiel von Bias und Synpasengewichten ist aber nicht nur für die Aktivierung eines Neurons wichtig, sondern auch für die spätere Auswahl der finalen Interpretation. Je stärker die Aktivierungen innerhalb einer Interpretation aktiv sind, desto höher wird diese Interpretation gewichtet.
Um eine beliebige Graphstruktur abbilden zu können, trennt Aika das Anlegen der Neuronen von der Verknüpfung mit anderen Neuronen. Mit createNeuron(“E-Schneider (Nachname)”) wird also zunächst einmal ein unverknüpftes Neuron erzeugt, das dann über die initNeuron Funktion mit den Eingabeneuronen wortSchneiderNeuron, kategorieVornameNeuron und unterdrueckendesNeuron verknüpft wird. Über den Parameter RelativeRid wird hier angegeben auf welche relative Wortposition sich die Eingabesynapse bezieht. Die Eingabesynpase zu der Kategorie Vorname bezieht sich also mit -1 auf die vorherige Wortposition. Der Parameter Recurrent gibt an ob es sich bei dieser Synpase um eine Feedback-Schleife handelt. Über den Parameter RangeMatch wird angegeben wie sich der Textbereich, also die Start- und die Endposition zwischen der Eingabe- und der Ausgabeaktivierung verhält. Bei EQUALS sollen die Bereiche also genau übereinstimmen, bei CONTAINED_IN reicht es hingegen wenn der Bereich der Eingabeaktivierung innerhalb des Bereichs der Ausgabeaktivierung liegt. Dann kann noch über den Parameter RangeOutput angegeben werden, dass der Bereich der Eingabeaktivierung an die Ausgabeaktivierung weiterpropagiert werden soll.

Fazit

Mit Aika können sehr flexibel umfangreiche semantische Modelle erzeugt und verarbeitet werden. Aus Begriffslisten verschiedener Kategorien, wie etwa: Vor- und Nachnamen, Orten, Berufen, Strassen, grammatikalischen Worttypen usw. können automatisch Neuronen generiert werden. Diese können dann dazu genutzt werden, Worte und Phrasen zu erkennen, einzelnen Begriffen eine Bedeutung zuzuordnen oder die Kategorie eines Begriffs zu bestimmen. Falls in dem zu verarbeitenden Text mehrdeutige Begriffe oder Phrasen auftauchen, kann Aika für diese jeweils eigene Interpretationen erzeugen und gewichten. Die sinnvollste Interpretation wird dann als Ergebnis zurück geliefert.

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.

Data Science Knowledge Stack – Was ein Data Scientist können muss

Was muss ein Data Scientist können? Diese Frage wurde bereits häufig gestellt und auch häufig beantwortet. In der Tat ist man sich mittlerweile recht einig darüber, welche Aufgaben ein Data Scientist für Aufgaben übernehmen kann und welche Fähigkeiten dafür notwendig sind. Ich möchte versuchen, diesen Konsens in eine Grafik zu bringen: Ein Schichten-Modell, ähnlich des OSI-Layer-Modells (welches übrigens auch jeder Data Scientist kennen sollte).
Ich gebe Einführungs-Seminare in Data Science für Kaufleute und Ingenieure und bei der Erläuterung, was wir in den Seminaren gemeinsam theoretisch und mit praxisnahen Übungen erarbeiten müssen, bin ich auf die Idee für dieses Schichten-Modell gekommen. Denn bei meinen Seminaren fängt es mit der Problemstellung bereits an, ich gebe nämlich Seminare für Data Science für Business Analytics mit Python. Also nicht beispielsweise für medizinische Analysen und auch nicht mit R oder Julia. Ich vermittle also nicht irgendein Data Science, sondern eine ganz bestimmte Richtung.

Ein Data Scientist muss bei jedem Data Science Vorhaben Probleme auf unterschiedlichsten Ebenen bewältigen, beispielsweise klappt der Datenzugriff nicht wie geplant oder die Daten haben eine andere Struktur als erwartet. Ein Data Scientist kann Stunden damit verbringen, seinen eigenen Quellcode zu debuggen oder sich in neue Data Science Pakete für seine ausgewählte Programmiersprache einzuarbeiten. Auch müssen die richtigen Algorithmen zur Datenauswertung ausgewählt, richtig parametrisiert und getestet werden, manchmal stellt sich dabei heraus, dass die ausgewählten Methoden nicht die optimalen waren. Letztendlich soll ein Mehrwert für den Fachbereich generiert werden und auch auf dieser Ebene wird ein Data Scientist vor besondere Herausforderungen gestellt.


english-flagRead this article in English:
“Data Science Knowledge Stack – Abstraction of the Data Scientist Skillset”


Data Science Knowledge Stack

Mit dem Data Science Knowledge Stack möchte ich einen strukturierten Einblick in die Aufgaben und Herausforderungen eines Data Scientists geben. Die Schichten des Stapels stellen zudem einen bidirektionalen Fluss dar, der von oben nach unten und von unten nach oben verläuft, denn Data Science als Disziplin ist ebenfalls bidirektional: Wir versuchen gestellte Fragen mit Daten zu beantworten oder wir schauen, welche Potenziale in den Daten liegen, um bisher nicht gestellte Fragen zu beantworten.

Der Data Science Knowledge Stack besteht aus sechs Schichten:

Database Technology Knowledge

Ein Data Scientist arbeitet im Schwerpunkt mit Daten und die liegen selten direkt in einer CSV-Datei strukturiert vor, sondern in der Regel in einer oder in mehreren Datenbanken, die ihren eigenen Regeln unterliegen. Insbesondere Geschäftsdaten, beispielsweise aus dem ERP- oder CRM-System, liegen in relationalen Datenbanken vor, oftmals von Microsoft, Oracle, SAP oder eine Open-Source-Alternative. Ein guter Data Scientist beherrscht nicht nur die Structured Query Language (SQL), sondern ist sich auch der Bedeutung relationaler Beziehungen bewusst, kennt also auch das Prinzip der Normalisierung.

Andere Arten von Datenbanken, sogenannte NoSQL-Datenbanken (Not only SQL)  beruhen auf Dateiformaten, einer Spalten- oder einer Graphenorientiertheit, wie beispielsweise MongoDB, Cassandra oder GraphDB. Einige dieser Datenbanken verwenden zum Datenzugriff eigene Programmiersprachen (z. B. JavaScript bei MongoDB oder die graphenorientierte Datenbank Neo4J hat eine eigene Sprache namens Cypher). Manche dieser Datenbanken bieten einen alternativen Zugriff über SQL (z. B. Hive für Hadoop).

Ein Data Scientist muss mit unterschiedlichen Datenbanksystemen zurechtkommen und mindestens SQL – den Quasi-Standard für Datenverarbeitung – sehr gut beherrschen.

Data Access & Transformation Knowledge

Liegen Daten in einer Datenbank vor, können Data Scientists einfache (und auch nicht so einfache) Analysen bereits direkt auf der Datenbank ausführen. Doch wie bekommen wir die Daten in unsere speziellen Analyse-Tools? Hierfür muss ein Data Scientist wissen, wie Daten aus der Datenbank exportiert werden können. Für einmalige Aktionen kann ein Export als CSV-Datei reichen, doch welche Trennzeichen und Textqualifier können verwendet werden? Eventuell ist der Export zu groß, so dass die Datei gesplittet werden muss.
Soll eine direkte und synchrone Datenanbindung zwischen dem Analyse-Tool und der Datenbank bestehen, kommen Schnittstellen wie REST, ODBC oder JDBC ins Spiel. Manchmal muss auch eine Socket-Verbindung hergestellt werden und das Prinzip einer Client-Server-Architektur sollte bekannt sein. Auch mit synchronen und asynchronen Verschlüsselungsverfahren sollte ein Data Scientist vertraut sein, denn nicht selten wird mit vertraulichen Daten gearbeitet und ein Mindeststandard an Sicherheit ist zumindest bei geschäftlichen Anwendungen stets einzuhalten.

Viele Daten liegen nicht strukturiert in einer Datenbank vor, sondern sind sogenannte unstrukturierte oder semi-strukturierte Daten aus Dokumenten oder aus Internetquellen. Auch hier haben wir es mit Schnittstellen zutun, ein häufiger Einstieg für Data Scientists stellt beispielsweise die Twitter-API dar. Manchmal wollen wir Daten in nahezu Echtzeit streamen, beispielsweise Maschinendaten. Dies kann recht anspruchsvoll sein, so das Data Streaming beinahe eine eigene Disziplin darstellt, mit der ein Data Scientist schnell in Berührung kommen kann.

Programming Language Knowledge

Programmiersprachen sind für Data Scientists Werkzeuge, um Daten zu verarbeiten und die Verarbeitung zu automatisieren. Data Scientists sind in der Regel keine richtigen Software-Entwickler, sie müssen sich nicht um Software-Sicherheit oder -Ergonomie kümmern. Ein gewisses Basiswissen über Software-Architekturen hilft jedoch oftmals, denn immerhin sollen manche Data Science Programme in eine IT-Landschaft integriert werden. Unverzichtbar ist hingegen das Verständnis für objektorientierte Programmierung und die gute Kenntnis der Syntax der ausgewählten Programmiersprachen, zumal nicht jede Programmiersprache für alle Vorhaben die sinnvollste ist.

Auf dem Level der Programmiersprache gibt es beim Arbeitsalltag eines Data Scientists bereits viele Fallstricke, die in der Programmiersprache selbst begründet sind, denn jede hat ihre eigenen Tücken und Details entscheiden darüber, ob eine Analyse richtig oder falsch abläuft: Beispielsweise ob Datenobjekte als Kopie oder als Referenz übergeben oder wie NULL-Werte behandelt werden.

Data Science Tool & Library Knowledge

Hat ein Data Scientist seine Daten erstmal in sein favorisiertes Tool geladen, beispielsweise in eines von IBM, SAS oder in eine Open-Source-Alternative wie Octave, fängt seine Kernarbeit gerade erst an. Diese Tools sind allerdings eher nicht selbsterklärend und auch deshalb gibt es ein vielfältiges Zertifizierungsangebot für diverse Data Science Tools. Viele (wenn nicht die meisten) Data Scientists arbeiten überwiegend direkt mit einer Programmiersprache, doch reicht diese alleine nicht aus, um effektiv statistische Datenanalysen oder Machine Learning zu betreiben: Wir verwenden Data Science Bibliotheken, also Pakete (Packages), die uns Datenstrukturen und Methoden als Vorgabe bereitstellen und die Programmiersprache somit erweitern, damit allerdings oftmals auch neue Tücken erzeugen. Eine solche Bibliothek, beispielsweise Scikit-Learn für Python, ist eine in der Programmiersprache umgesetzte Methodensammlung und somit ein Data Science Tool. Die Verwendung derartiger Bibliotheken will jedoch gelernt sein und erfordert für die zuverlässige Anwendung daher Einarbeitung und Praxiserfahrung.

Geht es um Big Data Analytics, also die Analyse von besonders großen Daten, betreten wir das Feld von Distributed Computing (Verteiltes Rechnen). Tools (bzw. Frameworks) wie Apache Hadoop, Apache Spark oder Apache Flink ermöglichen es, Daten zeitlich parallel auf mehren Servern zu verarbeiten und auszuwerten. Auch stellen diese Tools wiederum eigene Bibliotheken bereit, für Machine Learning z. B. Mahout, MLlib und FlinkML.

Data Science Method Knowledge

Ein Data Scientist ist nicht einfach nur ein Bediener von Tools, sondern er nutzt die Tools, um seine Analyse-Methoden auf Daten anzuwenden, die er für die festgelegten Ziele ausgewählt hat. Diese Analyse-Methoden sind beispielweise Auswertungen der beschreibenden Statistik, Schätzverfahren oder Hypothesen-Tests. Etwas mathematischer sind Verfahren des maschinellen Lernens zum Data Mining, beispielsweise Clusterung oder Dimensionsreduktion oder mehr in Richtung automatisierter Entscheidungsfindung durch Klassifikation oder Regression.

Maschinelle Lernverfahren funktionieren in der Regel nicht auf Anhieb, sie müssen unter Einsatz von Optimierungsverfahren, wie der Gradientenmethode, verbessert werden. Ein Data Scientist muss Unter- und Überanpassung erkennen können und er muss beweisen, dass die Vorhersageergebnisse für den geplanten Einsatz akkurat genug sind.

Spezielle Anwendungen bedingen spezielles Wissen, was beispielsweise für die Themengebiete der Bilderkennung (Visual Computing) oder der Verarbeitung von menschlicher Sprache (Natural Language Processiong) zutrifft. Spätestens an dieser Stelle öffnen wir die Tür zum Deep Learning.

Fachexpertise

Data Science ist kein Selbstzweck, sondern eine Disziplin, die Fragen aus anderen Fachgebieten mit Daten beantworten möchte. Aus diesem Grund ist Data Science so vielfältig. Betriebswirtschaftler brauchen Data Scientists, um Finanztransaktionen zu analysieren, beispielsweise um Betrugsszenarien zu erkennen oder um die Kundenbedürfnisse besser zu verstehen oder aber, um Lieferketten zu optimieren. Naturwissenschaftler wie Geologen, Biologen oder Experimental-Physiker nutzen ebenfalls Data Science, um ihre Beobachtungen mit dem Ziel der Erkenntnisgewinnung zu machen. Ingenieure möchten die Situation und Zusammenhänge von Maschinenanlagen oder Fahrzeugen besser verstehen und Mediziner interessieren sich für die bessere Diagnostik und Medikation bei ihren Patienten.

Damit ein Data Scientist einen bestimmten Fachbereich mit seinem Wissen über Daten, Tools und Analyse-Methoden ergebnisorientiert unterstützen kann, benötigt er selbst ein Mindestmaß an der entsprechenden Fachexpertise. Wer Analysen für Kaufleute, Ingenieure, Naturwissenschaftler, Mediziner, Juristen oder andere Interessenten machen möchte, muss eben jene Leute auch fachlich verstehen können.

Engere Data Science Definition

Während die Data Science Pioniere längst hochgradig spezialisierte Teams aufgebaut haben, suchen beispielsweise kleinere Unternehmen eher den Data Science Allrounder, der vom Zugriff auf die Datenbank bis hin zur Implementierung der analytischen Anwendung das volle Aufgabenspektrum unter Abstrichen beim Spezialwissen übernehmen kann. Unternehmen mit spezialisierten Daten-Experten unterscheiden jedoch längst in Data Scientists, Data Engineers und Business Analysts. Die Definition für Data Science und die Abgrenzung der Fähigkeiten, die ein Data Scientist haben sollte, schwankt daher zwischen der breiteren und einer engeren Abgrenzung.

Die engere Betrachtung sieht vor, dass ein Data Engineer die Datenbereitstellung übernimmt, der Data Scientist diese in seine Tools lädt und gemeinsam mit den Kollegen aus dem Fachbereich die Datenanalyse betreibt. Demnach bräuchte ein Data Scientist kein Wissen über Datenbanken oder APIs und auch die Fachexpertise wäre nicht notwendig…

In der beruflichen Praxis sieht Data Science meiner Erfahrung nach so nicht aus, das Aufgabenspektrum umfasst mehr als nur den Kernbereich. Dieser Irrtum entsteht in Data Science Kursen und auch in Seminaren – würde ich nicht oft genug auf das Gesamtbild hinweisen. In Kursen und Seminaren, die Data Science als Disziplin vermitteln wollen, wird sich selbstverständlich auf den Kernbereich fokussiert: Programmierung, Tools und Methoden aus der Mathematik & Statistik.

Entscheidungsbaum-Algorithmus ID3

Dieser Artikel ist Teil 2 von 4 der Artikelserie Maschinelles Lernen mit Entscheidungsbaumverfahren.

Entscheidungsbäume sind den Ingenieuren bestens bekannt, um Produkte hierarchisch zu zerlegen und um Verfahrensanweisungen zu erstellen. Die Data Scientists möchten ebenfalls Verfahrensanweisungen erstellen, jedoch automatisiert aus den Daten heraus. Auf diese Weise angewendet, sind Entscheidungsbäume eine Form des maschinellen Lernens: Die Maschine soll selbst einen Weg finden, um ein Objekt einer Klasse zuzuordnen.

Der ID3-Algorithmus

Den ID3-Algorithmus zu verstehen lohnt sich, denn er ist die Grundlage für viele weitere, auf ihn aufbauende Algorithmen. Er ist mit seiner iterativen und rekursiven Vorgehensweise auch recht leicht zu verstehen, er darf nur wiederum nicht in seiner Wirkung unterschätzt werden. Die Vorgehensweise kann in drei wesentlichen Schritten zerlegt werden, wobei der erste Schritt die eigentliche Wirkung (mit allen Vor- und Nachteilen) entfaltet:

  1. Schritt: Auswählen des Attributes mit dem höchsten Informationsgewinn
    Betrachte alle Attribute (Merkmale) des Datensatzes und bestimme, welches Attribut die Daten am besten klassifiziert.
  2. Schritt: Anlegen eines Knotenpunktes mit dem Attribut
    Sollten die Ergebnisse unter diesem Knoten eindeutig sein (1 unique value), speichere es in diesem Knotenpunkt und springe zurück.
  3. Schritt: Rekursive Fortführung dieses Prozesses
    Andernfalls zerlege die Daten jedem Attribut entsprechend in n Untermengens (subsets), und wiederhole diese Schritte für jede der Teilmengen.

Der Informationsgewinn (Information Gain) – und wie man ihn berechnet


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) = E(S) - \sum_{i=1}^n \frac{\bigl|S_i\bigl|}{\bigl|S\bigl|} \cdot E(S_i)

Wie die Berechnung des Informationsgewinnes funktioniert, wird Teil 3 dieser Artikel-Reihe (erscheint in Kürze) zeigen.

Die Vorzüge des ID3-Algorithmus – und die Nachteile

Der Algorithmus ist die Grundlage für viele weitere Algorithmen. In seiner Einfachheit bringt er gewisse Vorteile – die ihn vermutlich zum verbreitesten Entscheidungsbaum-Algorithmus machen – mit sich, aber hat auch eine Reihe von Nachteilen, die bedacht werden sollten.

Vorteile Nachteile
  • leicht verständlich und somit schnell implementiert
  • stellt eine gute Basis für Random Forests dar
  • alle Attribute spielen eine Rolle, der Baum wird aber tendenziell klein, da der Informationsgewinn die Reihenfolge vorgibt
  • funktioniert (mit Anpassungen) auch für Mehrfachklassifikation
  • aus der Reihenfolge durch den Informationsgewinn entsteht nicht unbedingt der beste bzw. kleinste Baum unter allen Möglichkeiten. Es ist ein Greedy-Algorithmus und somit “kurzsichtig”
  • die Suche nach Entscheidungsregeln ist daher auch nicht vollständig/umfassend
  • da der Baum via ID3 solange weiterwachsen soll, bis die Daten so eindeutig wie möglich erklärt sind, wird Overfitting geradezu provoziert

Overfitting (Überanpassung) beachten und vermeiden

Aus Daten heraus generierte Entscheidungsbäume neigen zur Überanpassung. Das bedeutet, dass sich die Bäume den Trainingsdaten soweit anpassen können, dass sie auf diese perfekt passen, jedoch keine oder nur noch einen unzureichende generalisierende Beschreibung mehr haben. Neue Daten, die eine höhere Vielfältigkeit als die Trainingsdaten haben können, werden dann nicht mehr unter einer angemessenen Fehlerquote korrekt klassifiziert.

Vorsicht vor Key-Spalten!

Einige Attribute erzwingen eine Überanpassung regelrecht: Wenn beispielsweise ein Attribut wie „Kunden-ID“ (eindeutige Nummer pro Kunde) einbezogen wird, haben wir – bezogen auf das Klassifikationsergebnis – für jeden einzelnen Wert in dem Attribut eine Entropie von 0 zu erwarten, denn jeder ID beschreibt einen eindeutigen Fall (Kunde, Kundengruppe etc.). Daraus folgt, dass der Informationsgewinn für dieses Attribut maximal wird. Hier würde der Baum eine enorme Breite erhalten, die nicht hilfreich wäre, denn jeder Wert (IDs) bekäme einen einzelnen Ast im Baum, der zu einem eindeutigen Ergebnis führt. Auf neue Daten (neue Kundennummern) ist der Baum nicht anwendbar, denn er stellt keine generalisierende Beschreibung mehr dar, sondern ist nur noch ein Abbild der Trainingsdaten.

Prunning – Den Baum nachträglich kürzen

Besonders große Bäume sind keine guten Bäume und ein Zeichen für Überanpassung. Eine Möglichkeit zur Verkleinerung ist das erneute Durchrechnen der Informationsgewinne und das kürzen von Verzweigungen (Verallgemeinerung), sollte der Informationsgewinn zu gering sein. Oftmals wird hierfür nicht die Entropie oder der Gini-Koeffizient, sondern der Klassifikationsfehler als Maß für die Unreinheit verwendet.

Random Forests als Overfitting-Allheilmittel

Bei Random Forests (eine Form des Ensemble Learning) handelt es sich um eine Gemeinschaftsentscheidung der Klassenzugehörigkeit über mehrere Entscheidungsbäume. Diese Art des “demokratischen” Machine Learnings wird auch Ensemble Learning genannt. Werden mehrere Entscheidungsbäume unterschiedlicher Strukturierung zur gemeinsamen Klassifikation verwendet, wird die Wirkung des Overfittings einzelner Bäume in der Regel reduziert.