范方云, 孫俊

(江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院,江蘇無錫214122)

基于BQPSO算法的癌癥特征基因選擇與分類

范方云, 孫俊*

(江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院,江蘇無錫214122)

提出了基于二進(jìn)制編碼的量子行為粒子群優(yōu)化算法(BQPSO)的癌癥特征基因選擇方法,利用BQPSO對(duì)樣本數(shù)據(jù)進(jìn)行特征選擇。使用選出的特征基因訓(xùn)練支持向量機(jī)進(jìn)行留一法交叉驗(yàn)證。實(shí)驗(yàn)結(jié)果表明,基于BQPSO算法的癌癥特征基因選擇方法是一種行之有效的方法。

微陣列數(shù)據(jù);特征基因;二進(jìn)制編碼的量子行為粒子群優(yōu)化算法;支持向量機(jī);留一法交叉驗(yàn)證

現(xiàn)代社會(huì),癌癥已經(jīng)成為威脅人類生命的重要因素之一。漏診和誤診使很多患者錯(cuò)過了最佳治療時(shí)機(jī)。因此,人們迫切需要更多可靠的輔助方法,結(jié)合醫(yī)療診斷,最大限度地提高癌癥診斷的正確率。隨著信息科學(xué)和分子生物科學(xué)的飛速發(fā)展,基因芯片技術(shù)因其微型化,高通量等特點(diǎn)為人們提供了大量的微陣列DNA表達(dá)數(shù)據(jù),被廣泛應(yīng)用于癌癥診斷、臨床檢驗(yàn)等方面。然而,DNA微陣列數(shù)據(jù)維度高,樣本量很少,且分布不均勻。過多的分類特征不一定能夠得到較好的分類結(jié)果,而且增加了計(jì)算復(fù)雜度。為此,在利用DNA微陣列表達(dá)數(shù)據(jù)進(jìn)行癌癥分類之前必須進(jìn)行特征選擇,選擇出對(duì)分類有積極作用的特征基因。

目前常用的特征選擇方法可以從兩方面進(jìn)行分類[1],即評(píng)價(jià)準(zhǔn)則和搜索策略。在基于評(píng)價(jià)準(zhǔn)則劃分的特征選擇方法中,又可根據(jù)特征選擇是否獨(dú)立于后續(xù)的學(xué)習(xí)算法分為過濾式(Filter)和封裝式(W rapper)兩種。Filter與后續(xù)學(xué)習(xí)算法無關(guān),而W rapper利用后續(xù)學(xué)習(xí)算法的訓(xùn)練準(zhǔn)確率評(píng)估特征子集。在基于搜索策略劃分特征選擇方法時(shí),按照特征子集的形成過程,可分為全局搜索,隨機(jī)搜索和啟發(fā)式搜索3種。一個(gè)具體的搜索算法會(huì)采用兩種或多種基本搜索策略[2-4]。張靖等[5]利用信噪比指標(biāo)過濾無關(guān)基因,再采用迭代Lasso方法進(jìn)行冗余基因的剔除,結(jié)合SVM分類器在數(shù)據(jù)集Leukemia,Prostate,colon上分別獲得了98.61%, 96.08%,90.32%的分類正確率。張煥萍等[6]提出了離散粒子群和支持向量機(jī)封裝模式的BPSO-SVM特征基因選擇方法,在數(shù)據(jù)集colon上用34個(gè)特征基因子集獲得了89.67%的平均正確率。目前結(jié)合多種特征選擇方法雖比單獨(dú)使用有一定改善,但存在的問題依然很明顯,如第二階段的纏繞過程如何在特征子集規(guī)模、所選特征的分類能力和其他約束條件等多個(gè)目標(biāo)下求得最優(yōu)解。

文中提出的基于BQPSO的癌癥特征基因選擇方法屬于全局搜索和啟發(fā)式搜索的結(jié)合,依靠改變BQPSO的初始搜索空間的大小和BQPSO的強(qiáng)搜索能力,本方法在分類正確率上獲得了較大的提高,同時(shí)也得到了規(guī)模更小的特征子集。

1 二進(jìn)制編碼的量子行為粒子群優(yōu)化算法

1.1 粒子群優(yōu)化算法

