Clustering for Metric and Nonmetric Distance Measures
Clustering for Metric and Nonmetric Distance Measures
复制标题
DOI：
10.1145/1824777.1824779
复制
发表时间：
2010-01-01
影响因子：
1.3
通讯作者：
Sohler, Christian
中科院分区：
文献类型：
--
作者：
Ackermann, Marcel R.;Bloemer, Johannes;Sohler, Christian
本文研究了k-中值问题关于任意相异性测度D的推广。给定一个大小为n的有限集合P，我们的目标是找到一个大小为k的集合C，使得误差之和D（P，C）= Sigma（p是P的一个元素）min（c是C的一个元素）{D（p，c）}最小。本文的主要结果如下：如果通过取一个常数大小的随机样本并精确求解该样本上的I-median问题，可以在（1 + 1）的因子内逼近I-median问题，则存在关于D的k-median问题的（1 + 1）-逼近算法。该算法需要时间n2（O（mklog（n/n），其中m是仅依赖于n和D的常数。利用这一特征，我们得到了任意度量空间中k-中值问题、Kullback-Leibler发散（相对熵）、Itakura-Saito发散、Mahalanobis距离和Bregman发散的第一线性时间（1 + λ）-近似算法.此外，我们得到以前已知的结果，欧几里德k-中位数问题和欧几里德k-均值问题的简化方式。我们的结果是基于Kumar等人[2004]的算法的新分析。
We study a generalization of the k-median problem with respect to an arbitrary dissimilarity measure D. Given a finite set P of size n, our goal is to find a set C of size k such that the sum of errors D(P, C) = Sigma(p is an element of P) min(c is an element of C) {D(p, c)} is minimized. The main result in this article can be stated as follows: There exists a (1 + epsilon)-approximation algorithm for the k-median problem with respect to D, if the I-median problem can be approximated within a factor of (1 + epsilon) by taking a random sample of constant size and solving the I-median problem on the sample exactly. This algorithm requires time n2(O(mklog(mk/epsilon))), where m is a constant that depends only on epsilon and D. Using this characterization, we obtain the first linear time (1 + epsilon)-approximation algorithms for the k-median problem in an arbitrary metric space with bounded doubling dimension, for the Kullback-Leibler divergence (relative entropy), for the Itakura-Saito divergence, for Mahalanobis distances, and for some special cases of Bregman divergences. Moreover, we obtain previously known results for the Euclidean k-median problem and the Euclidean k-means problem in a simplified manner. Our results are based on a new analysis of an algorithm of Kumar et al. [2004].