Soft-Clustering -- Von Heuristiken zu Approximationsalgorithmen (DFG Sachbeihilfe BL 314/8-1)

Das Problem

Unter einem Clustering versteht man die Partitionierung einer Menge von Objekten in Gruppen, welche als Cluster bezeichnet werden. Die Berechnung eines guten Clusterings ist ein typisches Problem aus dem Bereich des maschinellen Lernens und des Data-Minings, das in zahlreichen Gebieten, wie z.B. der Datenkompression, Bild- und Mustererkennung, und der Signalverarbeitung, Anwendung findet. Eines der bekanntesten partitionierenden Clusteringprobleme ist das sogenannte K-Means Problem. In der Praxis ist es allerdings nicht immer sinnvoll jeden Datenpunkt eindeutig einem Cluster zuzuordnen. Deshalb wird bei sogenannten Soft-Clusterings jeder Datenpunkt zu einem gewissem Grad jedem der Cluster zugeordnet. Eines der bekanntesten Soft-Clustering Probleme ist das Maximum Likelihood Estimation (MLE) Problem bezüglich Mixturmodellen. Ein in der Praxis sehr beliebter Ansatz für dieses Problem ist der Expectation-Maximization (EM) Algorithmus, eine Verallgemeinerung des häufig bezüglich des K-Means Problems eingesetzten Algorithmus von Lloyd. Obwohl er rege Anwendung findet, handelt es sich beim EM Algorithmus um eine Heuristik mit zwei signifikanten Schwachstellen. Zum einen gibt es für die Lösungen, die der EM Algorithmus berechnet, keinerlei Garantien. Zum anderen ist keine obere Schranke für seine Laufzeit bekannt.

Das Ziel

Das zentrale Ziel dieses DFG-Projekts ist, das MLE Problem für Mixturmodelle algorithmisch und komplexitätstheoretisch zu analysieren. Vergleicht man das MLE Problem mit dem gut analysierten K-Means Problem, so stellt man fest, dass es zwei wesentliche, strukturelle Unterschiede zwischen den beiden gibt. Die Zuordnung der Punkte in Form eines Soft-Clustering Problems, und die Kostenfunktion in Form eines Mixturmodells. Unser Ansatz besteht deshalb darin, dass wir uns dem MLE Problem aus zwei Richtungen nähern. Dazu wollen wir verschiedene Varianten "zwischen" dem K-Means und MLE Problem untersuchen. Die Idee ist, dass diese Varianten nicht beide angesprochenen strukturellen Unterschiede zum K-Means Problem aufweisen, sondern jeweils nur einen der beiden. Zu den von uns untersuchten Problemen gehören insbesondere das Fuzzy K-Means Problem und das CMLE Problem. Diese beiden Probleme sind, auch unabhängig von der Rolle die sie in diesem Projekt "zwischen" dem K-Means und dem MLE Problem einnehmen, von großem praktischen Interesse. Es gibt, analog zu Lloyd's Algorithmus und dem EM Algorithmus, Heuristiken, die in der Praxis eingesetzt werden um das Fuzzy K-Means Problem bzw. das CMLE Problem zu lösen. Unser Ziel ist die Entwicklung von Algorithmen, die diese Probleme mit beweisbarer Güte und Laufzeitschranke lösen.Darüber hinaus wollen wir die strukturellen Unterschiede zwischen diesen Problemen und dem K-Means Problem bzw. zwischen ihren optimalen Lösungen analysieren. Die dabei gewonnen Erkenntnisse wollen wir für die algorithmische und komplexitätstheoretische Untersuchung des MLE Problems nutzen.

Publikationen

Coresets for Fuzzy K-Means with Applications
J. Blömer, S. Brauer, K. Bujna, in: 29th International Symposium on Algorithms and Computation  (ISAAC 2018), Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018, pp. 46:1--46:12.
Classification and Approximation of Geometric Location Problems
S. Brauer, Classification and Approximation of Geometric Location Problems, Paderborn, 2019.
A Complexity Theoretical Study of Fuzzy K-Means
J. Blömer, S. Brauer, K. Bujna, ACM Transactions on Algorithms 16 (2020) 1–25.
How well do SEM algorithms imitate EM algorithms? A non-asymptotic analysis for mixture models
J. Blömer, S. Brauer, K. Bujna, D. Kuntze, Advances in Data Analysis and Classification 14 (2020) 147–173.
Alle Publikationen anzeigen