李 強，石陸魁，劉恩海，王 歌

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

0 引言

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

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

1 相關工作

1.1 微陣列數據分類方法

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

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

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

1.2 流形學習算法

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

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

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

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

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

2 基于流形學習的微陣列數據分類方法

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

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

圖1 基于流形學習的基因微陣列數據分類模型Fig.1 Classified model of gene microarray data based on manifold lear ning

3 實驗結果

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

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

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

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

表1 流形學習算法與K－NN算法結合的分類結果Tab.1 Results of combining manifold learning with K－NN

表2 流形學習算法與NB算法結合的分類結果Tab.2 Results of combining manif old learning with NB

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

表3 流形學習算法與SVM結合的分類結果Tab.3 Results of combining manifold learning with SVM

4 結論

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

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

（2）從實驗結果可以得出，對于白血病數據集，ISOMAP、LLE和LE算法與樸素貝葉斯法結合會取得最好的分類結果，流形學習方法與SVM的結合次之，流形學習方法與K－NN的結合最差.

［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］ 李杰，唐降龍，王亞東，等.基因表達譜聚類P分類技術研究及展望［J］.生物工程學報，2005，21（4）：667－673.

［5］ 于化龍，顧國昌，趙靖，等.基于DNA微陣列數據的癌癥分類問題研究進展［J］.計算機科學，2010，37（10）：16－22，32.

［6］ 王明怡，吳平，夏順仁.基于人工神經網絡集成的微陣列數據分類［J］.浙江大學學報：工學版，2005，39（7）：971－975.

［7］ 陳磊，劉毅慧.基于CART算法的肺癌微陣列數據的分類［J］.生物信息學，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.