Data Science – was ist das eigentlich?!

Annalyn Ng · Kenneth Soo

Data Science – was ist das eigentlich?! Algorithmen des maschinellen Lernens verständlich erklärt

Data Science – was ist das eigentlich?!

Annalyn Ng · Kenneth Soo

Data Science – was ist das eigentlich?! Algorithmen des maschinellen Lernens verständlich erklärt Aus dem Englischen übersetzt von ­Matthias Delbrück

Annalyn Ng Singapur, Singapur

Kenneth Soo Singapur, Singapur

ISBN 978-3-662-56775-3 ISBN 978-3-662-56776-0  (eBook) https://doi.org/10.1007/978-3-662-56776-0 Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über http:// dnb.d-nb.de abrufbar. Übersetzung der englischsprachigen Ausgabe: Numsense! Data Science for the Layman: No Math Added von Annalyn Ng und Kenneth Soo. © 2017 by Annalyn Ng and Kenneth Soo. Alle Rechte vorbehalten. © Springer-Verlag GmbH Deutschland, ein Teil von Springer Nature 2018 Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Jede Verwertung, die nicht ausdrücklich vom Urheberrechtsgesetz zugelassen ist, bedarf der vorherigen Zustimmung des Verlags. Das gilt insbesondere für Vervielfältigungen, Bearbeitungen, Übersetzungen, Mikroverfilmungen und die Einspeicherung und Verarbeitung in elektronischen Systemen. Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche Namen im Sinne der Warenzeichen- und MarkenschutzGesetzgebung als frei zu betrachten wären und daher von jedermann benutzt werden dürften. Der Verlag, die Autoren und die Herausgeber gehen davon aus, dass die Angaben und Informationen in diesem Werk zum Zeitpunkt der Veröffentlichung vollständig und korrekt sind. Weder der Verlag noch die Autoren oder die Herausgeber übernehmen, ausdrücklich oder implizit, Gewähr für den Inhalt des Werkes, etwaige Fehler oder Äußerungen. Der Verlag bleibt im Hinblick auf geografische Zuordnungen und Gebietsbezeichnungen in veröffentlichten Karten und Institutionsadressen neutral. Einbandabbildung: © monsitj/stock.adobe.com Springer ist ein Imprint der eingetragenen Gesellschaft Springer-Verlag GmbH, DE und ist ein Teil von Springer Nature Die Anschrift der Gesellschaft ist: Heidelberger Platz 3, 14197 Berlin, Germany

Dieses Buch ist Ihnen, unseren Leserinnen und Lesern, gewidmet – von zwei Data-Science-Enthusiasten, Annalyn Ng (University of Cambridge) und Kenneth Soo (Stanford University). Uns fiel auf, dass Data Science zwar immer häufiger in betrieblichen Entscheidungsprozessen eingesetzt wird, jedoch kaum jemand wirklich etwas darüber weiß. Darum haben wir aus unseren Tutorials ein Buch zusammengestellt – für wissbegierige Studierende, Professionals in Unternehmen oder schlicht alle Neugierigen. Jedes Tutorial deckt die wichtigsten Funktionen und Annahmen einer Data-Science-Methode ab, und das ohne Mathematik und Fachausdrücke. Illustriert werden die Methoden mit „Real-Life-Daten“ und Beispielen.

Allein hätten wir dieses Buch jedoch nicht schreiben können. Wir danken Sonya Chan, unserer Lektorin und guten Freundin, die unsere unterschiedlichen Schreibstile gekonnt zusammengefügt und dafür gesorgt hat, dass der rote Faden nahtlos durchläuft. Dora Tan danken wir für ihre Ratschläge zum Layout und zu den Grafiken. Unseren Freunden Michelle Poh, Dennis Chew and Mark Ho verdanken wir unschätzbare Tipps, wie sich der Inhalt noch verständlicher ausdrücken ließ. Ebenso danken wir Prof. Long Nguyen (University of Michigan, Ann Arbor), Prof. Percy Liang (Stanford University) und Dr. Michal Kosinski (Stanford University) für die Geduld, mit der sie uns ausgebildet haben, und für ihre Expertise, an der sie uns bereitwillig teilhaben ließen. Zum Schluss möchten wir uns selbst gegenseitig danken – wir zanken uns wie gute Freunde, bleiben aber immer dran, bis das fertig ist, was wir zusammen begonnen haben.

Vorwort

„Big Data“ bedeutet heute „Big Business“. In dem Maß, in dem immer größere Datensammlungen fast alle Aspekte unseres Lebens bestimmen, stürzen sich immer mehr Unternehmen darauf, solche Daten zu Geld zu machen. Techniken zur Mustererkennung und datenbasierte Vorhersagen eröffnen neue Dimensionen geschäftlicher Strategien. Intelligente Produktempfehlungen etwa sind eine Win-win-Situation für Verkäufer und Kunden, wenn sie Kunden auf Produkte aufmerksam machen, an denen sie mit hoher Wahrscheinlichkeit tatsächlich interessiert sind, und die Gewinne der Verkäufer gleichzeitig durch die Decke gehen.

VII

VIII     Vorwort

Big Data ist jedoch nur ein Aspekt des Phänomens. Data Science1 erlaubt es uns, Daten in nahezu beliebiger Menge zu analysieren und zu bearbeiten. Diese neue interdisziplinäre Wissenschaft umfasst unter anderem maschinelles Lernen, Statistik und verwandte Zweige der Mathematik. Das maschinelle Lernen steht hier übrigens nicht zufällig an erster Stelle. Es ist das primäre Werkzeug für das Erkennen von Mustern in Datensätzen und für daraus abgeleitete Prognosen. Mithilfe der Algorithmen des maschinellen Lernens ermöglicht Data Science unschätzbare Einsichten und ganz neue Wege, Informationen aus Daten zu destillieren. Um zu erkennen, wie Data Science die derzeitige Datenrevolution antreibt, brauchen Uneingeweihte allerdings zumindest ein Grundverständnis dieses vielfältigen Wissensgebiets. Die dazu benötigten Kenntnisse stellen leider für manche eine große Hürde dar, der weitverbreitete Datenanalphabetismus führt in der Praxis zu einem massiven Bedarf an Fachkräften. An dieser Stelle kommt Data Science – was ist das eigentlich?! ins Spiel. Wer die Arbeiten von Annalyn Ng und Kenneth Soo kennt, ist nicht verwundert, dass ihr Buch die Frage im Titel leicht verständlich beantwortet. Hier geht es um Data Science für Uneingeweihte, und die oft sehr komplexe Mathematik – welche das Buch durchaus auf hohem Niveau beschreibt – wird absichtlich nicht im Detail hergeleitet. 1Man könnte „Data Science“ als Datenwissenschaft übersetzen, im Deutschen wird jedoch in der Regel der englische Begriff verwendet. Ähnliches gilt für viele andere Fachbegriffe wie Support vector oder Random Forests (Anm. d. Übers.).

Vorwort      IX

Verstehen Sie dies nicht falsch: Der Inhalt wird in keiner Weise versimpelt, vielmehr enthält das Buch robuste Informationen, die knapp und präzise zusammengefasst sind. Was nützt einem dieser Ansatz, könnten Sie sich jetzt fragen. Ziemlich viel – ich würde sagen, dass dies für Anfängerinnen und Anfänger auf jeden Fall der denkbar sinnvollste Einstieg ist. Denken Sie an einen Fahrschüler in der ersten Fahrstunde: Funktion und Bedienung der wichtigsten Schalter sind erst einmal wichtiger als die thermodynamische Theorie des Verbrennungsmotors. Das Gleiche gilt für Data Science: Wenn Sie das Fach kennenlernen wollen, ist es besser, mit allgemeinen Konzepten zu beginnen, anstatt sich sofort in mathematischen Formalien zu verlieren. Die Einführung des Buchs macht den Laien auf wenigen Seiten mit den grundlegenden Konzepten vertraut, sodass jede und jeder auf demselben Fundament zu bauen beginnt. Wichtige Themen wie das Auswählen von geeigneten Algorithmen – die oft in einführenden Texten ausgelassen werden – werden hier direkt angesprochen. Auf diese Weise versteht der Leser auch gleich, wie wichtig es ist, sich weiter mit dem Thema zu beschäftigen, und er erhält gleichzeitig einen umfassenden Bezugsrahmen dafür. Es gibt natürlich sehr viele weitere Themen der Data Science, die Annalyn und Kenneth mit Fug und Recht auch noch in ihr Buch hätten aufnehmen können, und ebenso natürlich eine Vielzahl von möglichen Darstellungsweisen. Ihre Entscheidung, sich auf die wichtigsten Algorithmen des maschinellen Lernens zu konzentrieren, zusammen mit ein paar thematisch passenden Szenarios, war großartig. Gut eingeführte Algorithmen wie

X     Vorwort

k-Means-Clustering, Entscheidungsbäume und k-nächste Nachbarn werden gebührend gewürdigt. Neuere Klassifikations- und Ensemble-Algorithmen wie Support-Vektor-Maschinen – deren komplexe Mathematik einen schon ziemlich einschüchtern kann – oder Random Forests werden ebenso erklärt wie die neuronalen Netze, die hinter dem aktuellen Deep-Learning-Hype stecken. Eine weitere Stärke von Data Science – was ist das eigentlich?! sind die intuitiven Anwendungsbeispiele. Seien es die Verbrechensvorhersage mit Random Forests oder das Clustering von Blockbuster-Fans, die gewählten Beispiele verbinden Klarheit mit Alltagsbezug. Gleichzeitig hält die Abwesenheit von jeglicher höheren Mathematik das Interesse und die Motivation lebendig, sich auf das spannende Studium von Data Science einzulassen. Ich kann dieses Buch wirklich nur empfehlen: Data Science für Laien ist der ideale Einstieg in die Welt von Data Science und ihren Algorithmen. Ich fände es schwierig, eine vergleichbare Alternative zu benennen. Mit Data Science – was ist das eigentlich?! gibt es keinen Grund mehr, sich von der Mathematik den Spaß am Lernen ausreden zu lassen! Matthew Mayo Data-Science-Experte und Mitherausgeber von KDnuggets @mattmayo13

Inhaltsverzeichnis

1

Das Wichtigste in Kürze … 1 1.1 Datenaufbereitung 2 1.2 Auswahl des Algorithmus 7 1.3 Parameter 11 1.4 Evaluation der Ergebnisse 14 1.5 Zusammenfassung 18

2

k-Means-Clustering 19 2.1 Wie man Kunden-Cluster findet 19 2.2 Beispiel: Persönlichkeitsprofile von Filmfans 20 2.3 Cluster definieren 22 2.4 Grenzen 27 2.5 Zusammenfassung 28

XI

XII     Inhaltsverzeichnis

3 Hauptkomponentenanalyse 29 3.1 Der Nährwertgehalt von Lebensmitteln 29 3.2 Hauptkomponenten 31 3.3 Beispiel: Nahrungsmittelgruppen 34 3.4 Grenzen 40 3.5 Zusammenfassung 43 4 Assoziationsanalyse 45 4.1 Muster im Einkaufsverkaufsverhalten 45 4.2 Support, Konfidenz und Lift 46 4.3 Beispiel: Daten aus einem Lebensmittelgeschäft 49 4.4 Das A-priori-Prinzip 52 4.5 Grenzen 55 4.6 Zusammenfassung 56 5

Soziale Netzwerkanalyse 57 5.1 Beziehungen abbilden 57 5.2 Beispiel: Waffenhandel und Geopolitik 59 5.3 Die Louvain-Methode 63 5.4 PageRank-Algorithmus 65 5.5 Grenzen 69 5.6 Zusammenfassung 71

6 Regressionsanalyse 73 6.1 Trendlinien 73 6.2 Beispiel: Vorhersage von Hauspreisen 74

Inhaltsverzeichnis      XIII

6.3 6.4 6.5 6.6 6.7 7

Gradientenverfahren 78 Regressionskoeffizienten 80 Korrelationskoeffizienten 82 Grenzen 84 Zusammenfassung 85

k-nächste Nachbarn und Ausreißererkennung 87 7.1 Der Weindetektiv 87 7.2 Gleich und gleich gesellt sich gern 88 7.3 Beispiel: Der statistische Sommelier 90 7.4 Ausreißererkennung 92 7.5 Grenzen 94 7.6 Zusammenfassung 94

8 Support-Vektor-Maschine 97 8.1 „Nein“ oder „Oh Nein“? 97 8.2 Beispiel: Diagnose einer Herzerkrankung 98 8.3 Die optimale Grenzlinie 100 8.4 Grenzen 104 8.5 Zusammenfassung 105 9 Entscheidungsbaum 107 9.1 Wie man eine Katastrophe überlebt 107 9.2 Beispiel: Rettung von der Titanic 109

XIV     Inhaltsverzeichnis

9.3

Einen Entscheidungsbaum erstellen 110 9.4 Grenzen 113 9.5 Zusammenfassung 115

10 Random Forests 117 10.1 Die Weisheit der Crowd 117 10.2 Beispiel: Verbrechensvorhersage 118 10.3 Ensembles 123 10.4 Bootstrap Aggregating 124 10.5 Grenzen 126 10.6 Zusammenfassung 127 11 Neuronale Netze 129 11.1 Bauen Sie sich ein Gehirn! 129 11.2 Beispiel: Handgeschriebene Zahlen erkennen 132 11.3 Wie ein neuronales Netz denkt 135 11.4 Aktivierungsregeln 139 11.5 Grenzen 140 11.6 Zusammenfassung 144 12 A/B-Tests und vielarmige Banditen 147 12.1 Grundlagen des A/B-Tests 147 12.2 Grenzen von A/B-Tests 148 12.3 Abnehmendes-Epsilon-Strategie 149 12.4 Beispiel: Vielarmige Banditen 150

Inhaltsverzeichnis      XV

12.5 Nett zu wissen: van Gaals Elfmeterschützen 153 12.6 Grenzen einer AbnehmendesEpsilon-Strategie 154 12.7 Zusammenfassung 156 Anhang 157 Glossar 165 Literatur 175

Über die Autoren

Annalyn Ng schloss ihr Studium an der University of Michigan in Ann Arbor ab, wo sie auch als Statistik-Tutorin arbeitete. Anschließend erwarb sie einen Master of Philosophy am Psychometrie-Zentrum der University of Cambridge, wo sie mithilfe von Data Mining an Daten aus sozialen Medien gezielte Werbekampagnen erarbeitete und kognitive Einstellungstests programmierte. Disney Research gewann sie später für ihr Behavioral-­SciencesTeam, wo sie psychologische Kundenprofile erforschte. Kenneth Soo erwarb seinen Master of Science in Sta­ tistik an der Stanford University. Vorher erzielte er wäh­ rend seiner drei Studienjahre an der University of Warwick durchgängig Top-Ergebnisse in „Mathematics, Operational Research, Statistics and Economics“ (MORSE). Dort arbeitete er auch als Research Assistant in der Gruppe XVII

XVIII     Über die Autoren

„Operational Research & Management Sciences“, und zwar über bikriterielle robuste Optimierung mit Anwendungen in zufallsfehleranfälligen Netzwerken. Die Autoren freuen sich über Feedback zum Buch und sind hierfür unter [email protected] erreichbar.

Warum Data Science?

Stellen Sie sich vor, Sie sind eine junge Ärztin oder ein junger Arzt. Ein Patient kommt in Ihre Klinik und klagt über Kurzatmigkeit, Brustschmerzen und gelegentliches Sodbrennen. Sie prüfen Blutdruck und Puls, beides normal, es gibt keine relevanten Vorerkrankungen. Der Patient macht allerdings einen etwas rundlichen Eindruck. Und da seine Symptome ziemlich typisch für übergewichtige Menschen sind, versichern Sie ihm, dass alles unter Kontrolle ist, und raten für alle Fälle zu etwas sportlicher Betätigung. Allzu oft führt eine solche Situation zu einer nicht diagnostizierten Herzerkrankung – denn Patienten mit Herzproblemen zeigen häufig ganz ähnliche Symptome wie sonst gesunde Übergewichtige. So werden weitere Tests XIX

XX     Warum Data Science?

unterlassen, welche die ernstere Erkrankung aufgezeigt hätten (siehe hierzu auch Abschn. 8.2). Unsere menschlichen Urteile werden von begrenzten, subjektiven Erfahrungen und unvollständigem Wissen geleitet. Dies beeinträchtigt unsere Entscheidungsfindung und kann, wie im Fall eines unerfahrenen Arztes, weitere Untersuchungen verhindern, welche zu akkurateren Schlüssen geführt hätten. Dies ist die Stelle, an der Data Science helfen kann. Anstatt sich auf das Urteil eines Einzelnen zu verlassen, erlauben uns Data-Science-Techniken, Informationen aus vielen Quellen zu verwerten, um so zu besseren Entscheidungen zu kommen. Wir könnten zum Beispiel archivierte Patientendaten auswerten, in denen ähnliche Symptome vorkommen, und so auf Diagnosen stoßen, auf die wir von allein nicht gekommen wären. Mit modernen Rechnern und fortschrittlichen Algorithmen können wir • versteckte Trends in großen Datensätzen aufspüren, • mithilfe von Trends Vorhersagen treffen, • die Wahrscheinlichkeit jedes möglichen Ergebnisses berechnen und • schnell exakte Resultate erhalten. Dieses Buch wurde, wie bereits im Vorwort angekündigt, in Laiensprache geschrieben und führt ganz sanft in die Konzepte und Algorithmen von Data Science ein. Dazu greifen wir auf intuitive Erklärungen und jede Menge Grafiken zurück.

Warum Data Science?      XXI

Jeder behandelte Algorithmus hat sein eigenes Kapitel, das erklärt, wie er funktioniert, und eine Beispielanwendung aus dem prallen Leben vorstellt. Die dabei benutzten Daten sind online verfügbar, die Quellen finden Sie im Anhang. Wenn Sie wiederholen möchten, was Sie gelernt haben, schauen Sie zunächst in die Zusammenfassungen der einzelnen Kapitel. Am Ende des Buchs haben wir dann noch einmal die Vor- und Nachteile der einzelnen Algorithmen tabellarisch zusammengestellt, dazu gibt es ein Glossar von häufig auftauchenden Begriffen. Wir hoffen, dass wir Ihnen mit diesem Buch zu einem ersten praktischen Verständnis von Data Science verhelfen können, sodass auch Sie mit Data-Science-Techniken fundierte Entscheidungen treffen werden. Auf geht’s!

1 Das Wichtigste in Kürze …

… aber so kurz dann auch wieder nicht. Um wirklich verstehen zu können, wie die Data-Science-Algorithmen funktionieren, müssen wir bei den Grundlagen beginnen. Daher ist diese Einleitung das längste Kapitel in diesem Buch, etwa doppelt so lang wie die übrigen Kapitel, welche die einzelnen Algorithmen vorstellen. Dafür gewinnen Sie aber mit dieser Einleitung auch einen soliden Überblick über die fundamentalen Schritte, die praktisch im gesamten Data-Science-Bereich immer wieder auftauchen. Wenn Sie diese grundlegenden Prozesse kennen, können Sie für Ihre Untersuchungen geeignete Algorithmen auswählen und auch deren Grenzen abschätzen. Jede Data-Science-Studie enthält die folgenden vier Schritte: Erstens müssen die Daten prozessiert und für die Analyse aufbereitet werden. Dann werden für diese Studie © Springer-Verlag GmbH Deutschland, ein Teil von Springer Nature 2018 A. Ng und K. Soo, Data Science – was ist das eigentlich?!, https://doi.org/10.1007/978-3-662-56776-0_1

1

2     A. Ng und K. Soo

jeweils geeignete Algorithmen ausgewählt. Als Nächstes müssen die Parameter der Algorithmen optimiert werden. Schließlich werden Modelle abgeleitet, aus deren Vergleich (Evaluierung und Validierung) sich dann das für die jeweilige Situation am besten geeignete ergibt.

1.1 Datenaufbereitung Bei Data Science hängt letztlich alles von den Daten ab. Ist deren Qualität schlecht, wird selbst die ausgefeilteste Analyse nur Unfug hervorbringen. In diesem Abschnitt werden wir die wesentlichen Datenformate kennenlernen, ebenso wie Methoden der Datenaufbereitung zur Verbesserung der Resultate.

1.1.1 Datenformate Die gebräuchlichste Form, Daten zu präsentieren, ist die Tabelle (siehe Tab. 1.1). Jede Zeile steht für einen Datenpunkt, das heißt eine Einzelbeobachtung, jede Spalte zeigt eine Variable, deren Wert den Datenpunkt beschreibt. Variablen heißen auch Merkmale, Attribute oder Dimensionen. Je nachdem was wir vorhaben, können wir unterschiedliche Arten von Beobachtungen in den jeweiligen Zeilen anführen. Beispielsweise erlaubt uns die Darstellung in Tab. 1.1, nach Mustern in einer Reihe von Transaktionen zu suchen. Würden uns stattdessen jedoch Transaktionsmuster in Abhängigkeit vom Datum interessieren, müssten wir in den Zeilen die Daten eines Tages aggregieren.

1  Das Wichtigste in Kürze …     3

Für eine weitergehende Analyse könnten wir andererseits auch noch weitere Variablen aufnehmen, etwas das Wetter an dem jeweiligen Tag (siehe Tab. 1.2). Tab. 1.1  Fingierter Datensatz mit Lebensmitteleinkäufen („Transaktionen“) verschiedener Tiere in einem Supermarkt. Jede Zeile ist eine Transaktion, jede Spalte liefert Informationen über die Transaktionen Transaktion #

Variablen Tierart Datum

1 2 3

Pinguin Bär Kaninchen Pferd Pinguin Giraffe Kaninchen Katze

4 5 6 7 8

Gekaufte Fisch Betrag Früchte gekauft? (€)

1. Januar 1 1. Januar 4 1. Januar 6

Ja Ja Nein

5,30 9,70 6,50

2. Januar 2. Januar 3. Januar 3. Januar

Nein Ja Nein Nein

5,50 6,00 4,80 7,60

Ja

7,40

6 2 5 8

3. Januar ?

Tab. 1.2  Der fingierte Datensatz nach Tagen aggregiert und mit der zusätzlichen Variablen „Wetter“ Datum

1. Januar 2. Januar 3. Januar

Variablen Einnahmen (€)

Anzahl Kunden

Wochenende?

Wetter

21,50 11,50 19,80

3 2 3

Ja Nein Nein

Sonnig Regen Sonnig

4     A. Ng und K. Soo

1.1.2 Arten von Variablen Es gibt vier Grundtypen von Variablen, die jeweils passend zum verwendeten Algorithmus gewählt werden müssen. • Binär: Dies ist der einfachste Variablentyp, der nur zwei mögliche Werte annehmen kann. In Tab. 1.1 gibt eine binäre Variable an, ob ein Kunde Fisch gekauft hat oder nicht. • Qualitativ: Wenn es mehr als zwei Optionen gibt, die sich aber nicht unbedingt mit Zahlenwerten angeben lassen, kann die Information durch eine kategoriale Variable ausgedrückt werden. In Tab. 1.1 ist „Tierart“ eine kategoriale Variable. • Ganzzahlig oder diskret: Diese Variablen können entweder natürliche beziehungsweise ganze Zahlen als Werte haben oder aber eine gewisse Menge anderer „erlaubter“ Werte, zum Beispiel die Menge {1/2; 1/3; 1/4; 1/5; …}. In Tab. 1.1 gibt eine diskrete Variable an, wie viele Früchte der jeweilige Kunde gekauft hat. • Stetig: Dies ist die detaillierteste Art von Variablen. Sie nimmt reelle Zahlen, also Dezimalzahlen, mit im Prinzip beliebig vielen Nachkommastellen als Werte an. In Tab. 1.1 ist der von den Kunden ausgegebene Geldbetrag eine stetige Variable (hier sind es jeweils nur zwei Nachkommastellen).

1.1.3 Auswahl von geeigneten Variablen Oft haben wir es mit sehr großen Sätzen von Originaldaten zu tun, die eine Vielzahl von Variablen enthalten.

1  Das Wichtigste in Kürze …     5

Wenn man allerdings zu viele Variablen in einen Algorithmus füttert, kann dies zu langen Rechenzeiten oder auch falschen Vorhersagen aufgrund von „Datenrauschen“ führen. Darum müssen wir uns auf die wichtigen Variablen konzentrieren. Variablen auszuwählen ist oft ein Prozess mit Versuch und Irrtum, bei dem wir Variablen streichen oder hinzunehmen, je nach den ermittelten (Zwischen-)Ergebnissen. Ein guter Startpunkt sind einfache Plots zum Aufdecken von Korrelationen (siehe Abschn. 6.5) zwischen Variablen. Die interessantesten davon werden dann für die weitere Analyse ausgesucht.

1.1.4 Merkmalsextraktion Manchmal müssen die passenden Variablen allerdings erst „herausgezogen“ werden, man spricht auch von Feature Engineering. Wenn wir zum Beispiel vorhersagen möchten, welche Kunden in Tab. 1.1 keinen Fisch mögen, könnten wir die Variable „Tierart“ untersuchen und dann Zeile für Zeile herausfinden, dass Kaninchen, Pferde und Giraffen wohl eher keinen Fisch einkaufen würden. Hätten wir dagegen die Tierarten der Kunden von vornherein in die übergeordnete Kategorie „Pflanzenfresser, Allesfresser oder Fleischfresser“ gruppiert, bräuchten wir nicht mehr lange zu überlegen: Pflanzenfresser machen sich nichts aus Fisch. Man kann nicht nur die Werte einer Einzelvariablen umgruppieren, es lassen sich auch mehrere Variablen zusammenfassen, was man dann Dimensionsreduktion

6     A. Ng und K. Soo

nennt (Kap. 3). Mit Dimensionsreduktion extrahieren wir die interessantesten und nützlichsten Informationen aus einer Vielzahl von Variablen und analysieren sie dann anhand eines kleineren Satzes von Variablen.

1.1.5 Fehlende Daten Es ist nicht immer möglich, vollständige Datensätze zu sammeln. In Tab. 1.1 wurde zum Beispiel die Anzahl der bei der letzten Transaktion erworbenen Früchte nicht notiert. Fehlende Daten erschweren natürlich die Analyse; es gibt mehrere Möglichkeiten, damit umzugehen: • Näherungswerte: Wenn ein fehlender Wert bei entweder einer binären oder einer kategorialen Variablen auftritt, könnte man dafür den Modus (den häufigsten Wert im Datensatz) einsetzen. Bei diskreten oder stetigen Werten bietet sich der Median an (der Wert in der Mitte aller auftretenden Werte). Dieser Ansatz würde in Tab. 1.1 zu der Annahme führen, dass die Katze fünf Früchte gekauft hat, da 5 der Median der Menge {1; 2; 4; 5; 6; 6; 8} ist. • Berechnete Werte: Fehlende Werte könnten auch mithilfe von fortgeschrittenen Algorithmen des überwachten Lernens berechnet werden (dazu kommen wir in Abschn. 1.2). Auf diese Weise berechnete Schätzwerte sind zwar rechenaufwendiger, sind aber meist treffsicherer, da die Algorithmen nur ähnliche und nicht einfach alle Transaktionen in die Näherung einbeziehen. Aus Tab. 1.1 ersehen wir, dass Kunden, die

1  Das Wichtigste in Kürze …     7

Fisch kaufen, eher weniger Früchte erwerben, und schätzen daher, dass die Katze eher bloß zwei oder drei Früchte gekauft hat. • Werte streichen: Als letzter Ausweg bietet sich an, Zeilen mit fehlenden Werten komplett zu streichen. Dies versucht man jedoch möglichst zu vermeiden, da so natürlich die Zahl der für die Analyse verfügbaren Daten abnimmt. Darüber hinaus könnte der Ausschluss von Datenpunkten den verbleibenden Datensatz verfälschen, indem bestimmte Gruppen bevorzugt werden. Beispielsweise könnten Katzen besonders unwillig sein, die Zahl der von ihnen gekauften Früchte preiszugeben. Wenn wir dann Kunden ohne Angabe ihrer Frucht-Transaktionen ausschließen würden, wären ­Katzen im analysierten Datensatz unterrepräsentiert. Sind die Daten fertig aufbereitet, ist es für uns Zeit, mit der Datenanalyse zu beginnen.

1.2 Auswahl des Algorithmus In diesem Buch werden wir Ihnen zehn verschiedene Algorithmen vorstellen, mit denen Sie Ihre Daten analysieren können. Auf welchen Algorithmus die Wahl fällt, hängt von den Aufgaben ab, die wir zu erledigen haben. Diese fallen grundsätzlich in drei Kategorien. Tab. 1.3 zeigt Ihnen, zu welchen Kategorien die Algorithmen in diesem Buch gehören.

8     A. Ng und K. Soo Tab. 1.3  Kategorien von Algorithmen Algorithmen Unüberwachtes Lernen

Überwachtes Lernen

Bestärkendes Lernen

k-Means-Clustering Hauptkomponentenanalyse Assoziationsanalyse Soziale Netzwerkanalyse Regressionsanalyse k-nächste Nachbarn Support-Vektor-Maschine Entscheidungsbaum Random Forests Neuronale Netze A/B-Test, Abnehmendes-EpsilonStrategie (vielarmige Banditen)

1.2.1 Unüberwachtes Lernen Aufgabe: Sag mir, was für Muster in meinen Daten verborgen sind! Um versteckte Muster in unserem Datensatz aufzudecken, könnten wir Algorithmen des unüberwachten Lernens benutzen. Diese Algorithmen heißen „unüberwacht“, weil wir noch nicht wissen, nach welchem Muster wir eigentlich suchen, und es deshalb dem Algorithmus überlassen, was er ans Licht bringt. In Tab. 1.1 würde ein Modell mit unüberwachtem Lernen vielleicht herausfinden, welche Artikel oft zusammen gekauft werden (mithilfe der Assoziationsanalyse, siehe Kap. 4). Oder es könnte die Kunden anhand ihrer Einkäufe in Cluster gruppieren (das erklären wir in Kap. 2). Die Ergebnisse eines Algorithmus mit unüberwachtem Lernen können wir auf indirekte Weise validieren, das heißt

