Clusteranalyse

Unter einem Clustering versteht man die Einteilung einer Menge von Objekten in Gruppen (Cluster), so dass Objekte innerhalb eines Clusters einander ähnlich sind, während sich Objekte in unterschiedlichen Clustern voneinander unterscheiden. Dazu muss man allerdings zunächst einmal festlegen, was mit Ähnlichkeit gemeint ist.
Betrachten wir beispielsweise eine Landkarte. Wenn wir die verzeichneten Orte als unsere Menge von Objekten interpretieren, dann können wir vereinbaren, dass die Ähnlichkeit von Objekten groß ist, wenn die Entfernung zwischen den Orten gering ist. Das Clustering entspricht dann einer Einteilung der Karte in Ballungsgebiete.
Clusteringalgorithmen versuchen möglichst gute Clusterings zu berechnen, d.h. Clusterings mit möglichst geringen Kosten. Es muss also auch eine Kostenfunktion gewählt werden, die die Güte eines berechneten Clusterings bewertet.

k-means

Eines der bekanntesten Clusteringrobleme ist die Einteilung von Datenpunkten in eine festgelegte Anzahl Cluster. Jeder der Cluster besitzt einen eindeutig bestimmten Repräsentanten. Die Kosten des Clusterings bestimmen sich dann durch die Summe der Abstände aller Datenpunkte zu ihrem jeweiligen Repräsentanten. Dabei wird üblicherweise als Abstandsmaß die quadriert Euklidische Distanz, oder allgemeiner Bregman-Divergenzen, verwendet.
Der k-means Algorithmus (Lloyds, 1982) ist eine gegebene Lösung schrittweise zu verbessern und so ein Clustering zu bestimmen, das ein lokales Minimum der Kostenfunktion darstellt. Ein Problem des k-means Algorithmus ist, dass die Güte der gefundenen Lösung stark von der gegebenen Lösung abhängt. Mit der k-means++ Initialisierung (Arthur und Vassilvitskii, 2007) kann eine initiale Lösung bestimmt werden, deren Kosten im Erwartungswert bis auf einen logarithmischen Faktor an die optimalen Kosten herankommt.

Fuzzy k-means

Eine Verallgemeinerung des k-means Problems besteht darin, die feste Zuordnung der Datenpunkte zu den Clustern aufzuweichen. Jeder Datenpunkt wird anteilig jedem Cluster zugewiesen. Analog zum k-means Algorithmus gibt es für das Fuzzy k-means Problem einen Algorithmus, der ein lokales Minimum der Kostenfunktion bestimmt.

Clustering mit Gaußmixturen

Dieses Forschungsthema kombiniert das anteilige Zuweisen von Datenpunkten zu allen Clustern und die Verwendung von Gaußverteilungen als Repräsentanten. Dieses Problem ist auch bekannt als das Maximum Likelihood Estimation (MLE) Problem für Gaußmixturen. Der Expectation Maximization (EM) Algorithmus (Dempster, 1977) ist eine Verallgemeinerung des k-means Algorithmus, der jedoch nicht notwendigerweise ein lokales Optimum liefert. Umso wichtiger ist es hier, den Algorithmus mit einer guten Lösung zu initialisieren.

Unsere Ergebnisse

Eine neue theoretische und experimentelle Analyse einer randomisierten Version des EM-Algorithmus für Gaußmixturen, dem Stochastic Expectation Maximization (SEM) Algorithmus. Unter gewissen Voraussetzungen verhalten sich der EM und der SEM Algorithmus fast gleich, wobei der SEM Algorithmus jedoch fast doppelt so schnell ist.
Ein experimenteller Vergleich verschiedener Initialisierungsmethoden für den EM Algorithmus für Gaußmixturen.
Nicht-darstellbarkeit von optimalen Fuzzy k-means Lösungen.
Ein Algorithmus mit garantierter Approximationsgüte für das Fuzzy k-means Problem.
Eine Kernmengenkonstruktion for das Fuzzy k-means Problem.

Offene Fragen

