Alexander Hinneburg

Density-Based Clustering in large Databases using Projections and Visualizations

Dissertation zur Erlangung des akademischen Grades doctor rerum naturalium (Dr. rer. nat.) vorgelegt an der Mathematisch-Naturwissenschaftlich-Technischen Fakultät der Martin-Luther-Universität Halle-Wittenberg
verteidigt am 19.12.2002

Abstract
In dieser Arbeit wurde ein Rahmen-System für Clusteranalyse entwickelt, daß Cluster-Primitive für verschiedene Aufgabenstellungen bereit hält. Alle Cluster-Primitive basieren auf Dichteschätzung, die von der eigentlichen Clusteranalyse getrennt wurde. Diese Trennung führte zu Algorithmen mit geringerer Laufzeitkomplexität. Um hoch-dimensionale Daten zu bearbeiten, wurde ein neuer Algorithmus vorgeschlagen, der Cluster in verschiedenen Projektionen des hoch-dimensionalen Datenraumes finden kann. Der neue Algorithmus kann Cluster finden, die von anderen bekannten Verfahren nicht gefunden werden können. Zum Abschluss wurde das HD-Eye-System entwickelt, das automatische Verfahren mit Visualisierungstechniken verknüpft, um dem Nutzer eine bessere Grundlage für seine Entscheidungen zu liefern und um das Verständnis und die Einschätzung der Ergebnisse zu erleichtern. In zukünftigen Arbeiten kann der Algorithmus zum Finden von Clustern in Projektionen erweitert werden, um auch Cluster mit abhängigen Attributen zu finden. In diesem Rahmen gibt es auch Potential zur Entwicklung neuer Visualisierungstechniken.

In the thesis we propose a new framework for clustering based on primitives for different clustering schemes. Our ideas is that the primitives are based on density estimation, which is a separated task from cluster analysis. This separation leads to new algorithms with lower run time complexity as previous published ones. To handle high dimensional data we proposed a new algorithm which determines clusters in different projections of the high dimensional data space. We demonstrate that the new algorithms finds clusters, which are missed by known projected clustering methods. Finally we describe an interactive visual clustering system, called HD-Eye, which combines automated clustering algorithms with novel visualization techniques. This combination provides the analyst a good basis for data exploration and improves her/his understanding of the results. In future work we will exploit extensions of our projected clustering algorithm to find also clusters with dependent attributes. There is also potential for the development of advanced visualization techniques.

Keywords:
Cluster Analyse, Dichteschätzung, Data Mining, Datenbanken, hochdimensionale Daten, Informationsvisualisierung

Cluster Analysis, Density Estimation, Data Mining, Databases, high dimensional Data, Information Visualization

Online-Dokument im PDF-Format (3.769 KB) mit integrierter Gliederung.

Inhaltsverzeichnis
Contents (1-2)
1 Introduction (3-6)
2 Related Work (7-16)
3 A Clustering Framework based on Primitives (17-44)
4 Clustering in Projected Spaces (45-76)
5 Clustering & Visualization (77-88)
6 Conclusions (89-90)
Bibliography (91-96)