基于cs搜索的K-均值算法简介

1、基于cs搜索的K-均值算法简介在各种智能算法发展迅速的今天，算法优化问题变得愈发重要，在数据挖掘学习中， 普通的K-均值聚类算法过于依赖初始质心的选择而增加了计算的复杂度。本文首先介绍了 cs算法的发展历史和论文的研究背景，并给出了几种改进的cs算法，由于cs算法具有搜索速度快，选择路径优，包含参数少等优点，将其应用到K-均值模型中，解决了K-均值模型依赖于初始聚类质心，算法效率低，易受噪声，孤立点干扰的缺点；本文的 创新点是将cs算法跳跃性强，不易陷入局部最优的优点与K-均值算法结合，有效的提高算法的搜索速度，在算法初期进行多次cs迭代，提高了初始质心的计算速度，防止初始质心过早地陷入局部最

2、优，避免了大量不必要的计算，对算法的效率有了大的提高。 最后，对于算法改进进行了总结与展望。关键词：cs算法；Levy飞行；K-均值III第一章绪论1.1 研究目的及背景优化是工作计划阶段的一项重要工作，对于优化问题我们最关心的就是效益 和时间代价，但是20世纪70年代，在软件设计规划，工业生产，资源调度，物 流配送等众多领域都出现了大量的 NP完全问题，所谓NP完全问题，就是人们无 法在有限的时间和空间内找到问题的最优解，这使得优化问题遇到很大的困难。 目前的研究工作主要集中在如何快速高效地寻求这些问题的最优解，这对我们的工作生活都有重要的意义。到目前为止，对于 NP完全问题已经形成了相对成

3、熟 的理论与方法体系，如近似算法，动态规划法，贪婪算法等等。但是后面出现的 元启发式算法解决这些问题更高效快捷，如蚁群优化算法，萤火虫算法，模拟退火算法，这些方法得出的结论被大量实际问题所证实。我们将很多智能算法结合起来也可以使其进一步优化，在这里，我们选择将cs算法的一部分融入到K-均值算法中，由于传统的K-均值聚类算法的质心是随 机选择的，因此对于有的数据来说该算法容易达到局部收敛从而影响到整个过程 的聚类，因此，我们这里提出的改进聚类算法旨在改变算法选取初始质心的方法， 选择更理想的初始聚类质心，这时候，不易陷入局部最优的cs算法就起到了关键的作用，本文就是利用这种算法对 K-均值算法进

4、行了改进。1.2 算法介绍遗传算法(genetic algorithm)是源于达尔文的进化论的一种智能算法，在 1975年，它第一次被美国的J.Holland教授提出来。根据描述，在这个算法中， 个体组成了种群，他用算法的解替代了一个个生物个体， 每个解都对应了一个函 数。根据遗传学原理，物种的繁殖就是不断的重复计算这些解，若干代以后，遗 传算法收敛，产生一个最优解。因为解空间的无限性，它能够产生很多局部最优 的解，参考物种的生殖，经过很少的迭代就可以产生最优解，因此它是非常好的优化算法。遗传算法有目标函数，通过对解的计算限制可以推导出它们的目标函 数，通过重复这个过程计算出最优解。 这个算法

5、将计算变成编码。通过编码可以 有效解决不同的计算问题，减少算法的运行时间。这种通过生物得到的遗传方式， 我们可以进行基因的几种改变方式。 总体来说，这种算法在收敛性还有全局最优 解计算方面还有很大的改进空间。它的流程是：1：确定种群的规模为N ,交叉概率为Pa,变异概率为自，算法的终止条件， 随机生成N个个体作为初始的种群x (0),计算x (0)中的个体的适应值，令 t=0 02：从X (t)中选择母体，对选择的母体以概率 Pa进行配对，形成中间个体， 再对中间个体以概率Pb进行变异，构成新的种群X (t + 1)。3:计算新种群x (t + 1)中个体适应值。4：判断是不是满足终止条件，如

