【机器学习】一种基于模板缩减的新型粒子群遗传聚类算法

第11卷第4期 智能系统学报 Vol.11 No.4 2016年8月 CAAI Transactions on Intelligent Systems Aug.2016 D0I:10.11992.tis.201507026 网络出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20160315.1051.006.html 一种基于模板缩减的新型粒子群遗传聚类算法 贾旋，周治平 (江南大学物联网工程学院，江苏无锡214122) 摘要：针对群聚类算法的速度问题，提出一种基于模板缩减法加速的新型粒子群广义遗传(PS0-GG)聚类算法。 为了充分地同模板缩减法相结合，该算法采用一种广义遗传算法与粒子群算法串行使用，既能增加种群多样性，又 能对模板缩减操作中需要保护的模板进行储存。同时，对每个周期替换粒子数量采用一种递增策略来充分吸取粒 子群快速寻优和遗传算法搜索空间大的特性。实验表明：对8个数据集进行测试，该算法能够在基本不降低聚类品 质的基础上，显著地缩短聚类时间。 关键词：模板缩减：粒子群：广义遗传算法：聚类 中图分类号：TP18文献标志码：A文章编号：1673-4785(2016)04-0561-06 中文引用格式：贾旋，周治平.一种基于模板缩减的新型粒子群遗传聚类算法[J].智能系统学报，2016,11(4)：561566 英文引用格式：JIA Xuan,ZHOU Zhiping.A novel PSO-GGA for clustering based on pattern reduction[J小.CAAI Transactions on Intelligent Systems,2016,11(4):561-566. A novel PSO-GGA for clustering based on pattern reduction JIA Xuan,ZHOU Zhiping (School of Internet of Things Engineering.Jiangnan University,Wuxi 214122,China) Abstract:To address the flaws in clustering speed,this paper proposes a novel PSO-GGA clustering algorithm based on pattern reduction.To fully combine the pattern reduction method,the algorithm uses a generalized genetic algorithm in serial to improve the particle swarm optimization algorithm.This can increase the diversity of samples and protect patterns that need to be saved for compression.At the same time,to determine the number of particles needed to replace the poor particles an incremental strategy is employed.This fully embodies the PSO's ability for rapid search optimization and the genetic algorithm's advantage of a large search space.The experimental results show that the clustering time only required 20 percent compared to the original algorithm without showing any obvi- ous decline in accuracy. Keywords:pattern reduction;PSO;generalized genetic algorithm;clustering 聚类是将一批现实或抽象的数据对象分组成为形状的簇、处理高维数据等能力。而对于这些问题与 多个类或簇的过程。随着计算机技术、网络技术和信 要求，传统的聚类分析方法已然显得无力。 息技术的迅速发展，庞大、海量、复杂、高维的数据信 为解决这些问题，研究者们尝试引入各种群智 息充斥在当前世界的各个领域。如何处理这些数据 能算法，其中粒子群优化算法(PS0)逐渐引起人们 并从中快速、准确地提取有益的信息，越来越引起人 的注意，并在聚类分析中取得了比传统方法更好的 们的普遍关注。面对这些大规模复杂数据，聚类算法效果。从粒子群算法被提出用来解决聚类问题开 需要具有可伸缩性、处理不同类型的数据、发现任意 始，大批学者开展了对它的研究，如文献[1]提出了 收稿日期：2015-07-29.网络出版日期：2016-03-15. 一种结合自适应惯性权重参数和无线折叠迭代混沌 基金项目：江苏省自然科学基金项目(BK20131107);江苏省产学研联映射的混沌粒子群的模糊聚类方法；文献[2]中结 合创新资金-前瞻性联合研究项目(BY2013015-33). 通信作者：贾旋.E-mail:6141905027@vip-jiangnan.cd山.cn. 合Newton移动规则提出了重心加速粒子群算法；文

第 １１ 卷第 ４ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．４ ２０１６ 年 ８ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ａｕｇ． ２０１６ ＤＯＩ：１０．１１９９２．ｔｉｓ．２０１５０７０２６ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ｔｐ．２０１６０３１５．１０５１．００６．ｈｔｍｌ 一种基于模板缩减的新型粒子群遗传聚类算法 贾旋，周治平 （江南大学 物联网工程学院，江苏 无锡 ２１４１２２） 摘 要：针对群聚类算法的速度问题，提出一种基于模板缩减法加速的新型粒子群广义遗传（ＰＳＯ⁃ＧＧＡ）聚类算法。 为了充分地同模板缩减法相结合，该算法采用一种广义遗传算法与粒子群算法串行使用，既能增加种群多样性，又 能对模板缩减操作中需要保护的模板进行储存。 同时，对每个周期替换粒子数量采用一种递增策略来充分吸取粒 子群快速寻优和遗传算法搜索空间大的特性。 实验表明：对 ８ 个数据集进行测试，该算法能够在基本不降低聚类品 质的基础上，显著地缩短聚类时间。 关键词：模板缩减；粒子群；广义遗传算法；聚类 中图分类号： ＴＰ１８ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１６）０４⁃０５６１⁃０６ 中文引用格式：贾旋，周治平． 一种基于模板缩减的新型粒子群遗传聚类算法［Ｊ］． 智能系统学报， ２０１６， １１（４）： ５６１⁃５６６． 英文引用格式：ＪＩＡ Ｘｕａｎ， ＺＨＯＵ Ｚｈｉｐｉｎｇ． Ａ ｎｏｖｅｌ ＰＳＯ⁃ＧＧＡ ｆｏｒ ｃｌｕｓｔｅｒｉｎｇ ｂａｓｅｄ ｏｎ ｐａｔｔｅｒｎ ｒｅｄｕｃｔｉｏｎ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１６， １１（４）： ５６１⁃５６６． Ａ ｎｏｖｅｌ ＰＳＯ⁃ＧＧＡ ｆｏｒ ｃｌｕｓｔｅｒｉｎｇ ｂａｓｅｄ ｏｎ ｐａｔｔｅｒｎ ｒｅｄｕｃｔｉｏｎ ＪＩＡ Ｘｕａｎ， ＺＨＯＵ Ｚｈｉｐｉｎｇ （Ｓｃｈｏｏｌ ｏｆ Ｉｎｔｅｒｎｅｔ ｏｆ Ｔｈｉｎｇｓ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｊｉａｎｇｎａｎ Ｕｎｉｖｅｒｓｉｔｙ， Ｗｕｘｉ ２１４１２２， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｏ ａｄｄｒｅｓｓ ｔｈｅ ｆｌａｗｓ ｉｎ ｃｌｕｓｔｅｒｉｎｇ ｓｐｅｅｄ， ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｓ ａ ｎｏｖｅｌ ＰＳＯ⁃ＧＧＡ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｐａｔｔｅｒｎ ｒｅｄｕｃｔｉｏｎ． Ｔｏ ｆｕｌｌｙ ｃｏｍｂｉｎｅ ｔｈｅ ｐａｔｔｅｒｎ ｒｅｄｕｃｔｉｏｎ ｍｅｔｈｏｄ， ｔｈｅ ａｌｇｏｒｉｔｈｍ ｕｓｅｓ ａ ｇｅｎｅｒａｌｉｚｅｄ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｉｎ ｓｅｒｉａｌ ｔｏ ｉｍｐｒｏｖｅ ｔｈｅ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ． Ｔｈｉｓ ｃａｎ ｉｎｃｒｅａｓｅ ｔｈｅ ｄｉｖｅｒｓｉｔｙ ｏｆ ｓａｍｐｌｅｓ ａｎｄ ｐｒｏｔｅｃｔ ｐａｔｔｅｒｎｓ ｔｈａｔ ｎｅｅｄ ｔｏ ｂｅ ｓａｖｅｄ ｆｏｒ ｃｏｍｐｒｅｓｓｉｏｎ． Ａｔ ｔｈｅ ｓａｍｅ ｔｉｍｅ， ｔｏ ｄｅｔｅｒｍｉｎｅ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｐａｒｔｉｃｌｅｓ ｎｅｅｄｅｄ ｔｏ ｒｅｐｌａｃｅ ｔｈｅ ｐｏｏｒ ｐａｒｔｉｃｌｅｓ ａｎ ｉｎｃｒｅｍｅｎｔａｌ ｓｔｒａｔｅｇｙ ｉｓ ｅｍｐｌｏｙｅｄ． Ｔｈｉｓ ｆｕｌｌｙ ｅｍｂｏｄｉｅｓ ｔｈｅ ＰＳＯ’ｓ ａｂｉｌｉｔｙ ｆｏｒ ｒａｐｉｄ ｓｅａｒｃｈ ｏｐｔｉｍｉｚａｔｉｏｎ ａｎｄ ｔｈｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ’ ｓ ａｄｖａｎｔａｇｅ ｏｆ ａ ｌａｒｇｅ ｓｅａｒｃｈ ｓｐａｃｅ． Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｔｉｍｅ ｏｎｌｙ ｒｅｑｕｉｒｅｄ ２０ ｐｅｒｃｅｎｔ ｃｏｍｐａｒｅｄ ｔｏ ｔｈｅ ｏｒｉｇｉｎａｌ ａｌｇｏｒｉｔｈｍ ｗｉｔｈｏｕｔ ｓｈｏｗｉｎｇ ａｎｙ ｏｂｖｉ⁃ ｏｕｓ ｄｅｃｌｉｎｅ ｉｎ ａｃｃｕｒａｃｙ． Ｋｅｙｗｏｒｄｓ： ｐａｔｔｅｒｎ ｒｅｄｕｃｔｉｏｎ； ＰＳＯ； ｇｅｎｅｒａｌｉｚｅｄ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ； ｃｌｕｓｔｅｒｉｎｇ 收稿日期：２０１５－０７－２９． 网络出版日期：２０１６－０３－１５． 基金项目：江苏省自然科学基金项目（ＢＫ２０１３１１０７）；江苏省产学研联 合创新资金－前瞻性联合研究项目（ＢＹ２０１３０１５⁃３３）． 通信作者：贾旋． Ｅ⁃ｍａｉｌ：６１４１９０５０２７＠ ｖｉｐ．ｊｉａｎｇｎａｎ．ｅｄｕ．ｃｎ． 聚类是将一批现实或抽象的数据对象分组成为 多个类或簇的过程。 随着计算机技术、网络技术和信 息技术的迅速发展， 庞大、海量、复杂、高维的数据信 息充斥在当前世界的各个领域。 如何处理这些数据 并从中快速、准确地提取有益的信息， 越来越引起人 们的普遍关注。 面对这些大规模复杂数据，聚类算法 需要具有可伸缩性、处理不同类型的数据、发现任意 形状的簇、处理高维数据等能力。 而对于这些问题与 要求，传统的聚类分析方法已然显得无力。 为解决这些问题，研究者们尝试引入各种群智 能算法，其中粒子群优化算法（ＰＳＯ）逐渐引起人们 的注意，并在聚类分析中取得了比传统方法更好的 效果。 从粒子群算法被提出用来解决聚类问题开 始，大批学者开展了对它的研究，如文献［１］提出了 一种结合自适应惯性权重参数和无线折叠迭代混沌 映射的混沌粒子群的模糊聚类方法；文献［２］ 中结 合 Ｎｅｗｔｏｎ 移动规则提出了重心加速粒子群算法；文

.562 智能系统学报 第11卷 献[3]提出一种多优量子粒子群算法，以解决基因 v1=wvk+ci(Pid -xg)+c2r2(Pd-x)(3) 表达数据的聚类问题：文献[4]利用一种交互学习 Xk+1=Xk+V+1 (4) 策略在两个种群中确定学习种群与被学习种群来增 粒子通过不断地学习更新，最终飞至解空间中 加粒子群算法的全局搜索能力：文献[5]将基于K 最优解所在的位置，搜索过程结束，最后输出的P 均值的粒子群聚类算法应用于无线传感网能源节约 就是全局最优解。 的管理策略中；文献[6]将粒子群聚类算法应用于 在粒子群聚类的每个周期中，粒子调整完速度 多级阈值转化法中，以解决传统计算复杂度指数性 和位置后，还需要通过最近邻聚类对模板进行分类， 增长问题。 从而得到目标函数中的参数为”，。对于最近邻聚 随着研究的不断深入，基于粒子群的聚类算法 类而言，首先需要计算样本到每个簇心的距离，再取 越来越成熟、可伸缩性越来越强、可处理的数据类型 最小值以判断出模板所属簇，这一步需要耗费大量 也越来也多、使用场合越来越广。同时，聚类精度也 时间。但是，在不断的搜索过程中，必然会存在一些 得到了极大的提高，已基本达到临界值，很难再有较 “静态模板”在搜索前期就处于“最优”状态，即在之 大的提升。但是，这些研究也大都着眼于此，少有文 后搜索过程中不改变其所属簇的模板。如果找到这 献以提升聚类效率、降低聚类时间为目标，以期在处 些“静态模板”，并将其移除以避免再次的最近邻聚 理大规模数据时也能将聚类时间控制在一个可接受 类就可以节省大量的聚类时间。 的范围内。以上述文献为例，都是结合了新型策略 1.2模板缩减 的粒子群聚类算法，以提高聚类精度、扩大适应场景 模板缩减就是发现并压缩静态模板刀的过程， 为目标，都未考虑聚类时间。针对这一问题，本文采 而所谓的静态模板就是那些在之后的聚类过程中基 用一种基于粒子群的模板缩减4法，用来发现并移 本不会改变其所在簇的模板。这种模板缩减的方 除那些在之后的聚类周期中不会或者小概率会改变 法，可分为两步：静态模板检测和静态模板压缩。 簇的模板，以此来提升聚类效率，减小聚类算法周期 1.2.1静态模板检测 的执行时间。但是在此过程中不可避免地会使聚类 文献[8]采用两种方法结合的形式来检测模板 精度有所下降，对此本文采用一种能够充分结合该 是否有着大概率在下一周期聚类时不改变其所在簇： 模板缩减法的广义遗传算法来提升降低的精度。以 1)模板到其簇心的距离在一个很小的范围内：2)在几 期在基本不降低聚类品质的前提下，缩短大量的聚 个连续的迭代周期内不改变簇的模板。 类时间。 1)通过判断模板到簇心的距离来确定静态模 1基于模板缩减的粒子遗传聚类算法 板。准确地说，该方法只认定每个簇中到簇心的距 离小于y的模板是静态的。 1.1 粒子群聚类算法 Y=u±bo (5) 在粒子群聚类算法中，每一个聚类解可以看做搜 式中：μ和σ分别表示簇C中所有模板到簇心的平 索空间中的一个粒子。首先，生成初始群体，即在可 均距离和标准偏差。 行解空间中随机初始化m个粒子，每个粒子代表 通常来说，y不仅可以用来作为一个阈值来筛 种可行解，并由目标函数式(1)确定一个适应度值。 选静态模板，而且还是一个用来平衡准确度和算法 F(X,C)=22w2 收敛速度的参数。 (1) 2)通过判断模板连续保持在相同簇的次数S,来 (1,xC 0= (2) 确定静态模板。直观上来讲，一个静态模板连续保持 0,x:C 在同一个簇的迭代周期数S越大，则该模板是静态 式中：n为数据个数，k为聚簇的个数，d为数据的维 模板的可能性就越高。而设定多大的S作为阀值 数，x:为第i个数据点，：为第i个簇C:的中心，0 就取决于聚类算法的收敛速度或者是最终解的质量。 为数据x:对簇C的隶属度值。 不难发现，对于方法2，需要对周期的每个粒子 每个粒子都将在解空间中运动，并由运动速度 参数样本分类数据进行储存，才可以计算连续次数 决定其飞行方向和距离。粒子通过式(3)、(4)不断 S。假设S=3,就至少需要参考之前两个迭代周 调整自己的速度V:和位置X,来搜索新解。同时每 期中的样本分类数据，才可以判断出哪些模板可视为 个粒子自己搜索到的最优解Pa,以及整个粒子群 “静态模板”。对于文献[8]的方法来说，S的储存不 经历过的最优位置P。 止麻烦而且对于算法而言没有任何帮助，只会增加算

献［３］提出一种多优量子粒子群算法，以解决基因 表达数据的聚类问题；文献［４］利用一种交互学习 策略在两个种群中确定学习种群与被学习种群来增 加粒子群算法的全局搜索能力；文献［５］ 将基于 Ｋ 均值的粒子群聚类算法应用于无线传感网能源节约 的管理策略中；文献［６］将粒子群聚类算法应用于 多级阈值转化法中，以解决传统计算复杂度指数性 增长问题。 随着研究的不断深入，基于粒子群的聚类算法 越来越成熟、可伸缩性越来越强、可处理的数据类型 也越来也多、使用场合越来越广。 同时，聚类精度也 得到了极大的提高，已基本达到临界值，很难再有较 大的提升。 但是，这些研究也大都着眼于此，少有文 献以提升聚类效率、降低聚类时间为目标，以期在处 理大规模数据时也能将聚类时间控制在一个可接受 的范围内。 以上述文献为例，都是结合了新型策略 的粒子群聚类算法，以提高聚类精度、扩大适应场景 为目标，都未考虑聚类时间。 针对这一问题，本文采 用一种基于粒子群的模板缩减［４］ 法，用来发现并移 除那些在之后的聚类周期中不会或者小概率会改变 簇的模板，以此来提升聚类效率，减小聚类算法周期 的执行时间。 但是在此过程中不可避免地会使聚类 精度有所下降，对此本文采用一种能够充分结合该 模板缩减法的广义遗传算法来提升降低的精度。 以 期在基本不降低聚类品质的前提下，缩短大量的聚 类时间。 １ 基于模板缩减的粒子遗传聚类算法 １．１ 粒子群聚类算法 在粒子群聚类算法中，每一个聚类解可以看做搜 索空间中的一个粒子。 首先，生成初始群体，即在可 行解空间中随机初始化 ｍ 个粒子，每个粒子代表一 种可行解，并由目标函数式（１）确定一个适应度值。 Ｆ（Ｘ，Ｃ） ＝ ∑ ｎ ｉ ＝ １ ∑ ｋ ｊ ＝ １ ｗｉｊ ∑ Ｄ ｖ ＝ １ （ｘｉｖ － ｚｉｖ） ２ （１） ｗｉｊ ＝ １， ｘｉ ∈ Ｃｊ ０， ｘｉ ∉ Ｃｊ { （２） 式中：ｎ 为数据个数，ｋ 为聚簇的个数，ｄ 为数据的维 数， ｘｉ 为第 ｉ 个数据点， ｚｉ 为第 ｉ 个簇 Ｃｉ的中心，ｗｉｊ 为数据 ｘｉ 对簇 Ｃｊ的隶属度值。 每个粒子都将在解空间中运动，并由运动速度 决定其飞行方向和距离。 粒子通过式（３）、（４）不断 调整自己的速度 Ｖｉ 和位置 Ｘｉ 来搜索新解。 同时每 个粒子自己搜索到的最优解 Ｐｉｄ ，以及整个粒子群 经历过的最优位置 Ｐｇｄ 。 ｖｋ＋１ ＝ ｗｖｋ ＋ ｃ１ ｒ１（Ｐｉｄ － ｘｋ） ＋ ｃ２ ｒ２（Ｐｇｄ － ｘｋ） （３） ｘｋ＋１ ＝ ｘｋ ＋ ｖｋ＋１ （４） 粒子通过不断地学习更新，最终飞至解空间中 最优解所在的位置，搜索过程结束，最后输出的 Ｐｇｄ 就是全局最优解。 在粒子群聚类的每个周期中，粒子调整完速度 和位置后，还需要通过最近邻聚类对模板进行分类， 从而得到目标函数中的参数为 ｗｉｊ。 对于最近邻聚 类而言，首先需要计算样本到每个簇心的距离，再取 最小值以判断出模板所属簇，这一步需要耗费大量 时间。 但是，在不断的搜索过程中，必然会存在一些 “静态模板”在搜索前期就处于“最优”状态，即在之 后搜索过程中不改变其所属簇的模板。 如果找到这 些“静态模板”，并将其移除以避免再次的最近邻聚 类就可以节省大量的聚类时间。 １．２ 模板缩减 模板缩减就是发现并压缩静态模板［７］ 的过程， 而所谓的静态模板就是那些在之后的聚类过程中基 本不会改变其所在簇的模板。 这种模板缩减的方 法，可分为两步：静态模板检测和静态模板压缩。 １．２．１ 静态模板检测 文献［８］采用两种方法结合的形式来检测模板 是否有着大概率在下一周期聚类时不改变其所在簇： １）模板到其簇心的距离在一个很小的范围内；２）在几 个连续的迭代周期内不改变簇的模板。 １）通过判断模板到簇心的距离来确定静态模 板。 准确地说，该方法只认定每个簇中到簇心的距 离小于 γ 的模板是静态的。 γ ＝ μ ± ｂσ （５） 式中： μ 和 σ 分别表示簇 Ｃｉ中所有模板到簇心的平 均距离和标准偏差。 通常来说， γ 不仅可以用来作为一个阈值来筛 选静态模板，而且还是一个用来平衡准确度和算法 收敛速度的参数。 ２）通过判断模板连续保持在相同簇的次数 Ｓｉｊ来 确定静态模板。 直观上来讲，一个静态模板连续保持 在同一个簇的迭代周期数 Ｓｍａｘ越大，则该模板是静态 模板的可能性就越高。 而设定多大的 Ｓｍａｘ作为阀值 就取决于聚类算法的收敛速度或者是最终解的质量。 不难发现，对于方法 ２，需要对周期的每个粒子 参数样本分类数据进行储存，才可以计算连续次数 Ｓｉｊ。 假设 Ｓｍａｘ ＝ ３， 就至少需要参考之前两个迭代周 期中的样本分类数据，才可以判断出哪些模板可视为 “静态模板”。 对于文献［８］的方法来说，Ｓｉｊ的储存不 止麻烦而且对于算法而言没有任何帮助，只会增加算 ·５６２· 智 能 系 统 学 报 第 １１ 卷

第4期 贾旋，等：一种基于模板缩减的新型粒子群遗传聚类算法 ·563· 法的复杂度。但是本文基于广义遗传算法的粒子群 自然演化中，近亲繁殖往往不利于种群的繁荣，而远 聚类算法就可以很好地解决这一问题。对于广义遗 亲杂交往往会培育出更优良的品种：变异作为一种 传算法而言，本身就有保护分类数据的特点，而且还 重要的进化方式，是保持物种多样性的必要手段。 可以通过遗传算法来增加其样本多样性。因此，本文 因此，我们首先对每个迭代周期产生的分类数据进 算法不仅可以对分类的数据用一种新型的方式进行 行储存，以扩大遗传种群的数量，因为只有非常大的 储存，还可以很好地利用这些数据产生新的遗传粒子 种群量才能更好地进行远亲杂交。再从中选取一组 以替换适应值低的PSO粒子。 种群粒子与当前的“优质”粒子进行交叉、变异，生 1.2.2静态模板压缩 成新的粒子。此处，通过系数！来避免“近亲”繁殖， 静态模板压缩操作是为了记录、传送静态模板 即不选择近代生成的种群粒子。该算法通过不断地 的信息给后期的其他操作，以确保没有多余的计算 补充、记录、生成新的种群粒子，在不断寻优的过程 被执行。该操作的数学表达形式如式(6)所示。 中，也增加了粒子群聚类的样本多样性。 x=(X UT))/R (6) 1.4基于模板缩减的新型粒子群遗传聚类算法 式中：X表示所有输入模板集合，Q表示所有静态 该算法创新性地将一种修改后的新型广义遗传 模板集合，g表示静态模板的压缩模板集合，x表示 算法同基于模板缩减的粒子群聚类算法相结合，在充 输入模板的压缩模板集合。 分同模板缩减相结合的同时，也提高了样本多样性。 基于模板缩减法的粒子群聚类，每个迭代周期 基于模板缩减的粒子群聚类算法，其对于初始 只需要对属于x的模板执行聚类操作。这种方式， 中心的敏感性不仅没有降低反而会更加敏感，将严 可以确保Q中的静态模板不被重复计算。 重导致聚类精度的不稳定。本文通过选取10%的 样本进行简单的k-means聚类，来初始簇心。同时， 对于静态压缩模板9，本文提出一种新型的编 为了更好地提高由模板缩减而降低的聚类精度，本 码方式，该方法可以很好地保存输入模板的信息，同 文在聚类迭代中并行k-means,即在重新分配完粒 时也可以完美地同复合了k-means的粒子群聚类相 子后，使用式(8)来重新计算簇心。 结合。 其中，每个静态压缩模板g中包含两种信息，分 6=立0/20g,i=1,2…,k (8) =1 j=1 别为属于簇C,的静态模板的平均特征值aw:,如式 考虑到迭代前期粒子群聚类不需要太多的遗传 (7)所示，和属于簇C的静态模板的个数s:。 粒子，而后期特别是当粒子群聚类陷入局部最优时 am,=∑，/l,l,,ec:and,∈R (7) 往往需要较大量的遗传粒子来增加其调出陷阱的能 1.3广义遗传算法 力。因此，对替换粒子量C采用一种递增策略来解 采用模板压缩方法减少计算时间的过程中，不 决这一矛盾。 可避免地会导致聚类精度的下降，也就是说会比传 C=+(1-prN/PN)x (9) 统PS0聚类更容易陷入“早熟”收敛。文献[8]采 式中：pW代表压缩后模板的数量，PN表示模板的 用一种“多星”操作来解决这一问题，即通过随机选 总数量。中。表示没有模板缩减时，最小替换个数； 取种群中粒子相互交叉产生新的粒子，类似于一种 少表示最大可以增加的替换个数； 简易的“遗传”算法。但是，在粒子群寻优的过程 该聚类算法的实现过程如下： 中，所有粒子都不断地向着个体最优解和全局最优 Begin 解靠近。也就是说，在迭代了许多代后，整个种群可 Initialize 能已经大部分收敛，但是还没有得到稳定的全局最 输入样本数据集X,聚类数据k: 优解。此时整个种群的平均适应度值较高，而且最 设置粒子群数m,替换粒子数C; 优个体的适应度值与全体适应度均值间的差别不 选取10%的X,初始化种群P(0): 大，即使在种群中随机选取粒子进行交叉产生新的 while不满足停止准则 粒子，也没有足够的力量推动种群的寻优找到最优 根据式(1)计算每个粒子适应度 解，从而陷入到“局部”最优。 更新Pa和P: 为了解决这一问题，本文更好地吸取了遗传算 fori=1:M-C 法的优点，修改了一种广义遗传算法来增加样本多 根据式(3)、(4)更新粒子i的速度和位置： 样性，提高算法跳出“局部”最优的能力。考虑到在 for每个属于粒子i数据集x的样本

法的复杂度。 但是本文基于广义遗传算法的粒子群 聚类算法就可以很好地解决这一问题。 对于广义遗 传算法而言，本身就有保护分类数据的特点，而且还 可以通过遗传算法来增加其样本多样性。 因此，本文 算法不仅可以对分类的数据用一种新型的方式进行 储存，还可以很好地利用这些数据产生新的遗传粒子 以替换适应值低的 ＰＳＯ 粒子。 １．２．２ 静态模板压缩 静态模板压缩操作是为了记录、传送静态模板 的信息给后期的其他操作，以确保没有多余的计算 被执行。 该操作的数学表达形式如式（６）所示。 ｘ ＝ （Ｘ ∪ {ｒ} ） ／ Ｒ （６） 式中： Ｘ 表示所有输入模板集合， Ｑ 表示所有静态 模板集合， ｑ － 表示静态模板的压缩模板集合， ｘ － 表示 输入模板的压缩模板集合。 基于模板缩减法的粒子群聚类，每个迭代周期 只需要对属于 ｘ － 的模板执行聚类操作。 这种方式， 可以确保 Ｑ 中的静态模板不被重复计算。 对于静态压缩模板 ｑ － ，本文提出一种新型的编 码方式，该方法可以很好地保存输入模板的信息，同 时也可以完美地同复合了 ｋ⁃ｍｅａｎｓ 的粒子群聚类相 结合。 其中，每个静态压缩模板 ｑ － 中包含两种信息，分 别为属于簇 Ｃｉ的静态模板的平均特征值 ａｖｉ，如式 （７）所示，和属于簇 Ｃｉ的静态模板的个数 ｓｉ。 ａｖｉ ＝ ∑ｚｐ ／ ｚｐ ，ｚｐ ∈ ｃｉ ａｎｄ ｚｐ ∈ Ｒ （７） １．３ 广义遗传算法 采用模板压缩方法减少计算时间的过程中，不 可避免地会导致聚类精度的下降，也就是说会比传 统 ＰＳＯ 聚类更容易陷入“早熟” 收敛。 文献［８］ 采 用一种“多星”操作来解决这一问题，即通过随机选 取种群中粒子相互交叉产生新的粒子，类似于一种 简易的“遗传” 算法。 但是，在粒子群寻优的过程 中，所有粒子都不断地向着个体最优解和全局最优 解靠近。 也就是说，在迭代了许多代后，整个种群可 能已经大部分收敛，但是还没有得到稳定的全局最 优解。 此时整个种群的平均适应度值较高，而且最 优个体的适应度值与全体适应度均值间的差别不 大，即使在种群中随机选取粒子进行交叉产生新的 粒子，也没有足够的力量推动种群的寻优找到最优 解，从而陷入到“局部”最优。 为了解决这一问题，本文更好地吸取了遗传算 法的优点，修改了一种广义遗传算法来增加样本多 样性，提高算法跳出“局部”最优的能力。 考虑到在 自然演化中，近亲繁殖往往不利于种群的繁荣，而远 亲杂交往往会培育出更优良的品种；变异作为一种 重要的进化方式，是保持物种多样性的必要手段。 因此，我们首先对每个迭代周期产生的分类数据进 行储存，以扩大遗传种群的数量，因为只有非常大的 种群量才能更好地进行远亲杂交。 再从中选取一组 种群粒子与当前的“优质”粒子进行交叉、变异，生 成新的粒子。 此处，通过系数 ｌ 来避免“近亲”繁殖， 即不选择近代生成的种群粒子。 该算法通过不断地 补充、记录、生成新的种群粒子，在不断寻优的过程 中，也增加了粒子群聚类的样本多样性。 １．４ 基于模板缩减的新型粒子群遗传聚类算法 该算法创新性地将一种修改后的新型广义遗传 算法同基于模板缩减的粒子群聚类算法相结合，在充 分同模板缩减相结合的同时，也提高了样本多样性。 基于模板缩减的粒子群聚类算法，其对于初始 中心的敏感性不仅没有降低反而会更加敏感，将严 重导致聚类精度的不稳定。 本文通过选取 １０％的 样本进行简单的 ｋ⁃ｍｅａｎｓ 聚类，来初始簇心。 同时， 为了更好地提高由模板缩减而降低的聚类精度，本 文在聚类迭代中并行 ｋ⁃ｍｅａｎｓ，即在重新分配完粒 子后，使用式（８）来重新计算簇心。 ｃｉ ＝ ∑ ｎ ｊ ＝ １ ｗｉｊ ｘｊ ／ ∑ ｎ ｊ ＝ １ ｗｉｊ， ｉ ＝ １，２，…，ｋ （８） 考虑到迭代前期粒子群聚类不需要太多的遗传 粒子，而后期特别是当粒子群聚类陷入局部最优时 往往需要较大量的遗传粒子来增加其调出陷阱的能 力。 因此，对替换粒子量 Ｃ 采用一种递增策略来解 决这一矛盾。 Ｃ ＝ φｍｉｎ ＋ （１ － ｐｒＮ／ ＰＮ） × φｍａｘ （９） 式中：ｐｒＮ 代表压缩后模板的数量，ＰＮ 表示模板的 总数量。 Φｍｉｎ 表示没有模板缩减时，最小替换个数； Φｍａｘ 表示最大可以增加的替换个数； 该聚类算法的实现过程如下： Ｂｅｇｉｎ Ｉｎｉｔｉａｌｉｚｅ 输入样本数据集 Ｘ ，聚类数据 ｋ； 设置粒子群数 ｍ，替换粒子数 Ｃ； 选取 １０％的 Ｘ ，初始化种群 Ｐ（０）； ｗｈｉｌｅ 不满足停止准则 根据式（１）计算每个粒子适应度 更新 Ｐｉｄ 和 Ｐｇｄ ； ｆｏｒ ｉ ＝ １：Ｍ － Ｃ 根据式（３）、（４）更新粒子 ｉ 的速度和位置； ｆｏｒ 每个属于粒子 ｉ 数据集 ｘ － 的样本 第 ４ 期 贾旋，等：一种基于模板缩减的新型粒子群遗传聚类算法 ·５６３·

,564 智能系统学报 第11卷 根据最近邻法则划分： 问题：更典型的，像文献[11]这些针对粒子群聚类算 保存到广义遗传算法的种群中； 法需要预先设定聚类中心个数的问题进行算法改进 根据式(8)重新计算聚类中心： 的策略，对粒子群算法本身没有什么变动，和本文算 检测生成静态压缩模板9； 法就更谈不上什么冲突了；所以，本次试验只采用基 根据式(6)生成新的x; 本的粒子群聚类(PSO)和典型的混合k-means的 end for kmPS0[]混合聚类算法（记为KP)进行实验分析，并 同文献[7]的MPREPSO算法(MP)比较来测试本文 end for for i=1:C 算法的性能。 在区间[1，n-l]中生成一个随机整数l: 仿真实验基于MATLAB201Ob平台，计算机的 选择第！代种群与当种群进行交叉、变异操 硬件配置为：Intel Core i5-4200MCPU2.5GHz、4 作生成第n+1代种群； GB RAM。选取UCI数据库中的8个典型数据集在 end for 该环境下对本文和比较算法进行测试。其中，数据 end while 集的特性如表1所示。 输出最优P对应的广义遗传算法种群中的 表1实验数据集的特性 最优分类： Table 1 The feature of experimental data set End 数据集 数据集个数 类 维数 1.5计算复杂度分析 Iris 150 3 4 从1.4中的算法流程中可以看出，每个周期需 Glass 214 7 9 要进行以下5步计算：适应度计算、粒子更新、最近 Ionosphere 351 2 34 邻划分、静态模板检测和缩减、遗传粒子计算。其 Balance Scale 625 3 中，适应度计算和最近邻划分，由于需要对数据到各 CMC 1472 3 g 个簇心的距离，其计算复杂度最高，为O(mm'n2): Yeast 1484 10 8 减部分，只需要对划分后的数据进行求平均值、比较 Wall following 2 5456 4 2 和删除操作，所以其计算复杂度为O(mm'n);其余 Wall following 4 5456 4 操作，可忽略不计。综上，本文算法的计算复杂度为 O(rmmn'n2),其中r表示迭代周期数，n'表示非静态 根据聚类准确度、运行时间对本文的基于模板 模板数。可以看出，随着静态模板数的增加其计算 缩减的粒子群广义遗传聚类算法(PR-PSO-GGA)聚 复杂度逐渐减小，从而达到了降低聚类时间的目的。 类性能进行分析比较，考虑到实验要求，4种基于粒 子群的聚类算法参数一致，设置同文献[7]相同： 2实验结果分析 w=0.72,c1=c2=2。每种算法独立运行20次，计算 2.1实验环境 各自的适应度值、accuracyts)、Rand Index)指标和 目前，大部分对于粒子群聚类算法的改进基本都 运行时间，聚类结果如表2所示。其中，适应度值函 是从适应值函数、编码方式、参数调整等方面着手。 数由式(1)定义。 而本文算法，只是从模板方面着手进行缩减，每个周 2.2实验分析 期需要对多少个样本分类对目前的粒子群改进没有 对于评价聚类算法的聚类品质而言，低适应度 丝毫的影响，只需要调整不同编码方式就可以同这些 值一定代表着高品质，但较高accuracy值和Rand 改进措施完美衔接。同时，虽然很多改进措施是通过 ndex值却不一定意味着较高的品质。因为，基于粒 混合不同的策略来优化粒子群的聚类算法，但大多都 子群的聚类算法都是围绕着适应度值在不断地寻 是将采用的策略同粒子群并行使用，对每个周期需要 优，以期找到最低的适应度值，这就意味着适应度值 对多少个样本进行操作没有要求。例如，文献[9]提 越低该聚类算法的寻优能力越强，聚类算法的聚类 出的基于模糊c均值和粒子群的模糊聚类方法；文献 品质也就越高。accuracy和Rand Index指标作为外 [10]提出了使用边界约束策略的自适应粒子群聚类； 部评价指标和目标函数有着密切联系，只能大致评 这类文献，只是引入一些改进策略混合并行使用来改 价聚类结果，不能完美地表现粒子群聚类算法寻优 善粒子群算法的一些缺陷，同样对每个周期对多少个 能力的优劣。因此，本文实验分析将根据适应度值 样本进行操作也没有影响，同本文算法衔接没有任何 来评价聚类结果，聚类accuracy和Rand Index值仅

