王 年, 許鴻洋, 梁 棟, 鮑文霞

(安徽大學(xué) 計算智能與信號處理教育部重點實驗室, 合肥 230039)

隨著生命科學(xué)和信息科學(xué)的發(fā)展，研究人員將生物學(xué)問題轉(zhuǎn)化為模式識別問題，并將基因表達(dá)譜應(yīng)用于基因組分析，挖掘出腫瘤組織中的病變基因，從而準(zhǔn)確識別出腫瘤類型；但基因表達(dá)譜數(shù)據(jù)具有樣本小，維數(shù)高，噪聲大的特點[1]。直接使用數(shù)據(jù)進(jìn)行腫瘤特征分析是不可行的[2， 3]，須對數(shù)據(jù)進(jìn)行降維處理，在獲得最優(yōu)特征的同時丟棄一些冗余信息，以降低數(shù)據(jù)的維數(shù)和系統(tǒng)的復(fù)雜性。

目前數(shù)據(jù)降維方法分為線性和非線性，常見的線性降維方法有獨立分量分析(ICA)、線性判別分析(LDA)、主成分分析(PCA)等。線性降維方法的算法復(fù)雜度較低，但應(yīng)用于非線性分布的數(shù)據(jù)時，降維效果較差，因此需要采用非線性方法對數(shù)據(jù)進(jìn)行維數(shù)約減。流行學(xué)習(xí)是常見的非線性方法，如拉普拉斯本征映射(LM)[4]，局部線性嵌入(LLE)[5]和等距映射(ISOMP)[6]等。Roweis等針對非線性數(shù)據(jù)提出基于LLE的無監(jiān)督數(shù)據(jù)降維方法，能夠使高維空間中的數(shù)據(jù)點映射到低維流行空間中，同時降維后的數(shù)據(jù)保持了原有數(shù)據(jù)的拓?fù)浣Y(jié)構(gòu)；近年來，針對 LLE算法存在的相似度度量、鄰域的選取及對新樣本的泛化能力等問題，各種改進(jìn)方法被陸續(xù)提出，Zhang等通過將圖像的相似度計算引入到LLE中，用以取代傳統(tǒng)的歐式距離準(zhǔn)則[7]；Liu等提出有監(jiān)督的局部線性嵌入算法(Supervised local linear embedding)，在保留樣本的流行結(jié)構(gòu)的同時引入樣本的類別信息，在人臉識別中取得了較好的效果，但仍然無法解決新樣本泛化問題[8]；Nicholos等提出LLE+SVM分類方法，在參數(shù)最優(yōu)的情況下, 可以獲得較好的分類結(jié)果[9]；Cai等提出LLE+LBP用于人臉識別，通過調(diào)節(jié)參數(shù)以增強(qiáng)對新樣本的泛化能力[10]；Pan等提出基于權(quán)值的無監(jiān)督的局部線性嵌入方法，用于深度挖掘數(shù)據(jù)的內(nèi)在結(jié)構(gòu)，并成功應(yīng)用于人臉識別中[11]；Zhao等提出基于概率分布的LLE腫瘤識別方法，通過計算樣本間互為近鄰的概率，再結(jié)合LLE算法，選取概率大的樣本作為近鄰樣本[12]；Andres等將數(shù)據(jù)劃分為N個區(qū)域，通過求得區(qū)域最優(yōu)解來獲得全局最優(yōu)解，但該算法未能充分的利用樣本的類別信息[13]。

LLE/SLLE算法對近鄰數(shù)的選擇具有較高的依賴性，且通過試湊法進(jìn)行參數(shù)的選擇，具有偶然性且耗時。本文算法通過對歐式距離函數(shù)進(jìn)行修改，將高斯核技巧引入到腫瘤識別之中，結(jié)合樣本的類別信息，為樣本自動設(shè)置合理的近鄰，很好地解決了鄰域選取問題，使得鄰域中大部分為同類樣本，有效地對數(shù)據(jù)進(jìn)行降維及待測樣本的分類；降低標(biāo)準(zhǔn)LLE/SLLE算法中對噪聲和稀疏數(shù)據(jù)的敏感性。最后，通過與已有算法的對比，驗證本文方法的實時性和準(zhǔn)確性。

