Soft clustering algorithms
Kathrin Bujna · Amtliche Mitteilungen (Universitätsbibliothek Paderborn) · 2017
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.