算法分析 ｌ欺字技术 叶 基于蚁群粒子群 混合算法的Ｋ均值聚类优化算法研究 饶酷’唐双喜 刘国平。 （１．海军工程大学兵器工程系湖北武汉４３００３３；２．海军９２８４０部队山东青岛２６６４０５） 摘要：Ｋ均值聚类算法是一种经典的数据挖掘算法，但该算法存在对初始值敏感且容易陷入局部最优问题，一定程度上影响分类结果的准确性。通 过分析蚁群算法和粒子群算法，将两者混合算法应用到Ｋ均值聚类算法，提出一种Ｋ均值聚类优化算法。仿真结果表明，该优化算法不易受到初始值取 值的影响，且具有较强的全局寻优能力，可作为聚类分析的一种有效方法．． 关键词：蚁群算法粒子群算法Ｋ均值聚类算法 中图分类号：ＴＰ１８１ 文献标识码：Ａ 文章编号：１００７—９４１６（２０１５）０４—０１２２ ０２ Ａｂｓｔｒａｃｔ：Ｋ ｌｌｌｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｉｓ ａ ｃｌａｓｓｉｃ ｄａｔａ ｍｉｎｉｎｇ ｍｅｔｈｏｄ，ｂｕｔ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｉｓ ｓｅｎｓｉｉｖｅ ｔｔｏ ｉｎｉｔｉａｌ ｖａｌｎｅ ａｎｄ ｅａｓｙ ｔｏ ｆａＵ ｉｎｔｏ ｌｏｃａｌ ｏｐｔｉｍｕｎ１ ｐｒｏｂｌｅｍ．Ｔｈｅ ａｃｃｕｒａｃｙ ｏｆ ｔｈｅ ｃｌａｓｓｉｉｆｃａｔｉｏｎ ｒｅｓｕｌｔｓ ａｒｅ ａｆｆｅｃｔｅｄ ｔｏ ａ ｃｅｒｔａｉｎ ｅｘｔｅｎｔ．Ｔｈｒｏｕｇｈ ｔｈｅ ａｎａｌｙｓｉｓ ｏｆ ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ（ＡＣＡ）ａｎｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ａ￣ｏｒｉｔｈｍ（ＰＳＯ），ｔｈｅ ｈｙｂｒｉｄ ａｌｇｏｒｉｔｈｍ ｉｓ ａｐｐｆｉｅｄ ｔＯ ｔｈｅ Ｋ—ｍｅａｎｓ ａｌｇｏｒｉｈｍ，ｗｅ ｐｒｏｐｏｓｔｅ ａｎ ｉｍｐｒｏｖｅｄ Ｋ—ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ．Ｔｈｅ ｓｉｍｕｌａｔｉｏｎ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｍ ｉｈｓ ｎｏｔ ｅａｓ￣ｙ ａｆｆｅｃｔｅｄ ｂｙ ｔｈｅ ｉｎｉｔｉａｌ ｖａｌｕｅ ｏｆｔｈｅ ｉｎｆｌｕｅｎｃｅ，ａｎｄ ｈａｓ ｔｈｅ ｓｔｒｏｎｇ ａｂｉｌｉＷ ｏｆｇｌｏｂａｌ ｏｐｔｉｍｉｚａｔｉｏｎ．Ｉｔ ｉｓ ａｎ ｅｆｆｅｃｔｉｖｅ ｍｅｔｈｏｄ ｏｆ ｃｌｕｓｔｅｒ ａｎａｌｙｓｉｓ． Ｋｅｙ ＷｏＫｔＳ：ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ；ｐａｒｔｉｃｌｅ ｓｗａｍｌ ａｌｇｏｒｉｔｈｍ；Ｋ—ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ １引言 始，通过找到规律使解空间逐渐逼近直至最终达到全局最优。在 信息素更新公式为 针对要求较高、难以凭经验和先验知识准确分类的问题，通过 ＡＣＡ算法中，聚类分析口 】，将样本数据按某些属性或准则分成多个类别，使得同 类样本相似程度尽可能大，同时，不同类别的样本差异程度也尽可 能大。Ｋ均值聚类算法是聚类分析中一种非监督实时聚类算法 ｓＩ， 该算法是在最小误差函数的基础上将数据划分成不同类别。本文在 蚁群算法和粒子群算法的基础上，通过对两种算法进行结合，提出 了一种基于蚁群粒子群混合算法的Ｋ均值聚类优化算法。 Ｐ）・ （ｔ）＋∑Ａｒ： ｋ＝ｌ 其中，Ｐ为消减因子， （ｔ）为ｔ时刻路径（ ，＇，）上的信息素浓 度，Ａｒ 为时刻ｔ与时刻ｔ＋ｎ之间第只Ｊ｝ｊ蚂蚁在路径（ｆ， ）上留下 的信息素浓度，且 ＝ ２传统Ｋ均值聚类算法的不足 根据Ｋ均值聚类算法思想 首先对ｎ个数据对象随机选择ｍ个对 象，将这ｍ个对象视为ｍ个类的数据均值，则ｍ个均值就分别表示初 始的ｍ个不同聚类中心；然后计算剩余数据与聚类中心的相似度，并 分别赋给与聚类中心相似度最大的聚类；初始分类完成后，再以各 其中，Ｑ表示信息素总量，三表示搜索路径总长度。则第只七蚂 类数据均值作为对应类别的聚类中心，进行重新聚类；如此反复迭 蚁从城市 到城市 的转移概率为 代计算，直至类收敛或达到最大的迭代次数时结束。Ｋ均值聚类算法 虽然具有计算简单，收敛速度快等优点ｂｌ，但该算法仍然存在如下不 足： ： ∑《（ｔ）ｒｌａ（ｔ ）’ ，一 Ⅳ ”‘ Ｎ （１）在计算之前必须确定初始聚类的个数。聚类的个数直接影响 聚类结果及准确性。 （２）初始值的选取对聚类结果影响较大。当初始值选取不当时， 可能会出现无解情况。 ，２ｅＮｔ ０， 其中，Ⅳ 是第ｋ只蚂蚁在城市ｆ的可行邻域城市集合， 和 （３）Ｋ均值聚类算法采用的是梯度法求得最优解，因而求得的结 分别为信息素浓度和启发式信息值在概率中的权重系数。 果是局部最优解，而不是全局最优解。 粒子群算法（ＰａｒｔｉｃｌｅＳｗａｒｍＯｐｔｉｍｉｚａｔｉｏｎ，ＰＳＯ）是一种基于群 ３ Ｋ均值聚类优化算法 ３．１蚁群粒子群混合算法 蚁群算法（ＡｎｔＣｏｌｏｎｙＡｌｇｏｒｉｔｂ＿ｍｓ，ＡＣＡ）是一种源于大自然的 体智能理论的全局寻优算法，通过将每一个解看作搜索空间中具有 一定速度的粒子，根据该粒子当前搜索最优解和粒子群全局搜索最 优解两个极值进行动态调整粒子位置。在ＰＳＯ算法中，粒子速度和位 置更新公式为 仿生类算法，它不需要任何先验信息，从最初的的随机搜索路径开 收稿日期：２０１５一Ｏ４—２２ 作者简介：饶菇（１９８８一），男，湖北武汉人，博士研究生，研究方向：制导与控制技术。 ｉ 技术 １．６ ｌ ｈｋＴ， ｈ｝ ’ ． 自Ｉ １．５ ＼ …～㈣ｌ≈ ＬⅢ Ｔ ＾ 且ｌ玳 畀Ｔ℃ ｆ． Ｚ １．４ ｜ 旧 １．３ ｜ １．２ １ １ ＼ １．０ Ｏ ２Ｏ ４Ｏ ６０ ８Ｏ 迭代次数 图１收敛曲线 Ｖ ｋ＋ ＝ ＋ ‘（ｐ 一 ） ＋ｃ （ｇ 一ｘ ｋ） （４） （５） 其中，ｐ 和ｇ 分别表示个体极值和全局极值。ＣＯ为惯性权 重，七为迭代次数；ｃ１为调节微粒飞向自身最好位置方向的步长，调 节微粒向全局最好位置飞行的步长，￣１＿Ｃ１，ｃ２∈（０，２）；，ｉ和 为相 互独立的随机函数，且 ，ｒｚ ｃ（０，１） 通过粒子群算法进行粗搜索，得 到聚类原型，再此基础上利用蚁群算法求得最优聚类结果［１１ ＿］。由 式（３－５），可得ＡＣＡ算法和ＰＳＯ算法混合算法，即 （ｔ＋ｎ）＝ （ｔ） （ｔ＋ ） （７） ３．２ ＡＣＡ－ＰＳＯ￣合算法对Ｋ均值聚类算法的优化 根据ＡＣＡ－ＰＳＯ混合算法的思想，对Ｋ均值聚类算法进行优化， 步骤如下： （１）粒子初始化。计算原始聚类中心，得到初始粒子的位置编码， 算法分析 同时计算粒子适应度并初始化粒子速度，生成Ⅳ个初始粒子群。＋ （２）确定个体极值。比较每个粒子适应度与当前个体极值的最好 ＝ 位置适应度，若前者大于后者，则用该粒子的位置代替最好位置。Ｊ ｒ●Ｌ （３）确定全局极值。比较每个粒子适应度与当前全局极值的最好 位置适应度，若前者大于后者，则用该粒子的位置代替最好位置。∽ 托 厂 （４）根据式（５）和式（６）对粒子速度和位置进行更新。ｒ，，Ｌ ｔ ， （５）Ｋ均值优化 对粒子的聚类中心编码，并根据最邻近法则确 、＝：， — 定粒子类别，然后对各类别的聚类中心进行计算，同时更新粒子适 一 应度以确定新的聚类中心编码值。 （６）优化结束。确定最好位置和最大迭代次数时结束优化，否则 回到第２步中继续优化，直至优化结束。 ＋ ４仿真分析 为验证蚁群粒子群？昆合算法优化的Ｋ均值聚类算法相比于传 统Ｋ均值聚类算法的优越性，通过仿真比较两种算法，如图１所示。在 相同条件下，传统Ｋ均值聚类算法收敛速度较快，但容易陷入局部最 优问题。而本文提出的改进Ｋ均值聚类算法具有很强的全局寻优能 力，解决了局部最优问题，从而证明本文方法的有效性。 ５结语 针对传统Ｋ均值聚类算法存在的不足，提出了一种基于蚁群粒 子群混合算法的Ｋ均值聚类优化算法。仿真结果表明，该优化算法对 初始值不敏感，且具有较强的全局寻优能力，能够对大数据进行准 确分类，具有一定的应用价值。 参考文献 ［１］周丽娟．改进粒子群算法和蚁群算法混合应用于文本聚类［Ｊ］．长 春工业大学学报（自然科学版），２００９，３０（３）：３４１—３４６． ［２］ｌｏａｎ Ｃｒｉｓｔｉａｎ Ｔｒｅｌｅａ．Ｔｈｅ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ａＩｇｏｒｉｔｈｍ：Ｃｏｎｖｅｒｇｅｎｃｅ ａｎａｌｙｓｉｓ ａｎｄ ｐａｒａｍｅｒ ｓｅｌｅｃｔｉｏｎ［Ｃ］． Ｉｎｆｏｒｍａｔｉｏｎ ｐｒｏｃｅｓｓｉｎｇ Ｌｅｔｔｅｒｓ，２００２：３１ ７－３２５． ［３］Ｆｒａｎｓ ｖａｎｄｅｎ Ｂｅｒｔｈ．Ａｎ Ａｎａｌｙｓｉｓ ｏｆ Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚｅｒｓ ［Ｄ］．Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｐｒｅｔｏｒｉａ，２００１． ［４］张宇飞．模拟电路多软件故障特征的智能优化提取方法研究［Ｄ］． 哈尔滨：哈尔滨理工大学，２０１４． ［５］梁烨炜．Ｋ均值聚类算法的改进及其应用［Ｄ］．湖南：湖南大学， ２０１ ２． ［６］张维存．蚁群粒子群混合优化算法及应用［Ｄ］．天津：天津大学， ２００７． ［７］张建萍，刘希亚．基于聚类分析的Ｋ均值算法研究与应用［Ｊ］．计算 机应用研究，２００７，２４（５）：１６６—１ ６８．
