2015, Vol. 26
2 西华大学 电气信息学院, 四川 成都 610039;
3 Research Group of Natural Computing, University of Seville, Sevilla, Spain
2 School of Electrical and Information Engineering, Xihua University, Chengdu 610039, China;
3 Research Group of Natural Computing, University of Seville, Sevilla, Spain
聚类分析是数据挖掘中的一个核心问题.在很多场合中所获取的数据仅有输入而没有对应的输出,所以这些数据是未标记的或无监督的.数据聚类是用于处理这种数据的无监督学习过程,它依据某个相似性度量将对象进行分组,使得同组中的样本是相似的但不同组的样本是不相似的[1].聚类方法能够大体上分为3类:层次方法、划分方法和重叠方法[2,3]:层次聚类通过连续合并较小的簇为较大的簇或者分裂较大的簇来实现数据聚类,层次聚类包括凝聚和分裂两种子类型;划分方法依据某个准则将数据集分解为几个不相交的簇;而重叠方法则以某种方式放宽相互不重叠的约束实现软的或模糊划分.数据聚类已成功地应用于诸多领域,如数据挖掘、机器学习、图像处理和生物学等[4, 5, 6, 7].
对于划分聚类,普遍采用的准则是最小化每个簇中样本的不相似性和最大化不同簇间相异性.K-means是最流行的划分聚类算法之一,它之所以受到广泛关注,是由于其算法的简单性和伸缩性以及对于问题中任何变量具有线性渐进时间[8,9].然而,k-means对初始簇中心的选取非常敏感,以至于当未正确选取初始簇中心时,它可能会陷入局部最优解.近年来,进化算法的全局搜索能力已被采用,以克服k-means的缺陷.首先,几种基于遗传算法(GA)的聚类算法相继被开发,它们采用了不同形式表达聚类解.第1种算法直接采用染色体编码每个数据点所属的簇号[10,11],然而当数据点激增时,这种算法会遭遇巨大的搜索空间和高的搜索代价.为了改善搜索性能,第2种算法使用一种间接表示法,即,染色体编码一个数据集的全部簇中心[12,13,14,15],间接表示法随后被多数进化聚类算法所采用.此外,也开发了混合GA和k-means的方法,其中,GA用于聚类的特征选取[16].然而,GA可能遭遇退化是这类聚类算法的一个严重缺陷.为此,几个基于粒子群优化(PSO)、蚁群优化(ACO)的聚类算法已相继被提出.Kao等人提出了一种组合PSO和k-means的聚类方法[17],而Shelokar等人引入ACO去处理聚类问题[18].另外,Niknam等人提出了一种组合PSO,ACO和k-means的聚类方法[19].
膜计算(membrane computing)是一类新颖的分布式、并行计算模型,由Gheorghe Păun于2000年正式提出[20].作为自然计算的一个新分支,它旨在从生命细胞的结构与功能中以及从组织和器官等细胞群的协作中抽象出计算模型,这类计算模型也常称为P系统(P systems).P系统包含3个核心要素:膜结构、对象和进化规则[21].P系统通过细胞(膜)中对象的进化实现信息的计算和处理.此外,源自于细胞生物学的不同机制已融入到P系统中,提出了众多的变体[22, 23, 24, 25, 26, 27, 28].这些多种多样的机制为处理实际问题提供了新颖的思路.
为了弥补上述缺陷,本文引入膜计算处理数据聚类问题,提出了一种在膜计算框架下的聚类算法,称为膜聚类算法(membrane clustering algorithm),简称MC算法.为此开发了一个组织P系统.它由3个细胞构成,每个细胞包含若干对象,并且每个对象表达一组候选的簇中心.分别引入3种不同的进化机制以实现对象进化,即遗传算子[29]、速度-位移模型[30]和差分进化机制[31].而且,通过融入细胞膜间的转运机制提出了原始的速度-位移模型和差分进化机制的改进版本,其中,两种不同源的最好对象在这些改进进化机制中将指导对象进化.在这些进化机制和转运机制的控制下,这个组织P系统能够充分地开采整个搜索空间并发现出最优簇中心.
近年来,膜计算由于并行计算、非确定性、可编程性等特征已经受到越来越多的关注.膜计算的研究主要涵盖3个方面:(1) 建模与理论分析,即,各种P系统的建立及其计算能力和有效性分析;(2) 面向实际系统的P系统构建与应用;(3) P系统仿真平台的开发.已有理论成果揭示了P系统是强大的(在大多数情况下具有图灵完备性)和高效的(特别是其能以线性或多项式时间求解众多的NP完备问题);同时,多个P系统软、硬件仿真平台相继开发成功[24].近年来,膜计算的应用研究逐步受到重视,学者们陆续采用膜计算求解一些实际问题,诸如模糊推理[25,27]、故障诊断[26]、图像处理[28]、优化问题[32]、生态系统仿真[33]和合成生物学[34]等.不同于已有的工作,本文的动机是采用膜计算求解数据聚类问题,并且成功开发出一种在膜计算框架下的聚类算法.
1 数据聚类问题数据聚类是诸如数据挖掘、机器学习和模式识别的基础工具之一.众所周知,通过最小化某个相异性度量在非均匀数据中发现数据分组是一个NP难问题.一个d维欧式空间中的数据聚类可被描述为这样一个过程,它根据某种相似性(距离)度量将一个含n个模式或数据点的数据集划分到几个组(或簇)中.记X={X1,X2,…,Xn}是一个由n个未标记数据点组成的数据集,其中,Xi=(xi1,xi2,…,xid)是一个d维向量,i=1,2,…,n,且xij表示Xi的第j个实值特征.对于数据集X,划分聚类算法尝试发现K个簇的一个划分{C1,C2,…,CK},使得相同簇中的模式有最大的相似性,而不同簇中的模式有尽可能高的相异性.这个划分应满足如下的性质:(1) Ci¹Æ,对任意iÎ{1,2,…,K};(2) CiÇCj=Æ,对任意i¹j且i,jÎ{1,2,…,K};(3) $\bigcup\nolimits_{i = 1}^K {{C_i}} = S.$
在评估两个模式的相似性时,多数方法使用了欧式距离.任何两个d维模式Xi和Xj的欧式距离由下式给出:
| $d({X_i},{X_j}) = \sqrt {\sum\limits_{p = 1}^d {{{({x_{ip}} - {x_{jp}})}^2}} } = ||{X_i} - {X_j}||$ | (1) |
为了发现K个簇的最优划分,聚类问题常定义为一个性能函数的最优(最小)问题.对于这K个簇的优良性度量,一种较流行的性能函数是整体簇内方差或整体均方差(MSE),即
| ${J_m}({C_1},{C_2},...,{C_K}) = \sum\limits_{i = 1}^K {\sum\limits_{{X_j} \in {C_i}} {||{X_j} - {z_i}||} } $ | (2) |
其中,z1,z2,…,zK分别是划分C1,C2,…,CK的簇中心,且ziÎRd,i=1,2,…,K.
2 带混合进化机制的膜聚类算法组织P系统是膜计算模型的主要类型之一,它抽象于在一个公共环境中进化的多个单膜细胞行为,其结构为网状结构,其中每个细胞视为一个信息处理器,它处理对象并且沿细胞之间预先指定的通道转运这些对象[22].对象的处理由进化规则完成,而转运通过转运规则所实现.所探讨的膜聚类算法使用一个度为3的组织P系统,这里,我们仅讨论这个特殊设计的组织P系统,而有关更一般的组织P系统的知识请参阅文献[21,22].
2.1 一个度为3的组织P系统我们所考虑的度为3的组织P系统(由3个细胞组成)形式地定义为如下的一个元组:
P=(O1,O2,O3,R1,R2,R3,R¢,io).
其中,(1) O1,O2和O3分别为这3个细胞的对象集;(2) R1,R2和R3分别为这3个细胞的进化规则集;(3) R¢为细胞膜之间转运规则集;(4) io=0,指示环境为系统的输出区域.
图 1给出了这个组织P系统的膜结构,其中,3个细胞分别由3个基本膜所围成,分别用1,2和3标记.环境由0标记.这3个基本膜称为进化膜,因为其作用是进化系统中的对象.将引入混合进化机制实现对象的进化,具体设计如下:细胞1采用3种遗传算子(选择、交叉和变异)作为对象进化机制,细胞2使用速度-位移模型,而细胞3则应用差分进化机制实现对象的进化.混合进化机制带来的益处是增强系统中对象的多样性.图 1中的有向线表示进化膜之间对象的转运通道,对象转运将实现进化膜之间对象交换与共享.对象的转运是由转运规则完成.这种转运机制能够实现在这3个进化膜之间对象的协同进化,并加速系统的收敛.约定环境为系统的输 出膜.
 | Fig. 1 A tissue P system of degree 3图 1 一个度为3的组织P系统 |