1  Das Wichtigste in Kürze …     9

überprüfen, etwa indem wir schauen, ob die gebildeten Kunden-Cluster mit bekannten (und vor allem sinnvollen) Kategorien übereinstimmen, zum Beispiel „Pflanzen-, Allesoder Fleischfresser“.

1.2.2 Überwachtes Lernen Aufgabe: Leite aus den Mustern in meinen Daten Prognosen ab! Wenn wir Vorhersagen machen wollen, bieten sich die Algorithmen des überwachten Lernens an. Diese Algorithmen sind insofern „überwacht“, als ihre Vorhersagen auf bestimmten vorgegebenen Mustern fußen sollen. Ein Modell mit überwachtem Lernen könnte anhand der Daten in Tab. 1.1 beispielsweise vorherzusagen lernen, wie viele Früchte ein Kunde aus einer gegebenen Tierart vermutlich kaufen würde, vorausgesetzt, er mag Fisch beziehungsweise nicht (unabhängige oder Prädiktor-Variablen ). Die Güte eines Modells mit überwachtem Lernen können wir ganz einfach und direkt testen: Wir setzen Werte für die Variablen Tierart und „kauft Fisch?“ ein und prüfen dann, ob beziehungsweise wie gut die vom Modell vorhergesagte Zahl der gekauften Früchte stimmt. Wenn wir diskrete oder stetige Zahlenwerte vorhersagen, beispielsweise die Zahl der gekauften Früchte, lösen wir ein Regressionsproblem (siehe Abb. 1.1a). Wenn wir binäre oder kategoriale Variablen vorhersagen (kauft Fisch/kauft keinen Fisch), hätten wir es mit einer Klassifikationsaufgabe zu tun (siehe Abb. 1.1b). Nichtsdestotrotz sind auch die meisten Klassifikationsalgorithmen dazu in der Lage,

10     A. Ng und K. Soo

a) Regression

b) Klassifikaon

Abb. 1.1  Bei einer Regressionsanalyse wird eine Trendlinie ausgerechnet, während eine Klassifikation die Einteilung von Datenpunkten in Gruppen erfordert. Beachten Sie, dass in beiden Aufgabentypen Fehler zu erwarten sind. Bei einer Regression weichen Datenpunkte mehr oder weniger von der Trendlinie ab, während bei einer Klassifikation Datenpunkte möglicherweise in die falsche Kategorie sortiert werden

zahlenmäßige Vorhersagen der Form „sie wird mit 75 % Wahrscheinlichkeit eine Fischkäuferin sein“ zu treffen.

1.2.3 Bestärkendes Lernen Aufgabe: Leite aus den Mustern in meinen Daten Vorhersagen ab und verbessere diese Vorhersagen, wenn neue Daten eintreffen! Anders als beim unüberwachten oder überwachten Lernen, wo die einmal implementierten Modelle unverändert weiterbenutzt werden, verbessert sich das Modell beim bestärkenden Lernen fortwährend selbst, indem es die erzielten Ergebnisse als Feedback nutzt.

1  Das Wichtigste in Kürze …     11

Hier verlassen wir die doch etwas sehr fingierten Daten aus Tab. 1.1 zugunsten eines realistischeren Beispiels: Stellen Sie sich vor, Sie möchten die Wirksamkeit von zwei Online-Werbebannern vergleichen. Sie könnten dazu zunächst einmal beide Anzeigen gleich häufig einblenden und aufzeichnen, wie oft die beiden Banner jeweils angeklickt werden. Ein Modell mit bestärkendem Lernen würde dann die Zahl der Klicks als Feedback zur Beliebtheit der Werbeanzeige verwenden, sodass in der Folge die beliebtere Anzeige häufiger zu sehen ist. Dieser iterative Prozess führt dann am Ende dazu, dass ausschließlich die bessere Anzeige eingeblendet wird.

1.2.4 Andere Überlegungen Außer in der Aufgabe, für die sie formuliert wurden, unterscheiden sich Algorithmen auch in anderen Aspekten, so in ihrer Fähigkeit, mit verschiedenen Datentypen umzugehen, und in der Form der von ihnen ermittelten Ergebnisse. Diese Fragen werden in den nachfolgenden Kapiteln zu den einzelnen Algorithmen ebenfalls behandelt, Sie finden darüber hinaus weitere Informationen hierzu in Anhang A (für unüberwachtes Lernen) beziehungsweise Anhang B (für überwachtes Lernen).

1.3 Parameter Die zahlreichen Algorithmen in der Data Science führen natürlich zu einer großen Menge an möglichen Modellen – doch auch ein und derselbe Algorithmus kann

12     A. Ng und K. Soo

unterschiedliche Resultate liefern, je nachdem wie seine Parameter eingestellt werden. Parameter sind Optionen, mit denen sich die Einstellungen eines Algorithmus variieren lassen, so wie man bei einem Radio die Frequenz seines Lieblingssenders einstellt. Verschiedene Algorithmen haben unterschiedliche Parameter, an denen sich drehen lässt. Häufig benutzte Parameter der in diesem Buch vorgestellten Algorithmen finden Sie in Anhang C aufgelistet. Es versteht sich von selbst, dass die Leistung eines Modells leidet, wenn seine Parameter nicht richtig eingestellt sind. Schauen Sie sich Abb. 1.2 an. Derselbe Klassifikationsalgorithmus erzeugt ganz unterschiedliche Grenzen zwischen den Gebieten mit orangenen und blauen Punkten, wenn er mit verschiedenen Parametersätzen läuft. In Abb. 1.2a waren die Parameter des Algorithmus so eingestellt, dass er „überempfindlich“ gearbeitet und zufällige Abweichungen als reale Muster fehlinterpretiert hat. Diesen Fehler nennt man Überanpassung (overfit). Ein überangepasstes Modell macht sehr präzise und detaillierte Vorhersagen für die vorliegenden Daten, lässt sich jedoch kaum auf andere Daten übertragen. In Abb.  1.2c wiederum war der Algorithmus zu unempfindlich und hat auch offensichtliche Strukturen in den Daten ignoriert. Dies nennt man dann Unteranpassung (underfit). Ein unterangepasstes Modell vernachlässigt signifikante Trends, was dazu führt, dass man weder für die vorliegenden noch für zukünftige Daten verlässliche Aussagen erhält.

1  Das Wichtigste in Kürze …     13

a) Überanpassung

b) idealer Fit

c) Unteranpassung

Abb. 1.2  Ergebnisse desselben Algorithmus mit unterschiedlichen Parameterwerten

Wenn aber die Parameter gerade richtig eingestellt sind, wie in Abb. 1.2b, hält der Algorithmus gerade die Balance zwischen dem Aufspüren wichtiger Trends und dem Ignorieren von kleineren Schwankungen, wodurch das Modell zu sinnvollen und belastbaren Vorhersagen gelangt. Sehr viele Studien laufen Gefahr, überangepasste Modelle zu verwenden. Im Bestreben, den Vorhersagefehler zu minimieren, sind wir versucht, die Komplexität unseres Vorhersagemodells immer weiter hochzuschrauben, was im Endeffekt zu Resultaten wie in Abb. 1.2a führt – hochdetaillierte Datenbeschreibungen ohne irgendwelche übertragbaren Erkenntnisse! Eine Möglichkeit, die Komplexität eines Modells unter Kontrolle zu halten, ist die Einführung eines sogenannten Strafparameters, man nennt dieses Verfahren auch Regularisierung. Dieser Parameter „bestraft“ jede Verkomplizierung des Modells, indem er dann den Vorhersagefehler künstlich erhöht. Auf diese Weise werden bei der Optimierung der Modellparameter zu komplexe

14     A. Ng und K. Soo

Ansätze ausgeschlossen, wodurch das Modell seine Generalisierbarkeit wahrt.

1.4 Evaluation der Ergebnisse Ist ein Modell fertig implementiert, muss es evaluiert, das heißt bewertet werden. Man verwendet Bewertungsmetriken, um die Präzision von Modellvorhersagen zahlenmäßig zu vergleichen. Diese Metriken unterscheiden sich untereinander darin, wie sie die verschiedenen Typen von Vorhersagefehlern definieren und quantifizieren. Im Folgenden stellen wir Ihnen drei Bewertungsmetriken vor, die oft benutzt werden. Je nach Anlage einer Studie könnte man auch andere, neue Metriken entwerfen, die auf spezielle Arten von Fehlern abzielen. Insofern ist die Aufzählung von Bewertungsmetriken in diesem Buch alles andere als erschöpfend. Einige weitere Beispiele sehen Sie in Anhang D. Klassifikationsmetriken Prozentsatz korrekter Vorhersagen: Die einfachste Definition von Vorhersagegenauigkeit ist der Anteil der Vorhersagen, die sich als korrekt herausgestellt haben. Bei unseren Lebensmitteltransaktionen in Tab. 1.1 könnten wir die Resultate einer Beispielaufgabe wie „Fischkäufer raten“ folgendermaßen ausdrücken: Unser Modell zur Vorhersage, ob ein Kunde Fisch kauft, war in 90 % der Fälle korrekt. Diese Metrik ist einfach zu verstehen, aber sie liefert keine Informationen darüber, wo der Vorhersagefehler herrührt.

1  Das Wichtigste in Kürze …     15

Wahrheitsmatrix (Konfusionsmatrix): Wahrheitsmatrizen zeigen genauer, wo unser Vorhersagemodell erfolgreich war und wo nicht. Werfen wir einen Blick auf Tab. 1.4: Das Modell hatte nach der Klassifikationsmetrik eine Gesamtgenauigkeit von 90 %, doch es konnte die Nicht-Käufe viel besser vorhersagen als die tatsächlich getätigten Käufe. Wir sehen weiterhin, dass der Vorhersagefehler sich zu gleichen Teilen auf falsch positive (FP) und falsch negative (FN) Vorhersagen aufteilte (jeweils fünf Fehler). In manchen Situationen ist es entscheidend, unterschiedlich auf die verschiedenen Arten von Vorhersagefehlern zu reagieren. Eine falsch negative Erdbebenwarnung (das heißt, ein Erdbeben tritt auf, ohne dass davor gewarnt worden wäre) wäre viel schlimmer als eine falsch positive (also ein falscher Alarm – eine Erdbebenwarnung ohne Erdbeben).

1.4.1 Regressionsmetrik Quadratisches Mittel (RMS, root mean square): Da Regressionsanalysen mit stetigen Werten arbeiten, werden Vorhersagefehler hier im Allgemeinen als Differenzen zwischen vorhergesagten und tatsächlichen Werten berechnet. Tab. 1.4  Wahrheitsmatrix für die Beispielaufgabe „Fischkäufer raten“

Tatsächlich gekauft Nicht gekauft

Vorhersage Wird kaufen

Wird nicht kaufen

1 (RP) 5 (FP)

5 (FN) 89 (RN)

16     A. Ng und K. Soo

Die genauen Werte der Straffunktion hängen direkt von der Größe des Fehlers ab. Eine häufig verwendete Regressionsmetrik ist die quadratisch gemittelte Abweichung (RMSE, root mean squared error ). Sie ist besonders nützlich, wenn wir in erster Linie zu große Fehler vermeiden wollen: Jede einzelne Differenz zwischen Vorhersage und Realität wird quadriert, wodurch große Fehler ein größeres Gewicht bekommen. Dies macht die RMSE-Metrik sehr empfindlich auf Ausreißer.

1.4.2 Validierung Metriken sind nicht alles. Ein überangepasstes (siehe Abschn. 1.3) Modell erzielt beispielsweise bei einer bestimmten Metrik gute Werte für die vorliegenden Daten, bei anderen Daten würde es jedoch viel schlechter abschneiden. Um dies zu vermeiden, sollten wir Modelle immer anhand eines angemessenen Validierungsverfahrens beurteilen. Validierung bedeutet die Prüfung der Genauigkeit, mit der ein Modell Vorhersagen für neue Daten generiert. Anstatt allerdings geduldig auf das Eintreffen neuer Daten zu warten, können wir auch den uns vorliegenden Datensatz in zwei Hälften aufteilen. Die eine verwenden wir als sogenannte Trainingsdaten, um ein Vorhersagemodell zu erstellen und zu optimieren, und die andere als Testdatensatz zur Abschätzung der Vorhersagegenauigkeit dieses Modells. Das beste Modell ist dann dasjenige, das die genauesten Vorhersagen für den Testdatensatz macht. Damit dieser Validierungsprozess effektiv abläuft, müssen

1  Das Wichtigste in Kürze …     17

wir die Datenpunkte zufällig und ohne systematische Abweichungen in Trainings- und Testdaten aufteilen. Ist allerdings der originale Datensatz zu klein, haben wir möglicherweise nicht genügend Datenpunkte, um einen Testdatensatz abzutrennen, denn wir verlieren dann zu viel Vorhersagegenauigkeit aufgrund des dann noch kleineren Trainingsdatensatzes. In diesem Fall verwendet man denselben Datensatz für Training und Test, man spricht dann von Kreuzvalidierung. Eine Kreuzvalidierung maximiert die Zahl der für die Validierung verfügbaren Datenpunkte, indem der Datensatz in verschiedene Segmente aufgeteilt wird, mit denen das Modell wiederholt getestet wird. In einem einzelnen Iterationsschritt dienen alle Segmente bis auf eines als Trainingsdatensatz für ein Modell, dessen Ergebnisse dann auf diesem letzten Segment getestet werden. Dieses Verfahren wird so lange mit immer anderen Segmenten wiederholt, bis jedes Segment genau einmal als Testdatensatz an der Reihe war (siehe Abb. 1.3). Da in jeder Iteration ein etwas anderer Trainingsdatensatz und ein anderes Testsegment verwendet werden, erhält man jedes Mal etwas andere Vorhersagen. Indem wir diese Abweichungen berücksichtigen, können wir eine robustere Abschätzung der tatsächlichen Vorhersagekraft eines Modells erhalten. Die letztlich zugewiesene Vorhersagegenauigkeit ist der Mittelwert der Testergebnisse über alle Iterationen. Wenn die Kreuzvalidierung eine zu niedrige Vorhersagegenauigkeit unseres Modells ergibt, sollten wir entweder unsere Modellparameter neu anpassen oder die Daten neu aufbereiten – oder beides …

18     A. Ng und K. Soo Segmente

Test

Training

Training

Training

Resultat 1

Training

Test

Training

Training

Resultat 2

Training

Training

Test

Training

Resultat 3

Training

Training

Training

Test

Resultat 4

Abb. 1.3  Kreuzvalidierung eines Datensatzes. Der Datensatz wird in vier Segmente geteilt, die jeweils als Testdatensatz dienen. Die zugewiesene Vorhersagegenauigkeit ist der Mittelwert der erhaltenen vier Resultate

1.5 Zusammenfassung Eine Data-Science-Studie besteht aus vier Schritten: 1. Datenaufbereitung, 2. Wahl des Algorithmus zur Modellierung der Daten, 3. Abstimmung der Modellparameter für den gewählten Algorithmus, 4. Evaluierung und Validierung der Modelle anhand ihrer Vorhersagegenauigkeit.

2 k-Means-Clustering

2.1 Wie man Kunden-Cluster findet Lassen Sie uns über Filme reden. Vielleicht haben Sie eine Freundin, die 50 erste Dates geliebt hat – dann ist es ziemlich wahrscheinlich, dass sie auch andere Schnulzen wie 27 Dresses gern sieht. So funktioniert Clustering: Man ermittelt gemeinsame Vorlieben oder Eigenschaften von Personen und teilt diese dann in Gruppen, die man zum Beispiel mit auf sie zugeschnittenen Werbekampagnen anspricht. Es kann aber ziemlich knifflig sein, relevante Kundengruppen zu bilden. Zunächst einmal wissen wir weder, wie die Kunden eingeteilt werden sollten, noch wie viele Gruppen es überhaupt gibt.

© Springer-Verlag GmbH Deutschland, ein Teil von Springer Nature 2018 A. Ng und K. Soo, Data Science – was ist das eigentlich?!, https://doi.org/10.1007/978-3-662-56776-0_2

19

20     A. Ng und K. Soo

Ein Verfahren namens k-Means-Clustering könnte diese Fragen beantworten. Es teilt Kunden oder Produkte (oder welche Daten auch immer) in Cluster genannte Gruppen, wobei k die Zahl dieser Cluster angibt.

2.2 Beispiel: Persönlichkeitsprofile von Filmfans Um Kunden mittels k-Means-Clustering in Gruppen einzuteilen, brauchen wir quantifizierbare Informationen über die Kunden. Eine oft benutzte Variable ist das Einkommen, da Gruppen mit höherem Einkommen eher Markenprodukte erwerben als solche mit niedrigerem Einkommen. Kaufhäuser können diese Information dazu nutzen, per Direktmarketing ihre hochpreisigen Artikel gezielt den Gruppen mit prall gefülltem Konto anzubieten. Persönlichkeitszüge sind auch eine gute Möglichkeit, um Kunden zu gruppieren – wie zum Beispiel in der folgenden Untersuchung von Facebook-Nutzern. Die User wurden gebeten, in einem Fragebogen anzugeben, wie sehr sie die folgenden vier Persönlichkeitszüge aufweisen: extrovertiert (wie sehr mögen sie soziale Interaktionen), gewissenhaft (wie hart arbeiten sie), emotional (wie oft fühlen sie sich gestresst) und offen (wie aufgeschlossen sind sie Neuerungen gegenüber). Eine erste Analyse ergab positive Assoziationen zwischen diesen Persönlichkeitszügen. Sehr gewissenhafte Menschen waren eher extrovertiert, sehr emotionale Menschen tendenziell offener. Darum haben wir einerseits Gewissenhaftigkeit mit Extrovertiertheit gepaart und

2  k-Means-Clustering     21

andererseits Emotionalität mit Offenheit. Anschließend haben wir die Werte jeweils aggregiert und schließlich die Daten in einem zweidimensionalen Plot visualisiert. Die jeweiligen aggregierten Persönlichkeitswerte wurden dann für jede Person gegen die Filme aufgetragen, die er oder sie auf Facebook mit „Gefällt mir“ markiert hatte, wodurch wir die Filmfans in Gruppen mit ausgeprägten Persönlichkeitsprofilen einteilen konnten (siehe Abb. 2.1). In Abb. 2.1 sehen wir im Wesentlichen zwei Cluster: • Rosa: gewissenhafte Extrovertierte, die Actionfilme und romantische Komödien mögen, • Himmelblau: emotionale und offene Menschen, die Avantgarde- und Fantasyfilme schauen. Gewissenhaft und extrovertiert

Die Hochzeits-Crasher Nur mit Dir Selbst ist die Braut 27 Dresses

GoodFellas

50 erste Dates Terminator Karate Kid

Findet Nemo Stolz und Vorurteil Der Herr der Ringe

Avatar The Breakfast Club Die Chroniken von Narnia Harry Potter Zurück in die Zukunft Big Fish Pulp Fiction Scott Pilgrim gegen den Rest der Welt Die Ritter der Kokosnuss

District 9

Abb. 2.1  Persönlichkeitsprofile von Filmfans

Emotional und offen

Salt Der Pate Die Goonies Nie wieder Sex mit der Ex

22     A. Ng und K. Soo

Außerhalb dieser beiden Cluster finden sich in der Bildmitte diejenigen Blockbuster, welche die ganze Familie beziehungsweise jede Zielgruppe ansprechen. Mit solchen Informationen können zielgruppengerechte Anzeigen konzipiert werden. Wenn eine Person 50 erste Dates mag, kann ihr ein Onlineshop-Betreiber ganz einfach einen weiteren Film aus dem rosa Cluster oder sogar spezielle Sonderangebots-„Bundles“ mit fünf solchen Filmen vorschlagen.

2.3 Cluster definieren Wenn wir Cluster definieren wollen, müssen wir zwei Fragen beantworten: Wie viele Cluster gibt es in den Daten? Und was gehört zu welchem Cluster?

2.3.1 Wie viele Cluster haben wir? Dies ist eine subjektive Frage. Während Abb. 2.1 nur zwei Cluster enthält, könnte man die Filme durchaus auch in weitere, kleinere Cluster unterteilen. Beispielsweise finden wir im himmelblauen Cluster Dramen wie Stolz und Vorurteil oder The Breakfast Club ebenso wie die Fantasykomödien Die Ritter der Kokosnuss und Scott Pilgrim gegen den Rest der Welt, die man als Sub-Cluster definieren könnte. Wenn die Zahl der Cluster ansteigt, werden sich die Mitglieder eines Clusters zunehmend ähnlicher, aber benachbarte Cluster sind immer schlechter voneinander zu

2  k-Means-Clustering     23

Variabilität innerhalb der Cluster

unterscheiden. Im Extremfall wäre dann jeder Datenpunkt sein eigener Cluster, woraus sich dann gar nichts mehr ableiten ließe. Ganz offensichtlich müssen wir also einen Mittelweg finden. Die Zahl der Cluster sollte groß genug sein, um aussagekräftige Muster abzuleiten, die bei geschäftlichen Entscheidungen helfen können, aber gleichzeitig so klein bleiben, dass die Cluster sich noch deutlich voneinander unterscheiden lassen. Ein Weg, um eine passende Anzahl von Clustern zu ermitteln, ist der sogenannte Scree-Test (siehe Abb. 2.2). In einem Scree-Test trägt man die Streuung beziehungsweise Variabilität innerhalb der Cluster gegen die Anzahl der Cluster auf, man nennt das dann einen Scree-Plot. Wie Sie in Abb. 2.2 erkennen, fällt die Kurve im ScreePlot nach rechts hin ab, die Variabilität innerhalb der

0

1

2

3

4

5

6

7

8

9

10

Zahl der Cluster

Abb. 2.2  In diesem Scree-Plot finden wir einen Knick bei zwei bis drei Clustern

24     A. Ng und K. Soo

Cluster sinkt also mit deren Anzahl.1 Bei nur einem einzigen Cluster ist die Cluster-Streuung maximal, je mehr Cluster es gibt, desto kleiner und homogener werden diese. Ein Knick2 in der Scree-Plot-Kurve deutet dann darauf hin, dass bei dieser Anzahl die Variabilität innerhalb der Cluster nicht nur schon ein gutes Stück abgefallen ist, sondern auch bei Einführung von noch mehr Sub-­Clustern nicht mehr wesentlich kleiner wird. Insofern ist diese Zahl die optimale Anzahl von Clustern für die gegebenen Daten. In Abb. 2.2 liegt solch ein Knick bei einer Clusterzahl von zwei, was den beiden farblich markierten Film-Clustern in Abb. 2.1 entspricht. Ein weiterer Knick lässt sich mit etwas gutem Willen bei der Clusterzahl drei ausmachen, wir könnten also noch mit einer gewissen Berechtigung die Blockbuster in der Mitte als dritten Cluster aufnehmen. Darüber hinaus würde die Aufnahme weiterer Cluster in unser Modell wenig bringen, da diese dann nur noch schlecht voneinander zu unterscheiden wären. Nachdem wir eine sinnvolle Anzahl von Clustern ermittelt haben, können wir als Nächstes herausfinden, welcher Datenpunkt zu welchem Cluster gehört.

1„Scree“

bedeutet auf Englisch so viel wie „Geröllhalde“; stellen Sie sich vor, die Datenpunkte wären Brocken, die einen nach rechts abfallenden Hang unterschiedlich weit heruntergerutscht sind (Anm. d. Übers.). 2Ein anderer Name für den Scree-Test ist „Ellenbogentest“ – der Knick ist der „Ellenbogen“ zwischen dem „Oberarm“ der Kurve (rasant abfallende Variabilität) und ihrem „Unterarm“ (kaum mehr Änderung der Variabilität) (Anm. d. Übers.).

2  k-Means-Clustering     25

2.3.2 Was gehört in meinen Cluster? Die Zugehörigkeit zu einem Cluster wird in einem iterativen Prozess festgestellt, wie es Abb. 2.3 für ein 2-Cluster-Beispiel illustriert. Da in einem guten Cluster die Datenpunkte möglichst dicht beieinander liegen (und fern von allen anderen),

a) Schri 0

b) Schri 1

c) Schri 2

d) Schri 3

Abb. 2.3  Iterative Datengruppierung beim k-Means-Clustering

26     A. Ng und K. Soo

könnten wir einen Cluster danach beurteilen, wie weit seine Mitglieder vom Mittelpunkt des Clusters entfernt sind. Leider ist dessen Position jedoch anfangs nicht bekannt und muss darum zunächst einmal approximiert beziehungsweise geraten werden. Die Datenpunkte werden dem jeweils nächstgelegenen dieser vorläufigen Clustermittelpunkte zugeordnet. Im nächsten Iterationsschritt berechnet man erst die tatsächlichen Mittelpunkte der zuvor gebildeten Cluster und weist dann die Datenpunkte aufs Neue den Clustern zu, und zwar jetzt nach ihrer Entfernung zu den neu ermittelten Clustermittelpunkten. Es kann jetzt also vorkommen, dass ein Datenpunkt, der zu weit vom neuen Mittelpunkt seines bisherigen Clusters liegt, einem anderen Cluster zugewiesen wird. Die iterative Einteilung des Datensatzes in Cluster verläuft somit über die folgenden Schritte: • Schritt 0: Die (hier zwei) möglichen Clustermittelpunkte werden geraten. Wir nennen sie „vorläufige Mittelpunkte“, da wir noch nicht wissen, wo die tatsächlichen Mittelpunkte am Ende liegen werden. • Schritt 1: Jeder Datenpunkt wird dem nächstgelegenen vorläufigen Mittelpunkt zugeordnet. So erhalten wir zwei Cluster, einen roten und einen blauen. • Schritt 2: Die vorläufigen Clustermittelpunkte werden durch die tatsächlichen Mittelpunkte von rotem und blauem Cluster ersetzt. • Schritt 3: Die Schritte 1 (Datenpunkte zuordnen) und 2 (Mittelpunkte neu berechnen) werden so lange wiederholt, bis es keine Änderungen der Clusterzusammensetzung mehr gibt.

2  k-Means-Clustering     27

Obwohl wir hier nur eine zweidimensionale Analyse vorgeführt haben, ist Clustering ebenso in drei oder mehr Dimensionen möglich. Solche zusätzlichen Dimensionen könnten etwa für einen Ladenbesitzer das Alter seiner Kunden oder die Häufigkeit ihrer Besuche sein. Das ist dann zwar schwierig bis unmöglich zu visualisieren, doch für ein Computerprogramm ist es ein Leichtes, mehrdimensionale Abstände zwischen Datenpunkten und Clustermittelpunkten zu berechnen.

2.4 Grenzen Obwohl k-Means-Clustering sehr nützlich sein kann, hat der Algorithmus auch gewisse Schwächen. Jeder Datenpunkt kann nur zu einem Cluster gehören. Manchmal liegt ein Datenpunkt aber genau in der Mitte zwischen zwei Clustern und wird mit gleicher Wahrscheinlichkeit einem von ihnen zugewiesen. Cluster werden als kreisförmig (beziehungsweise sphärisch in n Dimensionen) angenommen. Die iterative Zuordnung von Datenpunkten zum nächsten Clustermittelpunkt bedeutet eine schrittweise Verringerung des Clusterradius, sodass der resultierende Cluster einer kompakten Kugel (in 2, 3 oder n Dimensionen) entspricht. Dies kann ein Problem darstellen, wenn die tatsächliche Form des Clusters eher einer Ellipse oder einem räumlichen Ellipsoid ähnelt – solche „länglichen“ Cluster werden unter Umständen abgeschnitten und ihre Mitglieder fälschlich den Nachbar-Clustern zugeordnet.

28     A. Ng und K. Soo

Cluster sind so definiert, dass sie sich gegenseitig ausschließen. Beim k-Means-Clustering dürfen sich Cluster weder überschneiden, noch darf ein Cluster in einem anderen enthalten sein. Anstatt dass man jeden Datenpunkt in genau einen Cluster hineinzwingt, kann man auch robustere Clustering-Verfahren einsetzen, welche Wahrscheinlichkeiten dafür berechnen, dass ein Datenpunkt vielleicht auch zu anderen Clustern gehört. Damit lassen sich nicht-sphärische oder überlappende Cluster realisieren. Trotz dieser Einschränkungen liegt die Stärke des k-Means-Clustering-Algorithmus in seiner eleganten Einfachheit. Eine gute Strategie wäre es daher, zunächst mit k-Means-Clustering ein grundlegendes Verständnis der Struktur seiner Daten zu gewinnen und danach den Schwächen des Algorithmus mit komplexeren Methoden abzuhelfen.

2.5 Zusammenfassung • k-Means-Clustering ist eine Methode, mit der sich ähnliche Datenpunkte in Gruppen zusammenfassen lassen. Die Zahl k der Cluster muss dabei vorher festgelegt sein. • Um Datenpunkte zu clustern, weist man erst jeden Datenpunkt einem vorläufigen Clustermittelpunkt zu und korrigiert dann den Clustermittelpunkt anhand der zugewiesenen Punkte. Diese zwei Schritte werden wiederholt, bis es keine Änderungen mehr gibt. • k-Means-Clustering funktioniert am besten bei sphärischen, nicht-überlappenden Clustern.

3 Hauptkomponentenanalyse

3.1 Der Nährwertgehalt von Lebensmitteln Stellen Sie sich vor, Sie sind Ernährungsberater. Wie lassen sich Speisen am besten aufschlüsseln? Nach ihrem Vitamingehalt? Den enthaltenen Proteinen? Oder vielleicht nach einer Kombination von beidem?

© Springer-Verlag GmbH Deutschland, ein Teil von Springer Nature 2018 A. Ng und K. Soo, Data Science – was ist das eigentlich?!, https://doi.org/10.1007/978-3-662-56776-0_3

29

30     A. Ng und K. Soo

Eine einfache Ernährungspyramide

