范方云, 孙俊

(江南大学物联网工程学院,江苏无锡214122)

基于BQPSO算法的癌症特征基因选择与分类

范方云, 孙俊*

(江南大学物联网工程学院,江苏无锡214122)

提出了基于二进制编码的量子行为粒子群优化算法(BQPSO)的癌症特征基因选择方法,利用BQPSO对样本数据进行特征选择。使用选出的特征基因训练支持向量机进行留一法交叉验证。实验结果表明,基于BQPSO算法的癌症特征基因选择方法是一种行之有效的方法。

微阵列数据;特征基因;二进制编码的量子行为粒子群优化算法;支持向量机;留一法交叉验证

现代社会,癌症已经成为威胁人类生命的重要因素之一。漏诊和误诊使很多患者错过了最佳治疗时机。因此,人们迫切需要更多可靠的辅助方法,结合医疗诊断,最大限度地提高癌症诊断的正确率。随着信息科学和分子生物科学的飞速发展,基因芯片技术因其微型化,高通量等特点为人们提供了大量的微阵列DNA表达数据,被广泛应用于癌症诊断、临床检验等方面。然而,DNA微阵列数据维度高,样本量很少,且分布不均匀。过多的分类特征不一定能够得到较好的分类结果,而且增加了计算复杂度。为此,在利用DNA微阵列表达数据进行癌症分类之前必须进行特征选择,选择出对分类有积极作用的特征基因。

目前常用的特征选择方法可以从两方面进行分类[1],即评价准则和搜索策略。在基于评价准则划分的特征选择方法中,又可根据特征选择是否独立于后续的学习算法分为过滤式(Filter)和封装式(W rapper)两种。Filter与后续学习算法无关,而W rapper利用后续学习算法的训练准确率评估特征子集。在基于搜索策略划分特征选择方法时,按照特征子集的形成过程,可分为全局搜索,随机搜索和启发式搜索3种。一个具体的搜索算法会采用两种或多种基本搜索策略[2-4]。张靖等[5]利用信噪比指标过滤无关基因,再采用迭代Lasso方法进行冗余基因的剔除,结合SVM分类器在数据集Leukemia,Prostate,colon上分别获得了98.61%, 96.08%,90.32%的分类正确率。张焕萍等[6]提出了离散粒子群和支持向量机封装模式的BPSO-SVM特征基因选择方法,在数据集colon上用34个特征基因子集获得了89.67%的平均正确率。目前结合多种特征选择方法虽比单独使用有一定改善,但存在的问题依然很明显,如第二阶段的缠绕过程如何在特征子集规模、所选特征的分类能力和其他约束条件等多个目标下求得最优解。

文中提出的基于BQPSO的癌症特征基因选择方法属于全局搜索和启发式搜索的结合,依靠改变BQPSO的初始搜索空间的大小和BQPSO的强搜索能力,本方法在分类正确率上获得了较大的提高,同时也得到了规模更小的特征子集。

1 二进制编码的量子行为粒子群优化算法

1.1 粒子群优化算法

粒子群优化算法(Particle Swarm Optimization, PSO)[7]是在1995年由Kennedy和Eberhart提出的基于群体智能理论的优化算法,它模拟了鸟群的觅食过程,通过个体间的合作与竞争产生的群体智能指导优化搜索。PSO算法首先初始化一组随机解,通过迭代搜寻最优值。每个优化问题的解视为搜索空间的一只鸟,称为“粒子”。所有的粒子对应一个优化问题的适应值,粒子的速度决定其飞行的方向和距离,粒子通过追寻群体中的最优粒子来完成在解空间的搜索。

1.2 量子行为粒子群优化算法

在PSO算法的基础上,Efron B等[8]从量子力学的角度出发,提出了一种新的PSO算法模型,即量子行为粒子群优化算法(Quantum-Bahaved Particle Swarm Optimization,QPSO)。QPSO的量子模型,参考量子物理学,将粒子的运动状态用波动函数表示。同时,在QPSO算法的模型中,利用波动函数φ给定的概率密度函数确定粒子在某个时刻某个位置出现的概率。

