蚁群聚类组合方法参数m的研究

蚁群聚类组合方法参数m的研究韩强1，邢洁清11.琼台师范高等专科学校信息技术系海南海口571100ResearchcombinationmethodofparametermbasedonantColonyClusteringHanQiang1XingJie-qing11.DepartmentofModerneducationtechnology,QiongtaiteacherscollegeHainanHaiko571100,ChinaEmail:[e-mail]:Theant-basedclusteringparametervaluesindifferentcircumstances,oftenwillsolvetheperformanceandefficiencyofthealgorithmhaveasignificantimpact.Inthispaper,basedonantcolonyclusteringcombinationmethodbasedonthestudy,focusingontheantcolonyclusteringalgorithmcombinationmethodKMAOCantcolonyalgorithmparametersarethenumberofmpairsofKMAOCalgorithmperformanceinfluenceontheparametersofthealgorithmKMAOCthenumberofantsm,respectivelyexperimentalvaluesbyseveralgroupsofexperimentalverificationprovidesthebetterproposalthataKMAOCantalgorithmparameterstoconfigurethenumberofm.Keywords:Clustering；Antcolonyalgorithm;Pheromone;Clusteringcombination摘要：蚁群算法中参数在不同取值情况下，常常会对算法的性能和求解效率产生重大影响。本文在基于蚁群聚类组合方法的研究基础上，重点研究了蚁群聚类组合方法KMAOC算法中蚁群算法参数蚂蚁数m对KMAOC算法性能的影响，对KMAOC算法中的参数蚂蚁数m分别取值进行实验，通过几组实验验证提供了KMAOC算法中参数蚂蚁数m配置的较好建议。关键词：聚类，蚁群算法，信息素，聚类组合中图分类号:TP311;TP12文献标识码:A1引言聚类在科学数据探测、图像处理、模式识别、医疗诊断、计算生物学、文档检索、Web分析等领域起着非常重要的作用，它已经成为当前数据挖掘研究领域中一个非常活跃的研究课题[1].经典聚类方法包括分层算法，划分方法如K均值算法、模糊C均值算法，图论聚类法，神经网络法，以及基于统计的方法等[2].近来随着数据挖掘研究的深入，涌现了大量新的聚类算法，如蚁群聚类算法等.蚁群算法作为一种开创性的生物仿真算法，因其具有并行性、鲁棒性等优良性质得到了广泛的应用[3]。由于蚁群算法的研究历史还很短，在实际问题中应用还较少，因些存在许多有待进一步研究改进的地方，如需要设置的参数太多、参数的设置还有一定难度[4]。算法收敛性差和较长时间的花费.特别是运用蚂蚁觅食的原理利用信息素来实现聚类的蚁群聚类方法，如其信息素的值从0或相等值开始，各条路径上的信息素要想明显区别开，一般需要很长时间。研究表明蚁群聚类算法与K-means算法构成的蚁群聚类组合方法(KMAOC)能较好的弥补这些缺陷[5]。目前国内基于蚁群算法的组合算法研究也进行了不少，如杨燕等在文献[6]中指出为了改善聚类分析的质量提出了一种基于阈值和蚁群算法相结合的聚类方法。按此方法，首先由基于阈值的聚类算法进行聚类，生成聚类中心，聚类个数也随之初步确定；然后将蚁群算法的转移概率引入K-平均算法，对上述聚类结果进行二次优化。将上述两种算法结合，能够优势互补，避免单独应用一种算法时的局限性，而高尚等在文献[7]研究中提出克服从不同聚类算法的输出结果中求共识划分的困难，较好地基金项目:琼台师范高等专科学校科研项目(批准号:qtky2009-20)作者简介:韩强(1982－),男,助教,主要研究领域为计算机应用等;邢洁清(1977－),男,硕士,副教授,主要研究领域为软件应用，人工智能等;改善聚类质量。建立了聚类分析问题模型,分析了K-均值算法、模拟退火算法和基本蚁群算法的优缺点。对蚁群算法作了改进，思路是K-均值方法混合，利用K-均值方法的结果作为初值。经过比较测试，两种混合蚁群算法的效果都比较好，特别混合方法二的效果最好。本文基于KMAOC蚁群聚类组合算法的研究基础上仅对组合方法中蚂蚁参数m值进行讨论并进行实验分析。2K-means聚类算法与经典蚁群算法(1)K-means算法是基于划分的聚类方法，也是最常用的聚类算法.该算法不断计算每个聚类的中心，也就是聚类中对象的平均值，作为新的聚类种子.K-means算法试图找出使平方误差函数值最小的k个划分.当结果簇密集并且各簇之间的区别明显时，它的效果较好.处理大数据集时，K-means算法具有较好的可伸缩性和高效率[8].应用K-means聚类算法时当结果簇密集并且各簇之间的区别明显时，它的效果较好.但区别不明显时则效果较差.该算法的缺点是必须事先给出要生成的聚类数目。(2)经典蚁群聚类算法蚁群算法的特点[9]：1)蚁群算法具有很强的发现较好解的能力。由于算法本身采用了正反馈原理，加快了进化过程，且不易陷入局部最优解；2)蚁群算法具有很强的并行性，个体之间不断进行信息交流和传递，有利于发现较好解。单个个体容易收敛于局部最优，多个个体通过合作，可很快收敛于解空间的某一个子集，有利于对解空间的进一步探索，从而发现较好解。蚁群聚类算法存在的问题[5]：1).算法效率：蚁群聚算法的收殓过程比较缓慢.特别是在迭代初期，由于系统参数改变很慢，导致整个计算过程非常耗时.在基于蚂蚁觅食原理的聚类分析中，对各路径上的信息素的初始化，为简化操作，一般全都赋为相等的常量C(通常为0).因此，信息素的值从相等常量C开始，各条路径上的信息素要想明显区别开，一般需要很长时间.蚁群聚类算法与K-means算法构成的蚁群聚类组合方法(KMAOC)能较好的解决这一问题。2).初始值的选择：初值的选择对聚类的最终结果影响很大.而在经典蚁群算法中，确定初始参数时，一般缺乏已知的指导经验.初始参数的确定带有很大的盲目性.该聚类方法中α，β，m的选择对算法运行效率和聚类结果都有较大影响，选择不当将影响算法执行效率和效果，所需时间增长等缺点.可以根据情况尝试不同的方法避免算法陷于局部最优。本文将重点研究m参数对算法的影响。3基本蚁群算法参数及参数m研究蚁群算法中参数在不同取值情况下，对算法的性能和求解效率会产生重大影响。蚁群算法是一种自适应的、正发馈、分布式的模拟优化算法，它在求解各复杂的组合优化问题上表现出一定的优势，较好的α、β、ρ、m组合有较好的解质量以及好的稳定性，但如果对蚁群算法的参数选择不当，蚁群算法较快收敛到局部最优或较慢地收敛，对算法性能有极大的影响[10]。张杰慧等在文献[11]中就为了验证蚂蚁个数是不是越多越好的这一设想，选择了wpbc数据集作为实验数据。图1反应为选择不同蚂蚁数目时的实验结果，并否认了蚂蚁数目越多效果越好的假想,在其实验中就取针对其实验数据的参数m=5。图1不同蚂蚁数目的分类性能图[11]由其研究可见，参数m的选取不是越大越好，但也不能取之过小。在TSP实验中，蚂蚁数目越大越有利于求解，但是计算的迭代次数也会变大。根据实验，蚂蚁数目一般设定在城市规模数的1/2到2/3之间较为合适[12]。4基于K-Means的蚁群聚类算法引入K-Means作为预计算求解聚类问题的基本蚁群算法(AOC)做为一种蚁群聚类组合方法(KMAOC)如下[5]：Step1任选k个初始聚类中心：C1，C2，C3，…CK；Step2逐个将数据集{X}中各个数据对象按最小距离原则分配给k个聚类中心的某一个Cj；Step3计算新的聚类中心Cj’(j=1,2,…,k)，即jj1C'=NXSX，其中Nj为第j个聚类域Sj包含的个数；Step4若jjC'C(j=1,2,…,k)且未快速分类到设定聚类效果阀值γ或是指定次数时转Step2.Step50nc(nc为循环次数)，由k-means算法分类结果计算出的聚类中心Cj(j=1,2,…,k)，计算每个样本数据Xi相对应的到不同聚类中心Cj的初值τij(0)(i,j=1,2,…,N)，.给出Q、ρ(信息素持久)、n(蚂蚁数)的值，随机给出分配方案；Step6对每个蚂蚁按转移概率pij(t)选择下一个节点；Step7计算新的聚类中心，计算每个样本数据到新的聚类中心的距离.由蚂群聚类公式修改信息素强度τij(t).Step8若nc预定的迭代次数且无退化行为(即找到的都是相同的解)，则输出最好的解；否则转Step65算法测试本文采用外部评价F-measure方法[13]以及总的运行时间对提出的聚类算法与K均值算法和标准蚁群算法进行评价和比较。F-measure的取值在[0，1]之间，取值越接近1越好。实验数据取于UCI机器学习数据库的Wine数据集.数据集有自己的分类，可用于聚类性能的评价。对于聚类算法的性能评价通常采用外部和内部两种，其依据是有无关于数据集的先验知识。表1数据库描述数据库名称数据大小属性个数分类数目Wine178133表2给出了KMAOC算法参数m为8种不同取值情况下Runtime①、F–measure的值(取100次实验的平均值).表2参数m变化算法时间比与F-measure值参数m520406080100120140Runtime①0．670．790．931.0000．851．121．211．43F-measure0.6950.7120.7040.7190.7140.7200.7210.721注①在同一台计算机上运行以KMAOC算法算法参数值：α=1，β=5，ρ=0.99，Q=80，蚂蚁数m=60.迭代次数nc为200次。以其为标准时间，取值为1.当算法参数m变化时的Runtime取值为算法参数m变化时实际运行时间/KMAOC算法参数m为60的实际运行时间得出的比值。.实验结果表明：对于迭代次数与其它α，β，ρ参数取值相同情况下，KMAOC算法参数m取值的不同其Runtime与F-measure值都不同。但相比而言，对本数据集取m值为60左右的Runtime与F-measure所得值较为理想。若取m值其较小时收敛时间减少，但F-measure也较小。若取m值较大时虽然F-measure值增大，但同时收敛时间又增大较多。由实验可知，根据实际问题的应用背景，确定m值，应选取Runtime与F-measure取值都较为理想的情况。6结束语本文对引入K-Means作为预处理过程的蚁群算法（KMAOC）中参数蚂蚁数m的取值进行了讨论。提出参数取值情况应根据不同数据对象进行取值，对参数m取值得到了较好的取值范围。由于KMAOC算法较好的避免了经典蚁群算法初始阶段学习缓慢的缺点。因而相比经典蚁群算法参数m取值而言，KMAOC算法的参数m取值可取得相对大些。建议m的取数应是聚类数的1.6至2倍间取值较好。参考文献[1]JHandl,JKnowles,MDorigo.Ontheperformanceofant-basedclustering[C].In:Procofthe3rdIntConfonHybridIntelligentSystems,IOSPress,Australia,2003-12.[2]韩家炜，KAMBERM.数据挖掘:概念与技术[M].北京:机械工业出版社，2001：223-251.[3]曾洲等,蚁群算法不确定性分析[J],计算机应用，2004;10:136-138.[4]陈应