基于QPSO的数据聚类

基于QPSO的数据聚类

龙海侠,须文波,孙　俊

(江南大学信息工程学院,江苏无锡214122)

3

摘　要:在K2Means聚类、PSO聚类、K2Means和PSO混合聚类(KPSO)的基础上,研究了基于量子行为的微粒群优化算法(QPSO)的数据聚类方法,并提出利用K2Means聚类的结果重新初始化粒子群,结合QPSO的聚类算法,即KQPSO。介绍了如何利用上述算法找到用户指定的聚类个数的聚类中心。聚类过程都是根据数据之间的Euclidean(欧几里得)距离。K2Means算法、PSO算法和QPSO算法的不同在于聚类中心向量的“进化”上。最后使用三个数据集比较了上面提到的五种聚类方法的性能,结果显示基于QPSO算法的数据聚类性能比一般

PSO算法更好。

关键词:聚类;K2Means;PSO;QPSO;聚类中心

中图法分类号:TP391　　　文献标识码:A　　　文章编号:100123695(2006)1220040203DataClusteringBasedonQuantum2behavedParticleSwarmOptimization

LONGHai2xia,XUWen2bo,SUNJun

(CollegeofInformationTechnology,SouthernYangtzeUniversity,WuxiJiangsu214122,China)

Abstract:ThispaperinvestigatesQuantum2behavedParticleSwarmOptimization(QPSO)algorithmtoclusterdatabasedon

theK2Meansclustering,PSOclusteringandKPSOclustering.AfterthatweintroduceusingK2Meansclusteringtoseedtheinitialswarm,combingwithQPSOtoclusterdata,namelyKQPSOandintroducehowthesealgorithmscanbeusedtofindthecentroidsofauserspecifiednumberofclusters.AlltheprocessofclusteringbasedontheEuclideandistanceamongdatavec2tors.ThedifferencesbetweenK2Means,PSO,QPSOistheevolutionofthecluster2centroids.Finally,wecomparetheperfor2manceofthefiveclusteringmethodonthreedatasets.TheexperimentsresultshowQPSOclusteringsuperiority.Keywords:Clustering;K2Means;PSO;QPSO(Quantum2behavedParticleSwarmOptimization);Cluster2centroids

　　聚类(Clustering)是一个将数据集划分为若干组(Class)或类(Cluster)的过程,并使得同一组内的数据对象具有较高的相似度,而不同组中的数据对象是不相似的。相似或不相似的描述是基于数据描述属性的取值来确定,通常是利用(各对象间)距离来进行表示的。许多领域,包括数据分析、数据挖掘、图形分割、统计学、机器学习等均使用了聚类算法。聚类技术已经成功地解决了机器学习和数据挖掘算法的可量测性问题。

聚类算法可以分成两类,即有监督的和无监督的。对于有监督的聚类,学习算法有一个外界的教师信号,对数据向量属于哪个类提供类别标记;对于无监督的聚类,不存在一个外界的教师信号,而是根据各对象间的距离进行分组。本文集中讨论的是无监督的聚类。

目前已有的许多无监督聚类算法中,大多数算法在聚类中不依赖输入空间的布局,这些算法包括K2Means,ISODATA,LVQ;另一方面,自组织映射(SOM)要求输入空间的布局结构。虽然聚类算法通常分为有监督的和无监督的,但是已经开发了具有更好性能的混合聚类算法,如LVQ2Ⅱ,它综合了有监督学习和无监督学习。

最近,图形聚类和数据向量的聚类均使用了粒子群优化算法(ParticleSwarmOptimization,PSO)。本文提出了一种新的能收稿日期:2005209227;修返日期:2005211224基金项目:国家自然科学基金资助项目(60474030)

保证全局收敛的粒子群算法,即量子粒子群算法(Quantum2be2

[1,2]

havedParticleSwarmOptimization,QPSO)。实验证明,QPSO的性能优于PSO算法。本文的目的是研究QPSO算法在数据聚类中的应用,研究内容包括:①使用QPSO聚类任意的数据;②结合K2Means和QPSO算法聚类任意的数据。

1　K2Means聚类

聚类算法中一个最重要的元素是相似性的度量,K2Means聚类利用欧几里得(Euclidean)距离来描述相似性。一个类中数据向量之间的Euclidean距离很小,并且数据向量与该类中心向量的Euclidean距离也很小。中心向量代表了聚类的中点。以下是一些符号的定义:

(1)Nd代表输入的维数,也就是每一个数据向量的维数。

(2)Nc代表聚类中心的数目(由用户提供),也就是要形

