论文研究-粒子群K-means聚类算法的改进.pdf

所需积分/C币:40 2019-09-13 00:18:56 581KB .PDF
收藏 收藏
举报

粒子群(PSO)与K-means结合是聚类分析中的重要方法之一,但都未考虑粒子更新导致的空类问题。提出基于多子群粒子群伪均值(PK-means)聚类算法,为该问题的解决提供一种有效途径,并与粒子群K均值(PSOK-means),K-means算法进行比较。理论分析和实验表明,该算法不但可以防止空类出现,而且同时还具有非常好的全局收敛性和局部寻优能力,并且在孤立点问题的处理上也具有很好的效果。
沈艳,余冬华,王昊雷:粒子群K- means聚类算法的改进 2014,50(21)127 殖得到子代,用N个子代粒子作为N组均值初始中心。 2.5 (5)每一个粒了选择离均值初始中心最近的数据样 2.0 本对象作为新的簇中心。 1.5 (6)将数据样本集中每个数据对象(再)指派到最相 似的簇。 1.0 (7)计算每个簇的均值。 0.5 (8)对于钶个簇的均值中心,选择离其最近的数据 对象作为新的簇中心 (9)判断屮心点是否稳定,如果稳定,进行聚类,根 长度 图1部分Iris数据集聚类为空示意图 据聚类结果得到新一组N个粒子的粒子群并计算其适 应度值。然后转向(10),否则,转向(5)。 中心为 对应坐标值为(1.4.0.3),(3 (10)比较适应度值。通过对比父代与其子代的适(60,1.2),此时聚类中心x2所对应的类会成为空类, 应度值大小,更新局部最优粒子p,同时比较所有的父采用仍均值聚类后,会选择与聚类中心点最近的样本 代与所有的子代适应度值。选取最大适应度值作为全点允当伪均值,即图1中的x,x2,x3,对应坐标值为 局最优粒子p (14,0.3),(1.9,0.4),(6.0,1.8),而这三个聚类中心必定 (11)判断全局最优粒子n是否满是结束条件,不属于不同类别且均为样本数据点,故不会出现空类。 满足转向(3),否则,结束程序,输出聚类结果。 4.2Iris与wine数据集聚类仿真 为了从实验方面验证PK- means算法的聚类效果 4实验仿真 下面对UCI(htp:/ archive.ics. uciedu/ml/)上的Irs和wine 数据进行实验.该数据均可分为3类。其中Iris数据选 4.1聚类为窄实例 取其第三与第四维属性值( petal length, petal width) 在离散的样本点中,采用连续化方法选取中心点而wie数据选取其全部的13个属性值,对于Iis数据点可 不加处理,就可能导致某个中心点的聚类结果为空类。 以在平面用散点图反映,见图2。 采用粒了群(PSO)方法优化的 K-means方法就存在这个 问题。下面将取lris数据集中部分点(取72个样本,分 别来自3个类别)作为例子说明聚类结果为空是可能的 将该72个点划分为3类,此时粒子的可能解区域为 2.0 理 矩形域[.0,6,9x0.1,2.5,某一次粒子更新后,有两个 中心点分别为G,G,,以G,G,为圆心,以能够包含所 有点的最小半径r,2作圆,然后再以G,G2为圆心,以 2r,2r2作圆,划分出的区域如图1,而第三个中心点因 粒子更新进入了区域G,聚类完成后,第三类将成为室 类,因为任何一个数据点此时与第三个中心点的距离必 花瓣长度 定大于min{r1,r2,故该数据点一定不会指派到第三类。 图2Iris数据散点图 而伪均值算法将不会出现这和情况,如果采用 使用PK- neans对lris数据和wine数据聚类吋参数 K-means计算出均值落入区域G,所寻找的伪均值就是设置如下:类数K=3, PK-means算法中的参数,N=10, 离该均值最近的一个样本点作为新的中心点,至少该点P=0.5,c1=0.2,c2=1,c1=0.5,c=0.5,,m=0.8 属于样本集,如假设初始化中心点或粒子更新后的聚类mmx=1.2。在表1中,给出了聚类次数与lrs和winc的 表1分类结果 错分数 算法 ris数据初始聚类中心 Iris数据集winc数据集 K- means1(1.125,0.175)(1.523,0.270)(4.925,1.682) K- means2(1.810,0385)(4.161,1,267)(5281,1.861) 2770,0.752)(5.133,2.100)(5.706,1.942) (1.810,0.385)(4413,1,374)(5.549,2024) 57 PSOK- Ineans(1.540,0.431)(4.502,2010)(4.701,2.110) PK- means(1.500,0.200)(4300,1,300)(5600,2.100) 6 128 014,50(21) Computer Engineering and4 pplications计算机工程与应用 各自的错分点个数,由于wine的属性值比较多,故表中数据集的第三个类只有一个数据点,该点正是加入的那 只给出了相应的Iris的初始中心点,PK- Ineans算法的最个孤立点,而对于其他的数据分类,错分数分别为6个 优初始中心点分别为样本集中第49个,第98个,第129与18个,并没有因为加入了狐立点而影响到分类效果。 个数据点,其中, K-means聚类结果参照文献[10。从表1如果有必要,可以将分离开的孤立点剔除,然后再重新 可以看出,K- means对初始中心点的敏感程度非常大,分类。 虽然错分数可以接受,但是PSOK- mcans、 PK-mcans无 论是从对初始中心点的依赖稈度,还是在分类的准确程5结论 度上,都能够好于K- means算法,有效减少了聚类的随 PK- mcans算法综合了k- mcdaid算法和行粒子 机性,PK- mcans与PSOK- mcans具有相同的效果,并没样算法思想,在理论和实验上验证了该算法在克服初始 有因为引入伪均值而降低聚类最终效果。 屮心点,局部极小,防止空类及处理孤立点问题上,都能 为了反映出多子群粒子群在算法中所起的作用,使收到很好的效果,并且在理论上论证了聚类结果非室的 用某次聚类过程中全局最优粒子更新代数和公式(5)的间题。此外,PK- means算法的收敛速度也很快,聚类的 适应度函数值,画出初始中心点的调整(即粒子代数)与结果很稔定。值得指出,伪均值同样可以与混沌粒子样 适应度函数值之间的曲线,如图3。mis粒子适应度值每变异粒子群及量子粒子群聚类算法结合,防止空类又不 次改变,都说明多子群粒子群找到了更优的初始中心影响聚类准确性。 点,即跳出了局部极小点,而Wine粒子的适应度值为直 线,说明在初始化时,就已经找到了最优初始中心点。这参考文献 也说明,加入的多子群粒子群算法起到了相应的效果。[刘靖明,韩丽川,侯立文基于粒子群的K均值聚类算法[ 系统工程理论与实践,2005(6):54-58 Swarup K s Particle swarm optimization based -means clustering approach for security assessment in power systems[J Expert Systems with Applications, 2011 38:10839-10846 30.5 [3 Li Y R, Zhu YY, Zhang C NThe K-means clustering 30.0 lgorithm based on chat 29 +lris数据集 Theoretical and Applied Information Technology, 2013 9.0 Wine数据集 48(2):762-767 28.5 78 4]王东,罗可基于变异粒子群的聚类挖[计算机T程与 粒子代数 应用,2011,47(21):130-132 图3Iris与winc粒子更新代数与适应度值关系 [S]叶安新,金永贤基于量子粒子群算法的聚类分析方法[ 对于含有孤立点的数据来说,适当增加类数,即K 计算机工程与应用,2012,48(32):52-55 值,一般可以把这些孤立点单独聚成类,而并不会影响 [6 Cheng M y, Huang k Y, Chen H MK-means particle swarm optimization with embedded chaotic search for 数据分类,对于Iris数据,增加(14,0)与(20,0.2)两个 solving multidimensional problems[J].Applied Mathematics 点,这两个点很明显超出了原有数据的属性值范围而成 and Computation, 2012, 219: 3091-3099 为狐立点,对于wime数据增加点(0,0,0,0,0,0,0,0.0,[7] Masoud h,Jlis, Hasheminejad s M H Dynamic clus 0,0,0,0),然后将增加了孤立点的数据聚成4类,结果 tcring using combinatorial swarm optimization [J]. Applicd 如表2。 Intelligence,2013,38:289314 表2加入孤立点后聚类结果 [8 Lin Y C, Tong N, Shi M J, et al. K-means optimization clustering algorithm based on Particle Swarm Optimiza 数据集 数据点个数 第一类第二类第三类第四类 错分数 tion and multiclass merging J. Advances in Computer S ence and Information Engineering, 2012, 168: 569-578 Wine 55 73 50 [9]闫允一.粒子群优化及其在图像处理中的应用研究[D]西 安:西安电子科技大学,2008 从表2可以看出,Iis数据集的第一个类只有两个[10连风娜,吴锦林,唐琦.一种改进的 K-means聚类算法门 数据点,恰为加入的孤立点(14,0)与(20,0.2),而wine 电脑与信息技术,2008,16(1):3840

...展开详情
试读 4P 论文研究-粒子群K-means聚类算法的改进.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    img
    • 至尊王者

      成功上传501个资源即可获取

    关注 私信 TA的资源

    上传资源赚积分,得勋章
    最新推荐
    论文研究-粒子群K-means聚类算法的改进.pdf 40积分/C币 立即下载
    1/4
    论文研究-粒子群K-means聚类算法的改进.pdf第1页
    论文研究-粒子群K-means聚类算法的改进.pdf第2页

    试读已结束,剩余2页未读...

    40积分/C币 立即下载 >