Archive | Learning Analytics RSS feed for this section

Masterarbeit: Near Copy Detection in large text corpora (ODIN): Optimieren einer MapReduce Jobkette oder Datenstrukturen, Datenstrukturen, Datenstrukturen und an die Algorithmen denken!

29 Jul

Ich habe in letzter Zeit einen Algorithmus zur near copy detection (NCD) in MapReduce für Apache Hadoop implementiert und dabei erst richtig gelernt, was es eigentlich heißt, mit Big Data umzugehen. Ich habe den Algorithmus mittlerweile das dritte mal implementiert und unzählige (> 100) Versionen, in denen immer wieder Optimierungen eingeflossen sind, erstellt. Hier ein kleine Geschichte von Datenstrukturen und Algorithmen und vielen vielen Daten.

Ich teste meinen Algorithmus mit einem Satz von Testdaten, der 230.000 verschiedene Sätze und 124.000 verschiedene Worte umfasst. Der Algorithmus ist eine Implementierung von Fuzzysets, die die Ähnlichkeit zwischen Sätzen berechnen. Der erste Schritt ist für jeden Satz der gegen den Hintergrundkorpus geprüft werden soll einen Liste an Zielsätze zu finden, die eine gewisse Ähnlichkeit zum Quellsatz haben, um nicht den Quellsatz gegen alle Sätze des Korpus prüfen zu müssen. Hierfür baue ich eine Lookuptabelle auf, in der alle Worte auf die Sätze abgebildet sind die sie enthalten, also ein inverser Index. Hiermit können alle Sätze ermittelt werden, die z.B. zumindest ein Wort mit dem Quellsatz gemein haben. Der nächste Schritt umfasst das Holen der Zielsätze und die Berechnung der Ähnlichkeiten zum Quellsatz. Hierfür habe ich eine Tabelle die die Termfrequenzen für alle Sätze enthält. Die Sätze haben als ID einen MD5Hash über die alphabetisch geordnete Menge der Worte des Satzes („Das ist ein Haus und ein Auto“ = MD5Hash (autodaseineinhausistund)). Dies garantiert eindeutige Hashes, da die Anordnung der Worte für Fuzzyset unwichtig ist. Als letzter Schritt sollen die Ergebnisse weggeschrieben werden. Die drei Version des Algroithmuses unterscheiden sich hauptsächlich in der Anzahl und der Funktion der MapReduce Jobs. Waren es in der erst noch drei Jobs, so waren es in der zweiten 9 und in der dritten vier. Die Ausführungszeiten und die Größe der Zwischenergebnisse unterscheiden sich in den drei Versionen drastisch, so variierte die Ausführungszeit auf meinem Testsatz zwischen 2 Stunden in der dritten Version und >16Stunden in der zweiten. Auch die Größe der Zwischenergebnisse variierte drastisch. In der zweiten Version ca. 6Tb und in der dritten <3Gb.

Ein paar Kleinigkeiten die ich schmerzlich gelernt habe stehen unter den Motto „Datenstrukturen, Datenstrukturen, Datenstrukturen und an die Algorithmen denken!“. Einige Beispiele werden im Folgenden näher erläutert:

Datenstrukturen 1
Was der Begriff BigData bedeutet, habe ich festgestellt als ich darüber nachdachte, ob ich ein Integer sparen sollte oder ob ich mir den Luxus gönne. :-) (Ich fühlte mich in die Zeit versetzt als man beim 386er jedes Byte im untern Speicherbereich gespart hat um ein bestimmtes Spiel zu starten können). Hierbei ging es um die Frage, wie ich die md5 Hashes meiner Satzids speichern sollte. Hadoop stellt ein Objekt zur Speicherung von dynamisch langen Bytearrays zur Verfügung (BytesWritable). Nach meiner ersten Implementierung der Kandidatenauswahl hatte ich 3Mrd Vergleiche von Satzpaaren, was sich in 6Mrd. Ids niederschlägt. Das ByteWirtable speichert einen Integerwert für die Länge des Bytearray und das Array an sich. Da die Länge bei md5 aber fix mit 16Byte ist, sind die 4Byte für das Längenint überflüssig. Ein anderes Objekt von Hadoop, MD5HashWritable, speichert nur ein Bytearray, mit der fixen Größe von 16Byte. Das macht 25% Overhead (24Gb) bei 96GB für die ids. Es lohnt sich über die Datenstrukturen nachzudenken, denn ein gespartes Int kann mal schnell drei DVDs ausmachen.

