Soft-Clustering - From Heuristics To Approximation Algorithms
Final Report Abstract
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.
Publications
- (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.
(See online at 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.
(See online at 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.
(See online at 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.
(See online at https://doi.org/10.1145/3409385)