成的聚类数目。

(3)zp代表第p个数据向量。(4)mj代表聚类j的中心向量。

(5)nj代表聚类j中数据向量的数目。(6)Cj代表形成聚类j的数据向量的集合。

使用上面的符号,标准的K2Means算法流程如下:输入　聚类个数Nc、数据向量

输出　每次迭代后的适应性值Je(即每次迭代后的量化误差)

第12期龙海侠等:基于QPSO的数据聚类　　　・41・

(1)初始化Nc个聚类中心向量(初始化要参照数据向量

经验,是局部最优位置;③gbest(t)是社会部分,表示微粒间的社会信息共享,是全局最优位置。下面实验用到的w=0172,

c1=c2=1149。

的范围)。

(2)迭代。

①聚类的过程:对于每一个数据向量,计算它与每个聚类中心的距离(每个聚类中心代表一个类),将这个数据向量分配到距离最小的中心向量中。数据向量到中心向量的距离为

d(zp,mj)=

Ndk=1

粒子i的自身最好位置为

pbesti(t+1)=pbesti(t)　　iff(xi(t+1))≥f(pbesti(t))

xi(t+1)　　iff(xi(t+1))(6)

∑(zpk-mjk)2

(1)

212　PSO聚类

这里下标k代表维数。

②使用式(2)重新计算聚类中心向量:

mj=

在PSO聚类问题中,一个粒子代表Nc个聚类中心向量,即每个粒子的构造为

(2)

xi=(mi1,…,mij,…,miNc)

(7)

1nj

Πzp∈cjp

∑z

其中,mij代表聚类Cij中第i个粒子的第j个聚类中心向量。因此,一个群代表要聚类的数据集的多个候选聚类。粒子的适应性值用下面的量子化误差来度量:

③使用式(3)计算适应值函数Je:

NC

Je=

j=1

∑[∑d(zp,mj)/|Cj|]

Πz∈Cj

pNc

(3)

Je=Nc

j=1∑[∑d(zp,mij)/|Cij|]Πzp∈Cij

直到满足算法结束的条件。

当满足下列条件之一时,K2Means聚类过程结束:

(1)超过迭代的最大次数(迭代的最大次数由用户指定)。(2)经过多次迭代之后,中心向量的变化很小。(3)经过多次迭代之后,聚类中的数据向量不再变化。

Nc(8)

其中,d在式(1)中已被定义,|Cij|表示属于聚类Cij的数据向量的数目。

PSO聚类算法的流程如下:

在实现算法时,本文选择的是迭代结束条件(1)。

输入　聚类的个数Nc、数据集、粒子的个数

输出　每次迭代后粒子的最佳适应性值Je

(1)初始化每一个粒子的位置和速度,每一个粒子中均包含Nc个聚类中心向量(初始化值要参照数据向量的范围)。

(2)初始化粒子群的局部最优位置和全局最优位置。

(3)Fort=1totmaxdo(这里的tmax代表迭代的最大次数)

2　微粒群优化算法聚类

211　PSO算法

PSO算法是在1995年由美国社会心理学家JamesKenne2dy和电气工程师RussellEberhart共同提出,其基本思想是受

①for每一个粒子xido

for对每一个数据向量zpdo

他们早期对鸟类群体行为研究结果的启发,并利用了生物学家

FrankHeppner的生物群体模型。微粒群优化算法与其他算法

计算数据向量zp和粒子xi中所包含的每一个中心向量的

Euclidean距离d(zp,mi,j)

相类似,也采用群体和进化的概念,同样也是依据个体(微粒)的适应值大小进行操作。所不同的是,微粒群优化算法不像其他进化算法那样对于个体使用进化算子,而是将每个个体看作是Nd维搜索空间中的一个没有重量和体积的微粒,并在搜索空间中以一定的速度飞行。该飞行速度由个体的飞行经验和群体的飞行经验动态调整。每个粒子代表Nd维空间中的一个位置,朝着下面两个方向调整粒子的位置:至今发现的每个粒子的最优位置;粒子群的最优位置。

每一个粒子i包含下列信息:

(1)xi=(xi1,xi2,…,xid)代表粒子的当前位置;

(2)vi=(vi1,vi2,…,vid)代表粒子的当前速度;

(3)Pi=(Pi1,Pi2,…,Pid)代表粒子i的最佳适应性值,即pbest;

(4)Pg=(Pg1,Pg2,…,Pgd)代表粒子群的最佳适应性值,

聚类:将数据向量分配到类Cij

