流行學(xué)習(xí)算法應(yīng)用于基因芯片數(shù)據(jù)分析

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

關(guān)鍵詞： 基因芯片； 流行學(xué)習(xí)； 高維數(shù)據(jù)； 支持向量機； LLE

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

0 引言

流行學(xué)習(xí)是近來發(fā)展起來的維數(shù)約減算法，在圖像處理和指紋識別方面有很好應(yīng)用。它要求基于非線性的數(shù)據(jù)結(jié)構(gòu)，這與生物系統(tǒng)的非線性特點相適應(yīng)?；诹餍袑W(xué)習(xí)的非線性降維包含兩類：①全局方法，包括等距映射算法（ISOMAP）與最大方差展開（MVU）[1-3]；②局部方法，包括局部線性嵌入算法（LLE）、拉普拉斯特征映射算法（LE）和局部切空間排列（LTSA）[1，4]。

基因芯片是嶄新的生物學(xué)技術(shù)，與傳統(tǒng)的基因檢測技術(shù)比較，基因芯片最大特點是能同時定量和定性檢測成千上萬個基因信息。但對于不斷增多的實驗數(shù)據(jù)，若不能及時有效地處理，就會導(dǎo)致“數(shù)據(jù)資源”變?yōu)椤皵?shù)據(jù)災(zāi)難”?；蛐酒瑪?shù)據(jù)特點是基因數(shù)多而樣本數(shù)少，即存在維數(shù)高、樣本少的“維數(shù)災(zāi)難”問題。所以解決的方法就是通過維數(shù)約減。本文主要應(yīng)用等距映射算法、局部線性嵌入算法和局部切空間排列算法來處理高維基因芯片數(shù)據(jù)。

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

1 流行學(xué)習(xí)算法

1.1 局部線性嵌入（LLE）

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

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

步驟2 計算局部重建權(quán)值矩陣，定義重構(gòu)誤差函數(shù)：

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

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

1.2 等距離映射算法（ISOMAP）

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

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

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

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

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

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

1.3 局部切空間排列（LTSA）

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

步驟1 選取領(lǐng)域

計算每個樣本點的領(lǐng)域。記Xp=[xp1，…，xpk]是樣本點Xp包含自身在內(nèi)的最近k個近鄰點。

步驟2 局部線性投影

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

步驟3 局部坐標系統(tǒng)的排列

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

2 支持向量機（SVM）

支持向量機分類實際上是通過非線性變換將輸入空間變換到一個高維空間，然后在這個新空間中求取最優(yōu)線性分類面，這種非線性變換是通過定義適當?shù)膬?nèi)積函數(shù)來實現(xiàn)[11-12]。

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

內(nèi)積函數(shù)K=（xi，x）也稱核函數(shù)，目前常用的核函數(shù)主要有三種：

⑴ 多項式形式的內(nèi)積函數(shù)，即：

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

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

⑵ 徑向基內(nèi)積函數(shù)

徑向基內(nèi)積函數(shù)是普遍使用的核函數(shù)，因為它對應(yīng)的特征空間是無窮維的，有限的數(shù)據(jù)樣本在該特征空間中肯定是線性可分。

⑶ S形函數(shù)內(nèi)積

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

這里，支持向量機實現(xiàn)的是一個兩層的多層感知器神經(jīng)網(wǎng)絡(luò)[11-12]。

3 實驗方法

在基因變量里，存在噪聲基因，這些基因?qū)Ψ诸愐饬x不大，因此，在進行降維前，需對數(shù)據(jù)進行預(yù)處理，即基因篩選。本文預(yù)處理方法采用t值統(tǒng)計方法[13-16]。

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

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

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

（b） 對預(yù)處理之后數(shù)據(jù)，基于流行學(xué)習(xí)的數(shù)據(jù)降維分析。

（c） 經(jīng)降維之后的訓(xùn)練集采用5-倍交叉驗證方法，計算出最優(yōu)的σ與C，構(gòu)造分類器模型。

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

4 實驗結(jié)果與分析

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

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

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

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

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

5 結(jié)束語

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

參考文獻：

[1] 劉小明.數(shù)據(jù)降維及分類中的流行學(xué)習(xí)研究[D].浙江大學(xué)博士論文，

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] 姜偉，楊炳儒.基于流行學(xué)習(xí)的維數(shù)約簡算法[J].計算機工程，2010.36（12）：25-27

[6] 肖傳樂，曹槐.基于流行學(xué)習(xí)的基因表達譜數(shù)據(jù)可視化[J].生物信息學(xué)，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] 李波.基于流行學(xué)習(xí)的特征提前方法及其應(yīng)用研究[D].中國科學(xué)技術(shù)大學(xué)博士論文，2008.

[10] 黃啟宏.流行學(xué)習(xí)方法理論研究及圖像中的應(yīng)用[D].電子科技大學(xué)博士論文，2007.

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

[12] 邊肇祺.模式識別[M].清華大學(xué)出版社，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] 胡煜.降維方法與有監(jiān)督分類在基因芯片數(shù)據(jù)分析中的應(yīng)用比較[D].中山大學(xué)碩士論文，2007.

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

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

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