根据最近邻法则划分； 保存到广义遗传算法的种群中； 根据式（８）重新计算聚类中心； 检测生成静态压缩模板 ｑ － ； 根据式（６）生成新的 ｘ － ； ｅｎｄ ｆｏｒ ｅｎｄ ｆｏｒ ｆｏｒ ｉ ＝ １：Ｃ 在区间［１， ｎ － ｌ ］中生成一个随机整数 ｌ； 选择第 ｌ 代种群与当种群进行交叉、变异操 作生成第 ｎ＋１ 代种群； ｅｎｄ ｆｏｒ ｅｎｄ ｗｈｉｌｅ 输出最优 Ｐｇｄ 对应的广义遗传算法种群中的 最优分类； Ｅｎｄ １．５ 计算复杂度分析 从 １．４ 中的算法流程中可以看出，每个周期需 要进行以下 ５ 步计算：适应度计算、粒子更新、最近 邻划分、静态模板检测和缩减、遗传粒子计算。 其 中，适应度计算和最近邻划分，由于需要对数据到各 个簇心的距离，其计算复杂度最高，为 Ｏ（ ｍｎ′ｎ ２ ）； 减部分，只需要对划分后的数据进行求平均值、比较 和删除操作，所以其计算复杂度为 Ｏ（ｍｎ′ｎ）；其余 操作，可忽略不计。 综上，本文算法的计算复杂度为 Ｏ（ｒｍｎ′ｎ ２ ），其中 ｒ 表示迭代周期数，ｎ′表示非静态 模板数。 可以看出，随着静态模板数的增加其计算 复杂度逐渐减小，从而达到了降低聚类时间的目的。 ２ 实验结果分析 ２．１ 实验环境 目前，大部分对于粒子群聚类算法的改进基本都 是从适应值函数、编码方式、参数调整等方面着手。 而本文算法，只是从模板方面着手进行缩减，每个周 期需要对多少个样本分类对目前的粒子群改进没有 丝毫的影响，只需要调整不同编码方式就可以同这些 改进措施完美衔接。 同时，虽然很多改进措施是通过 混合不同的策略来优化粒子群的聚类算法，但大多都 是将采用的策略同粒子群并行使用，对每个周期需要 对多少个样本进行操作没有要求。 例如，文献［９］提 出的基于模糊 ｃ 均值和粒子群的模糊聚类方法；文献 ［１０］提出了使用边界约束策略的自适应粒子群聚类； 这类文献，只是引入一些改进策略混合并行使用来改 善粒子群算法的一些缺陷，同样对每个周期对多少个 样本进行操作也没有影响，同本文算法衔接没有任何 问题；更典型的，像文献［１１］这些针对粒子群聚类算 法需要预先设定聚类中心个数的问题进行算法改进 的策略，对粒子群算法本身没有什么变动，和本文算 法就更谈不上什么冲突了；所以，本次试验只采用基 本的粒子群聚类（ＰＳＯ） 和典型的混合 ｋ⁃ｍｅａｎｓ 的 ｋｍＰＳＯ ［ １２］混合聚类算法（记为 ＫＰ）进行实验分析，并 同文献［７］的 ＭＰＲＥＰＳＯ 算法（ＭＰ）比较来测试本文 算法的性能。 仿真实验基于 ＭＡＴＬＡＢ２０１０ｂ 平台，计算机的 硬件配置为：Ｉｎｔｅｌ Ｃｏｒｅ ｉ５ － ４２００Ｍ ＣＰＵ ２． ５ ＧＨｚ、４ ＧＢ ＲＡＭ。 选取 ＵＣＩ 数据库中的 ８ 个典型数据集在 该环境下对本文和比较算法进行测试。 其中，数据 集的特性如表 １ 所示。 表 １ 实验数据集的特性 Ｔａｂｌｅ １ Ｔｈｅ ｆｅａｔｕｒｅ ｏｆ ｅｘｐｅｒｉｍｅｎｔａｌ ｄａｔａ ｓｅｔ 数据集 数据集个数 类 维数 Ｉｒｉｓ １５０ ３ ４ Ｇｌａｓｓ ２１４ ７ ９ Ｉｏｎｏｓｐｈｅｒｅ ３５１ ２ ３４ Ｂａｌａｎｃｅ Ｓｃａｌｅ ６２５ ３ ４ ＣＭＣ １ ４７２ ３ １９ Ｙｅａｓｔ １ ４８４ １０ ８ Ｗａｌｌ ｆｏｌｌｏｗｉｎｇ ２ ５ ４５６ ４ ２ Ｗａｌｌ ｆｏｌｌｏｗｉｎｇ ４ ５ ４５６ ４ ４ 根据聚类准确度、运行时间对本文的基于模板 缩减的粒子群广义遗传聚类算法（ＰＲ⁃ＰＳＯ⁃ＧＧＡ）聚 类性能进行分析比较，考虑到实验要求，４ 种基于粒 子群的聚类算法参数一致，设置同文献［７］ 相同： ｗ ＝ ０．７２，ｃ１ ＝ ｃ２ ＝ ２。 每种算法独立运行 ２０ 次，计算 各自的适应度值、ａｃｃｕｒａｃｙ ［８］ 、Ｒａｎｄ Ｉｎｄｅｘ ［３］ 指标和 运行时间，聚类结果如表 ２ 所示。 其中，适应度值函 数由式（１）定义。 ２．２ 实验分析 对于评价聚类算法的聚类品质而言，低适应度 值一定代表着高品质，但较高 ａｃｃｕｒａｃｙ 值和 Ｒａｎｄ Ｉｎｄｅｘ 值却不一定意味着较高的品质。 因为，基于粒 子群的聚类算法都是围绕着适应度值在不断地寻 优，以期找到最低的适应度值，这就意味着适应度值 越低该聚类算法的寻优能力越强，聚类算法的聚类 品质也就越高。 ａｃｃｕｒａｃｙ 和 Ｒａｎｄ Ｉｎｄｅｘ 指标作为外 部评价指标和目标函数有着密切联系，只能大致评 价聚类结果，不能完美地表现粒子群聚类算法寻优 能力的优劣。 因此，本文实验分析将根据适应度值 来评价聚类结果，聚类 ａｃｃｕｒａｃｙ 和 Ｒａｎｄ Ｉｎｄｅｘ 值仅 ·５６４· 智 能 系 统 学 报 第 １１ 卷

