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

杜洪波，董文娟

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

?

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

杜洪波，董文娟

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

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

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

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

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

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

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

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

1　特征選擇算法

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

(1)

其中，H(x)為與樣本x同類的最近相鄰樣本點；M(x)為與樣本x異類的最近相鄰樣本點。

PSO算法模擬鳥群覓食行為，是一種基于群體協(xié)作的隨機搜索算法，初始化隨機粒子，每次迭代過程中粒子根據(jù)飛行經(jīng)驗調(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()為隨機數(shù)，取值0～1之間；Pi為局部最優(yōu)值，代表粒子i在搜索空間中所經(jīng)過的最佳位置；Pg為全局最優(yōu)值，代表整個粒子群在搜索空間中所經(jīng)過的最佳位置；c1和c2為加速系數(shù)。

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

(4)

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

(5)

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

(6)

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

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

(7)

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

(8)

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

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

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

圖1　算法流程

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

Step1：Filter操作進行預(yù)選，剔除類無關(guān)噪聲基因；

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

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

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

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

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

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

2　實驗數(shù)據(jù)

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

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

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

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

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

實驗所使用基因數(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”對應(yīng)未被選擇基因，“1”對應(yīng)選擇基因，解碼過程中刪除“0”對應(yīng)基因，由“1”對應(yīng)基因構(gòu)成新的數(shù)據(jù)集，如結(jié)腸癌數(shù)據(jù)集有2 000個特征，則“0”、“1”編碼長度為2 000。

3　結(jié)果與分析

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

表2　實驗結(jié)果

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

表3　分類準確率對比結(jié)果

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

4　結(jié)　論

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

圖2　分類準確率對比結(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]黃德雙.基因表達譜數(shù)據(jù)挖掘方法研究[M].北京：科學(xué)出版社，2009.

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

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

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

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

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

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-)，男，吉林榆樹人，副教授，碩士生導(dǎo)師，研究方向為數(shù)據(jù)挖掘、復(fù)雜網(wǎng)絡(luò)。

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

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

TP391

A

1673-1603(2016)03-0267-05