基于支持向量機(jī)遞歸特征消除和特征聚類的致癌基因選擇方法

葉小泉,吳云峰

(廈門大學(xué)信息科學(xué)與技術(shù)學(xué)院，福建省智慧城市感知與計算重點實驗室，福建廈門361005)

癌癥通常緣于正常組織在物理或化學(xué)致癌物的作用下基因組發(fā)生突變，即基因表達(dá)水平的改變，使得許多生物過程失調(diào)[1]．而基因表達(dá)信息可以通過基因芯片技術(shù)測得，基因芯片(通常也稱為DNA微陣列或生物芯片)是附著于固體表面的微觀DNA斑點的集合．在分子生物學(xué)領(lǐng)域，根據(jù)核苷酸分子在形成雙鏈時遵循堿基互補(bǔ)原則，研究人員能夠使用基因芯片測量大量基因的表達(dá)水平信息，從而得到基因表達(dá)譜．因此，若利用這些基因表達(dá)譜數(shù)據(jù)確定出與癌癥有密切關(guān)系的基因，將對癌癥的診斷和治療發(fā)揮重要意義[2]．

由于存在與測定相關(guān)的成本問題，基因表達(dá)譜數(shù)據(jù)具有高維小樣本的特性．較高的維數(shù)是獲得問題準(zhǔn)確描述的有力保障，但它又難以避免地會引入大量冗余和與類別無關(guān)的噪聲信息，這給傳統(tǒng)的機(jī)器學(xué)習(xí)方法帶來了挑戰(zhàn)．因此，從成千上萬個基因中判斷出在不同疾病類別上具有差異性表達(dá)的少量致癌基因前，需要剔除掉大量無關(guān)基因，而特征選擇是一種有效的手段．

在利用基因表達(dá)譜數(shù)據(jù)進(jìn)行致癌基因選擇的問題上，Golub等[3]對急性白血病亞型識別和致病基因的判別進(jìn)行了研究，用信噪比(SNR)指標(biāo)來作為基因?qū)颖绢悇e的區(qū)分能力，其研究結(jié)果表明白血病亞型之間在基因表達(dá)上的差異可以通過一系列基因的表達(dá)水平檢測來進(jìn)行臨床診斷,并可以由此指導(dǎo)后續(xù)治療方案的制定．該方法運行速度較快，適用于高維數(shù)據(jù)，但由于其不能識別冗余基因，結(jié)果常常不盡人意．另外，Guyon等[4]將支持向量機(jī)(SVM)與遞歸特征消除(RFE)相結(jié)合提出了SVM-RFE算法，該方法通過SVM每個維度權(quán)重的絕對值來度量對應(yīng)特征的重要性，每次迭代刪除權(quán)重排名靠后的一個特征，取得了良好的效果．但是它每次迭代只刪除一個特征，在高維數(shù)據(jù)中仍耗時較長．因此Ding等[5]對它進(jìn)行了改進(jìn)，使得每次可以按比例刪除特征，提高了計算速度，但同時也發(fā)現(xiàn)所選的特征對每次迭代刪除的特征表現(xiàn)得十分敏感．此外Yousef等[6]提出了一種基于SVM的遞歸聚類特征消除(SVM-RCE)算法，該方法使用聚類方法對特征集進(jìn)行聚類，隨后利用SVM對各個特征類進(jìn)行評分，最后迭代刪除得分最低的那些特征類．此類遞歸聚類特征選擇算法能夠有效去除大量無關(guān)特征，但最后剩下的部分特征之間存在相似性較高、容易導(dǎo)致特征冗余的問題．因此，在特征排序和SVM-RFE算法的基礎(chǔ)上，本研究將二者結(jié)合并引入聚類算法，提出一種新的、適用于基因表達(dá)譜數(shù)據(jù)的特征選擇方法：K類別SVM-RFE(K-SVM-RFE)．

1 相關(guān)工作介紹

