Sommer Hausarbeit Keywd
In Abschnitt 1 finden Sie die wichtigsten Informationen und Termine zur Hausarbeit, Abschnitt 2 führt theoretisch in das Hausarbeitsthema ein. Informationen zur von uns bereitgestellten Vorlage finden Sie in Abschnitt 3, bevor in Abschnitt 4 die Anforderungen an Ihre Hausarbeit ausführlicher spezifiziert werden. Abschnitt 5 schließlich gibt Hilfestellungen bei der Bearbeitung der gestellten Aufgabe.
Die Vorlage zur Hausarbeit finden Sie hier (als ZIP, kann als Projekt in Eclipse importiert werden)
Die Hausarbeit besteht aus 4 Anforderungen (s. Details in Abschnitt 4), die für den Scheinerwerb erfüllt werden müssen:
- Implementation des Programms gemäß den Anforderungen dieser Beschreibung, Abgabe auf CD.
- Interne Dokumentation von Klassen, Attributen und Methoden der API mit Javadoc – evtl. ist zusätzliche Dokumentation innerhalb von Methodenkörpern sinnvoll. Die interne Dokumentation muss wie der Code selbst (Bezeichner von Klassen, Methoden, Variablen) auf Englisch abgefasst werden.
- Externe Dokumentation, ausgedruckt, der Form einer wissenschaftlichen Arbeit entsprechend, vgl. Hinweise zur Form. Die Hausarbeit muss auf Deutsch abgefasst werden.
- Sie müssen in der Lage sein, uns den Programmablauf Ihrer Implementation darzulegen, damit wir sichergehen können, dass Sie selbst programmiert haben.
Kennzeichnen Sie CD und Dokumentation mit Ihrem Namen, Ihrer Matrikelnummer sowie Ihrer Email-Adresse. Das Programm kann sich an den Vorschlägen in diesem Dokument orientieren (siehe Abschnitt 5).
Gruppenarbeit ist nicht möglich. Sie sollen mit dieser Arbeit beweisen, dass Sie der Sprache Java mächtig sind und in der Lage sind, Anforderungen wie die hier gestellten eigenständig zu erfüllen. Ähneln sich Implementierungen zu sehr, wird die mündliche Darlegung (s.o., Anforderung 4) umfangreicher ausfallen.
Abgabe: Die Arbeit muss bis spätestens Donnerstag, 15.09.2011, 12 Uhr in der Sprachlichen Informationsverarbeitung abgegeben werden. Achtung: Um sichergehen zu können, dass Sie nicht vor verschlossenen Türen stehen, sollten Sie zur Abgabe nur zu den Geschäftszeiten kommen! Daher auch die Zeitangabe beim spätesten Abgabetermin.
Das Programm muss in einem lauffähigen, funktionalem Zustand vorliegen, andernfalls gilt die Arbeit als nicht bestanden. Sollten einige der weniger relevanten Anforderungen nicht erfüllt sein, so werden Sie (per Email, bitte auf dem Deckblatt der Dokumentation angeben) aufgefordert, die entsprechenden Punkte nachzubessern.
Ihre Aufgabe ist es, ein Programm zur Keyword-Extraktion von Websites zu entwerfen und zu implementieren. Bei der Keyword-Extraktion handelt es sich um eine Form von Informationsextraktion, vgl. etwa Wikipedia zur Terminology Extraction.
Mit der Aufgabenstellung bekommen Sie ein Templating-System ausgeliefert, welche die Aufbereitung der Ergebnisse der Keyword-Extraktion übernimmt (vgl. Abschnitt 3). Ihr Programm muss mit dieser mitgelieferten Template Engine kommunizieren. Selbstverständlich können Sie diese auch erweitern, wenn Sie noch weitere Funktionalitäten realisieren wollen. Führen Sie aber bitte alle Änderungen, die Sie an der Vorlage vornehmen, in der externen Dokumentation auf!
Eine Keyword-Extraktion lässt sich auf viele verschiedene Arten realisieren. Verschiedene Strategien zur Lösung des Problems werden weiter unten dargestellt. Eine Extraktion von Keywords setzt unabhängig vom konkreten Verfahren eine Aufbereitung und Speicherung der textuellen Inhalte voraus, die einen Zugriff auf die Terme der Dokumente ermöglicht.
Ein erster, einfacher Ansatz zur Ermittlung von Keywords eines Dokuments ist die Annahme, dass häufige auftretende Wörter (d.h. Wörter mit einer hohen Termfrequenz) wichtig sind. Ein Problem dabei ist, dass die häufigsten Wörter Funktionswörter sind, die in allen Dokumenten vorkommen. Eine Lösung dieses Problems besteht im Filtern dieser häufigen Wörter bei der Keyword-Extraktion.
Die Vorlage enthält eine Stoppwortliste mit solchen Wörtern in res/stopwords.txt. Teil der Aufgabe ist die Implementierung einer Keyword-Extraktion auf Basis der Termfrequenz tf(t,d), d.h. der Häufigkeit des Terms t im Dokument d, unter Ausschluss der in der Stoppwortliste enthaltenen Wörter.
Selbst mit Stoppwortliste hat die Verwendung der einfachen Termfrequenz ein Problem: Wörter, die insgesamt im Korpus häufig vorkommen, sind keine guten Diskriminatoren für einzelne Dokumente. In einem Korpus über Autos etwa ist zu erwarten, dass in allen Artikeln der Begriff Auto häufig vorkommt, und damit kein gutes Keyword für einzelne Artikel darstellt.
Eine Grundidee ist hier, nur Wörter hoch zu bewerten, die in einem Dokument häufig vorkommen, aber im gesamten Korpus selten vorkommen. Dazu wird zunächst die Dokumentenfrequenz df(t,c) für einen Term ermittelt, d.h. die Anzahl von Dokumenten im Korpus c, in denen der Term t vorkommt.
Ist diese Zahl gering, soll der Term eine hohe Wertung erhalten. Um insgesamt einen hohen Wert für gute Terme zu bekommen, invertieren wir die Dokumentenfrequenz (invertierte Dokumentenfrequenz, idf), indem wir sie durch die Gesamtzahl der Dokumente teilen. Um das Spektrum der Werte zu verringern (d.h. um extrem hohe Werte für sehr niedrige Dokumentenfrequenzen zu verhindern), verwenden wir den Logarithmus der invertierten Dokumentenfrequenz:
Um die Termfrequenz mit der invertierten Dokumentenfrequenz zu kombinieren, multiplizieren wir tf mit idf, und erhalten so den TF-IDF-Wert für einen Term t in einem Dokument d:
Teil der Aufgabe ist die Implementierung einer Keyword-Extraktion auf Basis der beschriebenen TF-IDF-Berechnung. Vergleichen Sie ihre Ergebnisse mit den Ergebnissen der einfachen TF-Extraktion. Für weitergehende Information zur TF-IDF-Berechnung s. Manning et al., Kap. 6.2 (Term frequency and weighting) und Wikipedia (TF-IDF).
Die Vorlage enthält folgende Verzeichnisse:
-
srcenthält den Quellcode der Vorlage. Fügen Sie hier eigene Funktionalität und Tests hinzu. -
libenthält Bibliotheken, die von der Vorlage verwendet werden. -
resenthält Konfigurationsdateien und Templates, die von der Vorlage verwendet werden. -
buildist anfangs leer, enthält nach einem Build die von Ant generierten Dateien; wird durchant cleanundant allgeleert
Sowie die Dateien:
-
build.xmldefiniert den Build-Prozess für Ant (s. Details unten) -
keywd.jarenthält eine ausführbare Referenzimplementierung der Zielfunktionalität. Erzeugt Ergebnisse im Ordnerbuild, vgl. Programmausgabe (ausführbar auf der Kommandozeile überjava -jar keywd.jar, optional kann der absolute Pfad zu einem serialisierten Korpus übergeben werden, s.u.)
Damit Ihre Implementation im Hauptprogramm und in den JUnit-Tests genutzt wird, müssen Sie die Klassen Keywd und KeywdTests so anpassen, dass Instanzen Ihrer Klassen verwendet werden.
Es empfiehlt sich, eigene Tests zu schreiben, um die Funktionalität Ihres Programms besser überprüfen zu können und Fehlfunktionen, die sich evtl. eingeschlichen haben, schnell zu entdecken. Orientieren Sie sich dazu an den Tests im Beispielcode aus dem Semester.
Im Projektverzeichnis befindet sich eine Datei namens build.xml. Dies ist das Build-Skript für Ant, das u.A. Javadocs des Projekts automatisch erzeugt. Ziehen Sie die Datei in Eclipse auf den Ant-View, klappen Sie keywd auf, und Führen Sie einen Doppelklick auf das target doc aus (alternativ können Sie in der Kommandozeile ant doc ausführen). In der Konsole von Eclipse sollte eine Ausgabe erscheinen, die mit BUILD SUCCESSFUL endet.
Wenn Sie mit der Implementierung fertig sind, sollte auch das Ausführen des Default-Targets all in einem erfolgreichen Build enden. Dieses Target kompiliert den Code, führt die Tests aus, generiert Javadoc, und führt schließlich die Klasse Keywd aus. Ein erfolgreicher Build bei Ausführung des all Targets ist eine notwendige Bedingung für die Annahme Ihres Projekts.
Die Vorlage enthält drei Interfaces und eine Klasse, die diese Interfaces verwendet. Aufbau und grundlegendes Zusammenspiel der Entitäten sind im folgenden UML-Diagramm dargestellt:
Eine Template Engine ermöglicht eine komfortable und gut gekapselte Generierung von Text. Im Fall der Vorlage wird HTML generiert, das eine Zusammenfassung und Detailseiten zu den analysierten Dokumenten darstellt. Die Vorlage verwendet die Template-Engine StringTemplate. Die verwendeten Templates finden sich im Ordner res (Dateiendung .st). Zu Details siehe http://www.stringtemplate.org/
In diesem Kapitel finden Sie nähere Informationen zu den Anforderungen an Ihre Hausarbeit.
Ihr Programm muss in der Lage sein, durch Ausführung der Klasse Keywd ein Textkorpus aus Websites zusammenzustellen, dieses mit zwei verschiedenen Keyword-Extraktoren zu analysieren und einen Bericht zu generieren, der mit dem Ergebnis der Referenzimplementierung vergleichbar ist. Speziell bestehen folgende Anforderungen:
- Ihr Programm muss über die definierten Schnittstellen mit der mitgelieferten Template-Engine interagieren. Ihnen steht dabei frei, die Templates weiter auszubauen.
- Ihr Programm darf bis auf die mitgelieferten externen Bibliotheken keine weiteren nutzen. Wenn Sie der Meinung sind, dass Ihr Programm durch die Nutzung bestimmter Bibliotheken gewinnen könnte, können wir nach Rücksprache eine Ausnahmegenehmigung erteilen. Wenden Sie sich dann bitte frühzeitig an uns.
- Zur Extraktion sollen deutsche Online-Texte verwendet werden, z.B. von Zeit- oder Spiegel-Online.
- Die Quelle des Korpus wird in der Datei
res/keywd.propertiesbeschrieben (die Seed-Seiten und die zu verwendende Crawl-Tiefe). Diese Datei muss von ihrem Programm entsprechend eingelesen werden. Eine einfache Verarbeitung solcher Dateien ermöglicht die Klassejava.util.Properties. - Beim Crawling sollen relative Links korrekt verfolgt werden (d.h. auch Links, deren href-Attribute keine vollständigen URLs enthalten sollen verarbeitet werden, z.B.
/politik/artikel.html); dazu müssen Sie eine Form von Normalisierung der relativen Links vornehmen. Beim Crawling sollten Sie zurückhaltend vorgehen, und z.B. ein Crawl-Delay von min. 1 Sekunde verwenden. Wenn das Crawling über den hier geforderten kleinen Rahmen hinausgeht, sollten Sie unbedingt weitere Höflichkeitsregeln befolgen, insbesondere das Robots Exclusion Protocol - Tokenisierung: Mindestvoraussetzung ist die Umsetzung eines einfachen Wortmodells – Wörter sind Abfolgen von Buchstaben, getrennt durch nicht-Buchstaben (vgl. Sitzung zur Vorverarbeitung). Es steht Ihnen natürlich frei, auch solche Dinge wie Abkürzungen, Mailadressen o.ä. als Wörter zu behandeln.
- Die Dokumente des Korpus sollen in sortierter Form vorliegen (z.B. nach ihrem Titel) und das Korpus soll keine doppelten Einträge enthalten.
- Bei der Verarbeitung von Texten müssen Umlaute korrekt dargestellt werden, Ergebnisdateien müssen UTF-8 verwenden.
- Korpus serialisieren und deserialisieren: Um zu vermeiden, dass das Korpus bei jedem Programmstart neu erstellt werden muss, soll es mittels Objektserialisierung persistiert werden, vgl. Object Persistence Made Easy. Entsprechend muss beim Start des Programms überprüft werden, ob evtl. ein serialisiertes Korpus besteht, das eingelesen werden muss.
- Entsprechend der auszuprogrammierenden Teile, die durch die Interfaces
Corpus,DocumentundExtractorsowie die Methodenrümpfe inKeywdvorgegeben sind, muss eine Ermittlung von Text, Termen, Ort und Keywords der verarbeiteten Websites implementiert werden. Sie können selbst entscheiden, wie viele Keywords extrahiert werden, und ob diese Anzahl je nach Ergebnis variiert. DietoStringRepräsentation von Dokumenten muss den Titel des Dokuments enthalten (vgl. Referenzimplementierung). - Zur Kapselung des Extraktionsalgorithmus wird das Interface
Extractorbereitgestellt (eine Form des Strategy-Patterns, das Sie vom Comparator kennen). Sie müssen mindestens zwei Strategien zur Extraktion implementieren: eine Häufigkeitsanalyse inklusive Stoppwortfilter, und eine TF-IDF-Analyse. - Bei der Berechnung von Termfrequenz (TF) und Dokumentenfrequenz (DF) muss ihr Programm in konstanter Zeit ein Ergebnis für diese Teilschritte liefern, damit die Laufzeitkomplexität der Keyword-Extraktion auch für größere Korpora praktikabel bleibt.
Wie über die Interfaces Corpus und Document definiert (Methode toDot), sollen Ihre Implementierungen eine Visualisierung über Graphviz DOT zurückgeben. Diese wird von dem vorgegebenen Templating-System mittels der Google Charts API in eine Darstellung umgewandelt, die automatisch in den generierten Bericht eingefügt wird (vgl. Keywd-Klasse und Ergebnis der Referenzimplementierung). Die Referenzimplementierung etwa stellt für ein Korpus die verwendeten Seed-URLs, die Zahl der eingelesenen Dokumente und die Gesamtzahl der Terme im Korpus dar:
Ein Dokument wird in der Referenzimplementierung als Übersicht der URL, der ausgehenden Links und der Terme des Dokuments visualisiert:
Es steht ihnen frei, eine vergleichbare Visualisierung zu implementieren oder alternative Formen, z.B. für Dokumente die Seite, von der das Dokument verlinkt war, Details zu den weitergehenden Links oder extrahierten Keywords bzw. für das Korpus Details zu Crawl-Tiefe, Struktur des Korpus etc. In jedem Fall muss die Visualisierung eine dynamische Komponente enthalten, d.h. sie muss sich für unterschiedliche Dokumente und Korpora unterscheiden. Studieren Sie zur Erzeugung der DOT-Darstellung den Beispiel-Code aus dem Seminar sowie die DOT-Einführung und die Graphviz-Dokumentation.
Die Klassen der Vorlage sind vollständig mit Javadoc kommentiert. Öffnen Sie die Datei index.html (wählen Sie den Punkt Open With → System Editor im Kontextmenü) im Verzeichnis build/doc nach Ausführen von ant doc (s.o.), um zur Übersicht über die Klassen im Projekt zu gelangen. Sie müssen die von Ihnen angelegten Klassen ebenfalls dokumentieren. Es jedoch nicht notwendig, jede einzelne Methode zu kommentieren – beachten Sie jedoch folgende Anforderungen:
- Jede Methode und jede Variable, die als
publicoderprotectedmarkiert ist, muss dokumentiert werden, inkl. der Parameter (param), Rückgabewerte (return) und Exceptions (throws). - Methoden mit geringerer Sichtbarkeit müssen dokumentiert werden, wenn sich die Funktionalität nicht ohne weiteres erschließt, oder wenn bestimmte Anforderungen an die Parameter gestellt werden (z.B. X darf nicht null sein, String darf keine Leerzeichen enthalten o.ä.).
Die Anforderungen haben zur Folge, dass Sie umso weniger kommentieren müssen, je mehr Klassen, Methoden und Variablen Sie nicht public oder protected deklarieren, und je besser Sie die Namen der Methoden und Variablen wählen. String s muss in jedem Fall dokumentiert werden, String currentWord nicht unbedingt.
Warnungen beim Ant-Build, welche die von Ihnen ausprogrammierten Klassen betreffen, weisen Sie darauf hin, dass Sie im Javadoc-Kommentar obligatorische Elemente vergessen oder leer gelassen haben. Diese Warnungen sollten Sie beherzigen und die Gründe dafür beseitigen. Nach Ausführung des Builds sollte die Dokumentation im Verzeichnis build/doc aktualisiert sein. Neue Javadoc-Kommentare sollten nun ebenso wie neue, von Ihnen erzeugte und kommentierte Klassen in den HTML-Seiten erscheinen.
Die externe Dokumentation soll dazu dienen, die Funktionsweise Ihres Programms, Ihre Lösungsstrategie und die verwendeten Datenstrukturen zu erläutern, sowie das Zusammenspiel der von Ihnen implementierten Klassen zu erklären, und dabei Probleme, Alternativen und Verbesserungsmöglichkeiten zu diskutieren. UML-Diagramme können dabei hilfreich sein. Der Umfang der Dokumentation soll etwa 5-7 Seiten betragen. Für die Formatierung der Dokumentation gelten unsere Hinweise zur Form verbindlich.
Die nachfolgenden Erläuterungen sind lediglich Hinweise, wie das komplexe Problem Keyword-Extraktion angegangen werden kann. Sie können diese Überlegungen einfach ignorieren und ein eigenes Design entwerfen, allerdings müssen Sie die oben (Abschnitt 4) spezifizierten Anforderungen sämtlich erfüllen.
Auch wenn es vielleicht etwas trivial klingt: Überlegen Sie zunächst ohne Computer, stattdessen mit Zettel und Stift, wie Sie das Problem lösen können. Versuchen Sie, das Problem zunächst grob zu umschreiben und versuchen Sie dann, einzelne Teilprobleme darin ausfindig zu machen. Dann können Sie diese Strategie rekursiv auf die Teilprobleme anwenden, bis Sie schließlich feststellen, dass Sie nur eine relativ große Menge von einfachen Problemen lösen müssen.
Es ist kein guter Stil, alle Funktionalität in einer Klasse zu implementieren. Klassen, die mehr als 200 Zeilen Code enthalten, sollten vermieden werden – stattdessen bietet es sich an, Aufgaben aufzuteilen und an Hilfsobjekte zu delegieren. Ähnliches gilt auch für Methoden – hier gilt als Richtwert 15-20 Zeilen, die nicht überschritten werden sollten. Versuchen Sie also auch hier, eine Funktionalität in Teilfunktionen zu zerlegen. Natürlich sind dies lediglich Richtwerte, Sie sollten jedoch versuchen, sich an diesen zu orientieren, Abweichungen zu vermeiden und zu begründen.
Nutzen Sie außerdem die Möglichkeit, eigene Pakete anzulegen und so Ihr Programm weiter zu strukturieren. Beispielsweise bieten sich Pakete an, welche die Komponentenklassen Ihrer Keyword-Extraktion von den Klassen für die Datenstrukturen und -beschaffung trennen.
Eine Keyword-Extraktion besteht im Grunde aus zwei Hauptkomponenten: Der Datenbeschaffung und der eigentlichen Extraktion von Keywords. Die Datenbeschaffung selbst besteht aus dem Einlesen von Daten von Websites, einer Vorverarbeitung und der Speicherung der eingelesenen Daten. Diese Überlegungen könnten etwa zu folgenden Komponenten führen:
| Komponente | Verwendet | Erzeugt |
| Crawler | URL | HTML |
| Parser | HTML | Texte |
| Preprocessor | Texte | Terme |
| Extraction | Terme | Keywords |
Soweit es sinnvoll ist, können Sie gerne auch Lösungen zu im Kurs gestellten Hausaufgaben für die Lösung der Hausarbeit verwenden, oder den zur Verfügung gestellten Beispielcode. Sie sollten sich dabei aber nicht darauf verlassen, dass die Code-Beispiele die Teilanforderungen korrekt erfüllen, sondern diese lediglich als Beispiele betrachten, wie Sie die geforderte Funktionalität grundsätzlich implementieren können.
Wir haben uns bemüht, diese Dokumentation zur Hausarbeit möglichst umfassend zu gestalten. Allein, keine Dokumentation ist perfekt. Wenn Sie daher nach eingehender Lektüre weitere Fragen oder Probleme mit der Vorlage haben sollten, melden Sie sich per Mail an [email protected] oder [email protected] (am schnellsten wird Ihnen wohl geantwortet, wenn Sie an uns beide schreiben). Behalten Sie auch diese Seite im Auge, da hier häufiger gestellte Fragen beantwortet und eventuelle Korrekturen der Vorlage bzw. der Dokumentation veröffentlicht werden.