约束k均值问题的快速算法外文翻译资料

英语原文共 18 页，剩余内容已隐藏，支付完成后下载完整资料

约束k均值问题的快速算法

Anup Bhattacharya, Ragesh Jaiswal和Amit Kumar

计算机科学与工程系,印度理工学院⋆德里

摘要。经典的基于中心的聚类问题，如k-均值/中值/中心，假设最优聚类满足同一聚类中的点彼此接近的局部性。在机器学习中出现了许多聚类问题，其中最优聚类不遵循这种局部性。例如，考虑R-聚集聚类问题，其中存在一个额外的约束，即每个集群至少应具有R点；或者考虑具有容量的聚类问题，其中集群大小有一个上限。考虑k-均值问题的一个变体，它可能被视为此类问题的一般版本。这里，最优簇O1，hellip;，OK是对数据集的任意划分，目标是输出K中心C1，hellip;，CK，使目标函数PKi＝1xisin;oi xminus;ci 2最小化。不难证明任何算法（没有

了解输出单组k中心的最优簇）在优化上述目标函数方面表现不佳。但是，这并不能排除算法的存在，这些算法输出这样的K中心列表，这样至少有一个K中心的行为良好。给定一个误差参数εgt;0，让_表示K中心最小列表的大小，这样至少一个K中心给出（1 ε）近似值w.r.t.上述目标函数。本文给出了一个随机算法，给出了_的上界，该算法输出一个2（k/ε）k-中心1的列表。我们还给出了2Omega;（k）的近似匹配下界。/

ε）. 此外，我们的算法按时间运行o nd·2o（k/ε）。这是对Ding和Xu[dx15]之前的结果的显著改进，他们给出了一个运行时间为o nd·（log n）k·2poly（k/ε）的算法，并输出一个大小为o（log n）k·2poly（k/ε）的列表。我们的技术概括了k-中值问题以及涉及非欧几里得距离测量的许多其他设置。

1介绍

聚类问题旨在根据点之间的邻近程度对高维数据进行分类。有一个固有的假设，集群满足局部性——彼此相邻的点(在几何意义上)应该属于同一类别。通常，我们用基于中心的聚类问题的概念来对此类问题建模。我们想要确定一组中心，每个中心对应一个集群，然后通过将每个点分配到最近的中心来获得集群。例如，k-means问题定义如下:给定一个数据集X = {x1，hellip;,xn}sub;Rd和整数k, k中心输出一组{c1,。,ck}sub;Rd,目标函数Px Xisin;mincisin;{c1,hellip;hellip;，ck} ||x - c||2最小。通过定义一个合适的目标函数，以类似的方式定义了k中值问题和k中心问题。

