一种基于粒子群算法的聚类算法

第35卷第1期2009年3月延边大学学报(自然科学版)

Journal of Yanbian University (Natural Science )Vol.35No.1Mar.2009

收稿日期:2008-10-18

作者简介:姜浩(1981—

),男,硕士研究生,研究方向为粒子群算法.文章编号:100424353(2009)0120064204

一种基于粒子群算法的聚类算法

姜浩,　崔荣一

(延边大学工学院计算机科学与技术系智能信息处理研究室,吉林延吉133002)

摘要:提出一种基于粒子群算法的聚类算法,该算法利用粒子群算法随机搜索解空间的能力找到最优解.首先,将样本所属类号的组合作为粒子,构成种群,同时引入极小化误差平方和来指导种群进化的方向.其次,通过对全局极值的调整,搜索到全局最优值.最后,通过仿真实验的对比,验证了该算法在有效性和稳定性上要好于K 2means 算法.

关键词:粒子群;聚类;极小化误差平方和中图分类号:TP301.6 文献标识码:A

A Method of Clustering

B ased on

the P article Sw arm Optimization

J IAN G Hao ,　CU I Rong 2yi

(I ntelli gent I nf ormation Processing L ab.,De partment of Com puter Science and Technolog y ,

College of Engineering ,Yanbian Universit y ,Yanj i 133002,China )

Abstract :A clustering method based on the particle swarm optimization is provided ,using the ability of PSO algorithm which can search all of the solution space to find the optimum solution.Firstly ,the combination of the cluster number of the samples was taken as particles to consist a swarm.Meanwhile ,the evolution trend was used to modulate with the theory of the L MS error criterion.Secondly ,according to the modulating for global best ,the algorithm researched the global optimum.Finally ,the simulation results show that the new algorithm of proposed algorithm is more efficient and stable than K 2means algorithm.K ey w ords :particle swarm optimization ;clustering ;L MS error criterion

0　引言

聚类分析研究具有很长的历史,其重要性及

与其他研究方向的交叉特性得到人们的肯定[1].聚类是数据挖掘、模式识别等研究方向的重要研究内容之一,在识别数据的内在结构方面具有极其重要的作用.聚类技术广泛应用于语音识别、字符识别、图像分割、机器视觉、数据压缩和文献信息检索等领域.聚类的另一主要应用是数据挖据(多关系数据挖掘)、时空数据库应用(GIS 等)、序列和一类数据分析等.此外,聚类还应用于统计科学.值得一提的是,聚类分析对生物学、心理学、考

古学、地质学、地理学以及市场营销等研究也都有重要应用.

粒子群优化(Particle Swarm Optimization ,PSO )算法是由Eberhart 和Kennedy [2]于1995年提出的一类基于群智能的随机优化算法.该算法模拟鸟群飞行觅食的行为,通过个体之间的集体协作和竞争来实现全局搜索,是一种基于群智能的演化计算技术.同遗传算法相比,虽然同是基于迭代的进化算法,但没有交叉和变异算子,群体在解空间中根据自身经历的最好位置,以及群体最优解来进行搜索.由于PSO 算法有着参数少,

　第1期姜浩,等:一种基于粒子群算法的聚类算法

易于实现,算法简单,具有良好的全局搜索能力等优点,被广泛应用于各个领域,如结构设计、函数优化、网络训练、模糊系统控制、电磁场以及任务调度等工程优化问题中.

目前为止,已有很多结合粒子群算法的聚类分析方法[325],其关键结合点是如何构造种群以及如何评价.比较有代表性的思想是结合K2means 算法,将初始的聚类中心作为种群,然后根据中心进行聚类,再利用聚类的结果来评价种群的质量,最后依据粒子群算法的原理更新聚类中心.这种算法改进了K2means算法对初始中心敏感的问题.在文献[4]中提出了动态的聚类方法,以解决分类数目不确定的聚类问题.

