Details

Autor(en) / Beteiligte

• Kuntze, Daniel
• Blömer, Johannes
• Sohler, Christian

Titel

Practical algorithms for clustering and modeling large data sets : analysis and improvements [Elektronische Ressource]

Erscheinungsjahr

2014

Link zum Volltext

• Hochschulschriften Visual Library - Scan2Web Hochschulschriften UB Paderborn (s2w-hsspadubpb)
• Volltext

  kostenfrei

Link zu anderen Inhalten

• Volltext

Verknüpfte Titel

Beschreibungen/Notizen

• Tag der Verteidigung: 07.11.2013
• Paderborn, Univ., Diss., 2013
• Open Access
• ger: In Zeiten von Big Data sind große Datenbankanwendungen von wachsender Bedeutung. Eine zentrale Aufgabe aus diesem Bereich ist die Reduzierung der zu verarbeitenden Datenmenge. Diese Aufgabe lässt sich beispielsweise lösen, indem die Struktur der gegebenen Daten erfasst wird. In dieser Dissertation beschäftigen wir uns mit zwei Techniken zur Strukturierung von großen Datenmengen. Im ersten Teil der Arbeit geht es um Clusteranalyse, speziell um das Durchmesser-k-Clustering-Problem. Wir liefern die erste Analyse des agglomerativen Complete-Linkage Clusteringalgorithmus. Wir zeigen, dass die vom Algorithmus berechnete Lösung für konstante Dimension d für jedes k eine O(log k)-Approximation des Durchmesser-k-Clustering-Problems ist. Außerdem analysieren wir das k-Center-Problem und das diskrete k-Center-Problem. Für die dazugehörigen agglomerativen Algorithmen leiten wir ebenfalls einen Approximationsfaktor von O(log k) her. Der zweite Teil der Arbeit beschäftigt sich mit der Parameterschätzung für allgemeine und Gaußsche Mixturverteilungen. Wir analysieren eine probabilistische Variante des Expectation-Maximization (EM) Algorithmus, die als Stochastic EM oder SEM Algorithmus bekannt ist. Für Gaußsche Mixturmodelle zeigen wir, dass die Updates des EM Algorithmus und seiner probabilistischen Variante mit hoher Wahrscheinlichkeit fast identisch sind, wenn die Datenmenge groß genug ist. Eine Reihe von Experimenten bestätigt, dass dies auch für eine große Anzahl aufeinanderfolgender Updateschritte noch gilt. Darüber hinaus erörtern wir, warum der SEM Algorithmus schneller arbeitet als der klassische EM Algorithmus. Insbesondere zeigen wir für Gaußsche Mixturmodelle, dass die probabilistische Variante eine Beschleunigung um einen konstanten Faktor erreicht.
• eng: In times of big data, large-scale database applications are of increasing importance. A central task in this field is to reduce the amount of data that has to be processed. One way to approach this task is to capture the structure of the given data. This thesis deals with two particular data structuring techniques. The first part of this thesis is about cluster analysis. More precisely, we consider the diameter k-clustering problem. We provide the first analysis of the agglomerative complete linkage clustering algorithm. Assuming that the dimension d is a constant, we show that for any k the solution computed by this algorithm is an O(log k)-approximation to the diameter k-clustering problem. Our analysis does not only hold for the Euclidean distance but for any metric that is based on a norm. Furthermore, we analyze the closely related k-center and discrete k-center problem. For the corresponding agglomerative algorithms, we deduce an approximation factor of O(log k) as well. The second part of this thesis deals with the parameter estimation problem for general and Gaussian mixture distributions. We analyze a probabilistic variant of the Expectation-Maximization (EM) algorithm, known as the Stochastic EM or SEM algorithm. Unlike the original work, we focus on the analysis of a single run of the algorithm. We focus on the SEM algorithm for Gaussian mixture models and show that with high probability the updates of the EM algorithm and its probabilistic variant are almost the same, given that the data set is sufficiently large. A series of experiments confirms that this still holds for a large number of successive update steps. Furthermore, we explain why the SEM algorithm is considerably faster than the classical EM algorithm. In particular, we show that the probabilistic variant establishes a constant factor speedup for Gaussian mixture models.