English

In this thesis, we study the k-median problem with respect to a dissimilarity measure Dϕ from the family of Bregman divergences: Given a finite set P of size n from R^d , our goal is to find a set C of size k such that the sum of error cost(P,C) = sum_p∈P min_c∈C Dϕ(p,c) is minimized. This problem plays an important role in applications from many different areas of computer science, such as information theory, statistics, data mining, and speech processing.

Our main contribution is the development of a general framework of algorithms and techniques that is applicable to (almost) all Bregman divergences. In particular, we give a randomized approximation algorithm for the Bregman k-median problem that computes a (1+ε)-approximate solution using at most 2^O(k/ε) n arithmetic operations, including evaluations of Bregman divergence Dϕ. In doing so, we give the first approximation algorithm known for this problem that provides any provable approximation guarantee. We also give a fast, practical, randomized approximation algorithm that computes an O(log k)-approximate solution for arbitrary input instances, or even an O(1)-approximate solution for certain, well separated input instances.

In addition to that, we study the use of coresets in the context of Bregman k-median clusterings. In a nutshell, a coreset is a small (weighted) set that features the same clustering behavior as the original input set. We show how classical coreset constructions for the Euclidean k-means problem can be adapted to a special subfamily of the Bregman divergences, namely the class of Mahalanobis distances. We also give a new, randomized coreset construction for the Mahalanobis k-median problem in low dimensional spaces that has several practical advantages. Furthermore, by introducing the notion of weak coresets, we give the first coreset construction applicable to (almost) all Bregman k-median clustering problems. Using these weak coresets, we are able to give the asymptotically fastest (1+ε)-approximation algorithm currently known for the Bregman k-median problem. This algorithm uses at most O(kn) + 2^O(k/ε) log^k+2 (n) arithmetic operations, including evaluations of Bregman divergence Dϕ.

Deutsch

Thema dieser Dissertationsschrift ist das k-Median Problem unter Verwendung eines Abstandsmaßes Dϕ aus der Familie der Bregman-Divergenzen: Zu einer gegebenen Eingabemenge P der Größe n aus dem R^d ist eine Zentrenmenge C der Größe k gesucht, welche die Zielfunktion cost(P,C) = sum_p∈P min_c∈C Dϕ(p,c) minimiert. Dieses Problem ergibt sich in Anwendungen aus den verschiedensten Teilbereichen der Informatik, etwa in der Informationstheorie, in der Statistik, beim Durchsuchen großer Datenbestände oder bei der Verarbeitung von Sprachsignalen.

Das Hauptresultat dieser Arbeit besteht in der Entwicklung einer Sammlung von Algorithmen und Techniken, die sich auf (nahezu) alle Bregman-Divergenzen anwenden lassen. Insbesondere präsentieren wir einen randomisierten Approximationsalgorithmus der Güte (1+ε) für das Bregman-k-Median-Problem. Dieser Algorithmus berechnet seine Lösung unter Verwendung von maximal 2^O(k/ε) n arithmetischen Operationen, darunter auch Auswertungen des Abstandsmaßes Dϕ. Dabei handelt es sich um den ersten für das Bregman-k-Median-Problem anwendbaren Algorithmus, der eine beweisbare Approximationsgüte aufweist. Außerdem präsentieren wir einen effizienten, praktisch relevanten, randomisierten Approximationsalgorithmus, der Lösungen der Güte O(log k) berechnet; für spezielle, wohlseparierte Eingabeinstanzen berechnet dieser Algorithmus sogar Lösungen konstanter Güte.

Darüber hinaus untersuchen wir die Anwendung von Kernmengen für das Bregman-k-Median-Problem. Kurz zusammengefasst handelt es sich bei einer Kernmenge um eine kleine (gewichtete) Punktemenge, welche die gleichen Clustering-Eigenschaften wie die ursprüngliche Eingabemenge aufweist. Wir demonstrieren, wie sich klassische Kernmengenkonstruktionen des euklidischen k-Mittelwert-Problems auf eine spezielle Teilmenge der Bregman-Divergenzen verallgemeinern lassen, nämlich auf die Klasse der so genannten Mahalanobis-Distanzen. Wir präsentieren ferner eine neue, praktisch vorteilhafte, randomisierte Kernmengenkonstruktion für das Mahalanobis-k-Median-Problem in niedrigdimensionalen Räumen. Zudem greifen wir das Konzept der schwachen Kernmengen auf und präsentieren damit die erste Kernmengenkonstruktion, die sich für (fast) alle Bregman-Divergenzen anwenden läßt. Unter Anwendung dieser schwachen Kernmengen erhalten wir den derzeit asymptotisch effizientesten (1+ε)-Approximationsalgorithmus für das Bregman-k-Median-Problem. Dieser Algorithmus benötigt maximal O(kn) + 2^O(k/ε) log^k+2 (n) arithmetische Operationen, darunter auch Auswertungen des Abstandsmaßes Dϕ.