Rapid Automatic Keyword Extraction – RAKE

by

Wie ich bereits in “Erste Versuche in Machine Learning” erwähnt habe, möchte ich mich in der nächsten Zeit mit dem Thema intensiver beschäftigen. Zwar werde ich die Ansätze aus dem Post verwerfen müssen, aber das Grundkonzept bleibt dasselbe. Das genaue Konzept und eine Vorstellung des Projekts mache ich, wenn ich Klarheit über die Zukunft des Projekts habe. Dies hängt derzeit an einigen Faktoren.

Dennoch möchte ich hier meine Gedanken über ein Paper, mit dem ich mich die letzten Tage beschäftigt habe, festhalten. Es handelt sich um “Rapid Automatic Keyword Extraction from individual documents” aus dem Jahre 2010 und ist mittlerweile auch Teil eines Buches1. Auf GitHub habe ich zwei Implementierungen gefunden (vermutlich gibt es noch mehr): RAKE-PHP ist die PHP-Implementierung und RAKE ist in Python geschrieben.

Kerngedanke bei dem Paper ist die Extraktion von Keywords aus einem Dokument. Dabei sind weniger “traditionelle” Machine-Learning-Ansätze gepaart mit Natural Language Processing (NLP) wie das überwachte Lernen, POS-Tagging (POS = Part of Speech) oder statistische Methoden im Vordergrund. RAKE beschreibt sich als “unsupervised”, “domain-independent” und “language-independent” und benötigt kein Training des Modells.

Keyword Extraction mit RAKE

RAKE fokussiert sich auf einzelne Dokumente und nicht ganzen Korpora. Es basiert auf die Beobachtung der Autoren, dass Keywords meistens zusammengesetzt aus mehreren Wörtern sind. Dabei beinhalten Keywords weniger Satzzeichen, Stop Words (oder Stopplisten, mehr dazu später) und anderen Wörtern mit geringer lexikalischer Bedeutung.

Beispiele für Stop Words sind “und”, “oder”, “auf”, “im” und noch viele weitere. Diese kommen i.d.R. viel zu häufig in einem Dokument vor und haben eine allgemeine Bedeutung. Auch sind sie wenig informationsreich bis bedeutungslos. Daher eignen sie sich nicht um den Inhalt eines Dokuments zu erkunden.

“Content Words” sind im Gegensatz zu Stop Words bedeutungsvolle Wörter von Relevanz für den Inhalt des Dokuments.

RAKE in der Praxis

Der Input für RAKE definiert sich wie folgt:

  1. Liste von Stop Words
  2. Liste von Phrasen-Trennzeichen
  3. Liste von Wort-Trennzeichen

Der Ablauf definiert sich wie folgt:

  1. Das Dokument wird in eine Liste von “candidate keywords”2 anhand der Wort-Trennzeichen getrennt.
  2. Die aus (1) resultierende Liste wird nochmals gesplittet, dieses Mal in eine Liste zusammenhängender Wörter getrennt an dem Phrasen-Trennzeichen und den Positionen der Stop Words 3.
  3. Die aus (2) resultierende Liste enthält Keywords mit einem oder mehreren Wörtern. Zusammen mit der Position im Text bilden diese Wörter ein “candidate Keyword”.

Keyword-Score Berechnung

Nachdem Candidate Keywords gefunden sind, muss jedes Keyword beurteilt werden (ein Score muss berechnet werden). Dies möchte ich anhand der Beispiele aus dem Paper demonstrieren. Das Paper verwendet ein typisches Abstract als Input:

Compatibility of systems of linear constraints over the set of natural numbers

Criteria of compatibility of a system of linear Diophantine equations, strict inequations, and nonstrict inequations are considered. Upper bounds for components of a minimal set of solutions and algorithms of construction of minimal generating sets of solutions for all types of systems are given. These criteria and the corresponding algorithms for constructing a minimal supporting set of solutions can be used in solving all the considered types of systems and systems of mixed types.

Aus diesem Abstract sind laut Paper folgende Candidate Keywords extrahiert:

Compatibility – systems – linear constraints – set – natural numbers – Criteria – compatibility – system – linear Diophantine equations – strict inequations – nonstrict inequations – Upper bounds – components – minimal set – solutions – algorithms – minimal generating sets – solutions – systems – criteria – corresponding algorithms – constructing – minimal supporting set – solving – systems – systems

Der Score wird für jedes einzelne Wörter innerhalb der Candidate Keywords berechnet. Der Score für das Keyword ist die Summe aller Scores, die sich in dem Keyword befinden. Zur Berechnung stehen drei Möglichkeiten zur Verfügung, von denen das letztere verwendet wird:

  1. frequency(w) = Häufigkeit des Wortes in dem Candidate Keyword
  2. degree(w) = Anzahl Wörter im Candidate Keyword – 1 + frequency(w)
  3. degree(w) / frequency(w) = degree – frequency ratio

Wichtig ist hier zu beachten, dass einige Wörter in mehreren Keywords vorkommen und somit eine Summe gebildet werden muss. Das Ergebnis für das Wort “linear”, was sowohl in “linear constraints” als auch in “linear Diophantine equations” vorkommt, lautet daher wie folgt:

  1. frequency(linear) = 2
  2. degree(linear) = 5
  3. degree(linear) / frequency(linear) = 2,5

Fazit

Das Paper bietet noch etwas mehr als das bisher aufgeführte. Beispielsweise wird eine Methode beschrieben wie man “adjoining Keywords”, also Keywords wie “axis of evil”, die in sich Stop Words beinhalten, aufspürt und entfernt. Ferner werden Benchmarks gegen Resultate anderer Paper gestellt. Interessant ist auch der Abschnitt “Stoplist Generation”, in der ein Ansatz beschrieben wird, wie man eine Stop Word-Liste erstellt. Im Paper wird in einem Nebensatz aber auch erwähnt, dass diese Stop Words sich i.d.R. nicht ändern und teilweise auch Domain-abhängig sind. Daher werde ich dieses durchaus spannende Kapitel nicht weiter bearbeiten, da im WWW sehr viele Stop Word-Listen in verschiedenen Sprachen vorhanden sind.

Last Update: 16.11.2020 22:05:40. Change Description:

Footnotes

  1. Text Mining: Applications and Theory
  2. siehe Definition von Keywords in der Einleitung
  3. Stop Words werden entfernt