1.3 二进制编码的量子行为粒子群优化算法

其中,dH(·)是计算Hamming距离的函数,它的值为两个位串对应位的不同值的总个数。

与文献[9]中式(2)不同,在BQPSO中,平均最优位置mbest的每个二进制位由群体中每个粒子最优个体pbesti对应的二进制位上0,1出现的情况决定。具体为:统计所有粒子pbesti二进制串每一位上0,1出现的次数。如果出现0的次数多,则mbest对应位为0;反之,则为1。若0,1出现的次数相同,mbest对应位随机出现0或者1。将获得mbest的函数记为

输入为粒子最优个体pbest;输出为平均最优位置mbest。

在BQPSO算法中,父代粒子最优个体pbesti和群体最优个体gbest随机交叉产生粒子的局部吸引子,即Pi。Pi值的函数表示为

而粒子的新位置Xid由Pid变异而来。变异的概率为

式中:ld为粒子第d维的长度;

其中,β为BQPSO算法的系数。由于Hamming距离为整数,对b值[·]取整再使用[7]。计算Xid的函数表示为

BQPSO算法的步骤[9]如下:

1)用二进制位串的形式初始化群体中的每个粒子Xi,并使得pbesti=Xi;

2)根据方程mbest=Get_mbest(pbest)计算群体平均最优位置mbest的值;

3)根据适应度函数值(例如最大化问题)计算群体中每一个粒子的适应值,并与前次的粒子最优值比较,如果f(Xi)≻f(pbesti),则pbesti=Xi;反之,则不更新;

4)计算群体中全局最优粒子pbestg,并与前次的全局最优值gbest比较,f(pbestg)＞f(gbest),则gbest= pbestg;反之,则不更新;

5)根据方程Pi=Get_P(pbesti,gbest),计算局部吸引子Pi的值;

计算pr的值;

7)根据方程Xid=Transf(Pid,pr)计算Xid的值,并连接生成X;

8)重复2)～7),直到满足算法结束条件。

2 实验设计

2.1 数据集

实验采用BRB-ArrayTools[10]主页上公开的3个DNA微阵列基因表达谱数据集,分别为急性白血病数据集Leukemia,前列腺癌数据集Prostate和结肠癌数据集Colon。这3个数据集均可以从如下的地址下载:http://linus.nci.nih.gov/～brb/DataArchive_ New.htm l

数据集中每个样本一定属于两类中的一种,根据SVM分类器的要求,分别将两类标识为0和1。每个数据集情况见表1。

表1 实验数据集描述Tab.1 Description of experim ental datasets

2.2 预处理

首先,对数据进行标准化处理,消除量纲对分类的影响,再对所有的特征进行T检验。取P值较小的前d个特征进行初步筛选,结果作为BQPSO算法的全局搜索空间。文中分别对d=20,30,40,50进行实验比较,为不同的数据集找出合适的d值。因为在BQPSO算法中,初始特征的个数就是粒子的二进制编码长度,若不用T检验进行初步筛选,粒子的二进制串长度会有几千甚至上万,这样不仅增加了计算复杂度,而且影响BQPSO的搜索效果。因为初始的搜索空间越大,BQPSO最终选择出的特征基因越多。所以,在保证较好的分类效果的同时,为每个数据集选择出尽量小的d值,以选择出最少的特征基因,同时具有较高的分类正确率。

2.3 BQPSO算法选择特征基因

用BQPSO算法对这d个基因进行第二次筛选,提取出真正具有分类信息的基因。根据数据集样本数量较少的特点,为了得到可靠稳定的分类模型,使用SVM分类器进行留一交叉验证(Leave-One-Out Cross-Validation,LOOCV)。采用数据集的留一分类正确率作为BQPSO的适应值,即f(·)等于SVM采用留一法分类数据集得到的分类正确率。若一个数据集有n个样本,留一交叉验证是指只使用所有样本中的一个作为预测集,剩下n-1个样本作为训练集,训练SVM并预测。重复,直到所有的样本都被当做一次预测集。留一分类正确率就是这n次分类正确率的均值。

