算法分析
基于蚁群粒子群
混合算法的K均值聚类优化算法研究
饶喆1唐双喜？刘国平？
(1.海军工程大学兵器工程系湖北武汉430033;2.海军92840部队山东青岛266405)
摘要：K均值聚类算法是一种经典的数据挖据算法，但该算法存在对初始值敏感且容易陷入局部最优问题，一定程度上影响分类结果的准确性。通过分析蚁群算法和粒子群算法,将两者混合算法应用到K均值聚类算法,提出一种K均值聚类优化算法。仿真结果表明，该优化算法不易受到初始值取值的影响具基有较强的全局等优能力,可作为聚类分析的一种有效方法。
关键词：双群算法粒子群算法K均值聚类算法中图分类号：TP18
文献标识码:A
文章编号：1007-9416(2015)04-0122-02
AbstractK means dlustering algorithm is a classic data mining method, but the algorithm is sensitive to initial value and easy to fall into local optimum problem. The accuracy of the classification results are afected to a certain extent. Through the analysis of ant colony algorithm (ACA) and particle swarm algorithm (PSO), the hybrid algorithm is applied to the K means algorithm, we propose an improved K - means algorithm. The simulation results show that the improved algorithm is not easily affected by the initial value of the influence, and has the strong abiliry of global optimization. It is an effective method of cluster analysis.
Key Words:ant colony algorithm; particle swarm algorithm; K means chustering algorithm
1引言
针对要求较高、难以凭经验和先验知识准确分类的间题，通过聚类分析1-3,将样本数据按某些属性或准则分成多个类别，使得同类样本相似程度尽可能大，同时，不同类别的样本差异程度也尽可能大。K均值聚类算法是聚类分析中一种非监督实时聚类算法4.% 该算法是在最小误差函数的基础上将数据划分成不同类别。本文在蚁群算法和粒子群算法的基础上，通过对两种算法进行结合，提出
了一种基于蚁群粒子群混合算法的K均值聚类优化算法。 2传统K均值聚类算法的不足
根据K均值聚类算法思想/首先对n个数据对象随机选择m个对象，将这m个对象视为m个类的数据均值，则m个均值就分别表示初始的m个不同聚类中心：然后计算剩余数据与聚类中心的相似度，并分别赋给与聚类中心相似度最大的聚类；初始分类完成后，再以各类数据均值作为对应类别的聚类中心，进行重新聚类，如此反复送代计算，直至类收效或达到最大的送代次数时结束，K均值聚类算法虽然具有计算简单，收敛速度快等优点，但该算法仍然存在如下不
足：
(1)在计算之前必须确定初始聚类的个数。聚类的个数直接影响
聚类结果及准确性。
(2)初始值的选取对聚类结果影响较大。当初始值选取不当时，可能会出现无解情况。
(3)K均值聚类算法采用的是梯度法求得最优解，因而求得的结
果是局部最优解，面不是全局最优解。 3K均值聚类优化算法
3.1奴群粒子群混合算法
蚊群算法(AntColonyAlgorithms，ACA)是一种源于大自然的仿生类算法，它不需要任何先验信息，从最初的的随机搜索路径开收稿日期：2015-0422
始，通过找到规律使解空间逐渐逼近直至最终达到全局最优。在 ACA算法中，信息索更新公式为
(++n)=(1-P)T,(0)+r
(1)
其中，P为消减因子，,()为{时刻路径(i,)上的信息素浓度，△，为时刻:与时刻1+n之间第只蚂数在路径(,)上留下的信息素浓度，且
At, =
fo/L
10
(2)
其中，Q表示信息素总量，L表示搜索路径总长度。则第只k蚂妈蚁从城市i到城市J的转移概率为
()() om0 1o,
jen,
(3)
je Nt
其中，N是第k只蚂蚁在城市i的可行邻域城市集合，α和β 分别为信息素浓度和启发式信息值在概率中的权重系数。
粒子群算法(ParticleSwarmOptimization，PSO)是一种基于群体智能理论的全局导优算法，通过将每一个解看作搜索空间中具有定速度的数子，根据该粒子当前换索最优解和粒子群全局搜索最优解两个极值进行动态调整粒子位置。在PSO算法中，粒子速度和位置更新公式为
作者简介：饶喆(1988一),男,湖北武汉人,博士研究生,研究方向：制导与控制技术。万方数据