Soft clustering algorithms : theoretical and practical improvements

In dieser Arbeit betrachten wir zwei Soft-Clustering Methoden: Fuzzy K-Means Clustering und modellbasiertes Clustering mittels Gaußmixturen. Im Gegensatz zum populären K-Means Clustering gibt es für diese beiden Ansätze kaum Algorithmen, die Garantien für die Güte der berechneten Clusterings bieten. Im ersten Teil der Arbeit präsentieren wir die allerersten Approximationsalgorithmen für das Fuzzy K-Means Problem: Wir zeigen, dass die sogenannte Superset-Sampling Technik auf das Fuzzy K-Means Problem angewendet werden kann. Darüber hinaus zeigen wir, dass sich eine Kernmenge für das Fuzzy K-Means Problem berechnen lässt. Wir nutzen diese Kernmengen-Konstruktion auch, um einen weiteren Approximationsalgorithmus für das Fuzzy K-Means Problem herzuleiten. Darüber hinaus betrachten wir verschiedene Varianten des Fuzzy K-Means Problems und verallgemeinern all diese Ergebnisse. Der zweite Teil dieser Arbeit dreht sich um den modellbasierten Clustering Ansatz, genauer gesagt, die Maximum-Likelihood-Methode für das Schätzen von Gaußmixturen. Als erstes vergleichen wir den klassischen Expectation-Maximization Algorithmus mit einer seiner randomisierten Varianten. Zweitens beschäftigen wir uns mit dem Problem, eine vernünftige initiale Lösung für den Expectation-Maximization Algorithmus für Gaußmixturen zu finden. Wir präsentieren zwei neue Initialisierungsmethoden und versuchen damit die Lücke zwischen den einfachen, aber eher unzuverlässigen Methoden und komplizierten Methoden, deren Qualität stark von den gewählten Hyperparametern abhängt, zu schließen. Drittens analysieren wir einen Spezialfall des Problems, der auch schlicht als das Soft-Clustering Problem bekannt ist.In this thesis, we study two soft clustering approaches: fuzzy K-means clustering and model-based clustering with Gaussian mixture models. In contrast to the popular K-means hard clustering, there are hardly any algorithms for these approaches that provide guarantees on the quality of the computed clusterings. In the first part of this thesis, we present the very first approximation algorithms for the fuzzy K-means problem: We show how the so-called superset sampling technique can be applied to compute an approximation for the fuzzy K-means problem. Moreover, we show that there is a refined version of a coreset construction for the K-means problem that yields a coreset for the fuzzy K-means problem. Furthermore, we use this construction to derive another approximation algorithm for the fuzzy K-means problem. Finally, we also consider alternative notions of fuzziness and generalize all of our results to a large class of soft clustering problems. In the second part of this thesis, we consider a model-based clustering approach, namely, the method of maximum likelihood for estimating Gaussian mixture models. Our contribution is threefold: First, we compare two popular heuristics with one another, namely the expectation-maximization algorithm and a stochastic variant thereof. Second, we tackle the problem of initializing the expectation-maximization algorithm. We propose two new initialization methods. Thereby, we aim to close the gap between simple, but rather unreliable, methods and complex methods, whose performance crucially depends on the right choice of hyperparameters. Third, we initiate the theoretical analysis of a constrained version of the maximum likelihood estimation problem, which is known as the soft K-means problem.Kathrin Bujna ; [accepted at the recommendation of Prof. Dr. Johannes Blömer (Paderborn University) and Prof. Dr. Eyke Hüllermeier (Paderborn University)]Tag der Verteidigung: 04.10.2017Universität Paderborn, Dissertation, 201