粒子群優(yōu)化算法(Particle Swarm Optimization, PSO)[7]是在1995年由Kennedy和Eberhart提出的基于群體智能理論的優(yōu)化算法,它模擬了鳥群的覓食過程,通過個(gè)體間的合作與競(jìng)爭(zhēng)產(chǎn)生的群體智能指導(dǎo)優(yōu)化搜索。PSO算法首先初始化一組隨機(jī)解,通過迭代搜尋最優(yōu)值。每個(gè)優(yōu)化問題的解視為搜索空間的一只鳥,稱為“粒子”。所有的粒子對(duì)應(yīng)一個(gè)優(yōu)化問題的適應(yīng)值,粒子的速度決定其飛行的方向和距離,粒子通過追尋群體中的最優(yōu)粒子來完成在解空間的搜索。

1.2 量子行為粒子群優(yōu)化算法

在PSO算法的基礎(chǔ)上,Efron B等[8]從量子力學(xué)的角度出發(fā),提出了一種新的PSO算法模型,即量子行為粒子群優(yōu)化算法(Quantum-Bahaved Particle Swarm Optimization,QPSO)。QPSO的量子模型,參考量子物理學(xué),將粒子的運(yùn)動(dòng)狀態(tài)用波動(dòng)函數(shù)表示。同時(shí),在QPSO算法的模型中,利用波動(dòng)函數(shù)φ給定的概率密度函數(shù)確定粒子在某個(gè)時(shí)刻某個(gè)位置出現(xiàn)的概率。

1.3 二進(jìn)制編碼的量子行為粒子群優(yōu)化算法

其中,dH(·)是計(jì)算Hamming距離的函數(shù),它的值為兩個(gè)位串對(duì)應(yīng)位的不同值的總個(gè)數(shù)。

與文獻(xiàn)[9]中式(2)不同,在BQPSO中,平均最優(yōu)位置mbest的每個(gè)二進(jìn)制位由群體中每個(gè)粒子最優(yōu)個(gè)體pbesti對(duì)應(yīng)的二進(jìn)制位上0,1出現(xiàn)的情況決定。具體為:統(tǒng)計(jì)所有粒子pbesti二進(jìn)制串每一位上0,1出現(xiàn)的次數(shù)。如果出現(xiàn)0的次數(shù)多,則mbest對(duì)應(yīng)位為0;反之,則為1。若0,1出現(xiàn)的次數(shù)相同,mbest對(duì)應(yīng)位隨機(jī)出現(xiàn)0或者1。將獲得mbest的函數(shù)記為

輸入為粒子最優(yōu)個(gè)體pbest;輸出為平均最優(yōu)位置mbest。

在BQPSO算法中,父代粒子最優(yōu)個(gè)體pbesti和群體最優(yōu)個(gè)體gbest隨機(jī)交叉產(chǎn)生粒子的局部吸引子,即Pi。Pi值的函數(shù)表示為

而粒子的新位置Xid由Pid變異而來。變異的概率為

式中:ld為粒子第d維的長(zhǎng)度;

其中,β為BQPSO算法的系數(shù)。由于Hamming距離為整數(shù),對(duì)b值[·]取整再使用[7]。計(jì)算Xid的函數(shù)表示為

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

1)用二進(jìn)制位串的形式初始化群體中的每個(gè)粒子Xi,并使得pbesti=Xi;

2)根據(jù)方程mbest=Get_mbest(pbest)計(jì)算群體平均最優(yōu)位置mbest的值;

3)根據(jù)適應(yīng)度函數(shù)值(例如最大化問題)計(jì)算群體中每一個(gè)粒子的適應(yīng)值,并與前次的粒子最優(yōu)值比較,如果f(Xi)?f(pbesti),則pbesti=Xi;反之,則不更新;

4)計(jì)算群體中全局最優(yōu)粒子pbestg,并與前次的全局最優(yōu)值gbest比較,f(pbestg)＞f(gbest),則gbest= pbestg;反之,則不更新;

5)根據(jù)方程Pi=Get_P(pbesti,gbest),計(jì)算局部吸引子Pi的值;

計(jì)算pr的值;

7)根據(jù)方程Xid=Transf(Pid,pr)計(jì)算Xid的值,并連接生成X;

8)重復(fù)2)～7),直到滿足算法結(jié)束條件。

2 實(shí)驗(yàn)設(shè)計(jì)

2.1 數(shù)據(jù)集

實(shí)驗(yàn)采用BRB-ArrayTools[10]主頁上公開的3個(gè)DNA微陣列基因表達(dá)譜數(shù)據(jù)集,分別為急性白血病數(shù)據(jù)集Leukemia,前列腺癌數(shù)據(jù)集Prostate和結(jié)腸癌數(shù)據(jù)集Colon。這3個(gè)數(shù)據(jù)集均可以從如下的地址下載:http://linus.nci.nih.gov/～brb/DataArchive_ New.htm l

