Adaptive exploration of intrinsic data properties for clustering, outlier detection, and dimensionality reduction

Qian, Li (2025): Adaptive exploration of intrinsic data properties for clustering, outlier detection, and dimensionality reduction. Dissertation, LMU München: Fakultät für Mathematik, Informatik und Statistik

Abstract

In the data-driven era, data has become a key element in supporting decision-making, scientific research, and technological innovation. As the scale and complexity of data continue to grow, it becomes increasingly important to extract actionable knowledge from it. Given this background, data mining is essential for discovering interesting patterns from large datasets, especially in unsupervised learning tasks such as clustering, outlier detection, and dimensionality reduction. However, existing methods often face critical challenges, including adapting to diverse and arbitrary data distributions, handling datasets with varying densities, and reducing dependence on dataset-specific parameters. Since each dataset exhibits unique intrinsic properties, such as local density and neighborhood relationships, this thesis focuses on developing an adaptive exploration framework for unsupervised learning by leveraging intrinsic data properties to enhance the adaptability, accuracy, and efficiency of unsupervised learning algorithms. For the clustering task, this thesis proposes the DBADV algorithm. Existing density-based methods, such as DBSCAN, although capable of recognizing clusters of arbitrary shapes and sizes, are ineffective when dealing with density variations. DBADV calculates the local density information of each object using perplexity, which not only reflects the individual properties of each object but also describes the density distribution of clusters and finds the adaptive search range of each object by collecting information from its neighbors. In addition, a new metric is designed to obtain the mutual nearest neighbors of each object to better distinguish objects near the cluster boundaries, significantly improving the clustering accuracy in the presence of noise and outliers. For the outlier detection task, this thesis proposes the ADOD algorithm. Existing proximity-based methods rely on either a globally fixed radius or a fixed number of neighbors as a parameter, both of which are prone to misjudgments when there is significant variation in data density. ADOD uses perplexity to calculate the local scale of each object and dynamically adjusts the neighborhood boundaries based on this scale to adapt to data with varying densities. Meanwhile, ADOD designs a density consistency score that determines the outlier score by calculating the local density difference between an object and its mutual neighbors, effectively identifying outliers that significantly deviate from their surroundings. Additionally, ADOD extends its utility in real-time applications by generalizing to unknown data through comparison with known data. For the dimensionality reduction task, this thesis proposes the DynoGraph algorithm. DynoGraph addresses two main issues of the existing graph-based methods like t-SNE and UMAP: how to construct a good graph and how to maintain the similarity structure of high-dimensional data in low-dimensional space. DynoGraph first develops an adaptive neighborhood graph construction method that accurately captures the intrinsic geometry of the high-dimensional data. Then, for the first time, it introduces a dynamic graph modification process during dimensionality reduction, guaranteeing that the data structure in the low-dimensional space faithfully reflects the high-dimensional data. Moreover, DynoGraph sets an adaptive threshold that is automatically adjusted according to the intrinsic structure of data, thus guiding the insertion and deletion of edges. These adjustments help to update their positions in subsequent embeddings, aligning them with the high-dimensional data. In summary, this thesis demonstrates how three adaptive algorithms can effectively leverage intrinsic data properties to adapt to arbitrary distributions, capture local density, and design self-adaptive parameters, thereby improving the performance of unsupervised learning tasks. This adaptive exploration framework not only enriches the theoretical approaches to data analysis, but also provides new perspectives and effective solutions for handling complex data in real-world scenarios.

Abstract

