基于改进粒子群和K-means聚类的优化算法.pdf

第37 卷第3期2023 年 6 月Journal of Jiangsu University of Science and Technology(Natural Science Edition)D0I:10.20061/j.issn.1673-4807.2023.03.013江苏科技大学学报（自然科学版）Vol.37No.3Jun.2023基于改进粒子群和 K-means 聚类的优化算法孙林,张一曼,张辰珂,徐久成（河南师范大学计算机与信息工程学院，新乡4530 0 7)摘要：为了解决粒子群优化（particle swarmoptimization，PSO）收敛速度慢和迭代次数多，以及传统K-means聚类算法采取的欧氏距离划分准则会导致聚类效果不理想等问题,构建了基于改进粒子群和K-means聚类的优化算法根据Sigmoid函数优势,对PSO算法中速度更新公式的惯性权重参数实施改进，得到新的惯性权重公式，有效提高PSO算法的收敛速度；在PSO算法的位置更新公式中引入时间权重，通过调整时间权重大小，控制粒子的空间搜索范围，增强粒子的搜索能力；在传统的欧氏距离中引入属性权值，得到新的欧氏距离计算公式，该公式在计算两个向量相似度时，同时考虑了两个向量间的累积差异以及它们之间的相似性，与改进的PSO算法相结合,设计了基于改进粒子群和K-means聚类的优化算法.在6 个基准测试函数和13个UCI数据集上，将所提出的优化算法与其他算法进行对比实验分析实验结果表明：所提算法在收敛速度和寻优稳定性方面得到了明显提升，有效地提高了聚类准确率并且降低了迭代次数.关键词：粒子群优化；K-means聚类；惯性权重；时间权重；欧氏距离中图分类号：TP181Optimization algorithm using improved particle swarm and K-means clusteringAbstract:To solve the problems that particle swarm optimization(PSO)has slow convergence and many itera-tions,and the traditional K-means clustering algorithms with the Euclidean distance partition criterion producethe unsatisfactory clustering effect,we propose an optimization algorithm based on improved PSO and K-meansclustering.Firstly,according to the advantages of Sigmoid function,the inertia weight parameter in the speedupdating formula of PSO is improved to obtain a new inertia weight formula,which can effectively improve theconvergence speed of PSO.Secondly,the position updating formula of PSO is improved by the time weight.Byadjusting the size of the time weight,the searching range of particle is controlled to enhance the searching abilityof particles.Finally,after introducing the attribute weight into the traditional Euclidean distance,a new calcula-tion formula of Euclidean distance is achieved.When computing the similarity of two vectors,the cumulativedifference between two vectors and their similarity is taken into account simultaneously.By integrating the improved PSO algorithm with the K-means clustering,an optimization algorithm is designed.For the six test bench-mark functions and 13 UCI datasets,our designed optimization algorithm is compared with the other algorithms.Experimental results show that the convergence speed and optimization stability of our algorithm are significantlyimproved,and the clustering precision is effectively enhanced and the number of iterations is reduced.Key words:particle swarm optimization,K-means clustering,inertia weight,time weight,Euclidean distanceK-means 算法是一种迭代求解的基于距离的划分聚类算法，由于该算法简易、收敛速度快等特文献标志码：ASUN Lin,ZHANG Yiman,ZHANG Chenke,XU Jiucheng(College of Computer and Information Engineering,Henan Normal University,Xinxiang 453007,China)文章编号：16 7 3-48 0 7(2 0 2 3)0 3-0 8 1-10点，已在基因表达、网络服务等领域广泛应用1-2 1但传统K-means聚类算法存在过度依赖聚类初始收稿日期：2 0 2 2-0 7-2 1基金项目：国家自然科学基金资助项目（6 2 0 7 6 0 8 9，6 197 6 0 8 2）；河南省科技攻关项目（2 12 10 2 2 10 136）作者简介：孙林（197 9一），男，博士，教授，研究方向为粒计算、数据挖掘、生物信息学等。E-mail：s l i n O K 12 6.c o m引文格式：孙林，张一曼，张辰珂，等.基于改进粒子群和K-means聚类的优化算法J.江苏科技大学学报（自然科学版），2 0 2 3,37（3）：8 1-90.D01:10.20061/j.issn.1673-4807.2023.03.013.82条件、对噪声和离群点敏感等缺点文献3 在计算一个点到最近的两质心之间的距离时,将等距离阈值大于等距离指数的点消除,提高了K-means算法的聚类效果但该算法的运行时间有所增加文献4 对空间中两点使用加权平方欧氏距离，提高K-means算法估计目标点的位置但随环境的变化，该算法的寻优稳定性会下降从上述文献可以看出,大部分K-means聚类算法仍存在迭代时间长、性能不稳定等局限性.粒子群优化算法（particleswarmoptimization，PSO)是通过对鸟群觅食行为改进所提出的5,但存在容易陷人局部最优、后期收敛速度慢，以及一些改进模型的机制复杂、参数偏多等问题文献6提出基于灰狼优化算法的PSO算法,增强了粒子群的全局搜索能力，但仍需要进一步改善其寻优稳定性文献7 采用自适应惯性权重和学习因子,提高了PSO算法的稳定性和收敛精度但该算法仍需要改进其收敛速度.为解决PSO算法收敛速度慢和迭代次数多,以及 K-means 聚类不稳定的问题,文献8 改进PSO算法并应用于K-means 聚类,解决算法易受初始聚类中心影响的问题但该算法的运行时间较长文献9 对PSO算法改进并将其应用于聚类分析中,有效提高了算法的收敛速度但该算法存在较多的迭代次数.文中将 PSO 引人K-means算法,构建基于改进粒子群和K-means聚类的优化算法,提高了算法的收敛速度、稳定性、聚类准确性，并减少迭代次数.1基础理论1.1粒子群优化算法PSO算法的基本思想是将每个粒子看作一个具有位置和速度的个体，每个粒子在迭代过程中朝向粒子群全体最优和个体最优趋近，通过不断寻找并更新最优值6 .在d维的数据搜索空间中,假设有n个粒子组成一个群落,第i个粒子可以记为X,=（x i，x i 2，,xia）,它的速度可以记为V,=（v i，Vi，,via）,第i个粒子目前搜索到的最优位置将作为个体最优值：Pest=(Pi,Pia2.,Pia)式中:i=1,2,n.江苏科技大学学报（自然科学版）式中:g=1,2,n.在PSO中,若获得了个体最优位置和群体最优位置,则PSO中的粒子群速度和位置更新表达式为：vi=wvia+Ciri(Pia-xa)+cr2(Pgd-xiu）(3)(4)式中：w为惯性权值，当w值较大时,说明其全局搜索能力被认为较强，则局部寻优能力将相对较弱，若w值较小时，说明其全局搜索能力较弱，局部寻优能力较强10 ;c和c为学习因子;r和r为0,1之间的随机数,PSO算法的具体过程参见文献10.为了获得算法的最优解，使用误差平方和作为适应度函数，即目标函数为：(x)=ZZ,d(x;,C,)xEC;式中：d（x j，C.）为粒子,到粒子群中心C,的距离，目标函数的值越小,则算法效果越好.1.2K-means 聚类传统K-means算法通过多次迭代来获得聚类结果，聚类结果的好坏由初始聚类中心的选取以及聚类数目决定,因此传统的算法存在一些不足该算法的基本思想为：首先，从数据集合中随机选择出k个样本作为初始聚类中心；然后,对每个对象计算它到k个初始聚类中心之间的距离，依据最近邻的原则,将样本点划分到相应的簇中,形成k个簇；最后，通过计算每个簇的平均值得到新的聚类中心，在每次迭代的过程中重新计算，当聚类中心不再发生变化或者满足终止条件时，聚类结束并输出聚类结果.K-means聚类算法的具体流程参见文献1.2基于改进 PSO 和 K-means 聚类的优化算法2.1非线性惯性权重惯性权重是智能优化算法中重要的参数之二.当惯性权重较大时,可以有效提升PSO算法的全局搜索能力，当惯性权重较小时，可以有效提高PSO算法的局部搜索能力12-13 由此线性递减惯性权重1为：(1)W=Wmax2023年Xi=Xia+Vid(5)Wmax-Wmin,tmax(6)t对于整个PSO种群而言，目前搜索到的最优位置可以被记作PSO群体最优位置：Gest=(Pgi,Ppa,.,Pga)式中：Wmax为惯性权重最大值；Wmin为惯性权重最小值;t为当前送代次数，tmax为总迭代次数.(2)在式(6)中，惯性权重与迭代次数成负相关.第3期在刚开始迭代的时候，惯性权重w比较大,反映在速度的计算公式上可以看出初始粒子的速度比较大，全局搜索能力较好，而局部搜索能力较弱12 当迭代次数被累加时，惯性权重值会变得越来越小,PSO中的粒子速度也会变得越来越小，此时PSO中的粒子将呈现出良好的局部搜索能力，但是此时的全局搜索能力表现较弱12 另外，由于线性递减权重的斜率不变,致使速度改变总体上是保持不变的13 因此,对传统线性权重递减速度不平衡的情况进行优化,基于Sigmoid函数的S型增长趋势的特点对惯性权重进行改进.定义1改进的惯性权重的表达式为：w=WmaxWmax-Wmina式中：=1/（1+e-3）为改进的 Sigmoid函数变式.由于PSO算法收敛速度较慢，根据Sigmoid函数的特点，可以提高其后期速度，并且经多次实验发现,当a=1/(1+e-3）时引人惯性权重的优化效果较好改进的惯性权重式（7)能够在PSO算法的迭代过程中有效平衡其搜索能力和粒子的收敛速度.2.2时间权重文献13 表明位移公式与时间、速度相关,传统PSO算法位置更新公式中潜藏了时间因素,且时间权重都为常数1,导致粒子在最优解附近来回震荡因此,在位置更新公式中引人时间权重的概念。定义2 在传统PSO算法的位置更新公式中引人时间权重，则改进的位置更新为：Wmax-Wmin)xia=xia+(10-t式中：xia为粒子更新后的位置;xia为粒子更新前的当前位置，Vi为粒子的当前速度，n的大小可以调整粒子的位置范围,依据文献13,n的数值取-0.02的时候效果最佳.在式(8)中可以通过调整时间权重的大小来控制粒子的搜索范围,增强粒子的搜索能力在PSO算法开始时选择较大的时间权重,有利于该算法实现快速的全局搜索，当迭代进行到一定程度时，选择较小的时间权重有利于局部开发.2.3加权欧氏距离样本之间的相似度是用欧氏距离来衡量的,距离越小样本越相似14设有n个样本点集合X=xi，x 2，x,，孙林,等：基于改进粒子群和K-means聚类的优化算法md(x;,x,)=S=为了提高计算两个不同向量相似度的准确性，对欧氏距离进行加权，同时考虑两个不同向量间的累积差异以及对应元素间的相似性,以便有效提高K-means 聚类结果的稳定性和聚类精度.为了加大数据属性之间的区分程度,使用文献15中的权值公式得到不同维度数据的权值为：(7)Wipn式(10)是根据每个样本点中各个分量的影响程度进行定义的,能够表现出样本点整体分布的特性;x，第i个样本点中的第p个分量；分母样本集中各个样本点的第p个分量的平均值；引人权重不仅没有改变传统K-means算法中欧氏距离的计算，而且加大了数据特征之间的区分程度.考虑到对应元素间的相似性，对应元素的值越相近,其对相似度的贡献越大,在最终的相似度结果中也会占有更大的权值14 计算对应元素间相似性的权值公式为：Wim=式中:设置g=1,m;=ee-1*):/,M=Zm:定义3两个样本点x；和x,加权后的欧氏距离表示为：Vid(8)83将两个样本点x；和x,之间的距离定义为欧氏距离,其中x;是m维向量,则两个m维向量x=(xil，X2,x i m)与x,=(xji，Xj 2,，x m)之间的欧氏距离14 为：(9)xip(10)-I x;-y;1/oeMd(x,x)=/o(xg-x,)25=1式中：;=（,+m）/为改进后的权值，ip为计算距离时样本点不同维度数据的权值，im为计算对应元素相似性的权值，x；和x分别是在向量空间第s维下样本点x，和样本点x,的数据值.在式(9)中引入改进权值后得到新的欧氏距离计算公式，式（12）在计算两个向量相似度时同时考虑两个向量间的累积差异和对应元素间的相似性，避免了片面化，从而提高聚类结果的稳定性和精度.2.4算法步骤将基于改进惯性权重和时间权重的PSO算法与欧氏距离加权的K-means聚类算法结合,设计了(11)(12)84为详细描述基于改进粒子群和K-means聚类的优化算法（optimization algorithm based on improvedparticle swarm optimization and k-means clustering,KCPSO)的具体步骤,其伪代码如下：算法1:KCPSO算法输人：数据集D输出：最优个体集合Stepl:初始化D=O,初始化粒子群及其参数Step2:将每个样本随机划分为某一类,计算各类的聚类中心cen作为初始粒子群的位置Step3:初始化粒子群Via、Xi a 和fgStep4:for i=1 to n doStep5:if fit2fit then 记录并更新 PbestStep6:if fitt2fg then 记录并更新 GbestStep7:end forStep8:根据公式(7)更新w;根据式(3)和式(8)更新所有粒子Via和xidStep9:for t=1 to m doStep10:for i=1 to n doStepl1:计算样本到各类的距离；按最近距离对粒子进行聚类划分；根据划分结果计算新的cen;记录粒子fgStep12:end for名称SphereSchwefelRosenbrockStepRastriginGriewank江苏科技大学学报（自然科学版）Step13:end forStep14:在符合终止条件时终止，否则进人Step5Step15:return最优个体集合在算法1中,Step2Step3为初始化粒子群和初始聚类划分，该过程的时间复杂度为0（n）.Step4Step7为更新粒子个体和群体最优适应度值的过程,该过程的时间复杂度为O（n）St e p 8 为更新粒子速度和位置的过程，该过程的时间复杂度为0(n）.St e p 9 St e p 13为新一代粒子优化的过程，该过程的时间复杂度为0（mn）,其中m为最大迭代次数，n为粒子个数。综上所述算法1的时间复杂度为0(mn).3实验结果与分析3.1实验准备为了验证KCPSO算法的有效性,实验分为两部分：第一部分从文献6 中选择6 个基准测试函数（表1)进行实验比较,第二部分使用13个UCI数据集（表2）进行实验比较.实验中使用Mat-lab2016b实现算法编程实验配置环境：Win-dows10操作系统,6 4位的基于x64的处理器,运行环境为 Intel CoreTMi5-6500CPU3.20 GHz和16 GB 内存.表16 个基准测试函数的描述Table 1Description of six benchmark functions函数i(a)=Z,(a)=Z(Z,)*f;(x)=-,100(xi+-x)+(1-x)J.(x)=Z(I x;+0.51)2;(x)=Z,x-10cos(2mx.)+10Z-I1f(x)=4 0002023年搜索范围全局最优值-100,1000-100,100 0 32,32 0-100,100 0 32,32 0cos+1i=1-600,600 0表2 13个UCI数据集信息Table 2Description of thirteen UCI datasets序号数据集1Iris2Wine3Glass4Balancescale5Zoo6Liver7Letter数据集大小1501782146251013455000属性个数41310417717序号8910111213数据集SonarHeartBreastpimaGermanSpambase数据集大小20827028676810004 601属性个数6013982057第3期3.2优化性能分析为了检验KCPSO算法的优化性能，分别将KCPSO算法、PSO算法、改进位置更新公式的PSO算法（PSOd)）【10)以及基于改进惯性权重（式(6)）的PSO算法(PSOw）,在6 个基准测试函数上进行寻优每种算法种群数规模设置为50，迭代次数Tmx=1000,其余参数均采用对应文献中的最佳实验参数依据文献6 ，采用3个指标：平均值（M e a n）、标准方差（standard deviation，St d）和排名（Ra n k）,评判算法的寻优精度其中,Mean反映算法的寻优精度，Std反映算法的寻优稳定性对每个算法运行30 次进行对比分析，结果如表3,实验结果中最优值用粗体表示.表34种算法在6 个基准测试函数上的3种指标结果对比Table 3Comparison of three metrics of fouralgorithms on six benchmark functions函数算法PSO4.26107PSOd2.5710lPSOw7.26103KCPSO1.8710-14PSO3.7102PSOd1.25103PSOw2.75101KCPSO3.2610l孙林,等：基于改进粒子群和K-means聚类的优化算法指标MeanStd3.2910-75.3110l7.3110-33.6410-141.831021.161038.38105.631085KCPSO算法寻优精度略低于最优的PSOw算法，这可能是由于KCPSO算法加入时间权重致使搜索范围扩大而造成的，但KCPSO算法的寻优稳定性优于PSOw算法，并且优于其他2 种算法从总排名来看,KCPSO算法与其他对比算法相比,KCPSO算法的寻优精度和寻优稳定性均优于其他3种算法.为了验证KCPSO算法的收敛性,图1为4种算法在6 个基准函数上寻优的收敛曲线,横轴为迭代次数，纵轴为最优值由图1可知,在函数fiV2、f4和f。上,KCPSO算法收敛比较快，其寻优精度高于其他3种算法,并且KCPSO算法迭代6 0 次时达到最优在f，函数上，KCPSO算法前2 0 次迭代的收敛速度略慢于PSO算法，但是在2 0 次之后,其收敛速度快于其他算法在f4函数上，在前6 0 次的迭代过程中,KCPSO算法和PSOd算法的收敛速度基本保持一致在fs函数上,KCPSO算法在前Rank40次迭代的收敛速度略慢于PSO算法，但KCPSO2算法在迭代6 0 次时达到最优。综上所述,KCPSO4算法在收敛速度上是优于其他算法的.31019834122.5PSO2.0元.54PSOPSOdKCFSo20PSO1.66102PSOd3.46 104PSOw1.14102KCPSO5.2510PSO2.610PSOd3.41102101201.0610232.5110447.0010l23.711012.321036.311024140选代次数(a）22010KCPSO+PSOd100120 140选代次数(b)160180200PSOwKCPSOPSOPSOdPSOwKCPSO2.0010-11.0010-16.9310l2.101022.7210l2.091014.8310-13.1010-12.1510l1.311023.891003.7810213421205100120140160180选代次数(+PSOdoPSOW+KCPSO4P5020600r50040020020选代次数(d)PSOdKCPSO7.0410-2PSO1.5410-12.2210PSOdPSOwKCPSO16总排名(PSO)由表3可知,KCPSO算法与其他3种算法相比,其优化性能较好，在fiVsV4Vs和f。这5个函数上,KCPSO算法的寻优性均优于其他3种算法，寻优精度提高了15个数量级在函数f上，2215.7810-147.5610-13.83 10-25.2010-24.001022413(PSOd)(PSOw)(KCPSO)100220选代次数()f,3图14种算法在6 个函数上的收敛曲线1Fig.1 Convergence curves of four algorithms7on six benchmark function3.3UCI数据集上的实验结果为了验证KCPSO算法的后期收敛速度,与原始PSO算法4、结合原始PSO算法5 和原始K-means 聚类算法 10 (combinational algorithm of K-means clustering and PSO，K PSO）、结合改进的非40120140160180200选代次数(f86线性惯性权重式（6）的粒子群和K-means算法（K PSO-V）、结合改进的时间权重式（7）的粒子群和K-means算法（KPSO-X）,以及结合改进的欧氏距离式（11）的粒子群和K-means算法（IKPSO）等5种算法进行对比为了节省版面空间,从表2 中选择2 个具有代表性的数据集,计算了6 种算法的运行时间与迭代次数，其实验结果如图2 从图2可以看出，原始PSO算法的运行时间随迭代次数增加呈明显增长趋势;KPSO-V、K PSO-X与IKP-SO这3种算法的运行时间随迭代次数增加而呈上下波动；KPSO算法的运行时间在迭代次数40 120之间呈上下波动，在迭代后期呈增长趋势；KCPSO算法的运行时间均低于其他结合算法,且随迭代次数增加呈明显下降趋势，特别在迭代后期,KCPSO算法的运行时间越来越少,究其原因是由式(7)分析可知,随着迭代次数增加,惯性权重会越来越大,反映到速度更新表达式上可以看出粒子速度在后期会越来越快，运行时间越来越少。7.27.0江苏科技大学学报（自然科学版）IKPSO这5种算法的搜索范围对比表4为5种算法的搜索范围上下限对比,其中,Max为搜索上限,Min为搜索下限.送代次数120(a)Iris数据集00120选代数(c)Glass数据集2023年1.401601.6018020(b)Wine数据集200120选代次数(d)Balancescale数据集3001401601802006.86.66.4S/画6.226.05.85.65.45.2206.05.85.65.45.25.04.84.64.44.24.020图2 2 个UCI数据集上6 种算法的运行时间与选代次数对比Fig.2Comparison of the runtime and iteration timesof six algorithms on two UCI datasets为了验证粒子群引人时间权重后，粒子搜索范围扩大和粒子搜索能力的增强，在Iris、W i n e、Glass、Ba l a n c e s c a l e、Le t t e r、Zo o、Li v e r 与 Sonar 这 8个UCI数据集上进行实验使用粒子群位置更新表达式（式（4)和式（8）求出图3和表4的搜索范围,图 3为 KCPSO、K PSO、K PSO-X、K PSO-V 和00PSOKPSOKCPSOPSO-XKPSO-VIKPSO406080100120140160180200选代次数(a)Iris数据集406080100120140160180200选代数(b)Zoo数据集1006080(e)Letter数据集PSOKPSOKCPSOPSO-XKPSO-VIKPSO00送代次数100120选代次数(g)Zoo数据集图35种算法在8 个数据集上的搜索范围对比Fig.3 Comparison of search range of fivealgorithms on eight datasets从图3（a）图3（d）、图3（e）、图3（f)和图3(h)中可以看出,KCPSO算法的搜索范围比KP-SO、K PSO-V和IKPSO这3种算法的搜索范围大，且在大部分迭代过程中优于KPSO-X算法的搜索能力.从图3(b）、图3(c)和图3(g)可知,KCPSO算法的搜索范围下限与其他4种算法的搜索范围下限基本在同一区间范围内，但是在Wine、G l a s s和Liver这3个数据集上,KCPSO算法的搜索范围1201401601802006080()Liver数据集401020先代次费(h)Sonar数据集140送代次160180200第3期表45 种算法在8 个数据集上的搜索范围Table 4 Search range of five algorithms on eight datasets搜索范围数据集算法KPSOKPSO-XIrisKPSO-VIKPSOKCPSOKPSOKPSO-XWineKPSO-VIKPSOKCPSOKPSOKPSO-XGlassKPSO-VIKPSOKCPSOKPSOKPSO-XBalance scaleKPSO-VIKPSOKCPSOKPSOKPSO-XLetterKPSO-VIKPSOKCPSOKPSOKPSO-XZo0KPSO-VIKPSOKCPSOKPSOKPSO-XLiverKPSO-VIKPSOKCPSOKPSOKPSO-XSonarKPSO-VIKPSOKCPSO上限比最差算法的搜索范围上限大了138 19 35.从表4可以看出，在Iris、W i n e、G l a s s、L i v e r 与 Sonar这5 个数据集上,KCPSO算法的搜索范围均是最优的.在Balance scale数据集上，搜索上限仅低于最优的KCPSO-X算法在Letter和Zoo这2 个数据集上,引人时间权重的KPSO-X算法的搜索范围是最优的,并且在大部分数据集上,KPSO-X算孙林,等：基于改进粒子群和K-means聚类的优化算法MaxMin7.15-1.19.56-1.027.99-2.948.09-0.4211.86-5.851 741.760.362 211.99-0.61292.620.39316.85-0.252 227.65-1.415137.36-0.05202.25-0.2172.590.07174.74-0.05210.15-3.370.504.825.935.073.345.8416.9464.8238.6524.3755.6111.0415.711.511.1615.46170.40223.859143.2990264.114.465.215.214.565.6887法的搜索范围上下限优于KPSO-V、I K PSO 和KP-SO这3种算法，仅次于KCPSO算法.因而，引人时间权重的KCPSO算法的搜索范围和搜索能力都得到了明显的增强。由式(5)可知,适应度函数的值可以衡量聚类效果,其值越小,聚类效果越好 17.因此,为了验证KCPSO 算法在 Iris、W i n e、Br e a s t、He a r t、G e r ma n、Pi-ma 和 Spamdase 这7 个UCI数据集上的聚类效果，将KCPSO算法与KPSO 算法、KM算法 17、PSOC算法 17 PTWDC算法 17 这4种算法进行对比,图4为7 个数据集上的适应度值变化的对比曲线.800KPSOKCPSO700KMPSOC50PTWDC20100-0.271000r9001.35800-0.26-0.712.15-6.63-2.032.83-4.431.0310-20-1.710-220.230.34-5.410-381.57-106.531.49-0.82-116.640.0390.005 60.0350.0560.005 416141210102040080504.540353.02.5201.5F图47 个UCI数据集上5 种算法的最优适应度值对比Fig.4Comparison of optimal fitness values offive algorithms on seven UCI datasets从图4(a）、图4（c）、图4（d）、图4(f)和图4(g)中可以看出,KCPSO算法能够快速、稳定的收敛且最优适应度值最小在Iris、H e a r t、Pi m a 和Spamdase这4个数据集上，KCPSO算法在送代2 0次就可以达到最优适应度值在Breast数据集上，KCPSO算法在迭代40 次就可以达到最优适应度值从图4(b)的实验结果可以看出，在迭代前40KPSOKCPSOPSOCKMPTWDC60T0o选代次数(a)Iris数据集(c)Breast数据集1020102020KPSOKCPSOPTWDCXPSO合KCPSOKMPSOCPTWDC0选代次数(e)German数据集3010选代次数(g)Spamdase数据集送代次数(b)Wine数据集453505303.53.02.0.0KPSOKMXCPSOPSOCPTWDC5070KPSOKCPSOKMPSOCPTWDC100(d)Heart数据集XPSOPSOCPTWDC选代次数()Pima数据集88次的迭代过程中,KM算法、PSOC算法和PTWDC算法效果较好，但在迭代40 次以后KCPSO算法效果较好从图4(e)的实验结果可知，在迭代2 0 次以后,5 种算法的效果基本保持同一水平。综合来看,KCPSO算法更稳定且聚类效果更好.3.4聚类效果对比分析为了验证KCPSO算法中改进的欧氏距离的有效性,使用文献 18 中的类内聚集度函数和类间离散度函数构造目标函数其中,类内距离越小，聚类内部越紧密，聚类效果越好；类间距离越大,聚类间差异就越大,聚类结果越优将KCP-SO算法与粗糙K-means算法（rough K-meansclustering，RSK）19、遗传算法改进的粗糙K-means 算法(rough K-means clustering based on ge-netic algorithm，G RSK）【2 0、蚁群算法改进的粗糙K-means 算法（rough K-means clustering combinedwith ant algorithm，A RSK）2 1、结合人工蜂群优化的粗糙 K-means 聚类算法（rough K-means cluste-ring combined with artificial bee colony optimization,ABCSK）18 进行对比.所有对比算法的数据选自文献 18，各算法均使用对应文献中的最佳实验Table 5 Comparison of experimental results of five algorithms on four datasets under four indexes数据集IrisWineBalance scaleSonar江苏科技大学学报（自然科学版）参数在Iris、W i n e、Ba l a n c e s c a l e、So n a r 这4个数据集上，采用类内距离 18、类间距离 18、准确率 18、迭代次数这4个指标，对实验结果进行评价，实验结果如表5.从表5 可以看出，KCPSO算法的类间距离和迭代次数均优于其他4种算法,在Iris、W in e 和Balane scale这3个数据集上,KCPSO算法的类间距离分别比次优的ABCSK算法增大了3.31、6.8 5 和1.7 3,在Sonar数据集上KCPSO算法的类间距离比次优的GRSK算法增大了13.5 3.在这4个数据集上，KCPSO算法的迭代次数分别比次优的ABCSK算法减少了0.7 次、4.0 5 次、5.5 7 次和2.51次在Iris、Ba l a n c e s c a l e、So n a r 这3个数据集上,KCPSO算法的准确率均优于其他4种算法，但在Wine数据集上,KCPSO算法的准确率比最优的ABCSK算法的准确率低了8%在Iris、W i n e 和Bal-ance scale这3个数据集上,KCPSO算法的类内距离均优于其他4种算法，比次优的ABCSK算法分别减少了6.6、45 0 0 和39.5 1,但在Sonar数据集上,KCP-SO算法的类内距离比最优的ABCSK算法高了1305.58.综合来看，所提出的KCPSO算法取得了相对较优且较稳定的聚类结果。表5 4个数据集上5 种算法在4个指标下的实验结果指标算法类内距离RSK839.10GRSK123.97ARSK122.41ABCSK117.93KCPSO111.33RSK1.65104GRSK1.51104ARSK1.50104ABCSK1.50104KCPSO1.05104RSK921.33GRSK837.47ARSK823.62ABCSK812.14KCPSO772.63RSK8 602.74GRSK6 478.16ARSK5353.85ABCSK5 002.87KCPSO6 308.452023年类间距离准确率/%24.9385.3232.8390.0129.5590.1233.6791.0336.9894.47464.6769.11471.1373.67474.3473.70481.2574.83488.1065.8927.3752.2635.4956.13436.1957.3