Tag Archives: hadoop

Author disambiguation

9 Jul

Nachdem ich mich lange mit dem Thema sehr schwer getan habe, kann ich nun endlich einen Zwischenstandsbericht abgeben.

Ich schreibe eine Abschlussarbeit zum Thema „Author disambiguation“. In dieser Arbeit geht es darum, aus einer anhand von Metainformationen (in meinem konkreten Fall BibTeX) gegebenen Menge von Dokumenten mit Autorenangaben herauszufiltern, welche genannten Autoren identische bzw. verschiedene Personen sind.

Nachdem ich anfangs eine Menge einschlägiger Artikel gelesen habe, bei denen fast überall externe Referenzdatenbanken (CiteSeer, Google, etc.) zur Entscheidungsfindung eingesetzt wurden – dies bei meiner Arbeit aber von vornherein ausdrücklich ausgeschlossen war – habe ich mich an ein paar – zugegebenermaßen recht naiven – eigenen Ansätzen versucht, die leider schon zu Beginn der Konzeptionsphase scheiterten.

Das in [1] beschriebene Framework motivierte mich dann jedoch neu, so dass ich mich daran machte, eine derartige Implementierung im Rahmen von Hadoop und HBase vorzunehmen und nun erste Ergebnisse präsentieren kann.

Meine derzeitige Testmenge umfasst knapp 25.000 Dokumente mit rund 80.000 Autorennamen. Diese partitioniere ich gemäß Framework in Cluster von Autoren mit (nach der Normalisierung) gleichen Nachnamen und erhalte so rund 23.000 Cluster verschiedenster Größe.  Auf jedem dieser Cluster kann man nun ein Klassifizierungsverfahren einsetzen, das die enthaltenen Autoren nach einem definieriten Ähnlichkeitsmodell gruppiert und so ein plausibles Ergebnis liefert.

Aufgrund der Datenmenge ist eine manuelle Überprüfung des Ergebnisses offensichtlich nicht möglich. Leider fehlt mir auch noch eine Referenzdatenmenge, mit der ich die Korrektheit des Algorithmus überprüfen kann, weshalb ich derzeit die Struktur des Codes etwas verbessere, Laufzeiten optimiere und ein Beurteilungsschema für die Qualität der Berechnung erarbeite.

Das Laufzeitverhalten ist trotz fehlender Optimierung recht beeindruckend für die ungeheure Datenmenge: Mein lokaler Rechner (Dual-Core, 1,8 GHz) benötigt rund 5 Minuten, um die 80.000 Autorennamen zu disambiguieren.

[1] L. Bolikowski, P. J. Dendek. „Towards a flexible author name disambiguation framework“, 2011.

Advertisements
Kurzmitteilung

Masterarbeit: Near Copy Detection in large text corpora (ODIN): Benchmark 2

18 Mrz

Das neue Cluster ist fertig und funktioniert. Wir haben zu unseren bestehenden Cluster von 3XCore2 quad Maschinen und Imhoteps sechs Kernen, um 14 neue Sechskernmaschinen erweitert. Mit den neuen und den alten Maschinen kommen wir also auf 102 Kerne!

Wir haben uns für die neuen Maschinen für AMD FX 6100 Prozessoren entschieden. Dieser taktet seine 6 Kerne mit bis zu 3,3GHz und hat in einer Preis/Leistungsabwägung gut abgeschnitten. Der Prozessor sitzt auf einem Asus M5A88-Mainboard das mit 4X4GB Ram besückt ist.

Damit die Prozessoren auch immer gut mit Daten versorg werden können haben wir uns entschieden jedem Rechner vier Festplatten zu spendieren. Hier haben wir uns für Seagate Barracuda Green 2TB entschieden. Diese sorgen im Clusterverbund für eine gewaltige Bandbreite. So hat sie in einem Schreibtest eine Bandbreite von 830MB/sec (zweifach redundant, also jeder Datenblock wird drei mal geschrieben. Hieraus ergibt sich 2,4GB/sec) ergeben.

Das ganze wurde in T5 Gehäuse von Sharkoon eingebaut. Diese waren recht Preiswert und haben eine gute Kabelführung. Die Stromversorgung übernehmen 400Watt Netzteile von Sharkoon.

Die Rechner des alten Clusters und die neuen Rechner sind mit einen eigenen 1Gbit Switch verbunden.

Insgesamt kommen wir auf :

18 Workernodes
102 Cores (12xCore2 Quad 2,8GHz, 6xIntel Xeon 2,9GHz, 96x AMD FX 6100 3,3GHz)
260GB Ram (3x8GB, 1x12GB, 14x16GB)
115TB HDD (56x2TB, 1x500GB, 9x330GB)

Auf allen Workernodes läuft Ubuntu Server. Das Hadoop Framework wird mit Konfiguration vom Master kopiert und mit Java 1.6 ausgeführt (Ich habe mich hier für java 1.6 entschieden da sich Java 7 in Bezug auf Stringverarbeitung anders verhält).

