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