Prax­is­nahe The­or­ie für Clus­terin­gal­gorith­men (DFG Pri­or­ity Pro­gramme 1307)

Das Problem

Unter Clustering (oder Clusteranalyse) 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 und nehmen die Menge der verzeichneten Orte als unsere Menge von Objekten. 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 nun 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.

In einem Forschungsprojekt mit der DFG versuchen wir einerseits herauszufinden, wie gut oder schlecht in der Praxis eingesetzte Clusteringalgorithmen sind und anderseits beweisbar gute Algorithmen zu entwickeln. Dabei interessieren wir uns insbesondere für spezielle Ähnlichkeitsmaße die etwa auf die Symmetrieeigenschaft verzichten. Ein Beispiel hierfür ist die sogenannte Kullback-Leibler-Divergenz (oder kurz KLD). Mit Hilfe der KLD kann man Aussagen über den Abstand zwischen zwei Wahrscheinlichkeitsverteilungen machen. Die KLD einer Verteilung P zu einer Verteilung Q beschreibt den Kompressionsverlust, der entsteht, wenn man Symbole, die mit der Wahrscheinlichkeitsverteilung P erzeugt werden mit einem optimalen Code für die Wahrscheinlichkeitsverteilung Q komprimiert. Mithilfe der KLD lässt sich damit die Clusteranalyse für die Datenkompression einsetzen. Die Abbildung zeigt die Asymmetrie der KLD. Die beiden eingefärbten Kurven haben den gleichen Abstand zum Zentrum, einmal von der Kurve zum Zentrum gerechnet und einmal vom Zentrum zur Kurve.

• Ein einfacher (1+ε)-Approximationsalgorithmus mit einer Laufzeit linear in Größe und Dimension der Eingabe bei konstanter Clusterzahl. Der Algorithmus funktioniert nicht nur für die KLD sondern sogar für beliebige Abstandsmaße, welche die obige Stichprobeneigenschaft besitzen (z.B. ||·||², Mahalanobis-Divergenzen, spezielle Bregman-Divergenzen).
• Ein praxistauglicher Algorithmus für Datenströme: StreamKM++. Dieser Algorithmus ist insbesondere für Clustering-Probleme auf sehr großen Datenmengen geeignet. Dabei erzielt er deutlich bessere Approximationsgüten als etwa der klassische BIRCH-Algoritmmus und erweist sich dabei zudem als effizienter als qualitativ vergleichbare Alternativen wie z.B. lokale Suchstrategien.
• Eine erste Analyse des weit verbreiteten Agglomerativen Complete-Linkage Clusteringalgorithmus für das Durchmesser-Clusteringproblem. Unter der Annahme, dass die Dimension konstant ist, ist die Laufzeit beschränkt durch O(log k), wobei k die Anzahl der berechneten Cluster ist.

• Lassen sich Ergebnisse und Algorithmen für Euklidische Clustering-Probleme auf das probabilistische Clustering-Problem übertragen?

• CluE - Eine Clustering-Bibliothek für C++
• StreamKM++ - Ein praxistauglicher Algorithmus für Datenströme

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