1 LLE和SLLE算法

1.1 LLE

設(shè)預(yù)處理后的基因表達(dá)譜數(shù)據(jù)為D維向量X={x1,x2,L,xm},x∈RD，LLE通過將高維數(shù)據(jù)集D映射到低維空間Rd，得到m個d維向量yi，i=1，2,L,m,yi為xi在d維空間的表示，且d?D。

LLE算法主要分為3個步驟：

1)鄰域選取，計算任意樣本xi與其他(m-1)個樣本間的距離，距離越小說明兩樣本間相似度越高，據(jù)此可確定樣本xi的k(k

2)對任意樣本xi，用其近鄰樣本的線性組合來表示xi，且使得重建誤差最小化，即求式(1)的最優(yōu)解；

(1)

(2)

3)通過求解局部重建權(quán)重矩陣，得到低維嵌入向量yi，該過程通過最小化重構(gòu)誤差和來實現(xiàn)，即式(3)：

(3)

利用Langrage乘數(shù)法，式(3)可轉(zhuǎn)化為式(4)的特征值求解問題：

MY=λY

(4)

其中M=(I-W)T(I-W)；取M的(2?d+1)個最小特征值所對應(yīng)的特征向量作為低維嵌入向量集Y。

LLE是一種局部線性逼近的無監(jiān)督的數(shù)據(jù)降維算法，無法充分利用腫瘤樣本的類別信息，使得算法對于稀疏數(shù)據(jù)和含噪聲數(shù)據(jù)處理效果較差。

1.2 SLLE

針對LLE算法未能充分利用樣本的類別信息，Ridder等[14]提出了有監(jiān)督的LLE算法；LLE根據(jù)歐式距離來獲得k個近鄰樣本，而SLLE在歐式距離基礎(chǔ)上增加樣本點的類別信息，通過式(5)來計算R個近鄰樣本點。

Δ=dist(xi,xj)+αmax(dist(xi,xj))Λij,α∈[0,1]

(5)

(6)

其中dist(xi,xj)為歐式距離；α(0≤α≤1)為經(jīng)驗參數(shù)，根據(jù)數(shù)據(jù)的稀疏程度適當(dāng)調(diào)節(jié)α的值，當(dāng)α=0時，LLE和SLLE相同。

2 改進(jìn)的SLLE算法

2.1 改進(jìn)的度量公式

本文對SLLE的度量公式進(jìn)行修改，將核方法引入到SLLE算法中，其主要思想是在核空間中結(jié)合樣本的類別信息來確定樣本的近鄰域，計算后類內(nèi)樣本點間距離較小，類間距離較大，算法中引入了高斯核函數(shù)，如式(7)所示：

(7)

對任意給定樣本點(xi,Li)，xi∈RD，距離公式(5)可修改為如式(8)所示：

(8)

其中參數(shù)sigma大小根據(jù)數(shù)據(jù)的稀疏程度適當(dāng)調(diào)節(jié)，Lj為樣本的類別。圖1為EKLLE與SLLE距離公式曲線圖。

圖1(a) EKLLE

圖1(b) SLLE

由圖1(a)及公式(8)知，引入樣本的類別信息后，隨著歐式距離的增加，EKLLE算法中類間距離的增長速率遠(yuǎn)大于類內(nèi)距離，使得具有鑒別能力的數(shù)據(jù)得以表達(dá)，當(dāng)含有噪聲數(shù)據(jù)時，Δ′增長較為緩慢，減少了噪聲的干擾，更適合含噪聲數(shù)據(jù)樣本分類[15]。由圖1(b)及公式(5)可知，隨著歐式距離的增加，SLLE算法中類內(nèi)樣本間與類間樣本間的距離均是線性增長的，且斜率相同，使得具有鑒別能力的數(shù)據(jù)無法表現(xiàn)出來；其次，SLLE算法中Δ∈[0,+∞]，對于含有較強(qiáng)噪聲的數(shù)據(jù)，易造成樣本鄰域混亂，影響實驗效果。

