基于流形學(xué)習(xí)的基因微陣列數(shù)據(jù)分類(lèi)方法

李 強(qiáng)，石陸魁，劉恩海，王 歌

（河北工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津300401）

0 引言

近些年來(lái)，隨著基因微陣列數(shù)據(jù)應(yīng)用逐漸趨于廣泛和微陣列數(shù)據(jù)庫(kù)的不斷完善，人們?cè)絹?lái)越需要充分深入地從大量的數(shù)據(jù)中捕獲信息.即使再大的基因組，人們可能只獲得少部分的基因信息.如果能研究出更加先進(jìn)的基因分析工具，使人們從基因微陣列數(shù)據(jù)中提取出有用的甚至于更深層次的信息，如基因功能信息、基因微陣列的進(jìn)化信息、與疾病相關(guān)的信息等，無(wú)疑能發(fā)揮出至關(guān)重要的作用.因此，如何對(duì)這些復(fù)雜的數(shù)據(jù)進(jìn)行有效地分析，挖掘出其中蘊(yùn)含的有用信息成為當(dāng)今社會(huì)研究的重點(diǎn)課題之一［1－7］.

對(duì)基因微陣列數(shù)據(jù)進(jìn)行分類(lèi)是挖掘微陣列數(shù)據(jù)中有用信息的一種重要手段.目前，在基因微陣列數(shù)據(jù)分類(lèi)研究方面，多數(shù)研究者采用有監(jiān)督的分類(lèi)方法，主要包括 K－近鄰（K－Nearest Neighbor，K－NN）、支持向量機(jī)（Support Vector Machine，SV M）和樸素貝葉斯（Naive Bayes，NB）等方法［8］.然而基因微陣列數(shù)據(jù)具有樣本少、非線(xiàn)性、維數(shù)高等特點(diǎn)，一般每個(gè)樣本的維數(shù)都高達(dá)幾千甚至上萬(wàn)，這種特性導(dǎo)致目前的一些分類(lèi)算法對(duì)其進(jìn)行分類(lèi)的效果不盡如人意.因此，如果能對(duì)微陣列數(shù)據(jù)集先進(jìn)行特征選擇或提取（降維處理），提取出與樣本類(lèi)別相關(guān)的基因或信息，再將分類(lèi)方法應(yīng)用到降維后的數(shù)據(jù)，可能會(huì)取得好的識(shí)別效果.而流形學(xué)習(xí)算法作為一種非線(xiàn)性降維方法，可以發(fā)現(xiàn)隱藏在高維數(shù)據(jù)中的非線(xiàn)性流形，在模式識(shí)別、數(shù)據(jù)挖掘等領(lǐng)域得到了廣泛地應(yīng)用.為此.作者提出了一種基于流形學(xué)習(xí)的基因微陣列數(shù)據(jù)分類(lèi)方法，可以較大地提高分類(lèi)精度.

1 相關(guān)工作

1.1 微陣列數(shù)據(jù)分類(lèi)方法

在基因微陣列數(shù)據(jù)的分類(lèi)研究中，多數(shù)研究人員采用有監(jiān)督的分類(lèi)方法，常用K－NN、樸素貝葉斯和SV M等方法對(duì)微陣列數(shù)據(jù)進(jìn)行分類(lèi).假設(shè)X是一個(gè)輸入向量，K－NN算法首先在訓(xùn)練集中找出與其距離最近的K個(gè)點(diǎn)，K一般為奇數(shù)（避免二義性問(wèn)題），然后再根據(jù)近鄰點(diǎn)所屬類(lèi)別確定其類(lèi)別.如果這K個(gè)點(diǎn)中屬于某個(gè)類(lèi)的點(diǎn)最多，則X就屬于該類(lèi).可見(jiàn)K－NN算法的關(guān)鍵就是求樣本點(diǎn)與訓(xùn)練集中每個(gè)點(diǎn)之間的距離，可以選擇歐式距離、向量夾角余弦、Pearson相關(guān)系數(shù)和Minkowski距離等.