在具有高維小樣本特性的基因表達(dá)譜數(shù)據(jù)中，一個快速且有效獲得致癌基因的方法是對特征排序．因此，在K-SVM-RFE算法中，利用基于SNR的特征排序方法剔除大量無關(guān)基因，將剩余基因利用K均值算法聚成多個類別，并利用SVM-RFE算法精選致癌基因．

1.1 基于SNR的特征排序

SNR通常用來表示電子信號中信號與噪聲的比例，而在特征選擇中，可以用SNR指標(biāo)來度量特征的重要性，進(jìn)而對特征排序．Golub等[3]的研究表明基于SNR的特征排序方法是一個快速且有效的致癌基因判別方法．基因gi的SNR數(shù)值RSN通過下式計算得到：

(1)

其中：u+(gi)和u-(gi)分別表示第i個基因gi在陰性類別和陽性類別的平均表達(dá)值；σ+(gi)和σ-(gi)分別表示基因gi在兩個類別中表達(dá)水平的標(biāo)準(zhǔn)差．

用式(1)來衡量每個基因的重要性，值越大說明該基因越重要．若某一基因在不同類別中的分布均值相等，那么它的RSN等于零，則該基因便被認(rèn)為是無關(guān)基因而剔除．

1.2 K均值聚類算法

K均值聚類算法[7]是最經(jīng)典的聚類方法之一，它基于觀測對象間的相似度將對象劃分不同類別，使得類內(nèi)具有較高的相似度，而類間的相似度較低．對于給定的一組樣本數(shù)據(jù)(x1,x2,…,xn)，現(xiàn)要將其劃分為K個子集合(類別)，S={S1,S2,…,SK}，K均值的劃分思想是：先從n個樣本中隨機(jī)選出K個樣本作為初始聚類中心，隨后將剩余樣本分別劃入與其距離最近的聚類中心的相應(yīng)類別中，使得類內(nèi)總距離達(dá)到最小，其目標(biāo)函數(shù)可以表示為：

(2)

其中ui表示集合Si的聚類中心點．所有樣本的類別劃分完畢后需要更新各個類別的中心點，第t+1次的聚類中心通過下式計算：

(3)

隨后對各個樣本重新劃分類別，重復(fù)以上過程直到中心值的變化可以忽略不計或者達(dá)到最大的迭代次數(shù)．

1.3 SVM-RFE特征選擇算法

SVM是一種基于統(tǒng)計理論的分類方法，它利用核函數(shù)將普通低維空間中難以用一條直線分開的數(shù)據(jù)映射到一個較高維度的空間中，使其達(dá)到線性可分的目的．在SVM超平面上的每個維度對應(yīng)著輸入數(shù)據(jù)集中的每個特征，因此可以把超平面上各個維度權(quán)重的絕對值看作該維度(或特征)的貢獻(xiàn)(或重要性)．所以，權(quán)重的絕對值便可以用來對特征排序，從中選出關(guān)鍵特征．SVM-RFE便是基于此思想的嵌入式特征選擇方法，最初由Guyon等[4]提出，它是將SVM與RFE的后項搜索方法相結(jié)合的產(chǎn)物．SVM-RFE的特征選擇過程如下所示．

輸入：訓(xùn)練數(shù)據(jù)集E(n個樣本，m個特征)，類標(biāo)簽(n,1).

1) 初始化當(dāng)前特征集合Enow為原始數(shù)據(jù)集，最優(yōu)特征集合Ebest為空，最優(yōu)特征子集分類正確率Sbest為0.

2) 設(shè)置每次刪除的特征數(shù)量比例p(0

3) 重復(fù)以下步驟，直至當(dāng)前特征集合Enow為空：

由Enow建立SVM模型，得到正確率評估值Snow;

按特征權(quán)重的絕對值|w|降序排列Enow中的特征；

刪除當(dāng)前子集Enow中排名靠后的p%個特征；

若當(dāng)前特征子集Enow的正確率Snow大于Sbest：Ebest=Enow.

