Theoretische Untersuchung praxisrelevanter Fragestellungen der Clusteranalyse

• Antragstellerinnen / Antragsteller: Professor Dr. Heiko Röglin; Professorin Dr. Melanie Schmidt
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2019 bis 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 416767905

Das Forschungsgebiet der Clusteranalyse beschäftigt sich mit der Suche nach unbekannten Strukturen in Daten. Das Ziel ist es, in den Daten versteckte Cluster zu finden, also Untergruppen zusammengehöriger Datenpunkte. Clustering wurde aufgrund seiner vielen Anwendungen im Bereich der Datenanalyse in einer großen Anzahl von Arbeiten in den unterschiedlichsten Ausprägungen untersucht. Dabei zeigt sich eine typische Diskrepanz zwischen Theorie und Praxis bereits bei der Wahl der Problemstellung. Während in der Theorie kombinatorische Fragestellungen wie zum Beispiel k-median und facility location intensiv untersucht wurden, spielen in praktischen Arbeiten Verfahren für andersartige Probleme eine viel größere Rolle, wie zum Beispiel k-means Clustering oder hierarchisches Clustering. Außerdem treten Probleme nicht notwendigerweise in ihrer Standardformulierung auf, sondern beinhalten zusätzliche Nebenbedingungen.Ziel dieses Projekts ist die theoretische Untersuchung praxisrelevanter Problemstellungen der Clusteranalyse. Dabei interessieren uns sowohl die Approximierbarkeit der Probleme, als auch die Untersuchung beliebter Heuristiken, zum Beispiel über Annahmen über Strukturiertheit der Daten. Wir werden insbesondere die folgenden beiden Themen betrachten.1) Clustering mit Nebenbedingungen:Im ersten Bereich beschäftigen wir uns mit der Frage, wie Nebenbedingungen die Approximierbarkeit von Clusteringproblemen verändern. Beispiele für Nebenbedingungen sind Kapazitäten, untere Schranken, Fairness-Bedingungen und Außreißer. Wir interessieren uns zunächst dafür, Techniken für Approximationsalgorithmen für Clusteringprobleme mit Nebenbedingungen zu entwickeln. Neben besonders guten konstanten Approximationen sollen in diesem Projekt auch beliebte Heuristiken analysiert und praktisch effiziente Approximationsalgorithmen entwickelt werden. Außerdem interessiert uns, wie Nebenbedingungen kombiniert werden können, und inwieweit Clustering mit Nebenbedingungen auch im Datenstrommodell approximierbar ist.2) Hierarchisches Clustering:Der zweite Bereich beschäftigt sich mit hierarchischem Clustering. Statt eines Clusterings für eine feste Clusteranzahl k wird hier eine Clusteringhierarchie berechnet. Obwohl hierarchische Clusterings in Anwendungen eine große Rolle spielen, sind sie theoretisch nicht gut verstanden. Wir möchten hier zum Beispiel die Güte von Greedy-Algorithmen untersuchen, die sehr beliebt, aber kaum theoretisch untersucht sind. Weiterhin möchten wir auch neue Approximationsalgorithmen mit kleinen Gütegarantien entwickeln, da für die meisten Varianten von hierarchischem Clustering keine solchen bekannt sind. Ergänzend dazu werden wir uns mit den Grenzen der Approximierbarkeit beschäftigen. Neben der Analyse anhand klassischer Maße möchten wir außerdem am Entwurf globaler Zielfunktionen für hierarchisches Clustering arbeiten.

• DFG-Verfahren: Sachbeihilfen