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

葉小泉,吳云峰

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

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

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

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

1 相關工作介紹

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

1.1 基于SNR的特征排序

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

(1)

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

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

1.2 K均值聚類算法

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

(2)

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

(3)

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

1.3 SVM-RFE特征選擇算法

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

輸入：訓練數據集E(n個樣本，m個特征)，類標簽(n,1).

1) 初始化當前特征集合Enow為原始數據集，最優特征集合Ebest為空，最優特征子集分類正確率Sbest為0.

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

3) 重復以下步驟，直至當前特征集合Enow為空：

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

按特征權重的絕對值|w|降序排列Enow中的特征；

刪除當前子集Enow中排名靠后的p%個特征；

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

輸出：最優特征子集Ebest.

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

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

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

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

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

1) 將原始數據預處理，處理結果記為D．

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

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

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

輸出：k個關鍵基因．

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

k1×k2≥k.

(4)

在本文中3.2節我們將進一步討論這3個參數的設置關系，以使K-SVM-RFE算法所選擇的特征達到最佳的分類效果．

3 實驗和結果分析

3.1 實驗數據

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

表1 實驗數據集

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

3.2 參數分析

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

表2 不同參數下所選特征的分類準確率

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

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

3.3 分類準確率的分析

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

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

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

圖2 不同分類器(KNN、SVM)在不同基因(結腸癌、肺癌、淋巴癌基因)表達譜數據集下3種特征排序方法的分類正確率與k的變化關系圖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 結 論

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

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