2.2 自動選擇近鄰

LLE算法中只有鄰域樣本參與重構(gòu)，因此近鄰數(shù)k的選擇尤為重要，對于分布不規(guī)則且噪聲大的數(shù)據(jù)，若k值選取過大，易造成非近鄰數(shù)據(jù)點誤歸為鄰域中，且易造成回路問題；若k值選取過小，則很難保證數(shù)據(jù)的整體幾何結(jié)構(gòu)；本文根據(jù)腫瘤基因數(shù)據(jù)的結(jié)構(gòu)特點，以樣本的平均相似度為閾值來自動劃定樣本的鄰域；

設(shè)基因表達(dá)譜數(shù)據(jù)樣本X={x1,x2,……,xm}兩兩樣本間的相似度定義為式(9)：

S(xi,xj)=1/Δ′(xi,xj)

(9)

對任意樣本點xi(i=1,2,L,m)到所有樣本的平均相似度為：

(10)

其中dmean(i)作為判別xj是否為xi近鄰的閾值，若S(xi,xj)>dmean(i),則xj為xi的近鄰，否則xj不是xi的近鄰，這樣有效的避免了鄰域過大或過小問題，保證數(shù)據(jù)的整體幾何結(jié)構(gòu)。近鄰數(shù)k一般比高維數(shù)據(jù)的本質(zhì)維數(shù)d大，這樣使得樣本鄰域間存在一定的重疊區(qū)域，從而使得m個鄰域相關(guān)聯(lián)，易于恢復(fù)數(shù)據(jù)的全局結(jié)構(gòu)。

3 實驗結(jié)果

3.1 數(shù)據(jù)預(yù)處理

設(shè)G′={g1,g2,……,gn}表示樣本中所有基因所構(gòu)成的集合，其中g(shù)j(1≤j≤n)代表每一個基因，n代表基因的總個數(shù)；設(shè)X={x1,x2,L,xm}代表m個樣本，xi(1≤i≤m)代表某一條件下所有樣本的表達(dá)值，m代表樣本的個數(shù)。

基因表達(dá)譜數(shù)據(jù)具有維數(shù)高，樣本少，冗余信息多，易導(dǎo)致分類結(jié)果偏置，本文采用Bhattacharyya距離對數(shù)據(jù)進(jìn)行預(yù)處理，即式(11)：

(11)

表1 實驗數(shù)據(jù)集樣本描述

本文所用數(shù)據(jù)為急性白血病(Leukemia)、結(jié)腸癌(Colon)、前列腺癌(Prostate)和肺癌(Lung)數(shù)據(jù)集[16-19]，具體描述如表1所示。

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

實驗中, 將實驗數(shù)據(jù)集分為訓(xùn)練集和測試集；對于結(jié)腸癌數(shù)據(jù)，訓(xùn)練集為40個樣本(27個為T(Tumor)樣本，13個為N(Normal)樣本)，測試集為22個樣本(13個為T樣本，9個為N樣本)[12, 16]；對于前列腺癌數(shù)據(jù)，訓(xùn)練集為70個樣本(33個為T樣本，37個為N樣本)，測試集為32個樣本(17個為T樣本，15個為N樣本)。分別對結(jié)腸癌數(shù)據(jù)及前列腺癌數(shù)據(jù)采用SLLE/EKLLE進(jìn)行驗證，重復(fù)實驗15次。圖2描述了相同子空間下，不同近鄰數(shù)對實驗結(jié)果的影響。

圖2近鄰數(shù)k不同對實驗結(jié)果影響