數(shù)據(jù)集中每個(gè)樣本一定屬于兩類中的一種,根據(jù)SVM分類器的要求,分別將兩類標(biāo)識(shí)為0和1。每個(gè)數(shù)據(jù)集情況見表1。

表1 實(shí)驗(yàn)數(shù)據(jù)集描述Tab.1 Description of experim ental datasets

2.2 預(yù)處理

首先,對(duì)數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理,消除量綱對(duì)分類的影響,再對(duì)所有的特征進(jìn)行T檢驗(yàn)。取P值較小的前d個(gè)特征進(jìn)行初步篩選,結(jié)果作為BQPSO算法的全局搜索空間。文中分別對(duì)d=20,30,40,50進(jìn)行實(shí)驗(yàn)比較,為不同的數(shù)據(jù)集找出合適的d值。因?yàn)樵贐QPSO算法中,初始特征的個(gè)數(shù)就是粒子的二進(jìn)制編碼長(zhǎng)度,若不用T檢驗(yàn)進(jìn)行初步篩選,粒子的二進(jìn)制串長(zhǎng)度會(huì)有幾千甚至上萬,這樣不僅增加了計(jì)算復(fù)雜度,而且影響B(tài)QPSO的搜索效果。因?yàn)槌跏嫉乃阉骺臻g越大,BQPSO最終選擇出的特征基因越多。所以,在保證較好的分類效果的同時(shí),為每個(gè)數(shù)據(jù)集選擇出盡量小的d值,以選擇出最少的特征基因,同時(shí)具有較高的分類正確率。

2.3 BQPSO算法選擇特征基因

用BQPSO算法對(duì)這d個(gè)基因進(jìn)行第二次篩選,提取出真正具有分類信息的基因。根據(jù)數(shù)據(jù)集樣本數(shù)量較少的特點(diǎn),為了得到可靠穩(wěn)定的分類模型,使用SVM分類器進(jìn)行留一交叉驗(yàn)證(Leave-One-Out Cross-Validation,LOOCV)。采用數(shù)據(jù)集的留一分類正確率作為BQPSO的適應(yīng)值,即f(·)等于SVM采用留一法分類數(shù)據(jù)集得到的分類正確率。若一個(gè)數(shù)據(jù)集有n個(gè)樣本,留一交叉驗(yàn)證是指只使用所有樣本中的一個(gè)作為預(yù)測(cè)集,剩下n-1個(gè)樣本作為訓(xùn)練集,訓(xùn)練SVM并預(yù)測(cè)。重復(fù),直到所有的樣本都被當(dāng)做一次預(yù)測(cè)集。留一分類正確率就是這n次分類正確率的均值。

實(shí)驗(yàn)設(shè)計(jì)群體共有20個(gè)粒子,每個(gè)粒子只有1個(gè)決策變量,即粒子的維數(shù)為1。每個(gè)粒子的長(zhǎng)度為d(d=20,30,40,50),即每個(gè)粒子用長(zhǎng)度為d的0,1串表示,1代表選中該特征,0代表沒有選中。初始時(shí),隨機(jī)產(chǎn)生20個(gè)長(zhǎng)度為d的0,1串Xi(i=1,2,…, 20),且設(shè)初始粒子最優(yōu)位置

用函數(shù) mbest=Get_mbest(pbest)

計(jì)算群體平均最優(yōu)位置mbest。根據(jù)每個(gè)粒子適應(yīng)值是否增大維護(hù)粒子最優(yōu)位置pbesti,即如果本次迭代中f(Xi)＞f(pbesti),則更新pbesti=Xi,否則不更新。根據(jù)所有的pbesti更新全局最優(yōu)位置gbest。

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

計(jì)算局部吸引子。根據(jù)

計(jì)算的概率,在局部吸引子上進(jìn)行變異,得到新的粒子種群。其中l(wèi)為粒子二進(jìn)制表示的長(zhǎng)度,即l= d。將以上過程重復(fù)進(jìn)行200代,或者當(dāng)f(gbest)＞99.99%時(shí)退出迭代。

3 結(jié)果分析

對(duì)每個(gè)數(shù)據(jù)集,取d為20,30,40,50分別進(jìn)行實(shí)驗(yàn),每個(gè)實(shí)驗(yàn)重復(fù)50次,記錄這50個(gè)LOOCV分類正確率的最高值和平均值。得到如圖1所示的不同d值時(shí)的最高和平均分類正確率。