Die Variablen zu kennen, nach denen sich Ihre Objekte am besten systematisieren lassen, hat einige Vorzüge: • Visualisierung: Objekte mit den richtigen Variablen zu plotten, kann Ihnen neue Einsichten vermitteln. • Cluster aufdecken: Mit einer guten Visualisierung treten verborgene Kategorien und Cluster zutage. Bei Lebensmitteln könnten wir zum Beispiel übergeordnete

3 Hauptkomponentenanalyse     31

Kategorien wie Fleisch und Gemüse oder Sub-­Cluster für unterschiedliche Arten von Obst oder Gemüse ­aufdecken. Die Frage ist bloß: Wie sollen wir die Variablen ermitteln, anhand derer wir am besten zwischen unseren Objekten unterscheiden können?

3.2 Hauptkomponenten Die Hauptkomponentenanalyse (PCA, principal component analysis ) ist eine Methode, mit der wir diejenigen zugrundeliegenden Variablen finden (die sogenannten Hauptkom­ ponenten), nach denen wir unsere Datenpunkte am besten aufschlüsseln können. Diese Hauptkomponenten lassen sich als die Dimensionen verstehen, entlang derer unsere Datenpunkte am weitesten verteilt sind (siehe Abb. 3.1). Eine Hauptkomponente kann durch eine oder mehrere Variablen ausgedrückt werden. Angenommen, wir benutzen nur die eine Variable Vitamin-C-Gehalt, um zwischen unseren Nahrungsmitteln zu unterscheiden. Da sich Vitamin C in Gemüse befindet, aber kaum in Fleisch, können wir damit das Gemüse vom Fleisch unterscheiden (linke Spalte in Abb. 3.2). Die Fleischprodukte lassen sich so aber unter sich nicht weiter ausdifferenzieren, sie „klumpen“ vielmehr zusammen.

32     A. Ng und K. Soo

p

au

H ste er

e nt ne o p m tko

m ko pt au eH eit zw ne po e nt Abb. 3.1  Visualisierung von Hauptkomponenten: Entlang der ersten Hauptkomponente ist der Datensatz am stärksten aufgefächert

Um die Einträge der Fleischprodukte auseinanderzuziehen, können wir den Fettgehalt als sekundäre Variable nutzen, denn praktisch jedes Stück Fleisch enthält Fett, während in Gemüse kaum Fett zu finden ist. Da Fett und Vitamin C jedoch in unterschiedlichen Einheiten gemessen werden, müssen wir die Werte zunächst standardisieren, bevor wir sie zusammenführen können. Standardisierung bedeutet, dass wir jede Variable in Form von Perzentilen angeben, wodurch die Variablen auf eine einheitliche, dimensionslose Standardskala transformiert werden. Anschließend lassen sie sich zu einer kombinierten neuen Variable verrechnen: Neue Variable: Vitamin C – Fett

3 Hauptkomponentenanalyse     33

Da der Vitamin-C-Gehalt die Gemüseverteilung nach oben auseinanderzieht, ziehen wir den Fettgehalt ab (Minuszeichen), damit die fetthaltigsten Fleischprodukte nach unten wandern (mittlere Spalte in Abb. 3.2).

Petersilie Petersilie Grünkohl Brokkoli

Blumenkohl Sojabohnen Süßkartoffeln Perlhuhn

(Vitamin C) – Fett

Vitamin C

Brokkoli Blumenkohl Weißkohl Spinat Süßkartoffeln Perlhuhn Blaubarsch Makrele Hühnerfleisch Rindfleisch

Erbsen Lotosblumenwurzel

(Vitamin C und Ballaststoffe) – Fett

Petersilie Grünkohl

Schnittlauch Blumenkohl Sojabohnen Aubergine Zuckermais Pilze Schellfisch Perlhuhn Blaubarsch Makrele Hühnerfleisch Rindfleisch

Schweinefleisch Lammfleisch Schweinefleisch Lammfleisch

Abb. 3.2  Nahrungsmittel sortiert nach verschiedenen Kombinationen von Variablen

34     A. Ng und K. Soo

Die Aufschlüsselung der Daten lässt sich noch verbessern, wenn wir den Gehalt an Ballaststoffen hinzunehmen, der bei Gemüsen recht unterschiedlich sein kann: Weitere neue Variable: (Vitamin C + Ballaststoffe) – Fett Diese zweite neue Variable verteilt die Daten am besten entlang der vertikalen Achse (rechte Spalte in Abb. 3.2). Während wir in diesem Beispiel die Hauptkomponenten im Wesentlichen durch Ausprobieren bestimmt haben, geht dies mit PCA auf ganz systematische Weise. Wie das abläuft, zeigt das folgende Beispiel.

3.3 Beispiel: Nahrungsmittelgruppen Mithilfe von offenen Daten des US-Landwirtschaftsministeriums haben wir die Nährstoffgehalte einer zufälligen Auswahl von Lebensmitteln untersucht, wobei wir vier ernährungswissenschaftliche Variablen betrachtet haben, nämlich die Gehalte an Fett, Eiweiß (Proteinen), Ballaststoffen und Vitamin C. Wie Abb. 3.3 zeigt, neigen bestimmte Nährstoffe dazu, gemeinsam in Lebensmitteln aufzutreten. Insbesondere tendieren Fett und Eiweiß einerseits beide in dieselbe Richtung und andererseits in die entgegengesetzte Richtung wie Ballaststoff- und VitaminC-Gehalte. Um diese erste Beobachtung zu bestätigen, können wir prüfen, ob die Nährwert-Variablen korreliert sind (siehe Abschn. 6.5). Tatsächlich würden wir eine signifikant positive Korrelation zwischen Fett- und

3 Hauptkomponentenanalyse     35

Lammfleisch

Schweinefleisch

Grünkohl

Petersilie Fe

Eiweiß Ballaststoffe Vitamin C

Abb. 3.3  Vergleich der Nährstoffgehalte verschiedener Lebensmittel

Eiweißgehalt finden (r = 0,56), ebenso wie zwischen Ballaststoffen und Vitamin C (r = 0,57). Aus diesem Grund können wir, anstelle die vier Variablen separat zu betrachten, die korrelierten Variablen jeweils kombinieren, woraufhin wir nur noch zwei ­Dimensionen zu untersuchen haben. Deswegen wird die PCA auch als eine dimensionsreduzierende Methode oder kurz Dimensionsreduktion bezeichnet.

36     A. Ng und K. Soo

HK1

HK2

HK3 0,58

HK4 0,18

Fett

– 0,45 0,66

Eiweiß

– 0,55 0,21

– 0,46 – 0,67

Ballaststoffe

0,55 0,19

0,43 – 0,69

Vitamin C

0,44 0,70

– 0,52

0,22

Abb. 3.4  Hauptkomponenten als optimal gewichtete Kombinationen von Nährwert-Variablen. Grau hinterlegte Zellen innerhalb derselben Hauptkomponente stehen für Variablen, die in dieselbe Richtung gewichtet sind

Wenden wir die PCA auf unseren Nahrungsmittel-Datensatz an, erhalten wir die Hauptkomponenten in Abb. 3.4. Jede Hauptkomponente ist eine gewichtete Kombination der vier Nährwert-Variablen, wobei die Gewichte positiv, negativ oder (ungefähr) null sein können. Zum Beispiel würden wir den Wert der ersten Hauptkomponente (HK1) für ein bestimmtes Lebensmittel erhalten, indem wir den folgenden einfachen Ausdruck berechnen: 0,55 · (Ballaststoffe) + 0,44 · (Vitamin C) – 0,45 · (Fett) – 0,55 · (Eiweiß)

3 Hauptkomponentenanalyse     37

Anstatt dass wir unsere Variablen per Trial-and-Error zusammenwurschteln wie im letzten Abschnitt, berechnet die PCA also exakte Gewichte, mit deren Hilfe die Variablen so kombiniert werden können, dass die gegebenen Daten optimal aufgeschlüsselt werden. Beachten Sie, dass die wichtigste Hauptkomponente (HK1) unser bisheriges Ergebnis – Fett ist mit Eiweiß gepaart, Ballaststoffe mit Vitamin C – widerspiegelt, auch sind die beiden Paare in der Tat gegenläufig verknüpft. Während HK1 Fleisch und Gemüse voneinander unterscheidet, zeigt die zweite Hauptkomponente (HK2) Sub-Kategorien innerhalb der Cluster Fleisch (nach Fettgehalt) und Gemüse (nach Vitamin-C-Anteil). Tragen wir nun für unsere Lebensmittel HK2 gegen HK1 auf, erreichen wir die bisher beste Aufspaltung der Datenpunkte (Abb. 3.5). Fleischprodukte (blaue Schrift) haben niedrige HK1Werte und sind daher auf der linken Seite der Abbildung zu finden, Gemüse entsprechend auf der rechten Seite (hohe HK1-Werte, orangene Schrift). Wir sehen auch, dass unter den Fleischprodukten Fisch und Meeresfrüchte (dunkelblau) weniger Fett enthalten und somit geringere HK2-Werte haben – sie sammeln sich somit in der unteren linken Ecke des Plots an. In ähnlicher Weise haben die Gemüsesorten, die nicht zum Blattgemüse zählen (dunkelorange) weniger Vitamin C als Blattgemüse und daher auch niedrigere HK2-Werte. Sie konzentrieren sich überwiegend unten rechts.

38     A. Ng und K. Soo Petersilie

Lammfleisch

Grünkohl

zweite Hauptkomponente (HK2)

Schweinefleisch

Rosenkohl Brokkoli

Sojabohnen Rindfleisch

Schnittlauch

Huhn Makrele

Blumenkohl Weißkohl

Blaubarsch Truthahn

Knoblauch

Perlhuhn

Tintenfisch Schellfisch

Erbsen

Spinat Auster

Süßkartoffel

Karotten Spargel Pilze Sellerie

erste Hauptkomponente (HK1)

Abb. 3.5  Nach den ersten zwei Hauptkomponenten aufge­ schlüsselte Lebensmittel

Die richtige Anzahl von Komponenten wählen:  Unser obiges Beispiel hatte vier Hauptkomponenten erzeugt, entsprechend den ursprünglich vier Variablen des Datensatzes. Da die Hauptkomponenten aus den bestehen Variablen abgeleitet werden, ist die zum Aufschlüsseln der Daten verfügbare Information auf diese vier Originalvariablen beschränkt.

3 Hauptkomponentenanalyse     39

Um die Ergebnisse jedoch einfach und übertragbar zu halten, sollten wir nur die ersten zwei Hauptkomponenten für Visualisierung und weitere Analyse auswählen. Die Hauptkomponenten sind angeordnet nach ihrer Fähigkeit, die Datenpunkte voneinander zu unterscheiden, wobei die erste Hauptkomponente dies am besten bewerkstelligt. Wie viele Hauptkomponenten wir letztlich verwenden sollten, zeigt auch wieder ein Scree-Test, wie wir ihn in Abschn. 2.3 kennengelernt haben. Der Scree-Plot zeigt die abnehmende Wirksamkeit der vier Hauptkomponenten (siehe Abb. 3.6). Gemäß der Faustregel aus Abschn. 2.3 weist der Knick in der Kurve dieses Plots auf die sinnvolle Zahl der Komponenten hin. In diesem Fall wären das also zwei. Wir würden zwar mit drei oder mehr Hauptkomponenten die Datenpunkte noch detaillierter auseinanderdröseln, diese zusätzliche

prozentualer Beitrag zur Aufschlüsselung der Daten

50 40 30 20 10

1

2

3

4

Anzahl der Komponenten

Abb. 3.6  Der Scree-Plot hat seinen Knick bei der 2 – wir sollten uns auf zwei Hauptkomponenten beschränken

40     A. Ng und K. Soo

Information dürfte aber die höhere Komplexität der Lösung nicht rechtfertigen. Wie wir in der Grafik sehen, liefern die ersten beiden Hauptkomponenten bereits rund 70 % der Datenvariabilität. Indem wir uns auf nur zwei Hauptkomponenten beschränken, stellen wir außerdem sicher, dass wir diese Komponenten auch auf zukünftige Datensätze verallgemeinern können.

3.4 Grenzen PCA ist hilfreich, wenn es darum geht, Datensätze mit vielen Variablen zu untersuchen. Nichtsdestotrotz hat die Methode auch Nachteile. Maximale Variabilität:  PCA macht die wichtige Annahme, dass die Dimensionen mit der größten Variabilität der Datenpunkte auch die aussagekräftigsten sind. Dies muss jedoch nicht immer der Fall sein. Ein einfaches Gegenbeispiel ist der Pfannkuchenstapel in Abb. 3.7.

Höhe des Stapels

Durchmesser der Pfannkuchen

Abb. 3.7  Ein Pfannkuchenstapel, mit dem die PCA ihre Schwie­ rigkeiten hätte

3 Hauptkomponentenanalyse     41

Um die Zahl der Pfannkuchen zu zählen, unterscheiden wir die einzelnen Pfannkuchen entlang der vertikalen Achse (das heißt mit der Variable Stapelhöhe). Wenn der Stapel allerdings niedrig ist, würde PCA fälschlich die horizontale Achse (Variable Pfannkuchendurchmesser) als beste Hauptkomponente auswählen, da in dieser Dimension die Streuung der Werte am größten ist. Interpretation der Komponenten:  Eine wesentliche Her­ ausforderung beim Arbeiten mit PCA ist die Interpretation der aus den Daten gezogenen Komponenten. Manchmal müssen wir uns regelrecht mühen zu erklären, warum die Variablen gerade in der vom Verfahren bestimmten Weise kombiniert werden sollen. Hier könnte uns allerdings unser Vorwissen helfen. Im Fall der verschiedenen Lebensmittel erlaubt uns unsere Kenntnis der wichtigsten Nahrungsmittelkategorien zu verstehen, warum die Nährwert-Variablen gerade in dieser Weise zu den Hauptkomponenten zusammengefasst wurden. Orthogonale Komponenten:  PCA erzeugt immer orthogonale Hauptkomponenten, was bedeutet, dass Komponenten jeweils senkrecht aufeinander stehen. Diese Annahme ist aber nicht immer gerechtfertigt, da Informationsdimensionen nicht zwangsläufig orthogonal sein müssen. Dies kann man berücksichtigen, wenn man mit einer alternativen Methode namens Unabhängigkeitsanalyse arbeitet (ICA, independent component analysis ). ICA lässt nicht-orthogonale Komponenten zu, die in ihnen enthaltene Informationen dürfen sich jedoch nicht

42     A. Ng und K. Soo

a) mit PCA ermielte Komponente

b) mit ICA besmmte Komponenten

Abb. 3.8  Vergleich zwischen PCA und ICA

überlappen (siehe Abb. 3.8). Dies führt dazu, dass jede unabhängige Komponente eine andere Information über den Datensatz in sich trägt. ICA kommt außerdem nicht nur ohne zwangsweise orthogonale Komponenten aus, sondern verlässt sich auch nicht ausschließlich auf die Streuung der Daten bei der Bestimmung seiner Komponenten, wodurch die Methode weniger anfällig für den Pfannkuchenfehler ist. Doch obwohl ICA überlegen erscheint, bleibt PCA eine der am meisten eingesetzten Techniken zur Dimensionsreduktion, und es ist immer nützlich zu wissen, wie so etwas funktioniert. Im Zweifelsfall könnten Sie immer noch nachträglich eine ICA über ihre Daten laufen lassen, um die Ergebnisse einer PCA zu verifizieren.

3 Hauptkomponentenanalyse     43

3.5 Zusammenfassung • Die Hauptkomponentenanalyse (PCA) ist eine Methode zur Dimensionsreduktion, da sie es erlaubt, die vorliegenden Daten mit einem kleineren Satz von Variablen zu beschreiben, welche Hauptkomponenten genannt werden. • Jede Hauptkomponente ist eine gewichtete Summe der ursprünglichen Variablen. Mit den wichtigsten Hauptkomponenten kann man sowohl die Analyse als auch die Visualisierung der Daten verbessern. • PCA funktioniert am besten, wenn die aussagekräftigsten Dimensionen die größte Streuung in den Daten haben und außerdem orthogonal auf allen anderen stehen.

4 Assoziationsanalyse

4.1 Muster im Einkaufsverkaufsverhalten Wenn Sie einkaufen gehen, haben Sie vermutlich eine Liste dabei, auf der steht, was Sie so alles benötigen – entsprechend Ihren Bedürfnissen und Vorlieben. Modernen Haushalte bevorzugen vielleicht eher gesunde Zutaten für das Essen der Familie, während Studenten sich möglicherweise lieber mit Bier und Chips versorgen. Solche Muster zu erkennen, kann die Verkaufszahlen in mehrerlei Hinsicht steigern. Wenn zum Beispiel zwei Artikel X und Y oft zusammen gekauft werden, bietet es sich an,

© Springer-Verlag GmbH Deutschland, ein Teil von Springer Nature 2018 A. Ng und K. Soo, Data Science – was ist das eigentlich?!, https://doi.org/10.1007/978-3-662-56776-0_4

45

46     A. Ng und K. Soo

• Werbeanzeigen für X auf Käufer von Y zuzuschneiden, • X und Y in demselben Regal zu platzieren, sodass der Kauf des einen Produkts zum Kauf des anderen anregt, oder • X und Y zu einem neuen Produkt zu kombinieren, etwa „X mit Y-Geschmack“. Um aufzudecken, wie Objekte mit anderen assoziiert sind, können wir uns der Assoziationsanalyse bedienen. Außer der Umsatzsteigerung im Einzelhandel gibt es noch viele andere Anwendungen dieser Methode, beispielsweise erlauben oft gemeinsam auftretende, sogenannte komorbide Symptome eine verbesserte Diagnose und Betreuung von Patienten.

4.2 Support, Konfidenz und Lift Es gibt drei gebräuchliche Maße, mit denen sich Assoziationen quantifizieren lassen. Maß 1 – Support:  Dieses Maß gibt an, wie häufig eine Menge von Objekten auftritt, gemessen als der Anteil aller Transaktionen, an welchen diese Menge beteiligt ist. In der Tabelle in Abb. 4.1 erscheint die einelementige Menge { } in vier von acht Transaktionen, also hat diese Menge den Support 4/8 = 50  % (Abb.  4.2). Wenn die Menge von Objekten mehr als ein Element enthält, geht man ganz } zwei von analog vor – so ist der Support von { acht, also 25 %. Mit einem Schwellenwert für den Support kann man häufige Objektmengen von seltenen unterscheiden. Mengen mit Supportwerten über diesem Schwellenwert gelten als häufig.

4 Assoziationsanalyse     47

Abb. 4.1  Beispieltransaktion

Support { } =

4 8

Abb. 4.2  Support als Maß

Maß 2 – Konfidenz:  Dieses Maß gibt an, wie häufig Artikel Y auftritt, wenn Artikel X vorliegt, man schreibt dies als {X → Y}. Berechnet wird die Konfidenz als das Verhältnis der Zahl an Transaktionen mit dem Artikel X, bei denen auch Y erscheint, zur Zahl aller Transaktionen mit X (Abb. 4.3). Mit den Werten aus Abb. 4.1 erhalten } drei von vier, das heißt wir als Konfidenz von { 75 %.

48     A. Ng und K. Soo

Konfidenz {

}=

Support { , } Support { }

Abb. 4.3  Konfidenz als Maß

Li {

}=

Support { , } Support { } x Support { }

Abb. 4.4  Lift als Maß

Ein Nachteil dieses Maßes ist, dass es die Bedeutung einer Assoziation unter Umständen falsch wiedergibt. Das Beispiel in Abb. 4.3 vergleicht die gemeinsamen Apfel-BierTransaktionen nur mit den Apfel-Käufen, berücksichtigt aber keinerlei Informationen über den Bierabsatz. Wenn Bier nämlich ganz allgemein sehr gern gekauft wird, was in Abb. 4.1 der Fall zu sein scheint, dann ist es offensichtlich, dass eine Transaktion mit Äpfeln auch Bier enthält, einfach weil Bier mehr oder weniger immer mit dabei ist. Dadurch wird das Konfidenzmaß künstlich aufgebläht. Wir könnten jedoch auch beide Einzelhäufigkeiten berücksichtigen, und zwar indem wir das folgende, dritte Maß verwenden. Maß 3 – Lift:  Dieses Maß gibt an, wie häufig die Artikel X und Y gemeinsam auftreten, und berücksichtigt dabei beide Einzelhäufigkeiten. } definiert als die KonDemzufolge ist der Lift von { } geteilt durch die Häufigkeit (den Supfidenz von { port) von { } (Abb. 4.4). } Mit den Werten aus Abb. 4.1 beträgt der Lift von { gerade eins. Dies lässt darauf schließen, dass die beiden Artikel nicht assoziiert sind. Ist der Lift größer als eins, ist es

4 Assoziationsanalyse     49

wahrscheinlich, dass Y gekauft wird, wenn auch X gekauft wird. Bei einem Lift kleiner als 1 ist es unwahrscheinlich, dass Y gekauft wird, wenn auch X gekauft wird.

4.3 Beispiel: Daten aus einem Lebensmittelgeschäft Um zu zeigen, wie man mit den Assoziationsmaßen umgeht, analysieren wir Daten, die in einem Lebensmittelgeschäft über 30 Tage aufgezeichnet wurden. Abb. 4.5 zeigt Assoziationen zwischen Paaren von Artikeln, bei denen die Mayonnaise Scheuermittel

Gewürze

Aperitifs Kräuter Zwiebeln

Aufschnitt Brötchen Scheibenkäse

Herrenkosmetik

anderes Gemüse

Suppen Wasserflaschen

Käsespezialitäten

Streichwurst

Putenfleisch Käsebruch („Curd“)

Joghurt

Weichkäse Müsli

Bierdosen

Reis

Vollmilch

Trauben Tropenfrüchte

Kernobst Tee Dosengemüse

Abb. 4.5  Assoziationsgraph von Lebensmitteln

Schmelzkäse

50     A. Ng und K. Soo

Konfidenz größer als 0,9 % ist und der Lift mehr als 2,3 beträgt. Große Kreise bedeuten großen Support, während rote Kreise für hohe Liftwerte stehen. Wir können hier verschiedene Muster im Einkaufsverhalten beobachten: • Die häufigsten Transaktionen waren solche mit Kernobst und Tropenfrüchten. • Ebenfalls häufig waren Zwiebeln und Gemüse. • Wer Aufschnitt gekauft hat, hat oft auch Scheibenkäse erworben. • Man hat vermutlich auch Tropenfrüchte gekauft, wenn Tee auf dem Einkaufszettel gestanden hatte. Wir erinnern daran, dass das Konfidenzmaß den Nachteil hat, dass es die Wichtigkeit einer Assoziation manchmal falsch wiedergibt. Um dies noch einmal zu verdeutlichen, sehen Sie in Tab. 4.1 drei Assoziationsregeln mit dem Artikel Bier. Die Assoziationsregel {Bier → Mineralwasser} hatte die höchste Konfidenz mit 17,8 %. Doch sowohl Bier als auch Mineralwasser kamen in allen Transaktionen häufig vor (siehe Tab. 4.2), also könnte ihre Assoziation auch einfach ein Zufall sein. Dieser Verdacht bestätigt sich, wenn Tab. 4.1  Assoziationsmaße für drei Assoziationsregeln mit dem Artikel Bier Transaktion

Support (%)

Konfidenz (%)

Lift

Bier → Mineralwasser Bier → Beerenobst Bier → Herrenkosmetik

1,38 0,08 0,09

17,8 1,0 1,2

1,0 0,3 2,6

4 Assoziationsanalyse     51 Tab. 4.2  Supportwerte für die einzelnen Artikel in den drei Bier-Assoziationsregeln Transaktion Bier Mineralwasser Beerenobst Herrenkosmetik

Support (%) 7,77 17,44 3,32 0,46

wir den zugehörigen Liftwert ansehen, der genau bei 1,0 liegt, was zeigt, dass in Wirklichkeit gar keine Assoziation zwischen den Käufen von Bier und Mineralwasser besteht. Auf der anderen Seite hatte die Assoziationsregel {Bier → Herrenkosmetik} zwar eine niedrige Konfidenz, doch lag dies daran, dass Herrenkosmetik ganz generell nur selten nachgefragt wurde. Nichtsdestotrotz war es tatsächlich besonders wahrscheinlich, dass sich einer der wenigen Käufer von Herrenkosmetik dazu auch ein paar Bier gegönnt hat, denn der Lift lag hier bei dem hohen Wert von 2,6. Das Gegenteil war richtig für {Bier → Beerenobst}: Der Lift von nur 0,3 liegt hier deutlich unter eins, daraus können wir schließen, dass Bierkäufer sich wahrscheinlich nicht viel aus gesunden Beeren gemacht haben. Während es leicht ist, die Häufigkeit von einzelnen Artikelmengen zu bestimmen, ist es wesentlich schwieriger – für den typischen Ladenbesitzer jedoch auch viel interessanter –, eine komplette Liste der beliebtesten Kombinationen von gekauften Artikeln zu bekommen. Hierfür müssen wir den Supportwert von allen denkbaren Mengen von Artikeln

52     A. Ng und K. Soo

berechnen, bevor wir daraus die interessanten Punkte mit einem Support oberhalb eines sinnvoll gewählten Schwellenwerts herausfiltern können. In einem Geschäft, das bloß zehn Artikel verkauft, wuppt sich die Gesamtzahl der möglichen Kombinatio­ nen bereits auf stolze 1023 (210 − 1), und diese Zahl wächst exponentiell weiter, je mehr Artikel ins Sortiment aufgenommen werden. Ganz offensichtlich brauchen wir einen effizienteren Ansatz.

4.4 Das A-priori-Prinzip Eine Möglichkeit, die Zahl der zu berücksichtigenden Artikelkombinationen zu reduzieren, bietet das sogenannte A-priori-Prinzip. Einfach ausgedrückt besagt das A-priori-Prinzip, dass wenn eine Kombination von Artikeln selten vorkommt, alle größeren Mengen von Artikeln, in denen diese Kombination enthalten ist, ebenfalls selten sein müssen. Wenn also {Bier} einmal selten nachgefragt sein sollte, dann muss dies auch für {Bier, Pizza}, {Bier, Wimperntusche} und so weiter gelten. Beim Aufstellen unserer Liste der häufigsten Artikelkombinationen können wir in diesem Fall also {Bier, Pizza}, {Bier, Wimperntusche} und überhaupt alle Kombinationen, in denen Bier vorkommt, ignorieren.

4 Assoziationsanalyse     53

4.4.1 Mengen von Artikeln finden, die hohen Support haben Mit dem A-priori-Prinzip stellen wir die Liste der häufigsten Artikelkombinationen folgendermaßen zusammen: • Schritt 0: Starte mit Mengen von Artikeln, die nur ein Element enthalten, etwa {Apfel} oder {Birne}. • Schritt 1: Bestimme den Support für alle diese Einzelartikel. Behalte diejenigen, deren Support über dem gewählten Schwellenwert liegt, und wirf alle anderen raus. • Schritt 2: Nimm einen weiteren Artikel zur Menge deiner Kandidaten hinzu (zum Beispiel {Vollkornbrot}) und erzeuge alle Konfigurationen mit diesem Artikel und denjenigen, die im vorigen Schritt nicht rausgeworfen worden sind. • Schritt 3: Wiederhole die Schritte 1 und 2 und bestimme so den Support für immer größere Artikelkombinationen, bis es keine neuen Kombinationen mehr zu untersuchen gibt. Abb. 4.6 zeigt, wie sich das Gestrüpp der Kandidatenkombinationen mithilfe des A-priori-Prinzips erkennbar lichten lässt. Wenn zum Beispiel {Apfel} einen niedrigen Supportwert hatte, können alle Kandidaten, in denen ein Apfel vorkommt, aussortiert werden, wodurch sich die Zahl der zu untersuchenden Fälle mit einem Schritt mehr als halbiert.

54     A. Ng und K. Soo

Abb. 4.6  Das A-priori-Prinzip: Artikelkombinationen innerhalb der rot gestrichelten Linie können aussortiert werden

4.4.2 Assoziationsregeln mit hoher Konfidenz oder hohem Lift Außer um Artikelkombinationen mit hohem Support zu finden, kann man das A-priori-Prinzip auch einsetzen, um Assoziationen mit hoher Konfidenz oder hohem Lift zu ermitteln. Dies ist nicht mehr ganz so rechenaufwendig, wenn die Kombinationen mit hohem Support bereits gefunden sind, da Konfidenz und Lift aus den Supportwerten berechnet werden. Angenommen, wir wollen Assoziationsregeln mit hoher Konfidenz finden. Wenn die Regel {Bier, Chips → Apfel}

4 Assoziationsanalyse     55

eine niedrige Konfidenz hatte, gilt dies auch für alle anderen Regeln mit denselben Artikeln, bei denen Apfel auf der rechten Seite auftaucht, zum Beispiel {Bier → Apfel, Chips} und {Chips → Apfel, Bier}. Wie zuvor werden diese niederwertigen Regeln aussortiert, sodass weniger zu untersuchende Kandidaten im Rennen bleiben.

4.5 Grenzen Rechenaufwand:  Auch wenn das A-priori-Prinzip die Zahl der Kandidaten erheblich einschränkt, kann diese Zahl immer noch unangenehm hoch sein, wenn das Inventar groß ist oder die Schwellenwerte niedrig gewählt sind beziehungsweise sein müssen. Eine Alternative wäre es, die Anzahl der Vergleiche dadurch zu reduzieren, dass man mithilfe ausgeklügelter Datenstrukturen die Kandidaten effizienter sortiert. Scheinassoziationen:  Assoziationen könnten auch zufällig zustande kommen, wenn man es mit einer großen Zahl von Artikeln zu tun hat. Um sicherzustellen, dass eine aufgedeckte Assoziation auch verallgemeinerbar ist, sollte sie validiert werden (siehe Abschn. 1.4). Trotz dieser Einschränkungen sind Assoziationsregeln eine intuitive Methode, um Muster in nicht zu großen Datensätzen zu erkennen.

56     A. Ng und K. Soo

4.6 Zusammenfassung • Assoziationsregeln lassen erkennen, wie häufig Objekte allein oder gemeinsam mit anderen auftreten. • Es gibt drei gebräuchliche Maße für den Grad der Assoziation: 1. Der Support von {X} gibt an, wie häufig X auftritt. 2. Die Konfidenz von {X → Y} beziffert, wie häufig Y erscheint, wenn X vorliegt. 3. Der Lift von {X → Y} zeigt, wie häufig X und Y zusammen auftreten, wobei berücksichtigt wird, wie häufig sie jeweils allein auftreten. • Das A-priori-Prinzip beschleunigt die Suche nach häufigen Kombinationen von Artikeln, indem große Bereiche von seltenen Kombinationen ausgeschlossen werden.

5 Soziale Netzwerkanalyse

5.1 Beziehungen abbilden Die meisten von uns gehören zu einer Reihe von sozialen Zirkeln, etwa aus Verwandten, Kollegen oder Schulfreunden. Um zu untersuchen, wie diese Leute zueinander in Beziehung stehen, welche Individuen besonders prominent sind oder wie die Gruppendynamik abläuft, können wir eine Methode namens Soziale Netzwerkanalyse (SNA) anwenden. Potenzielle Anwendungen der SNA liegen in viralem Marketing, der Modellierung von Epidemien oder auch bei Strategien für Mannschaftsspiele. Am bekanntesten ist diese Technik jedoch aus der Analyse von sozialen Netzwerken, woher sie auch ihren Namen hat. Abb. 5.1 zeigt ein Beispiel dafür, wie Beziehungen mithilfe der SNA dargestellt werden. © Springer-Verlag GmbH Deutschland, ein Teil von Springer Nature 2018 A. Ng und K. Soo, Data Science – was ist das eigentlich?!, https://doi.org/10.1007/978-3-662-56776-0_5

57

58     A. Ng und K. Soo Mary

Julia David

Tom

Abb. 5.1  Ein einfaches Freundschaftsnetz. Engere Freundschaften sind durch dickere Kanten dargestellt – sehen Sie das sich möglicherweise anbahnende Drama?

Abb. 5.1 zeigt ein Netzwerk, auch Graph genannt, aus vier Individuen, die jeweils durch einen Knoten (hier als Kreis gezeichnet) dargestellt sind. Beziehungen zwischen zwei Knoten sind als Linien gezeichnet, die man Kanten oder Links nennt. Jede Kante kann ein Gewicht haben, welches angibt, wie intensiv die Beziehung ist. Aus Abb. 5.1 können wir ablesen: • David hat die meisten Kontakte, er kennt drei Personen. • Tom kennt nur David, mit dem er gut befreundet ist. • Julia kennt Mary und David, aber eher flüchtig. • David kennt Mary besser als deren Freundin Julia. SNA kann nicht nur Freundschaften abbilden, sondern beliebige Geflechte von sozialen Beziehungen – solange es überhaupt Verbindungen gibt. In diesem Kapitel wenden wir die SNA an, um ein Netzwerk des internationalen Waffenhandels zu analysieren, wodurch wir die dominierenden Mächte und ihre Einflusssphären aufdecken.

5  Soziale Netzwerkanalyse     59

5.2 Beispiel: Waffenhandel und Geopolitik Wir erhielten die Daten über den Handel mit konventionellen Waffen vom Stockholm International Peace Research Institute (SIPRI). Wir haben den Waffenhandel als Indikator für die bilateralen Beziehungen der untersuchten Staaten ausgewählt, da man Waffen tunlichst nur an befreundete Staaten verkaufen sollte. In dieser Analyse haben wir den Wert der gehandelten Waffen auf US-Dollar in Preisen von 1990 standardisiert, außerdem wurden nur Geschäfte mit einem Wert von über 100 Mio. US-$ berücksichtigt. Um den Einfluss von Fluktuationen aufgrund von Produktionszyklen und neu eingeführten Technologien zu reduzieren, haben wir den Handel über eine zehnjährige Periode untersucht (2006 bis 2015). Auf diese Weise erhielten wir ein Netzwerk mit 91 Knoten und 295 Kanten. Um das Netzwerk zu visualisieren, wurde ein sogenannter Force-directed-Algorithmus benutzt: Knoten ohne Kanten beziehungsweise Links stoßen einander ab, während verlinkte Knoten sich gegenseitig anziehen, und zwar umso mehr, je stärker sie verbunden sind (siehe Abb. 5.2). Beispielsweise fand sich der größte Wert des bilateralen Waffenhandels zwischen Russland und Indien (22,3 Mio. US-$), also sind die beiden Länder durch die dickste Kante verbunden und außerdem dicht beieinander positioniert.

Südafrika

Südkorea

Brasilien

Ägypten Irak

Katar

Bangladesch

Sri Lanka

Abb. 5.2  Ein Netzwerk auf Basis des Waffenhandels zwischen den dargestellten Ländern

Iran

Uganda Aserbeidschan Sudan

Tschad

Äquatorial-Guinea DR Kongo Äthiopien

Weißrussland Syrien Jemen Kasachstan Nigeria Mongolei Armenien

Algerien Vietnam

Russia

Usbekistan

Tansania

Namibia Kambodscha

Ghana

China Ukraine Georgien Myanmar

Venezuela

Pakistan

Indien

Peru

Afghanistan

Italien

Israel

Bahrain Neuseeland Tunesien Libanon

Argentinien

Kolumbien Philippinen

Kuwait

Malaysia

Australien Japan Taiwan

VAE

Singapur

USA

Türkei

Finnland Polen Irland

Mexiko Norwegen

Spanien

Libyen

Kanada

Deutschland Frankreich

Großbritannien

Saudi-Arabien

Thailand

Turkmenistan

Schweiz

Marokko Indonesien

Schweden

ChileGriechenland

Portugal Brunei Österreich

Rumänien

Ecuador

Oman

Jordanien

Bulgarien

Ungarn

Belgien

Niederlande

Lettland

Dänemark

60     A. Ng und K. Soo

5  Soziale Netzwerkanalyse     61

Nach Anwendung der Louvain-Methode1 (die wir in Abschn. 5.3 kennenlernen werden) gruppierten sich die Länder zu drei geopolitischen Clustern beziehungsweise Allianzen: • Blau: Der größte Cluster, dominiert von den USA und ihren engsten Verbündeten, etwa Großbritannien und Israel. • Grün: Angeführt von Deutschland und vor allem mit europäischen Ländern, dieser Cluster hatte enge Verbindungen mit den blauen Ländern. • Rosa: Dominiert von Russland und China, dieser Cluster war weitgehend getrennt von den anderen beiden Clustern und bestand überwiegend aus asiatischen und afrikanischen Ländern. Diese Cluster spiegeln einige geopolitische Strukturen des frühen 21. Jahrhunderts wider, etwa die seit Langem bestehenden Allianzen zwischen westlichen Nationen, den nach wie vor bestehenden Gegensatz zwischen dem Westen und den früher kommunistischen Staaten und die zunehmende Konfrontation zwischen den USA und China. Außer dass wir sie in Cluster gruppiert haben, haben wir die einzelnen Länder auch ihrem jeweiligen Einfluss gemäß klassifiziert, wozu wir den berühmten PageRank-Algorithmus verwendet haben (auf den kommen 1Die

Louvain-Methode wurde an der Universität von Löwen entwickelt. Der flämische Name dieser belgischen Stadt ist Leuven, der französische Louvain, weswegen international auch von der Louvain-Methode gesprochen wird (Anm. d. Übers.).

62     A. Ng und K. Soo USA Russland Deutschland Frankreich China Ukraine Niederlande Italien Großbritannien Spanien Schweden Israel Türkei Indien Pakistan 0

PageRank

2

4

6

8

10

Gesamtvolumen des Waffenhandels (in Mrd. US-$)

Abb. 5.3  Die 15 einflussreichsten Länder nach Auswertung ihres Waffenhandels, ermittelt mit dem PageRank-Algorithmus. Der PageRank-Wert jedes Lands ist als gelber Balken dargestellt, der graue Balken steht jeweils für das Gesamtvolumen des Waffenhandels eines Staats

wir gleich zurück). Abb. 5.3 zeigt die 15 einflussreichsten Länder, die Sie in Abb. 5.2 an ihren großen Knoten und vielen ein- und auslaufenden Kanten erkennen können. Unsere Analyse zeigt (wie zu erwarten war), dass die fünf einflussreichsten Länder die USA, Russland, Deutschland, Frankreich und China sind. Dazu passt die Tatsache,

5  Soziale Netzwerkanalyse     63

dass sie (außer Deutschland) alle ständige Mitglieder im UN-Sicherheitsrat sind. In den nun folgenden Abschnitten wollen wir die Methoden, mit denen die Länder gruppiert und klassifiziert wurden, etwas näher vorstellen.

5.3 Die Louvain-Methode Wie wir in Abb. 5.2 gesehen haben, können wir Cluster in einem Netzwerk identifizieren, indem wir Knoten gruppieren. Die Untersuchung dieser Cluster kann uns helfen zu verstehen, wie Teile des Netzwerks sich voneinander unterscheiden und wo es Verbindungen zwischen diesen Teilen gibt. Die Louvain-Methode ist ein Weg, um Cluster in einem Netzwerk zu identifizieren. Sie probiert verschiedene Cluster-Konfigurationen aus, um 1) die Zahl und Stärke der Kanten zwischen Knoten im selben Cluster zu maximieren und 2) Zahl und Stärke der Kanten zwischen Knoten in unterschiedlichen Clustern zu minimieren. Der Grad, zu dem diese beiden Bedingungen erfüllt sind, heißt Modularität. Die optimale Cluster-Zuordnung ist diejenige mit der höchsten Modularität. Um auf diese optimale Cluster-Konfiguration zu kommen, iteriert die Louvain-Methode die folgenden Schritte: • Schritt 0: Behandle jeden Knoten als einen eigenen Cluster, sodass es zu Beginn genauso viele Cluster wie Knoten gibt.