实验设计群体共有20个粒子,每个粒子只有1个决策变量,即粒子的维数为1。每个粒子的长度为d(d=20,30,40,50),即每个粒子用长度为d的0,1串表示,1代表选中该特征,0代表没有选中。初始时,随机产生20个长度为d的0,1串Xi(i=1,2,…, 20),且设初始粒子最优位置

用函数 mbest=Get_mbest(pbest)

计算群体平均最优位置mbest。根据每个粒子适应值是否增大维护粒子最优位置pbesti,即如果本次迭代中f(Xi)＞f(pbesti),则更新pbesti=Xi,否则不更新。根据所有的pbesti更新全局最优位置gbest。

如果f(pbestg)＞f(gbest),更新gbest=pbestg。更新完pbesti和gbest之后,采用函数

计算局部吸引子。根据

计算的概率,在局部吸引子上进行变异,得到新的粒子种群。其中l为粒子二进制表示的长度,即l= d。将以上过程重复进行200代,或者当f(gbest)＞99.99%时退出迭代。

3 结果分析

对每个数据集,取d为20,30,40,50分别进行实验,每个实验重复50次,记录这50个LOOCV分类正确率的最高值和平均值。得到如图1所示的不同d值时的最高和平均分类正确率。

由图1可以看出,在分类不同的数据集时,得到最优结果时的d值不尽相同。数据集Leukemia中,当d为40时,数据集Prostate中,当d为50时,数据集Colon中,当d为20时,平均正确率和最好正确率都可达到最优。

表2给出了3个数据集在最优d值下经过BQPSO进一步筛选后提取的基因数和正确率。这里的基因个数是50次实验结果的平均值。最高、平均正确率同样来自这50次实验。

将实验结果与其他方法相比较,具体结果见表3。

图1 不同d值时的最高和平均分类正确率Fig.1 Best and the average classification accuracy w ith different d

表2 BQPSO特征选择实验结果Tab.2 Experimental results of gene selection based on BQPSO

表3 不同方法实验结果分类正确率的比较Tab.3 Com parison of experiment results from differentmethods 单位:%

由表3可知,对于数据集Leukemia,文中提出的BQPSO+SVM方法得到的LOOCV分类正确率,与GA+SVM方法一样都能达到100%,且优于迭代Lasso+SVM方法的98.61%;对于Prostate数据集,文中得到的最高和平均分类正确率均高于迭代Lasso+SVM方法得到的96.08%的正确率;对于colon数据集,文中得到的LOOCV正确率与GA+ SVM方法相同,高于迭代Lasso+SVM得到的90.32%,也高于BPSO+SVM得到的最高正确率。

由上述分析可知,文中提出的基于BQPSO的癌症特征基因选择方法在特征选择效果上具有明显的优势。

4 结 语

提出了基于BQPSO的用于高维微阵列数据的特征基因选择与分类方法。并且将实验结果与迭代Lasso+SVM、BPSO+SVM和GA+SVM相比较。T检验结合BQPSO+SVM的方法从微阵列数据成千上万的基因中选择出了10～20个最具分类信息的基因,并且得到了较高的分类正确率。由此可知,基于BQPSO算法的微阵列数据特征基因选择与分类方法是一种行之有效的方法。

[1]姚旭,王晓丹,张玉玺,等.特征选择方法综述[J].控制与决策,2012,27(2):161-166.

YAO Xu,WANG Xiaodan,ZHANG Yuxi,et al.Summary of feature selection algorithms[J].Control and Decision,2012,27(2): 161-166.(in Chinese)

[2]刘金勇,郑恩辉,陆慧娟.基于聚类和微粒群优化的基因选择方法[J].数据采集与处理,2014,29(1):83-89.