第4期 贾旋，等：一种基于模板缩减的新型粒子群遗传聚类算法 ·565 作为参考数据。 同时收敛周期也较长。因此，虽然模板缩减法会降 各数据集实验结果如表2所示。 低聚类精度，但是本文算法通过广义遗传算法等一 从表2中可以看出，针对不同的数据集，基于模 系列的措施却可以在缩短聚类时间的基础上提高其 板缩减的粒子群广义遗传算法的聚类时间只需要原 聚类精度。 算法20%左右的时间，对有些数据集甚至只需要 表2各数据集实验结果 10%的聚类时间。这些缩短的聚类时间一部分是由 Table 2 The result of experimental data set 于模板缩减法移除模板降低的周期执行时间所造成 Rand 数据集 算法 目标函数精度 时间 的，另一部分是由于串行了广义遗传算法减小了收 Index 敛周期所造成的，具体可参考图1和图2。 PSO 105.44 0.90 0.89 5.21 Glass KP 97.22 0.90 0.89 1.96 0.50 -+…pSO Iris MP 100.15 0.45 0.90 0.89 0.58 ---KP 0.40 --MP 本文 97.28 0.89 0.88 0.44 0.35 本文 PSO 276.54 0.49 0.62 7.55 0.30 KP 205.98 0.50 0.64 8.92 0.25 Glass MP 231.00 0.47 0.63 0.93 0.20 0.15 本文 216.00 0.48 0.63 0.84 0.10 PSO 858.74 0.69 0.57 4.07 0.05 796.17 0.71 0.58 2.96 0 lonosphere 4 681012141618 MP 815.67 0.70 0.58 1.14 迭代周期 本文 796.25 0.71 0.58 0.92 图1周期执行时间图 PSO 1431.73 0.53 0.60 15.81 Fig.1 The graph of cycle time Balance KP 1423.92 0.52 0.59 8.59 Glass Scale MP 1436.78 0.53 0.60 2.35 550 -+…PS0 本文 1427.180.53 0.60 2.07 500 ---KP -MP PSO 5618.57 0.40 0.56 41.99 450 ·…本文 KP 5541.63 0.40 0.56 28.96 4 CMC MP 5559.27 0.40 0.56 6.38 350 本文 5542.120.40 0.56 5.49 300 4+++十+++++ PSO 273.74 0.31 0.74 62.95 250 KP 235.73 0.36 0.75 214.55 Yeast 200 MP 249.21 0.34 0.74 8.58 101520 2530 本文 241.67 0.35 0.75 8.11 迭代周期 PSO 1299.33 0.62 0.72 355.72 图2目标函数收敛图 Wall KP 1292.42 0.66 0.72 186.52 Fig.2 The convergence graph of objective function following2 MP 1284.02 0.65 0.72 36.64 从图1可以看出，P和本文算法开始的周期 本文 1293.390.66 0.72 29.93 执行时间高于PS0和KP算法，并随着迭代次数的 PS03555.690.43 0.59 241.44 增加周期执行时间迅速减小。这说明基于模板压缩 Wall KP 3381.330.41 0.58 211.98 法粒子群算法虽说会增加算法复杂度，但随着算法 following4 MP 3371.740.41 0.58 32.67 本文3381.890.41 0.58 29.05 的运行其周期执行时间越来越短，将大大节约总体 聚类时间。从图2可以看出，算法迅速下降到一个 2)对于并行k-means的粒子群聚类算法而言， 本文算法的聚类结果对于Iis等数据集的目标函数 较低值并在短期内完成聚类。这表明较其他算法， 值只下低了千分之几，却只需要其25%~30%的聚 本文算法有着较快收敛速度和较低收敛周期。 类时间。其中，对精度降低最高的Glass数据集而 对表2的数据具体分析，可以看出： 言，目标函数下降了4.8%，但是其聚类时间却缩短 1)比起典型的粒子群聚类而言，本文算法不仅 了90%以上。本文算法通过增加广义遗传算法来 缩短了大量的时间，而且聚类精度也有所提高。典 加快收敛速度，在减少了每个周期的聚类时间的前 型的粒子群聚类算法只通过粒子间的个体协作与竞 提下也缩短了其聚类周期数。但是本文算法却不能 争来搜索最优解，不可避免会陷入“局部最优”中

