Erweiterte NMF-Algorithmen für XML-Clustering
Status
Abgeschlossene Diplomarbeit
Bearbeiter
- Ilya Neustroev
Abgabetermin
2006
-
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
Literatur
-
- Wei Xu; Xin Liu; Yihong Gong (2003).
- Document clustering based on non-negative matrix factorization. In Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval
-
- Farial Shahnaz; Michael W. Berry; Paul Pauca; Robert Plemmons (2004).
- Document Clustering using Nonnegative Matrix Factorization. Journal on Information Processing & Managementt 42(2)