TY  - THES
A3  - Blömer, Johannes
A3  - Sohler, Christian
AB  - 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.
AU  - Kuntze, Daniel
DA  - 2014
DP  - Universität Paderborn
LA  - eng
N1  - Tag der Verteidigung: 07.11.2013
N1  - Paderborn, Univ., Diss., 2013
PB  - Veröffentlichungen der Universität
PY  - 2014
T2  - Institut für Informatik
TI  - Practical algorithms for clustering and modeling large data sets: analysis and improvements
UR  - https://nbn-resolving.org/urn:nbn:de:hbz:466:2-12721
Y2  - 2026-02-06T21:53:57
ER  -