作为参考数据。 各数据集实验结果如表 ２ 所示。 从表 ２ 中可以看出，针对不同的数据集，基于模 板缩减的粒子群广义遗传算法的聚类时间只需要原 算法 ２０％ 左右的时间，对有些数据集甚至只需要 １０％的聚类时间。 这些缩短的聚类时间一部分是由 于模板缩减法移除模板降低的周期执行时间所造成 的，另一部分是由于串行了广义遗传算法减小了收 敛周期所造成的，具体可参考图 １ 和图 ２。 图 １ 周期执行时间图 Ｆｉｇ．１ Ｔｈｅ ｇｒａｐｈ ｏｆ ｃｙｃｌｅ ｔｉｍｅ 图 ２ 目标函数收敛图 Ｆｉｇ．２ Ｔｈｅ ｃｏｎｖｅｒｇｅｎｃｅ ｇｒａｐｈ ｏｆ ｏｂｊｅｃｔｉｖｅ ｆｕｎｃｔｉｏｎ 从图 １ 可以看出，ＭＰ 和本文算法开始的周期 执行时间高于 ＰＳＯ 和 ＫＰ 算法，并随着迭代次数的 增加周期执行时间迅速减小。 这说明基于模板压缩 法粒子群算法虽说会增加算法复杂度，但随着算法 的运行其周期执行时间越来越短，将大大节约总体 聚类时间。 从图 ２ 可以看出，算法迅速下降到一个 较低值并在短期内完成聚类。 这表明较其他算法， 本文算法有着较快收敛速度和较低收敛周期。 对表 ２ 的数据具体分析，可以看出： １）比起典型的粒子群聚类而言，本文算法不仅 缩短了大量的时间，而且聚类精度也有所提高。 典 型的粒子群聚类算法只通过粒子间的个体协作与竞 争来搜索最优解，不可避免会陷入“局部最优” 中， 同时收敛周期也较长。 因此，虽然模板缩减法会降 低聚类精度，但是本文算法通过广义遗传算法等一 系列的措施却可以在缩短聚类时间的基础上提高其 聚类精度。 表 ２ 各数据集实验结果 Ｔａｂｌｅ ２ Ｔｈｅ ｒｅｓｕｌｔ ｏｆ ｅｘｐｅｒｉｍｅｎｔａｌ ｄａｔａ ｓｅｔ 数据集 算法 目标函数 精度 Ｒａｎｄ Ｉｎｄｅｘ 时间 Ｉｒｉｓ ＰＳＯ １０５．４４ ０．９０ ０．８９ ５．２１ ＫＰ ９７．２２ ０．９０ ０．８９ １．９６ ＭＰ １００．１５ ０．９０ ０．８９ ０．５８ 本文 ９７．２８ ０．８９ ０．８８ ０．４４ Ｇｌａｓｓ ＰＳＯ ２７６．５４ ０．４９ ０．６２ ７．５５ ＫＰ ２０５．９８ ０．５０ ０．６４ ８．９２ ＭＰ ２３１．００ ０．４７ ０．６３ ０．９３ 本文 ２１６．００ ０．４８ ０．６３ ０．８４ Ｉｏｎｏｓｐｈｅｒｅ ＰＳＯ ８５８．７４ ０．６９ ０．５７ ４．０７ ＫＰ ７９６．１７ ０．７１ ０．５８ ２．９６ ＭＰ ８１５．６７ ０．７０ ０．５８ １．１４ 本文 ７９６．２５ ０．７１ ０．５８ ０．９２ Ｂａｌａｎｃｅ Ｓｃａｌｅ ＰＳＯ １４３１．７３ ０．５３ ０．６０ １５．８１ ＫＰ １４２３．９２ ０．５２ ０．５９ ８．５９ ＭＰ １４３６．７８ ０．５３ ０．６０ ２．３５ 本文 １４２７．１８ ０．５３ ０．６０ ２．０７ ＣＭＣ ＰＳＯ ５６１８．５７ ０．４０ ０．５６ ４１．９９ ＫＰ ５５４１．６３ ０．４０ ０．５６ ２８．９６ ＭＰ ５５５９．２７ ０．４０ ０．５６ ６．３８ 本文 ５５４２．１２ ０．４０ ０．５６ ５．４９ Ｙｅａｓｔ ＰＳＯ ２７３．７４ ０．３１ ０．７４ ６２．９５ ＫＰ ２３５．７３ ０．３６ ０．７５ ２１４．５５ ＭＰ ２４９．２１ ０．３４ ０．７４ ８．５８ 本文 ２４１．６７ ０．３５ ０．７５ ８．１１ Ｗａｌｌ ｆｏｌｌｏｗｉｎｇ２ ＰＳＯ １ ２９９．３３ ０．６２ ０．７２ ３５５．７２ ＫＰ １ ２９２．４２ ０．６６ ０．７２ １８６．５２ ＭＰ １ ２８４．０２ ０．６５ ０．７２ ３６．６４ 本文 １ ２９３．３９ ０．６６ ０．７２ ２９．９３ Ｗａｌｌ ｆｏｌｌｏｗｉｎｇ４ ＰＳＯ ３ ５５５．６９ ０．４３ ０．５９ ２４１．４４ ＫＰ ３ ３８１．３３ ０．４１ ０．５８ ２１１．９８ ＭＰ ３ ３７１．７４ ０．４１ ０．５８ ３２．６７ 本文 ３ ３８１．８９ ０．４１ ０．５８ ２９．０５ ２）对于并行 ｋ⁃ｍｅａｎｓ 的粒子群聚类算法而言， 本文算法的聚类结果对于 Ｉｒｉｓ 等数据集的目标函数 值只下低了千分之几，却只需要其 ２５％ ～ ３０％的聚 类时间。 其中，对精度降低最高的 Ｇｌａｓｓ 数据集而 言，目标函数下降了 ４．８％，但是其聚类时间却缩短 了 ９０％以上。 本文算法通过增加广义遗传算法来 加快收敛速度，在减少了每个周期的聚类时间的前 提下也缩短了其聚类周期数。 但是本文算法却不能 第 ４ 期 贾旋，等：一种基于模板缩减的新型粒子群遗传聚类算法 ·５６５·

.566 智能系统学报 第11卷 无限缩减每个聚类周期的时间，即使聚类后期“较 [4]秦全德，李丽，程适，等.交互学习的粒子群优化算法 优”的粒子模板已经大聚类后期“较优”的粒子模板 [J].智能系统学报，2012,7(6)：547-553 已经大部分被压缩并移除只剩下静态模板的静态压 QIN Quande,LILi,CHENG Shi,et al.Interactive learning particle swarm optimization algorithm[J].CAAI transactions 缩模板的集合g,但是每个周期还会产生C个新的 on intelligent systems,2012,7(6):547-553. 包含所有输入模板的粒子。如图1所示，本文算法 [5]SOLAIMAN B F,SHETA A F.Energy optimization in wire- 在后期的迭代周期中，周期执行时间逐渐收敛于一 less sensor networks using a hybrid K-means PSO clustering 个固定值： algorithm[J].Turkish Journal of electrical engineering and 3)比起MP聚类算法，本文算法对于Iis等 computer sciences,2015. 数据集既能缩短聚类时间，也能提高聚类精度。 [6]DASH P,NAYAK M.Multilevel thresholding using PSO 而对于数据Wall following而言虽说本文算法降 clustering[].International journal of computer applica- 低了千分之几的精度，但是却缩短了1/10的聚 tions,2014,97(18):27-32. 类时间。同MP算法相比，本文算法虽然增加了 [7]CHIANG M C,TSAI C W,YANG C S.A time-efficient pattern reduction algorithm for k-means clustering[J].Infor- 广义遗产算法等一系列操作，但是这些操作大多 mation sciences,2011,181(4):716-731. 能与模板缩减法相结合且不会增加太多计算复 [8]TSAI C W,HUANG K W,YANG C S,et al.A fast parti- 杂性，如图1所示，本文算法同MP算法在开始的 cle swarm optimization for clustering[J].Soft computing, 周期执行时间基本相等。所以本文算法能够在 2015,19(2):321-338. 增强聚类精度的基础上提高部分聚类速度。 [9]FILHO T M S,PIMENTEL B A,SOUZA R M C R,et al. 总体来看，本文算法能够在基本不降低聚类算 Hybrid methods for fuzzy clustering based on fuzzy c-means 法精度的前提下，缩短大量的聚类时间。 and improved particle swarm optimization[J].Expert sys- tems with applications,2015,42(17/18):6315-6328. 3结束语 [10]RANA S,JASOLA S,KUMAR R.A boundary restricted 随着规模庞大、结构复杂数据的不断出现，对其 adaptive particle swarm optimization for data clustering[J]. International journal of machine learning and cybernetics, 聚类往往需要耗费大量的时间。但是当今大量文献 2013,4(4):391-400. 研究往往都着眼于提高其准确度，很少针对聚类速 [11]张亮，杨国正.一种变维搜索的量子粒子群优化聚类算 度。本文基于模板缩减的粒子群聚类算法，将其与一 法[J].小型微型计算机系统，2012,33(4)：804-808. 种改进的广义遗传算法充分结合，不仅能够提高种群 ZHANG Liang,YANG Guozheng.A quantum particle 的多样性而且能够对模板缩减过程中必要的信息进 swarm optimization clustering algorithm using variable di- 行存储保护。实验表明，本文算法能够在基本不降低 mensions searching J.Journal of Chinese computer sys- 聚类精度的前提下，显著地缩短聚类时间。但是本文 tems,2012,33(4):804-808. 基本模板缩减的粒子群聚类算法，精度不可避免带有 [12]AHMADYFARD A,MODARES H.Combining PSO and k- 些许的损失，特别是当类数增加时误差会较大。对于 means to enhance data clustering[C]//Proceedings of In- 这一问题，应该是还没有将遗传算法的全部优，点挖掘 ternational Symposium on Telecommunications.Tehran,I- ran,2008:688-691 出来，下一步还有待改进。 作者简介： 参考文献： 贾旋，男，1992年生，硕士研究生， 主要研究方向为人工智能与模式识别。 [1]LI Chaoshun,ZHOU Jianzhong,KOU Pangao,et al.A no- vel chaotic particle swarm optimization based fuzzy cluste- ring algorithm[J].Neurocomputing.2012,83:98-109. [2]BEHESHTI Z,SHAMSUDDIN S M H.CAPSO:Centripetal accelerated particle swarm optimization[J].Information sci- 周治平，男，1962年生，教授，博 ences,2014,258:54-79. 士，主要研究方向为智能检测、自动化 [3]SUN Jun,CHEN Wei,FANG Wei,et al.Gene expression 装置、网络安全等。 data analysis with the clustering method based on an im- proved quantum-behaved particle swarm optimization[J]. Engineering applications of artificial intelligence,2012,25 (2):376-391