64     A. Ng und K. Soo

• Schritt 1: Ordne einen Knoten so einem anderen Cluster zu, dass die Modularität maximal zunimmt. Wenn die Modularität sich nicht mehr auf diese Weise erhöhen lässt, bleibt der Knoten, wie er ist. Wiederhole dies für alle Knoten. • Schritt 2: Bilde eine vergröberte Version des Netzwerks, indem du jeden Cluster aus Schritt 1 als einzelnen Knoten betrachtest und außerdem die Kanten zwischen den Clustern aus Schritt 1 in gewichtete Kanten zwischen den neuen Knoten übersetzt. • Schritt 3: Wiederhole die Schritte 1 und 2, bis keine weiteren Umgruppierungen und Vergröberungen mehr möglich sind. Auf diese Weise hilft die Louvain-Methode dabei, die signifikanten Cluster aufzudecken, indem sie erst kleine Cluster bildet und diese dann sinnvoll zusammenführt. Ihre Einfachheit und Effizienz macht die Louvain-Methode zu einem beliebten Werkzeug für das Netzwerk-Clustering. Sie hat allerdings auch ihre Grenzen: Wichtige, aber kleine Cluster könnten übersehen werden:  Das iterative Zusammenführen von Clustern könnte dazu führen, dass wichtige, aber kleine Cluster verschmolzen werden. Um dies zu vermeiden, könnten wir überprüfen, welche Cluster in den Iterationen gebildet wurden, und gegebenenfalls fälschlich „eingemeindete“ Cluster wieder unabhängig machen. Zu viele mögliche Konfigurationen: Bei Netzwerken mit überlappenden oder ineinander verschachtelten

5  Soziale Netzwerkanalyse     65

Clustern könnte es schwierig werden, das optimale Clustering zu finden. Wir können aber im Fall mehrerer Lösungen mit gleich hoher Modularität die Cluster mithilfe von Zusatzinformationen aus externen Quellen validieren, beispielsweise deuten die Übereinstimmungen zwischen geografischer Lage und geopolitischen Allianzen auf eine sinnvolle Clusterbildung in Abb. 5.2 hin.

5.4 PageRank-Algorithmus Cluster zeigen Gebiete auf, in denen besonders viele Interaktionen auftreten. Diese Interaktionen könnten von einem dominierenden Knoten hervorgerufen werden, um den sich dann der Cluster gebildet hat. Um solche dominierenden Knoten ausfindig zu machen, klassifizieren wir die Knoten mithilfe von Ranking-Methoden. Der PageRank-Algorithmus2 war einer der ersten Algorithmen, mit denen Google Websites klassifiziert hat. Wir beschreiben hier zwar PageRank im Kontext des Suchmaschinenrankings, es könnte aber genauso gut benutzt werden, um die Knoten eines beliebigen Netzwerks zu bewerten. Der PageRank einer Website wird von drei Faktoren bestimmt:

2Benannt

nach Larry Page (und nicht nach den Web-„Pages“, die bewertet werden!), der den Algorithmus zusammen mit Sergey Brin entwickelt hat und 1997 dafür ein Patent erhielt. Anschließend haben die beiden die Firma Google gegründet.

66     A. Ng und K. Soo

• Zahl der eingehenden Links: Wenn eine Website von einer anderen Website gelinkt wurde, wird sie wahrscheinlich von mehr Usern aufgerufen. • Stärke der Links: Je häufiger diese Links aufgerufen werden, desto mehr Traffic hat eine Website. • Ranking der Quellen von Links: Das Ranking einer Website erhöht sich, wenn sie mit Websites mit hohem Ranking verlinkt ist. Um zu sehen, wie PageRank funktioniert, betrachten Sie das Beispiel in Abb. 5.4, wo Knoten für Websites stehen und Kanten für Hyperlinks. Ein eingehender Hyperlink mit hohem Gewicht bedeutet viele User, die von einer anderen Seite auf die betrachtete Seite gelangen. Wir erkennen in Abb. 5.4, dass ein User von Website M doppelt so wahrscheinlich zu Website D wechselt wie zu Website J und dass er nicht direkt zu Website T gelangen kann. M 1 1 J

1

2

2 2

1 D

2

T

Abb. 5.4  Ein Netzwerk mit Websites als Knoten und Hyperlinks als Kanten

5  Soziale Netzwerkanalyse     67

M 25 J 25 25 D

25

T

Abb. 5.5  Die Ausgangssituation, wenn 100 User sich gleichmäßig auf vier Websites verteilen

Um zu verstehen, welche Website die meisten User anlockt, simulieren wir das in Abb. 5.4 dargestellte Surfverhalten für 100 User und notieren jeweils, auf welcher Website diese schließlich landen. Als Erstes verteilen wir dazu unsere 100 User gleichmäßig auf die vier Websites, wie in Abb. 5.5 dargestellt. Dann gruppieren wir die User neu, und zwar so, dass Websites desto mehr User bekommen, je stärker die ausgehenden Links sind. Zum Beispiel gehen zwei Drittel der Besucher von Website M als Nächstes zu Website D, während das übrige Drittel zu Website J wechselt. Die Kanten in Abb. 5.6 geben die Zahl der User an, welche die jeweilige Website besuchen beziehungsweise verlassen. Nachdem die User neu verteilt sind, sitzen bei Website M nun nur noch 23 User, von denen zehn von Website D kamen und 13 von Website J. Abb. 5.7 zeigt die resultierende Verteilung der User, gerundet auf ganze Werte (halbe User gibt es nicht). Zur Berechnung der PageRank-Werte für unsere vier Websites wiederholen wir diese Umverteilung der

68     A. Ng und K. Soo M 25

12,5 J 25

8,3 5 12,5

10

16,6 25 D

10 25

25

T

Abb. 5.6  Die User werden gemäß der Stärke der abgehenden Links neu verteilt

M 23 J 13 54 D

10

T

Abb. 5.7  Die neue Verteilung der User

virtuellen Nutzer, bis sich deren Zahl auf den Websites nicht mehr ändert. Diese abschließenden Werte nehmen wir dann als PageRank der einzelnen Websites – je mehr User sie angezogen haben, desto höher die Bewertung. Wir könnten ebenso gut die Dominanz eines Staats im Waffenhandelsnetzwerk mit PageRank bewerten (und haben es ja auch getan, siehe Abschn. 5.2). Ein hoher PageRank-Wert entspräche dann einem Land, das viele teure Waffendeals mit anderen hochbewerteten Ländern

5  Soziale Netzwerkanalyse     69

abschließt – was wir dann als einen einflussreichen Player in einer zentralen Position im globalen Waffenhandelsnetz beziehungsweise in den geopolitischen Beziehungen interpretieren würden. Trotz der einfachen Anwendung und des historisch fast beispiellosen Erfolgs hat der PageRank-Algorithmus eine Schwäche: Er bevorzugt ältere Knoten. Es könnte zum Beispiel eine neue Website mit exzellentem Inhalt online gehen, die wegen ihrer Unbekanntheit aber mit einem sehr niedrigen PageRank-Wert starten müsste – und deshalb zu Unrecht als uninteressant angesehen und nicht verlinkt würde. Um dies zu vermeiden, müssen PageRank-Werte regelmäßig aktualisiert werden, damit neue Websites die Gelegenheit haben, mit steigender Reputation die PageRank-Ränge hinaufzuklettern. Allerdings ist diese Tendenz zur Bevorzugung älterer Knoten nicht ausschließlich von Nachteil. Sie könnte etwa dabei helfen, langfristig wirksame Trends aufzudecken, wie das gerade bei geopolitischer Dominanz der Fall ist. Dies zeigt, dass die Schwäche eines Algorithmus bei einer geänderten Fragestellung sogar von Nutzen sein kann.

5.5 Grenzen Auch wenn Clustering und Ranking-Methoden uns zu tieferen Einsichten in Netzwerke verhelfen, sollten wir die Resultate mit einer gewissen Vorsicht betrachten. Nehmen wir zum Beispiel unsere Waffenhandelsdaten, mit denen wir die Beziehungen zwischen Staaten analysiert haben. Dieses sehr simple Maß hat einige Fallstricke:

70     A. Ng und K. Soo

Ignorieren von diplomatischen Beziehungen ohne Waffen­handel:  Die meisten Kanten bestehen zwischen einem Waffenexporteur und einem Importeur. Freundschaftliche Beziehungen zwischen zwei Ländern, die beide überwiegend Waffen importieren (oder exportieren) werden nicht berücksichtigt. Andere Motive bei Waffenverkäufen werden übersehen:  Neu gekaufte Waffen müssen in bestehende Waffensysteme integriert werden können, was geopolitisch vorteilhafte Waffengeschäfte vereiteln kann. Außerdem können bei waffenexportierenden Staaten innen- und wirtschaftspolitische Gründe geopolitische Erwägungen überwiegen, sodass Waffen auch an nicht befreundete oder sogar feindlich eingestellte Länder verkauft werden, wenn das Geld dringend genug gebraucht wird. Dies könnte erklären, warum die Ukraine im Ranking auf Platz 6 kommt, ohne tatsächlich über größeren geopolitischen Einfluss zu verfügen. Hier ist noch eine allgemeine Warnung angebracht: Da die Belastbarkeit unserer Schlussfolgerungen davon abhängt, wie gut die Daten das Konstrukt repräsentieren, das wir untersuchen wollen, müssen wir die Daten, aus denen das Netzwerk aufgebaut werden soll, sorgfältig auswählen. Die Datenquellen müssen hinreichend zuverlässig sein und die Analysetechniken ausreichend robust, und wir sollten auf jeden Fall die Ergebnisse mit anderen Informationsquellen abgleichen.

5  Soziale Netzwerkanalyse     71

5.6 Zusammenfassung • Mit der sozialen Netzwerkanalyse können wir Beziehungen zwischen Objekten abbilden und analysieren. • Die Louvain-Methode identifiziert Cluster in einem Netzwerk, indem sie die Interaktionen innerhalb der Cluster maximiert und diejenigen zwischen Clustern minimiert. Sie funktioniert am besten, wenn die Cluster gleich groß und disjunkt (nicht überlappend) sind. • Der PageRank-Algorithmus bewertet Knoten in einem Netzwerk anhand der Zahl ihrer Links, deren Stärke und der Bewertungen von Quellen dieser Links. Während sich damit die dominierenden Knoten eines Netzwerks sehr gut auffinden lassen, bevorzugt das Verfahren ältere Knoten, die mehr Zeit hatten, substanzielle Links aufzubauen.

6 Regressionsanalyse

6.1 Trendlinien Trendlinien sind ein beliebtes Werkzeug für die Vorhersage von Datenwerten, da sie leicht zu ermitteln und zu verstehen sind. Sie brauchen nur einen Blick in Ihre Tageszeitung zu werfen, schon sehen Sie Trendlinien für Aktienkurse, Wassertemperaturen und alles Mögliche andere. Normalerweise verwendet man eine unabhängige Variable, auch Prädiktor genannt, um eine abhängige Variable oder Zielvariable vorherzusagen. So ist die Zeit bei einem Aktienchart der Prädiktor und der Aktienkurs die vorherzusagende Zielvariable. Die Vorhersagen lassen sich verbessern, wenn weitere Prädiktoren hinzugenommen werden, etwa die Umsatzerlöse im Fall des Aktienkurses. © Springer-Verlag GmbH Deutschland, ein Teil von Springer Nature 2018 A. Ng und K. Soo, Data Science – was ist das eigentlich?!, https://doi.org/10.1007/978-3-662-56776-0_6

73

74     A. Ng und K. Soo

An dieser Stelle kommt die Regressionsanalyse ins Spiel, welche uns nicht nur zu besseren Vorhersagen durch die Verwendung mehrerer Prädiktoren verhilft, sondern es auch erlaubt, die relative Stärke der Prädiktoren zu vergleichen. Um zu sehen, wie man dies macht, schauen wir uns eine Fallstudie zur Vorhersage von Hauspreisen an.

6.2 Beispiel: Vorhersage von Hauspreisen Wir benutzen Daten über Hauspreise in Boston währen der 1970er-Jahre. Eine Voranalyse hat ergeben, dass damals die zwei stärksten Prädiktoren für den Hauspreis in Boston die Anzahl der Räume im Haus und der Anteil der Anwohner mit niedrigen Einkommen in der Nachbarschaft waren. Aus Abb. 6.1 ersehen wir, dass teure Häuser im Allgemeinen mehr Räume haben. Um den Preis eines Hauses aus der Zimmerzahl vorherzusagen, zeichnen wir eine Trendlinie (blau) durch die Wolke der Datenpunkte, man spricht auch von einer Best-Fit-Linie oder einer Regressionsgeraden (sofern sie per Regressionsanalyse berechnet wurde). Diese läuft durch so viele Datenpunkte wie möglich oder kommt zumindest so vielen Punkten wie möglich so nahe wie möglich. Im Beispiel von Abb. 6.1 lesen wir für ein Haus mit acht Räumen einen Preis von etwa 38.150 US-$ ab.

Hauspreis in 1000 US-$

6 Regressionsanalyse     75

Durchschniliche Zimmerzahl Abb. 6.1  Hauspreis abhängig von der Anzahl der Räume

Außer der Zahl der Zimmer hat auch die soziale Zusammensetzung der Nachbarschaft den Preis der Bostoner Häuser beeinflusst. Häuser waren billiger in Gegenden, in denen viele Menschen mit niedrigem Einkommen wohnten (siehe Abb. 6.2). Da die Datenpunkte eher einer gekrümmten Linie folgten (Abb. 6.2a), haben wir eine mathematische Transformation namens Logarithmierung auf die Prädiktorwerte angewandt, woraufhin die transformierten Datenpunkte sich wieder brav entlang einer geraden Trendlinie aufreihten (Abb. 6.2b). Wir können beobachten, dass die Datenpunkte sich in Abb. 6.2b dichter um die Trendlinie scharen als in Abb. 6.1, was den Schluss erlaubt, dass der (fehlende)

Hauspreis

76     A. Ng und K. Soo

a) Original

b) transformiert

Abb. 6.2  Hauspreis abhängig vom Anteil der Nachbarn mit niedrigem Einkommen

Wohlstand in der Nachbarschaft ein besserer Prädiktor des Hauspreises war als die Anzahl der Räume. Um unsere Schätzung der Hauspreise weiter zu verbessern, können wir eine Kombination der beiden Prädiktoren Raumzahl und Nachbarschaft benutzen. Da wir allerdings bereits gesehen haben, dass der Wohlstand der Nachbarschaft der bessere Prädiktor ist, wäre es keine so gute Idee, einfach beide Prädiktoren voneinander abzuziehen. Stattdessen sollte dem Einfluss der Nachbarschaft ein größeres Gewicht gegeben werden (siehe Abschn. 6.4). In Abb. 6.3 sind die Hauspreise gegen eine optimal gewichtete Kombination der zwei Prädiktoren aufgetragen. Beachten Sie, dass die Datenpunkte jetzt noch näher an der neuen Trendlinie liegen als zuvor, die Vorhersagen dürften jetzt also die bisher zuverlässigsten sein. Dies lässt sich zeigen, indem man die mittleren Vorhersagefehler der drei Trendlinien miteinander vergleicht (siehe Tab. 6.1).

Hauspreis in 1000 US-$

6 Regressionsanalyse     77

kombinierter Prädiktor Abb. 6.3  Hauspreis abhängig von einer gewichteten Kombination von Raumzahl und (fehlendem) Wohlstand der Nachbarn Tab. 6.1  Mittlerer Vorhersagefehler bei den drei Trendlinien Vorhersagefehler (in 1000 US-$) Anzahl der Räume Fehlender Wohlstand der Nachbarn Beide kombiniert

4,4 3,9 3,7

Es ist nicht wirklich überraschend, dass eine geschickt gewichtete Kombination der beiden Prädiktoren zu besonders guten Vorhersagen führt. Interessant sind dagegen jetzt die folgenden zwei Fragen: 1) Wie bestimmen wir die optimalen Gewichte und 2) wie sollten wir sie interpretieren?

78     A. Ng und K. Soo

6.3 Gradientenverfahren Die Prädiktorgewichte sind die wesentlichen Parameter in einer Regressionsanalyse, welche die optimalen Gewichte durch das Lösen von Gleichungssystemen ausrechnet. Da jedoch die Regressionsanalyse ein einfaches Konzept ist, mit dem man gut auch andere Ansätze illustrieren kann, werden wir sie benutzen, um eine alternative Methode für die Parameteroptimierung vorzustellen. Diese Methode heißt Gradientenverfahren, sie wird eingesetzt, wenn die Parameter nicht direkt bestimmt werden können (etwa weil die Gleichungssysteme nicht oder nur sehr schwer zu lösen sind). Kurz gesagt, schätzt beziehungsweise rät der Algorithmus des Gradientenverfahrens einen ersten Satz von sinnvoll erscheinenden Gewichten und berechnet dann mit diesen Werten iterativ Vorhersagen, wobei der Vorhersagefehler mit der Zeit immer kleiner wird. Dieses Vorgehen lässt sich vergleichen mit einem Bergsteiger, der einen Abhang heruntersteigt. Bei jedem Schritt bestimmt der Algorithmus, in welche Richtung es am steilsten hinuntergeht, und rekalibriert daraufhin die Gewichte, sodass er sich in diese Richtung bewegt. Schließlich kommt er am niedrigsten Punkt an, wo es in keiner Richtung mehr nach unten geht und somit der minimale Vorhersagefehler erreicht ist. Abb. 6.4 illustriert, wie eine optimierte Regressionsgerade dem niedrigsten Punkt auf einer abfallenden Kurve entspricht. Nicht nur bei der Regressionsanalyse, sondern auch bei anderen Methoden kann man mit dem Gradientenverfahren Parameter optimieren, etwa bei Support-­ VektorMaschinen (siehe Kap. 8) und neuronalen Netzen (siehe

6 Regressionsanalyse     79

b) opmal

Vorhersagefehler

a) subopmal

Gradientenverfahren Vorhersagefehler

Trendlinie

Abb. 6.4  Optimierung einer Trendlinie mit dem Gradientenverfahren

Kap. 11). Bei diesen komplexeren Modellen kann das Gradientenverfahren allerdings zu falschen Ergebnissen führen beziehungsweise unterschiedliche Ergebnisse liefern, je nachdem mit welchen Parameterwerten wir starten (an welcher Stelle oben am Hang wir losgehen). Wenn wir zum Beispiel zufällig oberhalb einer kleinen Mulde oder „lokalen Senke“ beginnen, führt uns das Gradientenverfahren direkt in diese Senke und denkt, es wäre bereits am Ziel, da es von dort aus in keine Richtung weiter abwärts geht (siehe Abb. 6.5). Um das Risiko, in einer lokalen Senke stecken zu bleiben, zu verringern, kann man sogenannte stochastische

Vorhersagefehler

80     A. Ng und K. Soo

Abb. 6.5  Das Gradientenverfahren kann eine lokale Senke (grünes Dreieck) mit dem absoluten Minimum verwechseln (grüne Linie)

Gradientenverfahren einsetzen, wo ein Zufallselement mit ins Spiel kommt. Beispielsweise werden nicht alle Datenpunkte zur Parameteranpassung im Iterationsschritt benutzt, sondern nur ein zufällig gewählter. Auf diese Weise kann der Algorithmus aus einer lokalen Senke entkommen. Die mit solch einem stochastischen Prozess bestimmten Parameterwerte sind zwar nicht zwangsläufig die absolut optimalen, kommen dem Optimum aber in der Regel recht nahe. Glücklicherweise tritt dieses Problem aber nur bei komplizierteren Modellen auf, bei der Regressionsanalyse brauchen wir uns darüber nicht den Kopf zu zerbrechen.

6.4 Regressionskoeffizienten Haben wir erst einmal die optimalen Gewichte für unsere Regressionsprädiktoren gefunden, müssen wir sie interpretieren. Die Regressionsgewichte werden formal Regressionskoeffizienten genannt. Der Regressionskoeffizient eines

6 Regressionsanalyse     81

