Abgeschlossene Diplomarbeit: K-Means-Clustering für semistrukturierte Daten

Betreuer

• Dipl.-Inform. Gudrun Fischer
• Prof. Dr.-Ing. Norbert Fuhr

Bearbeiter

• Nebil Nouri

Verwandte Projekte

CYCLADES

Verteilte und kollaborierende Dienste für offene digitale Archive

Abgabetermin

2004-11

Formalia

Voraussetzungen

• Vorlesung Informationssysteme oder Information Retrieval
• Programmiersprache Java

Aufgabenstellung

Das Deep Web ist der Teil des WWW, der für konventionelle Suchmaschinen nur schwer zugänglich ist. Neben nichttextuellen Daten in verschiedenen Medienformaten gehören dazu insbesondere auch generierte Seiten und Daten, die von digitalen Bibliotheken zur Verfügung gestellt werden. Während die Suche im Deep Web seit einigen Jahren Thema wissenschaftlicher Forschung ist, fehlen bislang weitgehend Lösungen für das Browsing, z.B. eine Kategorisierung im Stil von Yahoo oder eine automatische Aufteilung in inhaltlich zusammengehörige Gruppen (Clustering, siehe zum Beispiel [Berkhin:02] ).

K-Means [Hartigan/Wong:79] ist ein Algorithmus zur Aufteilung einer Menge von Daten in eine gegebene Anzahl von Clustern.

Im Rahmen dieser Diplomarbeit soll der K-Means-Algorithmus zum Clustern der Daten einer Deep-Web-Quelle eingesetzt werden. Dabei soll vereinfachend von einer homogenen Kollektion ausgegangen werden, d.h. die Dokumente haben eine weitgehend gleiche Struktur. Pfade, die in allen Dokumenten auftreten, lassen sich dadurch auch als Felder betrachten, und die Dokumente können als flache Feld-Wert-Struktur behandelt werden. Das für die Umsetzung des Algorithmus zu entwickelnde Ähnlichkeitsmaß soll zwei Eigenschaften solcher Daten berücksichtigen: Felder und verschiedene Datentypen.

Die Aufgabe umfaßt insbesondere folgende Punkte:

• Erarbeitung eines State-of-the-Art zum Clustering von semistrukturierten Daten
• Beschreibung und Anpassung von K-Means für das Clustern von semistrukturierten Daten
• Prototypische Implementierung und Auswertung für einen geeigneten Anwendungsfall.

Fertiger Text

Nebil Nouri (2004).

K-Means-Clustering für semistrukturierte Daten. Masterthesis

Literatur

Pavel Berkhin (2002).

Survey Of Clustering Data Mining Techniques. Technischer Bericht, Accrue Software, San Jose, CA

J. A. Hartigan; M. A. Wong (1979).

A K-Means Clustering Algorithm. Applied Statistics 28

A. Doucet; H. Ahonen-Myka (2002).

Naive clustering of a large XML document collection. In INEX:03