Faster Algorithms for the Constrained k-means Problem
Faster Algorithms for the Constrained k-means Problem
复制标题
DOI：
10.1007/s00224-017-9820-7
复制
发表时间：
2018-01-01
影响因子：
0.5
通讯作者：
Kumar, Amit
中科院分区：
文献类型：
--
作者：
Bhattacharya, Anup;Jaiswal, Ragesh;Kumar, Amit
经典的基于中心的聚类问题，如k-means/median/center，假设最优聚类满足局部性，即同一聚类中的点彼此接近。在机器学习中出现了许多聚类问题，其中最优聚类不遵循这种局部性。例如，考虑r -gather聚类问题，其中有一个额外的约束，即每个聚类应该至少有r个点，或者考虑有容量的聚类问题，其中有一个聚类大小的上限。考虑k-means问题的一个变体，它可以被视为这类问题的一般版本。这里，最优簇O-1，…， O-k是数据集的任意分区，目标是输出k个中心c(1)，…， c(k)使得目标函数Sigma(k)(i=1) Sigma（x是Oi的一个元素）平行于x - c(i)平行于(2)最小化。不难论证，任何输出单个k个中心的算法（不知道最优聚类），就优化上述目标函数而言，都不会表现良好。然而，这并不排除存在这样的算法，即输出这样的k个中心的列表，使得这些k个中心中至少有一个表现良好。给定一个误差参数epsilon > 0，设l表示最小k-中心列表的大小，使得k-中心中至少有一个给出（1 + epsilon）近似w.r.t.上述目标函数。在本文中，我们通过给出一个随机算法来显示l的上界，该算法输出2(（O) / tilde (k/epsilon)）个k-中心的列表。我们也给出了一个紧密匹配的下界2（)/ (k/√)）此外，我们的算法运行时间为O（nd）。2（0) / (k/)）这比Ding和Xu（2015）给出的运行时间为0 （nd）的算法的结果有了显著的改进。（log n）(k)2(poly(k/epsilon)))，输出一个大小为O((log n)(k)的列表。2 (poly (k /)ε))。我们的技术适用于k-中值问题以及涉及非欧几里德距离度量的许多其他设置。
The classical center based clustering problems such as k-means/median/center assume that the optimal clusters satisfy the locality property that the points in the same cluster are close to each other. A number of clustering problems arise in machine learning where the optimal clusters do not follow such a locality property. For instance, consider the r -gather clustering problem where there is an additional constraint that each of the clusters should have at least r points or the capacitated clustering problem where there is an upper bound on the cluster sizes. Consider a variant of the k-means problem that may be regarded as a general version of such problems. Here, the optimal clusters O-1, ... , O-k are an arbitrary partition of the dataset and the goal is to output k-centers c(1), ... , c (k) such that the objective function Sigma(k)(i=1) Sigma(x is an element of Oi) parallel to x - c(i)parallel to(2) is minimized. It is not difficult to argue that any algorithm (without knowing the optimal clusters) that outputs a single set of k centers, will not behave well as far as optimizing the above objective function is concerned. However, this does not rule out the existence of algorithms that output a list of such k centers such that at least one of these k centers behaves well. Given an error parameter epsilon > 0, let l denote the size of the smallest list of k-centers such that at least one of the k-centers gives a (1 + epsilon) approximation w.r.t. the objective function above. In this paper, we show an upper bound on l by giving a randomized algorithm that outputs a list of 2((O) over tilde (k/epsilon)) k-centers. We also give a closely matching lower bound of 2((Omega) over tilde (k/root epsilon)) . Moreover, our algorithm runs in time O(nd . 2((O) over tilde (k/epsilon))) . This is a significant improvement over the previous result of Ding and Xu (2015) who gave an algorithm with running time O(nd . (log n)(k) . 2(poly(k/epsilon))) and output a list of size O((log n)(k) . 2(poly(k/)epsilon)). Our techniques generalize for the k-median problem and for many other settings where non-Euclidean distance measures are involved.