貝葉斯分類(lèi)算法利用概率統(tǒng)計(jì)知識(shí)進(jìn)行分類(lèi).假定有m個(gè)類(lèi)，分別用C1，C2，…，Cm表示，設(shè)X＝｛x1，x2，…，xn｝是一個(gè)未知的數(shù)據(jù)樣本，X 屬于類(lèi)Ci當(dāng)且僅當(dāng)P（Ci｜X）＞P（Cj｜X），其中1≤j≤m且j≠i.根據(jù)貝葉斯定理，P（X）對(duì)于所有類(lèi)都為常數(shù)，最大化后驗(yàn)概率P（Ci｜X）可轉(zhuǎn)化為最大化先驗(yàn)概率P（X｜Ci）P（Ci）.根據(jù)貝葉斯方法，對(duì)一個(gè)未知類(lèi)別的樣本X，可以先分別計(jì)算出X 屬于每個(gè)類(lèi)別Ci的概率P（X｜Ci）P（Ci），然后選擇其中概率最大的類(lèi)別作為其類(lèi)別.

支持向量機(jī)遵循結(jié)構(gòu)化風(fēng)險(xiǎn)最小化原則來(lái)解決分類(lèi)問(wèn)題.支持向量機(jī)的基本思想是：首先將輸入空間投影到一個(gè)高維空間，然后在高維空間中基于分類(lèi)間隔最大求得最優(yōu)線(xiàn)性分類(lèi)面.但由于支持向量機(jī)算法通過(guò)變換空間的維數(shù)不能反映出所獲得分類(lèi)器的復(fù)雜度，該算法所獲得分類(lèi)器的復(fù)雜度通過(guò)采用支持向量的個(gè)數(shù)來(lái)反映，這就避免了其它算法可能會(huì)產(chǎn)生的過(guò)擬合問(wèn)題.

1.2 流形學(xué)習(xí)算法

流形學(xué)習(xí)可以發(fā)現(xiàn)隱藏在高維數(shù)據(jù)中的非線(xiàn)性流形，近年來(lái)得到了快速發(fā)展，并被應(yīng)用到圖像處理、模式識(shí)別等領(lǐng)域.比較具有代表性的流形學(xué)習(xí)算法包括局部線(xiàn)性嵌入法（Locally Linear Embedding，LLE）［9］、等度規(guī)映射法（ISOmetric feature MAPping，ISOMAP）［10］、拉 普 拉 斯 特 征 映 射 法（Laplacian Eigenmaps，LE）［11］和局部切空間校正法（Local Tangent Space Alignment，LTSA）［12］等.

LLE算法將全局非線(xiàn)性轉(zhuǎn)化為局部線(xiàn)性，其基本假設(shè)是每個(gè)數(shù)據(jù)點(diǎn)和它的鄰域點(diǎn)位于流形的一個(gè)線(xiàn)性或幾乎線(xiàn)性區(qū)域中，這樣可以在數(shù)據(jù)集中的每一個(gè)樣本點(diǎn)和它的鄰域點(diǎn)之間構(gòu)造局部線(xiàn)性平面，進(jìn)而在此基礎(chǔ)上建立函數(shù)并且優(yōu)化［9］.

ISOMAP算法是對(duì)多維尺度分析（Multi Dimensional Scaling，MDS）法的一種擴(kuò)展，其基本思想是用測(cè)地線(xiàn)距離代替MDS中的歐式距離.算法的關(guān)鍵是計(jì)算所有點(diǎn)間的測(cè)地線(xiàn)距離，對(duì)于近鄰點(diǎn)直接用歐式距離近似測(cè)地線(xiàn)距離，對(duì)于非近鄰點(diǎn)用兩點(diǎn)之間最短路徑來(lái)近似測(cè)地線(xiàn)距離.算法包括三個(gè)步驟：第一，確定每個(gè)樣本的k個(gè)近鄰點(diǎn)，構(gòu)建鄰域圖；第二，在鄰域圖上估計(jì)所有點(diǎn)間的測(cè)地線(xiàn)距離，測(cè)地線(xiàn)距離用點(diǎn)間的最短路徑近似；第三，利用MDS計(jì)算低維嵌入.

LE算法是基于譜圖理論的方法，它將從數(shù)據(jù)集得到的圖形拉普拉斯算子近似為流形上的拉普拉斯－貝爾特拉米算子.算法包括三個(gè)步驟：第一，確定每個(gè)對(duì)象的k個(gè)近鄰點(diǎn)，構(gòu)建鄰域圖；第二，為每條邊選擇一個(gè)權(quán)值，形成權(quán)值矩陣，權(quán)值可以用熱核方程或簡(jiǎn)單的方法確定；第三，進(jìn)行特征映射，利用拉普拉斯算子將權(quán)值矩陣轉(zhuǎn)化為推廣的特征值問(wèn)題，計(jì)算特征值來(lái)得到低維表示.