Prädiktors misst, wie aussagekräftig dieser Prädiktor in Gegenwart anderer Prädiktoren ist. Mit anderen Worten ist dies also eher der von diesem Prädiktor eingebrachte „Mehrwert“ als seine absolute Vorhersagekraft. Nehmen wir zum Beispiel an, wir würden mit der Grundfläche und der Zahl der Räume eines Hauses seinen Preis vorhersagen, dann könnte das Gewicht der Zimmerzahl gegen null gehen. Da nämlich die Zahl der Räume mit der Grundfläche als Maß der Größe eines Hauses stark überlappt, fügt sie kaum neue Informationen hinzu, das heißt, sie trägt nichts Neues zur Vorhersagekraft des Modells bei. Prädiktoren, die in unterschiedlichen Einheiten gemessen werden, würden ebenfalls eine sinnvolle Interpretation unserer Regressionskoeffizienten verhindern. Ein in Zentimetern angegebener Prädiktor hätte rein zahlenmäßig ein 100-mal schwächeres Gewicht als derselbe Prädiktor in der Einheit Meter. Aus diesem Grund sollten wir immer alle unsere Prädiktorvariablen standardisieren, bevor wir eine Regressionsanalyse durchführen. Standardisierung bedeutet, jede Variable in Form von Perzentilen auszudrücken. Bei derart standardisierten Prädiktoren nennt man die Koeffizienten Beta-Gewichte, diese können dann in jedem Fall sinnvoll miteinander verglichen werden. In unserem obigen Beispiel mit den Hauspreisen wurden die zwei Prädiktoren „Zimmerzahl“ und „Anteil von Nachbarn mit niedrigem Einkommen“ standardisiert und dann mit den relativen Gewichten 2,7 beziehungsweise 6,3 versehen. Der Einfluss der Nachbarschaft war also ein

82     A. Ng und K. Soo

viel stärkerer Prädiktor für den Hauspreis als die Anzahl der Räume. Die Regressionsgleichung sähe dann so aus: Preis = 2,7 · (Zimmerzahl) − 6,3 · (Anteil von Nachbarn mit niedrigem Einkommen) Beachten Sie, dass in dieser Gleichung der Anteil der nicht-wohlhabenden Nachbarn ein negatives Gewicht hat (Minuszeichen!). Dies liegt daran, dass der Prädiktor negativ mit dem Hauspreis korreliert ist – je mehr Leute mit niedrigem Einkommen, desto weniger Verkaufserlös. Die Trendlinie in Abb. 6.2 hat somit eine negative Steigung (fällt von oben links nach rechts unten ab).

6.5 Korrelationskoeffizienten Wenn es nur einen Prädiktor gibt, nennt man das Beta-­ Gewicht dieses Prädiktors Korrelationskoeffizient und bezeichnet es mit dem Buchstaben r. Korrelationskoeffizienten haben immer Werte zwischen −1 und +1. Man kann zwei Arten von Information aus ihnen ableiten (Abb. 6.6). Richtung:  Positive Koeffizienten bedeuten, dass der Prädiktor sich in dieselbe Richtung bewegt wie die Zielvariable; bei negativen Koeffizienten ist es umgekehrt. Der Preis eines Hauses ist mit der Anzahl seiner Zimmer positiv korreliert, gleichzeitig ist er negativ korreliert mit dem Anteil an Nachbarn mit niedrigem Einkommen. Stärke:  Je näher der Koeffizient an −1 oder +1 liegt, desto aussagekräftiger ist der Prädiktor. Zum Beispiel hat

6 Regressionsanalyse     83 r = _1

r = 0,5

r=0

r=1

Abb. 6.6  Streuung der Datenpunkte und Korrelationskoeffizient

der Korrelationskoeffizient der Trendlinie in Abb. 6.1 den Wert 0,7, während der in Abb. 6.2b bei −0,8 liegt. Dies heißt, dass der (fehlende) Wohlstand der Nachbarschaft ein besserer Prädiktor für den Hauspreis ist als die Zimmerzahl. Ein Korrelationskoeffizient null würde bedeuten, dass es keinen Zusammenhang zwischen Prädiktor und Zielvariable gibt. Da Korrelationskoeffizienten die Stärke eines Prädiktors unabhängig von anderen

84     A. Ng und K. Soo

Prädiktoren beziffern, sind sie ein zuverlässigeres Maß für die Güte von Prädiktoren als Regressionskoeffizienten.

6.6 Grenzen Auch wenn sie informativ und schnell zu berechnen ist, hat die Regressionsanalyse ihre Grenzen: Empfindlich auf Ausreißer:  Da die Regressionsanalyse alle Datenpunkte gleichermaßen berücksichtigt, können einige wenige Datenpunkte mit extremen Werten die Trendlinie signifikant verändern. Dies erkennt man, wenn man die Ausreißer zunächst in einem Streudiagramm identifiziert und probeweise vor der weiteren Analyse ausschließt. Verzerrte Gewichte von korrelierten Prädiktoren:  Schließt man hochkorrelierte Prädiktoren in sein Regressionsmodell mit ein, verfälscht man die Interpretation der Gewichte, man nennt dieses Problem Multikollinearität. Es lässt sich beheben, wenn korrelierte Prädiktoren von vornherein ausgeschlossen werden, oder indem man fortschrittlichere Techniken wie Lasso- oder Ridge-Regression einsetzt. Gekrümmte Trends:  In unseren Beispielen waren die meisten Trends gerade Linien. Es können aber durchaus auch gekrümmte Trendlinien (oder besser Trendkurven) vorkommen, so wie in Abb. 6.2a. In diesem Fall könnten wir die Prädiktorwerte wie in Abschn. 6.2 transformieren oder aber auf alternative Algorithmen wie Support-­VektorMaschinen zurückgreifen (siehe Kap. 8).

6 Regressionsanalyse     85

Liefert keinen Kausalzusammenhang: Angenommen, wir würden in unseren Daten eine positive Korrelation zwischen der Zahl der Hundebesitzer und den Hauspreisen finden. Wir wissen aber, dass die Aufnahme eines Hunds in den Haushalt den Wert des Hauses nicht ursächlich erhöht. Allenfalls könnte man argumentieren, dass reiche Haushalte sich sowohl größere und teurere Häuser als auch noch ein paar Haustiere dazu leisten. Trotz dieser Einschränkungen bleibt die Regressionsanalyse eine der meistgenutzten, einfach und intuitiv anzuwendenden Methoden, um Vorhersagen zu treffen. Eine gewisse Achtsamkeit bei der Interpretation unserer Resultate sichert die Seriosität unserer Schlussfolgerungen.

6.7 Zusammenfassung • Die Regressionsanalyse findet die „Best-Fit-Trendlinie“ oder Regressionsgerade, welche so viele Datenpunkte wie möglich berührt oder ihnen zumindest so nahe wie möglich kommt. • Eine Trendlinie wird mithilfe von gewichteten Kombinationen von Prädiktoren berechnet. Die Gewichte heißen Regressionskoeffizienten, sie geben die Aussagekraft eines Prädiktors in Anwesenheit von anderen Prädiktoren an. • Die Regressionsanalyse funktioniert am besten, wenn es wenig Korrelation zwischen den Prädiktoren und keine Ausreißer gibt und wenn der erwartete Trend eine gerade Linie ist.

7 k-nächste Nachbarn und Ausreißererkennung

7.1 Der Weindetektiv Lassen Sie uns über Wein reden. Haben Sie sich jemals gefragt, worin eigentlich der wahre Unterschied zwischen Rot- und Weißwein besteht? Viele Menschen nehmen an, dass man ganz einfach Rotwein aus roten Trauben (die eigentlich blauviolett sind) macht und Weißwein aus weißen (die eigentlich grün sind). Das stimmt so aber nicht ganz, denn Weißwein lässt sich auch aus roten Trauben keltern. Allerdings stammt Rotwein tatsächlich immer von „roten“ Trauben. Der Schlüssel liegt in der Art, wie die Trauben vergoren werden: Bei der Herstellung von Rotwein lässt man den auch bei roten Trauben in der Regel fast farblosen Traubensaft zusammen mit den dunklen Beerenschalen © Springer-Verlag GmbH Deutschland, ein Teil von Springer Nature 2018 A. Ng und K. Soo, Data Science – was ist das eigentlich?!, https://doi.org/10.1007/978-3-662-56776-0_7

87

88     A. Ng und K. Soo

gären, während für Weißwein der Saft ohne die Schalen verarbeitet wird. Obwohl viele Menschen Rot- und Weißwein eher optisch unterscheiden würden, lässt sich das auch deutlich komplizierter mithilfe von kriminaltechnischen chemischen Untersuchungen machen. Dies bedeutet, dass wir, ohne einen Blick auf den Wein zu werfen, allein aus seiner chemischen Zusammensetzung auf seine Farbe schließen können. Dazu bedienen wir uns einer der einfachsten Formen des maschinellen Lernens – einer Methode namens „k-nächste Nachbarn“.

7.2 Gleich und gleich gesellt sich gern k-nächste Nachbarn (kNN) ist ein Algorithmus, der einen Datenpunkt anhand der Eigenschaften seiner Nachbarn klassifiziert. Dies bedeutet, dass ein Datenpunkt mit unbekannter Farbe, der von vier roten und einem schwarzen Punkt umgeben ist, von dem Algorithmus als rot angenommen wird (siehe Abb. 7.1). Das „k“ in kNN ist ein Parameter, der die Anzahl der nächsten Nachbarn angibt, welche der Algorithmus jeweils zurate zieht. Im obigen Beispiel ist k = 5. Den richtigen Wert für k zu wählen, ist entscheidend für eine gute Vorhersagegenauigkeit, es stellt den wesentlichen Schritt der Parameteranpassung bei diesem Modell dar. Wenn k zu klein ist (Abb. 7.2a), würden sich die Datenpunkte nur an ihren unmittelbaren Nachbarn orientieren und es käme zu Fehlern aufgrund von zufälligen

7  k-nächste Nachbarn und Ausreißererkennung     89

?

Abb. 7.1  Der Datenpunkt in der Mitte wird als rot gewertet, da die Mehrheit seiner fünf nächsten Nachbarn rot ist

k=3

a) Überanpassung

k = 17

b) idealer Fit

k = 50

c) Unteranpassung

Abb. 7.2  Vergleich der Ergebnisse mit unterschiedlichen Werten des Parameters k. Punkte im grauen Bereich werden als „Weißwein“ angenommen, Punkte im rötlichen Bereich als „Rotwein“

Fluktuationen. Wenn k dagegen zu groß gewählt wird (Abb. 7.2c), richten sich die Datenpunkte auch an weit entfernten Nachbarn aus, wodurch reale Muster in den Daten „verschmiert“ würden. Ein optimaler k-Wert (Abb. 7.2b) würde hingegen die Datenpunkte mit einer sinnvollen mittleren Anzahl von Nachbarn verknüpfen, sodass kleinskaliges „Rauschen“ ignoriert wird, die realen Strukturen in den Daten jedoch offen zutage treten. Den idealen Fit findet man durch Kreuzvalidierung des Parameters k (siehe Abschn. 1.4). In einem binären

90     A. Ng und K. Soo

Klassifikationsproblem (nur zwei Datenwerte) ist es außerdem sinnvoll, k ungerade zu wählen, damit es kein „Unentschieden“ bei der Abstimmung unter den k Nachbarn geben kann. Außer zur Einteilung von Datenpunkten in Gruppen kann man kNN auch einsetzen, um stetige Datenwerte vorherzusagen, indem die Werte der k nächsten Nachbarn aggregiert (zusammengerechnet) werden. Eine Möglichkeit wäre es dabei, alle Nachbarn gleich zu behandeln und einfach den arithmetischen Mittelwert auszurechnen. Besser ist es aber oft, ein gewichtetes Mittel zu wählen, beim dem Werte von näher gelegenen Nachbarn ein höheres Gewicht haben als weiter entfernte, da letztere vermutlich einen geringeren Einfluss auf den fraglichen Punkt haben.

7.3 Beispiel: Der statistische Sommelier Kommen wir zurück zu unserem Weinbeispiel – wir wollen jetzt die Farbe eines bestimmten Weins aus der Farbe von anderen Weinproben mit ähnlicher chemischer Zusammensetzung ableiten. Unsere Daten kommen von roten und weißen Varianten eines portugiesischen Vinho Verde. Wir haben dafür von 1599 roten und 4898 weißen Weinen die Gehalte an zwei chemischen Verbindungen – Chloride und Schwefeldioxid – gegeneinander aufgetragen (siehe Abb. 7.3). Da die Schalen der Weinbeeren eine höhere Konzentration von Stoffen wie Natriumchlorid (auch unter der

Schwefeldioxid

7  k-nächste Nachbarn und Ausreißererkennung     91

Chloride Abb. 7.3  Die Gehalte an Chloriden und Schwefeldioxid in Weißweinen (schwarz) und Rotweinen (rot)

Bezeichnung „Speisesalz“ bekannt) enthalten, finden wir mehr Chloride in Rotweinen, da diese ja mit den Schalen gekeltert werden. Traubenschalen enthalten außerdem auch natürliche Antioxidantien, welche das Innere der Frucht schützen. Ohne diese Stoffe muss Weißweinen das Konservierungsmittel Schwefeldioxid zugesetzt werden. Aus diesen Gründen häufen sich in Abb. 7.3 die Rotweine unten rechts, während die Weißweine oben links versammelt sind. Um die Farbe eines Weins mit gegebenem Gehalt an Chloriden und Schwefeldioxid vorherzusagen, können wir die bekannten Farben von Weinen zu Hilfe nehmen, die

92     A. Ng und K. Soo

in dem Plot an der gleichen Stelle zu finden sind. Wenn wir dies für alle Datenpunkte machen, erhalten wir eine Grenzlinie, welche im Plot die Rotweine von den Weißweinen trennt (siehe Abb. 7.2). Mit einem idealen Fit (Abb. 7.2b), erreichen wir eine Vorhersagegenauigkeit von über 98 %.

7.4 Ausreißererkennung kNN eignet sich nicht nur zur Vorhersage von Datenwerten oder zur Gruppierung von Datenpunkten. Man kann damit auch Ausreißer erkennen, wodurch sich beispielsweise Betrugsversuche aufdecken lassen. Diese Ausreißererkennung (auch anomaly detection ) führt manchmal sogar zu zusätzlichen Erkenntnissen, etwa der Entdeckung eines Prädiktors, der bis dato übersehen wurde. Ausreißer lassen sich am einfachsten erkennen, wenn die Daten visualisiert werden. In Abb. 7.3 beispielsweise sehen wir sofort, welche Weine nicht bei ihren Clustern positioniert sind. Es ist allerdings nicht immer praktikabel, die Daten in zweidimensionalen Plots aufzutragen, insbesondere wenn mehr als zwei Prädiktorvariablen zu untersuchen sind. In solchen Fällen zeigen Modelle wie kNN ihren Nutzen. Da kNN in den Daten enthaltene Muster nutzt, um Vorhersagen zu treffen, deuten Vorhersagefehler auf Datenpunkte hin, die nicht zu den allgemeinen Trends passen. Tatsächlich könnte im Prinzip jeder beliebige Algorithmus,

7  k-nächste Nachbarn und Ausreißererkennung     93

der ein Vorhersagemodell generiert, zur Ausreißererkennung eingesetzt werden. So würden in einer Regressionsanalyse (Kap. 6) Datenpunkte, die merklich von der Regressionsgeraden abweichen, sofort als Ausreißer auffallen. Wenn wir nun die Daten von unseren Rot- und Weißweinen auf Ausreißer oder Anomalien (das heißt falsch zugewiesene Farbe) untersuchen, sehen wir, dass Rotweine, die fälschlich als Weißwein klassifiziert wurden, einen unüblich hohen Gehalt an Schwefeldioxid aufweisen. Daraufhin lesen wir im Weinlexikon nach, dass manche Weine mit niedrigem Säuregehalt mehr Schwefeldioxid als Konservierungsmittel benötigen, und werden bei der nächsten Untersuchung den Säuregehalt des Weins als weiteren Prädiktor miteinbeziehen und so zu noch besseren Vorhersagen gelangen. Während Ausreißer oft von nicht berücksichtigten Prädiktoren verursacht werden, ist es jedoch auch möglich, dass ihnen eine zu geringe Anzahl an Datenpunkten zugrunde liegt, sodass das Vorhersagemodell nicht ausreichend trainiert werden konnte. Je weniger Datenpunkte wir haben, desto schwieriger lassen sich Muster in den Daten ausmachen, es ist also sehr wichtig, ausreichend große Datensätze zusammenzutragen. Sind die Ausreißer erst einmal erkannt, können sie aus dem Datensatz ausgeschlossen werden, bevor die Parameter des Vorhersagemodells „trainiert“ (also angepasst) werden. Dies reduziert das Datenrauschen und verbessert die Vorhersagegenauigkeit des Modells.

94     A. Ng und K. Soo

7.5 Grenzen Obwohl kNN ein einfacher und effizienter Algorithmus ist, gibt es Situationen, in denen er weniger gute Ergebnisse liefert: Unterschiedlich große Klassen: Wenn verschiedene Klassen von Daten untersucht werden sollen und diese sehr unterschiedliche Größen haben, werden Datenpunkte aus den kleinsten Klassen leicht übersehen beziehungsweise falsch eingeordnet. Dem lässt sich gegensteuern, wenn sehr nahe Nachbarn ein deutlich höheres Gewicht bekommen. Überzählige Prädiktoren:  Wenn zu viele Prädiktoren im Spiel sind, muss das Verfahren Nachbarn und Abstände in Räumen mit sehr vielen Dimensionen betrachten, was sehr rechenintensiv werden kann. Darüber hinaus sind manche Prädiktoren möglicherweise redundant und verbessern die Vorhersagegenauigkeit gar nicht. Hier empfiehlt sich eine Dimensionsreduktion (siehe Kap. 3), um die für die aktuelle Analyse aussagekräftigsten Prädiktoren herauszuarbeiten.

7.6 Zusammenfassung • Die k-nächste-Nachbarn-Methode (kNN) klassifiziert Datenpunkte anhand der Werte von benachbarten Datenpunkten.

7  k-nächste Nachbarn und Ausreißererkennung     95

• k ist dabei die Anzahl der betrachteten Datenpunkte, sinnvolle Werte für diesen Parameter erhält man per Kreuzvalidierung. • kNN funktioniert am besten mit wenigen Prädiktoren und Klassen von vergleichbarer Größe. Falsche Klassifizierungen können Hinweise auf Ausreißerwerte geben.

8 Support-Vektor-Maschine

8.1 „Nein“ oder „Oh Nein“? Medizinische Diagnosen sind ein komplexes und schwieriges Thema. Unzählige Symptome müssen berücksichtigt werden, und der ganze Prozess kann von subjektiven Vorlieben der Ärztinnen und Ärzte beeinflusst werden. Manchmal gelingt die richtige Diagnose erst, wenn es schon zu spät ist. Ein systematischerer Ansatz zum Aufspüren der hinter den Beschwerden steckenden Krankheiten wäre es, Algorithmen an großen medizinischen Datenbanken zu trainieren und auf Grundlage des dort zusammengetragenen Wissens zu besseren Vorhersagen zu kommen. In diesem Kapitel stellen wir eine Vorhersagemethode mit dem Namen Support-Vektor-Maschine (SVM) vor. Sie ermittelt eine optimale Grenze zwischen Bereichen von © Springer-Verlag GmbH Deutschland, ein Teil von Springer Nature 2018 A. Ng und K. Soo, Data Science – was ist das eigentlich?!, https://doi.org/10.1007/978-3-662-56776-0_8

97

98     A. Ng und K. Soo

Datenpunkten, wodurch sich beispielsweise Patienten in die zwei Gruppen „gesund“ und „krank“ einteilen lassen.

8.2 Beispiel: Diagnose einer Herzerkrankung Herzerkrankungen gehören zu den häufigsten gesundheitlichen Beeinträchtigungen in entwickelten Ländern, hierzu zählt insbesondere die Verengung oder Blockade von Herzgefäßen mit dem Risiko eines Herzinfarkts. Die Erkrankung lässt sich mit bildgebenden Verfahren zuverlässig diagnostizieren, diese sind jedoch so teuer, dass sie nicht an allen Patienten routinemäßig durchgeführt werden können. Eine alternative Lösung könnte sein, anhand von bestimmten körperlichen Symptomen eine Gruppe von Risikopatienten zu definieren, bei denen dann in regelmäßigen Abständen Herzscans gemacht würden. Um zu bestimmen, welche Symptome das Vorliegen einer Herzerkrankung am besten vorhersagen, wurden Patienten in einer amerikanischen Klinik gebeten, ein körperliches Trainingsprogramm zu absolvieren, wobei diverse physiologische Daten aufgezeichnet wurden, einschließlich der maximalen Pulsfrequenz während des Trainings. Anschließend wurde mit bildgebenden Verfahren geprüft, ob die Patienten an einer Herzerkrankung litten. Mithilfe eines SVM-Vorhersagemodells, das die Pulswerte mit dem Alter der Patienten verknüpfte, gelang es uns, aus diesen Daten mit einer Vorhersagegenauigkeit von 75 % vorherzusagen, ob jemand an einer Herzerkrankung litt.

8 Support-Vektor-Maschine     99

maximaler Puls beim Training

Im Allgemeinen hatten Patienten mit Herzerkrankung (schwarze Punkte in Abb. 8.1) beim Training eine niedrigere maximale Pulsfrequenz als gesunde Erwachsene (hellgrüne Punkte) des gleichen Alters. Außerdem schien die Krankheit bei Über-55-Jährigen gehäuft aufzutreten.

Alter Abb. 8.1  Diagnose einer Herzerkrankung mit SVM. Die dunkelgrüne Region ist der Bereich von gesunden Erwachsenen, die graue der von Herzpatienten. Hellgrüne und schwarze Punkte repräsentieren einzelne gesunde Erwachsene beziehungsweise Herzpatienten

100     A. Ng und K. Soo

Während der Puls generell mit dem Alter abnahm, zeigten Herzpatienten um die 60 sogar höhere Frequenzen, ähnlich wie junge gesunde Erwachsene, was sich in der „Ausstülpung“ des weißen Gebiets nach oben zeigt. Nur weil SVM in der Lage ist, auch gekrümmte Grenzlinien auszumachen, konnten wir dieses Phänomen aufdecken.

8.3 Die optimale Grenzlinie Die Hauptaufgabe von SVM ist es, eine optimale Grenzlinie zu ermitteln, welche zwei Gruppen von Punkten voneinander trennt. Dies ist nicht so leicht, wie es klingt, denn es gibt unzählige Möglichkeiten (siehe Abb. 8.2). Um die optimale Grenzlinie zu ermitteln, müssen wir zunächst diejenigen Datenpunkte am Rand ihrer jeweiligen Gruppe finden, die am nächsten zu den Punkten

Abb. 8.2  Drei verschiedene Wege, die gleichen zwei Gruppen von Datenpunkten voneinander abzugrenzen

8 Support-Vektor-Maschine     101

ie

lin

o

pp

Su

nz re G le ma ren  op ekto n t-V re or to p k p Ve Su rt-

Abb. 8.3  Die optimale Grenzlinie liegt in der Mitte zwischen den äußersten Punkten der beiden Gruppen

der jeweils anderen Gruppe gelegen sind. Die optimale Grenzlinie verläuft dann in der Mitte zwischen den beiden Linien, welche die Randpunkte beider Gruppen jeweils verbinden (siehe Abb. 8.3). Da diese Randpunkte das Auffinden der optimalen Grenzlinie unterstützen, nennt man sie Support-Vektoren.1 Ein Vorteil von SVM ist, dass der Algorithmus schnell zu berechnen ist. Da zum Festlegen der Grenzlinie nur die Randpunkte betrachtet werden, braucht man viel weniger Rechenzeit als etwa bei der Regressionsanalyse (siehe

1Auf

Englisch heißt Unterstützung support. Und um ausnahmsweise doch einmal ein kleines bisschen Mathematik einzuflechten: Die Punkte heißen tatsächlich deshalb Support- oder Stützvektoren, weil sie im mathematischen Sinn diejenigen Vektoren sind, welche die zu findende Begrenzung als Gerade oder Ebene „aufspannen“, und der Fachausdruck dafür ist „Stützvektor“ (Anm. d. Übers.).

102     A. Ng und K. Soo

Kap. 6), bei der jeder Datenpunkt in die Berechnung einer Trendlinie eingeht. Diese Beschränkung auf einige wenige Datenpunkte hat allerdings auch einen Nachteil: Das Verfahren reagiert empfindlich auf Änderungen in der Lage der Support-Vektoren, und diese hängen natürlich davon ab, welche Datenpunkte als Trainingsdaten ausgewählt wurden. Darüber hinaus sind die Datenpunkte selten so schön sauber in zwei Gruppen aufgeteilt wie in Abb. 8.2 und Abb. 8.3. In der Realität überlappen sie sich meist in komplizierter Weise, etwa so wie in Abb. 8.1. Aus diesem Grund besitzt der SVM-Algorithmus einen speziellen Mechanismus, eine Art Pufferzone, innerhalb derer eine gewisse Zahl von Trainingsdatenpunkten auf die andere Seite wechseln kann. Dies führt zu einer „weicheren“ Grenzlinie, die weniger empfindlich auf Ausreißer reagiert und daher leichter auf neue Datensätze übertragen werden kann. Die Pufferzone entsteht, indem ein sogenannter Kostenparameter optimiert wird, der die Toleranz gegenüber Klassifikationsfehlern beschreibt. Ein größerer Kostenparameter bedeutet mehr Toleranz und daher eine breitere Pufferzone. Damit das erstellte Modell richtige Vorhersagen sowohl für die vorliegenden als auch für neue Daten macht, bestimmen wir den optimalen Wert des Kostenparameters per Kreuzvalidierung (siehe Abschn. 1.4). Eine weitere Stärke von SVM ist die Möglichkeit, gekrümmte Grenzlinien und Muster in den Daten zu beschreiben. Dies können zwar auch viele andere Methoden, SVM zeichnet sich aber durch seine überlegene Recheneffizienz aus, wenn es darum geht, kompliziert

8 Support-Vektor-Maschine     103

gekrümmte Muster zu definieren. Das Erfolgsgeheimnis dabei ist der sogenannte Kernel-Trick. Anstatt direkt eine gekrümmte Grenzlinie in der Datenebene einzuführen, projiziert SVM die Daten zunächst in eine höhere Dimension, wo die Datenpunkte durch eine gerade Linie (beziehungsweise deren höherdimensionales Äquivalent, siehe Abb. 8.4) getrennt werden können. Diese geraden Linien sind leicht zu berechnen und können auch recht einfach auf gekrümmte Linien in der ursprünglichen Datenebene zurückprojiziert werden. Die Möglichkeit, mit SVM Daten in höheren Dimensionen zu bearbeiten, hat die Methode zu einem beliebten Werkzeug für die Analyse von Datensätzen mit vielen Variablen gemacht. Zu den typischen Anwendungen zählen

Abb. 8.4  Ein Kreis von blauen Punkten auf einer zweidimensionalen Fläche könnte von einer geraden Linie begrenzt werden, wenn er auf eine dreidimensionale Kugeloberfläche projiziert wird

104     A. Ng und K. Soo

die Dekodierung von genetischen Daten und das Beurteilen von emotionalen Aussagen in Texten.

8.4 Grenzen Obwohl SVM ein vielseitiges und schnelles Vorhersage-Tool ist, ist es in bestimmten Fällen weniger gut geeignet: Kleine Datensätze: Da SVM die Grenzlinien aus den Support-Vektoren berechnet, kann es in kleinen Datensätzen nicht genug Punkte geben, um eine sinnvolle Grenzlinie ziehen zu können. Viele Gruppen:  SVM kann nur zwei Gruppen auf einmal voneinander trennen. Wenn es mehr als zwei Gruppen gibt, müsste man SVM iterieren, das heißt schrittweise immer zwei Gruppen voneinander trennen. Man nennt das multi-class SVM. Großer Überlapp zwischen Gruppen:  SVM klassifiziert einen Datenpunkt danach, auf welcher Seite der Grenzlinie er liegt. Wenn sich die Bereiche der beiden Datenpunktgruppen stark überschneiden, können Datenpunkte in der Nähe der Grenze leicht falsch eingeordnet werden. Und nicht nur das, SVM bietet auch keine Informationen über die Wahrscheinlichkeit einer Fehleinschätzung. Wir könnten allenfalls den Abstand eines Datenpunkts von der Grenzlinie als Hinweis auf die Zuverlässigkeit der Klassifikation annehmen.

8 Support-Vektor-Maschine     105

8.5 Zusammenfassung • Das Verfahren Support-Vektor-Maschine (SVM) klassifiziert Datenpunkte in zwei Gruppen, indem es in der Mitte zwischen den Randpunkten, hier Support-­ Vektoren genannt, eine Grenzlinie zieht. • SVM ist unempfindlich gegenüber Ausreißern, da es eine Pufferzone benutzt, innerhalb derer einige Datenpunkte auf die andere Seite der Grenzlinie wechseln können. Außerdem erlaubt der sogenannte Kernel-Trick die effiziente Berechnung von gekrümmten Grenzlinien. • SVM funktioniert am besten, wenn Datenpunkte aus großen Datensätzen in zwei gut unterscheidbare Gruppen geteilt werden sollen.

9 Entscheidungsbaum

9.1 Wie man eine Katastrophe überlebt Bei einer Katastrophe wird bestimmten Gruppen von Menschen – etwa Frauen und Kindern – möglicherweise vorrangig geholfen, wodurch sie eine größere Überlebenswahrscheinlichkeit haben. In solchen Situationen können wir mit Entscheidungsbäumen bestimmen, mit welcher Wahrscheinlichkeit die verschiedenen Gruppen überleben. Ein Entscheidungsbaum sagt die Chancen auf ein Überleben anhand einer Reihe von binären Fragen vorher (siehe Abb. 9.1), jede Frage hat also nur zwei mögliche Antworten (zum Beispiel „Ja“ oder „Nein“). Sie beginnen

© Springer-Verlag GmbH Deutschland, ein Teil von Springer Nature 2018 A. Ng und K. Soo, Data Science – was ist das eigentlich?!, https://doi.org/10.1007/978-3-662-56776-0_9

