Achtung:

Sie haben Javascript deaktiviert!
Sie haben versucht eine Funktion zu nutzen, die nur mit Javascript möglich ist. Um sämtliche Funktionalitäten unserer Internetseite zu nutzen, aktivieren Sie bitte Javascript in Ihrem Browser.

Info-Icon This content is not available in English
[Translate to English:] AG Codes und Kryptographie Show image information

[Translate to English:] AG Codes und Kryptographie

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?

Publikationen


Open list in Research Information System

2020

A Complexity Theoretical Study of Fuzzy K-Means

J. Blömer, S. Brauer, K. Bujna, ACM Transactions on Algorithms (2020), 16(4), pp. 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 (2020), 14, pp. 147–173

DOI


2019

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

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

DOI



2018

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


2017


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

S. Brauer, in: Lecture Notes in Computer Science, Springer International Publishing, 2017, pp. 116-127

Metric facility location and K-means are well-known problems of combinatorial optimization. Both admit a fairly simple heuristic called single-swap, which adds, drops or swaps open facilities until it reaches a local optimum. For both problems, it is known that this algorithm produces a solution that is at most a constant factor worse than the respective global optimum. In this paper, we show that single-swap applied to the weighted metric uncapacitated facility location and weighted discrete K-means problem is tightly PLS-complete and hence has exponential worst-case running time.


2016


Adaptive Seeding for Gaussian Mixture Models

J. Blömer, K. Bujna, in: Advances in Knowledge Discovery and Data Mining, Springer International Publishing, 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

One of the most popular fuzzy clustering techniques is the fuzzy K-means algorithm (also known as fuzzy-c-means or FCM algorithm). In contrast to the K-means and K-median problem, the underlying fuzzy K-means problem has not been studied from a theoretical point of view. In particular, there are no algorithms with approximation guarantees similar to the famous K-means++ algorithm known for the fuzzy K-means problem. This work initiates the study of the fuzzy K-means problem from an algorithmic and complexity theoretic perspective. We show that optimal solutions for the fuzzy K-means problem cannot, in general, be expressed by radicals over the input points. Surprisingly, this already holds for simple inputs in one-dimensional space. Hence, one cannot expect to compute optimal solutions exactly. We give the first (1+eps)-approximation algorithms for the fuzzy K-means problem. First, we present a deterministic approximation algorithm whose runtime is polynomial in N and linear in the dimension D of the input set, given that K is constant, i.e. a polynomial time approximation scheme (PTAS) for fixed K. We achieve this result by showing that for each soft clustering there exists a hard clustering with similar properties. Second, by using techniques known from coreset constructions for the K-means problem, we develop a deterministic approximation algorithm that runs in time almost linear in N but exponential in the dimension D. We complement these results with a randomized algorithm which imposes some natural restrictions on the sought solution and whose runtime is comparable to some of the most efficient approximation algorithms for K-means, i.e. linear in the number of points and the dimension, but exponential in the number of clusters.


2014


Analysis of Agglomerative Clustering

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

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


2013


2012

StreamKM++: A clustering algorithm for data streams

M.R. Ackermann, M. Märtens, C. Raupach, K. Swierkot, C. Lammersen, C. Sohler, ACM, 2012

DOI


2011

Hardness and Non-Approximability of Bregman Clustering Problems.

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


2010

Bregman Clustering for Separable Instances

M.R. Ackermann, J. Blömer, in: SWAT 2010, Springer 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)(4), pp. 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)


2009

Algorithms for the Bregman k-Median Problem

M.R. Ackermann, 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, 2009, pp. 1088-1097

DOI


Open list in Research Information System

The University for the Information Society