流行學習算法應用于基因芯片數據分析

摘 要： 基因芯片是近年發展起來的生物技術，其數據典型特征是基因數多而樣本少，因此必須及時采取有效方法來處理這些以指數級增長的數據。流行學習算法在高維數據方面有著廣泛應用，但在基因芯片數據分析的應用還比較少。為了能得到在基因芯片數據分析中更好的處理方法，文章應用三種非線性降維提取海量基因芯片數據的特征，然后利用支持向量機作為分類器，判斷樣本的類屬。實驗結果表明，通過LLE特征提取之后，能獲得與原基因芯片更為接近的成分，類屬判斷結果更為準確，為基因芯片數據分析提供了一定的科學指導。

關鍵詞： 基因芯片； 流行學習； 高維數據； 支持向量機； LLE

中圖分類號：TP3-05 文獻標志碼：A 文章編號：1006-8228（2013）11-06-03

0 引言

流行學習是近來發展起來的維數約減算法，在圖像處理和指紋識別方面有很好應用。它要求基于非線性的數據結構，這與生物系統的非線性特點相適應。基于流行學習的非線性降維包含兩類：①全局方法，包括等距映射算法（ISOMAP）與最大方差展開（MVU）[1-3]；②局部方法，包括局部線性嵌入算法（LLE）、拉普拉斯特征映射算法（LE）和局部切空間排列（LTSA）[1，4]。

基因芯片是嶄新的生物學技術，與傳統的基因檢測技術比較，基因芯片最大特點是能同時定量和定性檢測成千上萬個基因信息。但對于不斷增多的實驗數據，若不能及時有效地處理，就會導致“數據資源”變為“數據災難”。基因芯片數據特點是基因數多而樣本數少，即存在維數高、樣本少的“維數災難”問題。所以解決的方法就是通過維數約減。本文主要應用等距映射算法、局部線性嵌入算法和局部切空間排列算法來處理高維基因芯片數據。

我們對基因芯片數據的分析主要通過三個步驟：數據預處理；數據降維；支持向量機分類。我們的主要工作是比較三種基于流行學習的非線性降維在基因表達數據分析中的分類效果。

1 流行學習算法

1.1 局部線性嵌入（LLE）

LLE算法總體由三部分組成，即先找出K個近鄰點，再計算出局部重建權值矩陣，最后由局部重建權值矩陣與其近鄰點計算出該樣本點輸出值。具體過程如下。

步驟1 計算出每個樣本的K個近鄰點。所謂近鄰點就是相對所求樣本點距離最近的K各樣本點，其中，K是一個自己輸入的數值。常用的距離主要有歐式距離，但在高維空間數據非線性分布中，歐式距離效果往往沒那么顯著，這時，可以采用Dijstra距離。這是一種測地距離，它能夠保持樣本點之間曲面特性，在其他非線性降維算法中也有著廣泛的應用。

步驟2 計算局部重建權值矩陣，定義重構誤差函數：

M是一個n*n的對稱矩陣，M=（I-E）T（I-E）[4-5]。

最優解Y*是由矩陣M最小第d+1個至最小第2個特征值所對應的特征向量組成，因為最小的特征值為零。LLE算法問題歸結為稀疏矩陣特征向量求解，計算量相對較小，不過算法不能提供從高維空間到低維空間的投影映射[4-5]。

1.2 等距離映射算法（ISOMAP）

等距離映射算法的重要之處在于兩點間距離的測定，測地距離近似計算有兩種，一種是樣本點xi和它的領域點間的測地距離使用它們之間的歐式距離來替代；另一種是，樣本點xi與它領域外的點用它們之間最短路徑來替代[3，6]。其計算步驟如下。

步驟1 建立領域關系圖G（V，E），根據每個xi（i=1，2，…，n）計算k個近鄰記作Nj，根據點xi為頂點，歐氏距離d（xi，xj）為邊，建立了鄰域關系圖G（V，E）。