d(zp,mi,j)=minΠc=1,…,Nc{d(zp,mic)}

end

利用式(8)计算粒子的适应性值。

End

②更新粒子的局部和全局最优位置。③利用式(4)和式(5)更新聚类中心,直到满足循环终止的条件。

213　PSO和K2Means混合聚类———KPSO

K2Means算法比PSO算法收敛速度要快,但是K2Means算

法聚类不够精确,为了提高PSO算法的性能,要重新利用K2

Means算法的结果初始化群。这种混合聚类KPSO的过程为:

(1)执行K2Means聚类算法一次,使K2Means算法返回的

即gbest。

利用上面的符号,按照下面两个公式调整每个粒子的位置:

vi,k

(t+1)=wvi,k(t)+c1r1,k(t)(pbesti,k(t)-xi,k(t))+c2r2,k(t)

(4)(5)

(gbest(t)-xi,k(t))

xi(t+1)=xi(t)+vi(t+1)

结果为Nc个聚类中心向量;将这Nc个聚类中心向量作为粒子群中的一个粒子,粒子群中其余的粒子根据数据向量的范围随机初始化。

(2)执行PSO聚类算法的流程。

其中,w是惯性权重,c1和c2是加速常数,r1,j(t),r2,j(t)～

U(0,1),并且k=1,…,Nd。

3　基于量子行为的微粒群优化算法聚类

311　QPSO聚类

PSO是基于种群的进化搜索技术,性能优于其他遗传算

速度的计算以下面三个基值为基础:①vi,k(t)为微粒先前的速度;②gbestj,k(t)为认知部分,因为它仅考虑了微粒自身的

・42・计算机应用研究2006年

法。但是所有已开发的PSO算法均不能保证算法的全局收敛,因为PSO的进化方程式使所有粒子在一个有限的样本空间中搜索。本文提出的QPSO[1,2]算法不仅参数个数少,并且在搜索能力上也优于所有已开发的PSO算法。

在QPSO中,粒子群按照下面的三个公式进行移动:

mbest=

1M

i=1M

(2)Wine。它含有178个数据向量,分成三类,每个数据

向量有13个属性。

(3)Breast2cancer。WisconsinBreastCancer数据库含有

663个数据向量,分成两类,每个数据向量有九个输入。

每种算法的迭代次数为1000,运行30次得到表1中的置

(9)(10)

∑Pi=

1M

i=1

∑Pi1,…,

M

1M

Pid

信区间。

表1　K2Means,PSO,KPS0,QPSO,KQPSO聚类算法的比较

数据集

算法

K2MeansPSOKPSOQPSOKQPSO

K2MeansPSOKPSOQPSOKQPSOQuantizationErrorIntra2clusterDistanceInter2clusterDistance0.0.0.0.0.1.1.1.1.1.2.2.1.1.1.6507456336315294213451790450840146539678632

2675542958535

pid=φ×Pid+(1-φ)×Pgd,φ=rand

α×|mbestd-xid|×ln(xid=pid±

1u

),u=rand(11)

Iris

其中,mbest是粒子群pbest的中间位置;pid为Pid和Pgd之间的随机点;α为QPSO的收缩扩张系数,它是QPSO收敛的一个重要参数,一般可取α=(110-015)×(MAXITER-T)/MAXI2

TER+015可以达到比较好的效果,MAXITER是迭代的最大次

±0.±0.±0.±0.±0.±0.±0.±0.±0.±0.±0.±0.±0.±0.±0.

122

056133112152135052158098184063156114125184

3036343217636

3.3.3.3.3.4.4.4.4.4.6.7.6.6.6.

39253012453853858562593512384143325042216

158334173771058

±0.±0.±0.±0.±0.±0.±0.±0.±0.±0.±0.±0.±0.±0.±0.

2

195201195241256321412458514335356386387394

74326541046

0.0.0.0.0.1.2.2.2.2.1.3.3.3.3.

912585690187913486961591371775263514512

524626715227865

±0.±0.±0.±0.±0.±0.±0.±0.±0.±0.±0.±0.±0.±0.±0.

091

084097081070136215114102123219205125116121

5562657630480

Wine

数。QPSO的算法流程如下:

输入　聚类的个数、数据向量、粒子的个数输出　每次迭代后粒子最佳适应性值Je(1)初始化。

ForT=1:MAXITER

(2)根据Euclidean距离进行聚类(参照PSO聚类过程)。(3)根据式(9)计算mbest。(4)更新局部最优pbest。(5)更新全局最优gbest。(6)根据式(10)计算随机点。

