一种基于粒子群优化的顶点着色聚类算法及其应用

丁 辉 胡 芬

(四川师范大学数学与软件科学学院，四川 成都 610066)(长江职业学院公共课部，湖北 武汉 430074)

2013-09-10

丁辉(1983-)，男，硕士生，现主要从事算法设计方面的研究工作。

胡芬(1982-)，女，硕士，讲师，现主要从事概率统计方面的教学与研究工作；E-mail:644107401@qq.com。

一种基于粒子群优化的顶点着色聚类算法及其应用

丁 辉 胡 芬

(四川师范大学数学与软件科学学院，四川 成都 610066)(长江职业学院公共课部，湖北 武汉 430074)

针对数据挖掘中的聚类问题，提出一种基于粒子群优化的顶点着色聚类算法。根据修改粒子群算法中参数值，扩展种群的搜索范围，增强整个群体聚类效果，用顶点着色算法进行进一步聚类。将改进的聚类算法应用于识别阿尔兹海默病(Alzheimer’s disease)候选基因中，识别出了一些真实的候选基因(Somatostatin, GABRA1,MOG)。

粒子群优化；顶点着色；聚类算法； 阿尔兹海默病

粒子群优化(Particle Swarm Optimization, PSO)算法是一种基于群体智能的具有全局寻优能力的优化工具，通过群体中粒子间的合作与竞争产生的群体智能指导优化搜索，每代种群中的解具有“自我”学习提高和向“他人”学习的优点，能够得到较优解[1-2]。PSO算法的基本属性是：①基于一个随机初始化种群；②通过反复迭代寻找最优解；③基于当、前代的信息更新。粒子群优化算法具有并行处理特性，鲁棒性好，粒子只通过内部速度进行更新，因此原理更简单、参数更少、实现更容易[3]。但是，在算法运行过程中，粒子易陷入局部最优，会出现早熟收敛现象。此外，PSO算法聚类技术必须要提前指定所要得到的聚类数目，而在很多实际情况下，最佳的聚类数目是预先未知的。

聚类算法是基因分析中主要技术之一。聚类在事先不规定分类规则的情况下，将基因表达数据按照其自身特征划分为不同的类，它是一种无监督的学习方法。聚类结果要求不同类间数据相似性越小越好，而类内数据相似性越大越好。因此事先给出不同的分类规则，聚类效果和结果都会有一定影响。

应用图论的原理可以将基因聚类问题转化为对图的顶点着色问题。类内的基因数据拥有同一种颜色，类间的基因数据拥有不同颜色[4]。因此，基因聚类问题转化为图论中的顶点着色问题，聚类基因类的个数就是顶点着色的最少颜色数。在聚类的过程中，可能出现一个基因为一个类，这样的基因称为孤立点基因。

基于以上的介绍，笔者对PSO中的参数进行改进，优化了粒子群算法，避免粒子过早陷入局部最优，同时针对聚类数目情况，用图论中的顶点着色原理可以有效地克服聚类的数目，同时用改进的聚类算法作用于Alzheimer’s disease(AD)基因表达数据，从而识别出AD候选基因。

1 粒子群优化算法

1.1基本粒子群算法

(1)

式中，ω为惯性因子;c1,c2为学习因子;r1,r2为[0,1]上的随机数;pij为第i个粒子中自身最好位置的第j维坐标;gj为全局最好位置的第j维坐标。

由式(1)组成的PSO算法成为标准粒子群优化算法。另外可以通过给出粒子的速度和位置限定范围来限制粒子的移动，以达到对算法较好控制:

(2)

1.2惯性因子的改进

在算法的早期，通过提高惯性因子递减速度，可以加强算法的全局收敛性，且得PSO的惯性权值为凹函数策略优于线性函数策略，同时线性策略优于凸函数策略，而在凹函数中递减的指数函数性能最佳[5]。但是对于数据规模较大、维数较大的粒子群，如果搜索开始时过快降低惯性权值，使得在短时间内进入惯性权值比较小的状态，这样造成了局部搜索能力强而全局搜索能力弱的局面，容易早熟。因此笔者采用的惯性因子如下：