其中，確定近鄰點常用如下兩種方法：一是利用ε-近鄰方法，考慮點對xi，xj是其近鄰點，若；二是利用k-近鄰方法，要事先給定k，然后確定其近鄰點。

步驟2 計算出測地距離矩陣D（dij）n*m，在鄰域關系圖G（V，E）尋找最短路徑，即

步驟3 在距離矩陣D（dij）n*m運行在古典MDS上，尋找其低維構造點Y={y1，y2，…，yn}[5]。

ISOMAP算法用殘差E來衡量降維誤差，即E=1-R2（DG，DY），這里DG為距離矩陣，DY是d維空間中歐氏距離矩陣，R2是線性相關系數。一般，降維維數d越高，E就越小。通過E曲線出現拐點或者E已經小到一定閾值就可以來確定降維的維數d[7]。

1.3 局部切空間排列（LTSA）

局部切空間排列是浙江大學張振躍等人在2004年提出的非線性降維方法[8]，LTSA基本思想是采用樣本點所在領域的切空間以表示點的領域，并對每一個點建立了領域切空間，而后將這些局部切空間排列起來建立流形的全局坐標。LTSA首先也需要選擇各樣本點的近鄰點[9]。具體計算步驟如下。

步驟1 選取領域

計算每個樣本點的領域。記Xp=[xp1，…，xpk]是樣本點Xp包含自身在內的最近k個近鄰點。

步驟2 局部線性投影

對Xp進行中心化處理，得到，再對進行奇異值分解，即，獲得右奇異向量組成的矩陣Vp。

步驟3 局部坐標系統的排列

構造排列矩陣，這里，Wp=I-[lk/，Vp][lk/，Vp]T。計算的最小d+1個特征值所對應的特征向量u2，…，ud+1，T=[u2，…，ud+1]T即為計算的嵌入結果[8，10]。

2 支持向量機（SVM）

支持向量機分類實際上是通過非線性變換將輸入空間變換到一個高維空間，然后在這個新空間中求取最優線性分類面，這種非線性變換是通過定義適當的內積函數來實現[11-12]。

為了解決兩類不平衡問題，這里需要引入懲罰因子C，當yi=+1類時，0?αi?C+；當yi=-1時，0?αi?C-。

內積函數K=（xi，x）也稱核函數，目前常用的核函數主要有三種：

⑴ 多項式形式的內積函數，即：

K（x，xi）=[（x·xi）+1]q

這里得到的支持向量機是一個q階多項式分離器。

⑵ 徑向基內積函數

徑向基內積函數是普遍使用的核函數，因為它對應的特征空間是無窮維的，有限的數據樣本在該特征空間中肯定是線性可分。

⑶ S形函數內積

K（x，xi）=tanh（v（x·xi）+c）

這里，支持向量機實現的是一個兩層的多層感知器神經網絡[11-12]。

3 實驗方法

在基因變量里，存在噪聲基因，這些基因對分類意義不大，因此，在進行降維前，需對數據進行預處理，即基因篩選。本文預處理方法采用t值統計方法[13-16]。

其中，與是一類中，同一個基因的平均值，n1與n2是每類的樣本數量，s1與s2是類的方差。計算出每個基因的t值，在按照t值大小排序，一般認為，基因排序靠前的對應在一類有較高表達值，而排在后面的對應另一類有較高表達值。我們取出t值較大的與t值較小的基因作數據分析。

本文使用的支持向量機以徑向基BRF作為核函數，為了選取一個較好的σ以及懲罰因子參數C，選用5-倍交叉驗證方法，得到交叉驗證準確率來確定。處理過程如下。

（a） 計算t值統計量，選出前100個t值最大基因和后100個t值最小基因。

（b） 對預處理之后數據，基于流行學習的數據降維分析。

（c） 經降維之后的訓練集采用5-倍交叉驗證方法，計算出最優的σ與C，構造分類器模型。

