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

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, 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üg\-lich 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 zentrale Ziel dieses 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.

• DFG-Verfahren: Sachbeihilfen