107

108     A. Ng und K. Soo

überleben

Wurzel

sterben

männlich? ja

nein Monatseinkommen über 5000 US-$? ja

nein

0% überleben

100% überleben

75% überleben

Abb. 9.1  Beispiel für einen Entscheidungsbaum

bei der obersten Frage beziehungsweise dem obersten Knoten des Baums, der auch Wurzel genannt wird. Danach bewegen Sie sich den jeweiligen Antworten entsprechend die Kanten entlang – hier Zweige genannt –, bis Sie die Knoten der untersten Ebene erreichen, die Blätter heißen.1 Dort lesen Sie Ihre jeweilige Überlebenswahrscheinlichkeit ab.

1Entscheidungsbäume wachsen in der Regel von oben nach unten. Sie machen das einfach so (Anm. d. Übers.).

9 Entscheidungsbaum     109

9.2 Beispiel: Rettung von der Titanic Wir illustrieren die Verwendung von Entscheidungsbäumen anhand von Passagierdaten des 1912 gesunkenen Ozeandampfers Titanic, die Daten wurden vom britischen „Board of Trade“ zusammengetragen. Es soll dabei ermittelt werden, mit welcher Wahrscheinlichkeit verschiedene Gruppen von Passagieren die Katastrophe überlebt haben. Abb. 9.2 zeigt den hierfür berechneten Entscheidungsbaum. Man sieht sofort, dass von den dargestellten Gruppen männliche Kinder und generell Frauen eine hohe Überlebenschance hatten, sofern sie jeweils nicht das Pech hatten, in der 3. Klasse zu reisen.

Waren Sie …

männlich? ja

nein

erwachsen?

in der 3. Klasse? nein

ja

ja

nein

in der 3. Klasse? ja 20%

27%

nein 100%

46%

93%

Überlebenswahrscheinlichkeit

Abb. 9.2  Entscheidungsbaum für die Überlebenswahrscheinlichkeit auf der Titanic

110     A. Ng und K. Soo

Entscheidungsbäume haben ausgesprochen vielfältige Anwendungen, so zum Beispiel die Prognose von Heilungschancen nach einer bestimmten medizinischen Diagnose, Tipps für die Wahrscheinlichkeit, dass Minister der US-Regierung entlassen werden, oder das Aufdecken von betrügerischen Transaktionen. Sie können sowohl bei kategorialen Variablen (zum Beispiel männlich/weiblich) als auch bei solchen mit stetigen Werten eingesetzt werden (zum Beispiel Monatseinkommen). Stetige Werte lassen sich nämlich leicht in Gruppen zusammenfassen – etwa „größer/kleiner als der Durchschnitt“. In Entscheidungsbäumen gibt es normalerweise nur zwei mögliche Antworten an jeder Verzweigung, also etwa „ja“ oder „nein“. Wenn wir jedoch drei oder mehr Antworten zulassen wollen (zum Beispiel „ja“, „nein“ und „manchmal“), fügen wir einfach weitere Zweige hinzu (siehe Abb. 9.3). Entscheidungsbäume werden gerne eingesetzt, weil sie sehr leicht zu interpretieren sind. Es bleibt allerdings die Frage, wie wir einen Entscheidungsbaum am besten konstruieren.

9.3 Einen Entscheidungsbaum erstellen Wir „pflanzen“ einen Entscheidungsbaum, indem wir zunächst alle Datenpunkte in zwei Gruppen einteilen, sodass ähnliche Datenpunkte beieinander liegen, und dann diese Gruppen weiter binär aufsplitten (Abb. 9.4).

9 Entscheidungsbaum     111

überleben

Wurzel

sterben

männlich? ja

nein Monatseinkommen über 5000 US-$? ja

0% überleben

nicht ja Monatseinkommen über 5000 US-$? manchmal

nein

100% überleben

100% überleben

50% überleben

Abb. 9.3  Mehr als zwei Antwortmöglichkeiten bei einem Entscheidungsbaum

Im Ergebnis hängen unter jeder Verzweigung (jedem Knoten) sowohl weniger als auch homogenere Datenpunkte. Die Grundidee bei Entscheidungsbäumen ist somit, dass Datenpunkte, zu denen man von der Wurzel auf demselben Pfad gelangt, sich höchstwahrscheinlich sehr ähneln. Der Prozess, bei dem man durch wiederholtes Aufteilen immer homogenere Untergruppen erhält, heißt rekursive Partitionierung und besteht nur aus den folgenden zwei Schritten:

112     A. Ng und K. Soo 1 Wurzel Y

Ist X > 0,5? ja

nein

ja

X

0

Ist Y > 0,5?

1

nein Ist X > 0,25? ja

nein

Abb. 9.4  Einteilung von Datenpunkten per Entscheidungsbaum und Visualisierung in einem Streudiagramm

• Schritt 1: Finde die binäre Frage, welche die Datenpunkte am besten in zwei möglichst homogene Gruppen teilt. • Schritt 2: Wiederhole Schritt 1 für jeden Knoten, bis ein Abbruchkriterium erfüllt ist. Es gibt verschiedene denkbare Abbruchkriterien, man wählt auch hier sinnvollerweise durch Kreuzvalidierung aus (siehe Abschn. 1.4). Dazu zählen: • Stopp, wenn die Datenpunkte an jedem Blatt von ­derselben Kategorie sind oder denselben Wert haben, • Stopp, wenn die Blätter weniger als fünf Datenpunkte enthalten,

9 Entscheidungsbaum     113

• Stopp, wenn weitere Verzweigungen die Homogenität nicht weiter verbessern oder eine vorgegebene Mindesthomogenität erreicht ist. Da die rekursive Partitionierung nur die aufschlussreichsten binären Fragen zum Aufbau eines Entscheidungsbaums benutzt, würde die Anwesenheit von nicht-signifikanten Variablen die Ergebnisse nicht beeinflussen. Außerdem versammeln binäre Fragen die Datenpunkte tendenziell um gewisse zentrale Werte, sodass Entscheidungsbäume robust gegen Ausreißer sind.

9.4 Grenzen Entscheidungsbäume sind erfreulich leicht zu interpretieren, aber auch sie haben ihre Schwächen: Instabilität:  Da Entscheidungsbäume durch das Aufteilen von Datenpunkten in möglichst homogene Gruppen entstehen, kann eine kleine Änderung der Daten unter Umständen die Aufteilung deutlich verändern und zu einem ganz anderen Baum führen. Und weil Entscheidungsbäume jedes Mal nach der besten Aufteilung der Datenpunkte suchen, sind sie anfällig für Überanpassungen (siehe Abschn. 1.3). Ungenauigkeit:  Die beste binäre Frage für die erste Aufteilung der Daten zu verwenden, führt nicht immer zu den genauesten Vorhersagen. Manchmal bekommt man

114     A. Ng und K. Soo

mit weniger effizienten ersten Aufteilungen am Ende bessere Vorhersagen. Um dem entgegenzuwirken, können wir davon absehen, immer die beste Aufteilung zu fordern, und stattdessen unsere Entscheidungsbäume diversifizieren. Wir kombinieren dann die mit unterschiedlichen Bäumen erzielten Vorhersagen, wodurch die Resultate stabiler und genauer werden. Es gibt zwei Methoden, um Entscheidungsbäume zu diversifizieren: • Das erste Verfahren wählt zufällige Kombinationen von binären Fragen, um viele unterschiedliche Bäume zu erzeugen, deren Vorhersagen dann gemittelt oder anders aggregiert werden. Diese Technik bezeichnet man als Random Forest (siehe Kap. 10). • Anstelle einer Zufallsauswahl von binären Fragen wählt die zweite Methode binäre Fragen so aus, dass die Vorhersagegenauigkeit jedes Mal ein bisschen besser wird. Als Ergebnis nimmt man dann ein gewichtetes Mittel der Vorhersagen aller Bäume. Dieses Verfahren heißt Gradient Boosting. Während Random Forest und Gradient Boosting tendenziell bessere Vorhersagen produzieren, sind die damit erhaltenen Lösungen wegen ihrer höheren Komplexität schwieriger zu visualisieren, weswegen sie als „Blackboxes“ gelten. Dies erklärt, warum die klassischen Entscheidungsbäume weiterhin gerne eingesetzt werden, denn mit ihren leicht zu visualisierenden Ergebnissen lassen sich die Prädiktoren und ihre Interaktionen gut einschätzen.

9 Entscheidungsbaum     115

9.5 Zusammenfassung • Ein Entscheidungsbaum trifft Vorhersagen anhand einer Abfolge von binären Fragen. • Die Daten werden auf diese Weise schrittweise aufgeteilt, bis sie in eine Anzahl hinreichend homogener Gruppen zerfallen. Dieser Prozess heißt rekursive Partitionierung. • Entscheidungsbäume sind leicht zu benutzen und zu verstehen, jedoch anfällig für Überanpassung, was zu inkonsistenten Resultaten führen kann. Dem kann man mit alternativen Techniken wie Random Forests oder Gradient Boosting begegnen.

10 Random Forests

10.1 Die Weisheit der Crowd Kann ganz oft falsch richtig sein? Ja! Obwohl es der Intuition zuwiderläuft, ist dies bei einigen der besten Vorhersagemodelle nicht nur möglich – sondern sogar zu erwarten. Hinter diesem Bonmot steckt die Einsicht, dass es zwar immer viele falsche Vorhersagen, aber nur eine korrekte gibt. Wenn wir Modelle mit unterschiedlichen Stärken und Schwächen kombinieren, bestärken diejenigen mit zutreffenden Vorhersagen einander, während sich die falschen Vorhersagen gegenseitig aufheben. Die Idee, durch die Kombination von Modellen die Vorhersagegenauigkeit zu verbessern, ist als Ensembling oder Ensemble-Lernen bekannt. © Springer-Verlag GmbH Deutschland, ein Teil von Springer Nature 2018 A. Ng und K. Soo, Data Science – was ist das eigentlich?!, https://doi.org/10.1007/978-3-662-56776-0_10

117

118     A. Ng und K. Soo

Gut zu beobachten ist dieser Effekt in einem Random Forest, einer Ensemble genannten Kombination von Entscheidungsbäumen (siehe Abschn. 10.3 und Kap. 9). Um zu zeigen, dass ein Random Forest besser arbeitet als seine Mitglieder jeweils allein, haben wir 1000 mögliche Entscheidungsbäume erzeugt, die jeweils die Häufigkeit von Verbrechen in einer US-amerikanischen Großstadt vorhersagen sollen. Deren Vorhersagegenauigkeiten haben wir dann mit der von einem aus ihnen abgeleiteten Random Forest verglichen.

10.2 Beispiel: Verbrechensvorhersage Uns standen offene Daten des San Francisco Police Department aus den Jahren 2014 bis 2016 zur Verfügung, sie enthielten Informationen über Ort, Datum und Schwere von Verbrechen in der Stadt. Da die Forschung nahelegt, dass Verbrechen an heißeren Tagen wahrscheinlicher sind, haben wir lokale Wetterdaten (Tagestemperaturen und Niederschläge) aus diesem Zeitraum hinzugefügt. Wir nahmen an, dass es für die Polizei wegen ihrer begrenzten Personalressourcen nicht praktikabel ist, in alle Regionen mit vorhergesagten Verbrechenshäufigkeiten zusätzliche Sicherheitspatrouillen zu schicken. Darum haben wir unser Vorhersagemodell so programmiert, dass es von allen Gebieten diejenigen 30 % heraussucht, in denen die höchsten Wahrscheinlichkeiten für tägliche Gewaltverbrechen herrschen, sodass dort prioritär zusätzliche Streifenbeamte auf Patrouille geschickt werden können.

10  Random Forests     119

Eine vorgeschaltete Analyse zeigte, dass Verbrechen vor allem im Nordosten der Stadt (in dem Rechteck oben rechts in Abb. 10.1) verübt werden. Darum teilten wir diese Region für die weitere Analyse in kleinere Rechtecke mit den Abmessungen 260 m × 220 m. Um vorherzusagen, wann und wo ein Verbrechen geschehen könnte, wurden 1000 mögliche Entscheidungsbäume erzeugt, und zwar auf Grundlage der Verbrechenszahlen und der Wetterdaten. Anschließend wurden die Bäume dann zu einem Random Forest zusammengefasst. Wir verwendeten die Daten der Jahre 2014 und 2015, um die Vorhersagemodelle zu trainieren, und testeten deren Genauigkeit dann mit den Daten von 2016 (Januar bis August). Und wie gut war unsere Verbrechensvorhersage?

Abb. 10.1  Eine sogenannte Heatmap der Verbrechenshäufigkeit in San Francisco; grau: sehr selten, gelb: selten, orange: mäßig oft und rot: hoch

120     A. Ng und K. Soo

Das Random-Forest-Modell sagte 72 % (fast drei Viertel) aller Gewaltverbrechen korrekt voraus. Dies war merklich besser als der Durchschnitt der Vorhersagegenauigkeiten der 1000 Einzelbäume, welcher bei 67 % lag (siehe Abb. 10.2). Nur zwölf der 1000 einzelnen Entscheidungsbäume hatten eine Vorhersagegenauigkeit, die besser als die des Random Forests war, wir konnten also zu 99 % sicher sein, dass die Vorhersagen des Random Forests besser sind als die eines einzelnen Entscheidungsbaums. Abb. 10.3 zeigt als Beispiel die Vorhersagen des Random Forests für vier aufeinanderfolgende Tage. Diese legen nahe, dass die Polizei ihre Ressourcen in den rot markierten Bereichen konzentrieren und aus den grauen abziehen sollte (falls sie da bisher noch tätig war). Während es offensichtlich erscheint, dass die Polizei sich in

Anzahl der Bäume

0,72

0,55

0,60

0,65

0,70

0,75

0,80

0.85

Vorhersagegenauigkeit

Abb. 10.2  Histogramm der Vorhersagegenauigkeiten von 1000 Entscheidungsbäumen (Mittelwert: 67 %), die Vorhersagegenauigkeit des kombinierten Random Forests liegt mit 72 % darüber

10  Random Forests     121

Tag 1

Tag 2

Tag 3

Tag 4

Abb. 10.3  Verbrechensvorhersagen für vier aufeinanderfolgende Tage im Jahr 2016. Offene Kreise bezeichnen Orte, für die ein Gewaltverbrechen vorhergesagt wurde. Schwarze Kreise stehen für korrekte Vorhersagen. Kreuze bezeichnen Orte mit nicht vorhergesagten Gewaltverbrechen

122     A. Ng und K. Soo

Gegenden mit traditionell hohen Verbrechensraten sehen lassen sollte, ging das Modell noch weiter und konnte auch die Wahrscheinlichkeit von Verbrechen in nicht-roten Bereichen abschätzen. So wurde für Tag 4 in der Region rechts unten ein Gewaltverbrechen in einem grauen Bezirk korrekt vorhergesagt, obwohl es in den drei Tagen davor dort keine Verbrechen gegeben hatte. Ein Random-Forest-Modell erlaubt uns auch zu untersuchen, welche Variablen den größten Beitrag zu seiner Vorhersagegenauigkeit geleistet haben. Wie in Abb. 10.4 zu sehen ist, lassen sich Verbrechen mit Abstand am besten aus der durchschnittlichen Häufigkeit von Verbrechen vorhersagen, außerdem auch aus dem Ort, dem Tag im Jahr und der Maximaltemperatur. Zahl der Verbrechen im letzten Monat Zahl der Verbrechen in der letzten Woche Zahl der Verbrechen am vorigen Tag Ort Tag im Jahr maximale Temperatur Temperaturabweichung minimale Temperatur Wochentag Durchschnistemperatur Niederschlag Monat

Abb. 10.4  Variablen, die am meisten zur Vorhersagegenauigkeit des Random Forests zur Verbrechensvorhersage beigetragen haben

10  Random Forests     123

Wie Sie sehen, können Random Forests sehr effektiv komplexe Phänomene wie Gewaltverbrechen vorhersagen. Aber wie funktionieren sie?

10.3 Ensembles Ein Random Forest ist ein Ensemble von Entscheidungsbäumen. Ein Ensemble steht in diesem Zusammenhang für ein Vorhersagemodell, das durch die Kombination der Vorhersagen vieler verschiedener Einzelmodelle entsteht, etwa durch Mehrheitsentscheid oder die Bildung von Mittelwerten. Abb. 10.5 zeigt, dass ein Ensemble mit Mehrheitsentscheid genauere Vorhersagen liefert als die darin enthaltenen Einzelmodelle. Dies liegt daran, dass korrekte Vorhersagen einander bestärken, während Fehler sich Modell 1

70% korrekt

Modell 2

70% korrekt

Modell 3

60% korrekt

Ensemble

80% korrekt

Abb. 10.5  Drei Beispielmodelle für die Vorhersage von zehn Antworten auf eine binäre Frage (entweder blau oder rot). Die korrekte Vorhersage war in allen zehn Fällen blau. Ein Ensemble aus diesen drei Modellen, das mit Mehrheitsentscheid arbeitet, hatte eine höhere Vorhersagegenauigkeit als die drei Einzelmodelle

124     A. Ng und K. Soo

gegenseitig aufheben. Das Ensembling funktioniert allerdings nur, wenn die enthaltenen Modelle nicht alle dieselben Fehler machen, mit anderen Worten, die Modelle müssen unkorreliert sein. Ein systematischer Weg, um unkorrelierte Entscheidungsbäume zu erzeugen, ist das sogenannte Bootstrap Aggregating oder, verkürzt, Bagging.1

10.4 Bootstrap Aggregating Wir haben in Kap. 9 erwähnt, dass beim Aufbau eines Entscheidungsbaums ein Datensatz wiederholt in Teilbäume aufgeteilt wird, man orientiert sich dabei an der besten Variablenkombination. Es kann jedoch ziemlich schwierig sein, diese beste Kombination zu finden, da Entscheidungsbäume zur Überanpassung neigen (vergleiche Abschn. 1.3). Dem können wir gegensteuern, indem wir eine Vielzahl von Entscheidungsbäumen mit jeweils zufälligen Kombinationen und Anordnungen der Variablen konstruieren. Das so gewonnene Ensemble wird dann zu einem Random Forest zusammengefasst. Bootstrap Aggregating dient dazu, Tausende von Entscheidungsbäumen zu generieren, die sich alle gleichermaßen voneinander unterscheiden. Um eine möglichst 1Der Name kommt vermutlich daher, dass man sich im Englischen nicht wie Baron Münchhausen am eigenen Schopf aus dem Sumpf zieht, sondern am Stiefelriemen = „Bootstrap“. Aus demselben Grund „bootet“ man übrigens seinen Computer (Anm. d. Übers.).

10  Random Forests     125

niedrige Korrelation zwischen den Bäumen sicherzustellen, wird jeder Baum aus einer zufällig gewählten Untermenge der Trainingsdaten erzeugt, und dies mit einer zufälligen Untermenge der Prädiktorvariablen. So entstehen viele signifikant voneinander verschiedene Entscheidungsbäume, die jedoch alle eine gewisse Vorhersagekraft besitzen. Abb. 10.6 zeigt, wie die Prädiktorvariablen zufällig auf die einzelnen Knoten beziehungsweise Verzweigungen verteilt werden. In Abb. 10.6 gibt es insgesamt neun Prädiktorvariablen (farbige Kreise). Bei jeder Verzweigung werden zufällig drei Prädiktorvariablen ausgewählt, aus denen der Entscheidungsbaum-Algorithmus dann die jeweils beste Variable auswählt.

Wurzel

ja

nein ja

nein ja

nein

Abb. 10.6  So lässt Bootstrap Aggregating Entscheidungsbäume für den Random Forest wachsen

126     A. Ng und K. Soo

Indem wir die Zahl der möglichen Prädiktoren für jede Verzweigung beschränken, erzeugen wir immer wieder einen anderen Baum und vermeiden so Überanpassungen. Um die Überanpassung noch weiter zu reduzieren, könnten wir die Zahl der Bäume im Random Forest erhöhen, wodurch unser Modell noch präziser und noch generalisierbarer würde.

10.5 Grenzen Kein Modell ist perfekt. Wenn man sich für ein Random-Forest-Modell entscheidet, gewinnt man an Vorhersagekraft, muss dies aber mit einer verringerten Interpretierbarkeit der Ergebnisse bezahlen. Nicht zu interpretieren:  Random Forests muss man als Blackboxes betrachten, da sie aus zufällig erzeugten Entscheidungsbäumen bestehen und ihnen keine klaren Vorhersageregeln zugrunde liegen. Wir können daher nicht sagen, wie ein Random-Forest-Modell eigentlich auf sein Resultat gekommen ist – etwa die Vorhersage, dass ein Verbrechen dann und dort geschehen wird – außer, dass die Mehrheit seiner Entscheidungsbäume zu demselben Schluss gekommen ist. Diese Unklarheit über das Zustandekommen der Vorhersagen kann durchaus ethische Probleme aufwerfen, etwa wenn es um medizinische Diagnosen oder präventive Zwangsmaßnahmen geht. Trotzdem werden Random Forests oft eingesetzt, da sie leicht zu implementieren sind – besonders dort, wo

10  Random Forests     127

es mehr auf die Vorhersagegenauigkeit als auf die Interpretation der Ergebnisse ankommt.

10.6 Zusammenfassung • Ein Random Forest besitzt in der Regel eine bessere Vorhersagegenauigkeit als einzelne Entscheidungsbäume. Hierzu verhelfen ihm zwei Methoden: Bootstrap Aggregating und Ensembling oder Ensemble-­ Lernen. • Bootstrap Aggregating erzeugt eine große Zahl von unkorrelierten Entscheidungsbäumen, indem bei deren Aufbau zufällig einige Variablen „aus dem Spiel genommen“ werden. Ensembling wiederum bedeutet das Kombinieren der von diesen Bäumen gemachten Vorhersagen, etwa per Mehrheitsentscheid. • Die mit einem Random Forest erhaltenen Ergebnisse können nicht interpretiert werden, man kann aber immerhin die Prädiktoren nach ihren jeweiligen Beiträgen zur Vorhersagegenauigkeit klassifizieren.

11 Neuronale Netze

11.1 Bauen Sie sich ein Gehirn! Werfen Sie einen Blick auf Abb. 11.1. Was sehen Sie? Es dürfte Ihnen keine Schwierigkeiten bereiten, auf dem Bild eine – schwer übergewichtige – Giraffe zu erkennen. Das menschliche Gehirn mit seinen rund 80 Mrd. Neuronen hat die bemerkenswerte Fähigkeit, Objekte auch dann problemlos richtig zu klassifizieren, wenn sie deutlich anders aussehen als gewohnt. Diese Neuronen verarbeiten Input-Signale, zum Beispiel das Bild einer dicken Giraffe, zu einem Output – im Beispiel das Etikett „(trotzdem) Giraffe“. Die Funktionsweise der Neuronennetzwerke in unserem Gehirn ist das Vorbild für den Algorithmus der neuronalen Netze. © Springer-Verlag GmbH Deutschland, ein Teil von Springer Nature 2018 A. Ng und K. Soo, Data Science – was ist das eigentlich?!, https://doi.org/10.1007/978-3-662-56776-0_11

129

130     A. Ng und K. Soo

Abb. 11.1  Raten Sie einmal, was das ist!

Neuronale Netze sind unter anderem die Basis der modernen automatischen Bilderkennung, mittlerweile übertreffen sie echte Menschen sowohl in der Geschwindigkeit als auch der Vorhersagegenauigkeit. Die jüngsten Erfolge dieser Methode beruhen vor allem auf drei Faktoren:

11  Neuronale Netze     131

• Verbesserte Speicherung und Zugänglichkeit von Daten: Dadurch steht eine große Menge einschlägiger Daten für das Training von neuronalen Netzen zur Verfügung, wovon deren Performance erheblich profitiert hat. • Erhöhte Rechenleistung: Spezialisierte Grafikprozes­ soren, die bis zu 150-mal schneller sind als normale Mikroprozessoren, wurden zwar vor allem für HighEnd-Computerspiele entwickelt, doch sie eignen sich bestens für das Training von neuronalen Netzen an sehr großen Datensätzen. • Neue Algorithmen: Während es zwar in vielen Aspekten schwierig bleibt, mit Maschinen die Leistungsfähigkeit der Neuronen im menschlichen Gehirn zu erreichen, haben neue Methoden und Algorithmen die Performance der maschinellen Mustererkennung signifikant gesteigert. Einige von ihnen werden in diesem Kapitel vorgestellt. Die automatische Bilderkennung ist ein fantastisches Beispiel für die Fähigkeiten neuronaler Netze. Sie kommt mittlerweile in vielen Bereichen zum Einsatz, etwa in visuellen Überwachungssystemen oder bei der Navigation von autonomen Fahrzeugen. Selbst im Smartphone wird sie heute schon genutzt, nämlich beim maschinellen Lesen von Handschriften. Sehen wir uns an, wie man so etwas einem neuronalen Netz beibringt.

132     A. Ng und K. Soo

11.2 Beispiel: Handgeschriebene Zahlen erkennen Für dieses Beispiel haben wir Bilder von mit der Hand geschriebenen Zahlen, genauer gesagt einzelnen Ziffern, aus der MNIST-Datenbank des US-amerikanischen National Institute of Standards and Technology benutzt. Einen Ausschnitt des Datensatzes sehen Sie in Abb. 11.2. Damit eine Maschine diese Bilder lesen kann, mussten wir sie zunächst in Pixel übersetzen. Schwarze Pixel erhielten den Wert „0“, weiße den Wert „1“ (Abb. 11.3). Bei einem farbigen Bild hätten wir die jeweiligen Werte in den RGB-Farben Rot, Grün und Blau abgespeichert. Sind die Bilder in eine Folge von digitalen Zahlen übersetzt, lassen sich diese Werte in ein neuronales Netz eingeben. Wir trainierten unser Netz mit insgesamt 10.000 handgeschriebenen Ziffern, dazu erhielt es auch jeweils

Abb. 11.2  Mit der Hand geschriebene Ziffern aus der MNIST-Datenbank

11  Neuronale Netze     133 0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

0

0

0

0

0

0

0

0

0

0

0

1

1

1

0

0

0

0

0

0

0

0

0

0

0

0

1

1

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0

0

1

1

1

1

1

1

0

0

0

0

0

0

0

1

0

1

1

0

0

0

0

1

1

0

0

0

0

0

0

1

1

1

0

0

0

0

0

0

1

0

0

0

0

0

0

1

1

1

0

0

0

0

0

0

1

0

0

0

0

0

0

0

1

1

0

0

0

0

0

1

1

0

0

0

0

0

0

0

0

1

1

0

0

0

1

1

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0

0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0

0 0 0 1 1 0 0 0 0 1 1 1 1 1 0 0

0 0 1 1 0 0 0 0 1 1 0 0 0 1 1 0

0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0

0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0

0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0

0 1 0 0 0 0 0 0 1 0 0 0 0 1 1 0

0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0

0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Abb. 11.3  Ein Bild wird in Pixel übersetzt. Erkennt das neuronale Netz in Ihrem Gehirn die „6“ im rechten Bild?

die Zahl, welche das Bild darstellen sollte. Nachdem das neuronale Netz gelernt hatte, die Bilder mit den richtigen Zahlen zu verbinden, testeten wir, ob es 1000 neue handgeschriebene Ziffern ohne Angabe ihrer Bedeutung richtig lesen konnte. Von den 1000 handschriftlichen Ziffern erkannte das neuronale Netz 922 korrekt – eine Vorhersagegenauigkeit von 92,2 %. Aus der Kontingenztafel in Abb. 11.4 lässt sich ablesen, an welchen Stellen die relativ wenigen Fehler aufgetreten sind. Wir lesen aus Abb. 11.4 ab, dass die Ziffern „0“ und „1“ so gut wie immer korrekt erkannt wurden, während die Ziffer „5“ am schwierigsten zu entziffern war. Schauen wir uns die Lesefehler etwas genauer an. Es wurde beispielsweise die Ziffer „2“ in etwa 8 % der Fälle als „7“ oder „8“ gelesen. Während das menschliche Auge (beziehungsweise die ihm nachgeschalteten Neuronen) die Ziffern in Abb. 11.5 alle als „2“ erkannt

134     A. Ng und K. Soo

gelesene Ziffer

tatsächliche Ziffer

0 1 2 3 4 5 6 7 8 9 gesamt % 0 84 0 0 0 0 0 1 0 0 0 85 99 1 0 125 0 0 0 0 1 0 0 0 126 99 2 1 0 105 0 0 0 0 4 5 1 116 91 3 0 0 3 96 0 6 0 1 0 1 107 90 4 0 0 2 0 99 0 2 0 2 5 110 90 5 2 0 0 5 0 77 1 0 1 1 87 89 6 3 0 1 0 1 2 80 0 0 0 87 92 7 0 3 3 0 1 0 0 90 0 2 99 91 8 1 0 1 3 1 0 0 2 81 0 89 91 9 0 0 0 0 1 0 0 6 2 85 94 90 gesamt 91 128 115 104 103 85 85 103 91 95 1000 92

Abb. 11.4  Kontingenztafel für die Leistungsfähigkeit des neuronalen Netzes. Die erste Zeile besagt, dass 84 von 85 Bildern der Ziffer „0“ korrekt erkannt wurden, die 85. „0“ wurde fälschlich als „6“ gelesen. Die Spalte ganz rechts gibt die Vorhersagegenauigkeit an, bei der „0“ waren es 99 %

Ziffer 7: 99 % Ziffer 3: 1 %

Ziffer 7: 94 % Ziffer 2: 5 % Ziffer 3: 1 %

Ziffer 8: 48 % Ziffer 2: 47 % Ziffer 3: 4 % Ziffer 1: 1 %

Ziffer 8: 58 % Ziffer 2: 27 % Ziffer 6: 12 % Ziffer 0: 2 % Ziffer 5: 1 %

Abb. 11.5  Falsche Klassifikation der Ziffer „2“

11  Neuronale Netze     135

Ziffer 5: 90 % Ziffer 3: 9 % Ziffer 0: 1 %