輸出：最優(yōu)特征子集Ebest.

SVM-RFE算法用SVM超平面的每個維度的權(quán)重絕對值來代表相應(yīng)特征的重要性，隨后通過權(quán)重對特征按從大到小排列．從降序排列的特征集合開始，每次刪除排名最后的那個特征；隨后繼續(xù)使用SVM在剩余特征集合上訓(xùn)練分類器，再刪除特征；如此多次重復(fù)進(jìn)行直到該特征集合為空，或者達(dá)到了用戶設(shè)定的特征數(shù)量為止．由于其優(yōu)異的性能表現(xiàn)，SVM-RFE算法廣泛用于圖像處理，文本分析，生物信息處理等領(lǐng)域．

2 K-SVM-RFE基因選擇方法

特征排序算法(如基于SNR的特征排序算法)能夠快速且有效地得到在不同類別中具有差異性表達(dá)的特征，特別是對于具有高維小樣本特性的數(shù)據(jù)，特征排序算法可以迅速去除無關(guān)特征．但是，在排名靠前的特征中，往往部分特征之間具有較高的相似性，造成了特征的冗余，這將會對少數(shù)關(guān)鍵特征的確定造成困擾，進(jìn)而影響最終的分類性能．

因此，特征排序方法能夠高效地去除無關(guān)特征，但是不能識別和去除冗余特征，它適用于關(guān)鍵基因的初步篩選．基于此，本研究提出一種三階段的基因選擇方法K-SVM-RFE．首先，利用SNR指標(biāo)計算各個基因的權(quán)重，并按權(quán)重降序排列基因，初步過濾掉大量權(quán)重值較低的基因；其次，為了去除冗余基因，將初步篩選后基因通過聚類算法聚成k1個類別，并對各個類別利用SVM-RFE方法選出k2個具有代表性的基因，組成新的基因集合F；最后，再次利用SVM-RFE算法從F中選擇出k個關(guān)鍵基因．算法描述如下所示，流程如圖1所示．

輸入：原始數(shù)據(jù)集(n個樣本，m個特征)，類標(biāo)簽(n,1)，選擇基因數(shù)量k．

1) 將原始數(shù)據(jù)預(yù)處理，處理結(jié)果記為D．

2) 特征排序算法從D中篩選出d個基因，記為f1，其維度為(n,d)．

4)i從1循環(huán)至k1，令f2=f2+SVM-RFE(ci,k2)，其中SVM-RFE(ci,k2)表示使用SVM-RFE算法從ci中選擇出k2個關(guān)鍵基因．

5) 使用SVM-RFE算法從f2中選擇出k個關(guān)鍵基因．

輸出：k個關(guān)鍵基因．

值得注意的是，K-SVM-RFE方法中共涉及到3個關(guān)鍵參數(shù)，分別為k，k1和k2.其中，k為最后SVM-RFE算法選擇的基因個數(shù)，也即最終輸出的基因數(shù)量；k1為聚類算法所聚的類數(shù)；k2為各個類別中使用SVM-RFE方法選擇的基因數(shù)．k，k1和k2均可通過用戶設(shè)定，但為了保證最后一次的SVM-RFE方法能夠選出足夠的k個基因，應(yīng)至少滿足如下關(guān)系：

k1×k2≥k.

(4)

在本文中3.2節(jié)我們將進(jìn)一步討論這3個參數(shù)的設(shè)置關(guān)系，以使K-SVM-RFE算法所選擇的特征達(dá)到最佳的分類效果．

3 實驗和結(jié)果分析

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

實驗主要以分類準(zhǔn)確率來比較本研究所提出的K-SVM-RFE算法與基于SNR的特征排序算法以及SVM-RFE算法在分類上的性能差異．為了驗證K-SVM-RFE算法的有效性，本研究以3個公共的基因表達(dá)譜數(shù)據(jù)集作為實驗對象，包括結(jié)腸癌基因表達(dá)譜數(shù)據(jù)集[8]、淋巴癌基因表達(dá)譜數(shù)據(jù)集[9]以及肺癌基因表達(dá)譜數(shù)據(jù)集[10]．這些數(shù)據(jù)集均可以從生物識別研究計劃的網(wǎng)站[11]下載得到，其數(shù)據(jù)構(gòu)成如表1所示：