6、满足终止条件，则终止计算，输出最优解，不 然令t = t + 1,返回2。遗传算法具有较好的全局搜索能力，能快速的搜索出最优解，而不会陷入局 部最优解，因此其局部搜索能力较弱，容易出现早熟的现象，由此引发了大部分 学者的研究，有的改进改善了算法的搜索时间，有的提高了算法的收敛速度。1.3 本文研究内容本文的主要研究内容如下：(1)介绍了 cs算法的发展历史和论文的研究背景；(2)将cs中的莱维飞行原理应用到K-均值模型中，解决了 K-均值模型依赖于初 始聚类中心，易受噪声，孤立点干扰的缺点；(3)为了有效的提高算法的搜索速度，在算法初期进行多次cs迭代，避免了大量不必要的计算；(4)总结与展望

7、。本文研究的K-均值 聚类算法是在数据挖掘的聚类过程中可以称作比较经 典的算法，由于算法自身的特点，它的算法简单易理解，复杂性低，运行效率高， 在很多聚类分析的领域中都有广泛的应用。 原来的K-均值算法受限于几个方面， 主要是对于大型问题如果初始质心选择不当，可能会增加很多计算量，而且如果 数据点的分散性不好，也容易陷入局部最优的困境。这两点对于算法的伸缩性和 有效性都产生非常大的影响，制约了算法的进一步发展。本文将 cs算法的核心 内容加入到了 K-均值算法中，由于cs算法中Levy行走模型具有很强的跳跃性 和不确定性，因此它不会产生局部收敛，将它的这个特点应用到传统的K-均值算法中可以在算

8、法选取初始质心时优先选取更符合最终结果的质心，而且它不易陷入局部最优，对于各种类型的数据分布都有很好的解决。4.2展望K-均值算法作为一种解决聚类问题的经典算法，它是相对高效和可伸缩的，并且对于密集簇和凸型聚类都有很好的效果，当然，改进之后的算法也有很多可以继续优化的地方，比如怎么减小离群点对于聚类的影响，如何更好地确定K的取值，对于非凸类型的聚类如何去分析，这都是以后将要重点研究的方向。参考文献【1】 苏芙华，刘云连，武铁斌.求解无约束优化问题的改进布谷鸟搜索算法.计算机工程，2014, 10003428(2014)05 0224 02 Bertolazzi E.Trust Region M

9、ethod J .20053 Xu Z, Hou X, Sun J. Ant algorithm-based task scheduling in gridcomputingC/Electrical and Computer Engineering, 2003. IEEE CCECE 2003.Canadian Conference on. IEEE, 2003, 2: 1107-1110.【4】 侯慧超，布谷鸟优化算法改进及与粒子群算法融合研究，2014【5】 钱伟懿，侯慧超，蒋守勇，一种新的自适应布谷鸟搜索算法.计算机科学，2014,10.11896/j.issn.1002-137X.20

10、14.07.058【6】宋玉坚，叶春明，黄佐钮，基于克隆布谷鸟算法的资源均衡优化.计算机应用研究，2014,1001-3695 (2014) 05-1324-04【7】冯登科，阮奇，杜丽敏，二进制布谷鸟搜索算法.计算机应用，2013,1001-9081 (2013) 06-01566-05【8】郑洪清，改进布谷鸟搜索算法求解批量流水线调度问题.计算机系统应用，2014【9】肖辉辉，段艳明，基于差分进化的布谷鸟搜索算法.计算机应用，2014, 1001-9081 (2014)06-1631-05【10】刘逻，郭立红，基于结合自适应步长布谷鸟搜查算法的模糊神经网络的软件可靠性增长模型.计算机应用，

11、2014, 1001-9081 (2014) 10-2908-05.计算机应用与软件,2014 ,【11】屈迟文，基于决策者与带扰动因子的布谷鸟算法10.3969/j.issn.1000-386x.2014.07.075【12】郑巧燕，莫愿斌，刘付永，一种小规模多种群布谷鸟算法.计算机应用与软件，2014,10.3969/j.issn.1000-386x.2014.10.067【13】王李进，尹义龙，钟一文，逐维改进的布谷鸟搜索算法.软件学报，2013,2687-2698doi : 10.3724/SP.J.1001.2013.0447614 ANILKJ Data clustering : 50 years K-meansC.Department of Computer Science and Engineering,2009【15】 ARTHOR D, VASSIVISTIKY S.K-means+： The Advantages of Careful Seeding C.SODA Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms,2007:1027-1035【16】付德胜，周晨.基于密度的改进 K均值算法及实现J.计算机应用，2011