Ziffer 3: 57 % Ziffer 5: 38 % Ziffer 8: 5 %

Ziffer 3: 50 % Ziffer 5: 49 % Ziffer 0: 1 %

Ziffer 3: 87 % Ziffer 5: 8 % Ziffer 1: 4 % Ziffer 2: 1 %

Abb. 11.6  Die Ziffern „3“ und „5“ wurden relativ häufig verwechselt

hätte, könnte ein neuronales Netz beispielsweise darüber stolpern, dass manchmal der „Schwanz“ an der „2“ fehlt. Interessanterweise hat das neuronale Netz in 10 % der Fälle die Ziffern „3“ und „5“ miteinander verwechselt (siehe Abb. 11.6). Trotz dieser Fehler erreichte das neuronale Netz insgesamt eine hohe Vorhersagegenauigkeit und war darüber hinaus viel schneller als jeder Mensch.

11.3 Wie ein neuronales Netz denkt Um seine bemerkenswerten Fähigkeiten anzuwenden, etwa handgeschriebene Zahlen zu lesen, benutzt ein neuronales Netz seine in Schichten (auch Layer genannt) angeordneten Neuronen. Der Output einer Schicht ist dabei jeweils der Input für die nächste.

136     A. Ng und K. Soo

In Abb. 11.7 sehen Sie ein neuronales Netz, in welches zwei verschiedene Versionen der Ziffer „6“ eingegeben werden. Die unterschiedlichen Schreibweisen der „6“ aktivieren verschiedene Neuronen in den beiden dargestellten Schichten, werden aber am Ende zu derselben Vorhersage als Output führen. Obwohl jede Kombination von aktivierten Neuronen nur zu einer Vorhersage führt, kann jede Vorhersage von einer Vielzahl von unterschiedlichen Kombinationen aktivierter Neuronen herrühren. Ein typisches neuronales Netz besteht aus den folgenden Komponenten: • Input-Schicht: Diese Schicht verarbeitet jedes Pixel eines eingehenden Bilds. Insofern enthält sie in der Regel gerade so viele Neuronen, wie das Bild Pixel hat. Der Einfachheit halber fassen wir aber alle diese Neuronen in Abb. 11.7 zu einem einzelnen Knoten zusammen. Schicht 1 A Input

B C D

Schicht 1 A Schicht 2

Schicht 2 E F G

Output 6

Input

B C D

E F

Output 6

G

Abb. 11.7  Beispiel eines neuronalen Netzes, das zwei verschiedene Inputs erhält, bei dem aber in beiden Fällen eine „6“ ausgeben wird. Gerade aktivierte Neuronen sind rot dargestellt

11  Neuronale Netze     137

Um die Vorhersagen zu verbessern, könnte man noch eine sogenannte Faltungsschicht1 anfügen. Anstatt die Pixel alle einzeln zu bearbeiten, erkennt solch eine Schicht bestimmte Kombinationen von Pixeln, etwa einen Kreis oder eine nach oben weisende Linie (die zusammen eine Ziffer „6“ ausmachen). Da diese Art der Analyse nur von der Anwesenheit dieser Strukturen und nicht von ihrem Ort abhängt, würde ein solches neuronales Netz die Ziffern selbst dann erkennen können, wenn die charakteristischen Strukturen räumlich verschoben wären – diese Eigenschaft nennt man Translationsinvarianz. • Zwischenschichten oder versteckte Schichten: Nachdem das Bild in das neuronale Netz eingespeist ist, durchlaufen die Daten nacheinander verschiedene Schichten, in denen sie so transformiert werden, dass sie einem von denjenigen Bildern immer ähnlicher werden, an denen das Netz trainiert wurde und deren „Bedeutung“ es kennt. Eine große Zahl an solchen Schichten führt meist nicht zu einer wesentlich höheren Vorhersagegenauigkeit, vergrößert aber die Rechenzeit erheblich. Daher begnügt man sich meist mit relativ wenigen Schichten.2 In jeder Schicht sollte die Anzahl der Neuronen proportional zur Zahl der Bildpixel sein.

1Auf

Englisch convolution layer. In dieser Schicht wird nichts gefaltet, „Faltung“ ist vielmehr eine mathematische Technik, auf die wir hier zum Glück nicht weiter einzugehen brauchen (Anm. d. Übers.). 2Die jüngsten, besonders beeindruckenden Erfolge von neuronalen Netzen beruhen allerdings doch darauf, dass die Zahl der Schichten deutlich erhöht wurde. Dies ist das im Vorwort erwähnte „Deep Learning“ (Anm. d. Übers.).

138     A. Ng und K. Soo

•

•





In unserem Beispiel aus dem vorigen Abschnitt hatten die Zwischenschichten 500 Neuronen. Output-Schicht: Die Vorhersage beziehungsweise Antwort des neuronalen Netzes findet sich in dieser letzten Schicht, die aus nur einem Neuron bestehen kann oder auch aus so vielen, wie es mögliche Ergebnisse gibt. Loss-Schicht: Nicht dargestellt in Abb. 11.7 ist eine Schicht, die nur beim Training des neuronalen Netzes benötigt wird. Sie ermittelt, wie weit die Vorhersage des Netzes von dem beim Training ja bekannten wahren Wert abweicht, und bewertet diese Abweichung mit einer Kostenfunktion, welche in diesem Fall auf Englisch loss function genannt wird. Die Loss-Schicht ist essenziell für das Training eines neuronalen Netzes. Wenn eine korrekte Vorhersage getroffen wurde, verstärkt das Feedback von der LossSchicht die aktivierten Neuronen und Verbindungen, welche zu dieser Vorhersage geführt haben. Bei einer falschen Vorhersage wird der Fehler zurückverfolgt und die Aktivierungskriterien werden so verändert, dass sich der Fehler reduziert, also die Kostenfunktion einen kleineren Wert annimmt. Dies nennt man Backpropagation (auf Deutsch so viel wie Rückverfolgung). Mithilfe dieses iterativen Trainingsprozesses lernt das neuronale Netz, die Input-Signale mit den korrekten Output-Antworten zu assoziieren. Diese „gelernten“ Verbindungen sind nach dem Training als Aktivierungsregeln in den betreffenden Neuronen einprogrammiert. Daher können wir die Vorhersagegenauigkeit eines neuronalen Netzes dadurch verbessern, dass wir die Komponenten optimieren, welche seine Aktivierungsregeln festlegen.

11  Neuronale Netze     139

11.4 Aktivierungsregeln Um Vorhersagen zu treffen, müssen die Neuronen entlang eines Pfads durch die Schichten des neuronalen Netzes Schritt für Schritt aktiviert werden. Die Aktivierung eines Neurons wird jeweils von seiner Aktivierungsregel bestimmt, diese gibt an, von welchem vorgeschalteten Neuron Signale kommen müssen – und mit welcher Stärke –, damit das Neuron aktiviert wird. Diese Regel beziehungsweise ihre Parameter werden während des ­Trainings optimiert. Abb. 11.8 zeigt eine fingierte Aktivierungsregel für das Neuron G auf der linken Seite von Abb. 11.7. Nach dem Training hat das neuronale Netz gelernt, dass Neuron G mit den Neuronen A, C und D aus der vorigen Schicht verbunden sein sollte. Anders ausgedrückt: Nur Signale von diesen drei Neuronen können G aktivieren. Die Verbindungen zwischen den Neuronen können unterschiedliche Stärken haben, die man meist Gewichte Schicht 1 A

w

B

w=

C

w=1 1 w=-

D

=3 0

Schicht 2 G Schwellenwert = 3

Abb. 11.8  Beispiel für eine Aktivierungsregel

140     A. Ng und K. Soo

nennt und durch den Parameter w ausdrückt. Beispielsweise sehen wir in Abb. 11.8, dass eine Aktivierung von Neuron A ein stärkeres Signal (w = 3) zu Neuron G senden würde als die von Neuron C (w = 1). Der Parameter hat außerdem ein Vorzeichen, sodass eine Aktivierung von Neuron D (w = −1) tatsächlich die Aktivierung von Neuron G herabsetzen würde. Wir bestimmen das Gesamteingangssignal an Neuron G, indem wir alle Gewichte von aktivierten Neuronen in der vorigen Schicht aufsummieren (Neuronen, mit denen G nicht verbunden ist, haben das Gewicht 0). Wenn das Ergebnis dieser Rechnung über einem bestimmten Schwellenwert liegt, wird Neuron G aktiviert. In Abb. 11.8 ist das Eingangssignal an G 3 + (−1) = 2. Da der Schwellenwert von Neuron G jedoch 3 beträgt, bleibt G in diesem Fall inaktiv. Die optimalen Werte für die Gewichte und Schwellenwerte zu bestimmen, ist essenziell für Aktivierungsregeln, die zu korrekten Vorhersagen führen. Es gibt übrigens noch weitere Parameter in neuronalen Netzen, die ebenfalls optimiert werden müssen, etwa die Zahl der Zwischenschichten und die Anzahl der Neuronen pro Schicht. Geeignete Werte für diese Parameter könnte man mit dem Gradientenverfahren bestimmen (siehe Abschn. 6.3).

11.5 Grenzen Neuronale Netze haben das Potenzial, das menschliche Gehirn zu emulieren. Auf dem Weg dorthin müssen aber noch einige Schwierigkeiten überwunden werden. Dafür wurden mehrere Techniken entwickelt.

11  Neuronale Netze     141

Umfangreiche Trainingsdaten: Die Komplexität eines neuronalen Netzes ermöglicht es ihm, komplizierte Strukturen in den Input-Daten zu erkennen, dies gelingt aber nur, wenn es an einer großen Zahl von Trainingsdaten „ausgebildet“ wurde. Andernfalls kann es zu Überanpassungen kommen (siehe Abschn.  1.3). Sollte es schwierig sein, ausreichend viele Trainingsdaten zur Verfügung zu stellen, lässt sich eine der folgenden Methoden zur Vermeidung von Überanpassung einsetzen: • Subsampling: Um die Empfindlichkeit der Neuronen gegenüber zufälligem Rauschen in den Daten zu verringern, könnte man den Input in das Netz mithilfe des sogenannten Subsamplings „glätten“. Dies erreicht man durch die Verwendung von über Teilbereiche gemittelten Eingangsdaten. Handelt es sich dabei zum Beispiel um Bilder, würden deren Auflösung oder Farbkontrast reduziert. • Verzerrungen: Wenn es zu wenige Trainingsdaten gibt, könnten wir die Datenmenge vergrößern, indem wir die Bilddaten verzerren. Indem wir jedes verzerrte Bild als neuen Input benutzen, vergrößern wir die Menge unserer Trainingsdaten. Die eingesetzten Verzerrungen sollten denen entsprechen, die typischerweise auch im originalen Datensatz auftreten. So könnte man die handschriftlichen Zahlen in unserem Beispiel rotieren lassen, wie es auch bei verdrehten Notizzetteln passiert, oder die Ziffern schrägstellen (elastische Deformation),  wie es manche Menschen beim Schreiben gerne tun. • Dropout: Bei zu wenigen Trainingsdaten bilden die Neuronen in der Regel zu wenige Verbindungen mit

142     A. Ng und K. Soo

anderen Neuronen, was Überanpassungen nach sich zieht, weil kleine Gruppen von Neuronen sich zu sehr aufeinander beziehen. Dem lässt sich begegnen, wenn man in einem Trainingszyklus zufällig die Hälfte der Neuronen ausschließt (daher die Bezeichnung „Dropout“). Diese Neuronen würden vorübergehend deaktiviert und so lange von den übrigen Neuronen ignoriert. Im nächsten Zyklus würde dann eine andere Zufallsauswahl von Neuronen herausgenommen. Auf diese Weise zwingt die Dropout-Methode die Neuronen dazu, immer wieder mit anderen Neuronen Kontakt aufzunehmen und dadurch immer wieder neue Strukturen in den Trainingsdaten zu untersuchen. Hoher Rechenaufwand: Das Training eines neuronalen Netzes mit Tausenden Neuronen dauert einige Zeit. Natürlich kann man sich einen schnelleren Rechner kaufen, das kostet dann aber Geld statt Zeit. Eine alternative Lösung besteht darin, unsere Algorithmen so abzuändern, dass sie wesentlich schneller rechnen, aber nur wenig an Vorhersagegenauigkeit verlieren. Das können Sie folgendermaßen erreichen: • Stochastisches Gradientenverfahren: Beim klassischen Gradientenverfahren (siehe Abschn. 6.3) gehen wir pro Iterationsschritt durch alle Trainingsbeispiele, um einen einzigen Parameter zu aktualisieren. Da dies bei großen Datensätzen viel Zeit braucht, wäre es eine Alternative, in jedem Iterationsschritt den fraglichen Parameter bloß anhand eines Trainingsbeispiels zu aktualisieren. Dies ist das stochastische Gradientenverfahren. Und auch wenn

11  Neuronale Netze     143

die so ermittelten Parameterwerte zwar nicht unbedingt optimal sind, erreicht man mit ihnen trotzdem in der Regel eine recht anständige Vorhersagegenauigkeit. • Mini-Batch-Gradientenverfahren: Sich immer nur ein Trainingsbeispiel anzusehen, beschleunigt das Training zwar erheblich, es macht die Parameterschätzung aber weniger genau und außerdem konvergiert der Algorithmus dann nicht, sondern pendelt zum Beispiel beständig zwischen zwei Werten hin- und her. Ein besserer Kompromiss wäre es dann, in jedem Trainingsschritt weder alle noch nur einen, sondern eine kleinere Anzahl (oder einen kleinen „Batch“) an Trainingsbeispielen zu verarbeiten. Man spricht dann vom Mini-Batch-Gradientenverfahren. • Teilweise/vollständig verbundene Schichten: Die Zahl der möglichen Verbindungen zwischen den Neuronen steigt exponentiell mit der Anzahl der Neuronen. Um nicht immer alle denkbaren Kombinationen betrachten zu müssen, könnten wir die Neuronen in den ersten Schichten – die sich mit kleinen, lokalen Bildstrukturen beschäftigen – zum Teil unverbunden lassen. Nur in den letzten Schichten – wo große, globale Strukturen behandelt werden – lassen wir dann die Neuronen wirklich alle denkbaren Verbindungen mit den Nachbarschichten prüfen. Nicht zu interpretieren: Neuronale Netze bestehen aus vielen Schichten mit jeweils Hunderten von Neuronen, die alle ihren individuellen Aktivierungsregeln folgen. Dies macht es sehr schwer, eine bestimmte Kombination von InputSignalen zu bestimmen, die zur einer korrekten Vorhersage

144     A. Ng und K. Soo

führen würde. Bei Verfahren wie der Regressionsanalyse (siehe Kap. 6) ist das anders, dort kann man signifikante Prädiktoren herausarbeiten und miteinander vergleichen. Ein neuronales Netz ist dagegen eine Blackbox, was seine Benutzung in ethisch heiklen Fällen fraglich erscheinen lässt. Aus diesem Grund versucht man in der aktuellen Forschung, den Trainingsprozess auf der Ebene einzelner Schichten zu untersuchen, um zu sehen, wie einzelne InputSignale die sich ergebenden Vorhersagen beeinflussen. Trotz dieser Einschränkungen werden neuronale Netze dank ihrer großen Leistungsfähigkeit in immer mehr High-Tech-Anwendungen eingesetzt, etwa in virtuellen Assistenten oder autonomen Fahrzeugen. Neuronale Netze sind in manchen Gebieten bereits jedem Menschen überlegen, so konnte im Jahr 2015 das auf einem vielschichtigen neuronalen Netz beruhende Google-­ Programm AlphaGo einen weltberühmten Go-­ Spieler besiegen. Mittlerweile gilt es als ausgeschlossen, dass ein Mensch die aktuelle Version dieses Programms noch besiegen könnte. Mit immer schnelleren Rechnern und immer ausgefeilteren Algorithmen werden neuronale Netze eine zentrale Rolle im Zeitalter des Internet der Dinge spielen und unser Alltagsleben in noch kaum vorstellbarer Weise verbinden und automatisieren.

11.6 Zusammenfassung • Ein neuronales Netz besteht aus mehreren Schichten von Neuronen. Während des Trainings werden Neuronen der ersten Schicht von Input-Daten aktiviert, diese

11  Neuronale Netze     145

Aktivierungen werden dann von Schicht zu Schicht weitergereicht, bis sie schließlich in der letzten Schicht zu einem Output führen, der Vorhersage des Netzes. • Ob ein bestimmtes Neuron aktiviert wird, hängt von Stärke und Ursprung der dort einlaufenden Signale ab, berechnet wird seine Aktivierung mithilfe einer für jedes Neuron spezifischen Aktivierungsregel. Diese Regeln werden während des Trainings bei allen Neuronen optimiert, indem Feedback zur jeweiligen Vorhersagegenauigkeit einfließt. Diesen Prozess nennt man Backpropagation. • Neuronale Netze arbeiten am besten, wenn große Datensätze und leistungsfähige Rechner zur Verfügung stehen. Die Ergebnisse können allerdings im Wesentlichen nicht interpretiert werden.

12 A/B-Tests und vielarmige Banditen

12.1 Grundlagen des A/B-Tests Stellen Sie sich vor, Sie betreiben einen Onlineshop und möchten eine Anzeige schalten, um die Leute auf eine Rabattaktion aufmerksam zu machen. Welche Formulierung würden sie wählen? • Bis zu 50 % Rabatt auf Artikel! • Halber Preis für bestimmte Artikel Obwohl beide Aussagen dieselbe Bedeutung haben, könnte eine von ihnen überzeugender rüberkommen als die andere. So dürfte das Ausrufezeichen für mehr Aufmerksamkeit sorgen, aber klingt das zahlenmäßige „50 %“ interessanter oder der Ausdruck „halber Preis“? © Springer-Verlag GmbH Deutschland, ein Teil von Springer Nature 2018 A. Ng und K. Soo, Data Science – was ist das eigentlich?!, https://doi.org/10.1007/978-3-662-56776-0_12

147

148     A. Ng und K. Soo

Um herauszufinden, was besser funktioniert, könnten Sie beide Versionen des Werbespruchs in einem Pilotversuch 100 Personen vorlegen und registrieren, welche Anzeige häufiger angeklickt wird. Die mit mehr Klicks dürfte auch mehr Käufer anziehen und sollte deshalb für Ihre Werbekampagne benutzt werden. Diese Prozedur ist ein Beispiel für einen A/B-Test, bei dem zwei Versionen A und B miteinander verglichen werden.

12.2 Grenzen von A/B-Tests Bei der A/B-Test-Methode können zwei Probleme auftreten: Das Ergebnis könnte ein Zufallstreffer sein:  Eine schlecht gemachte Werbeanzeige könnte rein zufällig mehr Klicks bekommen als eine gute. Um dies auszuschließen, ließe sich die Zahl der Testpersonen erhöhen, doch dies führt direkt zum zweiten Problem. Mögliche Einnahmeverluste: Wenn wir mehr Personen beide Versionen der Anzeige vorlegen, also zum Beispiel 200 statt 100, würden wir doppelt so vielen Personen die lausige Anzeige präsentieren und so potenzielle Kunden verlieren, die von der besseren Anzeige begeistert gewesen wären. Diese beiden Probleme illustrieren einen grundsätzlichen Zielkonflikt bei A/B-Tests: erforschen oder erschließen. Wenn Sie die Zahl der Testpersonen erhöhen (den Markt erforschen), wissen Sie mit größerer Sicherheit,

12  A/B-Tests und vielarmige Banditen     149

welche Anzeige die bessere ist, aber Sie könnten mögliche Käufer verlieren (das Kundenpotenzial nicht genügend erschließen). Wie kommen wir aus dieser Zwickmühle heraus?

12.3 Abnehmendes-Epsilon-Strategie Während ein klassischer A/B-Test zunächst prüft, welche Anzeige die bessere ist (erforschen) und erst dann auf dem Markt aktiv wird (erschließen), können wir durchaus auch schon mit dem Erschließen beginnen, während das Erforschen noch läuft. Wenn unsere Anzeige A bei den ersten 100 Testpersonen bereits 60-mal angeklickt worden wäre und B nur 40-mal, könnten wir A bei den nächsten 100 Personen mit einer erhöhten Wahrscheinlichkeit von 60 % einblenden, während B dann nur noch in 40 % der Fälle aufpoppt (Abb. 12.1). Auf diese Weise würden wir einerseits bereits in der Testphase von der vermutlich besseren Qualität von Anzeige A profitieren. Andererseits hat B A/B-Test abnehmendes Epsilon erforschen

erschließen

Abb. 12.1  Ein A/B-Test beginnt mit einer Erforschungsphase (grau), an die sich eine Erschließungsphase (weiß) anschließt. Strategien mit abnehmendem Epsilon verbinden beide Phasen, wobei zu Beginn mehr erforscht und gegen Ende mehr erschlossen wird

150     A. Ng und K. Soo

immer noch die Chance, in der zweiten Testphase besser abzuschneiden, sodass wir weiterhin wichtige neue Informationen gewinnen können. Je mehr sich der A-Trend im weiteren Verlauf bestätigt, desto häufiger würden wir dann Anzeige A einblenden und desto seltener Anzeige B. Dieses Vorgehen ist als „Abnehmendes-EpsilonStrategie“ bekannt. Epsilon bezeichnet dabei den Anteil der Zeit, der mit der Suche nach einer Alternative oder einer deutlicheren Bestätigung des Gewählten verbracht wird. Da wir Epsilon genau dann kleiner machen, wenn sich unser Anfangsverdacht erhärtet, gehört dieser Algorithmus zur Klasse des bestärkenden Lernens.

12.4 Beispiel: Vielarmige Banditen Ein typisches Beispiel, um den Unterschied zwischen A/BTest und Abnehmendes-Epsilon-Strategie zu veranschaulichen, ist der auch als „einarmiger Bandit“ bekannte Spielautomat (Abb. 12.2). Wir stellen uns vor, ein Spieler steht vor einer Reihe solcher Geräte und weiß, dass verschiedene Maschinen unterschiedlich viel Gewinn auszahlen. Dann müsste der Spieler herausfinden, bei welchem Gerät er den meisten Gewinn zu erwarten hätte.

Abb. 12.2  Ein einarmiger Bandit

12  A/B-Tests und vielarmige Banditen     151

Der Name „einarmiger Bandit“ kommt zum einen daher, dass speziell in den USA ein großer, seitlich angebrachter Hebel betätigt werden muss, um das Spiel zu starten. Zum anderen weist er natürlich darauf hin, dass wie immer beim Glücksspiel auf die Dauer immer die Bank beziehungsweise der Automatenbetreiber gewinnt. Situationen, in denen man sich zwischen verschiedenen „Banditen“ entscheiden muss, heißen „vielarmiger Bandit“, es kann sich dabei um ganz unterschiedliche Allokationsprobleme handeln wie „Welche Anzeige schalte ich?“, „Welche Bücher soll ich mir für die Prüfung morgen früh noch einmal ansehen?“ oder „Welche Arzneimittelstudien sollen wir finanzieren?“. Stellen Sie sich der Einfachheit halber einen „zweiarmigen Banditen“ (aber ohne Füße!) vor, das heißt eine Auswahl zwischen zwei Spielautomaten A und B. Wir haben genug Geld, um auf beiden Geräten insgesamt 2000-mal zu spielen. In jeder Runde betätigen wir einen von beiden Spielautomaten, wodurch wir entweder 1 US-$ gewinnen oder nichts bekommen. Die Gewinnwahrscheinlichkeit beträgt bei Gerät A 50 %, bei Gerät B 40 %. Leider wissen wir das jedoch nicht. Die Frage ist also, wie wir unter diesen Voraussetzungen unseren Gewinn maximieren können. Lassen Sie uns mögliche Strategien vergleichen: Nur erforschen:  Wenn wir komplett zufällig an A oder B spielen, können wir einen durchschnittlichen Gewinn von 900 US-$ erwarten. A/B-Test:  Wenn wir während der ersten 200 Runden mit einem A/B-Test erforschen, welches Gerät mehr auszahlt,

152     A. Ng und K. Soo

und in den übrigen 1800 Runden uns die Gewinne von Gerät A erschließen, bekommen wir im Mittel 976 US-$ ausgezahlt. Aber Vorsicht: Da die Gewinnraten recht ähnlich sind, besteht eine 8%ige Chance, dass wir uns fälschlich für Gerät B entscheiden und dann in der Folge deutlich weniger ausgezahlt bekommen. Um dieses Risiko zu vermindern, könnten wir 500 Runden lang erforschen. Dann betrüge das Risiko einer falschen Wahl nur noch 1 %, aber der erwartete Gewinn läge dann auch nur noch bei 963 US-$. Abnehmendes-Epsilon-Strategie:  Wenn wir eine Abneh­ mendes-Epsilon-Strategie fahren und relativ frühzeitig häufiger am vermutlich besseren Gerät spielen, sind 984 US-$ an Auszahlung zu erwarten. Das Risiko einer falschen Gerätewahl läge bei nur 4 %. Wiederum ließe sich dieses Risiko auf Kosten eines geringeren Erwartungswerts des Gewinns noch verringern. Nur erschließen:  Wenn uns ein Insider verrät, dass Gerät A die besseren Chancen bietet, werden wir natürlich von Anfang an aufs richtige Pferd setzen und mit satten 1000 US-$ Gewinn rechnen können. Aber dies ist nicht (leicht) umzusetzen. Aus Abb. 12.3 sieht man sofort, dass – ohne Insiderwissen – eine Abnehmendes-Epsilon-Strategie die höchsten Gewinne erschließt. Darüber hinaus würde bei einer sehr hohen Zahl von Spielrunden eine mathematische Eigenschaft namens Konvergenz dafür sorgen, dass diese Strategie garantiert die bessere Maschine erkennt.

12  A/B-Tests und vielarmige Banditen     153 1000 976

984

963

900

nur erforschen

500 Runden erforschen

200 Runden abnehmendes nur erforschen Epsilon erschließen

Abb. 12.3  Vergleich der Auszahlungen bei verschiedenen Spielstrategien. Beachten Sie, dass die vertikale Skala nicht bei 0 beginnt!

12.5 Nett zu wissen: van Gaals Elfmeterschützen Eine interessante Anwendung des vielarmigen Banditen findet sich im Fußball. Während seiner Zeit als Trainer von Manchester United wählte der Niederländer Louis van Gaal eine unkonventionelle Strategie um zu entscheiden, wer in seinem Team die Elfmeter schießen sollte. Den als ersten ausgewählten Spieler ließ er so lange alle Elfmeter schießen, bis er einmal danebenschoss. Dasselbe galt für den nächsten, den übernächsten und so weiter. Betrachten wir die Wahl des Elfmeterschützen als Vielarmiger-Bandit-Problem und die Fußballer als Spielautomaten mit unbekannter Auszahlungswahrscheinlichkeit, dann bedeutet van Gaals Strategie, so lange bei einem

154     A. Ng und K. Soo

Gerät zu bleiben, bis es einmal nichts auszahlt, und dann zu wechseln. Mit dieser Strategie beträgt die zu erwartende mittlere Gewinnsumme im Beispiel aus dem letzten Abschnitt nur 909 US-$, also kaum mehr als bei völliger Zufallsauswahl. Wird das Gerät beziehungsweise der Spieler nämlich dermaßen oft gewechselt, steht die ausgiebige Testphase (also das Erkunden) in keinem Verhältnis zur geringen Ausbeute (dem Erschließen). Außerdem ignoriert van Gaals Strategie die Erkundungshistorie, also die Tatsache, dass manche Spieler lange Serien von Elfmetertoren schaffen, wenn er immer nur das letzte Spiel (den letzten Elfmeter) berücksichtigt. Diese Strategie ist ganz offensichtlich alles andere als ideal.

12.6 Grenzen einer AbnehmendesEpsilon-Strategie Während eine Abnehmendes-Epsilon-Strategie dem A/BTest grundsätzlich überlegen ist, hat sie ebenfalls eine gewisse Schwäche, weswegen sie sich schwieriger implementieren lässt als der A/B-Test. Um eine Abnehmendes-Epsilon-Strategie erfolgreich einzusetzen, muss man unbedingt den Wert von Epsilon sorgfältig im Auge behalten. Wenn Epsilon zu langsam abnimmt, „melken“ wir zu selten das bessere Gerät. Fällt Epsilon zu schnell, landen wir zu oft beim schlechteren Gerät. Die optimale Geschwindigkeit der Abnahme von Epsilon hängt stark davon ab, wie verschieden die Auszahlungsraten der beiden Geräte sind. Wenn sie sehr ähnlich sind wie in Tab. 12.1, sollte Epsilon langsam abnehmen. Man

12  A/B-Tests und vielarmige Banditen     155 Tab. 12.1  Auszahlungen bei verschiedenen Spielautomaten Gerät

Auszahlung

A B

0,5 0,4

kann optimale Werte für das Verhalten von Epsilon mithilfe einer Methode namens Th ­ ompson-Sampling ausrechnen. Eine Abnehmendes-Epsilon-Strategie beruht außerdem auf den folgenden nicht immer erfüllten Annahmen: 1. Auszahlungsrate ist konstant: Eine Werbeanzeige könnte morgens besser ankommen als abends, während eine andere rund um die Uhr ähnlich viele User anspricht. In diesem Fall würde ein Vergleich der beiden Anzeigen morgens zu einem anderen Ergebnis führen als abends. 2. Auszahlungsrate ist unabhängig von früheren Spielen: Wenn eine Anzeige sehr oft präsentiert wird, werden die Kunden vielleicht erst richtig neugierig und klicken sie deshalb mit größerer Wahrscheinlichkeit an (oder sie können sie nicht mehr sehen und klicken sie genervt weg). Dies bedeutet, dass man mehrfach erforschen muss, um die tatsächlichen Auszahlungsraten zu ermitteln. 3. Auszahlung erfolgt sofort: Wenn eine Anzeige per E-Mail verschickt wird, antworten potenzielle Kunden vielleicht erst nach ein paar Tagen. Dies würde verhindern, dass wir die Ergebnisse unserer Tests sofort erfahren, weswegen wir mit ihnen nicht klären können, ob wir besser erforschen oder erschließen sollten.