(7)根据式(11)更新粒子的中心向量。end

K2MeansPSO

Breast2cancerKPSO

QPSOKQPSO　　从表1可以得出下列信息:

(1)考虑量化误差,对于三个问题来说,QPSO和KQPSO量化误差的平均值最小,其性能最好。总体来说,QPSO和

KQPSO不如其他聚类方法稳定。

(2)考虑聚类内部的距离,它表明了一个聚类内部的每个

数据向量与聚类中心的偏离,其值越小,聚类越精确。QPSO对Iris和Breast2cancer问题来说,保证了聚类内部比较紧凑;

KQPSO保证了Wine聚类内部比较紧凑。

(3)考虑聚类之间的距离,它表明了聚类之间的中心向量

重复计算(2)～(7),直到满足迭代的次数为止。

PSO与QPSO的不同之处在于进化方法不同,即更新中心

向量的方法不同。

312　K2Means和QPSO的混合聚类———KQPSO

K2Means算法和QPSO算法混合聚类KQPSO的过程为:(1)执行K2Means聚类算法一次,使K2Means算法返回的

之间的距离,其值越大越好。QPSO对Wine问题来说,其聚类之间的偏差很大;KQPSO对Breast2cancer问题来说,其聚类之间的偏差很大。

图1是针对问题Wine的算法收敛性。从图1可以看出,K2

Means的收敛速度最快,但是其量化误差的值比较大,聚类不精

结果为Nc个聚类中心向量;将这Nc个聚类中心向量作为粒子群中的一个粒子,粒子群中其余的粒子根据数据向量的范围随机初始化。

(2)执行QPSO聚类算法的流程。

确;PSO和QPSO的收敛速度较慢,量化误差比较小;QPSO收敛速度比PSO稍慢,其量化误差也比PSO稍小,聚类比较精确。

4　实验结果

本节比较K2Means,PSO,KPSO,QPSO,KQPSO五种聚类方法的性能,依据下面的三条规则来测试五种算法的性能:

(1)式(8)定义的量化误差(即适应性函数)。

(2)聚类内部的距离(Intra2clusterDistances),即一个聚类

中数据向量之间的距离。

(3)聚类之间的距离(Inter2clusterDistances),即聚类的中心向量之间的距离。

我们的目标是缩小聚类的量化误差,将聚类内部的距离减到最小,将聚类之间的距离增到最大。

为了比较四种聚类方法的性能,实验中用到了三个数据集,分别为

(1)IrisPlantsDatabase。它含有150个数据向量,分成三类,每个数据向量有四个属性。

5　结论

本文使用了五种算法对数据集聚类。通过实验,表明了基于QPSO算法的聚类可以收敛到较小的量化误差,并且就总体来说,基于QPSO算法形成的聚类之间的距离比较大,聚类内部的距离比较小。参考文献:

[1]SunJ,XuWB.AGlobalSearchStrategyofQuantum2behavedParti2

cleSwarmOptimization[C].ProceedingsofIEEEConferenceonCy2berneticsandIntelligentSystems,2004.1112116.

(下转第45页)

第12期

束条件等。

刘　斌等:基于构件的工作流动态修改策略　　　・45・

　　(3)支持构件复用和模型复用。构件一经建立就可以复用在多个工作流模型中。同样,工作流模型建立后,直接或者稍加修改即可应用在同类工作流设计中,无须一个新的建模过程,从而节省了大量的资源和时间,提高了开发速度和开发质量。

当然,并不是所有的修改要求通过组装策略都可以组装成满足要求的工作流模型。当出现意外或不能满足修改要求时,可以按照组装策略中提到的解决方法在更新了构件库后重新进行组装,也可以提示用户进行自定义手动更新和组装,这样就保证了工作流实例运行的正确性。

③对不确定具体功能的工作流节点或者工作流部分流程进行修改。抽象构件用于表示在工作流模型定义阶段的不确定部分,在工作流执行过程中根据具体的实例确定抽象构件中的构件、构件连接方式及其属性。

为保证工作流修改时,系统能正常不间断地执行,对于不同状态下的工作流实例,我们的策略是:

(1)对于需要修改的已经执行完毕的工作流过程实例,仍

承认其执行结果。

(2)对于需要修改的工作流实例,如果正在执行,需要确

定其修改的范围是否正在工作;如果正在工作或者已经执行完毕,则按照原方案继续执行,即不进行修改;如果还没有执行到,则对其进行修改。

(3)对于需要修改的工作流实例,如果还没有开始执行,

6　结论

