Master-Arbeit - Hochschule für Technik und Wirtschaft Berlin

Transcrição

Hochschule für Technik und Wirtschaft Berlin
Freie wissenschaftliche Arbeit zur Erlangung des akademischen Grades
Master of Science in Wirtschaftsinformatik
Sentiment Analyse in Apache Spark
Masterthesis
im Fachbereich Wirtschaftswissenschaften II
im Studiengang Wirtschaftsinformatik
der Hochschule für Technik und Wirtschaft Berlin
vorgelegt von: Andreas Becker
Ostseestraße 67
10409 Berlin
528204
Erstbetreuer: Prof. Dr. Ingo Claßen
Zweitbetreuer: Prof. Dr. Christian Herta
Abgabetermin: 16.03.2014
Abstract
Abstract
Diese Arbeit beschäftigt sich mit dem Thema Sentiment Analyse im Big Data Bereich. Es wird der aktuelle Stand des Forschungsgebiets durch Literaturrecherche
erörtert. Des Weiteren wird ein Einblick in das maschinelle Lernen und die technischen Grundlagen der Datenspeicherung und –verarbeitung erklärt. In dem praktischen Teil der Arbeit wird Sentiment Klassifikation mit dem naives Bayes-Klassifikator und der Support Vector Machine auf dem Apache Spark Framework durchgeführt. Als Datenbasis dienen hierfür Kundenbewertungen des Onlinehändlers Amazon. Bei der Klassifikation wird das Hauptaugenmerk auf die Performance und Skalierbarkeit des Apache Spark-Frameworks innerhalb eines Computer Clusters gelegt. Dafür werden unterschiedliche Konfigurationen und verschieden große Datasets getestet. Die Ergebnisse der durchgeführten Tests zeigen, dass sich Spark
nicht skalieren lässt. Abschließend wird ein einfacher Algorithmus zur Generierung
eines Sentiment Lexikons in Spark implementiert. Dabei werden RDDs, also das
Speicherkonzept von Spark, genutzt
II
Inhaltsverzeichnis
Inhaltsverzeichnis
Abstract .............................................................................................................. II
Inhaltsverzeichnis ................................................................................................ I
Abbildungsverzeichnis ....................................................................................... III
Tabellenverzeichnis ............................................................................................ V
Abkürzungsverzeichnis ..................................................................................... VI
1 Einleitung ....................................................................................................... 1
1.1 Ziel und Aufbau ........................................................................................ 2
2 Fachliche Grundlagen .................................................................................... 3
2.1 Sentiment Analyse ................................................................................... 3
2.1.1 Begriffserläuterungen ...................................................................... 4
2.1.2 Aufgaben und Probleme .................................................................. 7
2.1.3 Ebenen der Sentiment Analyse ....................................................... 9
2.1.3.1 Dokumenten-Ebene .......................................................... 9
2.1.3.2 Satz-Ebene ..................................................................... 10
2.1.3.3 Aspekt-Ebene.................................................................. 15
2.1.4 Sentiment Lexikon ......................................................................... 21
2.2 Maschinelles Lernen .............................................................................. 26
2.2.1 Sentiment Klassierung durch überwachtes Lernen ....................... 27
2.2.2 Sentiment Klassierung durch unüberwachtes Lernen ................... 30
2.2.3 Klassifikatoren ............................................................................... 35
2.2.3.1 Naïve Bayes .................................................................... 35
2.2.3.2 Support Vector Machine .................................................. 38
2.2.3.3 Gradientenverfahren ....................................................... 40
2.2.4 Features ........................................................................................ 41
2.2.4.1 Wortart ............................................................................ 41
2.2.4.2 N-Gramme ...................................................................... 47
2.2.4.3 Lemmatisierung............................................................... 48
2.2.4.4 Stimmungsverändernde Wörter ...................................... 48
2.2.4.5 Stimmungswörter und –Sätze ......................................... 49
2.2.4.6 Kompositionelle Regeln .................................................. 49
2.2.4.7 Satz- und Sonderzeichen ................................................ 53
2.2.4.8 Syntakische Abhängigkeiten ........................................... 53
2.2.4.9 TF-IDF-Maß .................................................................... 54
3 Technische Grundlagen ............................................................................... 55
3.1 Daten und Datenspeicher ...................................................................... 55
3.2 Hadoop Distributed File System ............................................................ 59
I
Inhaltsverzeichnis
3.3 Apache Spark ........................................................................................ 60
3.3.1 Spark Komponenten und Architektur ............................................. 63
3.3.2 Resilient Distributed Datasets ....................................................... 67
3.3.3 Daten in Apache Spark ................................................................. 69
4 Sentiment Analyse in Apache Spark ............................................................ 72
4.1 Skalierbarkeit der Sentiment Klassifikation ............................................ 72
4.1.1 Vorgehen ....................................................................................... 72
4.1.2 Technische Basis .......................................................................... 73
4.1.3 Datenbasis .................................................................................... 75
4.1.4 Aufbereitung der Daten ................................................................. 77
4.1.5 Klassifikation ................................................................................. 83
4.1.6 Durchführung................................................................................. 84
4.1.7 Bewertung der Ergebnisse ............................................................ 93
4.2 Implementierung eines Algorithmus zur Sentiment Lexikon Generierung98
4.2.1 Grundlage...................................................................................... 98
4.2.2 Datenbasis .................................................................................... 98
4.2.3 Umsetzung .................................................................................... 99
4.2.4 Bewertung ................................................................................... 102
5 Schlussbemerkungen und Ausblick ........................................................... 105
6 Literaturverzeichnis ....................................................................................... VI
Anhang ............................................................................................................ XIII
A Code der Spark Sentiment Klassifikation .............................................. XIII
B Dictionary .............................................................................................. XIV
II
Abbildungsverzeichnis
Abbildung 1 Kundenbewertung Tablet ............................................................... 5
Abbildung 2: LDA Topic Model ......................................................................... 18
Abbildung 3: Schoutens Algorithmus zur Erkennung neuer Aspekte ............... 20
Abbildung 4: Vier Wege um von "good" auf "bad" zu kommen (Godbole) ........ 23
Abbildung 5: Gesichte des maschinellen Lernens ............................................ 26
Abbildung 6: Vergleich von verschiedenen Algorithmen in der Sentiment
Klassifikation ................................................................................... 29
Abbildung 7: Hyperebene im Vektorraum mit schmalen und breiten Rand ...... 39
Abbildung 8: Hyperebene in einem nicht linear trennbaren Datensatz ............. 40
Abbildung 9: Bag-of-Words-Modell................................................................... 47
Abbildung 10: Wissenspyramide ...................................................................... 56
Abbildung 11: HDFS-Architektur ...................................................................... 60
Abbildung 12: Ausführungszeigen Spark/Hive im Vergleich ............................. 62
Abbildung 13: Spark Stack ............................................................................... 64
Abbildung 14: Spark Cluster-Architektur .......................................................... 65
Abbildung 15: Jobausführung in einer Spark-Applikation ................................. 66
Abbildung 16: Abhängigkeitsformen von RDDs ................................................ 69
Abbildung 17: Partitionierung einer Datei in HDFS ........................................... 70
Abbildung 18: Architektur des HTW-Cluster ..................................................... 73
Abbildung 19: Aufbau der Datenbasis .............................................................. 77
Abbildung 20: Einlesen der Daten in SciKit Learn ............................................ 78
Abbildung 21: Aufteilung einer Datei in HDFS .................................................. 79
Abbildung 22: Datenvorbereitung Spark ........................................................... 80
Abbildung 23: Funktionen zur Datenvorbereitung in Spark .............................. 81
Abbildung 24: Ermittlung TFIDF in Spark ......................................................... 81
Abbildung 25: Code-Anpassung 1 .................................................................... 87
Abbildung 26: Bayes in Spark .......................................................................... 88
Abbildung 27: Caching in Spark ....................................................................... 91
Abbildung 28: Executoren im Cluster ............................................................... 94
Abbildung 29: Join in Spark .............................................................................. 95
III
Abbildung 30: Berechnung des Executor-Speichers ........................................ 97
Abbildung 31: Dictionary: Datenbasis ............................................................... 99
Abbildung 32: Dictionary: Daten einlesen und verteilen ................................... 99
Abbildung 33: Dictionary: Filter....................................................................... 100
Abbildung 34: Dictionary: Filtern von positiven Reviews ................................ 100
Abbildung 35: Dictionary: Filtern von Negation und POS-Tags ...................... 101
Abbildung 36: Dictionary: Funktionen zur Filterung ........................................ 101
Abbildung 37: Dictionary: Berechnung der Wortanzahl .................................. 101
Abbildung 38: Dictionary: Abgleich positiver und negativer Wörter ................ 102
Abbildung 39: Dictionary: Erweiterung der Seeds .......................................... 102
IV
Abkürzungsverzeichnis
Tabellenverzeichnis
Tabelle 1: Begriffe einer Meinung....................................................................... 5
Tabelle 2 Meinung 5-Tupel ................................................................................. 7
Tabelle 3: Aufgaben der Sentiment Analyse ...................................................... 8
Tabelle 4: Extrahierte Aspekte im LDMA-Modell .............................................. 19
Tabelle 5: Synonyme und Antonyme zu "good" (WordNet) .............................. 22
Tabelle 6: Muster zur Extraktion von two-word Phrases (entnommen aus Turney)
........................................................................................................ 31
Tabelle 7: Beispiel zur Bayes-Klassifizierung ................................................... 36
Tabelle 8: Tags der POS-Treebank.................................................................. 44
Tabelle 9: Stimmungsveränderte Wörter .......................................................... 49
Tabelle 10: Vergleich von Speichermedien ...................................................... 58
Tabelle 11: Apache Spark Projekt-Aktivität ...................................................... 61
Tabelle 12: Repräsentationselemente von RDDs ............................................. 68
Tabelle 13: Testsysteme .................................................................................. 74
Tabelle 14: Konfigurationsparameter ............................................................... 75
Tabelle 15: Zusammenfassung Datenbasis ..................................................... 76
Tabelle 16: Tags in Datenbasis ........................................................................ 77
Tabelle 17: Performance-Test 1 ....................................................................... 85
Tabelle 25: Dictionary: gefundene Adjektive .................................................. 103
V
RDD
Resilient Distributed Dataset
NLP
Natural Language Processing
KNN
k-Nearest-Neighbour
POS
Part of Speech
LSA
Latent Semantic Analysis
ESA
Explicit Semantic Analysis
HDP
Hierachi-cal Dirichlet Process
LDA
Latent Dirichlet Allocation
LDMA
Latent Dirichlet Markov Allocation
SVM
Support Vector Machine
KI
Künstliche Intelligenz
PMI
Pointwise Mutual Information
ONMTF
nonnegative tri-factorization model (ONMTF)
SSD
Solid State Disk
RAM
Random-Access Memory
HDFS
Hadoop Distributed File System
JSON
JavaScript Object Notation
XML
Extensible Markup Language
VI
Einleitung
1
Einleitung
Die Meinungen anderer Menschen beeinflussen unsere eigenen Entscheidungen
und Ansichtsweisen jeden Tag. Für die Geschäftswelt bedeutet das, dass Kunden
gerne über die Ansichten anderer Kunden informiert sind. So lesen beispielweise
88% der Befragten einer Studie von 20131 Kundenbewertungen um zu sehen, ob
ein lokales Geschäft gut ist. Auch Organisationen haben ein reges Interesse an der
Meinung von Menschen. Dies gilt für Unternehmen, die Kundenfeedback sammeln
ebenso wie für Nachrichtenmagazine, die über Twitter die Stimmung zu aktuellen
Themen sammeln.
Dass Meinungen wichtig sind ist schon lange bekannt. Sie werden deswegen gerne
gesammelt und ausgewertet. Die klassische Herangehensweise, Meinungen zu
sammeln, sind Umfragen und Befragungsbögen. Mit dem Aufkommen des Web 2.0
ergab sich allerdings eine neue Möglichkeit, aktiv Daten nach Meinungen zu durchsuchen: die Sentiment Analyse. Im Internet findet ein reger Informationsaustausch
in Blogs, Foren und Bewertungsportalen statt. Es werden riesige Datenmengen2,
die potentiell nützliche Informationen unter anderem für Unternehmen, Wissenschaftler, Politiker und Dienstleister enthalten, generiert. Aufgrund dieses Datenvolumen ist es nötig, diese maschinell zu entdecken, analysieren und zu bewerten.
Dieser Aufgabe hat sich die Sentiment Analyse gewidmet.
In dieser Arbeit wird die Sentiment Analyse in Hinblick auf die Verarbeitung großer
Datenmengen und des maschinellen Lernens betrachtet. Dabei wird zunächst auf
Grundlage einer intensiven Literaturrecherche der Forschungsstand der Sentiment
Analyse erläutert und anschließend die Grundlagen des maschinellen Lernens erklärt.
In Kontext des Big Data-Bereiche wird am Ende der Arbeit das Framework Apache
Spark genutzt, um Aufgaben der Sentiment Analyse auszuführen. Dabei steht vor
1
2
http://searchengineland.com/88-consumers-trust-online-reviews-much-personal-recommendations-195803
allein 500 Millionen Twitter-Posts pro Tag
1
Einleitung
allem die Performanz und Skalierbarkeit häufig genutzter Algorithmen der Sentiment Klassifikation im Vordergrund.
1.1
Ziel und Aufbau
Mit dieser Arbeit soll gezeigt werden, dass sich Aufgaben der Sentiment Analyse in
das Framework Apache Spark implementieren lassen und dort auf eine performante
Weise ausgeführt werden können.
Um auf dieses Thema hinzuführen, ist diese Arbeit einen theoretischen und praktischen Teil gegliedert. Im theoretischen Teil werden zunächst die Grundlagen der
Sentiment Analyse beschrieben. Dabei wird auf verschiedene Bereiche, wie die Aufgaben, Probleme und Vorgehensweisen eingegangen. Neben der Sentiment Analyse werden auch Grundlagen des maschinellen Lernens und der Klassifikation vermittelt. Anschließend wird auf die technischen Hintergründe der Datenspeicherung
und Apache Spark eingegangen. Der theoretische Teil mündet in einen praktischen
Teil, bei dem Methoden der Sentiment Analyse auf Apache Spark übertragen werden. Dabei wird ein Performance-Vergleich von Spark und Algorithmen zum maschinellen Lernen aus frei verfügbaren Python-Bibliotheken durchgeführt. Es wird
getestet, ab welcher Datenmenge sich die Benutzung der Spark Plattform auf einem
Cluster sich lohnt und wie gut skalierbar das System ist. Als Datenbasis dienen dafür Kundenbewertungen des Onlinehändlers Amazon, die in einer wissenschaftlichen Arbeit ([76]) gesammelt wurden.
2
Fachliche Grundlagen
2
In diesem Kapitel wird auf die fachlichen Grundlagen der Arbeit eingegangen. Dabei
wird zuerst die Sentiment Analyse beschrieben. Im Rahmen dieser Arbeit war es
nicht möglich, alle Bereiche der Sentiment Analyse abzudecken. Stattdessen soll
ein übersichtlicher Einstieg in das Thema gewährt werden, indem die Aufgaben und
Herangehensweisen der Sentiment Analyse erklärt werden, sowie ein etwas tieferer
Einblick in einige Themenbereiche gegeben wird.
Anschließend werden die grundlegenden Konzepte des Maschinenlernens beschrieben. Auch dieses Thema kann natürlich nicht umfassend erläutert werden. Im
Bereich des Maschinenlernens werde ich mich deshalb auf ausgewählte Verfahren
beschränken und nur die statistischen Grundlagen, die für diese Verfahren notwendig sind, erörtern.
2.1
Sentiment Analyse
Die Sentiment Analyse ist ein Themenkomplex aus verschiedenen Bereichen der
Computerlinguistik. Ihr Ziel ist es, die Haltung, Stimmung, Meinung und generelle
Einstellung von Personen zu verschiedenen Entitäten, wie zum Beispiel Produkten,
anderen Personen, Dienstleistungen und aktuellen Themen zu analysieren.
In der Wissenschaft ist die Sentiment Analyse laut [33] derzeit eines der aktivsten
Forschungsgebiete der linguistischen Datenverarbeitung (Natural Language Processing, kurz NLP). Die ersten Forschungen in diesem Bereich fanden um 2000
statt, jedoch wurde vor allem mit dem Web 2.0 ein starker Anstieg in der Forschung
erzielt. Die Stimmungen und Meinungen von Leuten wurden immer interessanter
und wichtiger und vor allem leichter zu erreichen. In Foren, Chats und anderen Plattformen, wie Twitter, tauschen sich täglich Millionen von Menschen aus. Wirtschaftliche Wichtigkeit erlangt die Sentiment Analyse im Bereich der Kundenbewertungen. Für viele Hersteller ist das Feedback ihrer Kunden wichtig und Kaufverhalten
kann über Bewertungen analysiert werden.
3
In diesem Themenbereich werde ich zunächst darauf eingehen, welche Aufgaben
die Sentiment Analyse hat und vor welchen Problemen der Analyst steht. Es wird
genau definiert, was eine Meinung im Sinne des NLP ist und welche Ebenen der
Sentiment Analyse es gibt. Des Weiteren wird erklärt, wie Dokumente nach Meinungen durchsucht und wie diese anschließend analysiert werden können.
2.1.1
Begriffserläuterungen
Sentiment Analyse bezieht sich für gewöhnlich auf subjektive Haltungen von Personen oder Meinungen. Im Folgenden wird genau definiert, was eine Meinung beinhaltet.
Nach Liu Bing in [31] bildet eine Meinung das 5-Tupel
(𝑒𝑖, 𝑎𝑖𝑗 , 𝑠𝑖𝑗𝑘𝑙 , ℎ𝑘 , 𝑡𝑙 )
bei dem 𝑒𝑖 eine Entität bezeichnet, 𝑎𝑖𝑗 ein Aspekt dieser Entität ist und 𝑠𝑖𝑗𝑘𝑙 die negative, positive oder neutrale Stimmung zu dem Aspekt 𝑎𝑖𝑗 der Entität 𝑒𝑖 darstellt.
Das 5-Tupel wird durch den Vertreter der Meinung ℎ𝑘 und durch den Zeitpunkt 𝑡𝑙 ,
an dem die Meinung ausgedrückt wurde, vervollständigt. Dabei gelten für die genannten Begriffe die Definitionen in Tabelle 1. Da die Veröffentlichungen im Bereich
der Sentiment Analyse hauptsächlich auf Englisch sind, führt diese Tabelle auch die
englischen Fachbegriffe.
Bezeichnung
Deutsch
Bezeichnung
lisch
Eng- Erklärung
Entität
Entity, Object, targed Das Ziel, gegen das sich die Meientity
nung richtet.
Aspekt
Aspect, Feature
Ein Teilbereich der Entität, wie zum
Beispiel das Lenkrad eines Autos.
Meinungsvertreter
Opinion holder
Die Person oder Organisation, die
die Meinung ausdrückt.
4
Stimmung,
nung
Mei- Sentiment, Opinion
Die subjektive Haltung des Meinungsvertreters zur Entität im Ganzen oder zu einem Aspekt der Entität.
Tabelle 1: Begriffe einer Meinung
Zur anschaulichen Darstellung werden anhand eines Amazon Reviews zum Tablet
Lenovo YOGA Tablet 2 nun einige Meinungs-5-Tupel gebildet. Dafür sind die einzelnen Sätze der Kundenbewertung mit Zahlen versehen.
Abbildung 1 Kundenbewertung Tablet
„ (1) Das Tablet hat ein sehr gutes und nützliches Design. (2)Der Standfuß lässt so
einiges mit sich machen. (3)Stehen, liegen und durch die Runde Form lässt es dich
sehr gut halten. (4)Durch die Dolby App können Leute doch sanfte Töne aus dem
Tablet abgespielt werden. (5)Ebenfalls hat das Display eine gute Auflösung.
(6)Doch es gibt einige Macken. (7)Einige Apps und der Chrome Browser laufen hackelig ab. (8)Videos werden durch das schwache WLAN mit ladekreiseln geprägt
und
verzögert
die
Ladezeit.
(9)Man darf nicht alles glauben was der Hersteller sagt wie z.B. die Akku-Laufzeit.
(10) Tests bestätigen eine enorm kürzere Laufzeit eines Entladezyklusses.
(11) Das größte Manko ist, die Speichererweiterung. (12)Eine MicroSD mit einer
FAT32 lässt sich nur einfügen. (13) Wenn man weitere Geräte wie externe Festplatte oder USB Stick per OTG einfügen möchte MÜSSEN diese ebenfalls das o.g.
Format haben. (15) Zudem darf auch keine SD eingesteckt sein. (16) Mäuse, Tastaturen, PS3 (Samsung Geräte unterstützen den Controller) und Xbox-Controller
werden
leider
auch
nicht
anerkannt.
(17) In allem ein Mittelmäßiges Tablet. (18) Doch für das Geld gibt es bessere.“
5
Zunächst müssen die Entität und ihre Aspekte identifiziert werden. Die Entität 𝑒𝑖 ist
das Tablet Lenovo YOGA 2. Diese Information wird aus den Meta-Daten der Kundenbewertung gezogen. Innerhalb der Reviews wird statt der offiziellen Bezeichnung lediglich „das Tablet“ (1) verwendet. Man hat also zwei Synonyme, die einer
Entität zugeordnet werden müssen.
𝑒𝑖 = {𝐿𝑒𝑛𝑜𝑣𝑜 𝑌𝑜𝑔𝑎 𝑇𝑎𝑏𝑙𝑒𝑡 2, 𝑇𝑎𝑏𝑙𝑒𝑡}
Innerhalb der Kundenbewertung werden neben dem Tablet selber auch verschiedene Aspekte sowohl neutral als auch mit positiver oder negativer Wertung angesprochen. Ein Beispiel hierfür ist das in Satz 1 positiv erwähnte Design, durch das
das Triple
(𝐿𝑒𝑛𝑜𝑣𝑜 𝑌𝑜𝑔𝑎 𝑇𝑎𝑏𝑙𝑒𝑡 2, 𝐷𝑒𝑠𝑖𝑔𝑛, 𝑝𝑜𝑠𝑖𝑡𝑖𝑣)
gebildet wird.
Der Zeitpunkt, an dem die Meinung geäußert wurde, und der Vertreter der Meinung
werden nicht explizit in der Kundenbewertung erwähnt, sondern müssen aus den
Metadaten genommen werden. In diesem Beispiel gibt es mit dem Amazon-User
„Charalambos“ nur einen Meinungsvertreter. Der Zeitpunkt der Meinungsäußerung
ist der 5. Januar 2015. Diese Information ist besonders wichtig, wenn untersucht
werden soll, wie sich die Meinungen im Laufe der Zeit geändert haben.
Ein vollständiges 5-Tupel wäre demzufolge
(𝐿𝑒𝑛𝑜𝑣𝑜 𝑌𝑜𝑔𝑎 𝑇𝑎𝑏𝑙𝑒𝑡 2, 𝐷𝑒𝑠𝑖𝑔𝑛, 𝑝𝑜𝑠𝑖𝑡𝑖𝑣, 𝐶ℎ𝑎𝑟𝑎𝑙𝑎𝑚𝑏𝑜𝑠, 05.01.2015)
In Tabelle 2 werden die restlichen 5-Tupel, die diesem Review entnommen werden
können, dargestellt.
5-Tupel
Satz
(𝐿𝑒𝑛𝑜𝑣𝑜 𝑌𝑜𝑔𝑎 𝑇𝑎𝑏𝑙𝑒𝑡 2, 𝐷𝑒𝑠𝑖𝑔𝑛, 𝑝𝑜𝑠𝑖𝑡𝑖𝑣, 𝐶ℎ𝑎𝑟𝑎𝑙𝑎𝑚𝑏𝑜𝑠, 05.01.2015)
Satz
1
(𝐿𝑒𝑛𝑜𝑣𝑜 𝑌𝑜𝑔𝑎 𝑇𝑎𝑏𝑙𝑒𝑡 2, 𝑆𝑡𝑎𝑛𝑑𝑓𝑢ß, 𝑝𝑜𝑠𝑖𝑡𝑖𝑣, 𝐶ℎ𝑎𝑟𝑎𝑙𝑎𝑚𝑏𝑜𝑠, 05.01.2015)
Satz
2
(𝐿𝑒𝑛𝑜𝑣𝑜 𝑌𝑜𝑔𝑎 𝑇𝑎𝑏𝑙𝑒𝑡 2, 𝐷𝑜𝑙𝑏𝑦 𝐴𝑝𝑝, 𝑝𝑜𝑠𝑖𝑡𝑖𝑣, 𝐶ℎ𝑎𝑟𝑎𝑙𝑎𝑚𝑏𝑜𝑠, 05.01.2015)
Satz
4
6
(𝐿𝑒𝑛𝑜𝑣𝑜 𝑌𝑜𝑔𝑎 𝑇𝑎𝑏𝑙𝑒𝑡 2, 𝐷𝑖𝑠𝑝𝑙𝑎𝑦, 𝑝𝑜𝑠𝑖𝑡𝑖𝑣, 𝐶ℎ𝑎𝑟𝑎𝑙𝑎𝑚𝑏𝑜𝑠, 05.01.2015)
Satz
5
(𝐿𝑒𝑛𝑜𝑣𝑜 𝑌𝑜𝑔𝑎 𝑇𝑎𝑏𝑙𝑒𝑡 2, 𝑃𝑒𝑟𝑓𝑜𝑟𝑚𝑎𝑛𝑐𝑒, 𝑛𝑒𝑔𝑎𝑡𝑖𝑣, 𝐶ℎ𝑎𝑟𝑎𝑙𝑎𝑚𝑏𝑜𝑠, 05.01.2015)
Satz
7
(𝐿𝑒𝑛𝑜𝑣𝑜 𝑌𝑜𝑔𝑎 𝑇𝑎𝑏𝑙𝑒𝑡 2, 𝑊𝐿𝐴𝑁, 𝑛𝑒𝑔𝑎𝑡𝑖𝑣, 𝐶ℎ𝑎𝑟𝑎𝑙𝑎𝑚𝑏𝑜𝑠, 05.01.2015)
Satz
8
(𝐿𝑒𝑛𝑜𝑣𝑜 𝑌𝑜𝑔𝑎 𝑇𝑎𝑏𝑙𝑒𝑡 2, 𝐴𝑘𝑘𝑢, 𝑛𝑒𝑔𝑎𝑡𝑖𝑣, 𝐶ℎ𝑎𝑟𝑎𝑙𝑎𝑚𝑏𝑜𝑠, 05.01.2015)
Satz
9 /
10
(𝐿𝑒𝑛𝑜𝑣𝑜 𝑌𝑜𝑔𝑎 𝑇𝑎𝑏𝑙𝑒𝑡 2, 𝑆𝑝𝑒𝑖𝑐ℎ𝑒𝑟𝑒𝑟𝑤𝑒𝑖𝑡𝑒𝑟𝑢𝑛𝑔, 𝑛𝑒𝑔𝑎𝑡𝑖𝑣, 𝐶ℎ𝑎𝑟𝑎𝑙𝑎𝑚𝑏𝑜𝑠, 05.01.2015) Satz
11
(𝐿𝑒𝑛𝑜𝑣𝑜 𝑌𝑜𝑔𝑎 𝑇𝑎𝑏𝑙𝑒𝑡 2, 𝑃𝑒𝑟𝑖𝑝ℎ𝑒𝑟𝑖𝑒𝑎𝑛𝑏𝑖𝑛𝑑𝑢𝑛𝑔, 𝑛𝑒𝑔𝑎𝑡𝑖𝑣, 𝐶ℎ𝑎𝑟𝑎𝑙𝑎𝑚𝑏𝑜𝑠, 05.01.2015) Satz
16
(𝐿𝑒𝑛𝑜𝑣𝑜 𝑌𝑜𝑔𝑎 𝑇𝑎𝑏𝑙𝑒𝑡 2, 𝑇𝑎𝑏𝑙𝑒𝑡, 𝑛𝑒𝑢𝑡𝑟𝑎𝑙, 𝐶ℎ𝑎𝑟𝑎𝑙𝑎𝑚𝑏𝑜𝑠, 05.01.2015)
Satz
17
(𝐿𝑒𝑛𝑜𝑣𝑜 𝑌𝑜𝑔𝑎 𝑇𝑎𝑏𝑙𝑒𝑡 2, 𝑃𝑟𝑒𝑖𝑠, 𝑛𝑒𝑔𝑎𝑡𝑖𝑣, 𝐶ℎ𝑎𝑟𝑎𝑙𝑎𝑚𝑏𝑜𝑠, 05.01.2015)
Satz
18
(𝐿𝑒𝑛𝑜𝑣𝑜 𝑌𝑜𝑔𝑎 𝑇𝑎𝑏𝑙𝑒𝑡 2, 𝑇𝑎𝑏𝑙𝑒𝑡, 𝑛𝑒𝑔𝑎𝑡𝑖𝑣, 𝐶ℎ𝑎𝑟𝑎𝑙𝑎𝑚𝑏𝑜𝑠, 05.01.2015)
Satz
18
Tabelle 2 Meinung 5-Tupel
2.1.2
Aufgaben und Probleme
Für die Sentiment Analyse ist es zuerst notwendig, die essentiellen Bestandteile
des im vorherigen Kapitel definierten 5-Tupel zu finden. Je nach Ebene der Sentiment Analyse (Kapitel 2.1.3) sind allerdings nicht alle Bestandteile notwendig. Wichtig ist zunächst das Finden der Entitäten und ihrer dazugehörigen Aspekte. Auf mögliche Features wird in Kapitel 2.2.4 eingegangen, während die Extraktion dieser
Features in Kapitel 2.1.3.2 beschrieben wird. Bereits an dieser Stelle ergeben sich
Herausforderungen. Nur die relevanten Entitäten müssen herausgezogen werden
7
und, wenn sie wie in Abbildung 1 auch unter Synonymen auftreten, gruppiert werden. Bei den Aspekten verhält es sich ähnlich und es kommt noch dazu, dass Aspekte nicht immer explizit genannt werden (Kapitel 2.1.3.2). Natürlich muss auch in
Erfahrung gebracht werden, ob zu den gefundenen Entitäten und Aspekten überhaupt eine Stimmung ausgedrückt wird oder ob schlichtweg Fakten genannt werden.
Eine Übersicht über die verschiedenen Aufgaben in den jeweiligen Ebenen wird in
[29] gegeben und im Folgenden kurz aufgelistet. Die Tabelle 3 macht deutlich, dass
sich die Aufgaben der Sentiment Analyse an den Ebenen orientieren. Die Ebenen
werden deswegen in den folgenden Abschnitten genauer erläutert.
Ebene
Aufgaben
DokumentenEbene
1. Klassifizierung von Kundenbewertungen mit den Klassen positiv,
neutral, negativ.
Satz-Ebene
1. Herausfinden, ob der gegebene Satz subjektiv ist und eine Meinung ausdrückt.
2. Klassifizierung des Satzes mit den Klassen positiv, neutral, negativ.
Aspekt-Ebene
1. Aspekte extrahieren
2. Herausfinden, ob die Meinungen zu den Aspekten positiv, neutral, negativ sind.
3. Gruppierung der Aspekte und Zusammenfassung der Meinungen.
Tabelle 3: Aufgaben der Sentiment Analyse
8
2.1.3
Ebenen der Sentiment Analyse
Man unterscheidet generell drei Ebenen, auch Level genannt, in der Sentiment Analyse. Die gröbste Ebene ist die Dokumenten-Ebene, bei der der gesamte Text nur
eine Meinung zu einem Produkt ausdrückt. Dies findet zum Beispiel bei Filmkritiken
Anwendung. Etwas feiner ist die Satz-Ebene, bei der jeder Satz einzeln analysiert
wird. Häufig reicht aber auch dieser Feinheitsgrad nicht aus, weswegen bei der Analyse auf der Aspekt-Ebene jeder einzelne Aspekt einer Entität betrachtet wird. Im
Folgenden werden die Ebenen genauer beschrieben und auf Besonderheiten eingegangen.
2.1.3.1 Dokumenten-Ebene
Eine Analyse auf der Dokumenten-Ebene bezieht sich auf das gesamte MeinungsDokument. Es wird untersucht, ob insgesamt ein positives oder negatives Sentiment
vorliegt. Eine Analyse auf dieser Ebene ist sinnvoll, wenn nur eine einzige Entität
als Untersuchungsobjekt vorliegt. Die Meinung wird nur genauer von einer Instanz
vertreten. Dies ist zum Beispiel bei Kundenbewertungen unterschiedlicher Produkte
und Dienstleistungen der Fall, da hier meistens nur genau ein Produkt von einer
Person bewertet wird. Problematisch wird es, wenn in einem Dokument mehrere
Produkte bewertet werden, wie es bei Blog-Beiträgen vorkommt, oder wenn es, wie
in Foren, mehrere Meinungsvertreter gibt.
“Sentiment classification assumes that the opinion document d (e.g., a product review) expresses opinions on a single entity e and the opinions are from a single
opinion holder h.” (Liu Bing, in [61] Seite 422)
Das in Kapitel 2.1.1 definierte 5-Tupel wird in diesem Fall vereinfacht dargestellt.
(e, allgemein, s, h, t)
9
Die Entität e wird von dem Vertreter der Meinung h mit der übergreifenden Stimmung s klassifiziert. Dabei können e, h und t bekannt, unbekannt, relevant oder
irrelevant sein.
Das Vorgehen bei der Sentiment Analyse entscheidet sich danach, welche Werte s
annehmen kann. Man unterscheidet hierbei zwischen kategorischen Werten, wie
zum Beispiel positiv und negativ, bei denen ein Klassifizierungsproblem entsteht,
und numerischen beziehungsweisen ordinären Werten, wie zum Beispiel 1-10
Sterne, bei denen ein Regressionsproblem entsteht.
2.1.3.2 Satz-Ebene
Die Analyse auf der Dokumenten-Ebene ist für viele Anwendungen zu ungenau, da
im ganzen Dokument nur eine Meinung ausgedrückt werden kann. Eine genauere
Untersuchungsmöglichkeit bietet die Analyse auf der Satz-Ebene. In diesem Fall
wird jeder Satz auf eine ausgedrückte Meinung untersucht.
Das in Kapitel 2.1.1 definierte 5-Tupel wird auf der Satz-Ebene nicht genutzt. Dies
liegt daran, dass die Analyse auf Satz-Ebene nur einen Zwischenschritt darstellt.
Wenn der Satz aus dem Dokument gelöst ist, kann der Bezug auf die Entität verloren gehen. Der Satz „Ich mochte es nicht.“ liefert auf Satzebene zwar eine negative
Haltung und einen Meinungsvertreter, aber die Entität wird erst deutlich, wenn der
Satz im Kontext zu den anderen Sätzen, also auf Dokumentenebene, gesehen wird.
Klassifikation auf der Satz-Ebene kann entweder als 3-Klassen-Problem (neutral,
negativ, positiv) oder als zweistufiges Problem gesehen werden, bei dem in einem
ersten Schritt danach klassifiziert wird, ob ein Satz eine Meinung enthält und im
zweiten Schritt, ob diese Meinung positiv oder negativ ist (vgl. Liu). Dieses Vorgehen wird auch als Subjectivity Classification bezeichnet.
10
2.1.3.2.1 Subjectivity Classification
Subjectivity Classification ist die Einteilung von Sätze in objektive und subjektive
Sätze. Objektive Sätze nennen im Allgemeinen nur Fakten, während subjektive
Sätze Meinungen, Stimmungen und Einstellungen bestimmter Personen gegenüber
beliebigen Entitäten ausdrücken. Ein guter Indikator für Subjektivität sind Adjektive.
Wiebe zeigt in [10] dass in einem Corpus mit mehr objektiven als subjektiven Sätzen
die Wahrscheinlichkeit, dass ein Satz subjektiv ist, wenn er ein Adjektiv enthält, bei
über 55% liegt. Dennoch kann der Unterschied zwischen einem objektiven und einem subjektiven Satz sehr subtil sein:
„Der Fernseher hat ein gutes Bild.“
„Der Fernseher ist ein gutes Gerät, um Filme zu gucken.“
Obwohl beide Sätze das Adjektiv „gut“ enthalten, ist nur der erste subjektiv, während
der zweite objektiv ist. Darüber hinaus können auch Substantive der Subjectivity
Classification dienen. Riloff et al erreichen in [22] mit dem naïve Bayes Klassifikator
(Kapitel 2.2.3.1)und Substantiven als Features eine Genauigkeit von circa 81%.
Kamal versucht Subjectivity Classification in [31] durch überwachtes Lernen. Dafür
nutzt er Unigrams und die Features TF-IDF, Position, Part-of-Speech, Opinion Indicator Seed Word (Stimmungswörter), Negation und Adverbien. Von den angewandten Klassifikatoren erzielte der naïve Bayes die besten Ergebnisse. Als präzisestes
Feature stellte sich Part-of-Speech heraus.
Eine weitere Herangehensweise zur Klassierung nach subjektiven und objektiven
Sätzen ist in [23] zu finden. Das in den meisten Fällen außer Acht gelassene Feature „Readiblity“ (Lesbarkeit) wird hier zur Klassierung genutzt. Die These dabei ist,
dass Sätze mit schlechter Lesbarkeit dazu tendieren, objektiv zu sein. Als Beispiel
hierfür kann ein Satz aus dem Wikipedia-Artikel zum Thema „Flash-Speicher“3 dienen:
3
http://de.wikipedia.org/wiki/Flash-Speicher#Funktionsprinzip
11
„Anders als das Gate bei normalen MISFETs ist das Floating-Gate von allen anderen Teilen (Kanalgebiet und von Steuer-Gate) durch ein Dielektrikum (derzeit
meist Siliziumdioxid) elektrisch isoliert; das Potential auf dem Floating-Gate ist daher im Grunde undefiniert (dies wird auch als schwimmend, englisch floating, bezeichnet).“
Dieser Satz ist nicht leicht verständlich, da er neben einer recht komplexen Struktur
auch viele Fachbegriffe enthält. Zum Testen der aufgestellten These werden sechs
verschiedene Lesbarkeits-Indikatoren als Feature genutzt. Jeder dieser Indikatoren
basiert auf mindestens einem der folgenden Merkmale:
1.
2.
3.
4.
5.
Durchschnittlich Wortlänge
Durchschnittliche Satzlänge
Durchschnittliche Anzahl einsilbiger Wörter pro Satz
Durchschnittliche Anzahl mehrsilbiger Wörter pro Satz
„Bekanntheit“ der Wörter (Frequenz in Leipzig`s Wortschatz4)
Die eigentliche Klassifikation wurde mit einer Support Vector Machine vorgenommen. Obwohl die verwendeten Merkmale als „rather crude“ (Remus) anzusehen
sind, konnte mit dem Experiment ein Verhältnis zwischen Lesbarkeit und Subjektivität hergestellt werden. Die Lesbarkeit ist also ein brauchbares Feature für die Subjectivty Classification auf Satz-Ebene.
2.1.3.2.2 Sarkasmus
Sarkasmus bezeichnet beißenden Spott und Hohn, der oftmals sehr subtil vermittelt
wird und dadurch maschinell besonders schwierig zu erkennen ist. Im Kontext der
Sentiment Analyse bewirkt Sarkasmus, dass eine positive Stimmung negativ wird
und umgekehrt.
Nach Liu in [33] spielt Sarkasmus in Kundenbewertungen eine untergeordnete
Rolle, während er online häufig in Diskussionen und Kommentaren anzutreffen ist.
4
http://wortschatz.informatik.uni-leipzig.de/
12
Eine häufige Datenquelle für die Forschung in Sarkasmus-Erkennung ist die OnlinePlattform Twitter.
In [51] wurde Sarkamus-Erkennung mithilfe von halb-überwachtem Lernen durchgeführt. Als Datensets dienten zum einen eine Sammlung von 5.9 Millionen TwitterBeiträgen (Tweets) und zum anderen eine Sammlung von 66000 Amazon-Reviews.
Zwei Beispielsätze aus den untersuchten Daten zeigen, wie schwierig SarkasmusErkennung sein kann.
1. „thank you Janet Jackson for yet another year of Super Bowl classic rock!“ (Twitter)
2. „[I] Love The Cover“ (Amazon, Buch-Review)
Der erste Satz bezieht sich auf den (angeblich) schwachen Super Bowl-Auftritt Janet Jacksons im Jahr 2010. Die negative Haltung wird hier nur durch den Vergleich
mit dem viel kritisierten Auftritts im Vorjahr („yet another“) erkennbar. Dennoch gibt
es keinen expliziten Verweis darauf, dass das Vorjahr wirklich als negativ einzustufen gilt.
Das zweite Beispiel wirkt alleingestellt zunächst durchaus positiv. Die Metadaten
enthalten jedoch die Information, dass der Titel der Kundenbewertung „don’t judge
a book by its cover“ ist. Durch diese subtile Nutzung der Redewendung, muss der
Bewertungstext als negativ angesehen werden.
Um diese Herausforderungen zu meistern, wurden in [51] Muster in Sätzen identifiziert. Dafür wurden zunächst spezifische Wörter, wie zum Beispiel Produktnamen,
Buchtitel, Autoren und User, durch allgemeine Tags ersetzt. Anschließend wurden
die vorkommenden Wörter in high-frequency words (häufig vorkommenden Wörter,
kurz HFWs) und content words (Wörter, die nicht so häufig vorkommen, kurz CWs)
unterteilt, wobei auch die gesetzten Tags und Satzzeichen als Wörter gelten. Ein
Satzmuster kann aus 2-6 HFWs und 1-6 CWs bestehen. Ein einzelner Satz kann
also mehrere Muster enthalten, die sich überschneiden können. Nachdem einige
Muster aussortiert wurden, wurden die übriggebliebenen Muster als Feature-Vektoren mit den Werten exact Match (alle Teile des Musters treten in der korrekten Reihenfolge ohne zusätzliche Wörter auf), sparse Match (zusätzliche Wörtern können
zwischen den einzelnen Teilen des Musters liegen), incomplete Match (nur ein paar
Teile des Musters treten auf) und no Match (kein oder nur ein Teil eines Musters)
13
genutzt. Zusätzlich wurden die Satzlänge, sowie die Anzahl von Ausrufezeichen,
Fragezeichen, Anführungsstrichen und großgeschriebenen Wörtern als generische
Feature genutzt.
Vor der Durchführung der Klassifikation mit der KNN-Methode, wurde eine Basis,
gegen die sich der vorgeschlagene Algorithmus messen muss, gebildet. Diese Basis basiert auf der Annahme, dass klassischer Sarkasmus die Form „das Gegenteil
von dem, was gemeint ist, sagen“ annimmt. Sollte eine Amazon-Kundenbewertung
einen positiven Text, aber eine negative Sterne-Bewertung (1-3 Sterne) haben, erfüllt sich dieses Schema. Das gleiche gilt für den umgekehrten Fall.
Das Ergebnis des Experiments zeigt, dass der Algorithmus der Mustererkennung
effektiver als die Basis ist. Die Genauigkeit ist mit 0.76 höher als die der Basis (0.5).
Darüber hinaus weisen das F-Maß (Basis 0.24; Experiment 0,788) und die falschen
Negative/Positive darauf hin, dass die Annahme, Sarkasmus sei nur das Gegenteil
von dem, was gesagt wird, zu trivialisiert ist und die subtileren Formen des Sarkasmus bei der Basis nicht erkannt wurden. Ein weiteres Ergebnis war, dass die Punktation der schwächste Prädikator ist. Die Ausnahme hierbei bilden drei aufeinanderfolgende Punkt („…“), die in Kombination mit anderen Features einen starken Prädikator bilden.
Ein weiterer Versuch zur Sarkasmus-Erkennung wurde in [21] unternommen. Es
wurde ein Algorithmus entwickelt, der Tweets, die eine positive Stimmung zu einer
negativen Situation beinhalten, identifiziert. Dies ist eine sehr spezielle Form des
Sarkasmus. Mithilfe eines Bootstrapping-Algorithmus und den Twitter-Hashtags
#sarcasm und #sarcastic wurden zunächst sarkastische Tweets gesammelt und
dann ausgehend vom Wort „love“, das als das häufigste positive Stimmungswort in
sarkastischen Tweets gilt, weitere positive Stimmungswörter und negative Situationen gesammelt. Ein Satz galt dann als sarkastisch, wenn eine negative Situation
direkt auf ein positives Stimmungswort fällt.
Das Experiment hat gezeigt, dass die Kombination „positive Verbalphrase gefolgt
von negativer Situation“ ein guter Hinweis auf Sarkasmus ist, während die Kombination „positive Verbalphrase gefolgt von negativem Sentiment“ weitaus schlechtere Werte erzielte. Dennoch stößt die Methode in einigen Situation an ihre Grenzen. Es wurden zwar Sätze wie
14
„I love fighting with the one I love“
„love working on my last day of summer“
„Can´t wait to wake up early to babysit“
als sarkastisch identifiziert, aber es gab auch falsche positive. Dies kommt daher,
dass einige Situationen häufig, aber nicht immer, negativ sind (es gibt Menschen,
die tatsächlich gerne früh aufstehen). Des Weiteren wurden zu allgemeine Situationen („I love working there“) als sarkastisch eingestuft.
2.1.3.3 Aspekt-Ebene
Die Analyse auf der Aspekt-Ebene ist die genaueste Form der Sentiment Analyse.
Anders als die Analyse auf der Dokumenten- oder Satz-Ebene, wird bei der AspektEbene das in Kapitel 2.1 definierte 5-Tupel
(𝑒𝑖, 𝑎𝑖𝑗 , 𝑠𝑖𝑗𝑘𝑙 , ℎ𝑘 , 𝑡𝑙 )
vollständig genutzt. Konkret bedeutet das, dass nun zu jedem Teil (Aspekt) einer
bestimmten Entität, die Stimmung eines Meinungsvertreters zu einem bestimmten
Zeitpunkt bestimmt werden kann. Anders als bei der Dokument-Ebene, in der ein
komplettes Dokument nur eine Stimmung zu einer Meinung ausdrücken kann, können Meinungen nun differenzierter betrachtet werden. So ist es häufig der Fall,
dass, zum Beispiel bei einer Produktbewertung, ein Teilbereich des Produkts als
negativ angesehen wurde, obwohl andere Bereiche und das Produkt insgesamt als
durchaus positiv gewertet wurden.
Nach Liu sind für die Analyse auf der Aspekt-Ebene zwei Schritte, die Aspekt Extraktion und die Sentiment Klassifikation, ausschlaggebend. Die Aspekt Extraktion
wird im folgenden Kapitel erklärt, während die Sentiment Klassifikation ein Teil des
Kapitels 2.2 ist.
15
2.1.3.3.1 Aspekt Extraktion
Der erste Schritt ist zunächst immer das Finden und Extrahieren der einzelnen Aspekte. Man unterscheidet hier zwischen expliziten und impliziten Aspekten. Ein expliziter Aspekt ist im Normallfall ein Substantiv, das den Teilbereich der Entität benennt. Dies könnte im Bereich der Produktbewertungen zum Beispiel „Geschwindigkeit“ oder „Preis“ sein. Implizite Aspekte werden meistens durch andere Wörter
beschrieben und nicht ausdrücklich genannt. So könnte der explizite Aspekt „Preis“
implizit durch die Wörter „billig“ oder „teuer“ erwähnt werden, während „Geschwindigkeit“ durch „langsam“ oder „schnell“ genannt werden kann.
Für das Finden von expliziten Aspekten werden hauptsächlich vier verschiedene
Herangehensweisen genutzt (vgl [33]).
Zum einen wird die Extraktion anhand von häufig genutzten Substantiven und Nominalphrasen vollzogen. Im einfachsten Fall wird das hierbei mit einem Part-of-Speech-Tagger bearbeitet und anschließend nach häufig vorkommenden Substantiven
und Nominalphrasen gefiltert. Diese Methode funktioniert vor allem bei Kundenbewertungen, da sich das Vokabular generell sehr ähnelt, wenn Menschen über die
verschiedenen Aspekte eines Produkts schreiben. Die weniger häufig genutzten
Wörter stehen meist nicht im direkten Zusammenhang zum Produkt und unterscheiden sich von Bewertung zu Bewertung stark. In fortgeschrittenen Methoden wird
versucht, nur Substantive und Nominalphrasen zu extrahieren, die in SentimentSätze vorkommen oder einem bestimmten Muster folgen.
Zum anderen können Aspekte durch ihre Beziehung zu Stimmungswörtern extrahiert werden. Die Stimmungswörter selber sind oft bekannt („großartig“, „schlecht“).
Sollten die Aspekte nicht bekannt sein, kommt das dem Stimmungswort am nächsten stehende Substantiv, bzw. die am nächsten stehende Nominalphrase, als Aspekt in Frage. Weiterreichende Extraktion kann hier durch die Erkennung von Dependenzgrammatik erreicht werden. Dieses linguistische Gebiet beschäftigt sich mit
der hierarchischen Struktur von Sätzen und den wechselseitigen Beziehungen,
16
bzw. Abhängigkeiten, von Wörtern. Zur Erkennung von Dependenzen können spezielle Parser verwendet werden.
Topic Models sind statistische Modelle, die vor allem in der Text Klassifizierung für
das Finden von Topics, also Themenbereichen, verwendet werden. Man geht dabei
davon aus, dass ein Dokument über ein bestimmtes Thema mehr themenspezifische Wörter enthält als ein Dokument, in dem dieses Thema nicht vorkommt. So
enthält ein Dokument über das Thema „Essenszubereitung“ wahrscheinlich Wörter
wie „kochen“, „braten“ und „schmecken“, während das Thema „Haustiere“ eher Wörter wie „Hund“, „Katze“ oder „Hamsterrad“ enthalten wird. Im Normalfall tauchen in
einem Dokument mehrere unterschiedliche Themen auf. Topic Models machen sich
diese Eigenschaft zu Nutze, indem sie von der statistischen Verteilung der Wörter
auf die Zusammensetzung der Themen schließen. Obwohl Topic Models zunächst
nur der Themenerkennung dienen, können sie leicht für die Sentiment Analyse erweitert werden (vgl. [31]). Im Bereich der Aspect Extraction sind die gefundenen
topics Aspekte. Allerdings müssen die Modelle hier erweitern werden, da zusätzlich
zu den Aspekten auch die Stimmungswörter gefunden werden müssen.
Mit Latent Semantic Analysis (LSA), Explicit Semantic Analysis (ESA), Hierachical
Dirichlet Process (HDP) und Latent Dirichlet Allocation (LDA) gibt es verschiedene
Topic Models, die für die Text Klassifizierung und die Sentiment Analyse genutzt
werden. Die klassischen Vorgehensweisen sind hierbei das LSA und das LDA, wobei das LDA, beziehungsweise erweiterte Formen von ihm, das meistgenutzte Model darstellt. Aus diesem Grunde wird im Folgenden kurz genauer auf das LDA eingegangen, während die anderen Modelle zunächst außer Acht gelassen werden.
Das Latent Dirichlet Allocation-Modell basiert, wie die anderen Modelle auch, auf
einem Bayesschen Netz, in dem die Knoten Zufallsvariablen und die Kanten die
Abhängigkeiten zwischen den Knoten beschreiben. Abbildung 2 stellt das LDA graphisch dar. Die schattierten und unschattierten Kreise zeigen beobachtbare und
nicht beobachtbare (latente) Variablen, die gerichteten Pfeilen zwischen ihnen die
Abhängigkeiten und die Rechtecke, die die Variablen umrunden, deuten eine mehrfache Ausführung der Schritte (die Anzahl wird jeweils durch den Buchstaben im
Rahmen gezeigt) an.
17
Abbildung 2: LDA Topic Model5
Wenn M die Anzahl der zu untersuchenden Elemente ist, jedes Dokument eine
Folge von N Wörtern ist, jedes Wort ein Element aus einem Vokabel-Index mit V
unterschiedlichen Elementen und T die Anzahl der Topics ist, verläuft der Algorithmus zur Wortgenerierung so:
1. Für jedes Topic z = {1…K}
ziehe die Dirichletverteilung ϕZ ~ Dirchlet (β)
2. Für jedes Dokument m = {1…M}
ziehe θm ~ Dirchlet(α)
für jedes Wort wi im Dokument m
ziehe ein Topic zd,i ~ θm
ziehe ein Wort wd,i ~ ϕZ d,i
Es sollen also die Verteilung von Topic-Wörtern, die Ausmaße der Topics und weitere Modell-Parameter gefunden werden.
In [59] hat das LDA zu einem mit dem Hidden Markov Model verbundenen Topic
Model, dem LDMA, erweitert. Das LDMA geht anders als das LDA nicht davon aus,
dass Wörter unabhängig voneinander auftreten und ignoriert somit auch die Wortposition. Durch das Hinzufügen einiger Variablen wird bei der Wortgenerierung entschieden, ob ein Wort als Unigramm, Bigramm oder Trigramm erstellt werden soll.
Aufeinanderfolgende Wörter haben also generell das gleiche Topic.
5
http://en.wikipedia.org/wiki/Latent_Dirichlet_allocation#mediaviewer/File:Smoothed_LDA.png
18
Durch diese Erweiterung war es möglich, in einem Testdatensatz über Kundenbewertungen zu Digitalkameras genauere Aspekte als im LDA zu finden. In Tabelle 4
sind zur Veranschaulichung einige Beispiele abgebildet.
Kundenbewertungen zu Canon-Kameras
LDMA
LDA
Canon
Canon
Canon powershot
Powershot
Digital zoom
Zoom
Optical zoom
Digital
picture quality
Picture
Photos quality
quality
Tabelle 4: Extrahierte Aspekte im LDMA-Modell
Während es viele Methoden gibt, um explizite Aspekte zu extrahieren, wurden bisher nur wenige Vorschläge der Wissenschaft, implizite Aspekte aus Texten herauszuziehen. Dies liegt unter anderem daran, dass der Großteil der in Kundenbewertungen genannten Aspekte explizit ist.
Dennoch gibt es einige Arbeiten, die sich mit diesem Thema beschäftigen. In [66]
werden implizite Aspekte mithilfe von Kookkurrenz-Assoziationsanalyse (co-occurrence Association Mining). Dieses Verfahren macht sich die Kookkurrenz, also das
gemeinsame Auftreten, von Stimmungswörtern und Aspekten zu nutze. Das Stimmungswort bildet in der Assoziationsregel das Antezedens und der Aspekt die Konsequenz („Wenn [Stimmungswort], dann [Aspekt]“). In einem ersten Schritt werden
diese Assoziationsregeln generiert und in einem zweiten Schritt durch Clustering
robuster gemacht. Anschließend wird nach Stimmungswörtern gesucht, denen kein
expliziter Aspekt zugeordnet wird und anhand der generierten Regeln das beste
Cluster und somit der geeignetste Aspekt zugeordnet.
Dieses Vorgehen kann ein relativ hohes F-Maß von ca. 74% erreichen und durch
das Hinzufügen von Substring-, Abhängigkeits- und topic model-Regeln erweitert
19
werden. Allerdings wird es dadurch beschränkt, dass nur implizite Aspekte gefunden werden können, die auch explizit im Dokument vorhanden sind.
Als Alternative wurde in [18] ein mehrstufiger Algorithmus vorgeschlagen. Zunächst
wird aus einem Trainingsdatensatz eine Liste mit allen einzigartigen impliziten Aspekten F, eine Liste mit allen einzigartigen Lemmata O und eine Kookurrenz-Matrix
C aus den impliziten Aspekten und Lemmata mit den Dimensionen |F|x|O| generiert.
Darauffolgend wird für jeden potentiellen impliziten Aspekt ein Wert berechnet, der
sich aus der Summe der Kookkurrenz jedes Wortes geteilt durch seine Häufigkeit
bildet. Für jeden Satz wird der Aspekt ausgewählt, für den der höchste Wert ermittelt
wurde und dessen Wert eine vorher festgelegte Grenze überschritten hat. In Pseudocode wird der Algorithmus wie in Abbildung 3 dargestellt.
Abbildung 3: Schoutens Algorithmus zur Erkennung neuer Aspekte
Diese Methode stellt eine Verbesserung gegenüber anderen Verfahren dar und erreicht generell eine höhere Performance. Des Weiteren muss durch den vorgegeben Grenzwert nicht jeder Satz einen impliziten Aspekt enthalten. Eine Annahme,
die der zuvor beschriebene Algorithmus trifft. Nachteilig wirkt sich aus, dass nur
maximal 1 Aspekt pro Satz gefunden werden kann und der Grenzwert nicht pro
Aspekt gilt.
20
2.1.4
Sentiment Lexikon
Ein offensichtliches Konzept der Sentiment Analyse ist es, Wörtern positive, negative und neutrale Stimmungen zuzuordnen. Diese Wörter können in Listen gesammelt und für die weitere Analyse, wie zum Beispiel bei der Klassierung 6, genutzt
werden. Nach [33] gibt es grundsätzlich drei Vorgehensweisen, um ein Sentiment
Lexikon zu erstellen: manuell, basierend auf Wörterbüchern und basierend auf dem
gegeben Text-Korpus.
Im manuellen Ansatz wird per Hand eine Liste aus positiven und negativen Wörtern
zusammengestellt. Durch die Vielzahl möglicher Wörter ist die Aufgabe sehr zeitund ressourcenintensiv. So gibt es im Englischen über 42 000 Adjektive 7, von denen
viele dazu in Frage kommen, Stimmungen auszudrücken. Hinzu kommen nach Substantive und selbst Wörter, die häufig falsch geschrieben werden und dadurch am
besten mehrmals in einem Sentiment Lexikon erscheinen müssten („beautiful“,
„beautifull“). Aus diesem Grund wird die manuelle Methode eher zu Verifizierung
automatisch gesammelter Lexika genutzt.
Bei dem auf Wörterbüchern basierenden Ansatz werden zunächst einige Wörter,
deren Sentiment bekannt ist, manuell rausgesucht. Diese Wörter werden als Seed
bezeichnet. Anschließend wird ein Online-Wörterbuch genutzt, um für die Seeds
Synonyme und Gegenteile zu finden. Wenn zum Beispiel „good“ als Seed gewählt
und WortNet als Wörterbuch gewählt wird, würde man an die in Tabelle 5 gezeigten
Wörter kommen.
6
7
siehe auch Kapitel 2.2.4 zur Feature Selection
http://www.oxforddictionaries.com/words/how-many-words-are-there-in-the-english-language
21
Good
Synonyme
Gegenteil
bang-up, bully, corking, cracking, bad
dandy, great, groovy, keen,neat, nifty,
not bad, peachy, slap-up, swell, smashing, old, satisfactory, acceptable, decent, solid, superb, well-behaved, hot,
redeeming, serious
Tabelle 5: Synonyme und Antonyme zu "good" (WordNet)
Diese Wörter werden ins Lexikon aufgenommen. Dabei gilt, dass die Synonyme das
gleiche Sentiment ausdrücken und die Gegenteile das gegenteilige Sentiment ausdrücken. Mit den neu gefundenen Wörtern kann nun eine neue Suche im Wörterbuch gestartet werden. So baut sich das Lexikon langsam auf. Am Ende des Prozesses kann das Lexikon manuell auf Korrektheit geprüft werden.
Dieses Vorgehen wurde zum Beispiel in [43] und [67] genutzt. Der Nachteil dieser
Methode besteht darin, dass der logische Zusammenhang zwischen den Synonymen nachlässt, wenn viele Iterationen durchgeführt werden. Dieses Problem wird in
[68] mit dem Beispiel von WordNet aufgefasst. Es ist möglich, mit der Hilfe von Synonymen in nur drei Iterationen von „good“ auf „bad“, also dem Antonym zu kommen
(Abbildung 4).
22
Abbildung 4: Vier Wege um von "good" auf "bad" zu kommen (Godbole)
Um diesem Problem entgegenzuwirken, wurde der Algorithmus so angepasst, dass
für jedes gefundene Wort ein Wert berechnet wird. Die gefunden Wörter verlieren
an Gewicht, wenn sie über einen langen Pfad (die Sprünge von Wort zu den Synonymen) gefunden wurden. Der wahre Wert jedes Wortes ist die Summe aller Werte
über die einzelnen Pfade. Zusätzlich dazu wird geprüft, ob ein genutzter Pfad zwischen positiven und negativen Wörtern wechselt. Pfade werden nur akzeptiert,
wenn die Anzahl der Wechsel unterhalb einer bestimmten Grenze bleibt. Des Weiteren werden nur die Synonyme und Antonyme ausgewählt, die in der WordNetListe weit oben stehen. Dieses Vorgehen nutzt die Sortierung von WordNet nach
Sense, also der Sinnhaftigkeit, der gegebenen Synonyme und Gegenteile. Zum
Schluss werden von den gefundenen Wörtern nur diejenigen genommen, die die
höchsten berechneten Werte haben, um nicht eindeutig negative oder positive Wörter ausschließen zu können.
Der auf Wörterbüchern basierende Ansatz hat den Vorteil, dass Stimmungswörter
recht einfach und schnell gefunden werden können. Allerdings sind die gefundenen
Wörter sehr allgemein und nicht auf bestimmten Domänen bezogen. Stimmungswörter können in unterschiedlichen Bereichen andere Bedeutungen haben. So ist
das Wort „love“ fast immer positiv, wenn es aber in einem Bericht zu einem Tennisspiel genutzt wird, steht es höchstwahrscheinlich dafür, dass in diesem Spiel keine
23
Punkte erzielt wurden. Ein ähnliches Beispiel ist der Nutzung von „loud“. Es ist erwünscht, dass Lautsprecher laut werden können, aber unerwünscht, dass der Kühlschrank laut ist.
Um auf dieses Problem besser reagieren zu können, wird statt des Wörterbuchs
basierten Ansatz der auf dem Text-Korpus basierende Ansatz genutzt. Der Korpus
basierte Ansatz ist angepasster und enthält in der Regel mehr themenspezifische
Wörter. Eines der ersten Konzepte für diesen Ansatz wird in [63] vorgeschlagen.
Ausgehend von einigen manuell ausgesuchten Adjektiven als Seed, sollten mithilfe
bestimmter Regeln neue Adjektive im Korpus gefunden werden. Die Idee hinter diesen Regeln ist, dass zusammenhänge Sätze, Wörter und Satzteile in ihrem Sentiment konsistent sein sollten. Eine der Regeln besagt beispielsweise, dass Adjektive,
die mit einem „and“ verbunden sind, die gleiche Stimmung ausdrücken („this refrigerator is quit and spacious“). Ähnliche Regeln wurden für Verbindungen mit or, but,
either-or und neither-nor aufgestellt. Da diese Verbindungen in der Realität nicht
immer so konsistent sind, wurden anschließend mithilfe eines log-linearen Regressionsmodels die Informationen unterschiedlicher Verbindungen kombiniert, um zu
prüfen, ob die verbundenen Adjektive jeweils das gleiche Sentiment haben. Durch
Clustering wurden die Adjektive in Subsets mit gleicher Orientierung verteilt und
nach Frequenz ausgewählt.
Dieses Vorgehen ist eines der Schlüsselkonzepte der Korpus basierten Lexikongenerierung und wurde in mehreren Werken genutzt und erweitert. So wird dieses
Vorgehen in [63] angewandt und zusätzlich nach der Kookkurrenz von Wörtern gesucht. Für jedes Wort, das nicht als Seed verwendet wird, wird die Häufigkeit ki(p/n),
dass das Wort zusammen mit einem positiven/negativen Seed auftritt, berechnet.
Mit der Häufigkeit kann anschließend die Wahrscheinlichkeit der Kookkurrenz
ki(p|n)
𝑂𝑝
O p|n = 1− ki(p|n) und das darauf basierende Log-Verhältnis ln 𝑂𝑛 berechnet werden. Dieses Verhältnis bildet den sogenannten polarity score (Polaritätswert). Wörter, mit einem ausreichend hohen Polaritätswert werden mit in das Lexikon aufgenommen.
24
Mit diesen beiden Herangehensweisen können zwar gezielt Wörter, die zum Korpus gehören, gefunden werden, aber die Tatsache, dass Wörter je nach Kontext
unterschiedliche Bedeutungen haben, bleibt bestehen. Diese Herausforderungen
werden in [33] als basic rules of opinion definiert und in dieser Arbeit in Kapitel 2.2.4
in der Featureauswahl beschrieben. Dabei ist vor allem der Teil zu erwünschten und
unerwünschten Fakten zu beachten.
25
2.2
Maschinelles Lernen
Das Fachgebiet des maschinellen Lernens beschäftigt sich mit der Entwicklung und
Analyse von Algorithmen, die Wissen generieren können. Es sollen Muster, Regelmäßigkeiten und Gesetze in Daten erkannt werden und somit ein Schließen auf
unbekannte Daten ermöglicht werden.
Die Idee des maschinellen Lernens besteht seit es Computer gibt und ist eng an die
Entwicklung von künstlicher Intelligenz gebunden. Bereits 1950, vier Jahre nachdem der erste Universalcomputer (ENIAC) in Betrieb genommen wurde, schlug Alan
Turing seinen legendären Test vor, um zu sehen, ob Maschinen das Denkvermögen
eines Menschen erreichen können. Die Orientierung an der Lernfähigkeit des Menschen blieb jahrelang bestehen. So wurde 1957 das erste neuronale Netz (Perzeptron) von Frank Rosenblatt entwickelt. Das Modell war stark an das menschliche
Gehirn mit seinen Neuronen angelehnt. Die Entwicklung im Bereich der KI und des
maschinellen Lernens stagnierte anschließend, da Expertensysteme für viele Aufgaben geeigneter waren.
Abbildung 5: Gesichte des maschinellen Lernens8
Erst Anfang der 90er Jahre erhielt das Forschungsgebiet wieder neuen Schub.
Durch die Einführung der Statistik in das maschinelle Lernen wurde eine neue Herangehensweise geschaffen. Mithilfe von Wahrscheinlichkeitsrechnung und bestimmten Modellen können anhand von Daten Vorsagen getroffen werden. In dieser
Zeit wurden viele der heute üblichen Modelle, wie die SVM, Entscheidungsbäume
8
http://www.aboutdm.com/2013/04/history-of-machine-learning.html
26
und neuronale Netze entwickelt (siehe Abbildung 6). Der Fokus ging immer weiter
auf die Daten statt auf das Wissen. Im Bereich von Big Data ist statistische KI heute
der Kernpunkt9.
Man unterscheidet hauptsächlich drei Arten vom maschinellen Lernen. Zum einen
ist dies das Überwachte Lernen (supervised learning), das auch in der Sentiment
Analyse weit gebräuchlich ist. Zum anderen wird auch das Unüberwachte Lernen
(unsupervised learning) genutzt. Diese beiden Ansätze werden in den folgenden
Kapiteln näher beschrieben.
Die dritte Art ist das sogenannte Bestärkte Lernen (reinforcement learning). Hier
interagiert eine Software, der Agent, mit einem dynamischen Umfeld, um ein bestimmtes Ziel zu erreichen. Der Agent bekommt keine Rückmeldung wie nah er vom
Ziel entfernt ist und wird nicht in seinen Fehlern korrigiert. Er muss also zum einen
das, was er bereits weiß, ausnutzen, aber zum anderen auch neue Möglichkeiten
testen, um in Zukunft bessere Entscheidungen treffen zu können10. Als Beispiel
kann man sich einen Agenten vorstellen, der versucht Tic-Tac-Toe zu erlernen11,
indem er das Spiel gegen jemanden spielt. Diese Form des maschinellen Lernens
spielt in der Sentiment Analyse eine eher untergeordnete Rolle, weswegen sie im
Folgenden nicht genauer erklärt wird.
2.2.1
Sentiment Klassierung durch überwachtes Lernen
Das überwachte Lernen erfolgt generell durch die Einteilung der Werte in bestimmte
Klassen. Klassen sind disjunkte und aneinander grenzende Intervalle mit Merkmalswerten. Die Einteilung in die Klassen wird als Klassierung bezeichnet. Besonders bei großen Datensets kann die manuelle Klassierung eine lange Zeit beanspruchen. Deswegen werden bestimmte Modelle genutzt, um die Klassierung durch
maschinelles Lernen durchführen zu lassen. Ein solches Modell wird als Klassifikator bezeichnet. Im vorhergehenden Kapitel wurden bereits einige Klassifikatoren wie
9
http://www.mlplatform.nl/what-is-machine-learning/
http://webdocs.cs.ualberta.ca/~sutton/book/ebook/node7.html
11
http://www.lwebzem.com/cgi-bin/ttt/ttt.html
10
27
die Support Vector Machine oder der Bayes Klassifikator ernannt. Für die Zuordnung zu den Klassen benötigt ein Klassifikator bestimmte Merkmale, anhand derer
er die Einteilung vornehmen kann. Solche Merkmale werden im Folgenden auch als
Feature(s) bezeichnet. Die Feature-Auswahl ist beim überwachten Lernen durch
Klassierung ausschlaggebend. Mögliche Features werden in Kapitel 2.24 besprochen.
Sentiment Analyse kann als eine Aufgabe des überwachten Lernens mit drei unterschiedlichen Klassen – positiv, negativ und neutral – formuliert werden. In der Forschung werden häufig Online-Produktbewertungen als Datensatz verwendet, da
diese leicht zu bekommen sind und häufig die vom Meinungsvertreter angedachte
Gesamtbewertung in Form einer ordinären Bewertung mitliefern. So werden zum
Beispiel Produktbewertungen auf Amazon mit 1 bis 5 Sternen bewertet, die dann in
die Klassen neutral (3 Sterne), positiv (4 oder 5 Sterne) und negativ (1 oder 2
Sterne) unterteilt werden können. Zur Vereinfachung des Problems kann die neutrale Klasse auch nicht berücksichtigt werden.
Die Sentiment Klassifizierung ist der traditionellen Text Klassifizierung (Unterteilung
von Dokumenten in verschiedene Themenbereiche wie Sport, Reisen, Wirtschaft)
mit dem Unterschied ähnlich, dass Stimmungswörter (z.B. gut, super, schlecht, miserabel) wichtiger als themenspezifische Wörter.
Dadurch, dass Sentiment Klassifizierung eine Text Klassifizierung ist (Liu, Seite 31),
können alle Klassierungs-Methoden des überwachten Lernens angewandt werden.
Für das überwachte Lernen ist ein Trainingsdatensatz, mit dem die angewandten
Klassifikatoren trainiert werden können, wichtig. Trainingsdaten müssen oft manuell
erstellt werden.
In der Wissenschaft gibt es zahlreiche Veröffentlichungen zu verschiedenen Ansätzen in der Sentiment Klassierung durch überwachtes Lernen.
Eine gute Übersicht wird in [25] geboten. Hier wird anhand eines Korpus aus Filmkritiken Sentiment Klassierung mit verschiedenen Klassifikatoren und Features
durchgeführt. Die Ergebnisse sind in Abbildung 6 zu sehen und werden im Folgenden kurz erklärt.
28
Abbildung 6: Vergleich von verschiedenen Algorithmen in der Sentiment Klassifikation
Zeile 1 zeigt den ursprünglichen Versuch. Die Filmkritiken wurden in einem Bag-ofWords-Modell zusammengefasst. Das Bag-of-Words-Modell stellt sowohl die Präsenz als auch die Häufigkeit von Unigrammen dar. Die Wörter, die in das Modell
aufgenommen wurden, kamen aus einem vordefinierten Wort-Katalog, der zum Beispiel Wörter wie „still“ oder „really stinks“ enthielt. Die getesteten Algorithmen sind
der naïve Bayes-Klassifikator (NB), die Support Vector Machine (SVM) und die Maximum-Entropy-Methode (ME), die im Gegensatz zum naïve Bayes kein bestimmtes
Verhältnis zwischen den Features voraussetzt. Die ersten beiden Klassifikatoren
werden in Kapitel 2.2.3 genauer beschrieben. In Zeile zwei und folgend wird nicht
mehr auf die Häufigkeit der Wörter, sondern nur noch auf ihre Präsenz geachtet. Es
werden Tests mit Bigrammen, POS-Tags und nur mit Adjektiven gemacht. Dabei
hat sich herausgestellt, dass nur Bigramme gegenüber Unigrammen eine schlechtere Genauigkeit erzielen und Adjektive nicht so präzise sind, wie die am häufigsten
vorkommenden Unigramme. In der letzten Zeile wird die Position des Worts im gesamten Dokument mit einbezogen. Da Filmkritiken oft mit einer allgemeinen Stimmung beginnen, dann die Handlung erklären und am Ende die Sicht des Autors
zusammenfassen, wird die Position durch erstes Viertel, letztes Viertel und Mittelteil
angegeben. Pang et al kommen zu dem Schluss, dass die Support Vector Machine
29
die besten Ergebnisse erzielte, aber weit hinter den in der klassischen Textklassierung nach Topics erzielten Ergebnissen liegt12. Als Grund wird dafür unter anderem
die verdrehte Schreibweise in den Filmkritiken angeführt. So enthält der Satz „This
film should be brilliant. It sounds like a great plot, the actors are first grade, and the
supporting cast is good as well, and Stallone is attempting to deliver a good performance. However, it can’t hold up” in einem Bag-of-Features-Modell viele positive
Feature, obwohl das Gesamtsentiment negativ ist.
2.2.2
Sentiment Klassierung durch unüberwachtes Lernen
Im Gegensatz zum überwachten Lernen wird im unüberwachten Lernen kein Trainingsdatensatz benötigt. Die Erstellung eines Trainingsdatensatzes erfordert oft
eine manuelle Vorbereitung und ist vor allem bei großen Datasets sehr zeitaufwändig. Mit Methoden des unüberwachten Lernens kann diese Arbeit gespart werden.
Allerdings sind sie oft nicht so genau und ausgereift wie die Klassierung im überwachten Lernen.
Die Klassierung von Sentiments durch unüberwachtes Lernen wurde in mehreren
Veröffentlichungen durchgeführt. Eine der bekanntesten und viel replizierten Techniken ist in [12] zu finden. Das unüberwachte Lernen wird hier auf einen Korpus von
Kundenbewertungen aus verschiedenen Bereichen angewandt und im Folgenden
beschrieben.
Zunächst werden Sätze, die Adjektive und Adverbien enthalten, extrahiert. Dies geschieht mithilfe eines Part-of-Speech-Taggers (siehe Kapitel 2.2.4.1). Da alleinstehende Adjektive und Adverbien zwar ein guter Hinweis auf Sentiment sein können,
aber durch die Isolation der Kontext verloren gehen kann, werden immer zwei aufeinanderfolgende Wörter gezogen. Die Wörter werden entnommen, wenn sie den
in der Tabelle 6 dargestellten Mustern entsprechen. Die Bedeutung der verwendeten Tags entspricht der PEN-Treebank und wird in Kapitel 2.2.4.1 erklärt.
12
dort werden Genauigkeiten von über 90% erreicht
30
Erstes Wort
Zweites Wort
Drittes Wort (wird nicht
mit extrahiert)
1. JJ
NN oder NNS
Irgendetwas
2. RB, RBR oder RBS
JJ
Nicht NN, nicht NNS
3. JJ
JJ
Nicht NN, nicht NNS
4. NN oder NNS
JJ
Nicht NN, nicht NNS
5. RB, RBR oder RBS
VB, VBD, VBN oder VBG
irgendetwas
Tabelle 6: Muster zur Extraktion von two-word Phrases (entnommen aus Turney)
In einem zweiten Schritt wird die semantische Orientierung der extrahierten Phrasen
ermittelt. Dafür wird die Transinformation (mutual information), also die Stärke des
semantischen Zusammenhangs, zwischen den beiden extrahierten Wörtern genutzt. Der verwendete Indikator ist die Pointwise Mutual Information (PMI), der
durch die Formel
𝑝(𝑤𝑜𝑟𝑡1 & 𝑤𝑜𝑟𝑡2)
𝑃𝑀𝐼(wort1, wort2) = 𝑙𝑜𝑔2 (
)
𝑝(𝑤𝑜𝑟𝑡1)𝑝(𝑤𝑜𝑟𝑡2)
definiert ist. Die Wahrscheinlichkeit, dass Wort1 und Wort2 zusammen auftreten,
wird durch 𝑝(𝑤𝑜𝑟𝑡1 & 𝑤𝑜𝑟𝑡2) beschrieben. Wenn die Wörter statistisch unabhängig
sind, wird die Wahrscheinlichkeit der Kookkurrenz durch das Produkt
𝑝(𝑤𝑜𝑟𝑡1)𝑝(𝑤𝑜𝑟𝑡2) gegeben. Das Verhältnis zwischen diesen beiden Werten drückt
also die statistische Abhängigkeit zwischen den beiden Wörtern aus. Zusätzlich zum
PMI wird die Sentiment Orientation (SO) eines Satzes mit der Formel
SO(Satz) = PMI(Satz, „excellent“) – PMI(Satz, „poor“)
31
berechnet. Die Referenzwörter „excellent“ und „poor“ wurden gewählt, weil sie in
einem klassischen 5 Sterne-Bewertungssystem häufig die Bezeichnung für die beiden Extrema bilden. Die Sentiment Orientation ist also positiv, wenn der Satz mehr
mit „excellent“ als mit „poor“ assoziiert wird und umgekehrt.
Der Algorithmus zur letztendlichen Berechnung des Sentiments nennt sich PMI-IR
und basiert darauf, Anfragen an eine Suchmaschine im Web zu schicken. Turney
verwendete dafür die Altavista Advanced Search Engine, da sie den NEAROperator, der die Suche auf die vorangehenden/nachfolgenden 10 Wörter des
durchsuchten Dokuments einschränkt, unterstützt. Die Wahrscheinlichkeit ergibt
sich aus den Treffern (hits) der abgesendeten Anfragen und wird durch die Formel
ℎ𝑖𝑡𝑠(𝑆𝑎𝑡𝑧 𝑁𝐸𝐴𝑅 "excellent")ℎ𝑖𝑡𝑠 ("poor"))
SO(Satz) = 𝑙𝑜𝑔2 (ℎ𝑖𝑡𝑠(𝑆𝑎𝑡𝑧 𝑁𝐸𝐴𝑅 "poor")ℎ𝑖𝑡𝑠 ("𝑒𝑥𝑐𝑒𝑙𝑙𝑒𝑛𝑡"))
definiert. Zum Schluss wird die durchschnittliche Semantic Orientation der Phrasen
in den Bewertungen ermittelt. Die Bewertung gilt als „empfehlenswert“, wenn die
durchschnittliche SO positiv ist und als „nicht empfehlenswert“, wenn sie negativ ist.
Im Experiment wurde eine durchschnittliche Genauigkeit von 74% erreicht, die allerdings je nach Bereich schwankt (z.B. nur 66% bei Filmkritiken, aber 84% bei Reisen).
Turneys Algorithmus wurde unverändert in [34] auf Twitter-Daten angewandt. Dabei
waren von ca. 800 als positiv eigenordneten Tweets über 100 false positiv. Bei den
als negativ eigenordneten Werten war dieses Verhältnis besser.
Eine weitere Methode des unüberwachten Lernens wird von Zagibalov in [5]beschrieben. Die Sentiment Klassierung wird auf einem chinesischen Korpus mithilfe
von Seeds durchgeführt. Seeds sind die Ausgangspunkte, von denen weitere lexikalische Einheiten („lexical items“) gefunden werden sollen. Zagibalov nutzt also
keine Seed-Wörter, sondern lexikalische Einheiten, die vom System als Einheit gesehen werden. Das können Morpheme13, Phrasen oder Wörter sein. Zunächst muss
13
Kleinste Spracheinheit (z.B. Silben)
32
also ein passendes Seed gefunden werden. In vorherigen Arbeiten wurde beobachtet, dass positive Wörter in der chinesischen Sprache öfter verwendet werden,
selbst wenn ein negatives Sentiment ausgedrückt wird (z.B. „nicht gut“ statt
„schlecht“). Der Algorithmus beschränkt sich also auf das Finden positiver Seeds
und geht dabei wie folgt vor:
1. Finde alle Buchstabenfolgen zwischen nicht-Buchstaben (z.B. Zahlen, Punktation), die Negation und Adverbien enthalten. Trenne die Folge an der Negation und speichere die Sequenz, die dem negierten Adverb folgt, ab
2. Zähle die Häufigkeiten der in 1. gefundenen eindeutigen Sequenzen, die
dem negierten Adverb folgen (X)
3. Zähle die Häufigkeiten der in 1. gefundenen eindeutigen Sequenzen, die
nicht dem negierten Adverb folgen (Y)
4. Finde alle Sequenzen, bei denen Y-X > 0 ist
Bei der Klassierung wird das Dokument anschließend in Zonen unterteilt. Eine Zone
ist ein Bereich zwischen Punktationen. Zonen gelten als positiv, wenn es überwiegend positive Vokabeln in ihnen gibt und als negativ, wenn es überwiegend negative
sind. Da es zwei Vokabellisten (positiv und negativ) gibt, werden zwei Werte nach
der Formel
Spos/neg =
L²d
SdNd
Lphrase
berechnet, wobei Ld die Länge der passenden lexikalischen Einheit, Lphrase die Länge
der aktuellen Zone, Sd der aktuelle sentiment score der lexikalischen Einheit und Nd
eine Checkvariable, die -1 ist, wenn eine Negation vor der lexikalischen Einheit steht
und ansonsten 1 ist. Der sentiment score einer Zone ist die Summe der Scores aller
Items, die in der Zone gefunden wurden. Um das Sentiment für das ganze Dokument zu bekommen, wird die Differenz zwischen den postivien und negativen Zonen
berechnet. Wenn diese größer als 0 ist, ist das Dokument positiv. Wie eingangs
erwähnt, startet der Algorithmus mit nur einem Eintrag („good“) in der Vokabelliste.
33
Diese Liste wird erweitert, in dem die Klassierung mehrmals durchgeführt wird. Lexikalische Einheiten werden in die Vokabelliste aufgenommen, wenn sie mindestens zweimal auftreten und ihre relative Häufigkeit14 hoch genug ist. Diese unüberwachte Auswahl an Seed-Wörtern stellte sich als äußerst effizient heraus und übertraf in manchen Fällen selbst die überwachte Auswahl an Seed-Wörtern (80% Genauigkeit bei überwachter, 82% Genauigkeit bei unüberwachter Auswahl).
In [69] wurde versucht, das in Zagibilov beschriebene Vorgehen auf einen Korpus
mit Filmkritiken in Englisch zu übertragen. Die Ergebnisse waren sehr schlecht und
lagen nur bei circa 51% Genauigkeit. Die Dominanz von positiven Seeds könnte
also eine Eigenheit der chinesischen Sprache sein.
Eine andere Herangehensweise wird in [41] vorgeschlagen. Dokumente können mit
Signalen, die Emotionen anzeigen, versehen sein. Dazu gehören zum Beispiel
Smileys, aber auch Abkürzungen wie „lol“ (laughing out lout) oder Sterne bei einer
Restaurantbewertung. Hu benutzt ein Twitter-Dataset und stellt die These auf, dass
in so kurzen Beiträgen selten Emotionssignale genutzt werden, die widersprüchlich
zum Text sind. Für das unüberwachte Lernen wird ein neues Framework, das Emotional Signals for unsupervised Sentiment Analysis (ESSA), vorgestellt. Die ersten
Schritte in dem Framework umfassen das Modellieren von Emotionsindikatoren und
Korrelationen von Emotionen. Anschließend wird die Sentiment Analyse mit einem
Modell, das auf dem orthogonal nonnegative tri-factorization model (ONMTF) basiert, durchgeführt. Die non-negativ matrix factorzization beschreibt im Grunde genommen einen Vorgang, bei dem eine Input-Matrix in mehrere kleinere Matrizen
zerlegt wird, die alle keine negativen Elemente besitzen. Dadurch können die Matrizen leichter analysiert werden. Das Zerlegungs-Problem ist nicht immer lösbar,
weswegen Werte auch approximiert werden.
Die Grundidee das OMNTF besteht darin, dass Daten anhand der Verteilung von
Features und Features anhand der Verteilung von Daten geclustert werden können.
Mit dem OMTF-Model wird versucht, die Input-Wort-Matrix mit einer drei Faktoren
14
Verhältnis zwischen positiven und negativen Auftreten
34
Matrix, die gleichzeitig Cluster Label zu Wörtern und ganzen Beiträgen zuweist, anzunähern. Das vorgeschlagene Modell erreicht auf den getesteten Datasets eine
Genauigkeit von bis zu 74%. Es wurde also bewiesen, dass ESSA ein effektives
Framework für unüberwachtes Lernen ist und Emotionssignale eine wichtige Rolle
bei der Sentiment Analyse spielen können.
2.2.3
Klassifikatoren
Sentiment Analyse kann mithilfe von Klassifikation, also dem Einteilen von Dokumenten in Klassen (positiv, negativ, neutral) durchgeführt werden. Ein Algorithmus,
der diese Klassifikation implementiert, nennt sich Klassifikator. Für die Sentiment
Analyse kann nahezu jeder Klassifikator genutzt werden. So wurden unter anderem
in [14] neuronale Netze, Entscheidungsbäume in [7] und k-nearest-Neighbor in [41]
genutzt. Eines der genauesten Verfahren ist die Support Vector Machine, während
der naïve Bayes aufgrund seiner ressourcenschonenden Performanz sehr beliebt
ist. Beide Klassifikatoren werden im Folgenden erläutert.
2.2.3.1 Naïve Bayes
Die Klassifikation nach dem( naïven) Bayes wurde mit als erstes genutzt um eine
Sentiment Analyse anhand von Filmkritiken durchzuführen (Pang, Lee, Vaithyanathan 2002) und ist auch weiterhin eines der meistverwendeten Verfahren. Dieser
Klassifikator beruht auf dem Satz von Bayes, der die Berechnung von bedingten
Wahrscheinlichkeit beschreibt.
Der Zusatz naïve bezeichnet die Annahme, dass jedes Attribut nur vom Klassenattribut abhängt. Dies bedeutet, dass die Wahrscheinlichkeit, dass ein Wort eines
Dokuments in eine bestimmte Kategorie gehört, unabhängig von der Wahrscheinlichkeit, dass auch andere Wörter in dieser Kategorie sind, ist. Durch diese Annahme wird der naïve Bayes eine sehr ressourcenschonende Methode ([16], S 33).
35
Allerdings ergibt sich hierbei vor allem bei der Sentiment Analyse ein Problem: die
genutzten Feature sind nicht immer unabhängig, da sie durch Syntax und Semantik
verbunden sind. Der naïve Bayes-Klassifikator ist dadurch eine sehr vereinfachte
Methode. Dennoch sind die erzielten Ergebnisse vor allem im Verhältnis zur Effizienz und zum Zeitaufwand angemessen und machen den Bayes-Klassifikator deshalb zu einer beliebten Methode zur Text Klassierung (vgl. [82]).
Der naïve Bayes wird durch die Funktion
vnb = arg
𝑚𝑎𝑥
∏
P(vj) P(ai|vj)
𝑣 ∈𝑉
𝑖
beschrieben. Dabei wird das Klassenlabel vnb = vj einem bestimmten j zugeordnet.
Der Berechnung liegen die Wahrscheinlichkeiten der einzelnen Feature zu Grunde.
Die Einfachheit dieses Algorithmus kann in einem (vereinfachten) Beispiel deutlich
gemacht werden. Ziel sei die Sentiment Klassifikation anhand von Stimmungswörtern mit den Klassen positiv und negativ. Der Bayes-Klassifikator wurde mit den in
Tabelle 7 abgebildeten Daten trainiert.
Feature 1
Feature 2
Feature 3
Feature 4
Sentiment
1
Schnell
Hübsch
Teuer
In
Positiv
2
Langsam
Hässlich
Teuer
In
Negativ
3
Schnell
Bäh
Teuer
Out
Negativ
4
Langsam
Hässlich
Lächerlich
Out
Negativ
5
Schnell
Hübsch
Preiswert
Angesagt
Positiv
Tabelle 7: Beispiel zur Bayes-Klassifizierung
Ein neuer Datensatz (Schnell, Hässlich, Preiswert, In) soll klassifiziert werden.
vnb = arg
𝑚𝑎𝑥
∏
P(vj) P(ai|vj)
𝑣 ∈𝑉
𝑖
36
vnb =
𝑚𝑎𝑥
𝑣 ∈ {𝑝𝑜𝑠𝑖𝑡𝑖𝑣, 𝑛𝑒𝑔𝑎𝑡𝑖𝑣}P(vj)
arg
𝑃(𝐹𝑒𝑎𝑡𝑢𝑟𝑒 1 = 𝑆𝑐ℎ𝑛𝑒𝑙𝑙) 𝑃(𝐹𝑒𝑎𝑡𝑢𝑟𝑒 2 =
𝐻ä𝑠𝑠𝑙𝑖𝑐ℎ) 𝑃(𝐹𝑒𝑎𝑡𝑢𝑟𝑒 3 = 𝑃𝑟𝑒𝑠𝑖𝑤𝑒𝑟𝑡) 𝑃(𝐹𝑒𝑎𝑡𝑢𝑟𝑒 4 = 𝐼𝑛)
Zunächst muss die Wahrscheinlichkeit P(positiv) und P(negativ) ermittelt werden.
2
P(positiv) = 5
3
P(negativ) = 5
Anschließend können die bedingten Wahrscheinlichkeiten abgeschätzt werden. Für
Feature 1 würde dies so aussehen.
P(Feature 1 = Schnell | Sentiment = positiv) =
2
2
1
P(Feature 1 = Schnell | Sentiment = negativ) = 3
Die Berechnung muss für alle Feature durchgeführt werden.
P(positiv)P(Schnell | pos) P(Hässlich | pos) P(Preiswert | pos) P(In | pos) = 0,25
P(negativ)P(Schnell | neg) P(Hässlich | neg) P(Preiswert | neg) P(In | neg) = 0,04
Normalisiert:
0,25
= 86%
0,25 + 0,04
0,04
= 14%
0,04 + 0,25
37
Das neue Element (Schnell, Hässlich, Preiswert, In) wird der Klasse „positiv“ zugeordnet. Bei geringen Datenmengen kann zusätzlich ein m-Schätzer genutzt werden,
um weitere Datensätze zu simulieren.
2.2.3.2 Support Vector Machine
Support Vector Machines (SVM) sind Modelle, die im überwachten Lernen zur
Klassifizierung und Regressionsanalyse genutzt werden können. Die mit ihr verbundenen Algorithmen sind dazu in der Lage, Muster zu erkennen und Daten zu analysieren.
SVMs basieren auf dem Prinzip der Structural Risk Minimization (SRM). Eine Herausforderung des Maschinenlernens ist immer, ein Model aus einem endlichen Trainingsdatensatz zu generieren, ohne dass es durch Überanpassung zu speziell wird,
um mit neuen Daten, die nicht aus dem Trainingsdatensatz stammen, umzugehen.
Das SRM-Prinzip adressiert dieses Problem indem die optimale Balance zwischen
Komplexität des Modells und der Fähigkeit, neue Daten aufzunehmen, gefunden
werden soll. Es soll also die Hypothese h gefunden werden, mit der die kleinstmögliche Wahrscheinlichkeit garantiert werden kann, in einem unbekannten und zufälligen Datensatz einen Fehler zu machen (vgl. [38]).
Der Ausgangpunkt für eine Support Vector Machine ist ein Trainingsdatensatz für
dessen Objekte die Klasseneinteilung bekannt ist.
(x1,y2), (x2, y2), …, (xn, yn) mit 𝑥i ∈ ℝg und 𝑦i ∈ {± 1}
{für 𝑖 = 1, 2, … , 𝑁}
Die Objekte werden durch Vektoren in einem Vektorraum repräsentiert, wobei xi den
Eingangsdaten und yi den beiden Klassen entsprechen, in die eingeordnet werden
soll.
Die Aufgabe der Support Vector Machine ist nun, diese Menge von Objekten durch
das Einfügen einer Hyperebene in zwei Klassen zu unterteilen. Im einfachsten Fall
38
erfolgt eine lineare Trennung. Schon hier gibt es mehrere Möglichkeiten, die Hyperebene zu platzieren.
Abbildung 7: Hyperebene im Vektorraum mit schmalen und breiten Rand
Abbildung 8 zeigt zwei Möglichkeiten, die Hyperebene in einen linear trennbaren
Datensatz zu legen. Im linken Bereich des Bildes wurde die Hyperebene so platziert,
dass nur ein schmaler Rand bis zur Klassengrenze entsteht. Es wird jedoch angestrebt, den Abstand zur Hyperebene zu maximieren, um möglichst viele neue Datensätze in der Klasse aufnehmen zu können. Im rechten Teil der Abbildung ist dies
besser gelungen.
In der Praxis ist die Arbeit mit linear trennbaren Datensätzen der Ausnahmefall. Viel
öfter kommt es vor, dass sich Klassengrenzen überschneiden. Die Hyperebene
kann nicht wie auf der linken Seite der Abbildung 8 verbogen gelegt werden. Stattdessen wird der Vektorraum mit den Trainingsdaten in eine so hohe Dimension
überführt, dass sich die Daten linear trennen lassen. Bei der Rücktransformationen
in den ursprünglichen Dimensionsraum wird die lineare Hyperebene wieder zu einer
nichtlinearen. Um den enorm hohen Rechenaufwand im höher dimensionalen
Raum zu vermeiden, werden Kern-Funktionen, die die ursprüngliche ersetzen, verwendet. Die Kern-Funktionen machen die SVM zu einem universalen Lerner (vlg
Joachims). Sie können dazu genutzt werden, die SVM zusätzlich zu linearen Funktionen, auch polynomische Klassifizierungsverfahren, radiale Basisfunktionen
(RBF) und neuronale Netze lernen zu lassen.
39
Abbildung 8: Hyperebene in einem nicht linear trennbaren Datensatz15
Joachims legt in [38] sowohl in der Theorie als auch in einem Experiment nieder,
warum Support Vector Machines ein für die Text Klassifizierung geeigneter Klassifikator sind. Zum einen ist die Text Klassifizierung, und damit auch die Sentiment
Analyse, typischerweise ein Klassifizierungsproblem mit einer hohen Anzahl von
relevanten Features. Die Gefahr der Überanpassung hängt bei SVMs nicht zwangsläufig von der Feature-Anzahl ab, wodurch sie in dieser Situation geeignet sind.
Hinzu kommt, dass es für jedes Dokument nur einige Einträge im Dokument-Vektor
gibt, die nicht 0 sind. So kann es gut sein, dass in einem Korpus von Kundenbewertungen, bei dem Stimmungswörter als Feature genutzt werden, das Wort „amazing“
nur in 5 von 1000 Bewertungen vorkommt. Bei 995 Bewertungen wäre dieser Vektoreintrag also 0. Der induktive Algorithmus der SVM kann mit diesen dünnbesetzten Vektoren gut umgehen.
2.2.3.3 Gradientenverfahren
Eine verbreitete Herangehensweise im maschinellen Lernen ist es, den Algorithmus
während seiner Trainingsphase zu verbessern, indem die Gewichtung falsch platzierter Klassenlabel geändert wird. Dieses Vorgehen wird als Gradientenverfahren
15
http://www.statsoft.com/textbook/graphics/SVMIntro3.gif
40
bezeichnet. Bei großen Datenmengen kann die Neuberechnung aller Gewichtungen
zur sehr hohen Kosten führen. Während [70] die Limitierung hier bei der Last für die
CPU sieht, stellt [71] eher Latenzen, Netzwerk-Beschränkungen und Bandbreiten
bei verteilen Systeme als Probleme dar. Der Grundgedanke, dass das Gradientenverfahren zu hohen Kosten führen kann, bleibt allerdings bei beiden bestehen.
Aus diesem Grund wird häufig ein vereinfachtes Verfahren, der Stochastic Gradient
Descent (SGD), genutzt. Im Gegensatz zum ursprünglichen Gradientenverfahren
werden beim SGD bei jeder Iteration des Algorithmus nur einige zufällig ausgewählte Gewichtungen angepasst. Durch diese Änderung senkt der SGD weiterhin
das erwartete Risiko der Fehlklassifikation, aber ist dabei effizienter und einfacher
zu implementieren als das normale Gradientenverfahren.
Dies macht das SGD zu einem weit genutzten Verfahren. So wird es zum Beispiel
in Praxisteil dieser Arbeit sowohl im SciKit-Learn als auch in Apache Spark beim
Einsatz der Support Vector Machine verwendet.
2.2.4
Features
Die Klassierung muss anhand bestimmter Merkmale, der Features, geschehen. In
der Sentiment Analyse gibt es eine Vielzahl möglicher Feature. Die wichtigsten werden in diesem Abschnitt erläutert.
2.2.4.1 Wortart
Die Wortart eines Wortes (engl. part-of-speech oder kurz POS) kann ausschlaggebend sein. Besonders für die Sentiment Analyse ist eine korrekte Zuordnung der
Wörter zu ihren Wortarten, also das sogenannte Part-of-Speech-Tagging, wichtig.
Adjektive drücken häufiger eine Stimmung aus, als es Substantive oder Verben tun
und werden deswegen zum Teil auch als special feature angesehen.
41
POS-Tagging geht weit über ein lexikalisches Zuordnen von Wörtern zu ihren Wortarten hinaus. In der deutschen Sprache unterscheidet man 10 Wortarten (und in
Englisch 9, da Artikel nicht als eigene Wortart gezählt werden).
1. Substantiv (Nomen, Hauptwort)
2. Verb (Zeit- oder Tätigkeitswort)
3. Adjektiv (Eigenschaftswort)
4. Adverb (Umstandswort)
5. Pronomen (Fürwort)
6. Präposition (Verhältniswort)
7. Konjunktion (Bindewort)
8. Numerale (Zahlwort)
9. Artikel (Geschlechtswort)
10. Interjektion (Ausrufe- oder Empfindungswort)
In der Praxis werden weit mehr als 10, respektive 9, POS-Tags genutzt. Das im
Deutschen weitverbreitete Stuttgart-Tübingen-Tagset (STTS)16 nutzt zum Beispiel
53 verschiedene Tags.
Im praktischen Teil dieser Arbeit wird vor allem mit dem Stanford Parser gearbeitet,
der das im Englischen etablierte „Penn Treebank POS Tags“ Tagset, mit 36 unterschiedlichen vordefinierten Tags, verwendet.
Tag
Bezeichnung
CC
Coordinating conjunc- Nebenordnende
Konjunktionen; and, but, nor, or, yet
tion
ausgeschriebene mathematische plus, minus, times
𝑥
(*), over (𝑦)
Operatoren
CD
Cardinal number
Kardinalzahlen
1988
DT
Determiner
Artikel; Determinative
a(n), every, no, the
another, any
EX
Existential there
Das „there“, das die Existenz/Prä- There (is a dog.)
senz von etwas anzeigt
FW
Foreign Word
Fremdwörter
16
Beschreibung
Beispiel
Hund
http://www.ims.uni-stuttgart.de/forschung/ressourcen/lexika/TagSets/stts-table.html
42
IN
Preposition or subordi- Präpositionen,
nating conjunction
Konjunktionen
unterordnende on, in, since, for
JJ
Adjective
JJR
Adjective, comparative vergleichende Adjektive mit der better
Endung -er
JJS
Adjective, superlative
Adjektive im Superlativ mit der En- best
dung -est, sowie most/least
LS
List item marker
Buchstaben / Zahlen, wenn sie ei- a), b), 1., 2.
ner Aufzählung dienen
MD
Modal verb
Alle Verben, die in der 3. Person can, could, may,
Singular kein –s als Endung haben might, must, ought,
shall
NN
Noun, singular or mass Substantiv im Singular
NNS
Noun, plural
NNP
Proper noun, singular Eigennamen im Singular
or mass
Adjektive; durch Bindestrichen ver- good
bundene
Zusammensetzungen, one-of-a-kind
die als Adjektiv dienen
second-smallest
car
Substantiv im Plural; oft mit En- cars
dung –s
California
NNPS Proper noun, plural
Eigennamen im Plural
PDT
Prederterminer
Determinative, die einem Artikel o- all (her toys)
der Possessivpronomen vorange- such an awful movie
stellt sind
POS
Possessive ending
Besitzanzeigende Wortendungen
PRP
Personal pronoun
Personalpronomen; Reflexsivpro- I, me, myself, mine
nomen; Demonstrativpronomen
PRP$
Possessive pronoun
Possessivpronomen
RB
Adverb
Adverb; fast alle Wörter mit der En- quietly
dung -ly; nachgestellte Attribute; (good) enough
negative Kennzeichner
RBR
Adverb, comparative
Beckers
(the dog)`s (toy)
my, your, his, her
not / n‘t
vergleichende Adjektive mit der earlier
Endung -er
43
RBS
Adverb, superlative
Adverben im Superlativ
earliest
RP
Particle
Partikel (hier gibt es Überschnei- off, well, um
dungen mit Adverben und Präpositionen)
SYM
Symbol
Mathematische/wissenschaftliche
Symbole und Ausdrücke
Ω, ∑
TO
To
Nur das Wort “to”
to
UH
Interjection
Interjektion
oh, please, uh, well
VB
Verb, base form
Verben im Imperativ, Infinitiv oder Do (it.)
Subjunctive (etwa der deutsche (You should) do (it.)
Konjunktiv)
(I suggest that you)
do (it.)
VBD
Verb, past tense
Verben im Präteritum; konjungierte (If I) were (tall.)
Form von “to be”
worked
VBG
Verb, gerund or pre- Partizip oder Gerundium
sent participle
writing
singing
VBN
Verb, past participle
written, sung
VBD
non-3rd
Verb,
person Präsenz von Verben (ohne 3. Per- write
singular present
son); ist VB vorzuziehen
VBZ
Verb, 3rd person singu- Präsenz von Verben (nur 3. Per- writes
lar present
son); ist VB vorzuziehen
WDT
Wh-determiner
Which/that als Relativpronomen
which, that
WP
WH-pronoun
Pronomen mit wh
what, who, whom
WP$
Possessive
noun
WRB
Wh-adverb
Partizip
wh-pro- Das Wort “whose”
whose
Adverben, die mit wh beginnen what,
und how
when
who,
Tabelle 8: Tags der POS-Treebank
44
how,
Trotz der umfangreichen Auswahl an Tags gibt es viele problematische Fälle (vgl.
[20]), die hier zwar nicht in ihrer Gesamtheit aufgezählt werden sollen, aber zumindest beispielhaft erwähnt werden, um die Komplexität des Taggens darzustellen.
Ein kritischer Fall ist die Unterscheidung zwischen Substantiven im Singular (NN)
und Substantiven im Plural (NNS). Hierbei geht es nicht darum, ob das Substantiv
in seiner Semantik in der Pluralform steht, sondern ob es die Pluralform des dazugehörigen Verbs auslöst. Im Satz
„Mathematics/NN is an interesting science”
wird “Mathematics” als Substantiv im Singular (NN) getaggt, obwohl es die für den
Plural typische Endung –s hat. Das gleiche gilt auch für den umgekehrten Fall, dass
ein im Singular stehendes Substantiv die Pluralform eines Verbs auslöst.
„The deer/NNS are hungry“
In diesem Satz wird “deer” aus dem Kontext heraus als NNS getaggt, obwohl das
alleinstehende Wort auch im Singular sein könnte.
Eine Ausnahme zu dieser Regel bilden Wörter, die eine Menge bezeichnen.
„Nine months/NNS is a short time.”
Die Unterscheidung zwischen Substantiv (NN) und Gerundium (VBG) stellt ebenfalls ein komplexes Problem dar. Verbformen, die auf –ing enden, können in vielen
Fällen auch Substantive sein. Hinzu kommt, dass sowohl VBG als auch NN ein Artikel oder Possessivpronomen vorangestellt sein kann. Um diese Wortarten auseinander zu halten, kann geprüft werden, ob das Wort eine Pluralbildung erlaubt.
„Running/VBG isn’t complicated. “
„The writing/NN on the wall is beautiful. “
Im ersten Fall wäre die Pluralform (“Runnings aren’t complicated.”) grammatikalisch
falsch, wohingegen „The writings on the wall are beautiful“ ein korrekt gebildeter
Satz ist. Adjektive und Adverbien können zusätzlichen Aufschluss über die Wortart
geben. Ein Substantiv kann nur durch ein Adjektiv (JJ) modifiziert werden, während
ein Gerundium nur durch ein Adverb (RB) modifizierbar ist.
„This is an expensive/JJ painting/NN. “
“Painting/VBG well/RB is a skill hard learned.”
45
Weiterhin weist die Nutzung des Worts in einem of-Satz darauf hin, dass es sich um
ein Substantiv handelt. Steht das Wort jedoch in einer Nominalgruppe, ist es ein
Gerundium. (Beispiel aus [20])
„GM`s closing /NN of the plant“
„GM`s closing/VBG the plant“
Sollte dem Wort mit der –ing Endung ein Substantiv vorangestellt sein, ist dieses
Wort auch ein Substantiv. (Beispiel aus [20])
„the plant/NN closing/NN“
„unsavory plant/NN closing/NN tactics/NNS“
In der letzten Regel für die Unterscheidung von Substantiven und Gerundien ist
festgelegt, dass ein -ing-Wort, das vor einem Substantiv steht, ein Gerundium ist,
wenn die Bedeutung des Satzes nach einer derartigen Umstellung, dass das Substantiv den Satzanfang bildet, gleich oder äquivalent bleibt.
„the rising/VBG market prices“
zu „the market prices are rising/VBG“
Wenn sich die Bedeutung des Satzes hingegen verändert, ist das –ing-Wort ein
Substantiv.
„hunting /NN permit“
Die Umstellung würde in diesem Fall „a permit that is hunting“ ergeben, gemeint ist
hingegen „a permit for hunting“.
46
2.2.4.2 N-Gramme
N-Gramme repräsentieren das zu untersuchende Dokument in Vektoren, die die
Existenz und Häufigkeit der einzelnen Wörter darstellen. Dazu gehören sowohl Unigramme, also N-Gramme, die nur aus einem Wort bestehen, als auch zusammenhängende Ausdrücke (z.B. das Tetragramm „United States of America“). Nach Liu
Bing ([33] S 33) sind N-Gramme die am häufigsten genutzten Features in der klassischen „topic based“ Text Klassifizierung, also der Einteilung von Texten in einzelne Themenbereiche und werden auch für die Sentiment Analyse genutzt. In [16]
wird erwähnt, dass N-Gramme mit mehr als 3 Wörtern nur bei sehr großen Datenmengen nützlich sind, da ein gemeinsames Auftreten der N-Gramme im gleichen
Dokument unwahrscheinlich ist. Google hat in diesem Zusammenhang ein NGramm-Model, das auch Pentagramme (5-Gramm) einschließt, mit über zehn Billion Wörtern aus dem World Wide Web trainiert17.
In [25] hat sich gezeigt, dass eine Vorhersage, die sich nur auf die Existenz von
Wörtern als Feature bezieht, eine höhere Genauigkeit erreichen kann als eine, die
die Häufigkeit der Wörter mit einbezieht. Für das reine Vorkommen von Wörtern ist
das Bag-of-Word-Model geeignet. Dieses recht einfache Model stellt die Wörter in
einem Dokument binär (vorhanden/nicht vorhanden) in einem Vektor dar. Dabei
können Füllwörter herrausgefiltert werden.
Abbildung 9: Bag-of-Words-Modell
17
http://googleresearch.blogspot.de/2006/08/all-our-n-gram-are-belong-to-you.html
47
2.2.4.3 Lemmatisierung
Lemmatisierung ist die Zurückführung von ihren Wörtern auf ihre Grundform, dem
Lemma. Die Effektivität der Lemmatisierung hängt unter anderem von der untersuchten Sprache ab. In [6] wurde festgestellt, dass sich das Zurückführen von Wörtern auf ihre Grundform (running -> run) im Englischen negativ auf die Vorhersagegenauigkeit auswirkt, wohingegen die Lemmatisierung im Russischen positive Auswirkungen hatte.
2.2.4.4 Stimmungsverändernde Wörter
In vielen Fällen können Wörter nicht isoliert betrachtet werden, sondern müssen im
Zusammenhang mit anderen Wörtern analysiert werden. Die Stimmung, die in einer
Meinung weitergegeben wird, kann durch die sogenannten „sentiment shifter“ geändert werden. Zu den Sentiment Shiftern gehört unter anderem die Negation, die
dem dazugehörigen Wort die gegenteilige Wirkung verleiht, aber auch Sarkasmus
kann dazu genutzt werden, Stimmung zu ändern. Tabelle 9 zeigt die nach Liu klassifizierten Sentiment Shiftern mit Beispielwörtern in Englisch.
Sentiment Shifter
Beispiel
Negation
Not, never, none, nobody, nowhere, neither, cannot
„I don`t like it.“ (das positive „like“ wird negativ)
Modal auxiliary (mo- Would, should, could, might, must, ought
dale Hilfsverben)
„The picture quality could be better.“
(das positive better erhält einen negativen Kontext)
Presuppositional Items Adverben: Barely, hardly
(Präsuppositionen)
Andere Wörter: fail, neglect
48
„It barely works.“ (works verliert seine positive Bedeutung)
Sarcasm (Sarkasmus)
„What an amazing quality, it broke on the first day“
Decrease/Increase
(Reduzierung/Zunahme)
„This drug reduced my pain significantly“
(Da Pain ein negatives Wort ist, entsteht durch die Reduzierung von pain ein positives Sentiment)
Tabelle 9: Stimmungsveränderte Wörter
2.2.4.5 Stimmungswörter und –Sätze
In jeder Sprache gibt es bestimmte Wörter und Sätze, die besonders häufig dafür
genutzt werden, eine Stimmung zu beschreiben. So werden positive Stimmungen
im Deutschen oft mit „großartig“, „super“ oder „wunderbar“ beschrieben, während
negative Stimmungen durch Wörter wie „schlecht“, „miserabel“ oder „widerlich“ ausgedrückt werden. Adjektive werden besonders häufig als Stimmungswörter genutzt,
aber auch Substantive (Vergnügen) und Verben (hassen) kommen in Frage.
Zusätzlich zu einzelnen Wörtern werden auch Redensarten genutzt, um Meinungen
auszudrücken („Bei dem Film ist doch Hopfen und Malz verloren“).
2.2.4.6 Kompositionelle Regeln
Die Rules of opionions, also die Regeln der Meinungsbildung, werden von Liu in
[31] als weiterführende Ausdrücke, die dazu genutzt werden können, explizite oder
implizite Meinungen zu bilden, beschrieben. Sie bestehen aus einer Kombination
49
anderer Feature und dienen dazu, auf besondere Situationen einzugehen und genaue Entscheidungen zu treffen. Der Ausgangpunkt für die Regeln ist die formale
Darstellung:
1. Positiv :: = P
2.
|PO
3.
|stimmungveränderndes_Wort N
4.
|stimmungsveränderndes_Wort NE
5. Negativ ::= N
6.
| NE
7.
|stimmungveränderndes_Wort P
8.
|stimmungveränderndes_Wort PO
Dabei stehen P und N für atomare (Wort oder Phrase) [p]ositive und [n]egative Stimmungswörter und PO, NE für Ausdrücke, die sich aus mehreren atomaren Stimmungswörtern zusammensetzen. Das gleiche gilt auch für die stimmungsverändernden Wörter. Die einfachste Regel ist in 3, 4, 7 und 8 zu sehen. Wenn stimmungsverändernde Wörter und Phrasen im Zusammenhang mit dem Wort stehen,
wird die gegenteilige Stimmung erzeugt. Ein weiteres Set von Regeln basiert auf
der Änderung der Menge des Elements, zu dem die Meinung ausgedrückt wird.
9. PO ::= weniger_oder_gesenkt N
10.
|mehr_oder_erhöht P
11. NE ::= weniger_oder_gesenkt P
12.
|mehr_oder_erhöht
Diese Regeln beschäftigen sich damit, dass eine Änderung der Menge von einem
Sentiment die Stimmung, die ausgedrückt wird, ändern kann. Liu bringt hier das
Beispiel von Medikamenten. Man nehme den Satz
„This drug reduced my pain significantly“
Normalerweise drückt Pain (Schmerz) eine negative Stimmung aus. Der Satz drückt
insgesamt jedoch eine positive Stimmung aus, weil das Negative verringert wird
(weniger Schmerz).
Ganz ähnlich verhält es sich mit Mengenangaben generell.
50
13.
14.
15.
16.
17.
18.
PO
::= kein_wenig_weniger_oder_verringerte_Anzahl_von NPI
| viel_mehr_erhöhte_Anzahl_von PPI
NE ::= kein_wenig_weniger_oder_verringerte_Anzahl_von PPI
| viel_mehr_erhöhte_Anzahl_von PPI
NPI ::= potentiell_negatives_Element
PPI ::= potentiell_positives_Element
Für einige Aspekte ist eine geringe Menge schlecht, während eine hohe Menge gut
ist und umgekehrt. So würde „this notebook costs a lot“ eine negative Stimmung
ausdrücken (NPI) und durch „the price of this notebook is reduced“ eine positve
Stimmung erhalten (PO).
Eine weitere Regel beschäftigt sich mit erwünschten und unerwünschten Fakten.
Neben subjektiven Ausdrücken kann Stimmung auch in objektiven Phrasen ausgedrückt. Der Satz „Schon nach einem Monat hatte ich eine Pfütze unter meinem
Wasserbett“ ist objektiv, drückt aber dennoch eine unerwünschte Situation und somit eine negative Stimmung aus. Dabei ist das Wort „Pfütze“ ansonsten kein Stimmungswort.
19. P ::= erwünschter_Fakt
20. N ::= unerwünschter_Fakt
Liu nennt noch zwei weitere Regeln. Zum einen ist dies die Abweichung von einer
Norm oder einem erwünschten Wertebereich und zum anderen die Produktion und
der Verbrauch von Ressourcen und Müll. Ersteres lässt sich in den Regeln 21 und
22 zusammenfassen. Bei bestimmten Aspekte ist es erwünscht, in einem bestimmten Wertebereich zu bleiben. Wenn von diesem Wertbereich abgewichen wird, entsteht eine negative Stimmung. Als Beispiel hierfür kann der Satz „Der Kühlschrank
kommt nie unter 15°C“ dienen.
21. P ::= innerhalb_gewünschter_Wertebereich
22. N ::= außerhalb_gewünschter_Wertebereich
Die letzten Regeln lauten:
23. P ::= produziert_viel_oder_mehr_Ressourcen
51
24.
| produziert_kein_wenig_weniger_Müll
25.
| verbraucht_keine_wenig_weniger_Ressourcen
26.
| verbraucht_viel_oder_mehr_Müll
27. N ::= produziert_kein_wenig_weniger_Ressourcen
28.
| produziert_viel_oder_mehr_Müll
29.
| verbraucht_viel_oder_mehr_Ressourcen
30.
| verbraucht_keine_wenig_weniger_Müll
Sie beziehen sich auf den Verbrauch und den Konsum von Ressourcen und Müll.
Ein typisches Beispiel hierfür ist der erwünscht niedrige Stromverbrauch technischer
Geräte.
Auch in anderen Werken wurden Kompositionsregeln aufgestellt. In [65] wurden
sechs Regeln aufgestellt: polarity reversal, aggregation (fusion), propagation, domination, neutralization und intensification. Polarity Reversal ist die Umkehrung der
Stimmung durch stimmungsändernde Wörter und die soeben beschriebenen Regeln zur Quantität eines Aspekts. Die Aggregation beschreibt das Zusammenschließen von gegenteiligen Wörtern zu der Stimmung des dominanteren Worts,
zum Beispiel POS(„beautiful“) und NEG („fight“) wird zu POS(„beautiful fight“). Propagation bezieht sich auf sogenannte „transfer“- und „propagation“-Wörter, die die
Stimmung auf ein anderes Wort übertragen. So ist „his behaviour“ allgemein kein
stimmungshaltiges Wort, wenn es jedoch im Zusammenhang mit POS(„to admire“)
steht, wird das positive Sentiment auch auf POS(„his behaviour“) mit übertragen.
Die Regeln der domination sind wie folgt. Wenn die Polaritäten von einem Verb und
einem Objekt entgegengesetzt sind, dann wiegt die Polarität des Verbs schwerer
(NEG(„to deceive“) und POS(„hopes“) => NEG(„to deceive hopes“). Wenn ein zusammengesetzter Satz durch „but“ eingeleitet wird, wiegt der Satzteil mit dem „but“
schwerer (NEG(„It was hard to climb a mountain all night long“), but POS(„a magnificent view rewarded the traveler at the morning“) => POS(ganzer Satz)).
Die Regel der neutralization sagt aus, dass Stimmungswörter neutralisiert werden
können, wenn bestimmte Modifizierer angebracht werden („despite“ und
NEG(„worries“) wird zu NEUT(„despite worries“).
Die letzte Regel ist die der intensification und besagt, dass bestimmte Modifizierer
die Stärke eines Sentiment erhöhen können (POS_Wert(„happy“) <
52
POS_Wert(„very happy“). In einem Experiment hat diese Auswahl an Features eine
signifikant höhere Genauigkeit gebracht als vorherige Methoden (bis zu 87%).
2.2.4.7 Satz- und Sonderzeichen
In bestimmten Fällen können neben den eigentlichen Wörtern auch Satzzeichen
einen Aufschluss über die ausgedrückte Stimmung geben. Die übermäßige Nutzung von Ausrufe- und Fragezeichen drückt oft eine aggressive Haltung des Meinungsvertreters aus und kann ein Hinweis auf Negativität sein. Diese aggressive
Haltung kann ebenso durch exzessive Großschreibung erreicht werden, wodurch
selbst die Kapitalisierung von Wörtern ein Untersuchungsobjekt darstellen kann.
Sonderzeichen werden unter anderem dafür verwendet, Emoticons zu erstellen.
Diese Stimmungs-Symbole ( „: - )“, „: - (“) drücken Zufriedenheit oder Abneigung
aus und sind somit wichtige Feature (vgl. [16]).
2.2.4.8 Syntakische Abhängigkeiten
Die bereits vorgestellten N-Gramme und das Bag-of-Words-Model sind nicht dazu
in der Lage, syntaktischen Abhängigkeiten von nicht zusammenhängenden Wörtern
abzubilden. Das heißt, dass in einem N-Gramm zwar die Folge „guter Film“ vorkommen kann, aber die Folge „ein guter und sehr spannender Film“ ein anderes NGramm bilden würde. In [74] wurde mithilfe eines Entscheidungsbaumes nach häufig vorkommenden Mustern in Filmkritiken gesucht. Diese wurden als Feature verwendet und haben zu einer sehr hohen Genauigkeit (87% statt circa 83% mit dem
Bag-of-Words-Modell) geführt.
53
2.2.4.9 TF-IDF-Maß
Das TF-IDF-Maß ist ein Wert, der zur Beurteilung der Wichtigkeit eines Wortes in
einem Korpus ausgewandt werden kann. Das TF steht für Term Frequency, also die
Häufigkeit des Vorkommens eines Worts in dem Korpus. Wenn dieser Häufigkeit
allerdings zu viel Gewicht zugeordnet wird, werden Wörter, die zwar häufig vorkommen, aber generell wenig sinnvolle Informationen weitergeben, in ihrer Wichtigkeit
zu hoch eingeschätzt. Im Deutschen sind dies unter anderem Bindewörter wie „und“
und „Artikel“. Aus diesem Grund wird mit der inversen Dokumentenhäufigkeit (IDF)
ein Wert zur Bestimmung des Informationsgehalts eines Wortes berechnet. Der
IDF-Wert wird durch die Formel
𝐼𝐷𝐹(𝑡, 𝐷) = log
|𝐷| + 1
𝐷𝐹(𝑡, 𝐷) + 1
bestimmt, wobei t das zu untersuchende Wort, D das zu untersuchende Dokument,
DF(t, D) die Anzahl der Dokumente, in denen das Wort t vorkommt und |D| die Gesamtanzahl aller Dokumente im Korpus ist. Die Nutzung des Logarithmus sorgt dafür, dass der IDF Wert 0 wird, wenn das Wort t in allen Dokumenten vorkommt. Der
TD-IDF-Wert kann anschließend durch
𝑇𝐹𝐼𝐷𝐹(𝑡, 𝑑, 𝐷) = 𝑇𝐹(𝑡, 𝑑) ∗ 𝐼𝐷𝐹(𝑡, 𝐷)
berechnet werden, wobei TF(t, d) die Anzahl des Wortes t in einem Dokument d ist.
54
Technische Grundlagen
3
In diesem Kapitel werden die technischen Grundlagen dieser Arbeit beschrieben.
Dabei wird zunächst darauf eingegangen, wie Daten aus technischer Sicht definiert
sind und wie diese gespeichert werden können. Es wird der Unterschied zwischen
flüchtigem und nicht flüchtigem Speicher erklärt und daraus abgeleitet, warum die
in dieser Arbeit genutzte in-memory-Technologie sinnvoll ist. Darüber hinaus wird
auf das verwendete System eingegangen, das sich auf dem Hadoop-Filesystem
HDFS und dem Framework Apache Spark zusammensetzt.
3.1
Daten und Datenspeicher
Der Oxford Dictionary definiert Daten als „the quantities, characters, or symbols on which
operations are performed by a computer, stored and recorded on magnetic, optical, or mechanical
recording media, and transmitted in the form of electrical signals“18. Im übertragenden Sinne
sind Daten also schlichtweg maschinenlesbare und -bearbeitbare Zeichenketten,
die einer bestimmten Syntax entsprechen. Sie werden dafür genutzt, Informationen
zu erlangen und Wissen zu generieren. So könnte die beispielsweise die Zeichenfolge „Phoenix“ eine Stadt, ein Name oder eine mystische Kreatur. Erst durch einen
Kontext wird aus den Daten eine bedeutungsvolle Information. Die Informationen
werden zum Wissen, wenn sie organisiert, weiterverarbeitet oder anderweitig genutzt werden.
18
http://www.oxforddictionaries.com/definition/american_english/data
55
Abbildung 10: Wissenspyramide
Jedes Jahr werden mehr digitale Daten auf der Welt produziert, verarbeitet und weitergeleitet. Während der weltweite Datenverkehr 2008 noch ein Volumen von 487
Milliarden Gigabyte hatte, sollen es im Jahre 2016 bis zu 1,3 Zettabyte, die fast
dreifache Menge von 2008, sein19.
Für diese Arbeit sind vor allem Konzepte zur Speicherung von Daten wichtig. Moderne digitale Computer arbeiten mit dem Binärsystem. Jegliche Daten werden in
eine Folge von Bits konvertiert. Ein Bit kann die Werte 0 und 1 annehmen. Es ist
jedoch unüblich, nur einzelne Bits zu speichern, da für die Repräsentierung eines
Schriftzeichens mehrere Bits notwendig sind. Die am meisten genutzte Speichereinheit ist deswegen das Byte, das eine Folge von 8 Bit darstellt und in der Anfangszeit der PCs zur Kodierung eines einzelnen Schriftzeichens ausreichte.
Die wichtigsten Technologien zur Datenspeicherung sind heutzutage Halbleiterspeicher und magnetische Speicher.
Die Hauptanwendung von magnetischen Speichern sind Festplatten zur Massenspeicherung von Daten. Eine Festplatte ist eine sich drehende Scheibe aus magnetisierbarem Material, über der ein Schreibarm (Actuator) mit einem elektromagnetischen Kopf sitzt20. Beim Schreiben von Daten magnetisiert der Kopf Bereiche der
19
http://www.spiegel.de/netzwelt/web/weltweiter-datenverkehr-soll-sich-bis-2016-vervierfachen-a836495.html
20
Festplatten haben noch weitere Bestandteile (z.B. Anschlüsse, Actuatorachsen, Stromversorgung), die an
dieser Stelle außer Acht gelassen werden
56
Plattenoberfläche. Hierbei muss hervorgehoben werden, dass sie sich Platte physisch um die eigene Achse drehen muss. Die Bipolarität der Platte lässt sich anschließend wieder auf das Binärsystem übertragen: nicht magnetisiert für 0, magnetisiert für 1. Das gleiche Prinzip gilt auch beim Lesen der Daten: Um einen bestimmten Bereich zu lesen, muss sich die Platte erst bis zu der Stelle drehen, an
der die Daten gespeichert sind. Dies nimmt Zeit in Anspruch und sorgt somit für
langsamere Lese-/und Schreibezeiten. Der Vorteil von Festplatten besteht darin,
dass sie nicht flüchtige Speicher sind, also ihre Daten auch ohne Stromzufuhr persistent halten können. Des Weiteren sind sie als sehr gereifte Technologie verhältnismäßig preiswert. Sie finden zum Beispiel als Datenspeicher von PCs oder Datenbanksystemen Anwendung.
Halbleiterspeicher basieren auf einem anderen Prinzip: jedes Bit wird in einem integrierten Schaltkreis, der aus ein oder mehreren Transistoren besteht, gespeichert.
Diese sogenannten Speicherzellen bilden die Basis vieler Datenträger, von denen
hier zunächst die Solid State Disk (SSD) und der Random-Access Memory (RAM)
hervorgehoben werden sollen. Die SSD verwendet NAND-Flash-Speicher, eine
Technologie, bei der Floating-Gate-Transistoren eingesetzt. Das Floating-Gate ist
eine isolierte Elektrode, die Ladung permanent speichern kann und erst beim Anlegen negativer Spannung wieder entladen wird. Dadurch ist auch die SSD, ähnlich
wie die oben beschriebene Festplatte, ein nicht flüchtiger Speicher. Sie erreicht höhere Lese-/und Schreibgeschwindigkeiten, ist durch die fehlenden mechanischen
Bewegungen leiser und robuster.
Der RAM ist hingegen ein flüchtiger Speicher. Das heißt, dass die Daten bei einer
Unterbrechung der Stromzufuhr verloren gehen. Der Name Random-Access Memory liegt dem Fakt zu Grunde, dass jede Speicherzelle direkt angesprochen werden kann und nicht sequenziell oder in Blöcken ausgelesen werden muss. Ram
zeichnet sich deswegen durch besonders schnelle Zugriffszeiten aus und wird deshalb als Hauptspeicher von Computern verwendet. Nachteilig wirken sich der verhältnismäßig hohe Preis und die Flüchtigkeit des Speichers aus.
57
Die Tabelle 10 fasst die Hauptmerkmale der drei vorgestellten Speichermedien zusammen. Bei den Zugriffsgeschwindigkeiten wird zwischen sequentiellen Zugriff
und direktem Zugriff unterschieden, um den Vorteil des Random-Access Memory
zu verdeutlichen. Zu beachten ist, dass die Werte von 2009 stammen. Zu dieser
Zeit waren SSDs auf dem Verbrauchermarkt noch nicht so weit gereift.
Speicher-
Flüchtigkeit
medium
Zugriffsgeschwindigkeit21
sequentiell
direkt
Preis22
Festplatte
(SATA)
Nicht flüchtig
53.2M
Werte/sek
316 Werte/sek
ab 0,03€ pro
GB
SSD
Nicht flüchtig
1924 Werte/sek
42.2M
Werte/sek
ab 0,35€ pro
GB
RAM
flüchtig
36.7M
Werte/sek
358.2M
Werte/Sekunde
ab 7,37€ pro
GB23
Tabelle 10: Vergleich von Speichermedien
Da bei großen Datenmengen eine hohe Verarbeitungsgeschwindigkeit ausschlaggebend ist, wird RAM immer häufiger im Bereich des Big Data als „In-Memory“Technologie eingesetzt. Dabei gilt es, zwei große Schwachpunkte des RAMs auszugleichen: Zuverlässigkeit und begrenzte Kapazität24. Eine angemessene Lösung
sind verteilte Systeme. Durch Replikation von Hardware und Daten werden die Auswirkungen bei Ausfällen reduziert. Des Weiteren wird das System sowohl in der
Kapazität als auch in der Rechenleistung horizontal skalierbar. Das HDFS ist ein
Dateisystem für verteilte Rechnersysteme und auch Apache Spark nutzt In-Memory
Technologie. Beide Systeme werden in den folgenden Kapiteln erklärt.
21
Werte entommen aus Figure 3 in http://queue.acm.org/detail.cfm?id=1563874
Endverbaucherpreise von www.alternate.de (20.02.2015)
23
DDR3-RAM
24
Vgl http://www.cubrid.org/blog/dev-platform/introduction-to-in-memory-data-grid-main-features/
22
58
3.2
Hadoop Distributed File System
Das Hadoop Distributed File System (HDFS) ist ein Dateisystem zum Speichern
großer Datenmengen auf verteilen Rechnersystemen (Cluster), das im Jahre 2008
im Rahmen des Hadoop-Projekts der Apache Foundation veröffentlich wurde.
Ziel bei der Entwicklung ist vor allem hohe Fehlertoleranz, da Fehler in der Hardware bei einer Vielzahl von Rechnern eher die Regel als die Ausnahme darstellen.
Des Weiteren soll die performante und skalierbare Arbeit mit großen Datasets ermöglicht werden. Typischerweise steht dabei eine hohe Lesegeschwindigkeit im
Vordergrund. Datensätze sollen möglichst nur einmal erstellt bzw. geschrieben werden, aber dauerhaft zum Lesen bereit stehen.
Die Architektur von HDFS ist nach dem Master/Slave-Modell aufgebaut. Den Kern
eines HDFS-Clusters bildet ein Master-Server, der sogenannte Namenode (Master). Er ist für die Regulierung der clientseitigen Zugriffe auf Dateien verantwortlich.
Darüber hinaus verwaltet er den Namensraum des Dateisystems. Der Namensraum
ähnelt stark dem anderer Dateisysteme: er ist hierarchisch strukturiert (Ordner, Unterordner, Dateien) und ermöglicht das Erstellen, Löschen, Verschieben und Umbenennen von Dateien und Ordnern. Intern werden Dateien in Blöcke aufgespalten
und in Datanodes (Slave) abgelegt. Das Mapping, also wie die Blöcke in den
Datanodes abgelegt werden, wird ebenfalls vom Namenode verwaltet.
59
Abbildung 11: HDFS-Architektur25
3.3
Apache Spark
Spark ist ein open-source Framework für skalierbare und verteilt arbeitende Software, das 2009 an der University of Berkeley entwickelt und 2013 an Apache gestiftet wurde. Spark ein sehr wachsendes und aktives Projekt (Tabelle 11). Es ist
zurzeit eines der drei aktivsten Projekte der Apache Foundation und hatte in der
ersten Hälfte des Jahres 2014 mehr Beiträge von Entwicklern als MapReduce,
YARN und HDFS zusammen. Auch im Vergleich mit allgemeinen Projekten des Big
Data- und Machine Learning-Bereichs sticht Spark hervor. So ist es zum Beispiel
aktiver als NumPy oder matplotlib, zwei beliebte Python-Projekte zur Datenverarbeitung.
25
http://hadoop.apache.org/docs/r1.2.1/hdfs_design.html
60
Juni 2013
Juni 2014
beitragende Entwickler
68
255
beitragende Firmen
17
50
Gesamtanzahl lines of code
63 000
175 000
Tabelle 11: Apache Spark Projekt-Aktivität
Warum konnte Spark in so einer kurzen Zeit so wachsen und welche Anwendungsbereiche hat es zurzeit?
Laut [78] ist die Fähigkeit große Datenmengen zu speichern kein Wettbewerbsvorteil mehr für Unternehmen, da die Kosten und der Aufwand für große Datenspeicher
in den vergangenen Jahren stark gesunken sind. Die wirklichen Vorteile liegen nun
in zwei Bereichen: Geschwindigkeit und Qualität der Datenverarbeitung. Die Geschwindigkeit beschreibt, wie schnell man von Daten zu Entscheidungen kommen
kann, während die Qualität beschreibt, welche Algorithmen man auf die Daten anwenden kann. In beiden Bereichen sticht Apache Spark hervor. In [3] wurde zum
ersten Mal die gute Performance von Spark SQL, das damals noch Shark hieß,
beschrieben. In einem Experiment wurden SQL-Abfragen an sowohl Apache Hive,
der Dataware House-Erweiterung von Hadoop und an Spark SQL geschickt. Die
verwendete Abfrage war nach dem Muster
SELECT * FROM grep WHERE field LIKE ’%XYZ%’;
aufgebaut und wurde auf ein 50GB Dataset angewandt. Sowohl das Hive Cluster
als auch das Spark Cluster haben bei einer gleichen Ausstattung 10 Nodes für die
Durchführung der Anfrage zur Verfügung gehabt. Die enormen Unterschiede in der
Performance können Abbildung 12 entnommen werden, wobei das „cold“ heißt,
dass zunächst ein RDD26 erstellt werden muss und „hot“, dass das RDD bereits
vorhanden ist und nur noch einmal verwendet werden muss.
26
Siehe Kapitel 3.3.2
61
Abbildung 12: Ausführungszeigen Spark/Hive im Vergleich
Ein ähnlicher Test wurde in der gleichen Arbeit auch zum Thema Machine Learning
gemacht. Sowohl auf Spark als auch auf Hadoop wurde eine lineare Regression
und ein k-means-Algorithmus über 10 Iterationen auf ein 100GB Dataset angewandt. Spark war bei der linearen Regression über 25mal schneller und bei der
rechenintensiveren k-means-Methode immernoch über 3mal schneller.
Noch beeindruckender sind die auf Databricks27 veröffentlichten Ergebnisse28 vom
letzten Jahr: Spark hält den Weltrekord im Sortieren großer Datenmengen. Beim
Test auf einem System aus 6592 Kernen und 206 Nodes konnte ein 100TB großes
Datenset innerhalb von 23 Minuten sortiert werden. Zum Vergleich: der vorherige
Weltrekord wurde von Hadoop MapReduce gehalten und lag bei der Nutzung von
10mal mehr Nodes bei 72 Minuten.
Darüber hinaus wird Spark mit einer Vielzahl von anspruchsvollen Algorithmen zur
Datenverarbeitung ausgeliefert und häufig erweitert. Die einzelnen Komponenten
erlauben unter anderen maschinelles Lernen und das Arbeiten mit Graphen. Die
27
28
Entstanden aus dem UC Berkeley AMPLab, Erfinder von Spark
http://databricks.com/blog/2014/11/05/spark-officially-sets-a-new-record-in-large-scale-sorting.html
62
Benutzung dieser Algorithmen kann sehr elegant sein. So hat zum Beispiel Yahoo!
in einem Testprojekt das bisherige Hadoop basierte Programm zur Personalisierung
der Website auf Spark umgestellt. Dabei ist das Projekt von 15 000 Zeilen C++ Code
auf nur 120 Zeilen Code in Scala geschrumpft. Viele weitere Firmen nutzen Spark
in unterschiedlichsten Bereichen wie Sicherheit29, Echtzeitempfehlungen30 und Business Intelligence31.
In den folgenden Kapiteln wird näher auf den Umfang und die Architektur von Spark
eingegangen. Des Weiteren werden die Resilient Distributed Datasets, die das fundamentale Konzept von Spark bilden, erläutert.
3.3.1
Spark Komponenten und Architektur
Das Spark-Projekt besteht aus mehreren Komponenten, die in Abbildung 13 grafisch dargestellt sind. Die Hauptfunktionen befinden sich im Spark Core. Hier werden die Aufgaben verwaltet, das Dateisystem angesprochen und die Fehlerbehandlung in Gang gesetzt. Im Spark Core ist darüber hinaus die Spark API enthalten, die
unter anderem die in Kapitel 3.3.2 beschriebenen RDDs bereitstellt.
29
https://www.youtube.com/watch?v=ogedtaPYsyM | https://www.youtube.com/watch?v=O6qUCfKzS_o
https://www.youtube.com/watch?v=3LBgiFch4_g | https://www.youtube.com/watch?v=dKOU16SG214
31
https://www.youtube.com/watch?v=5p3xU49ec_I
30
63
Abbildung 13: Spark Stack32
Eine weitere Komponente ist Spark SQL. Seine Anfänge hatte Spark SQL als
Apache Shark-Projekt, bis es komplett in Spark integriert wurde. Aus diesem
Grunde findet man noch viele Publikationen unter dem alten Namen. Im Grunde
genommen ist Spark SQL ein Datenanalyse-System, das neben SQL-Abfragen
auch weiterführende Funktionalität ermöglicht. Es ist kompatibel zu Apache Hive,
dem Datawarehouse-System von Apache, und ist in der Lage, Hive Query Language-Abfragen (HQL) auszuführen. Die Kompatibilität zu Hive ermöglicht die Arbeit
mit Systemen, die die Hadoop API implementieren. Dazu gehört auch das Dateisystem HDFS, das im praktischen Teil dieser Arbeit genutzt wird. Weitere Dateiformate, wie JSON, XML und Parquet werden ebenfalls unterstützt.
Für diese Arbeit ist außerdem das Modul Mlib wichtig. Mlib ist eine Bibliothek mit
verschiedenen Algorithmen und Funktionalitäten im Bereich des maschinellen Lernens. Es wird eine Vielzahl von Algorithmen bereitgestellt. Darunter befinden sich
auch die für die Sentiment Analyse üblichen Klassifikatoren, wie zum Beispiel Support Vektor Machines und Bayes. Die Klassen können in Java, Python und Scala
genutzt werden. Ähnlich wie bei Spark SQL ist es auch hier möglich, Hadoop-Dateisysteme anzusprechen.
32
http://www.pentaho.com/sites/default/files/uploads/resources/learning_spark_preview_ed.pdf
64
Die beiden anderen Komponenten, Spark Streaming und GraphX, spielen in dieser
Arbeit eine eher untergeordnete Rolle. Spark Streaming ermöglicht die Verarbeitung
von Datenströmen zur Laufzeit. GraphX hingegen ist eine Bibliothek mit diversen
Funktionen zur Manipulation und Verarbeitung von Graphen. Sie stellt gängige Algorithmen wie zum Beispiel PageRank bereit. Beide Komponenten erweitern die
RDDs von Spark und sind über Java, Python und Scala ansprechbar.
Die in Abbildung 15 unter dem Spark Core abgebildeten Elemente sind die sogenannten Cluster Manager. Spark wird üblicherweise auf Computer Clustern, also
einem Verbund mehrere Rechner, ausgeführt. Dabei koordiniert der SparkContext
die verschiedenen, voneinander unabhängigen, Prozesse der Spark Anwendung.
Um diese Aufgabe erfüllen zu können, muss der SparkContext mit einem Cluster
Manager verbunden werden, der die Ressourcen über die verschiedenen Anwendungen verteilt. Derzeit werden drei verschiedene Cluster Manager unterstützt:
Sparks eigener Cluster Manager, YARN und Mesos. Letztere sind ebenfalls Projekte der Apache Foundation.
Abbildung 14: Spark Cluster-Architektur33
Die höchste Einheit in Spark ist eine Applikation, also eine Instanz des SparkContext. Innerhalb einer Applikation können mehrere Jobs ausgeführt werden. Dies
33
https://spark.apache.org/docs/latest/img/cluster-overview.png
65
können einzelne Batches, interaktive Sitzungen mit mehreren Jobs oder dauerhaft
verfügbare Server, die auf Anfragen antworten, sein. Jede Applikation hat sogenannte Executors, die sich auf Worker Nodes befinden. Ein Executor führt bestimmte Prozesse für die Applikation aus und bleibt für die gesamte Laufzeit der
Applikation verfügbar. Also selbst dann, wenn er zurzeit keinen Prozess ausführt.
Dies hat verschiedene Vorteile. Zum einen laufen so Applikationen isoliert voneinander ab (vgl. [81]) und zum (vgl. [80]) anderen können sie Prozesse schnell gestartet werden und auf die in-memory Daten zugreifen Nachteilig ist, dass sich Applikationen keine Daten teilen können.
Mit Spark ist es möglich, Jobs sowohl innerhalb einer Applikation als auch applikationsübergreifend zu planen. Für die applikationsübergreifende Planung ist der
Cluster Manager verantwortlich. Generell unterscheidet man hier zwei Arten, Ressourcen zu verteilen. Beim static partioning erhält jede auf dem Cluster laufende
Applikation ein festgelegtes Maximum an Ressourcen. Etwas flexibler verhält sich
das dynamic sharing of CPU. Zwar bekommen die Applikationen auch hier ein festgelegtes Maximum zugewiesen, aber wenn sie nicht laufen, können andere Applikationen die zugewiesenen CPU-Kerne nutzen.
Innerhalb einer Applikation können mehrere Jobs gleichzeitig laufen (siehe Abbildung 16). Standardmäßig wird das First in-First out-Prinzip genutzt (FIFO). Das
heißt, dass der Job, der zuerst gestartet wurde, bei der Verteilung von Ressourcen
priorisiert wird.
Abbildung 15: Jobausführung in einer Spark-Applikation34
34
http://blog.cloudera.com/wp-content/uploads/2014/05/spark-yarn-f1.png
66
3.3.2
Resilient Distributed Datasets
Apache Spark nutzt Resilient Distributed Datasets (RDD) zur Ausführung von inmemory Anwendungen auf Computer-Clustern. RDDs wurden zuerst in [4] als
„read-only, partioned collection of records“ beschrieben. Sie können nur durch
Transformation (transformations), also deterministische Operationen, aus einem zuverlässigen Speicher oder anderen RDDs erstellt werden. Zu diesen Operationen
zählen zum Beispiel Filter, Gruppierungen, Kreuzprodukte, Partitionen und weitere.
Jedes RDD enthält Informationen darüber, wie es von anderen Datasets erschaffen
wurde. Dies dient der Fehlertoleranz, da es so für ein Programm nicht möglich ist,
ein RDD zu referenzieren, das es nach einem Fehler nicht wiederherstellen kann.
Für die Nutzung von RDDs wird gegen die API von Spark programmiert. Der erste
Schritt dabei ist die Definition und Transformation von RDDs aus einem zuverlässigen Speicher. Anschließend können auf diesen RDDs Operationen (actions) ausgeführt werden, die Werte zurückgeben oder Daten in einen Speicher exportieren.
Eine Übersicht über die gängigen Transformationen und Operationen kann der
Spark Dokumentation35 entnommen werden. Darüber hinaus können RDDs für die
spätere Nutzung mithilfe der persist-Methode im Speicher von Spark abgelegt werden.
In [4] werden sowohl Vorteile als auch Grenzen von RDDs ausgearbeitet. Verglichen wird hierbei mit der Distributed Shared Memory (DSM) Technologie, die die
Verteilung des Arbeitsspeichers auf verteilten Systemen beschreibt. Der größte Unterschied zwischen RDDs und den herkömmlichen DSM besteht auf in Granularität
der Lese- und Schreiboperationen. DSMs verhalten sich feingranular (fine-grained).
Dies bedeutet, dass bei einem Update jeder Datensatz einzeln angesprochen wird.
Im Gegensatz dazu sind RDDs grob granular (coarse grained). Die Datensätze können also nicht einzeln angesprochen werden. Stattdessen beziehen sich die Operationen immer auf das gesamte Datenset und es wird die Information, durch welche
Operation das RDD entstanden ist, mit abgelegt. Dadurch wird die Nutzung von
RDDs auf Anwendungen beschränkt, die ihre Datenoperationen in Bulk ausführen
35
http://spark.apache.org/docs/1.2.0/programming-guide.html#rdd-operations
67
wollen. Ein Vorteil hingegen ist, dass die Fehlerbehandlung effizienter wird, da fehlerhafte Partitionen eines RDDs schlichtweg neu berechnet werden können. Darüber hinaus wird auch ein großer Overhead gespart, da für die Wiederherstellung
der RDDs keine Log-Dateien, sondern nur der sogenannte Lineage-Graph, notwendig sind. Als Lineage-Graph bezeichnet man dabei die Kette von Informationen,
welche Transformationen auf den betreffenden RDDs durchgeführt wurden. Des
Weiteren kann die Runtime-Umgebung bei der Nutzung von Bulk-Operationen auf
RDDs durch Planung der Tasks die Performance verbessern.
Resilient Distributed Datasets werden für gewöhnlich durch fünf Elemente (Tabelle
12) so dargestellt, dass ihre Abstammung nachvollziehbar bleibt.
Bezeichnung
Spark-Implemen-
Erklärung
tierung
Partition
Partitions()
Atomare Stücke des Datasets.
Abhängigkeiten
Dependencies()
Abhängigkeiten zu den Eltern-RDDs
Berechnungsfunktion
Iterator(p, parentI- Eine Funktion, um das RDD anhand der Elters)
tern-RDDs zu berechnen.
Anordnung der Da- preferredLoca-
Informationen zur Anordnung der Daten.
ten
tions(p)
Auf einige Partionen p kann durch Lokalität
der Daten schneller zugegriffen werden.
Partionsschema
Partitioner()
Informationen zur Partitionierung der Daten
(hash/range).
Tabelle 12: Repräsentationselemente von RDDs
Durch die Nutzung von Operationen können zwischen den RDDs zwei verschiedene
Abhängigkeiten, nämlich die engen (narrow) und weiten (wide), entstehen. Bei engen Abhängigkeiten wird jede Partition des Eltern-RDD höchstens von einer Partition des Kind-RDDs benutzt, während es bei weiten Abhängigkeiten mehrere sein
können. Diese bewusste Unterscheidung hat den Vorteil, dass bei engen Abhängigkeiten ein besserer Ausführungsplan auf nur einem Knoten des Clusters genutzt
werden kann und die Wiederherstellung bei einem Fehler effizienter ist, da nur die
68
verlorengegangenen Eltern-Partitionen wieder hergestellt werden müssen. Abbildung 16 stellt den Unterschied zwischen den beiden Abhängigkeitsformen grafisch
so dar, dass ein blaues Rechteckt ein RDD ist, die in ihm liegenden ausgefüllten
Rechtecke Partitionen sind und die gerichteten Pfeile die Abhängigkeiten sind.
Abbildung 16: Abhängigkeitsformen von RDDs
3.3.3
Daten in Apache Spark
Apache Spark setzt auf das HDFS-Filesystem auf. Wie bereits in Kapitel 3.2 erwähnt, werden Dateien in HDFS in Blöcke unterteilt und auf Data Nodes abgelegt.
Die Größe der Blöcke kann dabei je nach Einstellung des Systems entweder 124MB
(Standard) oder 64MB. Dateien werden redundant auf die Data Nodes verteilt und
dabei gesplittet, wenn sie die Blockgröße überschreiten. Wie genau die Dateien gesplittet werden, hängt vom InputFormat36 ab. Textdateien können beispielsweise
zeilenweise aufgeteilt werden.
36
http://hadoop.apache.org/docs/stable/api/org/apache/hadoop/mapred/InputFormat.html
69
Abbildung 17: Partitionierung einer Datei in HDFS
Beim Laden von Dateien in Apache Spark orientiert sich die Partitionsgröße zunächst an den Blöcken im HDFS. Das heißt, die in Abbildung 17 gezeigte Datei
würde als RDD mit zwei Partitionen erzeugt werden. Zur Anpassung der Parallelisierung ist es möglich, RDDs zu repartitionieren. Das führt dazu, dass die Daten auf
dem Filesystem neu verteilt werden und kann somit anfangs Zeit in Anspruch nehmen.
Die wichtigsten in dieser Arbeit verwendeten Datenstrukturen der MLLIB-Bibliothek
und somit von Apache Spark sind Vektoren und LabeledPoints. Vektoren kann man
in sparse (dünnbesetzte) und dense (dichtbesetzte) Vektoren unterteilen. In der
Text-Klassifikation und somit auch in der Sentiment Analyse werden eher dünnbesetzte Vektoren genutzt, da es viele Feature (Wörter) in einem Korpus gibt, aber
wahrscheinlich nur wenige dieser Wörter in einem einzelnen Dokument vorkommen.
Man nehme zum Beispiel die beiden Sätze:
„Ich mag Hunde viel lieber als Katzen.“
„Du magst Hamster viel mehr als Katzen.“
Das gesamte Vokabular ist also
{Ich, mag, Hunde, viel, lieber, als, Katzen, du, magst, Hamster, mehr}.
70
In einem dichtbesetzten Vektor würden die beiden Sätze wie folgt repräsentiert werden.
Satz 1 = {1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0}
Satz 2 = {0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1}
Es werden also auch die Einträge, die nicht vorhanden sind, mit einer 0 repräsentiert. Dies führt bei einem großen Gesamtvokabular zu sehr großen, speicherintensiven Vektoren. Um dieses Problem zu umgehen, werden Daten auch in dünnbesetzten Vektoren dargestellt.
In Spark wurden dünnbesetzte Vektoren unter dem Namen SparseVector 37 in der
Version 1.0 implementiert (vgl. [72]). Die oben dargestellten Sätze sehen als SparseVector wie folgt aus:
Satz 1 = {11, [0, 1, 2, 3, 4, 5, 6, 7], [1, 1, 1, 1, 1, 1, 1]}
Satz 2 = {11, [3, 5, 6, 7, 8, 9, 10. 11], [1, 1, 1, 1, 1, 1, 1]}
Der erste Eintrag stellt dabei die Gesamtgröße des Vokabulars bzw. aller Feature
dar, der zweite Eintrag zeigt, an welchen Stellen (Index) der Vektor Einträge hat,
die nicht 0 sind und der dritte Eintrag stellt den Wert dieser Einträge dar. Die Nützlichkeit dieser Systems wird klar, wenn man sich die Verhältnisse zwischen Gesamtanzahl der Feature und der Anzahl der Feature Dokument ändert. Die Phrase „Ich
mag.“ würde beim oben beschriebenen Vokabular mit einem SparseVector wesentlich effizienter dargestellt werden als mit einem dichtbesetzten Vektor.
dense = {1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0}
sparse = {11, [1, 2], [1, 1]}
37
http://spark.apache.org/docs/1.2.1/api/scala/index.html#org.apache.spark.mllib.linalg.SparseVector
71
4
In diesem Kapitel wird die Sentiment Analyse in Apache Spark beschrieben. Dabei
wird zuerst auf die Sentiment Klassifikation auf Dokumenten-Ebene eingegangen.
Es soll untersucht werden, wie gut Spark mit einer großen Anzahl von Features, wie
es bei der Sentiment Klassifikation häufig der Fall ist, umgehen kann. Anschließend
wird die Implementierung eines einfachen Algorithmus zur Sentiment Lexikon Generierung auf Apache Spark beschrieben.
4.1
Skalierbarkeit der Sentiment Klassifikation
In diesem Kapitel wird auf die Sentiment Klassifikation in Apache Spark eingegangen. Dabei wird ein Vergleich zwischen einer lokalen Lösung, die auf der Python
Bibliothek SKLearn basiert und Apache Spark, das auf einem Computer-Cluster der
Hochschule für Technik und Wirtschaft Berlin aufgesetzt ist, durchgeführt. Das Ziel
dieses Vergleichs ist das Testen der Skalierbarkeit von Algorithmen zur Sentiment
Klassifikation. Obwohl also eine angemessene Genauigkeit der Analyse angestrebt
wird, steht diese nicht im Vordergrund.
4.1.1
Vorgehen
Die Grundlage für den Vergleich bilden die in Kapitel 4.2 beschriebenen Systeme
und die in Kapitel 4.3 beschriebenen Daten. Mithilfe von zwei Python Skripte (Anhang) werden zunächst Feature gesammelt und dann die Sentiment Klassifikation
mit dem naïven Bayes und der Support Vector Machine durchgeführt. Es wird versucht, die Skalierbarkeit der beiden Klassifikatoren zu beschreiben, indem verschiedene Konfigurationen des Clusters und unterschiedlich umfangreiche Daten genutzt
werden.
72
Die Sentiment Analyse wird stark vereinfacht auf der Dokumenten-Ebene durchgeführt. Das heißt konkret, dass viele der in Kapitel 2 beschriebenen Grundlagen nicht
getestet werden. Vielmehr geht es darum, ein möglichst großes Dataset mit Dokumenten in zwei Klassen, „positiv“ und „negativ“, einzuteilen. Dabei sollen die Möglichkeiten des Cluster-Systems und des Apache Spark-Framework genutzt werden.
4.1.2
Technische Basis
Die Testsysteme sind zum einen in Tabelle 13 und zum anderen in Abbildung 18
dargestellt. Das in Abbildung 18 gezeigte Computer-Cluster der Hochschule für
Technik und Wirtschaft Berlin besteht aus insgesamt 6 Rechnern, die über das
Netzwerk verbunden sind. Sie haben alle Zugriff auf das unterliegende HDFSFilesystem mit insgesamt 10TB Speicherplatz. Der Zugriff auf das Cluster ist über
das HTW-Netzwerk möglich und kann auch über VPN realisiert werden. Der SparkDriver, also die steuernde Einheit von Apache Spark im Cluster (siehe Kapitel 3.3.1)
wird auf dem Rechner Hadoop03 gestartet, während die Rechner Hadoop04-Hadoop08 als Worker arbeiten. Standardmäßig starten die jeweiligen Worker mit der
vollen Anzahl an Kernen (24) und 512MB Ram per Executor.
Abbildung 18: Architektur des HTW-Cluster
73
Lokales System
Computer Cluster
Leistung pro Rechner, 6
Rechner insgesamt
CPU
Intel i5-4570 3.2 GHz
Dell R420 Intel Xeon E52420 v2 2.20 GHz 1600Mhz;
Zwei Prozessoren bei Hyper
Threading 12 => 24 Kerne
RAM
8GB , davon ca. 6 GB nutz- 16GB RDIMM
bar
Festplatte
SATA 7200RPM,
Cache
Betriebssystem
Windows 8.1 64 Bit
Software
Python 2.7, SciKit-Learn, Python 2.7, Apache Spark
NLTK
64MB SAS-Festplatten,
HDFSVerbund über Netzwerk
Debian GNU/Linux 7.7
1.2, NLTK
Tabelle 13: Testsysteme
Die dort dargestellte genutzte Software ist zum einen das Natural Language Processing Toolkit (NLTK) und zum anderen SciKit-Learn. Das NLTK ist eine Bibliothek
zur Textverarbeitung, die vor allem in Python sehr verbreitet ist. Sie ist sehr umfangreich, gilt aber nicht immer als die performanteste Lösung. So ist zum Beispiel der
Algorithmus zum Part-of-Speech-Tagging vergleichsweise langsam38. Die zweite
38
https://honnibal.wordpress.com/2013/09/11/a-good-part-of-speechpos-tagger-in-about-200-lines-of-python/
74
Software, SciKit-Learn, bietet eine Vielzahl an Funktionen zum maschinellen Lernen. Darunter sind diverse Klassifikatoren und Möglichkeiten zur Datenaufbereitung.
Das Spark-Cluster lässt sich durch diverse Parameter in seiner Leistung konfigurieren.
Bezeichnung
Beschreibung
spark.driver.memory
Speicher des Driver (512MB Standard)
spark.executor.memory
Speicher pro Executor (512MB Standard)
Threading
Einstellbar unter –master x[Number of Threads],
legt die maximale Threadanzahl fest
Partitions per RDD
Einstellbar beim Parallelisieren der RDDs, z.B.
sc.parallelize(data, NumberOfPartitions)
Tabelle 14: Konfigurationsparameter
4.1.3
Datenbasis
Die Datenbasis für die Sentiment Analyse in Spark bilden die in [76] gesammelten
Amazon-Kundenbewertungen39. Insgesamt umfassen unbereinigten Daten fast
35GB. Die Bewertungen stammen aus verschiedenen Produktkategorien.
39
https://snap.stanford.edu/data/web-Amazon.html
75
Anzahl von Kundenbewertungen
34,686,770
Anzahl von Kunden
6,643,669
Anzahl von Produkten
2,441,053
Anzahl von Kunden mit > 50 Bewertungen
56,772
Durchschnittliche Anzahl von Wörter pro Bewertungen
82
Zeit
Jun 1995 - Mar 2013
Tabelle 15: Zusammenfassung Datenbasis
Die Bewertungen befinden sich in verschiedenen, nach Kategorien unterteilten,
Textdateien und haben folgende Metatags.
Tag
Bedeutung
Beispiel
product/productID
Produkt ID
B00004CQI3
review/userID
Kunden ID
A2H5D7IK95F07M
review/profileName
Kundenname
ER
review/helpfulness
Andere Kunden empfan- 2/3
den dieses Review als
hilfreich/nicht hilfreich
review/score
Bewertung (numerisch)
5.0
review/time
Zeit des Review
1268179200
review/summary
Titel /Zusammenfassung Great Family Movie
review/text
Bewertungenstext
„This is a fantastic movie for...“
76
Tabelle 16: Tags in Datenbasis
Innerhalb des Textfiles stehen die Informationen zu den Metadaten immer innerhalb
einer Zeile. Die einzelnen Bewertungen sind durch eine Leerzeile voneinander getrennt.
Abbildung 19: Aufbau der Datenbasis
4.1.4
Aufbereitung der Daten
Die Daten sind in ihrer ursprünglichen Form nicht für die Klassifikation nutzbar. Zum
einen beinhalten sie überflüssige Informationen und zum anderen sind sie in einem
falschen Format.
In einem ersten Schritt müssen nur die relevanten Informationen rausgefiltert werden. Dies ist zum einem der Review/Score und der Review/Text. Das Einlesen erfolgt auf dem lokalen System zeilenweise (Abbildung 20). Dabei werden die irrelevanten Zeilen übersprungen.
77
Abbildung 20: Einlesen der Daten in SciKit Learn
In Spark ist dieses Vorgehen ungeeignet, da nicht sichergestellt werden kann, dass
Reviews beim Partitionieren der Dateien nicht getrennt werden. Wie in Kapitel 3.3.3
beschrieben, werden Dateien in Spark aus den Data-Nodes des HDFS-Filesystem
heraus erstellt und zeilenweise in blockgroße Partitionen aufgeteilt. In Abbildung 21
ist die oben beschriebene Situation vereinfacht anhand einer 160MB Textdatei dargestellt. Man nehme an, dass in Zeile 442 die maximale Blockgröße von 128MB
erreicht wurde. Die Datei wird auf dem HDFS-Dateisystem also auf zwei Data-Nodes verteilt abgelegt. Für den Aufruf der Datei in Spark mit dem, Befehl
bedeutet das, dass Zeile 1-441 in Partition 1 und alles ab Zeile 442 in Partition zwei
zu finden ist. Mit den Befehlen getNumpartitions() und partitions.collect() kann dieses Verhalten nachvollzogen werden.
78
Abbildung 21: Aufteilung einer Datei in HDFS
Diese Information ist wichtig, weil es durch dieses Verhalten vorkommen kann, dass
ein Review/Score einem Review/Text nicht eindeutig zugeordnet werden kann. Um
dieses Problem zu umgehen, wird in Spark ein zusätzlicher Bearbeitungsschritt
durchgeführt. Die ursprüngliche Datei wird zunächst nach den relevanten Zeilen
gefiltert und dann repartioniert, damit sich alle Daten an einem Punkt befinden.
79
Abbildung 22: Datenvorbereitung Spark
Aus der Partition wird nun ausgehend von der in Python implementierten Logik,
dass ein Review/Text immer auf den dazugehörigen Review/Score folgt, eine neue
Datei erzeugt, die wieder im HDFS gespeichert wird. Nun sind alle zusammengehörigen Informationen in einer Zeile und können nicht mehr getrennt auftreten. Der
Aufbau der Daten ist nun ID[;]Score[;]Review/Text. Dieser Vorgang muss für jede
Datei nur einmal durchgeführt werden.
Sowohl in Spark als auch in SciKit Learn werden Review/Text und Review/Scores
für die Weiterverarbeitung getrennt gehalten und erst bei der Vorbereitung zur Klassifikation wieder zusammengeführt. Dies wird in Spark nun durch eine eindeutige
Zeilennummer ermöglicht (Review/Text und Review/Score von Bewertung 1 befindet sich in Zeile 1 der ursprünglichen Datei).
Der Review/Score ist bei der Klassifikation die erwünschte Klasse. Die Klassifikation
soll ein binäres Problem sein. Das heißt, dass in den Dokumenten nur zwischen
„positiv“ und „negativ“ unterschieden werden soll. Dabei gilt ein Score von über 3.0
als positiv und ein Score von 3.0 oder niedriger als negativ.
Aus dem Review/Text werden die Features gebildet. Der Text wird in einzelne Wörter unterteilt und weiter bearbeitet. Es werden verschiedene Bearbeitungsschritte
unternommen, die zum Testen der Skalierbarkeit allerdings teilweise weggelassen
werden. Darunter sind das Entfernen von Punktation, Lemmatisierung, das Zuordnen der Wortart und das Entfernen häufiger Wörter, wie „and“, „or“ und „is“, die
80
höchstwahrscheinlich keinen Einfluss auf das Ergebnis der Sentiment Klassifikation
haben werden (stopwords).
Abbildung 23: Funktionen zur Datenvorbereitung in Spark
Anschließend muss der Text in ein für den Klassifikator lesbares Datenformat gebracht werden. Bei SciKit Learn geschieht dies über einen TFID-Vectorizer, der für
jedes Wort im Dokument das TFID berechnet und abspeichert. Um ihn Spark ein
ähnliches Verfahren hinzukriegen, müssten mehrere Schritte durchgeführt werden.
Abbildung 24: Ermittlung TFIDF in Spark
Zunächst werden die Dokumente mit einem Hash-Vectorizer gehasht. Das heißt,
dass ein beliebiges Wort gemappt wird, indem mithilfe einer Hashfunktion ein Index
81
zugewiesen wird. Anschließend wird die Häufigkeit jedes Wortes anhand der Indizes berechnet. Der Vorteil dieser Funktion besteht darin, dass sie effizient ist, da
keine globale Index-zu-Wort-Zuordnung berechnet werden muss. Es kann jedoch
passieren, dass es zu Hash-Kollisionen kommt, also dass zwei unterschiedliche
Wörter einen gleichen Hash-Wert erhalten und somit gleichgesetzt werden.
Durch die Nutzung des HashingTF() entsteht in Spark ein Vektor, dessen StringRepräsentation in unten zu sehen ist. Vorne stehen die Hashwerte und hinten die
Häufigkeit des Auftretens in dem Dokument.
{1048576, [51713, 91349, 113450], [1.0, 2.0, 1.0]}
IDF und TFIDF sind in Spark getrennt. Zunächst muss IDF gebildet werden, indem
die vorher berechneten Hash-Werte mit der Funktion .fit() in das IDF-Model geladen
werden. Dadurch wird der IDF-Vektor berechnet, der anschließend mit der .transform() Anweisung skaliert werden kann. Das Ergebnis ist der TFIDF-Vektor:
(u‘4‘, SparseVector(1048576, {51713: 2.5257, 91349: 1.4271, 113450: 3.2189}))
dem an erster Stelle bereits seine ursprüngliche ID bzw. Zeilennummer hinzugefügt
wurde. Zusätzlich zum Hash-Wert jedes Worts ist nun der TFIDF-Wert (siehe Kapitel 2.2.4.9) angegeben.
Spark erwartet für die Klassifikation Daten im Format LabeledPoint40. Ein LabeledPoint besteht aus einem Double-Wert, der die Klasse bildet und einem Double-Array, das die Features enthält. Um diese benötigten Daten bereitzustellen, müssen
zunächst die Review/Scores- und Review/Text-Einträge, die nun in der Form eines
TFIDF-Vektors sind, wieder zusammengeführt werden. Dies geschieht mithilfe der
join()-Funktion über die anfangs zugeordneten IDs. Der LabeledPoint wird nun so
dargestellt:
40
https://spark.apache.org/docs/0.8.1/api/mllib/org/apache/spark/mllib/regression/LabeledPoint.html
82
(1.0,(1048576,[51713,91349,113450], [2.5257, 1.4271, 3.2189]))
Dieses Format kann anschließend von Spark zum maschinellen Lernen verwendet
werden.
In SciKit Learn wird statt des HashVectorizers ein CountVectorizer genutzt, der zum
selben Ergebnis führt. Die Anwendung des TFID-Vectorizers ist ähnlich.
4.1.5
Klassifikation
Die Klassifikation findet sowohl in Python als auch in Spark mit dem naiven Bayes
und einer Support Vector Machine statt. Diese Klassifikatoren wurden aufgrund ihrer häufigen Nutzung in der Text Klassifikation und der generell hohen Genauigkeit
ausgewählt. Während in SciKit Learn die auf hohe Datenmenge ausgerichtete CImplementierung der LIBLINEAR-SVM41 nutzt, wird in Spark eine eigene Implementierung mit SGD verwendet. Die unterliegenden mathematischen Funktionen sind
auf der Spark-Seite dokumentiert42.
41
42
http://www.csie.ntu.edu.tw/~cjlin/liblinear/#document
https://spark.apache.org/docs/1.1.0/mllib-linear-methods.html#mjx-eqn-eqregPrimal
83
4.1.6
Durchführung
Die Tests für die Skalierbarkeit werden in verschiedenen Phasen durchgeführt. In
Phase 1 wird die Python-Implementierung auf dem lokalen System und Apache
Spark auf einem einzelnen Rechner des Computer-Clusters getestet. Hiermit soll
ermittelt werden, wie die Leistung von Spark sich mit der von SciKit Learn bei ähnlicher Hardware vergleichen lässt. Danach wird nur noch auf Spark mit unterschiedlichen Einstellungen getestet. Die Parameter für Driver Memory und Executor Memory werden angepasst. Des Weiteren wird die Partitionierung der eingelesen Datei
manuell beeinflusst. Die Ergebnisse sind in den jeweiligen Tabellen zu sehen. Es
werden unterschiedlichen Dateigrößen getestet. Die Genauigkeit des Klassifikators
wird der Vollständigkeit halber mit angegeben. Die einzelnen Versuche werden im
Folgenden genauer beschrieben.
Versuch 1:
Datenvorbereitung: Einlesen, Sätze in Wörter splitten, Entfernen von Punktation,
Entfernen von Stop-Wörtern, Lemmatisierung, Part-of-Speech-Tagging
Spark I: 1 Rechner des Clusters, 2 Threads, 6 GB Driver Memory, 6 GB Executor
Memory, Apache Spark 1.2
Lokales System: Auslastung CPU: max. 29%, Auslastung RAM: max. 450 MB, SciKit Learn mit Python 2.7
84
Dateigröße
Datenvorbereitung
35MB, 58,621 Reviews
Lokales System
Spark I
13min 8sek
12min 20sek
(davon 12min 35sek (davon 11min 10sek
für POS-Tagging)
für POS-Tagging)
Naive Bayes (inkl. Erstellung des 1sek
TFIDS-Vektors)
83% Genauigkeit
30min 44sek (davon
30min
17sek
für
TFID)
83% Genauigkeit
Support Vector Machine (inkl. 1sek
Erstellung des TFIDS-Vektors)
87% Genauigkeit
30min 32sek (davon
30min
17sek
für
TFID)
84% Genauigkeit
Tabelle 17: Performance-Test 1
Versuch 2:
Änderung: größere Datei
Entfernen von Stop-Wörtern, Lemmatisierung, Part-of-Speech-Tagging
Lokales System: Auslastung CPU: max. 31%, Auslastung RAM: max. 700 MB, SciKit Learn
85
Dateigröße
Datenvorbereitung
Lokales System
Spark I
58min 10sek
53min 58sek
(davon 56min 15sek (davon 49min 58sek
für POS-Tagging)
für POS-Tagging)
TFIDS-Vektors)
77% Genauigkeit
1h 48min 37sek (davon 1h 48min 6sek für
TFID)
75% Genauigkeit
81% Genauigkeit
1h 48min 19sek (davon 1h 48min 6sek für
TFID)
71% Genauigkeit
Versuch 3:
Änderung: größere Datei, kein Part-of-Speech-Tagging
Entfernen von Stop-Wörtern, Lemmatisierung
Lokales System: Auslastung CPU: max. 30%, Auslastung RAM: max. 2,2 GB, SciKit Learn
86
Dateigröße
Datenvorbereitung
Lokales System
Spark I
3min 55sek
6min 40sek
TFIDS-Vektors)
80% Genauigkeit
1h 7min
56min
82% Genauigkeit
86% Genauigkeit
78% Genauigkeit
Aufgrund der enormen Laufzeiten in Spark wird für die folgenden Versuche der
Code angepasst. Statt Scores und Review-Texte getrennt zu halten und am Ende
zu joinen, werden sie nun in einem RDD geführt. Des Weiteren werden keine TFIDFWerte mehr berechnet, sondern nur die reinen Hash-Häufigkeitswerte genutzt. Die
betroffenen Stellen sind in Abbildung 25 zu sehen.
Abbildung 25: Code-Anpassung 1
87
Das bedeutet nun auch, dass die jeweiligen Punkte „Naive Bayes“ und
„SVM“/“Support Vector Machine“ nun nur noch folgende Operationen umfassen:
Tranieren des Modells, Prognose und Berechnung der Genauigkeit. Im Code sind
diese Elemente wie in Abbildung 26 (respektive auch für die Support Vector Machine) zu sehen umgesetzt.
Abbildung 26: Bayes in Spark
Versuch 4:
Änderung: größere Datei
Entfernen von Stop-Wörtern, Lemmatisierung
Lokales System: Auslastung CPU: max. 30%, Auslastung RAM: max. 6,6 GB, SciKit Learn
88
Dateigröße
1,085GB, 1,2 Mio Reviews
Lokales System
Spark I
Datenvorbereitung
20min 53sek
10min 32sek
Naive Bayes
1min 25sek
21min 41sek
80% Genauigkeit
83% Genauigkeit
2min 6sek
21min 30sek
88% Genauigkeit
75% Genauigkeit
Support Vector Machine
Diese Datei ist die letzte Datei, die mit dem lokalen System bearbeitet werden kann.
Die darauffolgenden Dateien führen beim Trainieren der Klassifikatoren zu Out-ofMemory-Fehlern.
Es beginnt Phase zwei der Durchführung, bei der verschiedene Einstellungen des
Spark-Clusters gegeneinander getestet werden.
Versuch 1:
Spark 1: 3GB Executor Memory, Partitionen wie in HDFS (50)
Spark 4: 12GB Executor Memory, neue Partitionierung (150)
89
Dateigröße
9,114GB, 7,85 Mio Reviews
Spark 1
Einlesen
Daten
der 12min 48sek
Spark 2
Spark 3
Spark 4
12min 36sek
12min 44sek
8min 47sek
Naive Bayes
21min 29sek
21min 33sek
21min 37sek
8min 26sek
SVM
21min 37sek
21min 32sek
21min 25sek
8min 37sek
Versuch 2:
Da Versuch 1 gezeigt hat, dass die bloße Änderung des zur Verfügung stehenden
Speichers kaum Einfluss auf die Leistung hat, wird in Versuch zwei eine etwas größere Datei in Hinblick auf Partitionierung getestet.
Spark 1: 12GB Executor/Driver Memory, Partitionen wie in HDFS (81)
Spark 4: 12GB Executor/Driver Memory, neue Partitionierung (300)
90
Dateigröße
14,3 GB, 12,8 Mio Reviews
Spark 1
Einlesen
Daten
der 16min 53sek
Spark 2
Spark 3
Spark 4
14min 12sek
13min 38sek
11min 55sek
Naive Bayes
26min 40sek
26min 31sek
25min 12sek
23min 55sek
SVM
26min 34sek
26min 15sek
25min 23sek
23min 37sek
Versuch 3:
Mit diesem Versuch soll die Auswirkung des Zwischenspeicherns von RDDs untersucht werden. Wenn ein RDD nicht gecached wird, muss es bei jeder auf ihm ausgeführten Aktion alle Transformationen erneut durchführen. Zur Untersuchung wird
das RDD an drei in Abbildung 27 gezeigten Stellen in den Cache geladen.
Abbildung 27: Caching in Spark
Der nun endgültige Code ist in Teil A des Anhangs zu sehen.
Versuch 4:
91
Spark 4: 12GB Executor/Driver Memory, neue Partitionierung (300)
Dateigröße
14,3 GB, 12,8 Mio Reviews
Spark 1
Einlesen
Daten
der 16min 55sek
Spark 2
Spark 3
Spark 4
13min 38sek
13min 38sek
12min 06sek
Naive Bayes
57sek
46sek
46sek
52sek
SVM
47sek
35sek
35sek
1min 46sek
Versuch 5:
Mit der in Versuch 4 neu gewonnenen Information, dass das Caching eines enormen Einfluss auf die Skalierbarkeit hat, werden nun noch unterschiedlichen Datenmengen mit den gleichen Einstellungen getestet. Die Einstellungen sind annähernd
die maximalen Einstellungen des Clusters mit Rücksicht auf eventuell andere laufende Prozesse und das Betriebssystem.
14GB Driver-Memory/Executor Memory
Partitionen anhand der Datei
Datei 1: 17 GB (137 Partitionen)
Datei 2: 34GB (237 Partitionen)
Datei 3: 68GB (548 Partitionen)
92
Test der Skalierbarkeit
Datei 1
Einlesen
Daten
der 22min 10sek
Datei 2
Datei 3
34min 19sek
52min 32sek
Naive Bayes
1min 10sek
12min 5sek
2h 32min
SVM
2min 56sek
3min 51sek
2h 35min
Bei der letzten Datei kam es zu häufigen Failed Stages, die zur erneuten Ausführung von Transformationen führten. Des Weiteren war es ob der großen Datenmenge nicht mehr möglich, die RDDs im Cache zu halten. Eine Alternative würde
hier die Funktion persist() geben. Dieser Test zeigt, dass sich Spark, mit Ausnahme
einiger Ausreißerwerte, die zum Beispiel durch konkurrierende Prozesse (es
herrscht das First in First-out-Prinzip) entstanden sein können, bei kleineren Datenmengen linear skalieren lässt.
4.1.7
Bewertung der Ergebnisse
Im Folgenden werden die Ergebnisse der Untersuchungen diskutiert. Dafür soll zuerst gezeigt werden, wie Spark den Programmablauf plant und durchführt.
Wie bereits in Kapitel 3.3.1 beschrieben wurde, verteilt der Driver Jobs und Tasks
an die Executor Nodes. Diese Jobs werden in Stages eingeteilt, da man in Spark
zwischen Transformationen und Aktionen unterscheidet. Alle Transformationen sind
lazy. Das heißt, sie werden erst dann ausgeführt, wenn sie wirklich ausgeführt werden müssen. Es ist dadurch möglich mehrere Transformationen auszuweisen ohne
dass sie direkt umgesetzt werden. Sobald eine Aktion ausgeführt wird, müssen die
vorher angegebenen Transformationen ausgeführt werden. Der DAG, also der interne Prozessplaner von Spark, ermittelt an dieser Stelle den besten Weg, um die
93
Transformationen und anschließend die Aktionen durchzuführen. Der Bereich zwischen jeder Aktion ist eine Stage. In den durchgeführten Versuchen sind die Stages
nach join() und collect() aufgeteilt. Innerhalb der Stages werden von den Executoren
Tasks ausgeführt. Dem Cluster stehen insgesamt sieben Executoren zur Verfügung.
Abbildung 28: Executoren im Cluster
Dabei wird Hadoop03 einmal als Executor und einmal als Driver aufgeführt. In der
Rolle als Driver ist dieser nur für das Sammeln von Daten und Verteilen von Aufgaben zuständig. Es wird kein Datenverarbeitung durchgeführt. Die Anzahl der verteilten Tasks hängt mit dem Level der Parallelisierung zusammen.
Problemstellen im Code
Bei der Durchführung der Versuche wurde schnell klar, dass die Leistung von Spark
im Cluster und auf einem einzelnen Rechner stark hinter der lokalen Lösung mit
Python bleibt. Der Grund hierfür wurde zuerst im Quellcode der Applikation gesucht.
Dort gab es vor allem zwei Problemstellen: die Berechnung des TDIDF und das
94
anschließende zippen der Werte, sowie den Join der neu berechneten ReviewWerte mit den Scores.
Bei einem Join entsteht, wie in [75] beschrieben, eine hoher Datenaustausch im
Netzwerk, da die Schlüssel beider zu joinenden Datasets über das Netzwerk an
eine Maschine geschickt und dann dort zusammengeführt werden.
Abbildung 29: Join in Spark
Dieses Verhalten lässt sich zum einen mit der partitionBy()-Funktion beeinflussen,
indem ein vorher definierter Partitionierer mitgegeben wird. So ist bekannt, welche
Keys sich wo befinden und es muss statt beiden Datasets nur eines über das Netzwerk gesendet werden. Dieses Verhalten ließ sich während der Versuche leider
nicht replizieren, weswegen der Join, wie bereits erklärt, schlichtweg weggelassen
wurde.
Lokalität der Daten
In Spark werden unterschiedlichen Lokalitäten der Daten unterschieden. Die nicht
repartitonierten Daten haben bei den durchgeführten Versuchen alle automatisch
95
die zwei besten Level, Process_Local und Nodel_Local, zugeordnet bekommen.
Neben der tatsächlichen Lokalität der Daten hat auch die Einstellung „spark.locality.wait“ Einfluss auf das Lokalitätslevel. Nach Ablauf der angegeben Zeit versucht
Spark, die benötigten Informationen auf dem nächsten Level zu finden. Das heißt
konkret, dass ein höher eingestellter Wert theoretisch dazu führen könnte, eine bessere Datenlokalität zu erreichen. Bei der Repartitionierung der Daten ist die Lokalität
auf den niedrigsten Level, ANY, gesunken. Dennoch war die tatsächliche Ausführungszeit geringer.
Driver Memory
Die Größe des Driver Memory ist immer dann von Bedeutung, wenn für eine Action
die Daten an einer Stelle gesammelt werden müssen. Das ist zum Beispiel bei collect() oder take() der Fall. In den durchgeführten Experimenten hatte Driver-Memory
keinen großen Einfluss auf die Performance.
Parallelisierung
Beim Einlesen einer Datei aus dem HDFS-Filesystem sind die Partitionen eines
RDDs zunächst die Block-IDs im HDFS (vgl [73]). Die dort eingestellte Blockgröße
von 128MB führt dazu, dass eine 1GB große Datei in 9 Partitionen unterteilt wird
und somit maximal 9 Threads erstellt werden können. Der optimale Level der Parallelisierung liegt allerdings weitaus höher. In der Spark-Dokumentation wird 2-3
Partitionen pro Kern das Cluster empfohlen, was sich beim verwendeten System
auf über 300 Partitionen hochrechnen lässt. Die tatsächliche Auswirkung des Änderns der Partitionierung waren nicht so stark wie angenommen, dennoch konnten
Unterschiede beobachtet werden. Dabei ist das anfängliche Neuverteilen der Daten
kein großer Aufwand. Zum Repartionieren einer 14GB von 81 auf 300 Partitonen
hat das System 14 Sekunden benötigt.
Executor
96
Zunächst muss erwähnt werden, dass der in der Befehlszeile angegebene Speicher
nicht der Speicher ist, den der Executor zum Bearbeiten der Daten zur Verfügung
hat.
In dieser Zeile wird angegeben, dass jeder Executor einen Speicher von 1GB haben
soll. Daraus ergeben sich dann die in der nächsten Zeile gezeigten 530.3MB Speicher, der für Daten zur Verfügung steht.
Grund hierfür ist die im Spark.storage43 hinterlegte und in Abbildung X gezeigte
Funktion, durch die vom gesamten zur Verfügung gestellten Speicher ein Teil der
Memory Fraction (Standard 0,6) und ein Teil der Safety Fraction (Standard 0,9) bereitgestellt wird.
Abbildung 30: Berechnung des Executor-Speichers
Die Einstellungen des Executor-Memory hatten bei den Tests nur marginale Auswirkungen. Es müsste eventuell eine größere Datenmenge getestet werden.
Speichern von RDDs
Die größten Performancegewinne sind durch das Cachen von RDDs zu erzielen.
Das liegt daran, dass ansonsten die jeweiligen RDDs in ihrer gesamten Historie
43
https://github.com/apache/spark/blob/master/core/src/main/scala/org/apache/spark/storage/BlockManager.scala#L1152
97
erneut berechnet werden müssen. Mit der Funktion cache() wird der derzeitige Berechnungsstand eines RDDs im RAM gespeichert. Mit der Funktion persist() könnte
er auf der Festplatte hinterlegt werden.
4.2
Implementierung eines Algorithmus zur Sentiment Lexikon Generierung
In diesem Kapitel wird der Ablauf und die Implementierung eines einfachen Algorithmus zur Sentiment Lexikon Generierung in Apache Spark beschrieben. Die
Schlüsselkonzepte dafür wurden bereits in Kapitel 2.1.4 beschrieben.
4.2.1
Grundlage
Die Grundlage für den Algorithmus ist die Annahme, dass positive Stimmungswörter
häufig mit anderen positiven Stimmungswörtern auftreten, während negative Stimmungswörter häufiger mit anderen negativen Stimmungswörtern auftreten. Des
Weiteren bildet die im Kapitel 2.2.4.5 und 2.1.4 untersuchte Aussage, dass Stimmungswörter sehr häufig Adjektive sind, die Basis des Algorithmus.
4.2.2
Datenbasis
Als Datenbasis dienen die im vorherigen Kapitel beschriebenen Amazon-Kundenbewertungen. Um die Laufzeit des Algorithmus zu verkürzen, werden die Daten vorbereitet. Die Vorbereitung wurde mit einer ursprünglich 35MB und einer ursprünglich 1GB großen Datei durchgeführt und ähnelt den Anfängen der in 4.1.4 beschriebenen Datenaufbereitung. Aus Reviews werden alle Zeilen, die nicht Review/Score
oder Review/Text sind entfernt. Anschließend wird mithilfe des POS-Taggers aus
dem NLTK das POS-Tagging für die gesamte Datei durchgeführt. Dieser Vorgang
98
wurde auf dem lokalen System ausgeführt und hatte bei der 1GB großen Datei eine
Gesamtlaufzeit von 1 Tag 4h 26min. Die hohe Laufzeit ist der Hauptgrund, warum
keine größere Datei als Datenbasis verwendet wurde. Eine einzelne Zeile aus den
jeweiligen Dateien hat nun das in Abbildung 31 gezeigte Muster.
Abbildung 31: Dictionary: Datenbasis
Im Gegensatz zu den Dateien in Kapitel 4.1 wurde die Reduktion der Review/Scores
auf 1.0 für positiv und 0.0 für negativ noch nicht vorgenommen.
4.2.3
Umsetzung
Nachdem die vorbereitete Datei in Spark eingelesen wurde, wird einer Trennung
der positiven und negativen Reviews vorgenommen. Da in der kleineren Datei zum
Beispiel dreimal so viele positive wie negative Reviews enthalten sind muss nun
eine Anpassung der Anzahl der Reviews vorgenommen werden. Dafür wird aus der
größeren Kategorie (positiv) nur ein Sample entnommen, während die kleinere Kategorie komplett erhalten bleibt.
Abbildung 32: Dictionary: Daten einlesen und verteilen
99
Mit diesen Daten wird nun der eigentliche Algorithmus begonnen. Ausgehend von
einem positiven („good“) und einem negativen („bad“) Seed werden nun die Bewertungen auf häufig vorkommende Adjektive durchsucht. Dazu wird für jedes positive
Review geprüft, ob es das Wort „good“ enthält und für jedes negative Review, ob es
das Wort „bad“ enthält. Alle Bewertungen in denen dies der Fall ist, enthalten potentielle Kandidaten zur Erweiterung der Seed-Liste und werden deswegen weiter
untersucht. Es werden alle Adjektive, die nicht auf eine Negation folgen, extrahiert.
Die Negationsliste ist dabei starr vorgegeben und enthält die Wörter {"not", "isnt",
"doesnt", "isn't", "doesn't", "hasnt", "hasn't", "dont", "don't", "havent", "haven't"}. Für
jedes ausgesuchte Adjektiv wird die Häufigkeit des Vorkommens in positiven und
in negativen Reviews festgehalten. Die 5 häufigsten Adjektive jeder Seite werden in
die Seed-Liste übernommen und der Algorithmus kann erneut starten.
Bei der Implementierung in Spark wurden RDDs und RDD-Funktionen genutzt. Zunächst werden Reviews mit der in Abbildung 32 gezeigten Funktion in einzelne
Wörter geteilt und so gefiltert, dass nur Bewertungen, die Seeds enthalten weiterverarbeitet werden (Abbildung 33 und 34).
Abbildung 33: Dictionary: Filter
Abbildung 34: Dictionary: Filtern von positiven Reviews
100
Anschließend werden erneut mithilfe der map() und filter() Funktion alle Adjektive,
die nicht auf eine Negation folgen, extrahiert, wie auf den Abbildungen 35 und 36
zu sehen ist.
Abbildung 35: Dictionary: Filtern von Negation und POS-Tags
Abbildung 36: Dictionary: Funktionen zur Filterung
Auf die beiden RDDs, die nun vermutlich positive und vermutlich negative Adjektive
enthalten, wird die reduceByKey()-Funktion so angewandt, dass für jedes Adjektiv
ein Tupel bestehend aus (Adjektiv, Anzahl) entsteht. Dabei werden für positive Adjektive positive Zahlen hoch gezählt (2mal „good“ -> (good, 2)), während für negative Adjektive negative Zahlen runtergezählt werden (2mal „bad“ -> (bad, -2).
Abbildung 37: Dictionary: Berechnung der Wortanzahl
Am Schluss werden beide RDDs per union() zusammengeführt. Dadurch kann es
nun vorkommen, dass es zwei Tupel mit dem gleichen Adjektiv gibt, da sie sowohl
in positiven als auch in negativen Reviews vorkamen. Eine zweite Anwendung des
reduceByKey() zieht nun die Anzahl der gleichen negativen Adjektive von den gleichen positiven Adjektiven ab.
101
Abbildung 38: Dictionary: Abgleich positiver und negativer Wörter
Dadurch haben nun Adjektive, die häufig in negativen Reviews vorkamen, eine
möglichst niedrige negative Zahl, während positive Adjektive eine hohe positive Anzahl aufweisen. Adjektive, deren Anzahl näher zu 0 liegt, kamen entweder generell
selten, oder häufig in positiven und negativen Reviews vor. In beiden Fällen kann
keine Aussage über ihre Orientierung getroffen werden. Um diese Adjektive auszuschließen, werden nun nur die 5 höchsten und niedrigsten Adjektive extrahiert.
Abbildung 39: Dictionary: Erweiterung der Seeds
Anschließend wird der Algorithmus erneut mit der erweiterten Seed-Liste durchgeführt. Die so gefundenen positiven und negativen Adjektive sollten anschließend
manuell geprüft werden.
Der gesamte Quellcode ist dieser Arbeit ist digitale Anlage beigelegt.
4.2.4
Bewertung
Der Algorithmus ist in der Lage, häufig genutzte Adjektive zu finden. Allerdings werden auch nicht geeignete Wörter gefunden. Eine Liste der ersten 50 positiven und
negativen gefundenen Wörter befindet sich im Anhang B. An dieser Stelle sollen
einmal die ersten Iterationsrunden der Kategorie „Electronics“ diskutiert werden.
102
Runde
neu positiv
neu negativ
Seed
good
bad
1
great, other, easy, small, nice
defective, horrible, terrible, poor,
unusable
2
many, cable, few, new, little
awful, told, unacceptable, disappointing, unreliable
3
old, only, big, happy, able
unable, tech, useless, dissapointed, technician
Tabelle 25: Dictionary: gefundene Adjektive
Wie in Tabelle 25 zu erkennen ist, wurden neben vielen korrekten Wörtern auch
nicht unbedingt korrekte Wörter gefunden. So ist „other“ nicht generell positiv.
„Cable“ und „technician“ sind keine Adjektive. Das heißt, dass einigen Wörtern nicht
die richtige Wortart zugeordnet wurde. Es fällt positiv auf, dass domänenspezifische
Wörter wie „tech“ und später „technical“ gefunden werden.
Der Algorithmus könnte in einer weiteren Implementierungsphase durch mehrere
Maßnahmen verbessert werden. Zum einen können die relevanten Wortarten ausgeweitet werden. Wie in Kapitel 2.2.4.5 beschrieben, kommen auch Substantive als
Stimmungswörter in Frage. Darüber hinaus können vergleichende Verben („/jjs“,
„jjr“) mit einbezogen werden. Dabei muss allerdings eine genauere Prüfung der Relevanz erfolgen, da „besser“ nicht gut sein muss. Auch die Behandlung der Negation
kann flexbiler gestaltet werden. Des Weiteren sollten semantische Regeln zur Prüfung von Stimmungswörtern genutzt werden. Die einfachen Beispiele in Englisch
sind hierfür die „and“, „or“, „neither“, „nor“. Wenn beispielsweise ein „and“ auf ein
Stimmungswort folgt, ist das darauffolgende oftmals auch ein Stimmungswort mit
der gleichen Orientierung. Diese Regeln können mit anderen Mustern auch über
Satzgrenzen hinweg genutzt werden.
103
104
Schlussbemerkungen und Ausb
5
Schlussbemerkungen und Ausblick
Diese Arbeit hat einen Einblick in das Forschungsgebiet der Sentiment Analyse, das
maschinelle Lernen und die Arbeit mit Apache Spark gegeben. Anfangs wurden die
Kernkonzepte der Sentiment Analyse beschrieben. Dennoch gibt es Bereiche, wie
die Meinungszusammenfassung, Meinungsbeschaffung und SPAM-Filterung, die
nicht abgedeckt werden konnten. Die Sentiment Analyse wird aufgrund der Wichtigkeit von Meinung und der hohen Datenverfügbarkeit durch das Web 2.0 auch in
Zukunft ein wichtiger Forschungsbereich bleiben.
Das gleiche gilt auch für das maschinelle Lernen. Generierung von Wissen aus Daten weiterhin ein relevantes Thema bleiben und durch verbesserte und billigere
Technologie voranschreiten.
Ebenso wie die vorgestellten Forschungsbereiche wird auch das Framework
Apache Spark weiterhin relevant sein. In dieser Arbeit wurde die Architektur von
Spark erläutert und Performancetests auf einem Cluster durchgeführt. Im Ergebnis
dieser Tests blieb Spark anfangs hinter den Erwartungen zurück. Die Performance
konnte allerdings noch durch Anpassung diverser Parameter verbessert werden.
Die Ergebnisse dieser Tests sollten grundlegendes Wissen über die Arbeit mit der
Plattform vermitteln und somit einen guten Einstiegspunkt für neuer Benutzer von
Spark bieten. Des Weiteren wurde ein einfacher Algorithmus zur Sentiment Lexikon
Generation implementiert. Mit ihm ist es möglich, korpusbasierte positive und negative Adjektive zu finden. Dabei sind die einzelnen Schritte der Implementierung beschrieben worden, so dass sich der Algorithmus auf dieser Basis erweitern lässt.
105
Literaturverzeichnis
6
[1] L. Zhang und B. Liu, „Extracting and Ranking Product Features in Opinion Documents.,“ in
Proceedings of the 23rd International Conference on Computational Linguistics (COLING2010), Beijing, 2010.
[2] M. Zaharia, R. Xin, J. Rosen, M. J. Franklin, S. Shenker und I. Stoica, „Shark: SQL and Rich
Analytics at Scale,“ in Proceedings of the 2012 ACM SIGMOD International Conference on
Management of Data, New York, 2013.
[3] M. Zaharia, R. Xin, A. Lupher, C. Engle, M. J. Franklin, S. Shenker und I. Stoica, „Shark: Fast
Data Analysis Using Coarse-grained Distributed Memory,“ in Proceedings of the 2012 ACM
SIGMOD International Conference on Management of Data, Scottsdale, 2012.
[4] M. Zaharia, M. Chowdhury, T. Das, A. Dave, J. Ma, M. McCauley, M. J. Franklin, S. Shenker und
I. Stoica, „Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster
Computing,“ in Proceedings of the 9th USENIX Symposium on Networked Systems Design and
Implementation, San Jose, 2012.
[5] T. Zagibalov und J. Carroll, „Automatic Seed Word Selection for Unsupervised Sentiment
Classification of Chinese Text,“ in Proceedings of the 22nd International Conference on
Computational Linguistics (Coling 2008), Manchester, 2008.
[6] N. Yussupova, D. Bogdanova und M. Boyko, „Applying of Sentiment Analysis for Texts in
Russian Based on Machine Learning Approach,“ in IMMM 2012 : The Second International
Conference on Advances in Information Mining and Management, Venedig, 2012.
[7] K. Yessenov und S. Misailovic, Sentiment Analysis of Movie Review Comments, 2009.
[8] G. Xu, Y. Zhang und L. Li, Web Mining and Social Networking, Springer, 2011.
[9] H. F. Witschel, „Using Decision Trees and Text Mining Techniques for Extending Taxonomies,“
in Proceedings of the Workshop on Learning and Extending Lexical Ontologies by using
Machine Learning OntoML, Bonn, 2005.
[10] J. Wiebe, E. Riloff und T. Wilson, „Learning Subjectivity Nouns using Extraction Pattern
Bootstrapping,“ in Proceedings of the Seventh Conference on Natural Language Learning
(CoNLL-2003), Edmonton, 2003.
VI
[11] W. Wang, H. Xu und X. Huang, „Implicit Feature Detection via a Constrained Topic Model and
SVM,“ in Proceedings of the 2013 Conference on Empirical Methods in Natural Language
Processing, Seattle, 2013.
[12] P. D. Turney, „Thumbs Up or Thumbs Down? Semantic Orientation Applied to Unsupervised
Classification of Reviews,“ in Proceedings of the 40th Annual Meeting of the Association for
Computational Linguistics (ACL), Philadelphia, 2002.
[13] I. Steinwart und A. Christmann, Support Vector Machines, New York: Springer, 2008.
[14] R. Socher, A. Perelygin, J. Wu, J. Chuang, C. Manning, A. Ng und C. Potts, „Recursive Deep
Models for Semantic Compositionality Over a Sentiment Treebank,“ in Proceedings of the
Conference on Empirical Methods in Natural Language Processing, Seattle, 2013.
[15] F. Sebastiani, „Machine Learning in Automated Text Categorization,“ ACM Computing Surveys
Vol. 34, pp. 1-47, März 2002.
[16] S. Schrauwen, „Machine Learning Approaches to Sentiment Analysis using the Durch Netlog
Corpus,“ Clips CTRS, Juli 2010.
[17] K. Schouten und F. Frasincar, „Implicit Feature Detection for Sentiment Analysis,“ in
Proceedings of the International World Wide Web Conference, Seoul, 2014.
[18] K. Schouten und F. Frasincar, „Finding Implicit Features in Consumer Reviews for Sentiment
Analysis,“ in Proceedings of the International Conference on Web Engineering, Toulouse,
2014.
[19] B. Santorini, M. P. Marcus und M. A. Marcinkiewicz, „Building a Large Annotated Corpus of
English: The Penn Treebanl,“ Computational Linguistics - Special issue on using large corpora:
II, pp. 313-330, Juni 1993.
[20] B. Santorini, Part-of-Speech Tagging Guidelines for the Penn Treebank Project, 1990.
[21] E. Riloff, A. Qadir, P. Surve, L. De Silva, N. Gilbert und R. Huang, „Sarcasm as Contrast between
a Positive Sentiment and Negative Situation,“ in Proceedings of the 2013 Conference on
Empirical Methods in Natural Language Processing, Seattle, 2013.
[22] E. Riloff, J. Wiebe und W. Phillips, „Exploiting Subjectivity Classifcation to Improve Information
Extraction,“ in Proceedings of the 20th National Conference on Artificial Intelligence (AAAI05), Pittsburgh, 2005.
VII
[23] R. Remus, „Improving Sentence-level Subjectivity Classification through Readability
Measurement,“ in Proceedings of the 18th International Nordic Conference of Computational
Linguistics (NODALIDA), 2011.
[24] G. Qiu, L. Bing, J. Bu und C. Chun, „Expanding Domain Sentiment Lexicon through Double
Propagation,“ in Proceedings of the 21st International Joint Conference on Artificial
Intelligence (IJCAI-09), Pasadena, Kalifornien, 2009.
[25] B. Pang, L. Lee und S. Vaithyanathan, „Thumbs up? Sentiment Classification using Machine
Learning Techniques,“ in Proceedings of the Conference on Empirical Methods in Natural
Language Processing , Philadephia, 2002.
[26] B. Pang und L. Lee, „Opinion mining and sentiment analysis,“ in Foundations and Trends in
Information Retrieval, Boston, James Finlay, 2008, pp. 1-135.
[27] R. Narayanan, B. Liu und A. Choudhary, „ Sentiment Analysis of Conditional Sentences,“ in
Proceedings of Conference on Empirical Methods in Natural Language Processing (EMNLP-09),
Singapore, 2009.
[28] J.-C. Na, H. Sui, C. Khoo, S. Chan und Y. Zhou, „Effectiveness of simple linguistic processing in
automatic sentiment classification of product reviews,“ in Knowledge Organization and the
Global Information Society: Proceedings of the Eighth International ISKO Conference,
Würzburg, 2004.
[29] N. Mishra und C. Jha, „Classification of Opinion Mining Techniques,“ International Journal of
Computer Applications, Oktober 2012.
[30] B. Liu, Web DataMining, Berlin: Springer, 2007.
[31] B. Liu, „Sentiment Analysis: A Multifaceted Problem,“ IEEE Intelligent Systems, pp. 76-80,
2010.
[32] B. Liu, „Sentiment Analysis and Subjectivity,“ in Handbook of Natural Language Processing,
Chapman & Hall, 2010.
[33] B. Liu, Sentiment Analysis and Opinion Mining, Morgan & Claypool Publisher, 2012.
[34] K. Latha und A. Sujitha, „Real-Time Twitter Sentiment Classification Using Unsupervised
Reviews,“ International Journal of Emerging Technology and Advanced Engineering, Mai
2014.
VIII
[35] S.-M. Kim und E. Hovy, „Determining the Sentiment of Opinions,“ in Proceedings of the
COLING conference, Genf, 2004.
[36] A. Kamal, „Subjectivity Classification using Machine Learning Techniques for Mining FeatureOpinion Pairs from Web Opinion Sources,“ International Journal of Computer Science Issues
(IJCSI), September 2013.
[37] J. Jotheeswaran und Y. Kumaraswamy, „Opinion Mining using decision tree based feature
selection through Manhattan hierachical cluster mesaure,“ Journal of Theoretical and Applied
Information Technology, 10 Dezember 2013.
[38] T. Joachims, „Text Categorization with Support Vector Machines: Learning with Many
Relevant Features,“ in Proceedings of the European Conference on Machine Learning (ECML),
1998.
[39] N. Jindal und B. Liu, „Mining Comprative Sentences and Relations,“ in Proceedings of 21st
National Conference on Artificial Intellgience (AAAI-2006), Boston, 2006.
[40] N. Jindal und B. Liu, „Identifying Comparative Sentences in Text Documents,“ in Proceedings
of the 29th Annual International ACM SIGIR Conference on Research & Development on
Information Retrieval (SIGIR-06), Seattle, 2006.
[41] X. Hu, J. Tang, H. Gao und H. Liu, „Unsupervised Sentiment Analysis with Emotional Signals,“
in Proceedings of the 22nd International World Wide Web Conference (WWW), Rio, 2013.
[42] M. Hu und B. Liu, „Mining Opinion Features in Customer Reviews,“ in Proceedings of Nineteeth
National Conference on Artificial Intellgience (AAAI-2004), San Jose, 2004.
[43] M. Hu und B. Liu, „Mining and Summarizing Customer Reviews,“ in Proceedings of the ACM
SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD-2004, full
paper), Seattle, 2010.
[44] D. E. Holmes und L. C. Jain, Data Mining: Foundations and Intelligent Paradigms Volume 2,
Heidelberg: Springer, 2012.
[45] D. E. Holmes und L. C. Jain, Data Mining: Foundations and Intelligent Paradigms Volume 1,
Heidelberg: Springer, 2012.
[46] R. Hausser, Computational Linguistics and Talking Robots, Heidelberg: Springer, 2011.
[47] J. Fischer, Support Vector Machines (SVM), 2007.
IX
[48] F. Fieber, M. Huhn und B. Rumpe, „FB Informatik Universität Braunschweig,“ 31 5 2008.
[Online]. Available: http://www.sse-tubs.de/publications/FHR08.pdf.
[49] J. Ecktstein, Agile Softwareentwicklung mit verteilten Teams, dPunkt Verlag, 2009.
[50] J. Dean, Big Data, Data Mining and Machine Learning, Wiley, 2014.
[51] D. Davidov, O. Tsur und A. Rappoport, „Semi-Supervised Recognition of Sarcastic Sentences
in Twitter and Amazon,“ in Proceedings of the Fourteenth Conference on Computational
Natural Language Learning, Uppsala, 2010.
[52] D. Davidov und A. Rappoport, „Efficient Unsupervised Discovery of Word Categories Using
Symmetric Patterns and High Frequency Words,“ in Proceedings of the 21st International
Conference on Computational Linguistics and 44th Annual Meeting of the ACL,, Sydney, 2006.
[53] E. Cambria, B. Schuller, Y. Xia und C. Havasi, „New Avenues in Opinion Mining and Sentiment
Analysis,“ IEE Intelligent Systems, 2013.
[54] J. Broß, Aspect-Oriented Sentiment Analysis of Customer Reviews Using Distant Supervision
Techniques, Berlin, 2013.
[55] S. Brody und N. Diakopoulos, „Cooooooooooooooollllllllllllll!!!!!!!!!!!!!! Using Word
Lengthening to Detect Sentiment in Microblogs,“ in Proceedings of the Conference on
Empirical Methods on Natural Language Processing, Edinburgh, 2011.
[56] M. Bramer, Principles of Data Mining, Springer, 2007.
[57] S. Blair-Goldensohn, K. Hannan, R. McDonald, T. Neylon, G. A. Reis und J. Reyna, „Building a
sentiment summarizer for local service reviews,“ in Building a sentiment summarizer for local
service reviews, Peking, 2008.
[58] S. Bird, E. Klein und E. Loper, Natural Language Processing, Sebastapol: O’Reilly Media, 2009.
[59] A. Bagheri, M. Saraee und F. de Jong, „Latent Dirichlet Markov allocation for sentiment
analysis,“ in Proceedings of the Fifth European Conference on Intelligent Management
Systems in Operations, Salford, 2013.
[60] A. Bagheri, M. Saraee und F. de Jong, „An Unsupervised Aspect Detection Model for
Sentiment Analysis of Reviews,“ in Natural Language Processing and Information Systems,
Salford, Springer, 2013, pp. 140-151.
[61] C. C. Aggarwal und C. Zhai, Mining Text Data, Springer, 2012.
X
[62] A. Abbasi, H. Chen und A. Salem, „Sentiment Analysis in Multiple Languages: Feature Selection
for Opinion Classification in Web Forums,“ ACM Transactions on Information Systems, 2008.
[63] V. Hatzivassiloglou und K. R. McKeown, „Predicting the semantic orientation of adjectives,“ in
Proceedings of the 35th Annual Meeting of the Association for Computational Linguistics and
Eighth Conference of the European Chapter of the Association for Computational Linguistics ,
Stroudsburg, 1997.
[64] D. R. Rice und C. Zorn, „Corpus-Based Dictionaries for Sentiment Analysis of Specialized
Vocabularies,“ in Proceedings of the New Directions in Analyzing Text as Data Workshop,
London, 2013.
[65] A. Neviarouskaya, H. Prendinger und M. Ishizuka, „Recognition of Affect, Judgment, and
Appreciation in Text,“ in Proceedings of the 23rd International Conference on Computational
Linguistics (COLING 2010), Peking, 2010.
[66] Z. Hai, K. Chang und J. Kim, „Implicit Feature Identification via Co-occurrence Association Rule
Mining,“ in Proceedings of the 12th International Conference on Computational Linguistics
and Intelligent Text processing (CICLing 2011), 2011.
[67] A. Valitutti, C. Strapparava und O. Stock, „Developing affective lexical resources,“
PsychNology Hournal, pp. 61-83, 2004.
[68] N. Godbole, M. Srinivasaiah und S. Skiena, „Large-Scale Sentiment Analysis for News and
Blogs,“ in International Conference on Weblogs and Social Media, Boulder, 2007.
[69] J. Rothfels und J. Tibshirani, „Unsupervised sentiment classification of English movie reviews
using automatic selection of positive and negative sentiment items,“ 2 Juni 2010. [Online].
Available: http://nlp.stanford.edu/courses/cs224n/2010/reports/rothfels-jtibs.pdf. [Zugriff
am 12 Februar 2015].
[70] L. Bottou, „Large-Scale Machine Learning with Stochastic Gradient Descent,“ in Proceedings
of the 19th International Conference on Computational Statistics (COMPSTAT'2010), Paris,
2010.
[71] R. Bekkerman, M. Bilenko und J. Langford, Scaling up Machine Learning, Cambridge:
Cambridge University Press, 2012.
[72] X. Meng, „Sparse data support in MLlib,“ in Spark Summit 2014, San Francisco, 2014.
XI
[73] M. Zaharia, M. Chowhury, M. J. Frankling, S. Shenker und I. Stoica, „Spark: Cluster computing
with working sets,“ in Proceedings of the 2nd USENIX conference on Hot Topics in Cloud
Computing, Berkeley, 2010.
[74] S. Matsumoto, H. Takamura und M. Okumura, „Sentiment Classification Using Word Subsequences and Dependency Sub-trees,“ in Advances in Knowledge Discovery and Data Mining,
Heidelberg, Springer, 2005, pp. 301-311.
[75] H. Karau, A. Konwinski, P. Wendell und M. Zaharia, Learning Spark, Sebastpol: O'Reilly Media
Inc, 2015.
[76] J. McAuley und J. Leskovc, „Hidden Factors and Hidden Topics: Understanding Rating
Dimensions with Review Text,“ in Proceedings of the 7th ACM conference on Recommender
systems, New York, 2013.
[77] P. Wendell, „Understanding the Performance of Spark Applications,“ 12 Dezember 2013.
[Online]. Available: https://www.youtube.com/watch?v=NXp3oJHNM7E. [Zugriff am 13 März
2015].
[78] M. Zaharia, „The State of Spark, and Where We're Going Next,“ 12 Dezember 2013. [Online].
Available: https://www.youtube.com/watch?v=nU6vO2EJAb4. [Zugriff am 05 März 2015].
[79] A. Davidson, „A Deeper Understanding of Spark Internals,“ 17 Juli 2014. [Online]. Available:
https://www.youtube.com/watch?v=dmL0N3qfSc8. [Zugriff am 13 März 2015].
[80] S. Ryza, „Apache Spark Resource Management and YARN App Models,“ 30 Mai 2014. [Online].
Available:
http://blog.cloudera.com/blog/2014/05/apache-spark-resource-managementand-yarn-app-models/. [Zugriff am 25 Februar 2015].
[81] Apache Spark Foundation, „Spark Programming Guide,“ [Online]. Available:
http://spark.apache.org/docs/1.2.0/programming-guide.html. [Zugriff am 25 Februar 2015].
[82] C. D. Manning, P. Raghavan und H. Schütze, An Introduction to Information Retrieval,
Cambrigde: Cambridge Universitry Press, 2009.
XII
Anhang
Anhang
A
Code der Spark Sentiment Klassifikation
XIII
Anhang
B
Dictionary
Positive Adjektive
Good, great, other, easy, small, nice, many, cable, few, new, little, old, only, big,
happy, able, much, high, digital, clear, music, light, extra, comfortable, long, large,
worth, simple, low, expensive, perfect, full, top, sure, portable, such, solid, fantastic, heavy, manual, sharp, wonderful, available, fast, standard, free, quick, optical, glad, overall, useful
Negative Adjektive
bad, defective, horrible, terrible, poor, unusable, awful, told, unacceptable, disappointing, unreliable, unable, tech, useless, disappointed, technician, technical, impossible, later, d-link, static, dead, refurbished, ridiculous, website, hold, stupid,
e-mail, stuck, lousy, blurry, lucky, third, sad, worthless, slow, same, sudden, sorry,
english, unhappy, next, exact, positive, common, site, drive, second, first, major,
weak
XIV
Eidesstattliche Versicherung
Ich versichere hiermit, dass ich die vorliegende Masterthesis selbstständig und ohne
fremde Hilfe angefertigt und keine andere als die angegebene Literatur benutzt
habe. Alle von anderen Autoren wörtlich übernommenen Stellen wie auch die sich
an die Gedankengänge anderer Autoren eng anlehnenden Ausführungen meiner
Arbeit sind besonders gekennzeichnet. Diese Arbeit wurde bisher in gleicher oder
ähnlicher Form keiner anderen Prüfungsbehörde vorgelegt und auch nicht veröffentlicht.
Berlin, den 16. März 2015

Master-Arbeit - Hochschule für Technik und Wirtschaft Berlin

Transcrição

Documentos relacionados

Inhalt - VC Magazin

exit - Tilo`s Bike-Shop

Kawasaki Z800

Sentiment Trading News - BWL I

NGK Spark Plug will Zündkerzenproduktion bis 2020 um 30

deutsch/englisch

NGK Spark Plug Europe: Persis Personalmanager

NGK Spark Plug Europe veröffentlicht neuen Katalog für Boots

NGK Spark Plug Europe holt Marc Kuntzsch als General Manager

Die Hamburger Schreibprobe