132 2009，45（33） Computer Engineering and Applications 计算机工程与应用 基于该粒子群算法的聚类算法 孙 洋，罗 可 SUN Yang，LUO Ke 长沙理工大学 计算机与通信工程学院，长沙 410076 Institute of Computer and Communication Engineering，Changsha University of Sciences and Technology，Changsha 410076，China E-mail：yangyang.sun@yahoo.com.cn SUN Yang，LUO Ke.Clustering method based on improved particle swarm optimization .Computer Engineering and Applications，2009，45（33）：132-134. Abstract：This paper proposes a clustering algorithm which is based on improved Particle Swarm Optimization（PSO）.Both the K -means，which has strong capacity of local searching，and the cross，mutation operation，which are based on the genetic algo－ rithm，are combined in the PSO algorithm.It not only improves the PSO’s local searching capacity，accelerates the convergence rate，and effectively prevents the premature convergence，for this clustering algorithm has a better convergence. Key words：cluster analysis；particle swarm optimization algorithm；K-means；genetic algorithm it adds cross and mutation operations.Experiments show that 摘 要：提出了一种基于改进的粒子群算法的聚类方法。该算法是将局部搜索能力强的 K-均值算法和基于遗传算法的交叉、变异 操作同时结合到粒子群算法中。既提高了粒子群算法的局部搜索能力、加快了收敛速度，同时因为加入了交叉、变异操作，有效地 防治了早熟收敛现象的发生。实验表明该聚类算法有更好的收敛效果。 关键词：聚类分析；粒子群算法；K-均值算法；遗传算法 DOI：10.3778/j.issn.1002-8331.2009.33.043 文章编号：1002－8331（2009）33-0132-03 文献标识码：A 中图分类号：TP18 1 引言 聚类分析作为一种无导师的学习方法，能够从研究对象的 特征数据中发掘出关联规则，因而是一种强有力的信息处理方 法。它在图像分割、模式识别、特征提取和信号压缩中都有着广 泛的应用[1]。 在已有的聚类算法中，K-均值聚类算法简单、收敛速度 快，且局部搜索能力强，但是对初始条件较为敏感，对不同的初 始值有不同的聚类结果。基于遗传算法（GA）的聚类方法能够 解决 K-均值算法对初值敏感的问题，并有更多的机会获得全 局最优解，但用 GA 仍会出现未成熟收敛现象，仍不能保证每 次运行都得到全局最优解[2]。 粒 子 群 优 化 算 法（Particle Swarm Optimization ，PSO）是 1995 年由 Kennedy 和 Eberhart 在鸟群、鱼群和人类社会的行 为规律的启发下提出的一种基于群智能的演化计算技术[3]。由 于算法收敛速度快，需要设置、调整的参数少，实现简洁，近年 来受到学术界的广泛重视。现在，PSO 算法在函数优化、神经网 络训练、模糊系统控制以及其他工程领域都得到了广泛应用[4]。 但是 PSO 算法也有缺点，其最主要的问题是它容易产生 早熟收敛、局部寻优能力较差等[5]。纵观目前各种与 PSO 算法 相关的混合算法，大多数基本上采用一种策略对其改进，要么 与其他算法结合，要么加入变异操作，同时采用两种策略的混 合算法较少[5]。 因此，提出了一种新的改进策略：将局部搜索能力强的 K- 均值算法和基于遗传算法的交叉、变异操作同时结合到 PSO 算法中。通过适当调节，发挥各自的优点，既提高了 PSO 算法 的局部搜索能力，又因为加入了交叉、变异操作增加了种群的 多样性，防止了算法早熟。通过与文献[6]中提出的方法对比，这 种改进的粒子群聚类算法的收敛效果更好一些。 2 K-均值聚类算法 ，x2 个点 x1 ，…，xN 事先给定）集合 G1 ，满足： Rn 空间中的聚类问题可以描述为对于给定的 Rn 中的 N ，按照它们之间的相似性将其划分为 K 个（K ，G2 ，…，Gk （1）Gi≠Φ，i=1，2，…，K； （2）Gi∩Gj=Φ，i，j=1，2，…，K；i≠j； （3）∪ K-均值聚类算法步骤如下[7]： （1）任选 K 个初始聚类中心 c1 （2）将样本集{X}中各个样本按最小距离原则分配给 K 个 ，…，xN}。 Gi={x1 ，c2 ，…，ck ； k i=1 ，x2 基金项目：国家自然科学基金（the National Natural Science Foundation of China under Grant No.60474070，No.10471036）；湖南省科技计划项目 （No.05FJ3074）；湖南省教育厅重点项目（No.07A001）。 作者简介：孙洋（1984-），女，硕士，主要研究方向为数据库技术、数据挖掘；罗可（1961-），男，博士，教授，研究方向为数据挖掘，计算机应用等。 收稿日期：2008-07-02 修回日期：2008-09-25 

孙 洋，罗 可：基于该粒子群算法的聚类算法 2009，45（33） 133 聚类中心的某个 ci ； （3）计算新聚类中心 ci′（i=1，2，…，k），即 ci′= 1 Ni Σ X，其 X∈Si 中 Ni 为第 i 个聚类域 Si （4）若 ci′≠ci 包含的个数； （i=1，2，…，k），转步骤（2）；否则算法收敛，计 算结束。 3 基本粒子群算法 PSO 以模拟鸟的群体智能为特征，以求解连续变量优化问 题为背景。在 PSO 中，每只鸟被称之为一个粒子，每个粒子用 其几何位置和速度向量表示，在问题求解中，每个粒子参考自 己既定方向、所经历的最优方向和整个鸟群的最优方向确定自 己的飞行[8]。 现在一般采用下面公式对每个粒子进行操作： ）+c2 ） xk+1=xk+vk+1 vk+1=wvk+c1 （gbest-xk （pbest-xk （1） （2） 是粒子当前位置。pbest 是粒子本 其中 vk 身所找到的最好解的位置，gbest 是整个种群目前找到的最优 解的位置。其他参数的介绍见第 4 部分。 是粒子的速度向量，xk 4 参数设定 PSO 算法中需要调节的参数主要包括：惯性权重系数 w、 以及种群规模 m，在该文算法 和 c2、最大速度 vmax 学习因子 c1 中还加入了最大位置 xmax。 4.1 惯性权重系数 惯性权重系数 w 用来控制前面的速度对当前速度的影 响，较大的 w 可以加强 PSO 的全局搜索能力，而较小的能加强 局部搜索能力。目前普遍采用将 w 设置为从 0.9 到 0.1 线性 下降的方法[9]，这种方法可使得 PSO 在开始时探索较大的区 域，较快地定位最优解的大致位置，随着 w 逐渐减小，粒子速 度减慢，开始精细地局部搜索。 4.2 学习因子 和 c2 学习因子（也称加速度系数）c1 分别调节粒子向全局 最优粒子和个体最优粒子方向飞行的最大步长。若太小，则粒 子可能远离目标区域；若太大则可能导致粒子忽然向目标区域 飞去或飞过目标区域[10]。合适的 c1 可以加快收敛且不易 陷入局部最优，目前大多数文献均采用 c1=c2=2。但文献[11]分 析指出，令 c1=1.5，c2=2.5 能使算法具有更好的收敛性能。 4.3 最大速度 最大速度 vmax 的引入实际上是对粒子的全局搜索能力和 和 c2 越大，则粒子的飞行速度越高， 局部搜索能力的一种平衡。vmax 从而可以对整个空间进行有效的搜索；vmax 越小，则粒子的飞行 速度越低，从而可以对局部区域进行更加有效的搜索，确保获 得较高的搜索精度。一般来说，对于基本 PSO 算法，若将搜索 空间第 d 维的变化范围定义为[-xdmax （d= 1，2，…，D），并且在 k∈[0.1，0.2][10]的范围内能够获得较好的性能。 4.4 种群规模 ，xdmax]，令 vdmax=k×xdmax PSO 算法种群规模较小，一般令 m=20～40。其实对于大部 分问题 10 个粒子就能取得很好结果，但对于较难或者特定类 别的问题，粒子数可能取到 100 或 200。 4.5 最大位置 最大位置 xmax 的引入是为了防止在迭代后期，粒子位置超 过取值区间。经实验得出，xmax=q×xmax [0.5，0.9]的范围内能够获得较好的性能。 （d=1，2，…，D），并且在 q∈ 5 改进的粒子群聚类算法 5.1 编码和适应度函数 算法中的个体采用基于聚类中心的浮点数编码方式，每个 粒子由 K 个聚类中心组成，它可表示为长度为 K×l 的浮点码 串。个体的适应度函数定义为： 1 f= 1+Jm 为各样本到各自聚类中心的欧式距离的和。 其中，Jm 5.2 基于遗传算法的交叉、变异操作 （3） 首先，采用基于轮盘赌选择策略选择适应度较高、与种群 规模一样大小的个体进行交叉、变异，然后将完成上述操作的 部分粒子按目标值的大小重新插入到原种群中，取代原种群中 目标值较大的个体。 具体的交叉、变异操作采用由菲尔德大学开发的遗传算法 工具箱中提供的离散重组的交叉方法和实种群变异方法。 5.3 解聚类问题的基本粒子群算法 步骤 1 设定粒子数 m，规定迭代次数 Max_DT，随机产生 m 个初始解 X0 ； 步骤 2 根据当前位置，以式（3）计算适应值 f。设置当前适 应值为个体极值 plbest，当前位置为个体极值位置 pxbest，根据 各个粒子的个体极值 plbest，找出全局极值 glbest 和全局极值 位置 gxbest； While（迭代次数<规定迭代次数）do For i=1：m 步骤 3 按式（1），更新自己的速度，并把它限制在 vmax 步骤 4 按式（2），更新当前的位置； 步骤 5 根据当前位置，各个样本按最小距离原则分配给 内； K 个聚类中心； 步骤 6 按式（3）计算适应度 f； 步骤 7 更新 plbest，pxbest； End； 步骤 8 根据各个粒子的个体极值 plbest，找出全局极值 glbest 和全局极值位置 gxbest； ； 步骤 9 X0=X1 End； 步骤 10 最后输出全局极值 glbest 和全局极值位 gxbest。 5.4 算法改进思路 算法是在文献[6]的基础上作的改进。首先在第（4）步，更新 位置时将其限制在 xmax 内，其他的改进如下： 改进方法 1：先用 K-均值算法作一快速分类，其结果作为 其中一个粒子结果，并在第（8）步后面对粒子进行交叉、变异操 作，其他步骤同上，此方法称为 Kmean+PSO+GA。 改进方法 2：采用 K-均值算法的思想，在第（5）步后面，在 新的分类基础上重新计算新的聚类中心，如果重新计算得到的 聚类中心的适应度比原来的差，则舍弃，否则更新为当前的位 置，且在第（8）步后面对粒子进行交叉、变异操作，此方法称为 PSO+Kmean+GA。 改进方法 3：综合改进方法 1 和方法 2，此方法称为Kmean+ PSO+Kmean+GA。 

134 2009，45（33） 6 仿真实验 Computer Engineering and Applications 计算机工程与应用 软件环境：操作系统 Windows XP，编译软件 Matlab7.0.1； 硬件环境：CPU AMD Sempron（2200+）1.5 GHz，内存 1 GB。在 以上条件下分别对 K-均值算法、GA 算法、POS 算法、Kmean+ POS 算法、POS+Kmean 算法、Kmean+POS+Kmean 算法、POS+ GA 算法、Kmean+POS+GA 算法、POS+Kmean+GA 算法、Kmean+ POS+K+GA 算法进行仿真实验。 实验参数设置如下：交叉概率 Pc=0.68，变异概率 Pm= 0.001，种群规模为 m=30，迭代次数 Max_DT=50，c1=1.5，c2=2.5， w=0.8（1+t）×0.2/Max_DT（t 为当前迭代次数），k=0.14，q=0.85。 实验采用 Fisher 的 Iris 植物样本数据，该数据集由分别属于三 种植物的 150 个样本组成，每个样本均为 4 维模式向量，代表 植物的 4 种特征数据。每种算法作了 20 次实验，结果见表 1。 表 1 对 Iris 植物样本数据聚类的实验结果 算法 平均值 最好解 最差解 最好解次数 K-均值算法 GA 算法 97.325 9 97.336 05 97.346 2 97.235 5 97.934 48 99.075 2 POS 97.295 0 97.475 03 97.519 7 POS+GA 97.309 8 97.446 29 97.516 7 Kmean+POS 97.325 9 97.355 81 97.634 4 Kmean+POS+GA 97.190 1 97.326 43 97.346 2 POS+Kmean 97.041 6 97.082 94 97.123 3 POS+Kmean+GA 97.040 6 97.075 52 97.116 5 Kmean+POS+Kmean 97.041 6 97.087 66 97.123 3 Kmean+POS+Kmean+GA 96.946 1 97.073 65 97.101 3 10 1 1 1 12 1 2 1 1 1 7 结论 提出了一种基于改进的 PSO 算法的新聚类算法。该算法 一方面结合了 K-均值，使得该算法具有局部搜索能力强，运算 量小的特点，从而能加快算法的局部寻优速度；另一方面，加入 了基于遗传算法中的交叉、变异操作，保证了种群的多样性，克 服了 PSO 未成熟收敛的现象。因此，算法具有较快的收敛速度 和较高的收敛精度。实验结果也表明，算法能够有效地收敛于 全局最优解。 参考文献： [1] 高坚.基于 C-均值和免疫遗传算法的聚类[J].计算机工程，2003，29 （12）：65-66. [2] 张雷，李仁厚.人工免疫 C-均值聚类算法[J].西安交通大学学报， 2005，39（8）：836-839. [3] Kennedy J，Eberhart R C，Shi Y.Swarm intelligence[M].SanFrancis－ co：Morgan Kaufman Publisher，2001. [4] 刘向东，沙秋夫，刘勇奎，等.基于粒子群算法的聚类分析[J].计算机 工程，2006，32（6）：201-202. [5] 海风吹. 蚁群算法，PSO 算法以及两种算法可以融合的几种方法 [DB/OL].（2008 -5 -20）.http：//www.cnblogs.com/hetonghai/archive/ 2008/04/09/1144145.html. [6] 高尚，杨静宇.一种新的基于粒子群算法的聚类方法[J].南京航空航 天大学学报，2006，38（6）：62-64. [7] Han Jia-wei，Kamber M.数据挖掘：概念与技术[M].范明，译.北京： 机械工业出版社，2007：263-264. [8] 高岳林，任子晖.带有变异算子的自适应粒子群优化算法[J].计算机 工程与应用，2007，43（25）：43-47. [9] 吕振肃，侯志荣.自适应变异的粒子群优化算法[J].电子学报，2004，32 （3）：416-420. [10] 寇保华，杨涛，张晓今，等.基于交叉变异的混合粒子群优化算法[J]. 计算机工程与应用，2007，43（17）：85-88. [11] Eberhart R C，Shi Yu -hui.Particle swarm optimization：Develop － ments，applications and resources [ C ] / / Proceedings of the IEEE Congress on Evolutionary Computation.Piscataway，NJ：IEEE Ser－ vice Center，2001：81-86. （上接 127 页） vation 而言，0.002 5 是一个很大的阀值，这与支持度或效用阀 值的取值范围差别很大。图 1 显示了事务的变化对算法性能的 影响。由于 HM-Two-Phase-Miner 需要多次扫描数据库，并可 能使候选集增加，当事务增长时，HM-Two-Phase-Miner 需要运 行更长的时间。在图 2 中，minmotivation 从 0.000 004 变化到 0.002 5（minsup 与 minutil 从 0.002 变化到 0.05）。minmotivation 越大，满足条件的项目越少，运行的时间越短。 6 结论 分析了支持度与效用在度量项集重要性方面的不足，提出 一种新的兴趣度量方法：激励。激励综合了支持度与效用的优 点，能同时反映项集的语义特性与统计特性，符合人们的决策 习惯。还证明了事务权重激励向下封闭特性的存在，并在新的 算法 HM-Two-Phase-Miner 中利用此特性进行减枝。实验证 明，算法 HM-Two-Phase-Miner 对短模式数据集性能较好。 参考文献： [1] Agrawal R，Srikant R.Fast algorithms for mining association rules[C]// Proc of 1994 Int’1 Conf of Very Large Data Base.Santiago，Chili： VLDB Endowment，1994：487-499. [2] Lu S F，Hu H P，Li F.Mining weighted association rules[J].Intelli－ gent Data Analysis，2001，5：211-225. [3] Shen Y D，Zhang Z，Yang Q.Objective-oriented utility-based asso－ ciation mining[C]//Proceedings of the 2002 IEEE International Con－ ference on Data Mining，2002：426-433. [4] Bayardo R J，Agrawal J R，Gunopulos D.Constraint -based rule mining in large，dense databases[J].Data Mining and Knowledge Dis－ covery，2000，4（2/3）：217-240. [5] Yao H，Hamilton H J.Mining itemset utilities from transaction databases[J].Data & Knowledge Engineering，2006，59：603-626. [6] Liu Y，Liao W K，Choudhary.A fast high utility itemsets mining al－ gorithm[C]//Proceedings of the 1st International Workshop on Utiliy- based Data Mining，2005：90-99. [7] 余光柱，邵世煌，易先军，等.一种基于划分的高效用长项集的挖掘 算法[J].计算机工程与应用，2007，43（29）：11-13. [8] Geng Li -qiang，Hamilton H J.Interestingness measures for data mining：A survey[J].ACM Computing Surveys（CSUR），2006，38（3）： 61-93. [9] Vroom V H.Work and motivation[M].New York：John Wiley，1964. [10] Wang Jing，Liu Ying，Zhou Lin，et al.Pushing frequency constraint to utility mining model[C]//Lecture Notes in Computer Science 4489： Proceedings of International Conference on Computational Science （ICCS），2007：685-692.