组织P系统在膜聚类算法中的主要职责是为一个数据集搜索最优的簇中心,为此,采用对象来表达一组(候选的)簇中心.假定数据集X有K个簇C1,C2,…,CK,对应的簇中心分别为z1,z2,…,zK.和数据点一样,每个簇中心是一个d维向量,即zi=(zi1,zi2,…,zid),i=1,2,…,K,于是,细胞中对象可设计为如下形式的Kxd维向量:
Z=(z11,z12,…,z1d,…,zi1,zi2,…,zid,…,zK1,zK2,…,zKd).
其中,z1d,…,zi1,zi2,…,zid对应于第i个簇中心的d个分量,i=1,2,…,K.
Oi是第i个进化膜的对象集,通常包含一定数量的对象,这些对象将由相应的进化规则所进化.为简单起见,假定3个进化膜有相同个数的对象,并记m为每个进化膜中对象个数.在计算过程中,环境中始终保存着整个系统迄今为止发现的最好对象,它称为全局最优对象,记为Zbest.当系统停机后,Zbest即为所求的最终解.
初始时,系统将为每个进化膜生成m个初始对象,组成其对象集Oi(i=1,2,3).当生成一个初始对象时,系统将重复地产生Kxd个随机实数并满足数据集中样本点相应维度的取值范围.
在对象进化过程中,系统需要一个度量来评估对象的优劣.本文直接使用聚类问题的性能函数Jm作为对象的度量或适应度.Jm值越小,对象越好;否则越差.
2.1.2 混合进化机制在组织P系统中,每个细胞包含若干进化规则,其作用是进化其对象.进化规则的一般形式为u®v,其含义是对象u被进化为对象v.在所设计的组织P系统中,3个进化膜分别引入了3种不同进化技术来实现对象的进化,它们分别是遗传操作(选择、交叉和变异)[29]、速度-位移模型[30]和差分进化机制[31].这3种不同进化技术分别作为3个进化膜的进化规则.进化膜的混合进化机制必将增强这个组织P系统在进化过程中对象的多样性.为了更好地融入这3种进化技术,依据所使用的膜结构与转运机制,开发了这3种进化技术的改进版本,特别是改进的速度-位移模型和改进的差分进化机制.具体描述如下:
· 膜1的进化规则
进化膜1采用GA[29]的3种遗传操作(选择、交叉和变异)作为进化规则,实现其对象的进化.在每个计算步中,进化膜1将自身的m个对象和转运自其他两个进化膜的2r个对象构成一个进化池.对进化池中对象执行选择、交叉和变异操作.为了保持膜中对象规模不变,将执行截断操作.截断操作依据对象的适应度进行,以保留最好的m个对象.
在具体实现中,选择操作采用轮赌法而交叉操作使用实数形式的单点交叉,其中,交叉位置(即,对象的某个分量)是根据交叉概率pc所确定.对象的变异采用了如下实数形式的单点变异:如果z是根据变异概率pm所确定的对象Z的变异点(即某个分量),则变异后的值为
| $z' = \left\{ {\begin{array}{*{20}{l}} {z \pm 2\delta z,{\rm{ }}z \ne 0}\\ {z \pm 2\delta ,{\rm{ }}z = 0} \end{array}} \right.$ | (3) |
其中,“+”和“-”以等概率出现,d是依据均匀分布生成的[0,1]中的一个随机实常数.
· 膜2的进化规则
PSO的速度-位移模型[30]作为进化膜2的进化规则被考虑.然而,结合组织P系统的相关机制,提出了一种改进的速度-位移模型.改进是源自于这样一种直觉:进化膜2有两种最优对象,一种是它迄今为止所发现的最优对象(称为局部最优对象,记为Zlbest),另一种是转运自其他两个进化膜的2r个最优对象(称为外部最优对象).从这2r个外部最优对象中随机地选取一个,记为Zebest.这两种最优对象将参与或指导进化膜2中对象的进化.这两种由不同进化技术所产生的最优对象势必增强系统对象的多样性和全局探测能力.
假设Zi为进化膜2中第i个对象,这个改进的速度-位移模型可被描述如下:
| $\left\{ {\begin{array}{*{20}{l}} {{V_i} = w \cdot {Z_i} + {c_1}{r_1}({P_i} - {Z_i}) + {c_2}{r_2}({Z_{lbest}} - {Z_i}) + {c_3}{r_3}({Z_{ebest}} - {Z_i})}\\ {{{Z'}_i} = {Z_i} + {V_i}} \end{array}} \right.$ | (4) |
其中,Vi为Zi对应的速度,Zi'为Zi进化后的值,Pi表示对象Zi迄今为此所发现的最好位置,w为惯性权重,c1,c2,c3为学习因子,r1,r2,r3为3个[0,1]中的随机数.在实现时,惯性权重将采用线性递减的策略.
· 膜3的进化规则
进化膜3将采用差分进化算法[31]的差分进化机制作为进化规则.众所周知,原始的差分进化机制主要包括3种进化算子:变异、交叉和选择.基于同样原因,提出了一种改进的差分进化机制,主要体现在变异算子的设计上,然而交叉和选择算子完全同原始的差分进化机制,这里不再赘述,仅描述改进的变异算子.
假设Zi为进化膜3中第i个对象,则变异向量Yi由下式生成:
| ${Y_i} = \left\{ {\begin{array}{*{20}{l}} {{Z_i} + \alpha ({Z_{lbest}} - {Z_i}) + \alpha ({Z_{ebest}} - {Z_i}) + \alpha ({Z_{{r_1}}} - {Z_{{r_2}}}),{\rm{ if }}rand(0,1) < \alpha }\\ {{Z_i} + F({Z_{{r_3}}} - {Z_{{r_4}}}),{\rm{ otherwise}}} \end{array}} \right.$ | (5) |
其中,Zlbest为膜3中的局部最优对象,Zebest是外部最优对象(它是从2r个外部最优对象中随机地选取一个),Zr1,Zr2,Zr3,Zr4是膜3中随机挑选的4个对象.a和F是两个尺度因子,分别计算如下:
| $\alpha = \frac{1}{{1 + \exp \left[{ - \frac{1}{{{t_{\max }}}}} \right]}},F = 0.5 \times (1 + rand(0,1))$ | (6) |
其中,tmax为最大计算步数(或最大迭代次数).在公式(5)和公式(6)中,rand(0,1)表示区间(0,1)的一个随机实数生成函数.在得到变异向量Yi后,再经过通常的交叉和选择规则产生Zi进化后的值.
2.1.3 转运机制细胞膜之间可能存在转运通道,用于它们之间对象的交换与共享.这种转运机制是通过细胞间的转运规则来提供.在所设计的组织P系统中,有如下两类转运规则:
· $(i,{Z_1}{Z_2}...{Z_r}/{Z'_1}{Z'_2}...{Z'_r},j)$,i¹j,i,j=1,2,3.
这是一条细胞i和细胞j之间的双向转运规则,其中,Z1,Z2,…,Zr为细胞i的r个对象,而${Z'_1},{Z'_2},...,{Z'_r}$为细胞j的r个对象.该规则执行意味着:细胞i中r个对象Z1,Z2,…,Zr被转运到细胞j中;同时,细胞j中r个对象${Z'_1},{Z'_2},...,{Z'_r}$被转运到膜i中.
· (i,Zlbest/l,0),i=1,2,3.
这是一条细胞i和环境之间的单向转运规则,其中,Zlbest为当前计算步中细胞i的(局部)最优对象,且l表示空对象.该规则的执行意味着:细胞i中对象Zlbest被转运到环境中,并更新环境中的全局最优对象Zbest.
在所设计的组织P系统中,3个进化膜利用第1类转运规则建立起它们之间的对象转运关系,这种转运关系逻辑上为任意两个细胞提供了两条虚拟有向弧,如图 2所示.每个进化膜通过第1类转运规则将其r个最好对象转运到其他两个进化膜中.于是,每个进化膜也将接收到来自于其他两个进化膜的最好对象.所接收到的这2r个对象构成该进化膜的一个外部最优对象子集,将在下一计算步中参与对象进化.
 | Fig. 2 Flow chart of the membrane clustering algorithm图 2 膜聚类算法的流程图 |
在每个计算步中,进化膜使用第2类单向转运规则将其最好对象转运到环境中,并更新全局最优对象Zbest.更新策略如下:如果转运的对象优于这个全局最优对象Zbest,则这对象将替换Zbest;否则,它被丢弃.
从上面的描述中可以看出,细胞间的这种转运关系隐含地揭示了这个组织P系统的网状结构.这种内在转运关系能够为采用混合进化技术的这3个进化膜提供一种协同进化机制,有助于加速整个系统的收敛.
2.1.4 停机与输出组织P系统的各个细胞作为执行单元并行地运行(假定存在一个全局时钟,用于标定时间),所以,系统的功能是分布式和并行的.定义组织P系统的一个计算为一系列的计算步,它们从包含初始对象集的3个细胞开始,并且在每个计算步中,一个或多个规则作用于当前对象集上.如果系统达到停机条件,则系统停机.这时,计算结果位于输出膜(即环境)中.
为简单起见,采用了一种简单的停机条件:设置最大执行步数.这个组织P系统会持续运行直到其达到最大执行步数为止,系统停机.当系统停机时,环境中所保存的最优对象为最终输出结果,即所发现的最优簇中心.
2.2 膜聚类算法本文所提出的膜聚类算法是一种在膜计算框架下的划分聚类算法,其核心是一个度为3、具有混合进化机制的组织P系统,其作用是自动地为一个待聚类的数据集搜索最优的簇中心.
对于一个具有n个数据点的数据集X,假定将这些数据划分为K个簇.组织P系统中的每个对象表达一组候选的簇中心.膜聚类算法首先为每个进化膜生成m个初始对象,然后执行这个组织P系统.在混合进化机制和转运机制的控制下,这个组织P系统不断地进化系统中的对象并更新全局最优对象Zbest,直到系统满足停机条件为止.当系统停机时,这个全局最优对象Zbest即为最优簇中心.最后,膜聚类算法根据这个最优簇中心重新划分n个数据点到相应的K个簇中完成数据聚类.
图 2给出了这种膜聚类算法的流程图.
3 仿真实验 3.1 实验数据集为了评估膜聚类算法,实验中使用了8个数据集,其中3个是2维的人工数据集(AD_5_2,Square_4和Sym_3_22),另外5个是来自于UCI的真实数据集(Iris,LungCancer,Newthyroid,Wine和Livedisorder)[35].图 3显示了这3个人工数据集.表 1给出了这8个数据集的简单描述.
 | Fig. 3 Three artificial data sets图 3 3个人工数据集 |
|
Table 1 Data sets used in experiments 表 1 实验中所使用的数据集 实验中所使用的数据集 |
在实验中,所提出的膜聚类算法将与k-means算法和几种典型的进化算法进行对比,包括GA[29],PSO[17],ACO[18]和PSO-ACO[19].同时,考虑到所设计的组织P系统中采用了改进的速度-位移模型和改进的差分进化机制,为了研究其对聚类性能的提升效果,我们实现了这个膜聚类算法的另外两个副本,它们分别使用标准的速度-位移模型和标准的差分进化机制(“rand/1”型的变异规则).记采用混合进化机制的系统为Hybrid-P systems,而另外两个副本分别为PSO-P systems和DE-P systems.通过在上述8个数据集上的仿真结果来评估这些聚类算法的聚类性能.
Hybrid-P systems的参数设置如下:每个细胞(膜)中对象的个数m为100,最大执行步数为100;(细胞1中)遗传操作采用自适应的交叉概率和变异概率;(细胞2中)改进的速度-位移模型采用线性递减的惯性权重,且c1=c2=c3=1.0;(细胞3中)改进的差分进化机制所使用的交叉概率为0.9.为了对比的需要,PSO-P systems和DE-P systems分别采用了与Hybrid-P systems的参数.
在实现其他4种进化算法(GA,PSO,ACO和PSO-ACO)时,通过几组典型参数的结果比较来确定最佳的参数值.这些参数设置如下:(1) PSO参数为c1=c2=2.0;(2) ACO参数为g1=g2=0.5,r=0.99;(3) 除了与PSO和ACO相同的参数以外,PSO-ACO的其他参数为D0=10,a=15,r=0.5;(4) GA的交叉概率和变异概率分别为0.8和0.001.另外,这些算法的最大迭代步数均设置为100.
3.3 实验结果为了评估这些聚类算法的聚类质量,实验采用如下3种度量:
(i) 整体均方差,见公式(2).一般地,其值越小,聚类质量越好.
(ii) Silhouette Index (SI).假设a表示一个点与来自于这个簇的其他点的平均距离,b表示这个点与其他簇中点的平均距离的最小值,于是这个点的Silhouette宽度定义为
| $s = \frac{{b - a}}{{\max \{ a,b\} }}$ | (7) |
SI值是所有数据点的Silhouette宽度的平均值,它介于[-1, 1]之间.一般地,较高的SI值意味着较好的聚类质量.
(iii) CS度量.该度量是由Chou等人[36]提出的.研究表明,CS度量能够有效地处理不同密度和规模的簇.CS度量定义如下:
| $CS(K) = \frac{{\sum\limits_{i = 1}^K {\left[{\frac{1}{{{N_i}}}\sum\limits_{{X_i} \in {C_i}} {\mathop {\max }\limits_{{X_q} \in {C_i}} ||{X_i} - {X_q}||} } \right]} }}{{\sum\limits_{i = 1}^K {\mathop {\min }\limits_{j \in K,j \ne i} ||{m_i} - {m_q}||} }}$ | (8) |
其中,mi由下式计算:
一般地,CS度量值越小则意味着所得到的划分越好.即,聚类算法获得了良好的聚类性能,反之亦然.
考虑到这些聚类算法中包含随机因素,并且每次运行的结果可能不一样,所以在每一个数据集上对每种算法都独立地运行100次,分别计算上述3个度量对这100次运行的平均值和标准差.平均值将反映算法的平均性能,而标准差则指示算法的鲁棒性.表 2~表 9分别给出了这些聚类算法在3个人工数据集和5个真实数据集上的仿真结果.每一个表分别提供了这8个聚类算法的Jm,SI和CS度量的平均值和标准差,它们是在对应数据集上独立地运行100次的结果.
|
|
Table 2 Experimental results on AD_5_2 表 2 在AD_5_2上的实验结果 |
|
|
Table 3 Experimental results on Square_4 表 3 在Square_4上的实验结果 |
|
|
Table 4 Experimental results on Sym_3_22 表 4 在Sym_3_22上的实验结果 |
|
|
Table 5 Experimental results on Iris 表 5 在Iris上的实验结果 |
|
|
Table 6 Experimental results on LungCancer 表 6 在LungCancer上的实验结果 |
|
|
Table 7 Experimental results on Newthyroid 表 7 在Newthyroid上的实验结果 |
|
|
Table 8 Experimental results on Wine 表 8 在Wine上的实验结果 |
|
|
Table 9 Experimental results on Livedisorder 表 9 在Livedisorder上的实验结果 |
首先,我们观察Hybrid-P systems与它的两个副本PSO-P systems和DE-P systems的对比结果.在所有的数据集上,对比于两个副本PSO-P systems和DE-P systems,Hybrid-P systems有更低的Jm值和CS值以及更高的SI值.这说明本文采用的混合进化机制在提升膜聚类算法平均性能方面具有较明显的优势.从标准差来看,Hybrid-P systems和DE-P systems均低于PSO-P systems.这说明Hybrid-P systems和DE-P systems均比PSO-P systems更加鲁棒,但两者却非常接近.
其次,我们比较Hybrid-P systems与其他4种聚类算法,Hybrid-P systems和PSO-ACO在这8个数据集上获得了更低的Jm值和CS值以及更高的SI值.这说明Hybrid-P systems和PSO-ACO有较好的聚类效果.与此同时,也能看到,Hybrid-P systems的聚类性能稍好于PSO-ACO算法.在标准差方面,Hybrid-P systems对比其他5种聚类算法有更加显著的优势,在多数情况下,Hybrid-P systems得到了为0或非常低的标准差.该结果说明,Hybrid-P systems有更好的鲁棒性.
从实验结果以及以上分析可以得出如下结论:(1) 由组织P系统内在机制所启发的膜聚类算法有更好的平均聚类性能以及较高的鲁棒性;(2) 混合进化机制以及改进的速度-位移模型和差分进化机制能够较好地改进膜聚类算法的聚类性能.
Wilcoxon秩和检验[37]是一种用于独立样本的非参数统计显著性检验方法.实验中,这种统计显著性检验已在5%的显著性级上完成.对每个数据集建立6个组,分别对应于这6种聚类算法(hybrid-P systems,k-means,GA,PSO,ACO和PSO-ACO),其中,每一个组由相应聚类算法分别在这些数据集上连续执行100次的SI值组成.表 2~表 9分别给出了这些数据集上每个聚类算法所对应的一组的SI的平均值.这些结果表明,Hybrid-P systems的平均性能比其他5个聚类算法的平均性能要好.
为了进一步说明这种优良性是统计显著的,我们完成了一个统计显著性检验.零假设是假定两个组的平均值之间没有显著性差别,然而另一种假设是两个组的平均值之间有显著性差别.实验依次比较了Hybrid-P systems这组与其他5个组中的任何一组,计算相应的Wilcoxon秩和检验所生成的P-值(接受零假设的概率).
表 10给出了在这些数据集上Wilcoxon秩和检验的结果.在表 10中,所有的P-值是低于0.05(5%显著性级),这表明以强的理由拒绝零假设.实验结果证实了Hybrid-P systems所产生的较好的SI平均值是统计显著的而不是偶然得到的.
|
|
Table 10 Results of P-values produced by Wilcoxon’s rank sum test 表 10 由Wilcoxon秩和检验产生的P-值结果 |
本文探讨了使用具有混合进化机制的组织P系统去处理数据聚类问题,提出了一种在膜计算下的划分聚类算法,即,膜聚类算法.一个由3个细胞构成的组织P系统是这种膜聚类算法的核心,并依据它的膜结构和转运机制提出了一种改进的速度位移模型和一种改进的差分进化机制.这种膜聚类算法的性能分别在3个人工数据集和5个真实数据集上进行评估.实验结果显示:与k-means和几种进化聚类算法相比,膜聚类算法有更好的优势.这个研究也揭示了组织P系统解决数据聚类问题的有效性.
组织P系统利用多个细胞中对象进化以及细胞间对象转运来搜索最优解,这类似于已有的多种群进化算法,然而,这里组织P系统的机理是源自于细胞生物学.众所周知,已有的众多P系统模型分别源自于细胞生物学的不同机理,诸如酶机制、催化机制、细胞分裂与溶解机制、转运通道的激活与抑制等.这些机制的引入,是我们进一步研究的方向.从另一个角度来讲,融合不同细胞生物学机理的、处理优化问题的P系统也可以视为多种群进化算法的一个补充.另外,本文的膜聚类算法存在一个限制,即,需要预先指定簇个数K.在进一步的工作中,我们考虑引入细胞分裂与溶解机制来解决这个问题.
| [1] | Gan G, Ma C, Wu J. Data Clustering: Theory, Algorithms, and Applications. SIAM, 2007. |
| [2] | Xu R, Wunsch D. Survey of clustering algorithm. IEEE Trans. on Neural Networks, 2005,16(3):645-678 . |
| [3] | Jain AK. Data clustering: 50 years beyond k-means. Pattern Recognition Letters, 2010,31(8):651-666 . |
| [4] | Everitt B, Landau S, Leese M. Cluster Analysis. London: Arnold, 2001. |
| [5] | Saha S, Bandyopadhyay S. A symmetry based multiobjective clustering technique for automatic evolution of clusters. Pattern Recognition, 2010,43(3):738-751 . |
| [6] | Das S, Sil S. Kernel-Induced fuzzy clustering of image pixels with an improved different evolution algorithm. Information Sciences, 2010,180(8):1237-1256 . |
| [7] | Naldi MC, Campello RJGB, Hruschka ER, Carvalho ACPLF. Efficiency issues of evolutionary k-means. Applied Soft Computing, 2011,11(8):1938-1952 . |
| [8] | Kanungo T, Mount D, Netanyahu NS, Piatko C, Silverman R, Wu A. An efficient k-means clustering algorithm: Analysis and implementation. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2002,24(7):881-892 . |
| [9] | Wu X, Kumar V. The Top Ten Algorithms in Data Mining. Chapman and Hall/CRC, 2009. |
| [10] | Murthy CA, Chowdhury N. In search of optimal clusters using genetic algorithms. Parttern Recognition Letters, 1996,17(8):825- 832 . |
| [11] | Maulik U, Bandyopadhyay S. Genetic algorithm based clustering technique. Pattern Recognition, 2000,33(9):1455-1465 . |
| [12] | Bandyopdhyay S, Saha S. GAPS: A clustering method using a new point symmetry-based distance measure. Pattern Recognition, 2007,40(12):3430-3451 . |
| [13] | Bandyopdhyay S. Genetic algorithms for clustering and fuzzy clustering. Data Mining and Knowledge Discovery, 2011,1(6): 524-531 . |
| [14] | Chang D, Zhang X, Zheng C. A genetic algorithm with gene rearrangment for k-means clustering. Pattern Recognition, 2009,42(7): 1210-1222 . |
| [15] | Nguyen CD, Cios KJ. GAKREM: A novel hybrid clustering algorithm. Information Sciences, 2008,178(22):4205-4227 . |
| [16] | Laszlo M, Mukherjee S. A genetic algorithm that exchanges neighboring centers for k-means clustering. Pattern Recognition Latters, 2007,28(16):2359-2366 . |
| [17] | Kao YT, Zahara E, Kao IW. A hybridized approach to data clustering. Expert Systems with Applications, 2008,34(3): 1754-1762 . |
| [18] | Shelokar PS, Jayaraman VK, Kulkarni BD. An ant colony approach for clustering. Analytica Chimica Acta, 2004,509(2): 187-195 . |
| [19] | Niknam T, Amiri B. An efficient hybrid approach based on PSO, ACO and k-means for cluster analysis. Applied Soft Computing, 2010,10(1):183-197 . |
| [20] | Păun G. Computing with membranes. Journal of Computer and System Sciences, 2000,61(1):108-143 . |
| [21] | Păun G, Rozenberg G, Salomaa A. The Oxford Handbook of Membrane Computing. New York: Oxford University Press, 2010. |
| [22] | Freund R, Păun G, Pérez-Jiménez MJ. Tissue-Like P systems with channel-states. Theoretical Computer Science, 2005,330(1): 101-116 . |
| [23] | Ionescu M, Păun G, Yokomori T. Spiking neural P systems. Fundameta Informaticae, 2006,71(2-3):279-308. |
| [24] | Păun G, Pérez-Jiménez MJ. Membrane computing: Brief introduction, recent results and applications. BioSystems, 2006,85(1): 11-22 . |
| [25] | Wang J, Zhou L, Peng H, Zhang GX. An extended spiking neural P system for fuzzy knowledge representation. Int’l Journal of Innovative Computing, Information and Control, 2011,7(7A):3709-3724. |
| [26] | Peng H, Wang J, Pérez-Jiménez MJ, Wang H, Shao J, Wang T. Fuzzy reasoning spiking neural P system for fault diagnosis. Information Sciences, 2013,235:106-116 . |
| [27] | Wang J, Shi P, Peng H, Pérez-Jiménez MJ, Wang T. Weighted fuzzy spiking neural P systems. IEEE Trans. on Fuzzy Systems, 2013,21(2):209-220 . |
| [28] | Peng H, Wang J, Pérez-Jiménez MJ, Shi P. A novel image thresholding method based on membrane computing and fuzzy entropy. Journal of Intelligent & Fuzzy Systems, 2013,24(2):229-237 . |
| [29] | Davis L. Handbook of Genetic Algorithms. Van Nostrand Reinhold, 1991. |
| [30] | Kennedy J, Eberhart R. Particle swarm optimization. In: Proc. of the IEEE Int’l Conf. on Neural Network, Vol.4. Piscataway, 1995. 1942-1948 . |
| [31] | Price K, Storn R, Lampinen J. Different Evolution—A Practical Approach to Global Optimization. Berlin: Springer-Verlag, 2005 . |
| [32] | Zhang GX, Cheng JX, Gheorghe M, Meng Q. A hybrid approach based on differential evolution and tissue membrane systems for solving constrained manufacturing parameter optimization problems. Applied Soft Computing, 2013,13(3):1528-1542 . |
| [33] | Colomer AM, Margalida A, Pérez-Jiménez MJ. Population dynamics P systems (PDP) models: A standarized protocol for describing and applying novel bio-inspired computing tools. Plos One, 2013,8(4):1-13 . |
| [34] | Frisco P, Gheorghe M, Pérez-Jiménez MJ. Applications of Membrane Computing in Systems and Synthetic Biology. Springer- Verlag, 2013 . |
| [35] | UCI datasets. http://www.ics.uci.edu/~mlearn/MLRepository.html |
| [36] | Chou CH, Su MC, Lai E. A new cluster validity measure and its application to image compression. Pattern Analysis and Applications, 2004,7(2):205-220 . |
| [37] | Hollander M, Wolfe DA. Nonparametric Statistical Methods. 2nd ed., 1999. |