(3)

式中，t为迭代次数；T为总迭代次数。

1.3学习因子的改进

学习因子c1表示粒子的个体认知能力，学习因子c2表示粒子的社会认知能力。因此在搜索的前期，c1取较大值而c2取较小值，目的是让粒子多些向自己的最优pbest学习，向全局最优gbest学习少一些，这样使得粒子的全局搜索能力增强；而在后期刚好相反，c1取较小值而c2取较大值，使粒子向全局最优位置gbest的局部靠拢，局部搜索能力增强[6]。因此，笔者对c1,c2作如下调整：

(4)

2 顶点着色算法

给定图G=(V,E)的一个k染色，用Vi表示在G中染以第i色的顶点集合(i=1,2,…,k)，则每个Vi都是G的独立集。因此G的一个k染色对应V(G)的一个划分[V1,V2,…,Vk]，其中每个Vi是独立集。反之，若V(G)有这样一个划分[V1,V2,…,Vk]，其中每个Vi均是独立集(1≤i≤k)，则相应地得到G的一个k染色，称V(G)的这样一个划分为G的一个色划分，每个Vi称为色类(i=1,2,…,k)。因此G的色数χ(G)就是使这种划分成为可能的最小自然数k。

如果一个图G表示聚类效果图时，通常利用图的邻接矩阵来描述它的结构。下面给出如下定义：

设图G的顶点集V(G)=(v1,v2,…,vn)，若vi与vj不同类时，则aij=1,反之若vi与vj同类时，则aij=0若则称元素aij(i,j=1,2,…,n)构成的n阶矩阵为图的邻接矩阵(adjacent matrix)。特殊地，若邻接矩阵中某一行元素只有一个0其他都为1时，则表示该行对应的顶点与其他顶点都不属于一类，即自己属于一类，这样的点称之为孤立点。

3 聚类算法设计

3.1适应度函数的选取

基于粒子群优化算法的顶点着色算法是在使用一种距离作为相似性度量的基础上，将数据集合划分为指定的M类，使得聚类划分总体类间差异(Total Within-cluster Variation, TWCV)最小化[7]。设{X1,X2,…,XN}为数据集合，xnd代表数据Xn的第d维属性(n=1,2,…，N)。若用Gm代表第m个类，Zm代表Gm中的元素个数，则类Gm的聚类中心Cm=(cm1,cm2,…,cmD)可以表示为：

(5)

由此第m类的类间差异(Within-cluster Variation, WCV)可表示为：

(6)

式中,d(xnj,cmj)表示xnj到该点质心cmj的一种距离。TWCV可表示为：

(7)

3.2顶点着色操作

根据邻接矩阵定义，得到顶点隶属关系。从顶点度数最小的顶点开始染色，找到不与其相邻的顶点并选择一个顶点进行染色，再找不与这2个顶点相邻的顶点集合中选择一个染色，如此下去，将所有顶点染色为止，程序结束[4]。

设{x1,x2,…,xN}为N个数据的集合，xnd代表数据xn的第d维属性(n=1,2,…，N)，定义邻接矩阵中的aij表示xi和xj的邻接关系，且:

(8)

式中,dij为xi和xj之间的欧式距离;δ为给定的一个值。

aij=1表示xi和xj属于不同的类，aij=0表示xi和xj属于同一类。

3.3聚类算法

基于PSO的顶点着色聚类首先定义聚类划分解的编码规则，解群体在随机初始化后随着迭代过程中进化，每一次进化，在当前代的粒子上进行PSO更新操作和顶点着色操作，产生新一代粒子群体，进化的过程一直持续到满足事先定义的终止条件。基于PSO算法的顶点着色聚类算法流程如下:

Step1(粒子编码) 在PSO聚类中，选择对聚类中心进行编码，即每个粒子由M个聚类中心向量表示为Xi=(Ci1,Ci2,…,Cij,…,CiM)，其中Cij表示第i个粒子的第j个聚类中心向量。每一个粒子代表了对当前数据的一种聚类划分，粒子数目和类的数目根据聚类问题的复杂度适当选取。

Step2(算法初始化) 在聚类的初始阶段，随机取出数据分配到M个类中，然后根据欧式距离得到每一类的数据，计算每一类的聚类中心，这样就得到了PSO算法的一个初始粒子，反复N次计算，得到了N个粒子的初始粒子群。计算每个粒子的个体最好位置pbest，并且设置pbest为粒子的初始位置，将具有最小的TWCV的pbest定义为算法的初始全局最好位置gbest。令P=0。

Step3若达到收敛条件则执行Step8，否则执行Step4。

Step4(粒子更新操作) 根据粒子群优化算法中采用式(3)、(4)给出的参数，由式(1)更新粒子速度和位置。

Step5(pbest和gbest的更新) PSO聚类的特点在于它的记忆性。整个粒子群的全局最好位置(gbest)和每个粒子的个体最好位置(pbest)在每次迭代后保存下来，用于下一次更新操作以指导新群体的产生。因此在PSO操作后和顶点着色操作后，每个粒子的pbest和整体gbest必须更新。

Step6产生一组gbest和聚类中心。

Step7P=P+1,转Step2。

Step8(顶点着色聚类)P组选取最佳聚类效果的粒子及其聚类中心点，给出每个类的分类阈值，由其对应的类中的数据距离建立邻接矩阵，根据顶点着色聚类算法，得到算法结果(笔者给出的分类阈值是该类间各顶点间距离平均值的3.5倍)。

4 算法试验与分析

4.1数据来源

数据是Alzheimer’s Disease(AD)基因数据，其来源于美国国家生物信息网[8]，该数据包含22283个基因，从正常、轻度、中度和重度4种状态下获取，为了进行基因表达数据进行运算，把所有的原始数据表示为矩阵的形式(如表 1)。表 1包含了22283行9列，每一行表示一个基因在9种不同的样本中获得的数据，每一列表示一个样本的22283个基因表达值，表 1的基因表达矩阵记为Mctrl。同样地可以得到轻度、中度和重度状态下的基因表达矩阵，分别记为Mincip、Mmoder和Msevere，这3个矩阵的行数均为22283，列数分别为7,8,7。

4.2算法参数设置

聚类实验中各聚类算法的参数设置如下：惯性因子最大值和最小值分别为2和0.5，速度最大值和最小值分别为0.5和-0.5，粒子群个数10组，每个粒子群由18个粒子组成，聚类中心点为75个，迭代次数100次。

表1 DNA microarray 数据组成结构

表2 识别候选基因表

表3 4种改进参数的聚类算法参数设置

注：PSO+VC、WPSO+VC、CPSO+VC、MPSO+VC为4种改进参数的顶点(VC)聚类算法。

4.3试验结果

聚类算法的试验环境为MATLAB 2010b， Intel Core 2 Quad Q8300 2.5GHz 4.00GB。识别AD候选基因的标准如下：当一个基因在正常状态下与其他基因聚为一类，但在其他3种生病状态与任何基因都不能聚为一类，这个基因成了孤立的；此外4种状态AD样本数据的采集是相互独立，因此孤立基因的出现只与疾病本身有关，而与外在条件无关，这样的孤立基因作为识别AD患者的候选基因。

利用基于粒子群优化的顶点着色聚类算法识别出了28个AD候选基因(表2)，其中SST和MOG证实与AD有关[9-10]；GABRA1作为突触成员之一，是调节G蛋白信号进行编码的基因，减少的GABRA1阻碍了AD脑的神经功能[9],其他某些基因可能潜在和AD有关的通路(不在笔者讨论范围内)。