Neben der Verwendung als Rechencluster, ist es auch sehr dekorativ und nützlich als Heizung an kalten Tagen. :-)

Hier einige Zeiten aus meiner Masterarbeit die ich mit einem Setup von 90 Kernen gemacht habe. Als Testdokumente habe ich 43.000 Paper aus der Computer Science genommen. Diese Paper haben ein Gesamtgröße von knapp 30GB. Auf diesem Datensatz habe ich fünf meiner MapReduce Job ausgeführt, diese haben die unten beschriebenen Funktionen.

PDFToText+Hyphenationremoval+Footer-Headerremoval: 1,35 Sekunden/Core/Dokument | 0,015 Sekunden/Dokument

Sentence+Tokensplitting+POS: 2,34 Sekunden/Core/Dokument | 0,026 Sekunden/Dokument

Lemmatizer: 23,4Sekunden/Core/Dokument | 0,260 Sekunden/Dokument (Der Lemmatizer ist gerade auf deutschen Texten sehr langsam)

Stemmen+Stopword+Numberremoval+Symbolremoval: 0,171 Sekunden/Core/Dokument | 0,0019 Sekunden/Dokument

Wordnet Synonymfindung: 43,2 Sekunden/Core/Dokument | 0,480 Sekunden/Dokument
Kurzmitteilung

Masterarbeit: Near Copy Detection in large text corpora (ODIN): Benchmark

21 Feb

In diesem Blog wollte ich ein paar Zwischenergebnisse des Hadoop Clusters auflisten. Das Cluster besteht momentan aus 4 Workernodes mit insgesamt 18 Cores (4,4,4,6 / Core2 2,8GHz) die alle ungefähr gleich schnell sind. Die Rechner sind mit insgesamt 7 Platten (3,3,3,1) ausgestattet und haben pro Core 2GB Ram. Der Testdatensatz umfasst ca. 43.000 PDFs mit einer gesamt Größe von ca. 27GB. Die aufgelisteten Werte drücken die Bearbeitungszeit eines Dokuments auf einen Core aus, dahinter die Bearbeitungszeit eines Dokuments auf den gesamten Cluster (geteilt durch die Anzahl der Cores).

PDFToText+Hyphenationremoval+Footer-Headerremoval: 0,074 Sekunden/Core/Dokument | 0,00411 Sekunden/Dokument

Sentence+Tokensplitting+POS: 1,828 Sekunden/Core/Dokument | 0,1015 Sekunden/Dokument

Lemmatizer: 11,554 Sekunden/Core/Dokument | 0,64189 Sekunden/Dokument

Stemmen+Stopword+Numberremoval+Symbolremoval: 0,111 Sekunden/Core/Dokument | 0,00617 Sekunden/Dokument

Daraus ergibt sich eine gesamt Zeit von 0,75367 Sekunden pro Dokument. Diese Zeit wird dominiert durch das Lemmatisieren was API-bedingt ist.

Masterarbeit: Near Copy Detection in large text corpora (ODIN): Was bisher geschah! (Hadoop)

1 Feb

Mit der Near copy detection Anwendung sollen großen Mengen an Publikationen untersucht werden können. Um dies zu gewährleisten habe ich mich für Apache Hadoop als Paralellisierungsframework entschieden. Hadoop ist eine Opensource Framework dass das Map Reduce Paradigma von google umsetzt. Hierzu benötigt wird außerdem ein verteiltes Dateisystem das in Form von HDFS ( Hadoop Distributed File System) mitgeliefert wird.

Map-Reduce: Das Map-Reduce Pattern wurde von Google (link) beschrieben, es handelt sich hierbei um eine Methode zur Verarbeitung großer Datenmengen in einem Cluster von Rechnern. Map Reduce verarbeitet die Daten in zwei Hauptschritten (Map und Reduce) die durch einige generische Schritte gekoppelt sind:

  • Map: Die Daten werden von dem Speichermedium eingelesen und in Splits an die Map Prozesse verteilt. Splits sind eine Teilmenge der Daten, zum Beispiel 64MB Blöcke, die an die einzelnen Map Instanzen verteilt werden. Der Map Prozess verarbeit den Split und erzeugt eine Map als Ergebnis. Am Beispiel eines Wordcounts enthält diese Map als Key jedes Wort und als Value das aufkommen des Wortes in diesem Split.
  • Shuffel and Sort: Die ergebniss Mengen werden auf alle Reducer verteilt (Shuffel). Dies kann zum Beispiel mit einer Hashfunktion passieren. Da es wahrscheinlich mehr Mapinstanzen geben wird als Reduceinstanzen bekommt jede Reduceinstance 1 bis #Mapinstanzen viele Ergebnismaps. Diese werden in einen merge Schritt vereinigt und sortiert. Dieser Schritt stell auch sicher das das ein Key nur zu einem bestimmten Reducer kommt,  es ist also ausgeschlossen das zwei Reducer des gleichen Key erhalten.
  • Reduce: Der Reduceschritt bekommt als Eingabe eine Map, also beim Wordcount Beispiel mit den Wörtern als Key und einer Liste über aller Value Ergebnisse der Mapper als Value. Die Reducerinstance kann nun alle values zusammen addieren und erhält die Anzahl eines Wortes der kompletten Eingabedaten.