表1 實驗數(shù)據(jù)集

在數(shù)據(jù)預(yù)處理階段，由于原始數(shù)據(jù)集中存在著基因表達(dá)水平全為0的數(shù)據(jù)列，同時也存在著少量的基因有表達(dá)值，但基因信息為空白的數(shù)據(jù)列，因此在獲得數(shù)據(jù)之后，本文中將這些全0列和信息不全的基因列作為問題數(shù)據(jù)剔除．隨后將數(shù)據(jù)離散化為0,1,2的整數(shù)，為下一步基因的分析研究做好準(zhǔn)備工作．對數(shù)據(jù)進(jìn)行離散化處理，一方面是由于基因表達(dá)譜數(shù)據(jù)的數(shù)值表征基因的表達(dá)水平，相鄰數(shù)據(jù)之間不具有連續(xù)性，另一方面數(shù)據(jù)離散化也可以看作是去噪的一個過程．

3.2 參數(shù)分析

K-SVM-RFE算法中共涉及到4個參數(shù)，分別為待選擇特征的數(shù)量k，初步篩選特征數(shù)量d，K均值聚類算法所聚的類數(shù)k1和在各個類別中使用SVM-RFE算法選擇的基因數(shù)k2.其中初步篩選特征的作用是首先去除大量無關(guān)的噪聲特征，降低下一過程的計算復(fù)雜度，因此d的選擇對實驗結(jié)果影響不大，它滿足遠(yuǎn)小于初始特征數(shù)量且稍大于待選特征數(shù)量即可．因此本研究在d取600時進(jìn)一步探究k與k1和k2之間的設(shè)置關(guān)系．本實驗以結(jié)腸癌基因表達(dá)譜數(shù)據(jù)集為實驗對象，以K最近鄰(KNN)作為分類器，設(shè)置不同的參數(shù)，采用五折交叉驗證的方式重復(fù)實驗10次，取分類準(zhǔn)確率的平均值作為最終的結(jié)果，實驗結(jié)果如表2所示．由第2節(jié)知，k1與k2需要滿足式(4)，所以表中不滿足此條件的實驗設(shè)為空．

表2 不同參數(shù)下所選特征的分類準(zhǔn)確率

在表2中，加粗的數(shù)據(jù)為所選特征數(shù)量k條件下的最佳分類準(zhǔn)確率結(jié)果．可以看出，當(dāng)k取15和20時，分類準(zhǔn)確率均在k1與k相等，k2取3時達(dá)到最大值，此時有k1×k2=3k;當(dāng)k取5和10時，雖然最大準(zhǔn)確率不在k1=k條件下，但是依然滿足k1×k2=3k的關(guān)系，且如果取k1=k，k2=3，其結(jié)果也依然較好．

因此，設(shè)置聚類算法所聚的類數(shù)與要選擇的特征數(shù)量相等，即k1=k且k2=3時，K-SVM-RFE算法所選特征能夠得到較好的分類性能．

3.3 分類準(zhǔn)確率的分析

