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