杜洪波，董文娟

(沈陽(yáng)工業(yè)大學(xué) 理學(xué)院，遼寧 沈陽(yáng) 110870)

?

Relief-PSO混合算法在基因微陣列特征選擇中的應(yīng)用

杜洪波，董文娟

(沈陽(yáng)工業(yè)大學(xué) 理學(xué)院，遼寧 沈陽(yáng) 110870)

在處理高維小樣本、高冗余、高噪聲的基因微陣列數(shù)據(jù)時(shí)，無(wú)法采用傳統(tǒng)特征選擇方法進(jìn)行分析。針對(duì)該問(wèn)題提出了一種結(jié)合Relief和粒子群優(yōu)化算法(Relief-PSO)的混合特征選擇方法。首先采用Relief預(yù)選濾除部分特征，然后以SVM-PSO封裝算法選擇出最優(yōu)特征子集，采用典型的小樣本高維公共微陣列數(shù)據(jù)測(cè)試算法。結(jié)果表明，總體分類(lèi)精度不低于85%，與SVMRFE，SVMDEA特征選擇算法進(jìn)行了比較，基于Relief和PSO的混合特征選擇算法精度較高，能夠有效應(yīng)用于基因微陣列數(shù)據(jù)的分析。

特征選擇；Relief；PSO；基因微陣列

隨著人類(lèi)基因組測(cè)序計(jì)劃的階段性進(jìn)展陸續(xù)完成，生命科學(xué)研究逐步邁進(jìn)后基因組時(shí)代，以微陣列實(shí)驗(yàn)為代表的高通量檢測(cè)技術(shù)日益興起[1]。

由于DNA微陣列實(shí)驗(yàn)的成本高、實(shí)驗(yàn)次數(shù)少，以致基因表達(dá)譜數(shù)據(jù)呈現(xiàn)小樣本特性；同時(shí)，實(shí)驗(yàn)測(cè)試表達(dá)的基因數(shù)量驚人，導(dǎo)致了基因表達(dá)譜數(shù)據(jù)呈現(xiàn)高維特性。在這種數(shù)據(jù)的高維小樣本問(wèn)題中，樣本特征維數(shù)遠(yuǎn)遠(yuǎn)高于樣本個(gè)數(shù)，傳統(tǒng)的機(jī)器學(xué)習(xí)算法難以擔(dān)負(fù)，給基因分析帶來(lái)了極大的挑戰(zhàn)[2-4]。

維數(shù)約簡(jiǎn)是處理該問(wèn)題的主要途徑，其包括特征抽取(FeatureExtraction)和特征選擇(FeatureSelection)2種方式，前者是通過(guò)組合變化構(gòu)造新的低維特征空間，后者是采用特定的評(píng)估標(biāo)準(zhǔn)選擇最優(yōu)特征子集，從而達(dá)到降維的目的[5]。相比而言，特征選擇具有不改變?cè)继卣骺臻g、計(jì)算復(fù)雜度低、更為精確、易于理解等特點(diǎn)，適用于大規(guī)模數(shù)據(jù)處理。

通過(guò)判斷是否有分類(lèi)器的參與，可以將特征選擇分為3大類(lèi)：過(guò)濾式(Filter)、纏繞式(Wrapper)、嵌入式，前兩種方法最為常用，區(qū)別在于學(xué)習(xí)過(guò)程是否獨(dú)立[6-9]。Filter方法時(shí)間效率高，但正是由于其分別考量單個(gè)特征的特點(diǎn)，導(dǎo)致特征間存在的相關(guān)性被忽視，可能產(chǎn)生的分類(lèi)模型與真實(shí)結(jié)果有較大偏差；相應(yīng)的，Wrapper方法復(fù)雜度高，在速度上較慢，但選擇出的規(guī)模較小的優(yōu)化特征子集有利于關(guān)鍵特征的辨識(shí)。

Filter類(lèi)典型特征選擇算法包括Focus算法和Relief算法，后者具有效率高、不限制數(shù)據(jù)類(lèi)型等優(yōu)點(diǎn)，應(yīng)用最為廣泛。Wrapper類(lèi)特征選擇包括分類(lèi)器和搜索算法兩個(gè)組成部分，分類(lèi)器中SVM廣泛應(yīng)用于wrapper特征選擇，具有小樣本學(xué)習(xí)、抗噪聲性能強(qiáng)、學(xué)習(xí)效率高、推廣性好等優(yōu)點(diǎn)；搜索算法中粒子群優(yōu)化算法(PSO)可以同SVM進(jìn)行封裝，具有卓越的全局搜索優(yōu)化能力[10-11]。綜上所述，采用Relief-PSO混合算法對(duì)基因微陣列特征選擇問(wèn)題進(jìn)行研究與計(jì)算，首先利用Relief作為預(yù)選濾除部分特征，然后采用PSO進(jìn)行搜索，SVM作為評(píng)估函數(shù)選擇最優(yōu)特征子集。