LIU Jinyong,ZHENG Enhui,LU Huijuan.Gene selection based on clusteringmethod and particle swarm optimization[J].Journal of Data Acquisition and Processing,2014,29(1):83-89.(in Chinese)

[3]于彬,张岩.基于GA-SVM方法的结肠癌基因表达谱数据分析[J].青岛科技大学学报:自然科学版,2013,33(6): 587-592.

YU Bin,ZHANG Yan.Analysis of colon cancer gene expression profiles based on GA-SVM method[J].Journal of Qingdao University of Science and Technology:Natutral Science Edition,2013,33(6):587-592.(in Chinese)

[4]徐久成,徐天贺,孙林,等.基于邻域粗糙集和粒子群优化的肿瘤分类特征基因选取[J].小型微型计算机系统,2014,35 (11):2528-2532.

XU Jiucheng,XU Tianhe,SUN Lin,et al.Feature celection for cancer classification based on neighborhood rough set and particle swarm optimization[J].Journal of Chinese Computer Systems,2014,35(11):2528-2532.

[5]张靖,胡学钢,李培培,等.基于迭代Lasso的肿瘤分类信息基因选择方法研究[J].模式识别与人工智能,2014,27(1): 49-59.

ZHANG Jing,HU Xuegang,LIPeipei,etal.Informative gene selection for tumor classification based on iterative lasso[J].Pattern Recognition and Artificial Intelligence,2014,27(1):49-59.(in Chinese)

[6]张焕萍,宋晓峰,王惠南.基于离散粒子群和支持向量机的特征基因选择算法[J].计算机与应用化学,2007,24(9): 1159-1162.

ZHANG Huanping,SONG Xiaofeng,WANG Huinan.Feature gene selection based on binary particle swarm optimization and support vectormachine[J].Computers and Applied Chemistry,2007,24(9):1159-1162.(in Chinese)

[7]孙俊,方伟,吴小俊,等.量子行为粒子群优化:原理及其应用[M].北京:清华大学出版社,2011.

[8]SUN Jun,FENG Bin,XUWenbo.Particle swarm optimization with particles having quantum behavior[C]//The 2004 Congress on Evolutionary Computation.Oregon:IEEE,2004:325-331.

[9]奚茂龙,孙俊,吴勇.一种二进制编码的量子粒子群优化算法[J].控制与决策,2010,25(1):99-104.

XIMaolong,SUN Jun,WU Yong.Quantum-behaved particle swarm optimization with binary encoding[J].Control and Decision, 2010,25(1):99-104.(in Chinese)

[10]Efron B,Hastie T,Johnstone I,et al.Least angle regression[J].The Annals of Statistics,2004,32(2):407-499.

[11]LIS,WU X,HU X.Gene selection using genetic algorithm and support vectorsmachines[J].Soft Computing,2008,12(7):693-698.

(责任编辑:邢宝妹)

Cancer Feature Gene Selection and Classification Based on BQPSO A lgorithm

FAN Fangyun, SUN Jun*
(School of Internet of Things Engineering,Jiangnan University,Wuxi214122,China)

In this paper,the cancer feature gene selectionmethod based on BQPSO(Quantum-Behaved Particle Swarm Optimization with Binary Encoding)is proposed where BQPSO algorithm is applied to select feature genes from example data and feature genes selected are used to train SVM classifiers and to make LOOCV(leave-one-out cross-validation).The experiment results show that the cancer feature selectionmethod based on the BQPSO algorithm is effective.

microarray data,feature gene,BQPSO,SVM,LOOCV

*通信作者:孙 俊(1971—),男,江苏无锡人,副教授,硕士生导师。主要从事智能计算、图像处理与模式识别等研究。Email:sunjun_wx@hotmail.com

TP 181

A

1671-7147(2015)01-0011-05

book=15,ebook=18

2014-08-15;

2014-10-16。

国家自然科学基金项目(61170119)。

范方云(1989—),女,江苏扬州人,计算机科学与技术专业硕士研究生。