由圖2可知，對于結(jié)腸癌數(shù)據(jù)和前列腺癌數(shù)據(jù)，近鄰數(shù)k值過大過小均會對實驗效果產(chǎn)生不利影響。EKLLE克服了SLLE易受不均勻稀疏數(shù)據(jù)的影響，根據(jù)樣本周圍數(shù)據(jù)的稀疏程度及樣本的類別信息，以改進(jìn)的歐式距離為自變量，為樣本自動設(shè)置近鄰域，避免因數(shù)據(jù)缺失而造成數(shù)據(jù)整體結(jié)構(gòu)的扭曲，同時也避免近鄰數(shù)太大造成的回路問題。在d=5,k=7時結(jié)腸癌正確率為93.18%，k=14時前列腺癌正確率為93.33%。SLLE對近鄰數(shù)k的取值較為敏感；隨著k值變化分類準(zhǔn)確率浮動較大；結(jié)腸癌和前列腺癌數(shù)據(jù)集內(nèi)樣本點的分布不盡相同, 且缺少有效的確定方法，無法使用某一固定k值，采用試湊法需要大量的時間；在結(jié)腸癌分類實驗中d=5，k=11,SLLE的最高正確率僅為90.91%。

分類實驗中需要確定3個變量，近鄰數(shù)k，低維嵌入空間d，參數(shù)sigma。EKLLE算法中的近鄰數(shù)k和低維嵌入維數(shù)d固定時，參數(shù)sigma的變化對實驗結(jié)果的影響如圖3所示。EKLLE算法對sigma(sigma=2∶1∶12)的變化不敏感，盡管隨著sigma的增加，識別率有所浮動，但仍具有較好的識別效果，使得EKLLE算法對樣本具有較好的泛化性。

圖3 參數(shù)sigma對分類正確率的影響

為驗證本文方法的可行性，分別在 Lung、Colon、Prostate、Leukemia數(shù)據(jù)集上進(jìn)行測試, 重復(fù)實驗15次；實驗正確率和相應(yīng)的運行時間如表2 所示。

由表2知，EKLLE算法的正確率高于SLLE和MMC算法，且EKLLE算法無需人工干預(yù)，減少試湊法所浪費的時間及計算復(fù)雜度。在d=5,k=22,sigma=6時，Lung數(shù)據(jù)的分類準(zhǔn)確率可以達(dá)到99.67%，運行時間僅為3.82 s。EKLLE算法緩解了歐式距離重構(gòu)過程中對流行結(jié)構(gòu)的扭曲，保持了基因表達(dá)譜數(shù)據(jù)的內(nèi)在幾何結(jié)構(gòu)，提高了數(shù)據(jù)降維后的效果；而SLLE采用歐式距離來構(gòu)造高維樣本點的鄰域未必能夠真實的反映基因表達(dá)譜數(shù)據(jù)的內(nèi)在結(jié)構(gòu)，易造成不同類別的點進(jìn)入同一鄰域內(nèi)，影響數(shù)據(jù)的降維效果。對于較難分類的Prostate數(shù)據(jù)集，SLLE算法在d=5,k=15,α=0.5時正確率為90.00%，但其近鄰數(shù)k須采用試湊法，具有偶然性，運算效率較低。較MMC相比，EKLLE算法采用核技巧與樣本的類別信息相結(jié)合，所需的鑒別維數(shù)明顯少于MMC，降低算法的運行時間，更具有實時性。

表2 Lung、Colon、Prostate和Leukemia實驗結(jié)果

4 結(jié)束語

本文結(jié)合生物學(xué)與模式識別領(lǐng)域的相關(guān)知識, 提出了一種增強(qiáng)的核局部線性嵌入算法，并應(yīng)用于基因表達(dá)譜數(shù)據(jù)分類中。該算法充分利用腫瘤樣本的類別信息和高斯核函數(shù)來改進(jìn)LLE/SLLE算法中距離的度量公式，無需人工干預(yù)，通過樣本點周圍數(shù)據(jù)幾何分布自動設(shè)置合理的近鄰數(shù)，彌補(bǔ)了LLE/SLLE算法耗時的缺點，EKLLE比LLE及SLLE算法中使用相同的近鄰數(shù)更加合理；且該方法對參數(shù)和噪聲不敏感，在Colon、Lung、Prostate和Leukemia的實驗結(jié)果證實了本文所提算法在腫瘤基因表達(dá)譜數(shù)據(jù)分類方面的魯棒性和優(yōu)越性，與其他方法相比，更具有現(xiàn)實意義。

