一种基于复合形粒子群算法的改进K—MEANS聚类算法

《一种基于复合形粒子群算法的改进K—MEANS聚类算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7卷第lO期软件导刊V01．7NO．1O2008年lO月S0ftwareGuideOct．2008一种基于复合形粒子群算法的改进k—means聚类算法易云飞，吴启明，唐凤仙(1．中南民族大学计算机科学学院，湖北武汉430074；2．河池学院计算机与信息科学系，广西宜州546300)摘要：针对k—means算法事先必须知道聚类的数目，难以确定初始中心以及受异常点影响很大等缺点，提出了一种改进的k—means聚类算法。改进后的算法首先使用复合形粒子群算法来选取聚类的初始中心点，然后使用k-means算法快速收敛获取聚类结果。Iris测试数据集的实验结果表明了改进后的算法能够

2、合理区分不同类型的簇集，可以有效地识别异常点，具有较好的性能。关键词：复合形法；粒子群优化算法；k-means算法；聚类中图分类号：TP312文献标识码：A文章编号：1672—7800(2008)10—0046—02(1)所示：0引言Cn∑∑p(1)j=lk=l聚类分析是数据挖掘领域重要的研究课题之一。所谓聚其中，j=l，2，⋯，c；mj~C个聚类的中心，它的值为簇Ci的均类．是指根据输入记录自身的属性和相互间的关系，把具有高值，即相似度的对象放在一个簇里，同时尽量把具有高相异度的对象放在不同的簇中的一种技术。k-means聚类算法是应用最为广=∑(2)泛的聚类算法之一，

3、因为它具有较低的计算复杂性、收敛速度，k=lk-means算法的处理过程：快以及能处理大数据库等优点。但是，该算法也存在着不足之处：k个初始聚类中心点的选取对聚类结果有较大的影响，同时(1)从n个数据对象集x，xz，⋯，X}中随机选取k个对象{y。，y2，⋯，Yk}作为初始聚类中心；由于该算法是采用梯度法求解极值，结果可能只是局部而非全(2)计算各对象到中心对象的距离，并根据最小距离重新局最优。划分：考虑到k—means算法的先天不足，本文提出了一种基于粒(3)更新簇的平均值，即计算每个簇中对象的平均值；子群和复合形法的改进的k均值聚类算法(Complex—PSOand(

4、4)循环(2)到(3)，直到每个聚类不再发生变化时算法终k—meansClusteringAlgorithm)，简称COPSOK算法。改进后的k—止。means算法可以选择适当的初始聚类中心点．同时也能得到更从算法流程不难看出，用该算法来聚类时，当结果簇是密好的聚类结果。集的。而簇与簇之间区别明显时，它的效果较好。对处理大数据1k—means聚类算法集，该算法是相对可伸缩的和高效率的，因为它的复杂度是0(nkt)，其中，n是所有对象的数目，k是簇的数目，t是迭代的次k—means算法的基本思想是，以k为参数，把n个对象划分成数。通常k“n且t”n。这个算法经常以局部最优结

5、束。但是，k—C个簇。以使簇内具有较高的相似度，而簇间的相似度较低。相means算法得到的聚类结果受初始时聚类中心对象的选取的影似度的计算根据簇的重心．其值用簇中各对象的平均值来计响很大，随机选取的不同的初始值可能导致不同的聚类结果，算。首先从数据集中随机选取C个点作为初始聚类中心，然后甚至可能出现得不到有意义的聚类结果的情况。另外，由于该对剩余的每个对象，根据其与各个簇中心的距离，将它赋予最算法是采取梯度法求解极值，而梯度法的搜索方向是沿能量减近的簇。重新计算每个簇的平均值来找簇的重心，如此反复，直小的方向进行的，所以得到的结果往往是局部最优而非全局最到准则函数收敛为止

6、。通常采用平方误差准则，其定义如公式优基金项目：广西教育科学课题(2006A—E004)；中南民族大学大学生科研创新基金项目(cxcy2008003y)；河池学院课题(2007B—N004)作者简介：易云飞(1981~)，男，广西资源人，中南民族大学硕士研究生，河池学院计信系讲师，研究方向为数据挖掘、智能计算、网络安全；吴启明(1973~)，男，湖南浏阳人，硕士，河池学院计信系讲师，研究方向为数据挖掘与用户兴趣建模；唐凤仙(1977~)，女，广西都安人，硕士，河池学院计信系讲师，研究方向为软件工程与人工智能。第l0期易云飞，吴启明，唐凤仙：一种基于复合形粒子群算法的改进k

7、-means聚类算法·47·搜索能力很强，但结果全局性较差。算法中的每一步都寻找一2复合形粒子群算法个较好点取代最差点，若未找到就剔除最差点。本文将复合形法作为一个算子对粒子群算法中的粒子进行运算，以充分发2．1复合形法挥两种算法的优点，在更有利于最优搜索的基础上，构建复合复合形法(ComplexMethod)是一种常用的直接搜索方法，形粒子群算法。该算法只需通过直接比较和利用各设计点的约束函数和目标2．4基于复合形和粒子群算法的改进k—nlealtlS算法函数本身的值来进行搜索，每一步都寻找一个较好点取代最差本文提出的基于复