（d） 用分類器模型對測試集進行測試，計算識別率。

4 實驗結果與分析

本文選用的基因數據來源于Leukemia的組織樣本，共有7129個基因。其中，訓練集包含38個樣本（27個ALL，11個AML），測試集包含34個樣本（20個ALL，14個AML）[13]。數據集可以從網站http：//datam.i2r.a-star.edu.sg/datasets/krbd/獲得[17]。

通過處理，得到不同特征基因數三種方法識別率比較，如圖1所示。

圖1表明非線性降維LLE最優識別率比其他兩種方法高，在維數2與3時得到最優識別率為97.0588%，34個測試樣本有33個被正確識別。等距離映射ISOMAP效果最差，而且各維識別率都較低，在基因表達數據應用并不適合。經過流行學習算法處理與未處理的最優識別率比較如表1所示。

從表1可以看出，經過LLE的降維后，34個測試樣本有33個被正確識別，識別率達到97.0588%，也遠高于未經任何降維處理的識別率。

從圖2可以看出錯誤劃分的樣本便是劃橫線的那個。

5 結束語

本文根據基因芯片數據的特點，把新的基于流行學習的非線性降維算法應用于該數據。通過預處理可以去掉與分類無關的噪聲基因，而非線性降維則可以提取特征基因，消除對分類不良影響的冗余特征。通過比較三種算法可知，局部線性嵌入（LLE）的識別率優于其他兩種，也高于未經降維處理的數據。面對海量數據的工業應用，LLE可以提高基因芯片數據分析的準確性。

參考文獻：

[1] 劉小明.數據降維及分類中的流行學習研究[D].浙江大學博士論文，

2007.

[2] Tenenbaum JB， de Silva V， Langford JC. A global geometric framework for nonlinear dimensionality reduction[J]. Science，2000.290（5500）：2319-2323

[3] M. Balasubramanian and E.L. Schwartz. The Isomap algorithm and topological stability[J].Science，2002.295（5552）：7

[4] S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction bylocally linear embedding[J]. Science，2000.290：2323-2326

[5] 姜偉，楊炳儒.基于流行學習的維數約簡算法[J].計算機工程，2010.36（12）：25-27

[6] 肖傳樂，曹槐.基于流行學習的基因表達譜數據可視化[J].生物信息學，2009.7（1）：48-51

[7] Peterson L E.Partitioning large-sample microarray-based gene expression profiles using principal components analysis[J]. Comput Methods Programs Biomed，2003.70（2）：107-119

[8] Z. Zhang and H. Zha. Principal manifolds and nonlinear dimensionality reduction via local tangent space alignment[J]. SIAM Journal of Scientific Computing，2004.26（1）：31-338

[9] 李波.基于流行學習的特征提前方法及其應用研究[D].中國科學技術大學博士論文，2008.

[10] 黃啟宏.流行學習方法理論研究及圖像中的應用[D].電子科技大學博士論文，2007.

[11] 白鵬.支持向量機理論及工程應用實例[M].西安電子科技大學出版社，2008.

[12] 邊肇祺.模式識別[M].清華大學出版社，2000.

[13] T. R. Golub， D. K. Slonim. Molecular Classification of Cancer： Class Discovery and Class Prediction by Gene Expression Monitoring [J].Science，1999.286（15）：531-535

[14] 胡煜.降維方法與有監督分類在基因芯片數據分析中的應用比較[D].中山大學碩士論文，2007.

[15] 高利宏，曹佳.基因芯片可靠性分析及數據處理[J].第三軍醫大學學報，2006.28（1）：80-82

[16] 劉春菊，劉自偉.基因表達數據在數據庫中的預處理[J].電腦知識與技術，2009.5（16）：4101-4105

[17] Kent Ridge Bio-medical Dataset[EB/OL]. http：//datam.i2r.a-star.edu.sg/datasets/krbd/