Gibt es einen Polynomialzeitalgorithmus mit garantierter Güte für das Fuzzy k-means Problem?
Können wir das Fuzzy k-means Problem in eine der klassischen Komplexitätklassen einordnen?
Gibt es beweisbar gute Initialisierungsmethoden für den EM-Algorithmus für Gaußmixturen?

Implementierungen und Datensätze

Publikationen

A Complexity Theoretical Study of Fuzzy K-Means

J. Blömer, S. Brauer, K. Bujna, ACM Transactions on Algorithms 16 (2020) 1–25.

DOI

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.

DOI

Complexity of single-swap heuristics for metric facility location and related problems

S. Brauer, Theoretical Computer Science 754 (2019) 88–106.

DOI

Classification and Approximation of Geometric Location Problems

S. Brauer, Classification and Approximation of Geometric Location Problems, Paderborn, 2019.

DOI

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.

DOI

Soft Clustering Algorithms - Theoretical and Practical Improvements

K. Bujna, Soft Clustering Algorithms - Theoretical and Practical Improvements, Universität Paderborn, 2017.

DOI

Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems

S. Brauer, in: D. Fotakis, A. Pagourtzis, V.T. Paschos (Eds.), Lecture Notes in Computer Science, Springer International Publishing, Cham, 2017, pp. 116–127.

DOI

Hard-Clustering with Gaussian Mixture Models

J. Blömer, S. Brauer, K. Bujna, (2016).

Adaptive Seeding for Gaussian Mixture Models

J. Blömer, K. Bujna, in: Advances in Knowledge Discovery and Data Mining, Springer International Publishing, Cham, 2016, pp. 296–308.

DOI

A Theoretical Analysis of the Fuzzy K-Means Problem

J. Blömer, S. Brauer, K. Bujna, in: 2016 IEEE 16th International Conference on Data Mining (ICDM), IEEE, 2016, pp. 805–810.

DOI

A Probabilistic Expectation Maximization Algorithm for Multivariate Laplacian Mixtures

S. Brauer, A Probabilistic Expectation Maximization Algorithm for Multivariate Laplacian Mixtures, 2014.

Analysis of Agglomerative Clustering

M.R. Ackermann, J. Blömer, D. Kuntze, C. Sohler, Algorithmica 69 (2014).

DOI

A Theoretical and Experimental Comparison of the EM and SEM Algorithm

J. Blömer, K. Bujna, D. Kuntze, in: 2014 22nd International Conference on Pattern Recognition, IEEE, 2014.

DOI

Practical algorithms for clustering and modeling large data sets - Analysis and improvements

D. Kuntze, Practical Algorithms for Clustering and Modeling Large Data Sets - Analysis and Improvements, Universität Paderborn, 2013.

StreamKM++: A clustering algorithm for data streams

M.R. Ackermann, M. Märtens, C. Raupach, K. Swierkot, C. Lammersen, C. Sohler, 17 (2012).

DOI

Hardness and Non-Approximability of Bregman Clustering Problems.

M.R. Ackermann, J. Blömer, C. Scholz, (2011).

Bregman Clustering for Separable Instances

M.R. Ackermann, J. Blömer, in: SWAT 2010, Springer Berlin Heidelberg, Berlin, Heidelberg, 2010, pp. 212–223.

DOI

Clustering for Metric and Nonmetric Distance Measures

M.R. Ackermann, J. Blömer, C. Sohler, ACM Trans. Algorithms (2010) 59:1--59:26.

DOI

On the initialization of dynamic models for speech features

A. Krueger, V. Leutnant, R. Haeb-Umbach, M. Ackermann, J. Blömer, Proc. of ITG Fachtagung Sprachkommunikation. ITG, Bochum, Germany (2010).

Algorithms for the Bregman k-Median Problem

M.R. Ackermann, Algorithms for the Bregman K-Median Problem, Universität Paderborn, 2009.

Coresets and Approximate Clustering for Bregman Divergences

M.R. Ackermann, J. Blömer, in: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2009, pp. 1088–1097.

DOI

Show all publications