參考文獻(xiàn):

[1]Golub T R, Slonim D K, Tamayo P, et al. Molecular classification of cancer: class discovery and class prediction by gene expression monitoring [J]. Science, 1999, 286(5439): 531-537.

[2]Thomas A, Thobault H, Yves V D P, et al. Robust biomarker identification for cancer diagnosis with ensemble feature selection methods [J]. Bioinformatics, 2010, 26(3):392-398.

[3]Lee C P, Leu Y. A novel hybrid feature selection method for microarray data analysis [J]. Applied Soft Computing, 2011, 11(1):208-213.

[4]Tu S T, Chen J Y, Yang W, et al. Laplacian eigenmaps-based polarimetric dimensionality reduction for SAR image classification [J]. IEEE Transactions on Geoscience and Remote Sensing, 2012, 50(1): 170-179.

[5]Roweis S T, Saul L K. Nonliner dimensionality reduction by locally linear embedding [J]. Science, 2000, 290 (5500): 2323-2326.

[6]Tenenbaum J B, Silva V D, Langford J C. A global geometric framework for nonlinear dimensionality reduction [J]. Science, 2000, 290(5500): 2319-2323.

[7]Zhang L J, Wang N. Locally linear embedding based on image Euclidean distance[C]. IEEE International Conference on Automation and Logistics, 2007: 1914-1918.

[8]Liu C, Zhou J L, He K, et al. Supervised locally linear embedding in tensor space[C]. Third International Symposium on Intelligent Information Technology Application, 2009, 3:31-34.

[9]Nichols J M, Bucholtz F, Nousain B. Automated, rapid classification of signals using locally linear embedding [J]. Expert systems with applications, 2011, 38(10): 13472-13474.

[10]Cai L B, Ying Z L. Face recognition with locally linear embedding on local binary patterns[C]. Internation Conference on Information Science and Engineering, 2009, 1246-1249.

[11]Pan Y Z, Ge S Z S, Mamun A A. Weighted locally linear embedding for dimension reduction [J]. Pattern Recognition, 2009, 42(5): 798-811.

[12]Zhao L X, Zhang Z Y. Supervised locally linear embedding with probability-based distance for classification [J]. Computer and Mathematics with Application, 2009, 57(6):919-926.

[13]Andres A M, Juliana V A, Genaro D S. Global and local choice of the number of nearest neighbors in locally linear embedding [J]. Pattern Recognition Letter, 2011, 32(16):2171-2177.

[14]de Ridder D, Kouropteva O, Okun O, et al. Supervised locally linear embedding [J]. Artificial Neural Networks and Neural Information Processing, 2003, 2714: 333-341.

[15]Geng X, Zhan D C, Zhou Z H. Supervised nonlinear dimensionality reduction for visualization and classification [J]. IEEE Transaction on Systems, Man, and Cybernetics, 2005, 35(6): 1098-1107.

[16]Wang H Q, Huang D S. Regulation probability method for gene selection [J]. Pattern Recognition Letters, 2006, 27(2): 116-122.

[17]Zhang H P, Song X F, Zhang X B. Identifying disease genes from gene expression data based on singular value decomposition [C]. International Conference on Biomedical Engineering and Information, 2011, 3: 1743-1747.

[18]Wang B Y, Xu H Y, Wang N, et al. A recursive information gene selection using improved laplacian maximum margin criterion[J]. Journal of Information and Computational Science, 2013, 10(14): 4435-4443.

[19]Kulkarni A, Kumar B S C N, Ravi V, et al. Colon cancer prediction with genetics profiles using evolutionary techniques [J]. Expert Systems with Application, 2011, 38(3): 2752-2757.