Lehr- und Forschungseinheit für Datenbanksysteme Datenbanksysteme Database Systems

Projektarbeit

Web Document Clustering

Inhalt

Das Internet stellt heutzutage etwa 300 Millionen HTML-Seiten zu Verfügung, deren Anzahl jedoch um 1  Million Seiten pro Tag zunimmt. Diese Flut an Information ist für den einzelnen Benutzer nicht mehr zu beherrschen, was den Einsatz von sogenannten Suchmaschinen zum Finden spezieller Informationen im Web nötig macht. Diese Suchmaschinen indizieren die Seiten im Netz und speichern diese in einer Datenbank. Bei einer Anfrage werden solche Einträge in der Datenbank gesucht die das vom Benutzer angegebene Suchwort enthalten. Die Menge der gefundenen Seiten wird dann als Liste ausgegeben. Das Problem mit dem die Benutzer solcher Suchmaschinen zu kämpfen haben ist die unüberschaubare Anzahl von Treffern und die unstrukturierte Ausgabe der ermittelten Seiten. Die gefundenen Dokumente lassen sich jedoch in den allermeisten Fällen thematisch einteilen. So werden z.B. beim Suchen nach Dokumenten zum Suchbegriff "Clustering" Seiten ermittelt, die thematisch in die drei Bereiche: passen. Eine für den Menschen bessere Ausgabe der Suchergebnisse einer Suchmaschine würde die Treffer hierarchisch so einordnen, dass es für den Benutzer sofort ersichtlich ist, zu welchem thematischen Gebiet das ermittelte Dokument gehört. Somit kann er schneller aus der Treffermenge die für ihn interessanten Seiten herausfinden.
 

Problemstellung

Es sollen die Suchergebnisse einer Anfrage an eine Suchmaschine so hierarchisch "geclustert" werden, dass Seiten die zum selben Themenkomplex gehören in einem Cluster zusammengefasst werden. Um dies realisieren zu können benötigt man zunächst ein Ähnlichkeitsmass das es erlaubt, zu beurteilen wie ähnlich sich zwei Dokumente thematisch sind um sie dann dem richtigen Cluster zuordnen zu können. Dies soll dann dazu verwendet werden die Ausgabe einer Suchmaschine strukturierter und für den Benutzer besser lesbar auszugeben.
 

Lösungsansatz

Die meisten Verfahren um Internetseiten zu clustern beruhen auf dem sogennanten "textbasierten" Clustering. Dabei wird die Ähnlichkeit von Dokumenten, bzw. die thematische Zugehörigkeit zu einen Themenkomplex, allein durch textuellen Vergleich des Inhalts der Seite, evtl. mit einer Anzahl gewisser markanter Begriffe, definiert. Diese Verfahren lassen jedoch oft in der Qualität der Ergebnisse zu wünschen übrig. Ein evtl. besseres Verfahren benutzt expliziet die Struktur von Hypertext-Dokumenten, die aus einzelnen, durch sogenannte Links verbundenen, Seiten bestehen. Die Idee ist dabei, dass die Anzahl der Links zwischen Seiten die zu verschiedenen Themengebieten gehören geringer sein wird als die zwischen themengleichen Dokumenten. Somit kann man die Anzahl der Verbindungen zwischen Seiten zur Definition eines Ähnlichkeitsmasses verwenden und mit dessen Hilfe einen Clustering-Algorithmus implementieren.

Ziel

Tools

Personen

Bearbeiter Florian Beil
Betreuer Dr. Jörg Sander

Arbeitsplan

Arbeitsabschnitt Zeitbedarf
Definition eines Ähnlichkeitsmasses und Auswahl eines geeigneten Clustering-Algorithmus 2 Wochen
Implementierung  5-7 Wochen
Testen der Implementierung und Anwendung auf typische Suchergebnisse 2-3 Wochen

Homepages: homeDBShomeInstituthomeLMU
08.011.1999 Florian Beil