1　特征選擇算法

Relief算法根據(jù)特征評(píng)估近距離樣本的區(qū)分能力特征，即認(rèn)為特征好的樣本距離接近，特征差異大的樣本距離疏遠(yuǎn)。其計(jì)算公式如下：

(1)

其中，H(x)為與樣本x同類(lèi)的最近相鄰樣本點(diǎn)；M(x)為與樣本x異類(lèi)的最近相鄰樣本點(diǎn)。

PSO算法模擬鳥(niǎo)群覓食行為，是一種基于群體協(xié)作的隨機(jī)搜索算法，初始化隨機(jī)粒子，每次迭代過(guò)程中粒子根據(jù)飛行經(jīng)驗(yàn)調(diào)整速度向最優(yōu)位置飛行，粒子速度與位置更新公式如下：

vij(t+1)=w·vij(t)+c1rand()·(pij(t)-

xij(t))+c2rand()·(pgj(t)-xij(t))

(2)

xij(t+1)=xij(t)+vij(t+1)

(3)

其中，t為迭代數(shù)；w為慣性權(quán)重；rand()為隨機(jī)數(shù)，取值0～1之間；Pi為局部最優(yōu)值，代表粒子i在搜索空間中所經(jīng)過(guò)的最佳位置；Pg為全局最優(yōu)值，代表整個(gè)粒子群在搜索空間中所經(jīng)過(guò)的最佳位置；c1和c2為加速系數(shù)。

SVM算法通過(guò)非線(xiàn)性變換把輸入樣本映射到高維空間，尋找低VC維的最優(yōu)分類(lèi)超平面，將原約束問(wèn)題轉(zhuǎn)化為凸二次規(guī)劃對(duì)偶表達(dá)式如下：

(4)

對(duì)不等式約束的二次函數(shù)求極值，有全局最優(yōu)的唯一解，滿(mǎn)足：

(5)

在式(5)的所有解中，非零樣本為支持向量，通過(guò)線(xiàn)性組合的方式得到最有分類(lèi)平面的權(quán)系數(shù)向量，分類(lèi)閥值b*由式(4)中的約束條件解得，由此可得最優(yōu)分類(lèi)函數(shù)為

(6)

其中，sgn()為符號(hào)函數(shù)。

K(xi,xj)=<φ(xi)·(xj)>

(7)

封裝算法中核函數(shù)采用的是徑向基函數(shù)RBF，如下式所示：

(8)

通過(guò)尋優(yōu)的方式調(diào)整容錯(cuò)懲罰系數(shù)C和內(nèi)核參數(shù)γ從而影響分類(lèi)精度。

為克服Relief算法不能去除冗余特征的缺點(diǎn)，采用了串聯(lián)式組合特征選擇算法Relief-PSO，該方法為兩階段特征選擇算法：第一階段，采用Relief得到特征權(quán)值，濾掉權(quán)值小于閾值的特征得到特征子集；第二階段，以分類(lèi)器準(zhǔn)確率為特征子集的評(píng)估標(biāo)準(zhǔn)，采用PSO算法逐步去除冗余特征，尋找最優(yōu)特征子集，算法流程如圖1所示。

首先利用Relief算法對(duì)提取的特征進(jìn)行篩選，保留了與目標(biāo)類(lèi)相關(guān)性較大的特征，然后利用PSO_SVM封裝算法對(duì)特征子集和SVM核參數(shù)進(jìn)行同步優(yōu)化。Relief算法和PSO_SVM封裝算法分別通過(guò)Weka軟件和Matlab語(yǔ)言平臺(tái)實(shí)現(xiàn)，最終得到最優(yōu)容錯(cuò)懲罰系數(shù)C和內(nèi)核參數(shù)γ分別為200和0.03。

圖1　算法流程

設(shè)PSO種群規(guī)模為N，既包含N個(gè)粒子，每個(gè)粒子的搜索空間為D，即粒子為D維向量，由樣本維數(shù)決定，維數(shù)即數(shù)據(jù)集特征數(shù)，則基于PSO的基因選擇算法描述如下：

Step1：Filter操作進(jìn)行預(yù)選，剔除類(lèi)無(wú)關(guān)噪聲基因；