為了分析比較不同特征數(shù)量對特征評價的準(zhǔn)確性，實驗分別測試重要特征數(shù)量為1,2,5,8,10,15,20,30,50,80,100,120時的分類性能．實驗中涉及到的一些參數(shù)包括：基于SNR的特征排序方法初步篩選出d=600個重要基因，k，k1與k2的取值根據(jù)3.2節(jié)取k1=k，k2=3;SVM-RFE算法每次迭代刪除的特征比例設(shè)為0.1，其他參數(shù)保持默認(rèn)．另外，在分類結(jié)果驗證上，特征選擇算法選出的關(guān)鍵基因分別作用于KNN和以徑向基為核函數(shù)的SVM這2個分類器.其中KNN分類器原理簡單，易于理解與實現(xiàn)，而SVM分類器在解決小樣本、非線性及高維模式識別中表現(xiàn)出許多特有的優(yōu)勢，將K-SVM-RFE算法同時作用于這2個分類器，可以驗證K-SVM-RFE算法所選特征在不同分類器上的適用情況．實驗采用五折交叉驗證的方式，取5次結(jié)果的平均值作為最終實驗的準(zhǔn)確率，實驗結(jié)果如圖2所示．

從圖2中可以看出，K-SVM-RFE算法在2種不同的分類器(KNN和SVM)下、3個不同的數(shù)據(jù)集和多個不同的關(guān)鍵基因數(shù)量上均展現(xiàn)出了比SVM-RFE算法和基于SNR的特征排序方法更好的分類準(zhǔn)確率．首先，隨著提取關(guān)鍵特征數(shù)量的遞減，K-SVM-RFE算法與經(jīng)典的SVM-RFE算法的分類準(zhǔn)確率在逐步拉開差距，K-SVM-RFE算法在分類表現(xiàn)上較SVM-RFE算法有較大提升，表明K-SVM-RFE算法在提取少量關(guān)鍵基因上的有效性．其次，在所有的結(jié)果中，基于SNR的特征排序方法所選擇特征的分類準(zhǔn)確率均不能達(dá)到100%，表明了該過濾式特征選擇方法不能去除冗余特征的局限性，而K-SVM-RFE算法能夠進(jìn)一步去除冗余特征，達(dá)到了特征精選的效果．

另外，對比相同數(shù)據(jù)集不同分類器條件下的結(jié)果，可以發(fā)現(xiàn)，以SVM作為分類器的分類結(jié)果總體都好于KNN分類器的結(jié)果.特別是淋巴癌基因表達(dá)譜數(shù)據(jù)集上，SVM的分類準(zhǔn)確率在特征數(shù)量為8時達(dá)到100%，而KNN分類器則在特征數(shù)量為15時分類準(zhǔn)確率才達(dá)到100%．產(chǎn)生這樣的差異一方面是因為K-SVM-RFE算法基于SVM學(xué)習(xí)，所以用SVM進(jìn)行分類可取得較好的結(jié)果；另一方面也是因為SVM在做分類器時它的懲罰因子的值主要是由樣本的數(shù)量而不是特征數(shù)量決定的，因此在各種數(shù)據(jù)集上應(yīng)用此模型都會有比較穩(wěn)定的分類性能．

圖2 不同分類器(KNN、SVM)在不同基因(結(jié)腸癌、肺癌、淋巴癌基因)表達(dá)譜數(shù)據(jù)集下3種特征排序方法的分類正確率與k的變化關(guān)系圖Fig.2 Classification accurate rates of different classifiers (KNN，SVM) with respect to kon different genes (colon, lung, andlymphoma gene) expression datasets solved by three feature sorting methods

4 結(jié) 論

本研究將聚類算法與SVM-RFE方法相結(jié)合，提出了一種新的面向基因表達(dá)譜數(shù)據(jù)的特征選擇方法K-SVM-RFE，以多個基因表達(dá)譜數(shù)據(jù)為實驗對象，并通過2個分類器分別驗證所選基因的分類效果．研究結(jié)果表明了K-SVM-RFE算法在致癌基因識別上的有效性，特別是在精選少量致癌基因上，性能更佳．

在取得上述成果的同時，本研究還有許多有待進(jìn)一步研究的地方.如本文中實驗數(shù)據(jù)均只有2個類別，對于多類別數(shù)據(jù)的分類性能還有待進(jìn)一步研究；SVM-RFE和其他聚類算法的結(jié)合效果以及k1和k22個參數(shù)的最佳設(shè)置，也有待進(jìn)一步探討．