Theoretische Untersuchung praxisrelevanter Fragestellungen der Clusteranalyse
Zusammenfassung der Projektergebnisse
Dieses Projekt gehört zum Bereich der Grundlagenforschung in der Algorithmik. Es geht um den Entwurf praxisrelevanter Approximationsalgorithmen für die Clusteranalyse sowie die Analyse bekannter Clusteringheuristiken. Mit Clusteranalyse werden Daten auf unbekannte Strukturen hin untersucht. Clusteringalgorithmen unterteilen eine gegebene Menge von Objekten automatisiert in Gruppen, sogenannte Cluster. In der theoretischen Algorithmik wird dabei durch eine mathematische Zielfunktion bewertet, wie gut eine Aufteilung in Cluster gelungen ist. Eine solche Zielfunktion kann zum Beispiel der größte Durchmesser oder Radius der Cluster sein, dies modellieren die k-diameter und die k-center Zielfunktion. Probleme wie das k-diameter und k-center Problem sowie verwandte Probleme wie das k-median und k-means Problem sind sowohl theoretisch als auch praktisch bereits sehr gut untersucht. Es gibt insbesondere verschiedene sogenannte Approximationsalgorithmen, die beweisbar gute Lösungen für die genannten Zielfunktionen berechnen. Allerdings treten Clusteringprobleme in der Praxis häufig weniger idealisiert auf, sodass die oben genannten Modellierungen nicht ausreichen. In diesem Projekt wurden praxisrelevante Erweiterungen untersucht. In Teil 1 ging es um die Betrachtung von Nebenbedingungen. Stellen wir uns vor, dass Haushalte in Gruppen unterteilt werden, um die Platzierung von städtischen Kindergärten zu entscheiden. Dann spielt neben der Entfernung der Haushalte zum nächsten Kindergarten auch die Kapazität der Einrichtungen eine Rolle: Die Anzahl der Haushalte, die einem Kindergarten zugewiesen werden, sollte weder zu klein noch zu groß sein. Neben kardinalitätsbasierten Nebenbedingungen haben wir auch Fairnessbedingungen untersucht, bei denen es darum geht, dass alle Cluster hinsichtlich eines sensitiven Attributs fair sind. In Teil 1 wurden Approximationsalgorithmen entworfen und die effiziente praktische Berechnung von Clusterings unter Nebenbedingungen u. a. für große Datenmengen untersucht. In Anwendungen ist es oft bereits eine wesentliche Herausforderung, die Zahl k der Cluster für eine gegebene Datenmenge sinnvoll zu wählen. Theoretische Modelle wie die oben genannten umgehen dieses Problem in der Regel dadurch, dass k als explizit gegeben angenommen wird, was aber oft unrealistisch ist. Hierarchische Clusterings lösen das Problem, indem eine Clusteringhierarchie gesucht wird, die für jedes k ein Clustering mit k Clustern enthält. Obwohl hierarchische Clusterings in Anwendungen eine große Rolle spielen, sind sie theoretisch nicht gut verstanden. Unser Ziel in Teil 2 war es, das theoretische Verständnis von hierarchischem Clustering zu erweitern, um die Lücke zwischen der Theorie und Praxis in diesem Bereich verkleinern. Wir haben verschiedene Algorithmen zur Berechnung von hierarchischen Clusterings entworfen und analysiert und konnten neue Schranken zeigen, wie gut die Lösungen sind, die diese Algorithmen berechnen.
Projektbezogene Publikationen (Auswahl)
-
Noisy, Greedy and Not so Greedy k-Means++. In: Proceedings of 28th Annual European Symposium on Algorithms (ESA), u Band 173, S. 18:1–18:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
Anup Bhattacharya; Jan Eube; Heiko Röglin & Melanie Schmidt
-
Achieving Anonymity via Weak Lower Bound Constraints for k-Median and k-Means. In: Proceedings of 38th International Symposium on Theoretiu cal Aspects of Computer Science (STACS), S. 7:1–7:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021.
Anna Arutyunova & Melanie Schmidt
-
Coresets for constrained k-median and k-means clustering in low dimensional Euclidean space. CoRR, abs/2106.07319, 2021.
Melanie Schmidt, Julian Wargalla
-
Upper and Lower Bounds for Complete Linkage in General Metric Spaces. In: Proceedings of 24th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), S. 18:1–18:22. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021.
Anna Arutyunova; Anna Großwendt; Heiko Röglin; Melanie Schmidt & Julian Wargalla
-
Applying Graph-based Clustering to Tracklet-Tracklet Correlation. In: Proceedings of the International Astronautical Congress, 2022. ISSN: 0074-1795.
Franziska Griese, Kathrin Rack, Simon Schmitz, Hauke Fiedler, Benjamin Hofmann, Melanie Schmidt, Daniel Schmidt
-
The Price of Hierarchical Clustering. In: Proceedings of 30th Annual European Symposium on Algorithms (ESA), Band 244, S. 10:1–10:14. Schloss Dagstuhl – u Leibniz-Zentrum für Informatik, 2022.
Anna Arutyunova & Heiko Röglin
-
Approximations for Hierarchical and Lower-Bounded Clustering and the Coma plexity of Minimum-Error Triangulation. Dissertation, Rheinische Friedrich-Wilhelms-Universit¨t Bonn, 2023.
Anna Arutyunova
-
How Does Fairness Affect the Complexity of Gerrymandering? In: Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems (AAMAS), S. 2869–2871. ACM, 2023.
Sandip Banerjee; Rajesh Chitnis & Abhiruk Lahiri
-
MRI Scan Synthesis Methods based on Clustering and Pix2Pix. CoRR, abs/2312.05176, 2023.
Giulia Baldini, Melanie Schmidt, Charlotte Zäske, Liliana L. Caldeira