Datenstrukturen 2
Ein weiteres Beispiel, warum es sinnvoll ist, eigene spezielle Datenstrukturen zu verwenden, anstatt von generischen, zeigt sich am Objekt MapWritable von Hadoop. Es ist zwar praktisch ein Objekt zu haben in dem die verschiedensten Writables gespeichert werden können, aber im Fall von sehr vielen kleinen Elementen auch Nachteile mit sich bringen kann. Das MapWritable speichert für jedes Key und Value jedes Elements den Datentyp als fully qualified String. Wenn beispielsweise nur IntWritable’s gespeichert werden sollen, ergibt das einen Overhead von 800% („org.apache.hadoop.io.IntWritable“ = min. 32Byte gegen Integer=4byte). Auch dies kann durch eine spezialisierte Datenstruktur vermieden werden und vermindert die Datenmenge extrem.

Datenstruktutren 3
Die Laufzeit des  Sort and Shuffle Prozess, zwischen Map und Reduce, wird maßgeblich durch die Menge der zu sortierenden Daten dominiert. In einer Version habe ich in der Map Phase die Kandidaten zu einem Quellsatz gesucht und dann die ids von Quell und Zielsatz zu einem 32Byte langen Bytearray kombiniert. Dieses Bytearray habe ich dann als Key zusammen mit einem leeren Value an die Reduce Phase gesendet. Das hat den Vorteil, dass eine totale Ordnung entstand. Der Nachteil bestand darin, dass viel Zeit zum Sortieren benötigt wurde.   Des Weiteren wurde die totale Ordnung auch nicht weiter benötigt. Hierbei werden dann 6Mrd. Elemente sortiert und geshuffelt, dann wird 6Mrd. mal die reduce Methode aufgerufen mit leeren iterable Values. Im Vergleich dazu, wenn nur die Quellid als key und die Zielids als Value zur Reduce Phase übertragen wird, fallen nur ca. 200.000 zu sortierende Elemente an und die reduce Methode wird auch nur 200.000 mal aufgerufen mit gefüllten iterable Values. Das brachte eine enorme Zeitersparnis, die mehrere Stunden umfasste.

Algrithmen
Bei meinem Ansatz hat sich herausgestellt, dass der Random Access auf die Lookupdaten in HBase die meiste Zeit beanspruchte. Hier gilt es noch eine bessere Lösung zu finden. Ich denke hier könnte PIG hilfreich sein. Auch zu große Zwischenergebnisse (Mehrere TByte) oder zu viel Sortierarbeit waren ein großes Hindernis. Schlussendlich kann ich sagen, dass ich aus den vielen Wochen der Optimierungsarbeit viel über die Funktionsweise von MapReduce gelernt habe und für den nächsten Algorithmus eine komplett andere Herangehensweise benutzen würde.

PS.: BigData stimmt bei diesem Artikel auch für die Überschrift.:-)

BA: SALAMI – SociAl Learning Analytics MonItor

28 Mrz

Auch ich schließe mich meinem „Vorredner“ Oliver an und poste hier meine Vortragsfolien meiner Abschlusspräsentation meiner Bachelorarbeit.

Diese Präsentation habe ich am 22.03. im Oberseminar von Professor Magenheim gehalten. Auch ich möchte mich bei allen Anwesenden für die Aufmerksamkeit bedanken.

Ein Großteil meiner Präsentation bestand aus einer Live-Demo des aktuellen Standes meiner Implementierung und ist in den Folien nicht enthalten. Für den ein oder anderen sind die Folien eventuell trotzdem interessant.