由圖1可以看出,在分類不同的數(shù)據(jù)集時(shí),得到最優(yōu)結(jié)果時(shí)的d值不盡相同。數(shù)據(jù)集Leukemia中,當(dāng)d為40時(shí),數(shù)據(jù)集Prostate中,當(dāng)d為50時(shí),數(shù)據(jù)集Colon中,當(dāng)d為20時(shí),平均正確率和最好正確率都可達(dá)到最優(yōu)。

表2給出了3個(gè)數(shù)據(jù)集在最優(yōu)d值下經(jīng)過BQPSO進(jìn)一步篩選后提取的基因數(shù)和正確率。這里的基因個(gè)數(shù)是50次實(shí)驗(yàn)結(jié)果的平均值。最高、平均正確率同樣來自這50次實(shí)驗(yàn)。

將實(shí)驗(yàn)結(jié)果與其他方法相比較,具體結(jié)果見表3。

圖1 不同d值時(shí)的最高和平均分類正確率Fig.1 Best and the average classification accuracy w ith different d

表2 BQPSO特征選擇實(shí)驗(yàn)結(jié)果Tab.2 Experimental results of gene selection based on BQPSO

表3 不同方法實(shí)驗(yàn)結(jié)果分類正確率的比較Tab.3 Com parison of experiment results from differentmethods 單位:%

由表3可知,對(duì)于數(shù)據(jù)集Leukemia,文中提出的BQPSO+SVM方法得到的LOOCV分類正確率,與GA+SVM方法一樣都能達(dá)到100%,且優(yōu)于迭代Lasso+SVM方法的98.61%;對(duì)于Prostate數(shù)據(jù)集,文中得到的最高和平均分類正確率均高于迭代Lasso+SVM方法得到的96.08%的正確率;對(duì)于colon數(shù)據(jù)集,文中得到的LOOCV正確率與GA+ SVM方法相同,高于迭代Lasso+SVM得到的90.32%,也高于BPSO+SVM得到的最高正確率。

由上述分析可知,文中提出的基于BQPSO的癌癥特征基因選擇方法在特征選擇效果上具有明顯的優(yōu)勢(shì)。

4 結(jié) 語

提出了基于BQPSO的用于高維微陣列數(shù)據(jù)的特征基因選擇與分類方法。并且將實(shí)驗(yàn)結(jié)果與迭代Lasso+SVM、BPSO+SVM和GA+SVM相比較。T檢驗(yàn)結(jié)合BQPSO+SVM的方法從微陣列數(shù)據(jù)成千上萬的基因中選擇出了10～20個(gè)最具分類信息的基因,并且得到了較高的分類正確率。由此可知,基于BQPSO算法的微陣列數(shù)據(jù)特征基因選擇與分類方法是一種行之有效的方法。

[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]劉金勇,鄭恩輝,陸慧娟.基于聚類和微粒群優(yōu)化的基因選擇方法[J].數(shù)據(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方法的結(jié)腸癌基因表達(dá)譜數(shù)據(jù)分析[J].青島科技大學(xué)學(xué)報(bào):自然科學(xué)版,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]徐久成,徐天賀,孫林,等.基于鄰域粗糙集和粒子群優(yōu)化的腫瘤分類特征基因選取[J].小型微型計(jì)算機(jī)系統(tǒng),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]張靖,胡學(xué)鋼,李培培,等.基于迭代Lasso的腫瘤分類信息基因選擇方法研究[J].模式識(shí)別與人工智能,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ī)的特征基因選擇算法[J].計(jì)算機(jī)與應(yīng)用化學(xué),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]孫俊,方偉,吳小俊,等.量子行為粒子群優(yōu)化:原理及其應(yīng)用[M].北京:清華大學(xué)出版社,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ìn)制編碼的量子粒子群優(yōu)化算法[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.

(責(zé)任編輯:邢寶妹)

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—),男,江蘇無錫人,副教授,碩士生導(dǎo)師。主要從事智能計(jì)算、圖像處理與模式識(shí)別等研究。Email:sunjun_wx@hotmail.com

TP 181

A

1671-7147(2015)01-0011-05

book=15,ebook=18

2014-08-15;

2014-10-16。

國(guó)家自然科學(xué)基金項(xiàng)目(61170119)。

范方云(1989—),女,江蘇揚(yáng)州人,計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)碩士研究生。