本文提出的算法与上述结合K2means算法的粒子群聚类不同,采用的方法是随机地分配每个样本的类号,将这些类号的组合作为一个粒子,再利用粒子群算法进行优化.所提出的算法实现简单,实验结果正确,稳定性良好.

1　基本PSO算法

基本PSO[6]中,粒子群由n个粒子组成,每个粒子的位置代表优化问题在d维搜索空间中潜在的解.在一个d维的目标搜索空间中,由这n个粒子组成一个群落,其中第i个粒子的位置为d维的向量X i=(X i1,X i2,…,X i d);第i个粒子的历史最优位置为P i=(P i1,P i2,…,P i d);整个群体迄今为止搜索到的最好的位置记为P g=(P g1,P g2,…,P g d);第i个粒子的“飞翔”速度也是一个d维的向量V i=(V i1,V i2,…,V i d),它决定粒子在搜索空间单位迭代次数的位移.粒子按式(1)和(2)来调整自己的位置:

V ij(t+1)=w V ij(t)+r1c1(P ij-

　X ij(t))+r2c2(P g-X ij(t)),(1)

X ij(t+1)=X ij(t)+V ij(t+1),

　1≤i≤n,1≤j≤d.(2)其中c1和c2是非负数,称为加速度因子,通常取c1=c2=2;r1和r2为[0,1]内的随机数;w为惯性因子,一般在0.1到0.9之间取值.此外,粒子速度V i由最大速度V max所限制,即V i在[-V max, V max]内取值.

PSO的基本算法步骤描述如下:

Step1　初始化粒子群,即随机设定各粒子的初始位置和初始速度;

Step2　计算每个粒子的适应值;

Step3　对每个粒子,比较它的适应值和它经历过的最好位置的适应值;若更好,更新粒子当前最好位置P i d;

Step4　对每个粒子的P i d进行比较,最好的位置如果优于P g d,则更新P g d的值为P i d;

Step5　根据式(1)和式(2)更新粒子速度和位置;

Step6　如果达到结束条件(一般为足够好的位置或最大迭代次数),则结束,否则转Step2.

算法中的w,c1和c2是影响算法性能的重要参数.w值较大时,算法的全局搜索能力强;反之,局部搜索能力强.c1的值决定了粒子更新时受自身影响的程度,c2的值决定了整个种群对个体粒子的影响程度.

2　聚类

聚类是一个无监督的分类,它没有任何先验知识可用.聚类遵从的一般原则是:一个类簇内的实体是相似的,不同类簇的实体是不相似的;一个类簇是测试空间中点的会聚;同一类簇的任意两个点间的距离小于不同类簇的任意两个点间的距离;类簇可描述为一个包含密度相对高的点集的多维空间中的连通区域,它们借助包含密度相对较低的点集的区域与其他区域(类簇)相分离.

聚类的形式描述如下:令U={P1,P2,…, P n}表示一个模式集合,P i表示第i个模式,i= {1,2,…,n};C tΑU,t=1,2,…,k,C t={P t1, P t2,…,P t w};proximity(P ms,P i r).其中,第1个下标表示模式所属的类,第2个下标表示某类中某一模式,函数proximity用来刻画模式的相似性距离.若诸类C t为聚类的结果,则诸C t需满足如下条件:

∪k t=1C t=U,(3)对于ΠC m,C rΑU,C m≠C r,有C m∩C r= (仅限于刚性聚类);

min(p roximity(P m u,P rv))>

　max(pro ximity(P m x,P m y)),(4)式(4)中参数满足如下条件:ΠP mu∈C m,ΠP rv∈C r,ΠC m,C rΑU并且C m≠C r;ΠP m x,P m y∈C m,ΠC mΑU.

典型的聚类过程主要包括数据(或称之为样本或模式)准备,特征选择和特征提取,接近度计算,聚类(或分组),对聚类结果进行有效性评估等步骤.

56