Präsentationstermin naht

16 Mrz

Nächste Woche Donnerstag, den 22.03. ist der Termin meiner Abschlusspräsentation meiner Bachelorarbeit SALAMI.
Aktuell befinde ich mich in der kreativen Phase zur Erstellung der Folien für eben diese Präsentation.

Der aktuelle Plan sieht folgenden Ablauf vor:

  1. Zu Beginn leite ich kurz in die gegebene Problematik ein und erläutere warum ein Tool wie SALAMI sinnvoll ist
  2. Anschließend erkläre ich meinen Lösungsansatz und mein Vorgehen bei der Planung der Arbeit
  3. Dann gehe ich auf Beispiele in der durchgeführten Implementierung ein
  4. Darauf folgt die ausgiebige Demonstration des aktuellen Standes der Arbeit
  5. Im Abschluss möchte ich kurz Zusammenfassen und einen Ausblick in die Zukunft des Projektes geben
Ich hoffe, dass meine zeitliche Vorstellung in etwa mit dem geplanten Zeitrahmen übereinstimmt. Dies wird sich in den nächsten Tagen bei einem Testlauf des Vortrags zeigen.

Im Anschluss an die Präsentation werde ich mein Folienpaket natürlich wie üblich auf Slideshare veröffentlichen und hier darüber berichten.

SALAMI: Implementierungsphase ist zu Ende

18 Dez

Seit meinem letzten Beitrag hier ist einiges passiert:
Viele der geforderter Features sind implementiert worden. Das Meiste und Wichtigste funktioniert soweit.
Bei manchen Punkten gab/gibt es unerwartete Probleme mit dem Zusammenspiel von AJAX, POST und GET, aber ich glaube das bekomme ich noch in den Griff.

Vor ein paar Wochen habe ich mir den Masterarbeitvortrag  über den Twapperlyzer angehört und gute Ideen und Quellen sammeln können.
Leider kann vieles aus Zeitmangel nicht mehr in meine BA „SALAMI“  einfließen, denn laut Zeitplan ist die Implementierungsphase bereits beendet und es muss noch einige geschrieben werden für die Arbeit selber.

Im Gegensatz zur längeren Implementierung wird die Evaluation viel kleiner als geplant durchgeführt werden müssen.
Dies resultiert aus mangelnder Aktivität im Social Media Monitoring Seminar an der Uni Augsburg – schade :-(

In den nächsten fünf Wochen heißt es nun Recherchieren, Schreiben, Schreiben und Schreiben.

Auf Los gehts los.

Schon mal ein frohes Fest allen Mitlesern! :) 

Zeitserienvisualisierung mit Cube

7 Dez

Heute bin ich über ein sehr interessantes Projekt zur Visualsierung von Zeitserien gestoßen, dass dazu noch technologisch sehr interessant ist. Cube baut auf Node.js, MongoDB und D3.js auf und erlaubt die schnelle Erzeugung recht ansprechender Visualisierungen, die in verschiedenen Kontexten eingesetzt werden können. Die Entwickler selbst beschreiben Cube als:

an open-source system for visualizing time series data, built on MongoDB, Node and D3. If you send Cube timestamped events (with optional structured data), you can easily build realtime visualizations of aggregate metrics for internal dashboards. Cube speaks WebSockets for low-latency, asynchronous input and output: new events are streamed in, and requested metrics are streamed out as they are computed. (You can also POST events to Cube, if that’s your thing, and collectd integration is included!) Metrics are cached in capped collections, and simple reductions such as sum and max use pyramidal aggregation to improve performance. Visualizations are generated client-side and assembled into dashboards with a few mouse clicks.

Es gibt auch ein typisches „Was kann man cooles in 60 Sekunden mit unserem Tool machen?“ Video, welches tatsächlich nur 31 Sekunden lang ist. Macht schon echt nen coolen Eindruck, oder?