目前,工作流管理系统在企业中仍然没有得到广泛的应用,其主要原因之一是目前的工作流管理系统在模型描述能力以及动态修改方面存在着不足。因此,本文提出了基于构件库和组装策略的动态修改体系结构。通过实际的工作流软件系统开发,表明该方法能使工作流的动态修改更简单、方便和安全,是工作流管理系统动态修改的一种比较理想的解决方案,将会具有非常广泛的应用前景。参考文献:

[1]ChiuDKW,LiQ,KarlapalemK.AMataModelingApproachto

WorkflowManagementSystemSupportingExceptionHanding[J].In2formationSystem,1999,24(2):1592184.

[2]HaakeJM,WangWG.FlexibleSupportforBusinessProcess:Ex2

tendingCooperativeHypermediawithProcessSupport[J].tionandSoftwareTechnology,1999,4(6):3552366.

[3]CasatiF,CeriS,PerniciB,etal.WorkflowEvolution[J].Dataand

KnowledgeEngineering,1998,24(3):2112238.

[4]ReichertM,DadamP.ADEPTflex2SupportingDynamicChangesof

WorkflowswithoutLoosingControl[J].JournalofIntelligentInforma2tionSystem,1998,10(2):932129.[5]

EdmondD,TerHofstedeAHM.AReflectiveInfrastructureforWorkflowAdaptability[J].DataandKnowledgeEngineering,2000,34(3):2712304.

Informa2

则对其进行修改。

工作流的修改过程归纳为四个阶段:

(1)暂停执行。它是指将工作流实例中需要修改的部分工作流构件的状态设为挂起状态。(2)进行修改。管理人员通过图形界面管理工具对工作流实例重新进行组装或者修改工作流构件属性。

(3)正确性验证。它是指对修改后的工作流实例的结构

和语义进行正确性验证,以避免出现死锁、不可达、输入/输出数据不一致及语义不连贯等问题。

(4)继续执行。对修改完毕的工作流构件状态重新设为

就绪状态,以便工作流继续执行。

5　可行性、正确性说明

采用基于构件的动态修改策略进行工作流修改的好处是:

(1)工作流模型比较容易设计和修改。模型由构件组装

而成,修改时只需用图形界面的管理工具进行构件的重新组装或者构件的更新,容易操作且简单直观。

(2)更好的稳定性和安全性。对用户提出的修改要求只

作者简介:

刘斌(19792),男,山东青岛人,硕士研究生,主要研究方向为工作流技术、构件;张春海(19632),男,山东青岛人,副教授,主要研究方向为数据库理论及应用、工作流技术、构件等。

1995.

[8]APEngelbrecht.SensitivityAnalysisofMultilayerNeuralNetworks

[D].Stellenbosch:DepartmentofComputerScience,UniversityofStellenbosch,1999.

[9]AngelinePJ.UsingSelectiontoImproveParticleSwarmOptimization

[C].ProceedingsofIEEEInternationalConferenceonEvolutionaryComputation,1998.842.

[10]ClercM,KennedyJ.TheParticleSwarm:Explosion,Stabilityand

ConvergenceinaMulti2dimensionalComplexSpace[J].IEEETran2sactionsonEvolutionaryComputation,2002,(6):58273.

需在修改的区域更换工作流构件或者对现有构件进行修改,不会影响工作流的其他部分,提高了整个工作流系统的稳定性和安全性。

(上接第42页)

[2]SunJ,FengB,XuWB.ParticleSwarmOptimizationwithParticles

HavingQuantumBehavior[C].Proceedingsof2004CongressonEvo2lutionaryComputation,2004.3252331.

[3]曾建潮,介婧,崔志华.微粒群算法[M].北京:科学出版社,2004.[4]DWvanderMerwe,APEngelbrecht.DataClusteringUsingParticle

SwarmOptimization[J/OL].http://cirg.cs.up.ac.za/publications/CEC2003d.pdf.

[5]JKennedy,RCEberhart.ParticleSwarmOptimization[C].Pro2

ceedingsoftheIEEEInternationalJointConferenceonNeuralNet2works,1995.194221948.

[6]JKennedy,RCEberhart,YShi.SwarmIntelligence[M].Morgan

Kaufmann,2002.[7]

TKohonen.

Self2OrganizingMaps[M].Berlin:Springer2Verlag,

作者简介:

龙海侠,女,硕士研究生,主要研究方向为生物信息学、人工智能;须文波,男,博导,主要研究方向为人工智能、计算机控制技术、嵌入式操作系统;孙俊,男,博士研究生,主要研究方向为人工智能。