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.

AG Codes and Kryptographie Bildinformationen anzeigen

AG Codes and 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-c-means

Eine Erweiterung 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-c-means Problem einen Algorithmus, der ein lokales Minimum der Kostenfunktion bestimmt.

Hartes Clustering mit Gaußverteilungen

Um die Form und die Größe von Clustern zu berücksichtigen, kann man als Repräsentanten Gaußverteilungen benutzen. In diesem Fall sind die Kosten eines Datenpunktes gegeben durch seine Likelihood bezüglich der Gaußverteilung des Clusters, dem der Datenpunkt zugeordnet ist.

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 Algorithmus (auch: EM, 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.

Offene Fragen

  • Welche strukturellen Eigenschaften haben optimale Fuzzy-c-means Lösungen?
  • Wie gut kann das Fuzzy-c-means Problem approximiert werden?
  • Wie gut lässt sich das Hart-Clustering-Problem mit Gaußverteilungen approximieren?
  • Gibt es beweisbar gute Initialisierungsmethoden für den EM-Algorithmus für Gaußmixturen?

Publikationen

  • Sascha Brauer
    A Technical Report on PLS-Completeness of Single-Swap for Unweighted Metric Facility Location and K-Means
    In: Computing Research Repository, 2017, [Download]
  • Sascha Brauer
    Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems
    In: 10th International Conference on Algorithms and Complexity (CIAC), 2017, [DOI], [Full Version]
  • Johannes Blömer, Sascha Brauer, Kathrin Bujna
    A Theoretical Analysis of the Fuzzy K-Means Problem
    In: IEEE International Conference on Data Mining (ICDM), 2016, [DOI]
  • Johannes Blömer, Sascha Brauer, Kathrin Bujna
    Hard-Clustering with Gaussian Mixture Models
    In: Computing Research Repository, 2016, [Download]
  • Johannes Blömer, Kathrin Bujna
    Adaptive Seeding for Gaussian Mixture Models
    In: Proceedings of the 20th Pacific Asia Conference on Knowledge Discovery and Data Mining (PAKDD), 2016, [DOI]
  • Johannes Blömer, Sascha Brauer, Kathrin Bujna
    Complexity and Approximation of the Fuzzy K-Means Problem
    In: Computing Research Repository, 2015, [Download]
  • Marcel R. Ackermann, Johannes Blömer, Daniel Kuntze, Christian Sohler
    Analysis of Agglomerative Clustering
    In: Algorithmica, 2014, [DOI]
  • Johannes Blömer, Kathrin Bujna, Daniel Kuntze
    A Theoretical and Experimental Comparison of the EM and SEM Algorithm
    In: Proceedings of the 22nd International Conference on Pattern Recognition (ICPR) 2014, Stockholm, Sweden, 2014, [DOI]
  • Johannes Blömer, Kathrin Bujna
    Simple Methods for Initializing the EM Algorithm for Gaussian Mixture Models
    In: Computing Research Repository, 2013, [Download]
  • Johannes Blömer, Kathrin Bujna, Daniel Kuntze
    A Theoretical and Experimental Comparison of the EM and SEM Algorithm
    In: Computing Research Repository, 2013, [Download]
  • Daniel Kuntze
    Practical algorithms for clustering and modeling large data sets - Analysis and improvements
    PhD Thesis, Paderborn University, 2013, [Download]
  • Marcel R. Ackermann, Christiane Lammersen, Marcus Märtens, Christoph Raupach, Christian Sohler, Kamil Swierkot
    StreamKM++: A Clustering Algorithm for Data Streams
    In: ACM Journal of Experimental Algorithmics, 2012, [DOI]
  • Marcel R. Ackermann, Johannes Blömer, Daniel Kuntze, Christian Sohler
    Analysis of Agglomerative Clustering
    In: Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS '11), 2011, [DOI]
  • Marcel R. Ackermann, Johannes Blömer, Christoph Scholz
    Hardness and Non-Approximability of Bregman Clustering Problems
    In: Electronic Colloquium on Computational Complexity (ECCC), 2011, [Download]
  • Marcel R. Ackermann, Johannes Blömer
    Bregman Clustering for Separable Instances
    In: Proceedings of the 12th Scandinavian Symposium and Workshop on Algorithm Theory (SWAT '10), 2010, [DOI]
  • Marcel R. Ackermann, Johannes Blömer, Daniel Kuntze, Christian Sohler
    Analysis of Agglomerative Clustering
    In: Computing Research Repository (CoRR), 2010, [Download]
  • Marcel R. Ackermann, Johannes Blömer, Christian Sohler
    Clustering for Metric and Non-Metric Distance Measures
    In: ACM Transactions on Algorithms, 2010, [DOI]
  • Marcel R. Ackermann, Christiane Lammersen, Marcus Märtens, Christoph Raupach, Christian Sohler, Kamil Swierkot
    StreamKM++: A Clustering Algorithm for Data Streams
    In: Proceedings of the 12th Workshop on Algorithm Engineering and Experiments (ALENEX '10), 2010, [DOI]
  • Alexander Krüger, Volker Leutnant, Reinhold Häb-Umbach, Marcel R. Ackermann, Johannes Blömer
    On the Initialisation of Dynamic Models for Speech Features
    In: Sprachkommunikation 2010 -- Beiträge der 9. ITG-Fachtagung, 2010
  • Marcel R. Ackermann
    Algorithms for the Bregman k-Median Problem
    PhD Thesis, Paderborn University, 2009, [Download]
  • Marcel R. Ackermann, Johannes Blömer
    Coresets and Approximate Clustering for Bregman Divergences
    In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '09), 2009, [DOI], [Download]
  • Marcel R. Ackermann, Johannes Blömer, Christian Sohler
    Clustering for Metric and Non-Metric Distance Measures
    In: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '08), 2008, [Download]
  • Daniel Kuntze
    Untersuchung von Clusteringalgorithmen für die Kullback-Leibler Divergenz
    Diploma Thesis, Paderborn University, 2007, [Download]

Die Universität der Informationsgesellschaft