Coresets and Approximate Clustering for Bregman Divergences

摘要

We study the generalized k-median problem with respect to a Bregman divergence D_Φ. Given a finite set P{is contained in}R~d of size n, our goal is to find a set C of size k such that the sum of errors cost(P,C) =∑min{D_Φ(p, c)}(p∈P, c∈C) is minimized. The Bregman k-median problem plays an important role in many applications, e.g. information theory, statistics, text classification, and speech processing. We give the first coreset construction for this problem for a large subclass of Bregman divergences, including important dissimilarity measures such as the Kullback-Leibler divergence and the Itakura-Saito divergence. Using these coresets, we give a (1 +ε)-approximation algorithm for the Bregman k-median problem with running time O(dkn + d~22~(( k/ε)~(Θ(1)) log~(k+2) n). This result improves over the previousely fastest known (1+ε)-approximation algorithm from [1]. Unlike the analysis of most coreset constructions our analysis does not rely on the construction of ε-nets. Instead, we prove our results by purely combinatorial means.