ON CORESETS FOR k-MEDIAN AND k-MEANS CLUSTERING IN METRIC AND EUCLIDEAN SPACES AND THEIR APPLICATIONS
ON CORESETS FOR k-MEDIAN AND k-MEANS CLUSTERING IN METRIC AND EUCLIDEAN SPACES AND THEIR APPLICATIONS
复制标题
DOI：
10.1137/070699007
复制
发表时间：
2009-01-01
影响因子：
1.6
通讯作者：
Chen, Ke
中科院分区：
文献类型：
--
作者：
Chen, Ke
我们针对 k 中值和 k 均值聚类问题提出了新的近似算法。为此，我们在一般度量空间和欧几里得空间中获得用于 k 中值和 k 均值聚类的小型核心集。在 R-d 中，这些核心集的大小与维度 d 具有多项式相关性。这导致在 Rd 中实现最佳 k 中值和 k 均值聚类的 (1 + epsilon) 近似算法，运行时间为 O(ndk + 2((k/epsilon)O(1)) d(2) log(k+2) n)，其中 n 是点数。这比以前的结果有所改善。我们使用这些核心集来维护 R-d 中点流的 (1 + epsilon) 近似 k 中值和 k 均值聚类，使用 O(d(2)k(2)epsilon(-2) log(8) n) 空间。对于这些问题，这些是第一个流算法，它们具有空间复杂度以及对维度的多项式依赖性。
We present new approximation algorithms for the k-median and k-means clustering problems. To this end, we obtain small coresets for k-median and k-means clustering in general metric spaces and in Euclidean spaces. In R-d, these coresets are of size with polynomial dependency on the dimension d. This leads to (1 + epsilon)-approximation algorithms to the optimal k-median and k-means clustering in Rd, with running time O(ndk + 2((k/epsilon)O(1)) d(2) log(k+2) n), where n is the number of points. This improves over previous results. We use those coresets to maintain a (1 + epsilon)-approximate k-median and k-means clustering of a stream of points in R-d, using O(d(2)k(2)epsilon(-2) log(8) n) space. These are the first streaming algorithms, for those problems, that have space complexity with polynomial dependency on the dimension.