英语原文共 25 页，剩余内容已隐藏，支付完成后下载完整资料
K-均值聚类的局部搜索近似算法
摘 要
在k-均值聚类中，我们给出了在d维空间中的一组n个数据点和一个整数k，并且问题是确定在中的一组k个点，称为中心，求出每个数据点到其最近的中心的平方距离的最小均值。对于这个问题没有已知的精确的多项式时间算法。虽然存在渐近有效的近似算法，但是这些算法因为涉及到非常高的常数因素而不实用。有很多启发式被应用到实践中，但我们知道它们的表现是没有限制的。
我们考虑的问题是对于K-均值聚类是否存在一个简单且能实际应用的算法。我们提出了一种基于交换中心进出的局部改进启发式。我们证明这产生一个（9 ɛ）-近似算法。我们举个例子，显示基于执行固定数量交换的任何方法在所有足够高的维度中达到至少（9-ɛ）的近似因子。因此，对于基于执行固定数量交换的算法，我们的近似因子几乎是非常严格的。为了建立启发式的实用价值，我们提出一个实证研究，表明当与劳埃德算法相结合时，这种启发式在实践中表现相当好。
关键词：聚类，k-均值，近似算法，局部搜索，计算几何
1介绍
集群问题出现在许多不同的应用中，包括数据挖掘和知识发现[15]，数据压缩和矢量量化[19]以及模式识别和模式分类[11]。有许多方法，包括分割和合并方法，如ISODATA [6,21]，随机化方法如CLARA [25]和CLARANS [34]，以及基于神经网络的方法[27]。进一步关于聚类和聚类算法的信息可以在[8,20,21,22,23,25]中找到。欧几里德空间中最受欢迎和广泛研究的聚类方法之一称为k-均值聚类。给定真实d维空间中n个数据点的集合P，和一个整数k,并且问题是确定在中的一组k个点，称为中心，最小化从每个数据点到其最近中心的欧几里德距离的平均平方。这种措施通常被称为平方误差失真[19,21]。集群为主在k-均值上与其他一些聚类和设备位置问题密切相关。这些包括欧几里德k-中位数[3,28]和韦伯问题[42]，其目标是最小化总和到最近的中心的距离，以及欧几里德k-中心问题[13,39]，其目标是最小化最大距离。没有任何这些问题已知的有效的精确解决方案一般k，一些配方是NP-hard [18]。
鉴于正确解决k-均值和其他聚类和定位问题的明显困难，通过多项式时间逼近算法来考虑近似值是很自然的对其结果的质量提供保证，或启发式，不作任何保证。其中一个最流行的启发式的k-均值问题是劳埃德的算法[17,30,31]，这通常被称为k-均值算法。将中心点的邻域定义为数据点集合这个中心是最近的。很容易证明，任何本地最小化的解决方案必须是重心，意思是每个中心位于其邻域的中心位置[10,14]。劳埃德算法以任何方式开始可行的解决方案，并重复计算每个中心的邻域，然后将中心移动到其邻域的质心，直到满足一些收敛标准。可以看出劳埃德的算法最终收敛到局部最优解[38]。计算最近的邻居是最多的劳埃德算法中的昂贵的步骤，但是这种算法的一些实际实现已经被[2，24，35，36，37]。
图1：劳埃德算法可以产生任意高的近似比
不幸的是，很容易构建劳埃德算法收敛到局部最小值的情况这与最优解相比是任意的。这样的例子如图1所示。 其中k = 3且x lt;y lt;z。最优失真是，但很容易验证底部是重心，并且具有的变形。通过增加的比值近似比劳合社的算法可以任意高。 k-均值聚类还有许多其他启发式，基于分支搜索，梯度下降，模拟退火和遗传等方法算法[7，12，41]。对于这些方法，没有证明的近似边界是已知的。
对启发式的质量有一些限制是可取的，给定一个常数，c-近似算法（对于最小化问题）产生一个最大一个因素c大于最优解的解决方案。近似因子与运行时间之间存在经典的折衷。一些集群 - 算法能够产生任意接近最优的解。这包括（1 ɛ） - Arora，Raghavan和Rao [3]和Kolliopoulos和Rao [28]的欧几里得k-中值问题的近似算法。后者实现了运行时间，假设尺寸d是固定的。它基于将动态规划应用自适应分层分解空间。另一个例子是用于欧几里得k-中心问题的（1 ɛ）近似算法由Agarwal和Procopiuc给出，它以时间[1]。
Matousek [32]通过呈现渐近高效（1 ɛ）-在k-均值聚类中，运算在中的近似算法固定k和d的时间。首先，Matousek显示如何计算一组称为“近似值”的候选中心质心集，从中可以绘出近似最优解。他然后表明，可以假设最优解包括良好扩展的k-元组，其直观地意味着没有子集的k-元组相对于其他点是强烈隔离的。最后，他证明给出了一组m点，有这样的传播集。该算法生成所有这些元组并返回k元组具有最小的失真。不幸的是，恒定因素远远超出实际范围，除非d和k非常小。在第4节中，我们表明，在合理假设下，选择候选中心（Matousek的算法满足），良好扩展的k-元组的数量该算法生成至少为。在典型应用中，k可以在数十到数百之间，所以这远远超出了实际的限度。提出了动态规划近似算法由Kolliopoulos和Rao为k中位数问题[28]也是修改的候选人，但也受苦来自同样大的常数因子。
近似算法中的另一种常见方法是开发更实用，更有效率算法具有较弱但仍然不变的近似因子。这包括Thorup的工作解决了稀疏图中的位置问题[40]和Mettu和Plaxton [33]对连续使用的问题交换公制k均值问题。与我们最密切相关的工作是近期，Korupolu，Plaxton和Rajaraman [29]，Charikar的度量k-中值问题的模拟算法和Guha [9]和Arya等人[5]。这些算法基于本地搜索，即逐步地通过将少量的点插入和移出解决方案集来改善可行的解决方案。
在本文中，我们提出了一种基于简单交换的k-均值的近似算法处理。在第2节中，我们推导出近似比为（9 ɛ）为启发式我们的方法是基于的关于Arya等人提出的k-中心的启发式[5]。然而，由于k-意味着问题，分析是不同的，并且依赖于k-均值特有的几何特性问题。在第3节中，我们显示这个边界对于本地搜索算法类来说基本上是紧的这是基于执行一定数量的互换。具体来说，我们举一个例子基于执行固定数量的互换的任何方法都不能达到近似因子在所有足够高的尺寸上优于（9-ɛ）。
高达9的近似因子几乎没有实际价值。尽管如此，我们认为，本地搜索和现有方法导致具有性能的实际近似算法担保。在第5节中，我们提出了一种基于局部搜索的混合近似算法劳埃德算法。我们提供经验证据表明，这种混合算法提供的结果无论是在失真和运行时间方面，与劳埃德算法一样好或更好。
2本地搜索算法
给定u，visin;令表示这些点之间的欧几里德平方，即
其中u·v表示向量u和v的点积。给定有限集Ssub;，定义其失真相对于任何点v为。
考虑在和整数k中n个数据点的集合P。 给定任意一组k点集S，对于任何qisin;,将定义为S到q的最近点。 我们的目标是计算最小化S相对于P的总失真的k元素点集合S，定义为
当P被理解时，我们将简称为。
将度量k-中值问题的现有方法扩展到k-均值的主要困难那个平方距离没有定义一个度量，特别是它们不能满足三角不等式，其中指出，对于任何点u，v和w，。 考虑平方时我们有距离
=
对于任何a和b，最终产品术语可以通过观察来界定。所以我们有以下加倍的三角不平等。
生成k-means的局部改进启发式的一个显而易见的概念将是推广Arya等人的方法[5]对于使用这个双重三角不等式的度量k-中值问题。 Unfor-好在这一点，似乎并不奏效，因为他们的分析依赖于三角不平等。在特别地，当三角不等式为原因时，在分析中产生的术语的取消失败一倍。
我们的做法是基于两个思路：第一是引入三角不平等的替代方法，这与双重三角不等式不同，对最优和启发式解决方案的比例敏感（见下面的引理2.3）。第二个是基于众所周知的事实，即最优解是重心（参见[10]）。令表示s的邻域，即接近于s的数据点集合S.的任何一点。通过将点作为向量，重心属性意味着
质心解决方案的一个重要特性如下： 它表示计算扭曲的目的，一组点可能被视为一个集中在其上的点质量质心。 从直接操纵失真的定义可以看出，但是我们包括了证明完整性。
引理2.1 给定中的有限子集S，令c为S的质心。对于任何,
证明：通过扩大的定义，我们有
最后一步是从事实上，如果c是S的重心是零向量。
2.1 单交换启发式
为了说明我们的方法，我们首先提出一个简单的本地搜索，提供（25 ɛ）近似k-均值问题。我们的方法类似于其他本地搜索启发式设施中使用的方法
Charikar和Guha [9]和Arya等人的位置和k-中值[5]。
在k-均值问题的陈述中，这些中心可以放在空间的任何地方。为了申请我们的本地改进搜索，我们需要假设我们给出一组离散的候选中心C可以从中选择k个中心。如上所述，Matousek [32]表明可以采取C作为大小为的近似质心，可以在时间。从此以后，当我们使用术语“最优”时，我们意味着C的k-元素子集最低失真。
这种单互换启发式操作通过从候选中心中选择一组初始的k个中心S组成C，然后反复尝试通过删除一个中心sisin;S并进行替换来改进解它与另一个中心。令是新的中心集合。如果修改解决方案具有较低的失真，则替换，否则不变。实际上这个过程是重复直到连续运行一连串的掉期，没有显着的下降失真。通过扩展标准结果[5,9]可以看出，牺牲一个小因子ɛgt; 0在近似比例中，我们可以保证该过程在多项式数之后收敛掉期交易。
为了简单起见，我们假设当没有单个交换导致减少时，算法终止在扭曲。 这样的一套中心据说是一个稳定的。 令O表示k个中心的最佳集合，一组我们有k个中心的S是1稳定的
（事实上这是真的，不管是什么，但我们的分析只依赖于这种较弱的财产。）使用这个以及最优解是重心的事实，我们将确定本节的主要结果，如下所述。
定理2.1 令S表示k个中心的1-稳定集合，并且令O表示k个中心的最优集合。然后。
请注意，实际的近似界限大一些ɛ gt; 0，由于使用a引起的错误候选中心C的离散集合和上述的近似收敛标准。我们的分析在结构上与Arya等人相似。 [5]，但有两个显着差异。第一个是我们的捕捉中心的概念与他们的不同，是基于距离最近的中心的距离，而不是分配给中心的数据点的数量。第二个是他们的置换功能我们不需要pi;，而是依赖于最优解的重心特性。
对于每个最优中心oisin;O，令表示S中最接近的启发式中心。我们说o被捕获由请注意，每个最佳中心只有一个启发式中心捕获，但每个启发式中心可能会捕获任何数量的最佳中心。我们说一个启发式的中心是孤独的，如果它没有获得最佳的中央。分析基于构建一组交换对，考虑到失真的总体变化结果，然后应用公式（1）以上限制整体变形的变化。
我们首先将启发式中心和最优中心的同时分区定义为两组对于某些r，对于组和，对所有,使。对于每启发式中心s位数为mge;1个最优中心点，我们形成一组最优中心由这些捕获的中心组成。相应的启发式中心组合在一起与任何m - 1个孤独的启发式中心。（见图2）
划分 交换对
图 2：分析启发式和最佳分析中心和交换对。在左边，边缘表示捕获关系，右侧表示交换对。
我们生成交换对如下。对于涉及我们生成的一个捕获中心的每个分区一个由启发式中心及其捕获中心组成的互换对。对于每个分区包含两个或更多的捕获中心，我们在孤独的启发式中心和最佳中心之间产生交换对，所以每个最优中心只涉及一个交换对，每个孤独中心最多涉及两个交换对。很容易验证：
（1）每个最优中心恰好交换一次，
（2）每个启发式中心最多交换两次，
（3）如果s和o被交换，则s不捕获除o之外的任何最佳中心。
我们建立由任何这样的交换对导致的失真变化的上限规定数据点到中心S-{s}cup;{o}的可行（但不是最佳）分配。首先，将中的数据点分配给o，意味着变形的变化
每个点已经丢失了s作为中心，并且必须重新分配给新的中心。令表示最接近q的最佳中心。由于q不在中，我们知道ne;，因此通过属性（3）以上s不捕获。因此，在交换后存在最接近的启发式中心。我们将q分配给。因此，由于该再分配引起的变形的变化最多
通过组合所有交换对，由于最优分配和重新分配而导致的失真变化与等式（1）我们得到以下内容。
引理2.2 让S是一个k个中心的一个稳定的集合，并且令O是k个中心的最优集合
其中。
证明：考虑只是交换对。 方程式 （2）和（3）以及S为1-稳定的事实我们有
为了限制所有交换对中的总和，我们记得每个最优中心被恰好交换一次因此每个点q贡献一次到第一个和。 请注意，第二个和的数量总是非负（因为isin;S和s是S到q中最接近的中心）。 因此，将总和扩展到所有我们只能增加其值。 回
全文共23432字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[142956]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
