一种改进的混合蛙跳和K均值结合的聚类算法  

A clustering algorithm based on modified shuffled frog leaping algorithm and K-means

作　　者：喻金平[1] 张勇[2] 廖列法[2] 梅宏标[3] 

机构地区：[1]江西理工大学工程研究院,江西赣州341000 [2]江西理工大学信息工程学院,江西赣州341000 [3]江西理工大学应用科学学院,江西赣州341000

出　　处：《计算机工程与科学》2016年第2期356-362,共7页Computer Engineering & Science

基　　金：国家自然科学基金(71462018);江西省教育厅自然科学基金(DJJ12346)

摘　　要：传统K均值聚类(KMC)算法过分依赖初始值的设置,容易陷入局部最优;混合蛙跳算法(SFLA)存在收敛速度和搜索速度较慢、局部和全局信息交流不全面等缺点。针对以上缺点,首先提出一种改进的混合蛙跳算法(MSFLA)。该算法根据粒子群优化和差分进化思想,在青蛙个体变异时,引入上一次移动距离的权重惯性系数和缩放因子,从种群中的最优位置和历史最优位置之间的随机点出发,以子群内的青蛙的平均值和最差位置差值为步长进行青蛙个体的更新操作。再将MSFLA与KMC算法结合提出MSFLA-KMC算法,有效地克服了KMC算法过分依赖初始值设置问题,同时降低了KMC算法陷入局部最优的可能性。实验结果表明,MSFLA具有较强的寻优能力,MSFLA-KMC算法则具有更好的聚类性能。Traditional k-means clustering （KMC） algorithm is over-dependent on initial value setting and falls into local optimum easily. Shuffled frog leaping algorithm （SFLA） has some shortcomings, such as slow speed on convergence and searching, incomprehensive exchange between local and global information. Aiming at these disadvantages, we propose a modified shuffled frog leaping algorithm （MSFLA）. According to the ideas of differential evolution and particle swarm optimization, inertia weight coefficients of former displacement and scaling factors are introduced into the MSFLA during individual variation of frogs. We randomly choose a point between the best location and the best historical position, and take the difference value between the average and the worst position as the step length to update individual frogs . We present the MSFLA-KMC based on the MSFLA and the KMC, which ef- fectively overcomes the problems of initial value setting of the KMC algorithm, and reduces the likelihood of the KMC algorithm into a local optimum. Experimental results show that the MSFLA has strong search capabilities while the MSFLA-KMC has better clustering performance.

关 键 词：K均值算法 混合蛙跳算法 距离更新公式 适应度函数 聚类 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]