Abgeschlossene Diplomarbeit: Erweiterte NMF-Algorithmen für XML-Clustering

Betreuer

Bearbeiter

Ilya Neustroev

Abgabetermin

2006-01

Formalia

Voraussetzungen

Vorlesung Informationssysteme oder Information Retrieval
Gute Programmierfähigkeiten
Erfahrung mit Matlab (wünschenswert)

Aufgabenstellung

Clustering ist das automatische Aufteilen von Daten in Gruppen mit dem Ziel, dass Daten aus derselben Gruppe untereinander möglichst ähnlich, Daten aus unterschiedlichen Gruppen dagegen möglichst unähnlich seien. Für das Clustering von Textdaten zeigte unter anderem NMF (non-negative matrix factorization, [Xu/etal:03] , [Shahnaz/etal:04] ) gute Ergebnisse. Dabei wird davon ausgegangen, dass sich jedes Dokument zu unterschiedlichen Anteilen aus mehreren Themen zusammensetzt. Deswegen wird die Matrix der Term-Dokument-Frequenzen so faktorisiert, dass sich jedes Dokument als Linearkombination von positiven Term-Frequenz-Vektoren mit ebenfalls positiven Faktoren darstellen lässt. Die Vektoren sollen dabei anschaulich den Themen in der Kollektion entsprechen, ihre Faktoren dem Anteil der jeweiligen Themen im Dokument.

Im Fall von semistrukturierten, baumartigen Dokumenten wie z.B. XML-Daten kann neben dem textuellen Inhalt auch die Struktur wichtig für die Gruppierung sein. Um vorhandene Matrix-basierte, faktorisierende Algorithmen auf solche Daten anzuwenden, müssen neben den Termhäufigkeiten daher auch noch strukturelle Eigenschaften berücksichtigt werden.

In dieser Diplomarbeit sollen Möglichkeiten untersucht werden, um NMF auf inhaltliche und strukturelle Eigenschaften von XML-Dokumenten anzuwenden. Die Arbeit umfasst daher folgende Aufgaben:

Aufarbeitung der Literatur zu NMF-Algorithmen
Entwicklung und Implementierung von erschiedenen Erweiterungsmöglichkeiten von NMF für die zusätzliche Berücksichtigung von Strukturinformationen beim Clustering von XML-Daten
Evaluierung der implementierten Algorithmen auf verschiedenen Testkollektionen

Fertiger Text

Ilya Neustroev (2006).: Erweiterte NMF-Algorithmen für XML-Clustering. Masterthesis

Literatur

Wei Xu; Xin Liu; Yihong Gong (2003).: Document clustering based on non-negative matrix factorization. In SIGIR:03
Farial Shahnaz; Michael W. Berry; Paul Pauca; Robert Plemmons (2004).: Document Clustering using Nonnegative Matrix Factorization. Journal on Information Processing & Management 42(2)