LTSA算法與前面所述流形學(xué)習(xí)算法不同的地方在于高維數(shù)據(jù)樣本點(diǎn)的鄰域選取標(biāo)準(zhǔn)不同，LTSA算法中樣本點(diǎn)的鄰域是用其所在領(lǐng)域的切空間表示的，并且建立每一個(gè)點(diǎn)的鄰域切空間，最后通過(guò)所有點(diǎn)的鄰域切空間的排列建立起低維流形的全局坐標(biāo).LTSA算法基于這樣的理論：理想的低維嵌入同局部的投影坐標(biāo)之間只相差一個(gè)仿射變換，并由此構(gòu)造一個(gè)最小化重構(gòu)誤差，求解最小化重構(gòu)誤差問(wèn)題可以轉(zhuǎn)化成求解一個(gè)稀疏矩陣的特征值問(wèn)題［12］.LTSA算法也是首先構(gòu)建鄰域圖，然后通過(guò)一個(gè)優(yōu)化函數(shù)計(jì)算d維仿射子空間，最后求得低維嵌入.

2 基于流形學(xué)習(xí)的微陣列數(shù)據(jù)分類(lèi)方法

基因微陣列數(shù)據(jù)中每個(gè)樣本含有幾千甚至上萬(wàn)個(gè)基因，具有很高的維數(shù)，直接使用分類(lèi)算法對(duì)這些高維數(shù)據(jù)進(jìn)行分類(lèi)一方面會(huì)造成分類(lèi)精度不高，另一方面會(huì)降低分類(lèi)算法的執(zhí)行效率.基因微陣列數(shù)據(jù)本身可以看作是嵌入在高維空間中的低維流形，如果使用流形學(xué)習(xí)算法對(duì)基因微陣列數(shù)據(jù)進(jìn)行降維，將其投影到低維空間中，提取出與分類(lèi)類(lèi)別相關(guān)的樣本特征，無(wú)疑會(huì)提高算法的執(zhí)行效率，而且會(huì)提高分類(lèi)識(shí)別的效果.基于此提出了基于流形學(xué)習(xí)的微陣列數(shù)據(jù)分類(lèi)模型，如圖1所示.

在該模型中，首先利用流形學(xué)習(xí)算法對(duì)微陣列數(shù)據(jù)進(jìn)行降維，然后對(duì)降維后數(shù)據(jù)利用分類(lèi)算法進(jìn)行分類(lèi).該模型是一個(gè)流形學(xué)習(xí)算法與分類(lèi)算法相結(jié)合的一般模型，流形學(xué)習(xí)算法可使用LLE、ISOMAP、LE和LTSA等算法中任何一個(gè)，分類(lèi)算法可使用KNN、Naive Bayes、SV M等算法中任何一種.通過(guò)流形學(xué)習(xí)將基因微陣列數(shù)據(jù)映射到低維空間中，再對(duì)降維后的數(shù)據(jù)進(jìn)行分類(lèi)，最終能達(dá)到相對(duì)較好的識(shí)別效果，并提高分類(lèi)算法的執(zhí)行效率.

圖1 基于流形學(xué)習(xí)的基因微陣列數(shù)據(jù)分類(lèi)模型Fig.1 Classified model of gene microarray data based on manifold lear ning

3 實(shí)驗(yàn)結(jié)果

為了驗(yàn)證所提出的分類(lèi)模型的有效性，在白血病數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn).該數(shù)據(jù)集由38個(gè)白血病的基因表達(dá)譜數(shù)據(jù)樣本組成，其中每個(gè)樣本包含5000個(gè)基因.整個(gè)數(shù)據(jù)集包括急性髓細(xì)胞性白血?。ˋML）和急性淋巴細(xì)胞白血?。ˋLL）兩種樣本，其中ALL又可以分為T(mén)細(xì)胞（T＿cell）和B細(xì)胞（B＿cell）兩個(gè)子類(lèi)，因此整個(gè)數(shù)據(jù)集實(shí)際上分為三種樣本，由11個(gè)急性髓細(xì)胞性白血?。ˋ ML），19個(gè)B＿cell急性淋巴細(xì)胞白血?。ˋLL＿B）和8個(gè) T＿cell（ALL＿T）急性淋巴細(xì)胞白血病組成.

