MinMax k-Means算法
引言
应用k-Means去极小化内部聚类方差的和是一种最受欢迎的聚类算法。当选择了一个不好的聚类中心以后，就包含了一个不是最佳的本地状态。为了处理k-Means的初始聚类问题，我们提出最小最大k-Means算法，是一种根据聚类的方差和k-Means的客观权重，给聚类分配权重的方法。通过一个迭代的过程。提出的权重计划限制了大方差聚类的出现，并允许一个高质量的方法被系统都包含，不会被初始聚类中心影响。实验证明了在一个不好的初始聚类中心条件下我们方法的有效性和鲁棒性，并且顺利的比较了k-Means和其他文献中的方法关于初始聚类中心的问题。
1.简介
聚类是出现在各个领域的一种基本的数据分析问题，比如模式识别,机器学习,生物学信息和影像处理。它的目的是在均匀的分组中区分一系列实例。比如说，通过一些客观的聚类，内部聚类的相似性有高有低。然而，耗尽心思的去寻找一个聚类实例的最佳分配是不能通过计算得到的,并且通常一个客观上本地最佳的聚类状态是已被找到的。
其中一个研究最充分的算法是k-Means算法，它极小化了内部聚类的方差，这种方法非常的简易和有效，作为一种受欢迎的方法去执行各种不同学科的聚类，甚至扩展到一个核心领域被发现：能够实现非线性分组的聚类。尽管这种方法被广泛接纳，但肯定是有一个严重的限制。这种方法严重依赖于聚类中的给定的初始点，因此当选择了一个不合适的初始聚类中心，很容易得到一个局部的极小值而不能得到整体的极小值。为了减小这种缺点带来的影响，清明是在实践中常用多种随机选择聚类中心重新开始的方法。
很多方法尝试用一种更有原则性的方式去克服初始聚类中心的敏感性问题。第一组方法应用了一种独特的技术，系统的躲避了在重新开始时选择不好的聚类中心。在[8]号文献中，随机的选取初始聚类中心以达到包含全部数据空间的目的，理论上保证了方法的兼容性和近似地生成了一个最佳聚类。两种方法从一个随机的聚类中心开始，并且使聚类不利于关联它们的出现频率，发表在[9,10]号文献中。不利于聚类当很多点已经被分配好的时候在后来的步骤中吸引一个新点。聚类中心一开始被选错并且没有在之后的步骤被充分利用，就会导致异常值聚类的生成并且影响聚类尺寸的平衡。其他方面，类似的策略记载在[11,12]号文献中。
第二组方法尝试去消除随机条件的依赖性，因此，重新开始不再是必要的。全球的k-Means算法[13]，修改了增量的算法，从一个单一的聚类开始并且每一步产生一个新的聚类，通过一个适当的标准添加在方法中。有一种基于内核版本的全球k-Means算法也可以在[16,17]文献中找到。在[18]号文献和它的扩展[19]号文献中，光谱聚类被应用去定位全球的最佳状态关于一个不拘束的版本，关于客观k-Means。通过把问题公式化去计算痕迹的极大值。尽管这些方法不易受不好的聚类中心影响，但他们的计算代价也变得更加昂贵。
在这篇文献中，我们提出了MinMax k-Means算法。一种新奇的方法通过客观的变更初始聚类中心处理了 k-Means初始聚类中心问题。我们的方法从一系列聚类中心中随机选取一个开始，尝试去极小化内部聚类方差的极大值而不是简单的叠加内部聚类的方差。特别地，权重关系到每个聚类，所以聚类有更大的方差就分配到更大的权重，并且权重是由初始聚类方差叠加标准衍生出来的。关于权重的不同观念被开发出来，在文献中通过很多 k-Means变量展现出来。在模糊的c-means和高斯混合模型中[20]，权重被用来去计算聚类中实例资格的度，在其他变异体中，权重被设置成特征变量或一组特征变量，所以聚类的任务和特征变量的选择是同时执行的[21,22]。同样地，在[23]号文献中，为了检测异常值，权重向量被添加在每个实例中。
每个聚类权重预先处理我们算法指向的主要的极小化这些聚类当前展示的一个巨大的方差。在本质上限制了一个大聚类方差在结果中的出现，并且自动学习聚类分配。提出的这个方法接替了类似 k-Means算法中的极小化步骤，并且附加了极大化步骤，权重通过一个封闭式的表达式计算。通过应用这个权重机制，我们发现了结果受到初始聚类中心的影响变得更加的小，并且方法的高效性得到了一致的赞同，甚至从一系列不恰当的初始聚类中心开始。另外，被包含的聚类在考虑到他们方差的情况下也得到了平衡。
当前的算法也包含一个参数p，它的值必须在执行前被优先指定，他调整了偏离指向大方差聚类不利的度。当p等于0时， k-Means算法可以被证实为一个零偏移的特殊实例。一个实际的框架继承MinMax k-Means算法去自动的适应数据集中的这个参数p，可以成功的隐藏数据中的组结构。 实验被管理在很多不同的数据集中，包含图像，手写数，蛋白质和病人记录。MinMax k-Means算法相比于k-Means算法，也相比于k-Means [8]和pifs k-Means[10],避开了最佳状态的退化，首先是通过有系统的选择初始聚类中心，第二步通过平衡距离尺寸来达到。我们根据经验评价被提议的聚类计划显示出的有效性在限制大方差聚类的出现和产生了一个优秀的方法层面上，相比于其他三种方法，当从随机选取的初始聚类中心重新开始的时候。此外。我们观察到我们的算法形成了一种在初始化k-Means的时候非常有前途的技术。 这篇文献的其他部分有以下几部分组成。我们接下来主要描述k-Means。在第三章节提出MinMax k-Means算法以及它的属性和分析。第四章介绍了我们设置参数p的实际框架。实验部分在第五章，在总结标记前是第六章。
2. k-Means
为了区分一个数据集在m中解体聚类，，k-Means极小化内部聚类的方差，当和，是方差的平方并且是第k个聚类的中心，分别的，是一个聚类的可变指标，如果和0或者其他的.聚类过程通过可供选择的封闭集中心的分配实例并且重新计算中心，直到取到一个本地的极小值。
（1）
聚类过程通过可供选择的封闭集中心的分配实例并且重新计算中心，直到取到一个本地的极小值。尽管它是简单和快速的，k-Means仍然存在一些缺点，最突出的就是依赖于初始中心的选择[6,7]。不恰当的距离中心会导致一个不对的极小值，因此，多种随机重新开始的方法通常被用来解决初始聚类中心问题。经常的，这个方法根据一些有意义的变异达到一个客观的值，范围是从一个最大值的最小值，尤其是当问题的搜索空间很大的时候。因此，算法的多次运行被用。来增加取到局部最小值的可能性。
3.MinMax k-Means
我们在第二章已经讨论过，k-Means初始聚类的敏感性和多种多样的方法没有包含在重新开始的时候，使他很困难的对一个数据做好的区分。通过这个动机，我们提出一种新的方法论，允许k-Means去增加系统的产生一个高质量的区分，在随机选择聚类中心重新开始的时候。
3.1客观最大方差
考虑到一个数据集去分离进m解体聚类，，而不是极小化内部聚类方差的总和，我们提出去极小化内部聚类方差的最大值。
（2）
，和在(1)式中已经定义
以下是这个方法的运行原理：综合覆盖在所有区内在客观k-Means中允许相似的值被达到，也通过产生一个很少的聚类，当方差很大在技术平衡的时候通过其他小的方差，或者通过所有聚类中的一个中等方差，这意味着，一些聚类方中的相关差异也没有被计算在公式中。聚类的方差是对它本身质量的一种衡量。以上的标记不支持极小化的时候，以上的第一个例子将会导致一个更高的客观值。因此，当极小化也不许的时候，大方差聚类将会被躲开并且方法的解空间严格的指向聚类显示的更相近的方差。 先前的观察有两种重要的含义，因为k-Means极小化了的值，它不能区分两种事例，因此当选择了一个不恰当的聚类中心以后，一个不好的方法实质上以返回值中的不同方差为特点，自然分组(大聚类方差)被融合并且其他的分组(小聚类方差)被分离，或异常值聚类被加工。如同以上的解释，内部聚类方差的客观极大值，不像其他方法一样聚集起来，因此它更容易克服一个不恰当聚类中心所带来的缺点。因此我们希望一个k-Means类型算法组合这个客观值去覆盖更好的组结构在重新开始的时候能一致协调，在图1中举例说明。 另外的，一个平衡影响的聚类出现了，文献中记载了用不同的方法平衡结果，比如说，在[10]k-Means和球形的k-Means被改进在实例数比例分配给他们的时候使聚类不利。在[24,25]，一个图标分割标准的最佳状态是支持了创造了一个子图，当边缘权重的总和在子图了中的时候是相近的。在我们的例子中，平衡已经用聚类的方差被完成而不是聚类实例的数量。当许多真实生活中的应用要求区分可比较尺寸的子集数据分析的时候，这是一个客观提出的好的、可想到的属性，已知的k-Means算法趋向于曲解一种方法，例如，聚类有多种多样广泛的实例或者空的聚类，尤其当一个数据有许多维度或聚类，因此在这个实例中解空间被极大的扩张。
3.2一个不严格的客观最大方差
尽管有上述的优点，直接极小化内部聚类方差的最大值容易造成重大的最佳状态问题。为了处理这个问题，因为目标是不严格的，所以他可以无困难的在k-Means迭代过程中最佳化。特别的，我们构建了一个权重公式，关于内部聚类方差的总和（3），更重要的是，例如一个更高的权重用一个大方差代替放在聚类中，去模仿极大化方差的标准（2）。
（3）
对比于，现在，所有聚类在客观上都是有帮助的。虽然通过的值规定不同的度，明显的，当一个权重方差越大的时候，他方差被极小化的时候反应就更加强烈，用这种方法，把大方差极大的减小在客观上变成了可能的，权重不是一个常量，但是参数必须在聚类标准中被设置成最佳状态，我们对待权重像方差一样去允许他们的值精确到反应的方程再训练和驱使他们去叠加个体去躲避过度粘合，并且得到一个有意义的最佳状态问题，p指数是一个使用者指定的常数，并且从0到1中间选择，并且控制了权重升级的敏感性对相对聚类方差的区别。比如说，他们不同之处的强烈程度通过权重反映出来，我们提供一个更内部的客观的解释p的角色。
聚类的通常目标是区分小方差的内部聚类并且与此同时防范大方差聚类的出现，也是一样。为了客观上不严格地使大聚类不利，一个更大的方差导致了一个更高的权重，这可以被意识到通过极大化反映到它的权重里，最佳状态问题就变成了表格中所显示的最大最小问题。
min max,
s.t. (4)
我们提出的迭代算法叫做MinMax k-Means算法，它提供了一个可供选择的，在和最佳状态步骤之间去得到一个局部的最佳状态，并且相应的派生和提出。标记p是不是最佳状态，而且必须被优先适配。
3.2.1极小化步骤
通过保持权重适合新的聚类分配，并且代表的可以被计算出来，对于这个设置，考虑到的计算涉及到距离指示符对第k个实例并且独立于其他实例，最佳状态被直接给出。
（5）
因此每个设置的聚类的实例从权重距离到代表实例是最小的。而且，他证明了权重是增长的，只有非常接近于代表着的实例被设置成第k个聚类
为了估计代表值派生出一个关于的客观公式，从零开始
（6）
同样对于k-Means，代表值与聚类的圆心相一致并且独立于权重。
3.2.2极大化步骤
为了升级已给出聚类设置好的权重和中心，权重约束(4)被包含在拉格朗日乘法器和由从零开始派生出的式子，很容易证实，客观上的限制是凹进去的，关于权重当时，因此他们的最佳值极大给出当前的区分可以被肯定。经过以下的操作出现：
（7）
当，同时又有，可以被观察到之类的方差越大，权重越大
3.3讨论
在这个章节，MinMax k-Means算法的一些方面在许多细节的分析上客观上(3)是不严谨的。通过(7)，对于一个给定的数据分类权重和聚类的方差是成比例的。在后来的极小化步骤中，聚类实例的设置用权重距离聚类中心来代表。明显的，对于高权重聚类，实例中派生出的代表值的权重距离是增长的。因此，一个大方差聚类将会失去很多当前的实例由此导致他们远离中心并且方差被期望是减小的。与此同时，小方差聚类，由于权重比较小，也可能获得不靠近他们中心的实例并且它们的方差将会增加。因此，MinMax k-Means算法的异常值处理过程，将会惩罚一个大方差聚类并且指向相近方差的聚类，像最小化客观方差(2)的好处被体现出来。
关于p的值，提出最自然的选择是。对于估算权重的式子简化成
（8）
明显的，只有当高方差聚类的迭代过程中达到一个非零的权重
全文共8100字，剩余内容已隐藏，支付完成后下载完整资料
英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[13723]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
