Subspace clustering for complex data

Günnemann, Stephan; Seidl, Thomas

doi:4103

Subspace clustering for complex data = Subspace Clustering für komplexe Daten

Günnemann, Stephan (Author)

2012

Verantwortlichkeitsangabevorgelegt von Stephan Günnemann

ImpressumAachen : Publikationsserver der RWTH Aachen University 2012

UmfangIII, 304, XXVII S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2012

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Seidl, Thomas (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2012-03-15

Online
URN: urn:nbn:de:hbz:82-opus-41038
URL: https://publications.rwth-aachen.de/record/82818/files/4103.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Data Mining (Genormte SW) ; Cluster-Analyse (Genormte SW) ; Cluster <Datenanalyse> (Genormte SW) ; Wissensextraktion (Genormte SW) ; Dichtebasiertes Clusterverfahren (Genormte SW) ; Algorithmus (Genormte SW) ; Netzwerk (Genormte SW) ; Fehlende Daten (Genormte SW) ; Hochdimensionale Daten (Genormte SW) ; Informatik (frei) ; Teilraum Clustering (frei) ; unvollkommene Daten (frei) ; Teilraumprojektion (frei) ; Redundanzentfernung (frei) ; subspace clustering (frei) ; graph mining (frei) ; imperfect data (frei) ; redundancy avoidance (frei)

Thematische Einordnung (Klassifikation)
DDC: 004
ccs: H.2.8 * I.5.3

Kurzfassung
Das gestiegene Potential von Speichertechnologien und Informationssystemen hat die Möglichkeit eröffnet, kostengünstig große Mengen an komplexen Daten zu sammeln. Neben einfachen Beschreibungen von Objekten durch einige wenige Attribute reichen diese Datenquellen von hochdimensionalen Vektorräumen über unvollkommene Daten hin zu Netzwerkdaten. Die Aufgabe des Data Mining ist es, mit Hilfe von automatischen oder semi-automatischen Algorithmen aus diesen Datenquellen bislang unbekannte und nützliche Muster zu extrahieren. In dieser Arbeit betrachten wir die Aufgabe des Clusterings, die darauf abzielt Gruppen von ähnlichen Objekten zu bilden und gleichzeitig unähnliche Objekte zu trennen. Da in heutigen Anwendungen häufig sehr viele Eigenschaften für jedes Objekt gespeichert werden, ist nicht zu erwarten, dass Objekte existieren, die bei Betrachtung der Gesamtheit aller Eigenschaften ähnlich zueinander sind. Vielmehr werden sinnvolle Gruppen nur in Teilräumen des Datenraums gefunden. Als Lösung für dieses Problem wurde das Paradigma des Subspace Clusterings eingeführt, welches automatisch für jede Gruppe von Objekten eine zugehörige Menge relevanter Attribute identifiziert, in welchen die Objekte ähnlich zueinander sind. In dieser Arbeit führen wir neue Methoden für ein effektives Subspace Clustering auf verschiedenen Typen von komplexen Daten ein. Wir untersuchen das Problem der Redundanz in Subspace Clustering-Ergebnissen und schlagen neue Modelle zur Vermeidung dieser Redundanz vor. Da jeder Teilraum eine andere Sicht auf die Daten liefert, können häufig mehrere sinnvolle Gruppierungen der Objekte gefunden werden. Daher führen wir Techniken ein, die nicht auf eine einzige Partitionierung der Objekte eingeschränkt sind sondern mehrere unterschiedliche Gruppierungen finden können. Neben der Lösung dieser Herausforderungen für das Subspace Clustering von vektoriell beschriebenen Daten analysieren wir ferner das Subspace Clustering auf unvollkommenen Daten sowie auf einer Kombination von Netzwerkdaten mit vektoriellen Daten. Wir schlagen integrierte Analysetechniken vor, welche mit Fehlern in den Daten umgehen können und verschiedene Datenquellen simultan analysieren. In experimentellen Untersuchungen zeigen wir die Stärken der neu entwickelten Clustering-Methoden. Insgesamt ermöglichen wir erstmalig die Bestimmung eines sinnvollen Subspace Clustering für diese komplexen Daten.

The increasing potential of storage technologies and information systems has opened the possibility to conveniently and affordably gather large amounts of complex data. Going beyond simple descriptions of objects by some few characteristics, such data sources range from high dimensional vector spaces over imperfect data containing errors to network data describing relations between the objects. Data Mining is the task of extracting previously unknown and useful patterns from such data sources by using automatic or semi-automatic algorithms. In this thesis, we focus on the mining task of clustering, which aims at grouping similar objects while separating dissimilar ones. Since in today's applications usually many characteristics for each object are recorded, one cannot expect to find similar objects by considering all attributes together. In contrast, valuable clusters are hidden in subspace projections of the data. As a general solution to this problem, the paradigm of subspace clustering has been introduced, which aims at automatically determining for each group of objects a set of relevant attributes these objects are similar in. In this thesis, we introduce novel methods for effective subspace clustering on various types of complex data. Our methods tackle major open challenges for clustering in subspace projections. We study the problem of redundancy in subspace clustering results and propose models whose solutions contain only non-redundant and, thus, valuable clusters. Since different subspace projections represent different views on the data, often several groupings of the objects are reasonable. Thus, we propose techniques that are not restricted to a single partitioning of the objects but that enable the detection of multiple clustering solutions. Besides tackling these challenges of subspace clustering for the case of vector data, we study the task of subspace clustering on two further data types: imperfect data and network data in combination with vector data. We propose integrated mining techniques directly handling errors in the data and simultaneously mining different information sources. In thorough experiments, we demonstrate the strengths of our novel clustering approaches. Overall, for the first time, meaningful subspace clustering results can be obtained for these types of complex data.

Fulltext:
PDF