在實(shí)驗(yàn)中，將數(shù)據(jù)集分為訓(xùn)練集和測(cè)試集，其中訓(xùn)練集包括10個(gè)ALL＿B細(xì)胞，4個(gè)ALL＿T細(xì)胞和5個(gè)A ML細(xì)胞，剩余的樣本作為測(cè)試集.為了比較降維前后的分類(lèi)效果，先在原始的白血病數(shù)據(jù)集上執(zhí)行分類(lèi)算法，然后再對(duì)白血病數(shù)據(jù)集利用流形學(xué)習(xí)算法進(jìn)行降維后執(zhí)行分類(lèi)算法.其中分類(lèi)算法包括K－NN、NB和SV M算法，流形學(xué)習(xí)算法包括ISOMAP、LLE、LE和LTSA算法，在實(shí)驗(yàn)中對(duì)三種分類(lèi)算法和四種流形學(xué)習(xí)算法進(jìn)行組合得到12種分類(lèi)器.在一般的分類(lèi)研究中，通常用識(shí)別率、查準(zhǔn)率和召回率來(lái)評(píng)價(jià)分類(lèi)算法的性能，在本文中也用這三個(gè)指標(biāo)來(lái)評(píng)價(jià)基于流形學(xué)習(xí)的微陣列數(shù)據(jù)分類(lèi)模型的性能.

在將微陣列數(shù)據(jù)映射到低維空間時(shí)，需要確定低維空間的維數(shù)，本文采用ISOMAP算法對(duì)白血病數(shù)據(jù)集進(jìn)行降維，用殘差曲線(xiàn)的拐點(diǎn)來(lái)近似數(shù)據(jù)集的本征維數(shù)，殘差曲線(xiàn)如圖2所示，其中鄰域參數(shù)k為3.從圖中可以看出殘差曲線(xiàn)在維數(shù)為3時(shí)出現(xiàn)較明顯的拐點(diǎn)，在本文中為了提高分類(lèi)算法的精度，低維維數(shù)選擇為10.對(duì)于LLE算法和LE算法鄰域參數(shù)也選擇為3，對(duì)于LTSA算法鄰域參數(shù)選擇為19，當(dāng)鄰域參數(shù)小于19時(shí)會(huì)出現(xiàn)奇異矩陣現(xiàn)象.對(duì)于四個(gè)流形學(xué)習(xí)算法低維維數(shù)都選擇為10.對(duì)于K－NN分類(lèi)算法，根據(jù)先驗(yàn)知識(shí)K可以設(shè)置為3.實(shí)驗(yàn)結(jié)果如表1至表3所示.

圖2 用ISOMAP算法得到的殘差曲線(xiàn)Fig.2 The curve of the residual variance with ISOMAP

表1 流形學(xué)習(xí)算法與K－NN算法結(jié)合的分類(lèi)結(jié)果Tab.1 Results of combining manifold learning with K－NN

表2 流形學(xué)習(xí)算法與NB算法結(jié)合的分類(lèi)結(jié)果Tab.2 Results of combining manif old learning with NB

從實(shí)驗(yàn)結(jié)果可以看出，流形學(xué)習(xí)算法與分類(lèi)方法結(jié)合后，與直接用原始數(shù)據(jù)進(jìn)行分類(lèi)相比，識(shí)別率、查準(zhǔn)率、召回率都有了較大幅度的提高.對(duì)于白血病數(shù)據(jù)集，直接用高維數(shù)據(jù)集進(jìn)行分類(lèi)，K－NN分類(lèi)算法的分類(lèi)精度最低，SV M的分類(lèi)精度最高.流形學(xué)習(xí)方法與分類(lèi)算法結(jié)合后，總體上是流形學(xué)習(xí)算法與樸素貝葉斯法結(jié)合的效果最好，在四種流形學(xué)習(xí)方法中用LE算法得到的結(jié)果最好.除了分類(lèi)精度大幅提高外，利用降維后的數(shù)據(jù)進(jìn)行分類(lèi)也會(huì)極大地提高分類(lèi)算法的執(zhí)行效率.