Step2：隨機(jī)產(chǎn)生N個(gè)長(zhǎng)度P的初始粒子群，粒子由候選基因子集組成，粒子群長(zhǎng)度由Step1中預(yù)選基因子集決定；

Step3：計(jì)算當(dāng)前粒子的使用度，支持SVM的交叉精度和選擇的基因子集大小作為粒子優(yōu)劣的參考標(biāo)準(zhǔn)；

Step4：更新局部個(gè)體最優(yōu)和全局最優(yōu)位置；

Step5：根據(jù)PSO算法更新每個(gè)粒子的位置；

Step6：產(chǎn)生新一代粒子群；

Step7：達(dá)到最大迭代數(shù)算法終止，否則跳到Step3。

2　實(shí)驗(yàn)數(shù)據(jù)

采用兩個(gè)典型的高維小樣本公共微陣列數(shù)據(jù)集來(lái)測(cè)試所提出特征選擇方法，分別為：

1)結(jié)腸癌數(shù)據(jù)集(Colon)

該數(shù)據(jù)集搜集了結(jié)腸活組織樣本中的表達(dá)值，數(shù)據(jù)集中包括62個(gè)結(jié)腸上皮細(xì)胞樣本，基因表達(dá)水平通過(guò)使用約6 000個(gè)高密度寡核苷酸陣列來(lái)測(cè)量。經(jīng)過(guò)測(cè)量表達(dá)水平的可信度選擇，保留了2 000 個(gè)基因在40例腺癌(Cancer)和22例正常組織(Normal)的樣本中的芯片表達(dá)數(shù)據(jù)集。

2)白血病數(shù)據(jù)集(Leukemia)

該數(shù)據(jù)集來(lái)自對(duì)兩類(lèi)急性白血病識(shí)別的芯片實(shí)驗(yàn)，基因表達(dá)水平為Aff.公司檢測(cè)，包括47例急性淋巴增生性白血病(acutemyeloidleukemia，ALL)和25例急勝髓性白血病(acutemyeloidleukemia，AML)樣本在7 129個(gè)基因中雜交結(jié)果。

實(shí)驗(yàn)所使用基因數(shù)據(jù)集由南洋理工大學(xué)的LiJ和LiuH收集，相關(guān)信息如表1所示。

表1　數(shù)據(jù)集相關(guān)信息

種群規(guī)模為50；最大迭代次數(shù)為200；結(jié)腸癌數(shù)據(jù)集w1=0.1，w2=0.2；白血病數(shù)據(jù)集w1=0.3，w2=0.4；粒子編碼形式采用“0”、“1”制，其中“0”對(duì)應(yīng)未被選擇基因，“1”對(duì)應(yīng)選擇基因，解碼過(guò)程中刪除“0”對(duì)應(yīng)基因，由“1”對(duì)應(yīng)基因構(gòu)成新的數(shù)據(jù)集，如結(jié)腸癌數(shù)據(jù)集有2 000個(gè)特征，則“0”、“1”編碼長(zhǎng)度為2 000。

3　結(jié)果與分析

首先利用Filter對(duì)基因表達(dá)譜數(shù)據(jù)的特征進(jìn)行預(yù)選，使得數(shù)據(jù)特征的相關(guān)性得到了很大的提升。利用PSO_SVM分類(lèi)器進(jìn)行檢驗(yàn)，可以完全對(duì)數(shù)據(jù)進(jìn)行有效分類(lèi)，在此過(guò)程中過(guò)濾法特征基因集包含分類(lèi)所需要的基因，并沒(méi)有去掉分類(lèi)所用的信息基因，分類(lèi)精度如表2所示。

表2　實(shí)驗(yàn)結(jié)果

同時(shí)，為了進(jìn)一步驗(yàn)證Relief-PSO特征選擇方法的適用性，分別采用了以F-sore作為評(píng)價(jià)準(zhǔn)則的Filter操作，與SVM-RFE、SVM-DEA方法進(jìn)行了分類(lèi)準(zhǔn)確度對(duì)比，通過(guò)對(duì)比準(zhǔn)確率來(lái)評(píng)價(jià)選擇方法的優(yōu)劣，對(duì)比結(jié)果如表3、圖2所示。

表3　分類(lèi)準(zhǔn)確率對(duì)比結(jié)果

從表3中可以看出，在準(zhǔn)確率(Acc.)方面，Relief-PSO在2個(gè)數(shù)據(jù)集上都要比SVM-RFE和SVM-DEA方法的分類(lèi)準(zhǔn)確率高，證明了所提出的混合特征選擇算法能夠解決基因微陣列特征選擇問(wèn)題，并取得更高的準(zhǔn)確率。

