Soft-Clustering - Von Heuristiken zu Approximationsalgorithmen

• Antragsteller: Professor Dr. Johannes Blömer
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2017 bis 2021
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 324506751

• Erstellungsjahr: 2021

Zusammenfassung der Projektergebnisse

Im digitalen Zeitalter entstehen täglich große Datenmengen - Big Data ist allgegenwärtig. Effiziente Werkzeuge zur Analyse solcher Massen an Daten sind wichtiger denn je zuvor. Eine beliebte Technik, auch zur erstmaligen Vorverarbeitung, sind Methoden des unüberwachten Lernens. In diesem Projekt haben wir uns mit einer solchen Technik, dem Clustering, beschäftigt. Clustering besteht aus einer Vielzahl verschiedener Problemstellungen, Modellen und Algorithmen. Die grundlegende Idee ist es, Gruppen ähnlich geformter Elemente zu identifizieren und so (wenige) geeignete Repräsentanten eines großen Datensatzes zu finden. Eine beliebte Zielfunktion aus diesem Bereich ist das Fuzzy k-Means Problem. Gegenüber anderen Problemen zeichnet es sich durch eine vergleichsweise hohe Resilienz gegenüber Ausreißern im Datensatz aus. Aus mathematischer Sicht hat es eine interessante Struktur, die klassische Analysetechniken schnell an ihre Grenzen stoßen lassen. Wir haben das Problem eingehend komplexitätstheoretisch und algorithmisch untersucht. Dabei haben wir einen Algorithmus entworfen, der sich einer optimalen Lösung des Problems beliebig annähert und dies in einer Laufzeit, die unabhängig von der eingegebenen Gewichtung der Datenpunkte ist. In Kombination mit anderen, ebenfalls von uns neu entwickelten Techniken ist es uns gelungen, einen Algorithmus zu formulieren, dessen Laufzeit nah an die Laufzeit der schnellsten Algorithmen für andere beliebte Clustering Probleme heranreicht. Diese positiven, algorithmischen Ergebnisse haben wir durch eine untere Laufzeitschranke eines anderen beliebten Algorithmus für dieses Problem komplementiert. Ein anderes, ebenfalls von uns untersuchtes, Problem ist das sogenannte MLE Problem für Gaußmixturen. Hier haben wir unsere theoretische und empirische Forschung ausgebaut und weiter verbessert.

Projektbezogene Publikationen (Auswahl)

• (2018). Coresets for Fuzzy K-Means with Applications. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany
  Blömer, J., Brauer, S., und Bujna, K.
  (Siehe online unter https://doi.org/10.4230/LIPIcs.ISAAC.2018.46)
• (2019). Classification and approximation of geometric location problems. Dissertation, Paderborn University
  Brauer, S.
  
• (2019). Complexity of single-swap heuristics for metric facility location and related problems. Theoretical Computer Science, 754:88–106
  Brauer, S.
  (Siehe online unter https://doi.org/10.1016/j.tcs.2018.04.048)
• (2019). How well do SEM algorithms imitate EM algorithms? A non-asymptotic analysis for mixture models. Advances in Data Analysis and Classification, 14(1):147–173
  Blömer, J., Brauer, S., Bujna, K., und Kuntze, D.
  (Siehe online unter https://doi.org/10.1007/s11634-019-00366-7)
• (2020). A Complexity Theoretical Study of Fuzzy K-Means. ACM Transactions on Algorithms, 16(4):1–25
  Blömer, J., Brauer, S., und Bujna, K.
  (Siehe online unter https://doi.org/10.1145/3409385)