156     A. Ng und K. Soo

Wenn allerdings die zweite und die dritte Annahme jeweils für beide Anzeigen oder Geräte verletzt wären, könnten sich die Effekte aufheben. Kommen etwa die Antworten auf beide Anzeigen verspätet an, wäre der Vergleich wieder fair.

12.7 Zusammenfassung • Der „vielarmige Bandit“ beschreibt ein Problem bei der Allokation von Ressourcen – sollen wir möglichst schnell Gewinne realisieren oder möglichst gründlich nach den besten Gelegenheiten dazu suchen? • Eine Lösung wäre es, erst alle verfügbaren Optionen zu erforschen und sich dann die mit der besten Option erreichbaren Gewinne zu erschließen. Diese Strategie heißt A/B-Test. • Eine andere Lösung liegt darin, allmählich immer mehr Ressourcen der vielversprechendsten Variante zuzuweisen, aber währenddessen gewonnene neue Informationen nicht zu ignorieren. Dies ist die Abnehmendes-Epsilon-Strategie. • Während die Abnehmendes-Epsilon-Strategie in den meisten Fällen erfolgreicher ist als der A/B-Test, ist es nicht leicht, die optimale Rate zu finden, mehr der die Allokation der Ressourcen aktualisiert werden sollte.

Anhang

A. Überblick über Algorithmen des unüberwachten Lernens

© Springer-Verlag GmbH Deutschland, ein Teil von Springer Nature 2018 A. Ng und K. Soo, Data Science – was ist das eigentlich?!, https://doi.org/10.1007/978-3-662-56776-0

157

158     Anhang

B. Überblick über Algorithmen des überwachten Lernens

C. Anpassbare Parameter

Support-Vektor-

Anhang     159

D. Weitere Bewertungsmetriken Bewertungsmetriken unterscheiden sich darin, wie sie verschiedene Arten von Vorhersagefehlern definieren und „bestrafen“, das heißt mit einem Wert ihrer Strafoder Kostenfunktion belegen. Dieser Abschnitt führt einige weitere gebräuchliche Metriken ein (vergleiche Abschn. 1.4).

Klassifikationsmetriken Fläche unter der ROC-Kurve (AUROC1 ):  Eine Metrik auf der Basis der Fläche unter einer gegebenen Kurve (mathematisch würde man so etwas ein Integral nennen) erlaubt es uns, zwischen einer maximierten Rate von richtig positiven (RPR) und einer minimierten Rate von falsch positiven (FPR) Vorhersagen zu wählen. • Richtig-Positiv-Rate (RPR): Anteil aller positiven Punkte, die korrekt als positiv erkannt wurden: TPR = TP/(TP + FN) • Falsch-Positiv-Rate (FPR): Anteil aller negativen Punkte, die fälschlich als positiv klassifiziert wurden: FPR = FP/(FP + TN) Im Extremfall könnten wir uns dafür entscheiden, ausschließlich die Richtig-Positiv-Rate zu maximieren, indem

1Für

englisch area under the receiver operating characteristic (Anm. d. Übers.).

160     Anhang

Richg-Posiv-Rate (RPR) in %

wir RPR überall auf 1 setzen, wodurch automatisch alle Punkte als positiv eingestuft werden. Damit gäbe es zwar keinerlei falsch negative Vorhersagen, die Zahl der falsch positiven würde aber deutlich ansteigen. Es gibt also einen Zielkonflikt zwischen möglichst wenigen falsch positiven und möglichst vielen richtig positiven Prognosen. Dies lässt sich mithilfe einer ROC2 -Kurve visualisieren (Abb. D.1). Die Performance des Modells wird mit der Fläche unter der ROC-Kurve gemessen, woher diese Metrik ihren Namen hat. Je genauer das Modell ist, umso näher

Falsch-Posiv-Rate (FPR) in %

Abb. D.1  Eine ROC-Kurve, die das Dilemma zwischen möglichst wenigen falsch positiven und möglichst vielen richtig positiven Ergebnissen zeigt

2receiver operating characteristic könnte man mit „Grenzwertoptimierungskurve“ übersetzen, meist wird aber der englische Begriff gebraucht (Anm. d. Übers.).

Anhang     161

verläuft die Kurve an der linken beziehungsweise oberen Kante. Ein perfektes Vorhersagemodell hätte eine ROCKurve, deren Fläche genau 1 beträgt, also das komplette Quadrat ausfüllt. Im Gegensatz dazu hätte ein Modell, das nur Zufallsergebnisse liefert, die gestrichelt eingezeichnete Diagonale als ROC-Kurve und eine AUC von 0,5. In der Praxis würden wir das Vorhersagemodell mit dem höchsten AUC-Wert als das beste ansehen und diese ROC-Kurve dann benutzen, um sinnvolle Schwellenwerte für RPR und FPR zu wählen, die wir gerade noch tolerieren würden. Während nun die ROC-Kurve es uns erlaubt, ganz bestimmte Arten von Fehlern zu vermeiden, könnten wir ebenso gut ganz allgemein alle falschen Vorhersagen „bestrafen“, indem wir eine logarithmische Kostenfunktion benutzen. Logarithmische Kostenfunktion (Log Loss): Vorhersagen für binäre und kategoriale Variablen werden generell als Wahrscheinlichkeiten ausgedrückt, etwa als die Wahrscheinlichkeit, dass ein Kunde Fisch kauft. Je näher diese Wahrscheinlichkeit bei 100 % liegt, desto sicherer ist sich das Modell, dass der Kunde Fisch kaufen wird. Eine logarithmische Kosten- oder Straffunktion beruht auf diesem Maß für die Sicherheit einer Prognose. Ihr Wert, also die „Strafe“ für eine falsche Vorhersage, ist umso höher, je sicherer sich das Modell ist, dass die Vorhersage falsch ist. Die Abbildung (Abb. D.2) zeigt, wie stark der Wert der Kostenfunktion zunimmt, wenn die Wahrscheinlichkeit einer falschen Vorhersage sich dem Maximalwert 100 %

162     Anhang 14

Kostenfunkon

12 10 8 6 4 2 0

0

10

20

30

40

50

60

70

80

90 100

Sicherheit einer falschen Vorhersage in % Abb. D.2  Die logarithmische Kostenfunktion nimmt stark zu, wenn das Modell sich zu fast 100 % sicher ist, dass die Vorhersage falsch ist

annähert. Wenn unser Modell zum Beispiel eine 80%ige Chance dafür ermittelt, dass ein Kunde Fisch kauft, und sich dies als falsch herausstellt, werden dem Modell 0,8 Strafpunkte zugewiesen. Hätte es stattdessen eine 99-%-Chance für einen Fischkauf vorhergesagt, hätte die Kostenfunktion den mehr als doppelt so großen Wert 2 geliefert. Da diese Metrik Kostenpunkte auf Basis der Vorhersagesicherheit verteilt, wird sie vor allem dann eingesetzt, wenn falsche Vorhersagen schlimme Folgen hätten.

Regressionsmetriken Mittlere absolute Abweichung (MAE, mean absolute error):  Ein einfacher Weg zur Bewertung eines Regres­ sionsmodells ist es, alle Fehler gleich zu „bestrafen“, indem man die mittlere Abweichung der vorhergesagten Werte

Anhang     163

vom jeweiligen wahren Wert berechnet – unabhängig von der Richtung der Abweichung. Quadratisch gemittelte logarithmische Abweichung (RMSLE, root mean squared logarithmic error):  In Abschn. 1.4 haben wir die quadratisch gemittelte Abweichung (RMSE) als Metrik vorgestellt, welche große Fehler besonders „hart“ bestraft. Außer der Größe der Abweichung könnten wir dazu auch die Richtung der Abweichung berücksichtigen, indem wir die quadratisch gemittelte logarithmische Abweichung als Metrik verwenden. Mit der RMSLE wollen wir eher Unteranpassungen als Überanpassungen vermeiden (zum Beispiel wenn für Regenwetter der Bedarf an Regenschirmen vorhergesagt wird). Unteranpassungen (zu wenige Regenschirme) führen zu unzufriedenen Kunden und entgangenen Einkünften, während Überanpassungen (zu viele Regenschirme) nur zu große Lagerbestände nach sich ziehen.

Glossar

A/B-Test   Strategie,

mit der sich der Nutzen oder die Einnahmen aus zwei Produkten A und B vergleichen lassen. Der Prozess beginnt mit einer „Erforschen“ genannten Phase, während der beide Produkte gleich häufig getestet werden. Anschließend bestimmt man, welches Produkt das bessere Ergebnis geliefert hat, und arbeitet danach ausschließlich mit diesem, um sich maximale Einnahmen zu erschließen – dies ist die sogenannte „Erschließen“-Phase. Es besteht ein Zielkonflikt zwischen einer möglichst langen Testphase (um möglichst sicher die bessere Alternative zu erkennen) und einer möglichst langen Erschließen-Phase (für möglichst hohe Gesamteinnahmen). Abnehmendes-Epsilon-Strategie    Methode des bestärkenden Ler­ nens für die Ressourcenallokation, bei der zwei Phasen ineinandergreifen: a) die bessere Alternative erforschen und b) maximale Einnahmen aus der vermuteten Lösung erschließen. © Springer-Verlag GmbH Deutschland, ein Teil von Springer Nature 2018 A. Ng und K. Soo, Data Science – was ist das eigentlich?!, https://doi.org/10.1007/978-3-662-56776-0

165

166     Glossar

Epsilon ist der Anteil der Zeit, die mit der Suche nach der besseren Alternative verbracht wird. Der Wert dieses Parameters wird allmählich verringert, und zwar in dem Maß, wie die Information über die bessere Alternative verlässlicher wird. Aktivierungsregel   Kriterium, das angibt, aus welcher Quelle und mit welcher Stärke Input-Signale bei einem Neuron in einem neuronalen Netz einlaufen müssen, damit dieses Neuron aktiviert wird. Neuronenaktivierungen pflanzen sich durch die Schichten des Netzes fort, bis sie in der letzten Schicht die Antwort oder Vorhersage des Netzes formen. A-priori-Prinzip    Regel, der zufolge man aus einer selten auftretenden Gruppe von Objekten darauf schließen kann, dass alle größeren Gruppen, welche diese Objekte enthalten, ebenfalls (oder sogar erst recht) selten sind. Mit dieser Annahme lässt sich die Zahl der Konfigurationen reduzieren, die bei einer Assoziationsanalyse untersucht werden müssen. Assoziationsanalyse    Verfahren des unüberwachten Lernens, das untersucht, ob Datenpunkte gehäuft mit bestimmten anderen Datenpunkte zusammen auftreten beziehungsweise assoziiert sind. Es gibt drei gebräuchliche Maße für Assoziationen: • Der Support von {X} gibt an, wie häufig Objekt X auftritt. • Die Konfidenz von {X→Y} gibt an, wie häufig Objekt Y auf­ tritt, wenn Objekt X anwesend ist. • Der Lift von {X→Y} gibt an, wie häufig die Objekte X und Y zusammen auftreten, wobei berücksichtigt wird, wie häufig die beiden jeweils einzeln vorkommen. Backpropagation    Prozess,

bei dem ein neuronales Netz Feedback über die Korrektheit seiner Vorhersagen erhält. Wenn eine Vorhersage falsch war, wird eine Fehlermeldung zurück durch die Schichten des Netzes geschickt, woraufhin die Aktivierungsregeln der beteiligten Neuronen so verändert werden, dass der Fehler kleiner wird.

Glossar     167 Bestärkendes Lernen   Klasse

von maschinellen Lernalgorithmen, bei der die Vorhersagen basierend auf der Güte der bisherigen Ergebnisse stetig verbessert werden. Best-Fit-Linie   Trendlinie, die so viele Datenpunkte wie möglich berührt oder ihnen zumindest so nahe wie möglich kommt. Blackbox    Ausdruck, der nicht interpretierbare Vorhersagemodelle beschreibt, bei denen sich nicht im Einzelnen nachvollziehen lässt, wie sie zu ihren Vorhersagen gelangen. Bootstrap Aggregating (Bagging)  Methode zur Erzeugung Tausender unkorrelierter Entscheidungsbäume, mit denen man gemittelte Vorhersagen gewinnt, die weniger anfällig für Überanpassung sind. Jeder Baum entsteht aus einer zufällig ausgewählten Untermenge der Trainingsdaten, wobei an jeder Verzweigung eine zufällig ausgewählte Untermenge an Prädiktorvariablen zum Einsatz kommt. Dimensionsreduktion   Prozess, bei dem die Zahl der Variablen eines Datensatzes reduziert wird, etwa durch Zusammenfassen von hochkorrelierten Variablen. Dropout    Technik, mit der sich bei einem neuronalen Netz Überanpassung vermeiden lässt. Man schließt dabei zufällig Gruppen von Neuronen von den Trainingsläufen aus, wodurch die Neuronen mit immer wieder anderen Neuronen in Kontakt treten müssen und keine „geschlossenen Zirkel“ bilden können. Ensembling   Kombination von zahlreichen Vorhersagemodellen zur Verbesserung der Vorhersagegenauigkeit. Dies basiert auf der Tatsache, dass Modelle mit korrekten Vorhersagen einander tendenziell bestätigen, während (zufällig) falsche Vorhersagen sich gegenseitig aufheben. Entscheidungsbaum   Methode des überwachten Lernens, die zu ihren Vorhersagen gelangt, indem eine Abfolge binärer Fragen gestellt wird, wodurch die Datenpunkte in immer homogenere Untergruppen aufgeteilt werden. Das Verfahren ist

168     Glossar

leicht zu verstehen und zu visualisieren, tendiert aber bis zu einem gewissen Grad zur Überanpassung. Gradient Boosting   Technik des überwachten Lernens, bei der zahlreiche Entscheidungsbäume durch Auswahl immer unterschiedlicher Kombinationen von binären Fragen aufgebaut werden. Die binären Fragen werden dabei gezielt (und nicht zufällig wie bei Random Forests) so ausgewählt, dass die Vorhersagegenauigkeit bei jedem nachfolgenden Baum besser ist als beim vorhergehenden. Die Vorhersagen der Einzelbäume werden dann in einem gewichteten Mittel zusammengefasst, wobei die zuletzt erzeugten Bäume das höchste Gewicht erhalten. Gradientenverfahren   Verfahren zur Parameteranpassung. Es startet mit einer ersten Schätzung der Parameterwerte, mit denen dann in einem iterativen Prozess zuerst Vorhersagen berechnet werden. Anschließend werden je nach Vorhersagegenauigkeit die Parameter so verändert, dass der Vorhersagefehler insgesamt abnimmt. Hauptkomponentenanalyse    Methode des unüberwachten Lernens, welche die Zahl der zu untersuchenden Variablen reduziert, indem die informativsten Variablen des Datensatzes zu neuen Variablen zusammengefasst werden, die man Hauptkomponenten nennt. Kernel-Trick    Technik, bei der Datenpunkte formal in eine höhere Dimension projiziert werden, wo sie sich durch eine gerade Linie (beziehungsweise deren höherdimensionales Äquivalent) separieren lassen. Diese geraden Grenzlinien sind einfacher zu berechnen und können auch leicht in gekrümmte Begrenzungen in der ursprünglichen, niedrigeren Dimension zurückgerechnet werden. Klassifikation   Klasse von Methoden des überwachten Lernens zur Vorhersage von binären oder kategorialen Werten. k-Means-Clustering   Technik des unüberwachten Lernens, welche ähnliche Datenpunkte in Gruppen zusammenfasst, wobei k angibt, wie viele Gruppen gebildet werden sollen.

Glossar     169 k-nächste Nachbarn   Technik

des überwachten Lernens, die einen Datenpunkt anhand der Werte der k nächstgelegenen Datenpunkte klassifiziert. Korrelation    Metrik, die lineare Assoziationen von Variablen misst. Korrelationskoeffizienten nehmen Werte zwischen −1 und +1 an und liefern uns zwei Informationen: 1) die Stärke der Assoziation, welche bei −1 und +1 maximal und bei 0 minimal wird, sowie 2) das Vorzeichen der Assoziation. Dies ist positiv, wenn die zwei Variablen sich gleichsinnig verändern, und negativ, wenn sie gegensinnig variieren. Kreuzvalidierung   Verfahren, mit dem man die Zahl der für eine Validierung verfügbaren Daten erhöhen kann, indem Untermengen des Datensatzes gebildet werden. In einem einzelnen Validierungslauf benutzt man alle Untermengen außer einer als Trainingsdaten, an dieser einen werden die Vorhersagen dann getestet und deren Güten notiert. Dies wird so lange wiederholt, bis alle Untermengen einmal als Testdaten gedient haben. Am Ende verwendet man den Mittelwert aller einzelnen Validierungen als Schätzwert für die Güte der Modellvorhersagegenauigkeit. Louvain-Methode   Technik des unüberwachten Lernens, welche ein Netz derart in Cluster aufteilt, dass die Interaktionen innerhalb der Cluster maximiert und die Interaktionen zwischen Clustern minimiert werden. Merkmalsextraktion   Kreatives Generieren von neuen Variablen, etwa indem eine einzelne Variable rekodiert wird oder mehrere Variablen miteinander verrechnet werden. Multikollinearität   Bei der Regressionsanalyse auftauchendes Problem, bei dem hochkorrelierte Prädiktoren die Interpretation der Regressionsgewichte verzerren. Neuronales Netz   Technik des überwachten Lernens, bei welcher in Schichten angeordnete „Neuronen“ Informationen verarbeiten, indem Aktivierungen von Schicht zu Schicht

170     Glossar

weitergegeben werden. Das Aktivierungsmuster der letzten Schicht ist dann die Vorhersage des Modells. Das Verfahren hat einerseits eine hohe Vorhersagegenauigkeit, die Ergebnisse sind aber wegen der großen Komplexität praktisch nicht zu interpretieren. PageRank   Algorithmus zum Auffinden der dominierenden Knoten in einem Netzwerk. Er bewertet Knoten anhand der Zahl ihrer Verbindungen, deren Stärke und der Bewertungen der Quellen dieser Verbindungen. Parameteranpassung   Prozess, bei dem die Parameter eines Algorithmus so eingestellt werden, dass die Vorhersagegenauigkeit des Modells maximiert wird, ähnlich wie man früher am Transistorradio die Senderfrequenz so eingestellt hat, dass man den besten Empfang hatte. Prädiktor    Unabhängige Variable, auf deren Grundlage ein Modell Werte für die abhängigen Variablen oder Zielvariablen vorhersagt. Quadratisch gemittelte Abweichung  Metrik zur Berechnung der Genauigkeit von Vorhersagen bei Modellen mit Regressionsanalyse. Diese ist besonders dann geschickt, wenn wir in erster Linie große Fehler vermeiden wollen. Da jeder einzelne Fehler quadriert wird, tragen große Fehler überproportional zur Bewertung bei, was die Metrik sehr empfindlich auf Ausreißer reagieren lässt. Random Forest   Technik des überwachten Lernens, die eine Vielzahl von unkorrelierten Entscheidungsbäumen generiert. Dabei werden zufällig jeweils andere Kombinationen von binären Fragen benutzt, um neue Zweige wachsen zu lassen. Aus den Vorhersagen der Einzelbäume wird dann am Ende die Modellvorhersage berechnet. Regressionsanalyse    Verfahren des überwachten Lernens zum Berechnen der Best-fit-Trendlinie durch die Datenpunkte, hier auch Regressionsgerade genannt. Deren Parameter erhält man als gewichtete Kombinationen von Prädiktoren.

Glossar     171 Regularisierung   Technik,

mit der man bei einem Vorhersagemodell Überanpassung vermeiden kann, indem man eine Strafoder Kostenfunktion einführt. Diese vergrößert zum Beispiel künstlich den Vorhersagefehler, wenn das Modell zu komplex wird. Auf diese Weise behalten wir bei der Optimierung der Modellparameter sowohl die Genauigkeit als auch die Überschaubarkeit im Auge. Rekursive Partitionierung   Wiederholtes Aufteilen eines Datensatzes in immer homogenere Gruppen, etwa beim Generieren von Entscheidungsbäumen. Scree-Plot   Graph, aus dem wir die optimale Anzahl von Datenclustern oder reduzierten Dimensionen ablesen können. Diese liegt normalerweise bei einem „Knick“ in der Datenkurve des Plots. Standardisierung   Prozess, bei dem man Variablen so umrechnet, dass sie auf einer dimensionslosen Skala verglichen werden können, zum Beispiel als Perzentile. Subsampling   Verfahren, mit dem man Überanpassung in einem neuronalen Netz vermeiden kann. Dazu werden die eingekoppelten Trainingsdaten durch Mittelwertbildung „geglättet“. Angewandt auf Bilddaten würde das beispielsweise zu einer reduzierten Auflösung oder vermindertem Farbkontrast führen. Support-Vektor-Maschine    Methode des überwachten Lernens, die Datenpunkte in zwei Gruppen einteilt, indem sie eine Grenzlinie in der Mitte zwischen den jeweils am weitesten außen liegenden Datenpunkten zieht. Letztere nennt man Support-Vektoren der beiden Gruppen. Mithilfe des Kernel-Tricks lässt sich diese Grenzlinie auch dann effizient berechnen, wenn sie eine gekrümmte Linie (oder Fläche) ist. Testdatensatz    Datensatz, mit dem man die Genauigkeit und Übertragbarkeit eines Vorhersagemodells überprüft. Die Testdaten dürfen nicht bei der Ausformulierung (dem Training) des Vorhersagemodells benutzt worden sein.

172     Glossar Trainingsdatensatz   Datensatz,

an dem man mögliche Beziehungen untersucht, um daraus ein Vorhersagemodell zu formulieren. Das Modell wird dann mithilfe von Testdatensätzen validiert. Translationsinvarianz    Eigenschaft von sogenannten Faltungsschichten in neuronalen Netzen, welche Strukturen in Bildern erkennen können, auch wenn die Bilder seitlich verschoben sind. Überanpassung    Phänomen, dass ein Vorhersagemodell zu empfindlich auf die Eingangsdaten reagiert und zufällige Schwankungen in den Daten als permanente Muster fehl­ interpretiert. Ein überangepasstes Modell kann zwar sehr genaue Vorhersagen für die vorliegenden Daten machen, lässt sich aber nur schlecht auf andere Daten übertragen. Überwachtes Lernen   Klasse von Vorhersage-Algorithmen des maschinellen Lernens. Diese Algorithmen heißen überwacht, weil wir dafür Sorge tragen, dass ihre Vorhersagen auf bereits bekannten Mustern in unseren Daten basieren. Unteranpassung    Phänomen, dass ein Vorhersagemodell zu unempfindlich auf die Eingangsdaten reagiert und reale Muster übersieht. Ein unterangepasstes Modell verpasst sehr wahrscheinlich wichtige Trends, was sowohl bei den vorliegenden als auch bei unbekannten Daten zu Vorhersagen mit niedriger Genauigkeit führt. Unüberwachtes Lernen   Klasse von Algorithmen des maschinellen Lernens, mit der sich noch unbekannte, „versteckte“ Muster in Daten auffinden lassen. Diese Algorithmen heißen unüberwacht, da wir ihnen keine Vorgabe machen, nach welchen Mustern sie suchen sollen. Validierung   Bewertung, wie genaue Vorhersagen unser Modell für neue Daten machen kann. Man muss dazu den vorliegenden Datensatz in zwei Gruppen aufteilen: Die eine dient als Trainingsdatensatz zum Erstellen und Optimieren unseres

Glossar     173

Vorhersagemodells, die andere verwenden wir als „neue“ Daten zum Testen der Vorhersagegenauigkeit des optimierten Modells. Variable    Information, die Datenpunkte beschreibt. Variablen heißen auch Merkmale, Attribute oder Dimensionen. Es gibt unterschiedliche Variablentypen: • binär:

die einfachste Art von Variable, bei der es nur zwei mögliche Optionen gibt (zum Beispiel ja/nein oder weiblich/männlich), • kategorial: eine Variable, die mehr als zwei Optionen hat, deren Typus aber sonst nicht beschränkt ist (zum Beispiel Nationalität, Farbe oder Charakter), • ganzzahlig oder diskret: eine Variable, deren Werte ganze Zahlen oder allgemein aus einer begrenzten Menge von Zahlen gewählt sind (zum Beispiel Alter in Jahren), • s tetig: eine Variable, die beliebige Dezimalzahlen („reelle Zahlen“) als Werte annehmen kann (zum Beispiel Kontostand). Vielarmiger Bandit   Bezeichnung

für bestimmte Aufgaben der Ressourcenallokation, etwa die Frage, an welchen aus einer Reihe von Geldspielautomaten („einarmigen Banditen“) man sein Geld setzen soll – wenn man es nicht grundsätzlich bleiben lassen kann. Wahrheitsmatrix (Konfusionsmatrix)   Metrik zur Bewertung der Genauigkeit von Klassifikationsalgorithmen. Die Matrix zeigt nicht nur die totale Vorhersagegenauigkeit, sondern auch, wie häufig falsch positive oder falsch negative Vorhersagen auftreten.

Literatur

Persönlichkeitszüge von Filmfans (k-Means-Clustering) Kosinski, M., Matz, S., Gosling, S., Popov, V., Stillwell, D.: Facebook as a social science research tool: opportunities, challenges, ethical considerations and practical guidelines. ­ Am. Psychol. 70(6), 543–556 (2015) https://doi.org/­10.1037/ a0039210 Stillwell, D., Kosinski, M.: myPersonality Project (Datenfiles und Beschreibung). Beispieldaten lassen sich von http://dataminingtutorial.com herunterladen (2012)

© Springer-Verlag GmbH Deutschland, ein Teil von Springer Nature 2018 A. Ng und K. Soo, Data Science – was ist das eigentlich?!, https://doi.org/10.1007/978-3-662-56776-0

175

176     Literatur

Nahrungsmittel (Hauptkomponentenanalyse) Agricultural Research Service, United States Department of Agriculture: USDA food composition databases (Daten). https://ndb.nal.usda.gov/ndb/nutrients/index (2015)

Lebensmitteleinkäufe (Assoziationsanalyse) Der Datensatz ist in dem folgenden R-Paket enthalten: Hahsler, M., Buchta, C., Gruen, B., Hornik, K.: arules: Mining Association rules and frequent itemsets. R-Paket-Version1.5-0. https://CRAN.Rproject.org/package=arules (2016) Hahsler, M., Chelluboina, S.: Visualizing association rules: introduction to the R-extension package arulesViz. R Project Module, 223–238 (2011) Hahsler, M., Hornik, K., Reutterer, T.: Implications of probabilistic data modeling for mining association rules. In: Spiliopoulou, M., Kruse, R., Borgelt, C., Nürnberger, A., Gaul, W. (Hrsg.) From data and Information Analysis to Knowledge Engineering, Studies in Classification, Data Analysis, and Knowledge Organization, S.  598–605. Springer, Berlin (2006)

Waffenhandel (Netzwerke) Stockholm International Peace Research Institute: Trade registers (Daten). http://armstrade.sipri.org/armstrade/page/trade_ register.php (2015)

Literatur     177

Hauspreise (Regressionsanalyse) Harrison, D., Rubinfeld, D.: Hedonic housing prices and the demand for clean air. J. Environ. Econ. Manage 5, 81–102 (1978) Harrison, D., Rubinfeld, D.: Boston housing data (Datenfile und Beschreibung). https://archive.ics.uci.edu/ml/datasets/ Housing (1993)

Weinzusammensetzung (k-nächste Nachbarn) Cortez, P., Cerdeira, A., Almeida, F., Matos, T., Reis, J.: Modeling wine preferences by data mining from physicochemical properties. Decis. Support Syst. 47(4), 547–553 (2009) Forina, M. et al.: Wine recognition data (Datenfile und Beschreibung). http://archive.ics.uci.edu/ml/datasets/Wine (1998)

Herzerkrankungen (Support-Vektor-Maschine) Detrano, R., et al.: International application of a new probability algorithm for the diagnosis of coronary artery disease. Am. J. Cardiol 64(5), 304–310 (1989) Robert, D. (M. D., Ph. D.): Virginia Medical Center, Long Beach, und Cleveland Clinic Foundation. Heart disease database (Cleveland) (Datenfile und Beschreibung). https:// archive.ics.uci.edu/ml/datasets/Heart+Disease (1988)

178     Literatur

Titanic-Überlebende (Entscheidungsbaum) British Board of Trade Inquiry: Titanic data (Datenfile und Beschreibung). http://www.public.iastate.edu/˜hofmann/ data/titanic.html (1990) Report on the Loss of the „Titanic“ (S. S.): British Board of Trade Inquiry Report (Nachdruck), Gloucester, UK: Allan Sutton Publishing. Auch behandelt in: Dawson, R. J. M. (1995). The „Unusual Episode“ Data Revisited. Journal of Statistics Education, 3(3) (1990)

Verbrechen in San Francisco (Random Forest) SF OpenData, City und County of San Francisco: Crime Incidents (Daten). https://data.sfgov.org/Public-Safety/Map-Crime-Incidents-from-1-Jan-2003/gxxq-x39z (2016)

Wetter in San Francisco (Random Forest) National Oceanic and Atmospheric Administration, National Centers for Environmental Information: Quality Controlled Local Climatological Data (QCLCD) (Datenfile und Beschreibung). https://www.ncdc.noaa.gov/qclcd/ QCLCD?prior=N (2016)

Literatur     179

Handgeschriebene Zahlen (neuronale Netze) LeCun, Y., Cortes, C.: The MNIST database of handwritten digits (Datenfile und Beschreibung). http://yann.lecun.com/ exdb/mnist (1998) LeCun, Y., Bottou, L., Bengio, Y., Haffner, P.: Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11), 2278–2324 (1998) __________________________________________________

Noch mehr offene Daten finden Sie bei Lichman, M.: UCI machine learning repository. University of California, School of Information and Computer Science, Irvine. http://archive.ics.uci.edu/ml (2013)