4　結(jié)　論

針對(duì)高維小樣本的基因微陣列特征選擇問(wèn)題，提出了一種混合Relief和PSO_SVM算法的混合特征選擇方法，給出了算法流程，并應(yīng)用在2個(gè)公共微陣列數(shù)據(jù)集上，對(duì)比結(jié)果表明，所提出的方法精度較高，能夠滿(mǎn)足基因微陣列特征選擇的要求。

圖2　分類(lèi)準(zhǔn)確率對(duì)比結(jié)果

[1]ZhangLJ,LiZJ.GeneSelectionforClassifyingMicroarrayDatausingGreyRelationAnalysis[C]//DiscoverScience2006.Barcelona,Spain：LNCS，2006,4265(1):378-382.

[2]ZhangLJ,LiZJ,ChenHW.AnEffectiveGeneSelectionMethodBasedonRelevanceAnalysisandDiscernibilityMatrix[C]//Pakdd2007.Nanjing,China：LNCS,4426:1088-1095.

[3]李瑤.基因芯片數(shù)據(jù)處理[M].北京：化學(xué)工業(yè)出版社，2006.

[4]CosminLazar,JonatanTaminau,StijinMeganck,etal.ASurveyonFilterTechniquesforFeatureSelectioninGeneExpressionMicroarrayAnalysis[J].IEEE,2012,9(4):11-19.

[5]InzaI,LarranagaP,BlancoR,etal.FilterversusgenewrapperapproachesinDNAmicroarraydomains[J].ArtificialIntelligenceinMedicine,2004,31(2):91-103.

[6]PodgorelecV,KokolP,StiglicB,etal.Decisiontrees:anoverviewandtheiruseinmedicine[J].JournalofMedicalSystems,2002,26(5):445-463.

[7]黃德雙.基因表達(dá)譜數(shù)據(jù)挖掘方法研究[M].北京：科學(xué)出版社，2009.

[8]萬(wàn)洪強(qiáng).應(yīng)用于基因選擇與癌癥分類(lèi)的微陣列數(shù)據(jù)分析[D].合肥：中國(guó)科技大學(xué),2010.

[9]李穎新,軟曉剛.基于支持向量機(jī)的癌癥分類(lèi)特征基因選取[J].計(jì)算機(jī)研究與發(fā)展,2005,42(10):324-330.

[10]ThomasJG,OlsonJM,TapscottSJ.AnEfficientandRebutStatisticalModelingApproachtoDiscoverDifferentiallyExpressedGenesUsingGenomicExpressionProfiles[J].GenomeResearch,2011,1(11)：1227-1236.

[11]陸慧娟.基于基因表達(dá)數(shù)據(jù)的癌癥分類(lèi)算法研究[D].徐州：中國(guó)礦業(yè)大學(xué),2012.

(責(zé)任編輯魏靜敏校對(duì)張凱)

ApplicationofReliefandPSOHybridAlgorithmforGeneMicroarrayFeatureSelection

DUHong-bo,DONGWen-juan

(SchoolofScience,ShenyangUniversityofTechnology,Shenyang110870,LiaoningProvince)

Thetraditionalfeatureselectionmethodisunfitforthedataanalysisofgenemicroarraywithhighdimensionalsmallsample,highredundancyandhighnoise.Inthispaper,ahybridfeatureselectionalgorithmwasputforwardwhichiscombinedReliefwithparticleswarmoptimizationalgorithm(Relief-PSO).Firstly,afewcharacteristicswerepre-filteredwithRelief,andthen,theoptimalfeaturessubsetwaschosenbySVM-PSOencapsulationalgorithm.Finally,thetypicalhigh-dimensionalsmallsamplepublicmicroarraydatawasutilizedtotestthealgorithm.Theresultsshowthattheoverallclassificationaccuracyisnotlessthan85%.ThehybridfeatureselectionalgorithmhasahighprecisioncomparedwithSVMRFE,SVMDEAcharacteristicsselectionalgorithm,anditcanbeappliedtothegenemicroarraydataanalysismoreeffectively.

featureselection;Relief;PSO;genemicroarray

2016-05-11

杜洪波(1977-)，男，吉林榆樹(shù)人，副教授，碩士生導(dǎo)師，研究方向?yàn)閿?shù)據(jù)挖掘、復(fù)雜網(wǎng)絡(luò)。

董文娟(1990-)，女，黑龍江黑河人，碩士研究生。

10.13888/j.cnki.jsie(ns).2016.03.016

TP391

A

1673-1603(2016)03-0267-05