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

20 Feb
Als weiteren Schritt zur near copy detection habe ich einige Algorithmen zur Textumformung implementiert. Diese Algorithmen dienen zur Vereinfachung der Texte sowie dem leichteren zerlegen in einzelne Fragmente wie Worte, Satzzeichen oder Zahlen. Im folgenden werden die acht Schritte kurz beleuchtet die ich hierzu umgesetzt habe:
  1. Language Detektion: Die Bestimmung der Sprache eines Textes wird von vielen weiteren Komponenten benötigt, da sie zum Beispiel auf Wörterbüchern oder speziell für eine Sprache trainierte maschinellelern Ansätze aufbauen. Die Sprachenbestimmung wird durch die API language-detection durchgeführt, die in der Lage ist 53 verschiedene Sprachen durch ngram Frequenzen zu identifizieren.
  2. Satz- und Tokenbestimmung: Um weitere Strukturen in die Fließtexte zu bekommen müssen Satzgrenzen und die einzelnen Bausteine des Satzes bestimmt werden. Die ist nötig um weitere Algorithmen anwenden zu können die auf Satzebene arbeiten, wie zum Beispiel der Lemmatizer oder Fuzzyset Ähnlichkeitsvergleiche. Die Sätze werden anschließend weiter, in Tokens zerlegt. Hierbei bildet jedes Wort und jedes Satzzeichen ein Token. Dezimalzahlen die mit Komma unterteilt sind werden beachtet und bilden nur ein Token, was wiederum wichtig ist für das Numberremoval. Nach diesem Schritt steht ein Dokumentobjekt zur Verfügung indem jedes Element im „Chunk“ Feld ein Satzbaustein enthält. Außerdem ist das Feld „Sentences“ mit den Startoffsets der Sätze gefüllt. Für diesen Schritt habe ich die Apache OpenNLP API verwand.
Die nächsten Schritte verändern das Documentobjekt nicht mehr direkt sondern erstellen entweder Substitutions- oder Removelist Objekte. Eine Substitutionlist enthält eine Map die als Key einen Offsetwert und als Value einen String beinhaltet der den Orginalstring aus dem Documentobjekt an dem Offset ersetzt. Eine Removelist enthält nur eine Liste an Offsets die aus dem Documentobjekt entfernt werden sollen. Die beiden Objekte werden separat von einander und von dem Documentobjekt gespeichert und ermöglichen so ein freies zusammensetzten von beliebigen Algorithmen.
  1. Lemmatisierung: Hier werden alle Worte eines Textes auf ihre Grundform zurückgeführt. Hierbei werden auch verschiedene Zeitformen beachtet. Also wird das englische Wort „went“ in seine Grundform „go“ zurückgeführt. Dies wird mit der Mate-Tools API bewerkstelligt. Diese API bietet Lemmatisierung für verschiedene Sprachen, hierfür wird auf einen maschinellenlernen Ansatz zurückgegriffen der mit unterschiedlichen trainierten Modellen mit einer Wissensbasis versorgt wird. Die API ist leider relativ langsam sodass, als eine zukünftige Tätigkeit, der Austausch dieser API gegen eine schnellere anstehen sollte. Die erzeugten Lemmata finden in der Synonymfindung eine Rolle und könne auch besser als Stemming in z.B. Wordclouds verwendet werden. Die Ergebnisse aus dem lemmatisieren werden in einer Substitutionlist abgelegt.
  2. Stemming: Ähnlich zum Lemmatisieren wird beim Stemmen versucht Worte auf einen gemeinsame Form zurückzuführen. Diese Form muss dabei aber kein korrektes Wort oder gar die Grundform eines Wortes sein. Das stemmen ist ein algorithmischer Ansatz der mit einen Satz von Umformungsregeln, die Sprachabhängig sind, arbeitet. Es wird keine komplexes Model verwand, was das stemmen um ein vielfaches schneller macht als das lemmatisieren. Die Ergebnisse sind zwar nicht so gut wie beim lemmatisieren können aber trotzdem zu Verallgemeinerung von Texten helfen. Das Stemmen wird mithilfe von der Analyse API von Apache Lucene durchgeführt und die Ergebnisse werden als eine Substitutionlist abgelegt.
  3. Part of speech: Das Erkennen der Satzstellung eines Wortes wird Part of Speech (POS) genannt. Jedem Wort eines Satzes wird hierbei seiner Bedeutung im Satz (Nomen, Verb, Adjektiv, Adverb, Eigennamen …) zugeordnet. Dies geschied mit der Apache OpenNLP API die auch hierbei trainierte Modelle als Input verwendet. Das Ergebnis ist ein Substitutionlist.
  4. Stopwordremoval: Stopworte (der, die, das, und, auf …) tragen nur geringe semantische Bedeutung, weshalb sie für viele Techniken ignoriert werden können. Dies reduziert den Rechenaufwand zum Beispiel bei Ähnlichkeitsberechnungen drastisch. Andere Techniken wie zum Beispiel die near copy detection auf Stopworten benutzt ausschließlich Stopworte. Die Detektion von Stopworten ist sehr einfach, es gibt Listen für sehr viele Sprachen. In Odin werden Liste aus der Analyse API von Apache Lucene benutzt. Das Ergebnis ist ein Removelist.
  5. Numberremoval: Das Entfernen oder austauschen von Zahlen gegen einen einheitlichen Wert, kann das Erkennen von kopierten Stellen vereinfachen. Wenn beim Kopieren von Textpassagen nur Zahlenwerte verändert werden, ergeben sich durch das entfernen oder generalisieren der Zahlen eine höhere Ähnlichkeit der beiden Textpassagen. In einer Substitutionlist werden alle Zahlenwerte eines Dokuments durch einen Stringidentifier „//NumberRemoved\\“ ersetzt.
  6. Symbolremoval: Hier werden alle Satzzeichen, Klammern und alle nicht alphanumerischen Zeichen in eine Removelist eintragen und damit aus dem Dokument entfernt.

Diese Algorithmen wurden alle implementiert und in Map Reduce Jobs für Hadoop verpackt und auf einen Testsatz von PDFs (43.000) ausgeführt. Der nächste Blogeintrag wird ein kleines Benchmark enthalten.

Schreibe einen Kommentar

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s

%d Bloggern gefällt das: