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