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.

Our Res­ults

  • 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. ||·||2, 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.

Open Ques­tions

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

Pub­lic­a­tions

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