Durch diese Aufteilung können die behandelten Probleme gut mit der Anzahl der Rechner im Cluster skaliert werden.

HDFS: Das verteile Filesystem von Hadoop ist optimiert auf das ausführen von Map-Reduce-Jobs. Große Files werden in Blocke eingeteilt (Standard 64MB). Dies Blöcke werden über alle Datanodes im System verteilt. Hier durch wird eine hohe Parallelität bei Lesen gewährleistet. Die Datanodes sollten zusammen mit den Rechennodes auf den gleichen Rechnern liegen. Sodass das verarbeiten der Daten möglichst Datenlokal geschieht, also kein Netzwerkverkehr benötigt wird.

Als Testinstance habe ich ein 5 Knoten großes Cluster aufgebaut das in Wolles Büro steht. Dieses Cluster verfügt über einen Masterknoten (Dual Core Pentium 4), vier Rechenknoten (3xquadcore Pentium4 und 6 Cores von Imhotep XEON Pentium4). Die Rechenknoten haben dann insgesamt 18 Cores, 30GB RAM, 2.8TB HDD.

Masterarbeit: Near Copy Detection in large text corpora (ODIN)

10 Jan

Im Rahmen meiner Masterarbeit werde ich ein System zur Detektion ähnlicher Textteile in wissenschaftlichen Arbeiten entwickeln die als Hinweise auf Plagiate dienen können.

Basierend auf einer Einstufung von Benno Stein und Sven Meyer zu Eissen kann man grob die folgenden Fälle einstufen:

NCD Mindmap

Zwei unterschiedliche Arten der Suche sind zu unterscheiden. Intrensische Suche, in der ein Zieldokument untersucht wird ohne ein bestimmtes Quelldokument. Hier können Sprach- und Strukturanalysen durchgeführt werden, die als hinweise auf unterschiedliche Authoren dienen können. Die zweite Suchart ist die suche auf einem hintergrund Korpus. Hier wird das Zieldokument mit den Dokumenten aus dem Korpus als Quelldokument verglichen. Die folgenden Fälle ergeben sich daraus:

  1. Das Detectieren von exacten kopien ist relativ einfach, es werden Wörter von Ziel und Quelldokument verglichen. Wird eine Kette von Worten gefunden die länger ist als ein Grenzwert ist die suche erfolgreich.
  2. In dem Zieldokument wurden die kopierten Teile verändert. Diese Veränderungen können das einfügen oder weglassen von Textstellen, ersetzen von Teilen durch Paraphrasen oder Synonymen oder das umstellen der Sätze sein. Hierfür gibt es verschiedene Methoden diese Strukturänderungen aufzudecken, wie n-gram und stopword-n-gram Analysen Fuzzy IR Analysen oder Desynonymizierung der Texte.
  3. Ohne einen Hintergrund Korpus können Struktur und Sprachanalysen durchgeführt werden, die Hinweise auf unterschiedliche Autoren geben können.
  4. Der schwierigste Fall ist die Analyse von Sprachänderungen, wurden Textteile aus einer anderen Sprache in ein Dokument eingefügt so können diese Textteile über einen Interlinguaindex mit Hilfe von Wordnets Analysiert werden.

Als erster Schritt hin zu diesen Analysemethoden ist das vorbereiten der Texte. Diese Texte liegen häufig in PDF form vor, diese müssen in Text umgewandelt werden und sich verschiedenen Cleaningschritten unterziehen (Entfernen von Worttrennung, entfernen von Headern und Footern). Anschließend werden einigen textunifikationschritte ausgeführt (Sentencedetection, Tokendetection, POS-detection, Lemmatizierung von Worten, Numberremoval, Desynonymizierung).

Der zweite Schritt wird die Umsetzung verschiedener Analysemethoden zum auffinden kopierter textstellen sein.

Die Umsetzung wir mit Hilfe der Apache Hadoop Plattform geschehen. Dies ermögliche eine gute Skalierbarkeit der Komponenten um die Untersuchungen auf einen großen Datenbestand von vielen tausenden PDFs durchzuführen.

Das System wurde ODIN getauft in Bezug auf den höchsten germanischen Gott, der als Gott des Wissens, der Magie, des Krieges und der Toten gilt (wenn ihr wissen wollt, warum dann fragt Wolle) und als Akronym für near cOpy Detection IN large text corpora.