Im Zeitalter von datengetriebenen Technologien sind Daten zu einem Schlüsselelement geworden, um Entscheidungsfindung, wissenschaftliche Forschung und technologische Innovation zu unterstützen. Mit dem kontinuierlichen Wachstum der Datenmengen und ihrer Komplexität wird es zunehmend wichtiger, verwertbares Wissen aus den Daten zu extrahieren. Vor diesem Hintergrund spielt Data Mining eine entscheidende Rolle bei der Entdeckung interessanter Muster in großen Datensätzen, insbesondere bei Aufgaben des unüberwachten Lernens wie der Clusteranalyse, Ausreißererkennung und Dimensionsreduktion. Bestehende Methoden stehen jedoch oft vor großen Herausforderungen, insbesondere in Anbetracht der Anpassung an vielfältige und beliebige Datenverteilungen, dem Umgang mit Datensätzen unterschiedlicher Dichte und der Reduzierung der Abhängigkeit von datensatzspezifischen Parametern. Da jeder Datensatz einzigartige intrinsische Eigenschaften, wie lokale Dichte und Nachbarschaftsbeziehungen aufweist, konzentriert sich diese Dissertation darauf, ein Rahmenwerk für die adaptive Exploration im Bereich des unüberwachten Lernens zu entwickeln, das diese intrinsischen Eigenschaften nutzt, um die Anpassungsfähigkeit, Genauigkeit und Effizienz von Algorithmen im Kontext des unüberwachten Lernens zu verbessern. Für die Clusteranalyse schlägt diese Dissertation den Algorithmus DBADV vor. Bestehende dichtebasierte Methoden wie DBSCAN, die zwar in der Lage sind, Cluster beliebiger Formen und Größen zu erkennen, sind bei der Handhabung von Dichtevariationen ineffektiv. DBADV berechnet die lokale Dichteinformation jedes Objekts mithilfe der Perplexität, die nicht nur die individuellen Eigenschaften jedes Objekts widerspiegelt, sondern auch die Dichteverteilung der Cluster beschreibt. Dabei wird der adaptive Suchbereich jedes Objekts durch das Sammeln von Informationen seiner Nachbarn ermittelt. Zusätzlich wird eine neue Metrik entwickelt, um die gegenseitigen nächsten Nachbarn jedes Objekts zu bestimmen, was es ermöglicht, Objekte in der Nähe von Clustergrenzen besser zu unterscheiden und die Clustering-Genauigkeit in Situationen erheblich zu verbessern, in denen Rauschen und Ausreißer vorhanden sind. Für die Ausreißererkennung schlägt diese Dissertation den Algorithmus ADOD vor. Bestehende nahebasierte Methoden verlassen sich entweder auf einen global festgelegten Radius oder eine feste Anzahl von Nachbarn als Parameter, die bei signifikanten Variationen in der Datendichte anfällig für Fehlurteile sind. ADOD verwendet Perplexität, um das lokale Ausmaß jedes Objekts zu berechnen, und ermittelt die Nachbarschaftsgrenzen dynamisch auf der Grundlage dieses Ausmaßes, um sich an Daten mit unterschiedlichen Dichten anzupassen. Darüber hinaus entwickelt ADOD eine Dichtekonsistenzbewertung, die den Ausreißerwert durch Berechnung des lokalen Dichteunterschieds zwischen einem Objekt und seinen gegenseitigen Nachbarn bestimmt und so effektiv Ausreißer identifiziert, die erheblich von ihrer Umgebung abweichen. Zusätzlich erweitert ADOD seine Anwendbarkeit in Echtzeitszenarien, indem es unbekannte Daten durch einen Vergleich mit bekannten Daten generalisiert. Für die Dimensionsreduktion schlägt diese Dissertation den Algorithmus DynoGraph vor. DynoGraph adressiert zwei Hauptprobleme bestehender graphenbasierter Methoden wie t-SNE und UMAP: Wie werden qualitativ hochwertige Graphen konstruiert und wie werden Ähnlichkeitsstrukturen hochdimensionaler Daten in einem niedrigdimensionalen Raum beibehalten. DynoGraph entwickelt zunächst eine adaptive Methode zur Konstruktion eines Nachbarschaftsgraphen, die die intrinsische Geometrie hochdimensionaler Daten präzise erfasst. DynoGraph führt erstmals einen anschließenden dynamischen Graphmodifikationsprozess während der Dimensionsreduktion ein, der sicherstellt, dass die Datenstruktur im niedrigdimensionalen Raum die hochdimensionalen Daten originalgetreu widerspiegelt. Darüber hinaus legt DynoGraph einen adaptiven Schwellenwert fest, der automatisch entsprechend der intrinsischen Datenstruktur angepasst wird, um das Einfügen und Löschen von Kanten zu steuern. Diese Anpassungen tragen dazu bei, die Positionen der Daten in den nachfolgenden Einbettungen zu aktualisieren und sie mit den hochdimensionalen Daten in Einklang zu bringen. Zusammenfassend zeigt diese Dissertation, wie drei adaptive Algorithmen die intrinsischen Eigenschaften von Daten effektiv nutzen können, um sich an beliebige Verteilungen anzupassen, lokale Dichte zu erfassen und selbstadaptive Parameter zu entwerfen, wodurch die Leistung bzgl. Aufgaben des unüberwachten Lernens verbessert wird. Dieses Framework für adaptive Exploration bereichert nicht nur die theoretischen Ansätze zur Datenanalyse, sondern bietet auch neue Perspektiven und effektive Lösungen für den Umgang mit komplexen Daten in realen Anwendungen.

• Dokumententyp: Dissertationen (Dissertation, LMU München)
• Keywords: Unsupervised Learning, Graph Construction, Adaptive Neighborhood, Local Density Estimation, Adaptive Parameter Selection
• Themengebiete: 000 Allgemeines, Informatik, Informationswissenschaft ; 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
• Fakultäten: Fakultät für Mathematik, Informatik und Statistik
• Sprache der Hochschulschrift: Englisch
• Datum der mündlichen Prüfung: 27. Mai 2025
• 1. Bericht­erstatter:in: Böhm, Christian