Methods for enhanced exploratory clustering analyses

Abstract

Nowadays, there are several mature approaches for companies and organizations to collect, store and analyze voluminous data. Especially a thorough data analysis is crucial in order to gain new insights from these data, resulting in detailed knowledge, which can be finally exploited to achieve competitive advantages. This thesis focuses on unsupervised clustering analyses as an important problem in data analysis. Clustering is a fundamental primitive used in manifold application domains, such as computer vision, business purposes, biology, and many others. In order to achieve valuable clustering results, parameters of the clustering algorithm have to be set appropriately, which is a tremendous pitfall for previously unseen datasets. To this end, analysts typically perform an exploratory clustering analysis by repeatedly executing the clustering algorithm with varying parameter values until a valuable clustering result is achieved. However, each single execution of the clustering algorithm is time-consuming on large datasets, hence leading to an infeasible exploration process in a reasonable time frame. This thesis proposes novel methods to enhance the overall exploration process for valuable clustering results. Therefore, we focus on (i) technically inexperienced analysts, who require in-depth support to perform exploratory clustering analyses in the first place, as well as on (ii) novice analysts, who lack domain knowledge and therefore suffer from a particular uncertainty regarding promising parameter values, i.e., requiring more time to achieve valuable clustering results. Related work in this area either focuses on methods to automatically conduct an exploratory clustering analysis, or on methods to accelerate the required runtime of a clustering algorithm. Yet, the interdependency between both aspects, a fundamental aspect in exploratory clustering analysis, is out of scope of related work. The proposed methods in this work address this interdependency by investigating characteristics of the overall exploration process, such as large parameter search spaces as they might be defined by novice analysts or the repetitive execution of a clustering algorithm on large datasets. Therefore, crucial additional benefits, like shorter runtimes for exploratory clustering analyses, are achieved, which significantly extend the current state of related work. In our comprehensive evaluations, we unveil the benefits for exploratory clustering analyses. We show that the proposed methods (i) enable technically inexperienced analysts to perform clustering analyses without detailed knowledge about internals of clustering algorithms, as well as (ii) support novice analysts by achieving tremendous runtime savings of up to several orders of magnitude, while gaining even more valuable clustering results in terms of internal characteristics. Concluding, the novel methods proposed in this thesis provide a crucial support for analysts with varying technical experience and domain knowledge. Therefore, the overall exploration process is enhanced, i.e., a valuable clustering result is achieved in a very reasonable time frame, thus significantly outperforming existing approaches for exploratory clustering analyses.

Heutzutage gibt es mehrere ausgereifte Ansätze für Unternehmen und Organisationen zur Erfassung, Speicherung und Analyse großer Datenmengen. Insbesondere eine sorgfältige Datenanalyse ist entscheidend, um aus diesen großen Datenmengen neue Erkenntnisse zu gewinnen, die zu detailliertem Wissen führen, das schließlich bspw. zur Erzielung von Wettbewerbsvorteilen genutzt werden kann. Der Kern dieser Arbeit ist die unüberwachte Clustering-Analyse, welche ein wichtiges Problem der Datenanalyse ist. Das Clustering ist ein grundlegendes Problem in vielen Anwendungsbereichen, wie z.B. für Computer Vision, für diverse Geschäftszwecke, für die Biologie und viele andere. Um wertvolle Clustering-Ergebnisse zu erzielen, müssen die Parameter des Clustering-Algorithmus entsprechend definiert werden, was eine besondere Schwierigkeit für bisher ungesehene Datensätze darstellt. Zu diesem Zweck führen Datenanalysten in der Regel eine explorative Clustering-Analyse durch, indem sie den Clustering-Algorithmus wiederholt mit verschiedenen Parameterwerten ausführen, bis ein wertvolles Clustering-Ergebnis erzielt wird. Jede einzelne Ausführung des Clustering-Algorithmus ist jedoch bei großen Datensätzen zeitaufwendig und führt daher zu einem nicht realisierbaren Explorationsprozess in einem angemessenen Zeitrahmen. In dieser Arbeit werden neue Methoden vorgestellt, welche eine Verbesserung des gesamten Explorationsprozesses für wertvolle Clustering-Ergebnisse ermöglichen. Daher liegt der Schwerpunkt dieser Thesis auf (i) technisch unerfahrenen Analysten, die tiefgreifende Unterstützung benötigen, um explorative Clustering-Analysen überhaupt durchführen zu können, sowie auf (ii) unerfahrenen Analysten, denen umfangreiches Domänenwissen fehlt und die daher unter einer großen Unsicherheit bezüglich vielversprechender Parameterwerte leiden. Folglich benötigen unerfahrene Analysten mehr Zeit, um wertvolle Clustering-Ergebnisse zu erhalten. Verwandte Arbeiten in diesem Bereich konzentrieren sich entweder auf Methoden zur automatischen Durchführung von explorativen Clustering-Analysen oder auf Methoden zur Beschleunigung der erforderlichen Laufzeit eines Clustering-Algorithmus. Die Wechselwirkung zwischen beiden Aspekten, ein grundlegender Aspekt der explorativen Clustering-Analyse, wird bisher von verwandten Arbeiten nicht adressiert. Die in dieser Arbeit vorgeschlagenen Methoden befassen sich mit dieser Wechselwirkung, indem sie Merkmale des gesamten Explorationsprozesses untersuchen, wie z.B. große Parametersuchräume, wie sie von unerfahrenen Analysten definiert werden können oder die wiederholte Ausführung eines Clustering-Algorithmus auf großen Datenmengen. Dadurch werden entscheidende Vorteile, wie z.B. kürzere Laufzeiten für explorative Clustering-Analysen, erreicht, die den aktuellen Stand der Wissenschaft erheblich erweitern. In umfassenden Evaluationen werden Vorteile für die explorative Clustering-Analyse dargestellt. Es wird gezeigt, dass die vorgeschlagenen Methoden (i) es technisch unerfahrenen Analysten ermöglichen, Clustering-Analysen ohne detaillierte Kenntnisse über die inneren Abläufe von Clustering-Algorithmen durchzuführen, sowie (ii) unerfahrene Analysten unterstützen, indem sie enorme Laufzeiteinsparungen von bis zu mehreren Größenordnungen erzielen und gleichzeitig noch wertvollere Clustering-Ergebnisse erzielen. Zusammenfassend lässt sich sagen, dass die in dieser Arbeit vorgestellten Methoden eine grundlegende Unterstützung für Analysten mit unterschiedlichen technischen und domänenrelevanten Kenntnissen darstellen. Dadurch wird der gesamte Explorationsprozess verbessert, sodass ein wertvolles Clustering-Ergebnis in einem angemessenen Zeitrahmen erzielt wird, wodurch bestehende Ansätze für explorative Clustering-Analysen deutlich übertroffen werden.