4.4算法分析

选取表 1中前1000行数据，给出了4个参数更改(表3)的基于粒子群的顶点着色聚类效果比较。针对参数改进的4种算法，为了可比性，其他设置一致：给定10个相同的初始聚类中心点，产生18个种群，迭代次数50。

图 1中表示了1000个基因表达水平的4种聚类效果图，每个子图都包含了1000行9列的颜色子块，相邻两行间的颜色子块不同反映了2个基因表达水平差异性。差异性越小，表示聚类效果越佳。图1(d)的差异性最小，相邻行间的颜色整体性较强。为了刻画聚类效果，根据文献[7]给出的几种计算质点与质心的相关性函数，计算了以上4种聚类效果的适应度值(表4)。分析表 4中数据可知，改进的聚类算法适应度各个指标均优于其他3种聚类算法，说明改进后的聚类算法在对聚类效果有一定改进。

图1 4种改进参数的聚类算法treeview效果图

指标算法PSO+VCWPSO+VCCPSO+VCMPSO+VC类内欧式距离平均数倒数307.83301.63308.69403.37相关系数845.80839.16840.41853.62指数距离法872.87868.88870.36873.62直接距离欧式距离923.06920.66920.83927.50c=0.3契比雪夫距离973.44972.26971.09978.82海明距离725.13718.87723.32726.91最大最小法1036.031034.731034.081040.57算术平均最小法1047.351046.201045.381052.09几何平均最小法2094.952092.652091.002104.48

注：表中数据表示该算法中各质点与其质心的相关性之和，数据越大，表示该算法中质点间越集中，聚类效果优。

5 结 语

提出了一种基于粒子群优化的顶点着色聚类算法，在标准粒子群的基础上，根据3个参数选取对聚类效果的影响，修改了这3个的参数值，并且利用该算法识别出阿尔兹海默病(AD)候选基因。试验结果表明，该算法提高了聚类效果，以及识别出的某些候选基因具有一定的合理性。但笔者的研究是直接给出了顶点着色聚类的阈值，没有分析阈值的改变而影响聚类效果和试验结果，今后将继续研究阈值的最佳选取，以提高聚类效果。

[1]纪震，廖惠连，吴青华.粒子群算法及应用[M].北京: 科学出版社,2009.

[2] 高尚，杨静宇.群智能算法及其应用[M].北京: 中国水利水电出版社,2006.

[3] 闻朝中，李智.粒子群算法在配电网络无功补偿优化中的应用[J].武汉工业学院学报, 2004,23(1): 18-21.

[4] 王海英，黄强，李传涛,等.图论算法及其MATLAB实现[M].北京: 北京航空航天大学出版社, 2010.

[5] 陈贵敏，贾建援，韩琪.粒子群优化算法的惯性权值递减策略研究[J].西安交通大学学报, 2006,40(1): 53-56.

[6] 徐生兵，夏文杰，代安定.一种改进学习因子的粒子群算法[J].信息安全, 2012,(7):17-19.

[7] 曲福恒，崔广才，李岩芳,等.模糊聚类算法及应用[ ].北京: 国防工业出版社, 2011.

[8] NCBI, A D gene expression level.2007.URL: http://www.ncbi.nlm.nih.gov/geoprofiles/.

[9] Burgos-Ramos E,et al.Somatostatin and Alzheimer’s disease[J].Molecular and cellular endocrinology, 2008,286(1): 104-111.

[10]Frenkel D,et al.Nasal vaccination with a proteosome-based adjuvant and glatiramer acetate clears β-amyloid in a mouse model of Alzheimer disease[J].Journal of Clinical Investigation, 2005,115(9): 2423-2433.

TP311.1

A

1673-1409(2013)31-0061-05

[编辑] 洪云飞