Detailansicht
A unified perception of density for clustering
Ekaterina Kuznetsova
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Informatik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Informatik
Betreuer*in
Claudia Plant
Mitbetreuer*in
Anna Beer
DOI
10.25365/thesis.77850
URN
urn:nbn:at:at-ubw:1-31220.35010.278350-6
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Dichtebasierte Clustering-Algorithmen wie DBSCAN sind hoch effektiv, aber sensitiv gegenüber der Wahl der Parameter, insbesondere des Nachbarschaftsradius (ε) und der minimalen Anzahl benachbarter Punkte zur Bildung eines Clusters (minPts). In dieser Arbeit wird ein Ansatz zur Automatisierung der Parameterabstimmung durch Integration der persistenten Homologie, einer Technik aus der topologischen Datenanalyse, vorgestellt. Die persistente Homologie analysiert topologische Merkmale, wie z. B. verbundene Komponenten und Zyklus, über mehrere räumliche Skalen hinweg und verbessert so die Genauigkeit und Robustheit der Clusterbildung. Die Studie untersucht die Beziehung zwischen dichtebasiertem Clustering und topologischen Strukturen anhand synthetischer Datensätze mit unterschiedlicher Dimensionalität, Dichte und Noise-Anteile. Die Ergebnisse der Experimente zeigen, wie Einsichten aus der persistenten Homologie helfen, optimale Parameterwerte zu identifizieren, indem Clustering-Ergebnisse und die entsprechenden ε-Graphen in verschiedenen Einstellungen analysiert werden. Darüber hinaus wird die Robustheit der Methodik unter unterschiedlichen initialen Bedingungen und in Gegenwart von Rauschen validiert. Die vorgeschlagene Technik verbessert den Prozess der Parameterwahl, sodass DBSCAN und verwandte Algorithmen effektiv auf verschiedenen Datensätzen angewendet werden können. Sie kombiniert topologische Erkenntnisse mit Clustering-Techniken und schafft eine Grundlage für robuste, skalierbare und automatisierte Ansätze zur Analyse komplexer Daten.
Abstract
(Englisch)
Density-based clustering algorithms like DBSCAN are highly effective but sensitive to parameter selection, particularly the neighborhood radius (ε) and the minimum number of neighboring points to form a cluster (minPts). This research introduces an approach to automate parameter tuning by integrating persistent homology, a technique from topological data analysis. Persistent homology analyzes topological features, such as connected components and loops, across multiple spatial scales, improving clustering accuracy and robustness. The study explores the relationship between density-based clustering and topological structures, using synthetic datasets with varying dimensionality, density, and noise levels. The results of the experiments demonstrate how insights from persistent homology can help to identify optimal parameter values by analyzing clustering outcomes and the corresponding ε-graphs across diverse settings. Furthermore, the research validates the robustness of this approach under different initial conditions and in the presence of noise. The proposed technique improves the parameter selection process, allowing \mbox{DBSCAN} and related algorithms to perform effectively on different datasets. It combines topological insights with clustering techniques to provide a foundation for robust, scalable, and automated approaches to complex data analysis.
Schlagwörter
Schlagwörter
(Deutsch)
DBSCAN Persistente Homologie Dichte-Konnektivität Clustering-Algorithmen Parameteroptimierung
Schlagwörter
(Englisch)
DBSCAN Persistent homology Density-connectivity Clustering algorithms Parameter optimization
Autor*innen
Ekaterina Kuznetsova 
Haupttitel (Englisch)
A unified perception of density for clustering
Publikationsjahr
2025
Umfangsangabe
ix, 41 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*in
Claudia Plant
Klassifikation
54 Informatik > 54.00 Informatik. Allgemeines
AC Nummer
AC17457066
Utheses ID
74857
Studienkennzahl
UA | 066 | 921 | |