Due to the technological progress over the last decades, today’s scientific and commercial applications are capable of generating, storing, and processing, massive amounts of data sets. This influences the type of data generated, which in turn means that with each data entry dierent aspects are combined and stored into one common database. Often the describing attributes are numeric; we name data with more than a handful attributes (dimensions) high-dimensional. Having to make use of these types of data archives provides new challenges to analysis techniques.



The work of this thesis centers around the question of finding interesting patterns (meaningful information) in high-dimensional data sets. This task is highly challenging because of the so called curse of dimensionality, expressing that when dimensionality increases the data becomes sparse. This phenomena disturbs standard analysis techniques. Automatic techniques have to deal with the data complexity not only increasing their runtime, but also vitiating their computation functions (like distance functions). Moreover, exploring these data sets visually is hindered by the high number of dimensions that have to be displayed on the two dimensional screen space.



This thesis is motivated by the idea that searching for interesting patterns in this kind of data can be done through a mixed approach of automation, visualization, and interaction. The amount of patterns a visualization contains can be measured by so called quality metrics. These automated functions can then filter the high number of high-dimensional visualizations and present to the user a pre-filtered good subset for further investigation. We propose quality metrics for scatterplots and parallel coordinates focusing on dierent user tasks like identifying clusters and correlations. We also evaluate these measures with regard to (1) their ability to identify clusters in a variety of real and synthetic datasets; (2) their correlation with human perception of clusters in scatterplots. A thorough discussion of results follows reflecting the impact on directions for future research.



As quality metrics were developed for a large number of dierent high-dimensional visualization techniques, we present our reflections on how these methods are related to each other and how the approach can be developed further. For this purpose, we provide an overview of approaches that use quality metrics in high-dimensional data visualization and propose a systematization based on a comprehensive literature review.



In high-dimensional data, patterns exist often only in a subset of the dimensions. Subspace clustering techniques aim at finding these subspaces where clusters exist and which might otherwise be hidden if a traditional clustering algorithm is applied. While subspace clustering approaches tackle the sparsity problem in high-dimensional data well, designing eective visualization to help analyzing the clustering result is not trivial. In addition to the cluster membership information, the relevant sets of dimensions and the overlaps of memberships and dimensions need to also be considered. Although, a number of techniques (for example, scatterplots, heat maps, dendrograms, hierarchical parallel coordinates) exist for visualizing traditional clustering results, little research has been done for visualizing subspace clustering results. Moreover, while extensive research has been carried out with regard to designing subspace clustering algorithms, surprisingly little attention has been paid to the developing of eective visualization tools analyzing the clustering result. Appropriate visualization techniques will not only help in monitoring the clustering process but, with special mining techniques, they could also enable the domain expert to guide and even to steer the subspace clustering process to reveal the patterns of interest. To this goal, we envision a concept that combines subspace clustering algorithms and interactive scalable visual exploration techniques. This work includes the task of comparative visualization and feedback guided computation of alternative clusterings.

Bedingt durch den technologischen Fortschritt der letzten Jahrzehnte sind heutige kommerzielle Applikationen in der Lage, riesige Datenmengen zu erzeugen, zu speichern und zu verarbeiten. Diese Entwicklung beeinflusst auch die Natur der erzeugten Daten, d.h. dass für jeden Dateneintrag unterschiedliche Aspekte in der gleichen Datenbank gespeichert werden. Oft sind die beschreibenden Attribute numerisch. Datensätze, die mehr als fünf solcher Attribute (Dimensionen) beinhalten, nenne ich hochdimensional. Der wertbringende Gebrauch solcher Datenarchive bringt neue Herausforderungen an Analysetechniken mit sich.