无限缩减每个聚类周期的时间，即使聚类后期“较 优”的粒子模板已经大聚类后期“较优”的粒子模板 已经大部分被压缩并移除只剩下静态模板的静态压 缩模板的集合 ｑ － ，但是每个周期还会产生 Ｃ 个新的 包含所有输入模板的粒子。 如图 １ 所示，本文算法 在后期的迭代周期中，周期执行时间逐渐收敛于一 个固定值； ３）比起 ＭＰ 聚类算法，本文算法对于 Ｉｒｉｓ 等 数据集既能缩短聚类时间，也能提高聚类精度。 而对于数据 Ｗａｌｌ ｆｏｌｌｏｗｉｎｇ 而言虽说本文算法降 低了千分之几的精度，但是却缩短了 １ ／ １０ 的聚 类时间。 同 ＭＰ 算法相比，本文算法虽然增加了 广义遗产算法等一系列操作，但是这些操作大多 能与模板缩减法相结合且不会增加太多计算复 杂性，如图 １ 所示，本文算法同 ＭＰ 算法在开始的 周期执行时间基本相等。 所以本文算法能够在 增强聚类精度的基础上提高部分聚类速度。 总体来看，本文算法能够在基本不降低聚类算 法精度的前提下，缩短大量的聚类时间。 ３ 结束语 随着规模庞大、结构复杂数据的不断出现，对其 聚类往往需要耗费大量的时间。 但是当今大量文献 研究往往都着眼于提高其准确度，很少针对聚类速 度。 本文基于模板缩减的粒子群聚类算法，将其与一 种改进的广义遗传算法充分结合，不仅能够提高种群 的多样性而且能够对模板缩减过程中必要的信息进 行存储保护。 实验表明，本文算法能够在基本不降低 聚类精度的前提下，显著地缩短聚类时间。 但是本文 基本模板缩减的粒子群聚类算法，精度不可避免带有 些许的损失，特别是当类数增加时误差会较大。 对于 这一问题，应该是还没有将遗传算法的全部优点挖掘 出来，下一步还有待改进。 参考文献： ［１］ＬＩ Ｃｈａｏｓｈｕｎ， ＺＨＯＵ Ｊｉａｎｚｈｏｎｇ， ＫＯＵ Ｐａｎｇａｏ， ｅｔ ａｌ． Ａ ｎｏ⁃ ｖｅｌ ｃｈａｏｔｉｃ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ｂａｓｅｄ ｆｕｚｚｙ ｃｌｕｓｔｅ⁃ ｒｉｎｇ ａｌｇｏｒｉｔｈｍ［Ｊ］． Ｎｅｕｒｏｃｏｍｐｕｔｉｎｇ， ２０１２， ８３： ９８⁃１０９． ［２］ＢＥＨＥＳＨＴＩ Ｚ， ＳＨＡＭＳＵＤＤＩＮ Ｓ Ｍ Ｈ． ＣＡＰＳＯ： Ｃｅｎｔｒｉｐｅｔａｌ ａｃｃｅｌｅｒａｔｅｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ［Ｊ］． Ｉｎｆｏｒｍａｔｉｏｎ ｓｃｉ⁃ ｅｎｃｅｓ， ２０１４， ２５８： ５４⁃７９． ［３］ＳＵＮ Ｊｕｎ， ＣＨＥＮ Ｗｅｉ， ＦＡＮＧ Ｗｅｉ， ｅｔ ａｌ． Ｇｅｎｅ ｅｘｐｒｅｓｓｉｏｎ ｄａｔａ ａｎａｌｙｓｉｓ ｗｉｔｈ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ａｎ ｉｍ⁃ ｐｒｏｖｅｄ ｑｕａｎｔｕｍ⁃ｂｅｈａｖｅｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ［ Ｊ］． Ｅｎｇｉｎｅｅｒｉｎｇ ａｐｐｌｉｃａｔｉｏｎｓ ｏｆ ａｒｔｉｆｉｃｉａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ， ２０１２， ２５ （２）： ３７６⁃３９１． ［４］秦全德， 李丽， 程适， 等． 交互学习的粒子群优化算法 ［Ｊ］． 智能系统学报， ２０１２， ７（６）： ５４７⁃５５３． ＱＩＮ Ｑｕａｎｄｅ， ＬＩ Ｌｉ， ＣＨＥＮＧ Ｓｈｉ， ｅｔ ａｌ． Ｉｎｔｅｒａｃｔｉｖｅ ｌｅａｒｎｉｎｇ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１２， ７（６）： ５４７⁃５５３． ［５］ＳＯＬＡＩＭＡＮ Ｂ Ｆ， ＳＨＥＴＡ Ａ Ｆ． Ｅｎｅｒｇｙ ｏｐｔｉｍｉｚａｔｉｏｎ ｉｎ ｗｉｒｅ⁃ ｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ｕｓｉｎｇ ａ ｈｙｂｒｉｄ Ｋ⁃ｍｅａｎｓ ＰＳＯ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ［Ｊ］． Ｔｕｒｋｉｓｈ Ｊｏｕｒｎａｌ ｏｆ ｅｌｅｃｔｒｉｃａｌ ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅｓ， ２０１５． ［６］ ＤＡＳＨ Ｐ， ＮＡＹＡＫ Ｍ． Ｍｕｌｔｉｌｅｖｅｌ ｔｈｒｅｓｈｏｌｄｉｎｇ ｕｓｉｎｇ ＰＳＯ ｃｌｕｓｔｅｒｉｎｇ［ Ｊ］． Ｉｎｔｅｒｎａｔｉｏｎａｌ ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒ ａｐｐｌｉｃａ⁃ ｔｉｏｎｓ， ２０１４， ９７（１８）： ２７⁃３２． ［７］ＣＨＩＡＮＧ Ｍ Ｃ， ＴＳＡＩ Ｃ Ｗ， ＹＡＮＧ Ｃ Ｓ． Ａ ｔｉｍｅ⁃ｅｆｆｉｃｉｅｎｔ ｐａｔｔｅｒｎ ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｋ⁃ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ［Ｊ］． Ｉｎｆｏｒ⁃ ｍａｔｉｏｎ ｓｃｉｅｎｃｅｓ， ２０１１， １８１（４）： ７１６⁃７３１． ［８］ＴＳＡＩ Ｃ Ｗ， ＨＵＡＮＧ Ｋ Ｗ， ＹＡＮＧ Ｃ Ｓ， ｅｔ ａｌ． Ａ ｆａｓｔ ｐａｒｔｉ⁃ ｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ｆｏｒ ｃｌｕｓｔｅｒｉｎｇ ［ Ｊ］． Ｓｏｆｔ ｃｏｍｐｕｔｉｎｇ， ２０１５， １９（２）： ３２１⁃３３８． ［９］ＦＩＬＨＯ Ｔ Ｍ Ｓ， ＰＩＭＥＮＴＥＬ Ｂ Ａ， ＳＯＵＺＡ Ｒ Ｍ Ｃ Ｒ， ｅｔ ａｌ． Ｈｙｂｒｉｄ ｍｅｔｈｏｄｓ ｆｏｒ ｆｕｚｚｙ ｃｌｕｓｔｅｒｉｎｇ ｂａｓｅｄ ｏｎ ｆｕｚｚｙ ｃ⁃ｍｅａｎｓ ａｎｄ ｉｍｐｒｏｖｅｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ［ Ｊ］． Ｅｘｐｅｒｔ ｓｙｓ⁃ ｔｅｍｓ ｗｉｔｈ ａｐｐｌｉｃａｔｉｏｎｓ， ２０１５， ４２（１７ ／ １８）： ６３１５⁃６３２８． ［１０］ＲＡＮＡ Ｓ， ＪＡＳＯＬＡ Ｓ， ＫＵＭＡＲ Ｒ． Ａ ｂｏｕｎｄａｒｙ ｒｅｓｔｒｉｃｔｅｄ ａｄａｐｔｉｖｅ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ｆｏｒ ｄａｔａ ｃｌｕｓｔｅｒｉｎｇ［Ｊ］． Ｉｎｔｅｒｎａｔｉｏｎａｌ ｊｏｕｒｎａｌ ｏｆ ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ ａｎｄ ｃｙｂｅｒｎｅｔｉｃｓ， ２０１３， ４（４）： ３９１⁃４００． ［１１］张亮， 杨国正． 一种变维搜索的量子粒子群优化聚类算 法［Ｊ］． 小型微型计算机系统， ２０１２， ３３（４）： ８０４⁃８０８． ＺＨＡＮＧ Ｌｉａｎｇ， ＹＡＮＧ Ｇｕｏｚｈｅｎｇ． Ａ ｑｕａｎｔｕｍ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｕｓｉｎｇ ｖａｒｉａｂｌｅ ｄｉ⁃ ｍｅｎｓｉｏｎｓ ｓｅａｒｃｈｉｎｇ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｈｉｎｅｓｅ ｃｏｍｐｕｔｅｒ ｓｙｓ⁃ ｔｅｍｓ， ２０１２， ３３（４）： ８０４⁃８０８． ［１２］ＡＨＭＡＤＹＦＡＲＤ Ａ， ＭＯＤＡＲＥＳ Ｈ． Ｃｏｍｂｉｎｉｎｇ ＰＳＯ ａｎｄ ｋ⁃ ｍｅａｎｓ ｔｏ ｅｎｈａｎｃｅ ｄａｔａ ｃｌｕｓｔｅｒｉｎｇ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ｉｎ⁃ ｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ． Ｔｅｈｒａｎ， Ｉ⁃ ｒａｎ， ２００８： ６８８⁃６９１． 作者简介： 贾旋，男，１９９２ 年生，硕士研究生， 主要研究方向为人工智能与模式识别。 周治平， 男， １９６２ 年生， 教授， 博 士，主要研究方向为智能检测、自动化 装置、网络安全等。 ·５６６· 智 能 系 统 学 报 第 １１ 卷