Archiv | Hadoop RSS feed for this section

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.

Werbeanzeigen
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

Masterarbeit: Near Copy Detection in large text corpora (ODIN): Was bisher geschah! (Wordnet;Synonym findung)

27 Feb

In dem nächsten spannenden Teil meiner Blogserie „ODIN! Was bisher geschah!“ widme ich mich dem Desynonymifizieren (entfernen von Synonymen wegen der Aussprache). Oft werden kopierte Textstellen abgewandelt um die Herkunft zu verschleiern. Diese Abwandlungen können sein, dass Umstellen von Sätzen, das Entfernen oder Hinzufügen von Worten, das Ändern von numerischen Werten oder das austauschen von Worten gegen Synonyme. Die letzte Möglichkeit ist Thema diese Blogposts.
Weiterlesen

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! (Text preprocessing)

8 Feb

Die Hauptaufgabe des Systems ist es Wissenschaftlichearbeiten zu verarbeiten und als Hintergrundkorpus für die Suche nach ähnlichen Textstellen zu verwenden. Als Eingabeformat sollen erstmal PDF-Daten herangezogen werden. In weiteren sollen aber auch andere Formate benutzbar sein, wie zum Beispiel ein Wikipediadump, um auch Textstellen aus dieser Quellen identifizieren zu können.

Texte die als PDF-Dateien zur Verfügung stehen haben aber einige Nachteile für die automatisierte Verarbeitung, so müssen nach der Textextraktion noch einige cleaning Schritte vollzogen werden, die ich im folgenden ein wenig Beschreibe:

  1. PDFToText: Den Volltext aus einer PDF-Datei zu extrahieren ist recht einfach. Hierzu gibt es eine Vielzahl an Tools die diese Aufgabe übernehmen können. Ich habe mich für Apache PDFBox entschieden, da diese API in JAVA implementiert ist und ich sie so direkt in Hadoop Map-Reduce Jobs verwenden kann. Mit PDFBox ist es möglich neben den Volltext als ganzes auch seitenweise Text zu extrahieren, auch ist es möglich die Grafiken auf den Seiten und die Seiten als Thumbnails zu extrahieren. Diese Möglichkeiten werden noch nicht benötigt, aber sie sind potenziell verwendbar um auch Kopien der Grafiken zu detektieren.
  2. Speichern der Texte: In der weiteren Verarbeitung können Textstellen entfernt, hinzugefügt oder geändert werden. Ich möchte aber gern die Positionen im Verhältnis zum Ausgangszustand beibehalten. Hierfür habe ich ein Speicherformat entwickelt das mir dies ermöglicht. Dieses Format kann in JSON ausgedrückt werden und sieht dann so aus:{„chunks“: {„0“: „text text“,“10″: „more text“},“pages“: [0,3119,6708],“sentences“: [0,15,33,67],“lines“: [0,100,219,322]}Das Feld „chunks“ beinhaltet hierbei einzelne Textteile, zum Anfang sind das die einzelnen Zeilen des Dokuments. Jeder Chunk ist mit einem Offset versehen das die Zeichenweise Position im Ursprungsdokument angibt. Das Feld „pages“ enthält die Startoffsets der einzelnen Seiten des Dokuments, gleiches gilt für die Felder „sentences“ und „lines“.
  3. Header-Footer-Removal: Die nächsten Cleaningschritte habe ich speziell für die Eigenarten von Printmedien entwickelt, das Entfernen von Header und Footer. Wenn auf zwei oder mehr Seiten die ersten, respektive die letzten Zeilen ähnlich sind wurde eine Kopf- bzw. Fußzeile gefunden. Ähnlich bedeutet hierbei die Textzeilen sind gleich bis auch einen numerischen Part der hoch zählt (also die Seitenzahl). Der Algorithmus beachtet dabei auch unterschiedliche Kopf- oder Fußzeilen in einem zwei seitigen Format.
  4. Hyphenation-Removal: Hier sollen Silbentrennung am Zeilenende entfernt werden. Dafür suche ich ein Bindestrich am Zeilenende, wird einer gefunden wird noch untersucht ob er direkt an einem Wort steht, wenn ja dann wird der Bindestrich entfernt und das erste Wort in der nächsten Zeilen an die neue Position geschoben. Dieser Algorithmus kann Fehler erzeugen, wenn zum Beispiel zusammengesetzte Worte wie „Meier-Schultze-Friese“ über zwei Zeilen getrennt wird, könne Wortkonstruktionen wie „Meier-SchultzeFries“ oder „MeierSchultze-Friese“ entstehen. Dies kann noch mit einer Rechtschreibprüfung abgefangen werden, indem geprüft wird ob das neue Wort korrekt ist. Dies ist aber (noch) nicht implementiert.
Die Ergebnisse aus diesen Schritten werden als JSON in HBASE gespeichert. Hier entspricht eine Zeile einem PDF-Dokument und jede Spalte einen Verarbeitungsschritt. Dementsprechend werden bis jetzt die Spalten „PDF“, „extractedFulltext“, „removeFooter“, „removedFooterAndHeader“ und „fulltext“ das alle ob Beschriebenen Schritte vereint und für die weitere Bearbeitung benutzt wird.