Die vorliegende Dissertation bearbeitet die Fragestellung, wie interessante Muster (bedeutende Information) in hochdimensionalen Räumen gefunden werden können. Diese Aufgabenstellung ist durch das Problem des Fluches der Dimensionalität äußerst herausfordernd. Dieses Problem besagt, dass Daten im hochdimensionalen Raum spärlich vorkommen. Herkömmliche Analysetechniken werden dadurch beeinträchtigt. Automatische Methoden müssen die Datenkomplexität nicht nur ihre Laufzeit, sondern auch ihre Berechnungsfunktionen (z.B. Distanzfunktionen) betreend, einbeziehen. Außerdem wird die visuelle Exploration dieser Daten durch die Zweidimensionalität der Darstellungen beeinträchtigt.



Diese Dissertation stützt sich auf das Konzept, dass die Suche nach interessanten Mustern in hochdimensionalen Datenmengen mit einem kombinierten Ansatz von automatischen, visuellen und interaktiven Methoden durchgeführt werden kann. Die Ausprägung der Muster einer Visualisierung kann durch sogenannte Qualitätsmaße gemessen werden. Durch diese automatischen Funktionen kann die große Menge an hochdimensionalen Visualisierungen eingegrenzt und dem Benutzer eine ausgewählte Menge zur weiteren Untersuchung zur Verfügung gestellt werden. Ich schlage Qualitätsmaße für Scatterplots und Parallele Koordinaten vor, die sich auf unterschiedliche Aufgaben, wie die Identifikation von Gruppen oder Korrelationen, konzentrieren. Zusätzlich werden diese Techniken bezüglich (1) ihrer Fähigkeit Cluster in unterschiedlichen realen und synthetischen Datensätzen und (2) ihrer Korrelation mit der menschlichen Wahrnehmung untersucht. Der ausführlichen Diskussion dieser Resultate folgen Überlegungen für die zukünftige Forschung.



Da viele verschiedene Qualitätsmaße für eine Reihe weiterer hochdimensionaler Visualisierungen entwickelt wurden, werde ich Vorschläge für deren Vernetzung und Weiterentwicklung vorstellen. Hierfür wird eine Übersicht über die verschiedenen Ansätze erstellt, welcher eine Systematisierung zugrunde liegt, die aufgrund einer umfassenden Literaturauswertung zustande kam.



Im hochdimensionalen Raum existieren manche Muster nur in verschiedenen Unterräumen des Datenraumes. Subspace Clustering Algorithmen wurden entwickelt, um Unterräume zu finden in denen Cluster existieren, die durch traditionelle Clustering Algorithmen nicht gefunden werden würden. Obwohl diese Algorithmen spärlich mit Daten besetzte, hochdimensionale Räume gut explorieren können, ist das Entwickeln von effektiven Visualisierungstechniken, um diese Clusteringresultate zu analysieren, nicht trivial. Zusätzlich zu der Clusterzugehörigkeit von Elementen müssen die relevanten Attributmengen eines Clusters und die Objekt- und Dimensionsüberlappungen von Subspaceclustern dargestellt werden. Auch wenn eine Reihe von Techniken für die Visualisierung von traditionellen Clustering Resultaten existiert (z.B. Scatterplots, Heatmaps, Dendrogramme, hierarchische Parallele Koordinaten) gibt es nur wenige Ansätze, um das Resultat von Subspace Clustering Algorithmen zu visualisieren. Außerdem wurden bisher erstaunlich wenige Ansätze vorgestellt, die eine visuelle Analyse der Subspace Clustering Ergebnisse unterstützen können, obwohl im Bereich der Subspace Clustering Algorithmen viel Forschung betrieben wurde. Angemessene Visualisierungstechniken, die von speziellen Methoden zur Extraktion von Informationen unterstützt werden, würden nicht nur die Nachverfolgung der Clustering Ergebnisse ermöglichen, sondern auch Fachleuten dabei helfen, den Subspace Clustering Prozess so zu steuern, dass relevante Muster zum Vorschein kommen. Dieses Ziel vor Augen stelle ich ein Konzept vor, das Subspace Clustering Algorithmen mit interaktiven skalierbaren Visualisierungen kombiniert. Meine Ansätze widmen sich deshalb der Aufgabe der Visualisierung zum Vergleich von alternativen Clustergruppen, die durch Nutzerfeedback gesteuert werden.