表3 流形學(xué)習(xí)算法與SVM結(jié)合的分類(lèi)結(jié)果Tab.3 Results of combining manifold learning with SVM

4 結(jié)論

由于基因微陣列數(shù)據(jù)具有極的高維數(shù)，直接進(jìn)行分類(lèi)會(huì)降低分類(lèi)算法的性能，因此降低數(shù)據(jù)的維數(shù)是非常必要的.流形學(xué)習(xí)作為一種非線(xiàn)性降維方法，可以將高維數(shù)據(jù)有效地映射到低維空間中，發(fā)現(xiàn)其內(nèi)在的流形結(jié)構(gòu).本文提出了一種基于流形學(xué)習(xí)的微陣列數(shù)據(jù)分類(lèi)模型，首先利用流形學(xué)習(xí)算法將基因微陣列數(shù)據(jù)映射到低維空間中，然后再用降維后的數(shù)據(jù)進(jìn)行分類(lèi).在實(shí)驗(yàn)中，討論了四種流形學(xué)習(xí)算法LLE、ISOMAP、LE和LTSA算法與三種分類(lèi)方法K－NN、NB和SVM結(jié)合的效果.通過(guò)實(shí)驗(yàn)得到以下結(jié)論：

（1）流形學(xué)習(xí)算法與分類(lèi)方法結(jié)合后分類(lèi)精度明顯提高，同時(shí)有效提高了分類(lèi)算法的執(zhí)行效率.

（2）從實(shí)驗(yàn)結(jié)果可以得出，對(duì)于白血病數(shù)據(jù)集，ISOMAP、LLE和LE算法與樸素貝葉斯法結(jié)合會(huì)取得最好的分類(lèi)結(jié)果，流形學(xué)習(xí)方法與SVM的結(jié)合次之，流形學(xué)習(xí)方法與K－NN的結(jié)合最差.

［1］ SLONI MD K，TAMAYO P，MESIROV J P，et al.Class prediction and discovery using gene expression data［C］.New York：ACM，2000：263－272.

［2］ RAMASWAMY S，GOLUB T R.DNA micro Arrays in clinical oncology［J］.Journal of Clinical Oncology，2002，20（7）：1932－1941.

［3］ KURAMOCHI M，KARYPIS G.Gene classification using expression profiles：A feasibility study［C］.New York：IEEE，2000：191－200.

［4］ 李杰，唐降龍，王亞?wèn)|，等.基因表達(dá)譜聚類(lèi)P分類(lèi)技術(shù)研究及展望［J］.生物工程學(xué)報(bào)，2005，21（4）：667－673.

［5］ 于化龍，顧國(guó)昌，趙靖，等.基于DNA微陣列數(shù)據(jù)的癌癥分類(lèi)問(wèn)題研究進(jìn)展［J］.計(jì)算機(jī)科學(xué)，2010，37（10）：16－22，32.

［6］ 王明怡，吳平，夏順仁.基于人工神經(jīng)網(wǎng)絡(luò)集成的微陣列數(shù)據(jù)分類(lèi)［J］.浙江大學(xué)學(xué)報(bào)：工學(xué)版，2005，39（7）：971－975.

［7］ 陳磊，劉毅慧.基于CART算法的肺癌微陣列數(shù)據(jù)的分類(lèi)［J］.生物信息學(xué)，2011，9（3）：229－234.

［8］ STATNIKOV A，ALIFERIS C F，TSAMARDINOS I.A comprehensive evaluation of multicategory classification methods for gene expression cancer diagnosis［J］.Bioinfor matics，2005，21（5）：631－643

［9］ ROWEIS S T，SAUL L K.Nonlinear dimensionality reduction by locally linear embedding［J］.Science，2000，290（5500）：2323－2326.

［10］ TENENBAUMJ B，DESILVA V，LANGFORD J C.A global geometric framework for nonlinear dimensionality reduction［J］.Science，2000，290：231－2323.

［11］ BELKIN M，NIYOGI P.Laplacian eigenmaps and spectral techniques for embedding and clustering ［C］.Cambridge：MIT Press，2002：585－591.

［12］ ZHANG Zhen－yue，ZHA Hong－yuan.Principal manifolds and nonlinear dimensionality reduction by local tangent space alignment［J］.SIAMJournal of Scientific Computing，2004，26（1）：313－338.