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