然而，这类聚类问题通常需要几个方面的约束。这样的约束限制了可行集群的集合。例如，r-gather k-means集群问题的定义方法与k-means问题相同，但是有一个额外的约束，即每个集群中必须至少有r个点。在这样的设置中，不再是通过Voronoi分区从中心集获得集群。丁和徐[DX15]对这些问题进行了系统的研究，这也是我们工作的出发点。他们定义了所谓的约束k均值问题。这类问题的一个实例由一组点X指定，一个参数k，集合C，其中C的每个元素都是将X分割成k个不相交子集(或簇)由于集合C可能是指数级大的，所以我们假设它是由一个有效的算法以一种简洁的方式指定的，该算法决定了这个集合的成员。一个解决方案需要输出一个元素O = {O1，hellip;和一组k个中心，c1，hellip;， ck, o中的每个簇对应一个，目标是最小化Pk i = 1Pxisin;Oi | | xminus;ci | | 2。很容易检查，中心ci必须是的平均值相应的集群Oi。注意，k-均值问题是这个问题的一个特例，其中集合C包含将X划分为k个子集的所有可能方法。约束k中值问题可以用类似的方法定义。我们将做一个自然的假设(丁和徐也是这样做的)，即找到一组k个中心就足够了。换句话说，有一个(有效的)算法AC，它给出了一组以k为中心的c1，hellip;， ck，输出聚类{O1，hellip;， Ok}isin;C，使得Pk i = 1Pxisin;Oi ||ci - x||2最小。这种算法称为分区算法，由丁和徐[DX15] 2。对于k-均值问题，该算法将给出Voronoi对c1的分区，hellip;，而对于r-gather k-means聚类问题，算法AC将通过合适的最小代价流计算给出(见[DX15]第4.1节)。

Ding和Xu [DX15]考虑了不同领域中出现的几个自然问题，例如机器学习，可以在这个框架中进行说明。这些问题包括所谓的r-聚集k-均值、r-容量k-均值和l-多样性k-均值问题。他们解决这类问题的方法是输出一个候选中心集列表(大小为k)，使其中至少一个中心接近最优中心。我们将这种方法形式化，并证明了如果k是一个常数，那么就可以得到运行时间为线性的约束k-均值(和约束k-中值)问题的PTAS加上对AC的调用次数为常数。

我们定义了列表k-均值问题。给定一组点的X和参数k和ε,我们想输出列表L组k点(或中心)。列表L应该具有以下属性:对于任何分区O = {O1，hellip;， Ok}将X分成k个簇，存在一个集合c1，hellip;， ck在列表L中，使(直到重新排序这些中心)

xisin;Oi x |Oi|表示Oi的均值。注意，后一个数量是的k-means成本

所以我们需要c1。， ck使得分配到这些中心的成本接近该集群的最优k-均值成本。我们将使用optk(O)表示O的最优k-均值成本。

丁和徐[DX15],他们给出了一个算法,输出一个sizeO列表(o (log n)) k·2聚(k /ε)。请注意，我们处理了一个既涉及算法又涉及存在的问题

L的大小，我们能多有效地找到它?我们还给出了这样一个列表L的大小的几乎匹配的下界。我们的查找L的算法依赖于d2采样的思想——通过选择离当前中心集很远的下一个中心来迭代地查找中心。虽然这些思想已经被用于k-means问题(如[JKS14])，但它们严重依赖于这样一个事实:给定一组中心，对应的聚类是通过对应的Voronoi分区获得的。我们的方法依赖于显示一个小尺寸的列表L，它适用于所有可能的集群。

也对这种划分算法进行了讨论，解决了一些带有边约束的聚类问题。

不难证明结果列表的k - means问题意味着相应结果的约束k - means问题电话交流的数量的大小等于列表l .因此,我们获得作为我们主要的推论结果有效约束k - means算法(以及约束k-median)问题。

1.1相关工作

经典的k均值问题是研究最广泛的聚类问题之一。对于k-均值和k-中值问题，要获得快速的PTAS需要做大量的工作(如[Mat00, BHPI02, dlVKKR03, HPM04, KSS10, ABS10, Che06, JKS14, FMS07]和参考文献)。其中一些作品含蓄地维护中心列表大小k,满足条件(1)对应于一个泰森多边形法分区的所有集群O(对一组k中心)的输入点集,和一组挑选最好的的中心从这个列表(见例如,[KSS10, ABS10 JKS14])。列表中有最多2聚(k /ε)元素,从这,一个人可以恢复(1 ε)光纤算法运行时间的k - means问题O 2 nd·保利(k /ε)。

更一般情况下的约束k - means问题研究了丁和徐[DX15]他也给出了一个算法,输出列表大小O (log n) k·2聚(k /ε)。我们的工作改进了这一结果。此外，我们认为拟订清单k-means问题是一项重要贡献，并认为在其他分类设置中采用类似的公式将是有用的。

1.2预赛

我们正式定义了本文所考虑的问题。一个有限点集的重心或均值Xsub;Rd用为这些集合的1-均值代价

点,即

列表的输入实例我k - means(或列表k-median)问题由一组X点,一个正整数k和积极的参数ε。把X分成不相交的子集O1，hellip;,好将称为x给定一个集群的集群O⋆= {O⋆1。。。⋆阿k} (X)和一组k中心C = {c1,。、ck}定义costC (O⋆)最小,所有排列pi;的C

。回想一下,optk (O⋆)表示最优k - means O⋆成本,即。,

对一组pointsX和一组点C(大小最多k),定义Phi;C (X) asPxisin;X mincisin;C | | Xminus;C | | 2,即。我们考虑了C引起的X的Voronoi划分，并考虑了X相对于这个划分的k-均值代价。当考虑列表k中值问题时，我们将使用相同的符号，只是我们将考虑欧几里德范数而不是欧几里德范数的平方。当C是一个单例C{},我们滥用符号用Phi;c (X),而不是Phi;}{C (X)。

在介绍中提到的,约束k - means问题是由一组指定点X,一个正整数k、C和一组可行的集群的进一步X,交流我们给出一个算法,给定一组k中心C,输出聚类在C O最小化costC (O)。目标是找到一个聚类Oisin;C和一个规模为k的集合C，使成本最小(O)。注意，C中的中心应该是o中的每个簇的均值。另一方面，如果我们知道C，那么我们可以通过调用AC找到C中的最佳簇。

现在我们提到一些将用于我们分析的结果。下面的事实是众所周知的。

事实1。对于任何Xsub;Rd和cisin;Rd

接下来，我们定义了d2采样的概念。

定义1 (D2-sampling)。给定一组点的Xsub;Rd和另一组点Csub;Rd, D2-sampling从X关于C样本点X X概率

Inaba等人[IKI94]的以下结果表明，就1-均值目标而言，恒定大小的随机样本是一组X点的足够好的近似。

引理1 ([IKI94])。让年代独立抽样获得的点集M点替换均匀随机从一个点集Xsub;Rd。然后对任何delta;gt; 0,

我们还将使用下面这个简单的事实，它可以解释为平方欧几里得距离的三角形不等式的近似形式。

事实2(近似三角形不等式)。对于任何x, y, zisin;Rd, | | xminus;z | | 2le;2·| | xminus;y | | 2 2·| | yminus;z | | 2。

1.3我们的结果

现在我们声明列表k-均值和列表k-中值问题的结果。

作为这个结果的一个推论，我们得到了约束k均值问题(和类似的约束k中值问题)的

证明。我们使用定理1中的算法来得到这个数据集的列表L。对于每个集合Cisin;L，我们用C作为中心集合调用AC——让O(C)表示由AC产生的聚类，输出代价最小的聚类。让O⋆最优聚类。,集群在C optk (O⋆)最低。我们知道的概率至少1/2,有集Cisin;L costC (O⋆)le;(1 ε)optk (O⋆)。现在,我们的算法产生的解决方案成本最多costC (O (C)),通过交流的定义,最多

我们也给出了一个几乎匹配的下限大小的L.下面的结果连同姚的

我们的技术也扩展到涉及许多其他的“近似”度量空间的设置(见第6节中的讨论)。另一个重要的观察是,在上面的下界的结果中,C与泰森多边形法分区对应的聚类x这点明了之前作品[KSS10、ABS10 FMS07, JKS14, JKY15]为什么所有算法的运行时间是

1.4我们的技术

我们的技术是基于这个想法的D2-sampling贾斯瓦尔et al . (JKS14)用来给(1 ε)光纤为k - means算法问题。我们的思想也与丁、徐的思想有相似之处[DX15]。我们将在本小节末尾讨论这些相似之处。

的重要成分之一,用于大部分的(1 ε)光纤的k - means算法引理1。这个结果本质上指出,给定一组点P,如果我们能够均匀样本O(1 /ε)点,然后这些采样点的意思是将是一个很好的替代P的意思。考虑一个最优聚类O⋆1,。⋆阿k的一组点x如果我们能均匀样本的每个集群⋆我阿,然后上面的论点,我们将完成。一遇到第一个问题是,人们只能从输入样本点集,所以,如果我们样本足够多从X点,我们需要以某种方式区分分属于O⋆我在这个示例。这可以处理使用以下参数:假设我们设法得到一个小样本的点(比如大小O (poly (k /ε)))包含至少Ω(1 /ε)点均匀分布在O⋆我,那么我们可以尝试所有可能的子集的大小O(1 /ε)并确保至少一个子集的一个统一的样品从O⋆我合适的大小。另一个问题是,我们如何确保样品有足够的代表从O⋆我?从输入X不会均匀采样工作因为我| | O⋆可能非常小的规模相比| | X。这就是d2采样发挥关键作用的地方，我们接下来将讨论这个问题。

给定一组点的Xsube;Rd和候选人中心c1,hellip;， ciisin;Rd, d2 -抽样关于中心c1，hellip;， ci采样点xisin;x，其概率与mincisin;{c1成正比，hellip;,ci} | | xminus;c | | 2。注意,这个过程“促进”的概率集群O⋆j有许多点{c1,。。。,ci}。因此,即使一个集群O⋆j具有体积小,我们将有一个好机会的采样点(如果它是远离当前的中心)。然而，这种非均匀采样技术带来了另一个问题。被采样点不再是最优聚类的均匀样本。根据当前的中心,不同的点在一个集群中O⋆j有不同的概率抽样。这个问题对于k均值问题并不是那么严重，因为我们可以认为最优的集群是Voronoi区域，因为概率并没有太大的不同。然而，对于约束k均值问题，当允许最优簇为输入点的任意划分时，问题就变得更加严重。这可以用下面的例子来说明。假设我们取了中心c1hellip;好,ci(集群成本)的最优簇O⋆1,。⋆阿,我。这一点让O⋆j表示集群除了O⋆1,。⋆阿,我,这样一个点采样使用D2抽样w.r.t. c1,。,ci是最有可能从O⋆j。假设我们样本的集合S O (k /ε)使用D2-sampling点。我们保证(w.h.p)。有一个统一的样本子集S O⋆j ?答案是否定的(实际上远非如此)。这是因为最优簇可能形式任意分区的气候资料,可能大部分的点O⋆j可能非常接近中心c1,。,ci。在这种情况下，抽样这些点的概率将接近于0。我们处理这个场景中,我们考虑一个盖S′的联盟的样本集和O(1 /ε)副本的c1,。,ci。然后,我们认为所有的点在O⋆j c1,。， ci将有很好的机会出现在S中(因此出现在S中)。另一方面，即使是接近c1的点，hellip;， ci将不表示在S(因此S )中，即中心(在c1中，hellip;ci),接近这些点有很好的表现在S′和这些中心可能被视为“代理”点O⋆j。

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[19963]，资料为PDF文档或Word文档，PDF文档可免费转换为Word