Clus­ter­ana­ly­se

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.

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.

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.

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.

• 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.

• 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?

• InitGMMLab — Adaptive Seeding for Gaussian Mixture Models
• SEMLab -- Comparison of SEM and EM Algorithms
• CluE — Eine Clustering-Bibliothek für C++
• StreamKM++ — Ein praxistauglicher Algorithmus für Datenströme