癌癥基因表達數據具有高維、小樣本的特點,對其進行維數約減十分有必要。傳統的線性降維方法不能發現數據點之間的非線性關系,降維效果不好,因此,本文引入一種改進距離的多組權局部線性嵌入(DMLLE)算法對其進行降維。該算法采用一種改進距離來計算每個數據點的近鄰點,為每一個近鄰引入多組線性無關的局部權向量進行線性重構,通過最小化重構誤差得到高維數據在低維空間的嵌入結果。實驗結果表明,DMLLE算法對癌癥基因表達數據有很好的降維效果。
引用本文： 劉文遠, 王春蕾, 王寶文, 王常武. 改進的局部線性嵌入算法在癌癥基因表達數據降維中的應用. 生物醫學工程學雜志, 2014, 31(1): 85-90. doi: 10.7507/1001-5515.20140017 復制
引言
癌癥基因表達數據的出現，為癌癥的研究提供了一種重要的研究手段，在癌癥的基礎研究和臨床應用等領域得到了越來越多的關注。分析和研究癌癥基因表達數據，對于癌癥的早期預測和癌癥的亞型分型都非常有幫助[1]。癌癥基因表達數據的顯著特點是基因數多，樣本數少，并且數據量巨大、高噪聲、高冗余，且數據分布不均衡等[2]，這些特點對數據分析方法提出了更高的要求。一個基因芯片可以同時檢測的基因數一般都為幾千個，用基因芯片實驗得到的癌癥基因表達數據維數都很高，對如此高維數的數據直接進行處理分析有一定的困難。實際上，與疾病相關的基因數目并沒有那么多，基因表達數據中存在大量的冗余基因，它們并不能對數據的分析提供有用的信息，還會增加算法的時間復雜度[3]。因此，在分析癌癥基因表達數據之前，先降低數據維數是十分必要的。通過對基因表達數據降維，得到數據的低維嵌入結果，有助于對癌癥基因表達數據更好地進行分類、聚類分析，為癌癥的臨床診斷和治療提供幫助。
非線性降維方法近年來引起了越來越多學者的關注，其中最具有代表性的包括等距映射(isometric mapping，ISOMAP[4])、局部線性嵌入(locally linear embedding，LLE[5])、局部切空間排列(locally tangent space alignment，LTSA[6])等。ISOMAP算法的核心是用測地線距離表征流形上數據點的內在幾何關系。2003年，Dawson等[7]把ISOMAP應用到乳腺癌基因芯片數據集中，很好地顯示出了高維數據集中所隱藏的低維生物學相關結構。2004年，Nilsson等[8]用ISOMAP分析了淋巴瘤和肺癌的基因表達數據，證明了ISOMAP對研究淋巴瘤和肺癌的可視化有很好的效果，也暗示了基因之間的功能關系是非線性的。
LLE算法被認為是一種降維的很有效算法，已經被應用于解決信息處理、模式識別和數據挖掘中的各種各樣的問題。它的的主要思想是：高維數據集在投影到低維空間中后，局部鄰域點之間的線性關系應該是不變的。它最突出的特點就是用局部的線性來逼近全局的非線性，保持局部的幾何性質不變，通過相互重疊的局部鄰域來提供整體的信息，從而反映出數據集的局部幾何結構。 Li等[9]將LLE算法應用到淋巴瘤數據集中，先進行降維處理，然后用支持向量機(support vector machine，SVM)進行分類，當把48個基因降到至少11維的空間中時，SVM分類器的準確率接近百分之百。實驗結果表明了LLE算法對于這個癌癥基因表達數據集具有很好的降維效果，并且能提高分類的準確率。但是，LLE算法容易受到最近鄰數目的影響，對于噪聲和缺失值非常敏感。2011年，蔡先發等[10]提出了一種改進距離的局部線性嵌入算法，用一種改進的距離來度量樣本之間的距離，使得處于樣本分布稀疏區域的樣本間距離減小，降低了近鄰數目對實驗結果的影響。將改進的LLE算法應用到乳腺癌和卵巢癌基因表達譜數據集中，進行特征提取后用K最近鄰算法進行分類。實驗結果表明，改進距離的LLE算法分類正確率要比LLE算法更高。但是，這種改進的LLE算法仍不夠穩定，當數據集中噪音較大或鄰域之間的關聯較弱時，對高維數據的嵌入結果會發生扭曲[11]。
本文引入了一種改進距離的多組權局部線性嵌入(improved distance and multiple weights locally linear embedding,DMLLE)算法，首先采用蔡先發等人引用的改進距離來找到每個數據點的k個近鄰點，從而使得樣本集的整體分布更均勻，適用于數據分布不均衡的癌癥基因表達數據的降維處理。然后為每一個近鄰引入多組線性無關的局部權向量來代替LLE算法中的單一權向量，這樣構造出來的線性結構，要比用單一權向量構造的具有更好的穩定性。對于噪聲大、樣本點間關聯較弱的癌癥基因表達數據，能夠得到更好地嵌入結果。實驗結果表明，用DMLLE算法來處理癌癥基因表達數據，更能反映出數據集的局部幾何結構，有很好的可視化效果。
1 癌癥基因表達數據的表示
基因芯片的工作原理類似于核酸分子雜交方法，用已知核酸序列與互補的探針序列雜交，通過原位合成法或直接點樣法來制作[12]。在基因芯片的實驗中，首先制作熒光標記的探針，然后用選取的基因芯片與探針雜交，最后對芯片進行掃描，獲得熒光強度圖像，利用圖像分析軟件從圖像中提取出基因表達數據，也就是基因表達譜。
不同條件或狀態下的樣本(如不同時間，或正常組織與癌癥組織)實驗得到的癌癥基因表達數據構成一個矩陣M，矩陣的每一列代表在一個樣本中所有基因的表達值，每一行代表一個基因在所有樣本中的表達值。矩陣中的每一個值用xij表示，即第j個樣本的第i個基因的表達值。設G={g1,g2,…，gM},表示一個樣本中所有的基因組成的一個集合，其中gi(1≤i≤M)表示一個基因，｜G｜=M表示所有基因的個數。設S={s1,s2,…,sN}表示實驗樣本所構成的樣本集合，｜S｜=N表示樣本的數量，每一個樣本si(1≤i≤N)表示在某個條件下所有基因的表達值，即si是一個M維空間向量。基因表達矩陣M可以表現為下面這種形式：
| $M=\left[ \begin{matrix} {{x}_{1,1}} & {{x}_{1,2}} & \cdots & {{x}_{1,N}} \\ {{x}_{2,1}} & {{x}_{2,2}} & \cdots & {{x}_{2,N}} \\ \vdots & \vdots & \cdots & \vdots \\ {{x}_{M,1}} & {{x}_{M,2}} & \cdots & {{x}_{M,N}} \\ \end{matrix} \right]$ |
通常情況下，M≥N。
2 改進距離的LLE算法
LLE算法的過程就是將數據集X={x1,x2,…,xn}(其中xi是一個D維空間向量),映射到數據集Y={y1,y2,…,yn}(其中yi是一個d維空間向量，且d＜D)。改進距離的LLE算法步驟為：
第一步，找出每個樣本點的近鄰點。對于每一個樣本點xi，計算它和其他n-1個樣本點的距離，再根據距離的大小，選取k個與xj最近的點作為它的近鄰點。改進距離的LLE算法[10]中,引入了一種非線性降維方法Conformal-Isomap[13]中所定義的距離：
| ${{d}_{ij}}\left( {{x}_{i}},{{x}_{j}} \right)=\left| {{x}_{i}}-{{x}_{j}} \right|M\left( i \right)M\left( j \right)$ |
其中｜xi-xj｜是LLE算法中采用的歐式距離，分母中M(i),M(j)分別表示xi(i=1,2,…,n)，xj(j=1,2,…,n)和其他各個點之間距離的平均值，通過這個距離來找到每個點xi(i=1,2,…,n)的k個近鄰點。這個新的距離使得處于樣本分布稀疏區域的樣本點之間距離變小，樣本集的整體分布更均勻，這就降低了k值對于實驗結果的影響。
第二步，對每一個樣本點由其近鄰點進行線性重構。定義一個重構權值誤差函數：
| $\varepsilon \left( w \right)={{\sum\limits_{i=1}^{n}{\left\| {{x}_{i}}-\sum\limits_{j=1,j\ne i}^{k}{{{w}_{ij}}{{x}_{j}}} \right\|}}^{2}},$ |
其中wij是線性重構權值，當xj不是xi的近鄰點時wij=0，且。這些權值有著很重要的性質：在樣本點和它的鄰域點作平移、旋轉和縮放時，重構權值是不變的[11]。誤差函數越小，則重構權值矩陣建的越好，因此通過最小化這個誤差函數來選取重構權值矩陣。
第三步，根據第二步得到的重構權值矩陣w來計算低維嵌入結果Y。為了保持樣本嵌入點與其在低維空間嵌入點之間的權值和線性關系不變，Y通過最小化式(4) 來計算：
| $\omega \left( Y \right)={{\sum\limits_{i=1}^{n}{\left\| {{y}_{i}}-\sum\limits_{j=1}^{k}{{{w}_{ij}}{{y}_{j}}} \right\|}}^{2}},$ |
同時為了保證低維嵌入結果不影響重構權值誤差，還需要滿足兩個約束條件：和(I是一個d×d的單位矩陣)。最后，求解滿足這些約束條件下的優化嵌入結果。
改進距離的LLE算法具有參數少、計算復雜度低、容易求解的特點。但是它并不夠穩定，當數據集的噪音大、樣本點稀疏或鄰域關聯性較弱時，嵌入的結果會發生扭曲，不能很好的反映出高維流形的局部幾何結構。
3 DMLLE算法
本文采用一種多組重構權的方法[11]來代替改進距離的LLE算法中用單一的權向量構造線性結構。對于隱藏在高維空間中的一維流形，采用單一權向量總能得到很理想的嵌入結果。但是對于高于一維的流形，只采用單一的權向量來構造線性結構是不夠的。因為對于高于一維的流形，單個權值不足以反映出流形上復雜的幾何結構，而且采用單個權值建立的樣本點之間的關聯也較弱。而癌癥基因表達數據，不是簡單的一維流形，具有非線性的特點。如果采用多組線性無關的權值來構造局部線性結構，能夠得到更好的嵌入結果。
首先令Ji為xi鄰域的鄰域點的下標集，k=｜Ji｜表示xi的鄰域點個數。在第3節中，對于每個樣本點xi和它的鄰域集{xj,j∈Ji}，LLE通過求解最優化問題
| $\underset{{{w}_{ij}},j\in {{J}_{i}}}{\mathop{\min }}\,{{\left\| {{x}_{i}}-\sum\limits_{j\in {{J}_{i}}}^{k}{{{w}_{ij}}{{x}_{j}}} \right\|}^{2}},\sum\limits_{j\in {{J}_{i}}}{{{w}_{ij}}=1},$ |
構造xi同鄰域點之間局部線性關系。用wi表示由局部權wij，j∈Ji構成的局部權向量，用1k表示所有分量都是1的k維列向量，記Gi=[…,xj-xi,…]j∈Ji，由可以得到
| $\left\| \sum\limits_{j\in {{J}_{i}}}{{{w}_{ij}}{{\left( {{x}_{i}}-{{x}_{j}} \right)}^{2}}} \right\|={{\left\| {{G}_{i}}{{w}_{i}} \right\|}^{2}},$ |
當Gi的零空間不正交于1k時，wi可以通過單位化Gi的零空間向量來求得。否則，wi=fi/1kTfi，其中fi是線性系統
| $G_{i}^{T}{{G}_{i}}{{f}_{i}}={{1}_{k}}$ |
的解。LLE算法在這個線性系統中加入一個小的正數γ，然后通過求解這個正則化的線性系統
| $\left( G_{i}^{T}{{G}_{i}}+\gamma \left\| {{G}_{i}} \right\|_{F}^{2}I \right){{f}_{i}}={{1}_{k}},{{w}_{i}}={{f}_{i}}/1_{k}^{T}{{f}_{i}}$ |
得到局部權。
當Gi有小的奇異值向量時，下面的定理1[11]證明了一組線性無關且近似最優的權向量是存在的。
定理1： 若G∈Rm×k,σ1(G)≥L≥σk(G)是G的k個奇異值，那么對于r＜k，存在k-r個線性無關向量w(j),j=1,…,k-r使得
| $\left\| G{{w}^{\left( j \right)}} \right\|\le \underset{1_{k}^{T}w=1}{\mathop{\min }}\,\left\| Gw \right\|+{{\sigma }_{r+1}}\left( G \right),1_{k}^{T}=1$ |
并且對于W*=[w(1),…,w(k-r)]有
| ${{\left\| G{{w}_{*}} \right\|}_{F}}\le \sqrt{k-r}\underset{1_{k}^{T}w=1}{\mathop{\min }}\,\left\| Gw \right\|+\sqrt{\sum\limits_{j=r+1}^{k}{\sigma _{j}^{2}\left( G \right)}},$ |
將定理1中的G改成Gi，就可以得到ki-ri(ki=｜ji｜是鄰域點的個數)個線性無關的權向量wi(1)，…，w(ki-ri)即
| $w_{i}^{\left( 1 \right)}=\left( 1-{{\alpha }_{i}} \right)w_{i}^{*}+V_{2}^{i}{{H}_{i}}\left( :,l \right),\quad l\le {{k}_{i}}-{{r}_{i}},$ |
其中wi*是的最優解，V2(i)是對應于Gi的ki-ri個最小奇異值的右奇異向量，且hi如下構造
| ${{h}_{i0}}={{\alpha }_{i}}{{1}_{{{k}_{i}}-{{r}_{i}}}}-{{\left( V_{2}^{\left( i \right)} \right)}^{T}}{{1}_{{{k}_{i}}}},{{h}_{i}}=\left\{ \begin{matrix} \frac{{{h}_{i0}}}{\left\| {{h}_{i0}} \right\|}, & {{h}_{i0}}\ne 0 \\ 0, & {{h}_{i0}}=0 \\ \end{matrix} \right.$ |
尋找一個d維嵌入{y1,…，yn}，其中yi∈Rd能夠保持xi和其鄰域點之間更強的線性結構，也就是極小化下列的嵌入價值函數
| $\varepsilon \left( Y \right)={{\sum\limits_{i=1}^{n}{\sum\limits_{l=1}^{{{k}_{i}}-r}{\left\| \sum\limits_{j\in {{J}_{i}}}{w_{ij}^{\left( l \right)}{{y}_{j}}-{{y}_{i}}} \right\|}}}^{2}},$ |
記Wi=[wi(l),…,wi(ki-ri)]為局部權矩陣，將它嵌入到n維空間。記為Rn×(ki-ri)，有
| $\begin{align} & {{{\hat{W}}}_{i}}\left( {{J}_{i}},\,\!: \right)={{W}_{i}},\hat{W}\left( i,\,\!: \right)=-1_{{{k}_{i}}-{{k}_{r}}}^{T}, \\ & \hat{W}\left( j,\,\!: \right)=0,j\notin {{I}_{i}}, \\ \end{align}$ |
其中Ii=JiU{i}。式(13)可重新寫成：
| $\varepsilon \left( Y \right)=\sum\limits_{i}{\left\| Y{{{\hat{W}}}_{i}} \right\|}_{F}^{2}={{Y}_{r}}\left( Y\Phi {{Y}^{T}} \right),$ |
其中
| $\Phi =\sum\limits_{i}{{{{\hat{W}}}_{i}}}\hat{W}_{i}^{T}=\left\lceil {{{\hat{W}}}_{1}},\cdots ,{{{\hat{W}}}_{n}} \right\rceil {{\left\lceil {{{\hat{W}}}_{1}},\cdots ,{{{\hat{W}}}_{n}} \right\rceil }^{T}}。$ |
ε(Y)的極小值就是對應于Φ的從第2到第d+1個最小特征值的特征向量所構成的矩陣Y=[u2,…,ud+1]T。
4 DMLLE算法應用于癌癥基因表達數據
4.1 實驗數據集的預處理
原始的癌癥基因表達數據往往包含著大量的實驗隨機誤差和系統誤差，所以必須在降維處理之前對數據集進行預處理，以減少這些誤差對實驗數據的影響，得到更準確真實的分析結果。首先采用行平均值(row average)的方法[14]對每一個癌癥基因表達數據集進行丟失數據的修補，然后對數據進行對數轉換，最后按照基因對其進行平均值標準化。
4.2 胃癌基因表達數據的實驗結果及分析
胃癌基因表達數據集來源于美國國家生物技術信息中心(NCBI)http://www.ncbi.nlm.nih.gov/的GEO數據庫，它在GEO數據庫中公開的記錄編號為GDS1210。這個數據集是20個原發性晚期胃癌組織的表達譜數據，包括30個樣本的表達譜，其中有8個是正常組織樣本，22個是癌癥組織樣本，每一個樣本包括7 192個基因的表達數據。
分別采用改進距離的LLE和DMLLE算法對表達譜數據進行降維，改進距離的LLE算法中的鄰域參數k設置為7，DMLLE算法中的鄰域參數k設置為15。圖 1(a)是剩余方差隨壓縮維數逐漸增大的變化曲線，曲線在維數為3時出現了比較明顯的拐點，所以確定胃癌基因表達數據的本征維數是3。
圖1
胃癌和白血病數據的剩余方差曲線
(a)胃癌數據剩余方差曲線；(b)白血病數據剩余方差曲線
Figure1. Residual variance curve of gastric cancer and leukaemia data(a) the residual variance curve of gastric cancer data; (b) the residual variance curve of leukaemia data
圖 2是分別采用改進距離的LLE和DMLLE算法把胃癌基因表達數據降到3維的可視化結果。可見DMLLE算法有更好的可視化結果，將正常的和癌癥組織樣本區分的更明顯，而改進距離的LLE算法則差得多。
圖2
胃癌數據改近距離的LLE和DMLLE三維投影圖(o和*表示正常和患有胃癌的樣本)
(a)胃癌數據改進距離的LLE三維投影圖；(b)胃癌數據的DMLLE三維投影圖
Figure2. Improved distance LLE and DMLLE projections of gastric cancer data (o and * show the samples from normal persons or patient,respectively)(a) improved distance LLE projections of gastric cancer data; (b) DMLLE projections of gastric cancer data
4.3 白血病基因表達數據的實驗結果及分析
白血病基因表達數據來自于Getz等[15]實驗中用到的實驗數據集。共包括72個樣本組織，其中47個樣本組織被診斷是急性淋巴細胞白血病ALL，其他25個樣本組織被診斷是急性骨髓細胞白血病AML，實驗采用的基因表達矩陣是1 753個基因的表達數據。
分別采用改進距離的LLE和DMLLE算法對表達譜數據進行降維處理，其中鄰域參數設置為12。圖 1(b)是剩余方差隨壓縮維數的變化曲線，曲線在維數為3時出現了比較明顯的拐點，確定本征維數為3。
圖 3為分別用改進距離的LLE和DMLLE算法將白血病基因表達數據降到三維的可視化結果。可見DMLLE算法有更好的可視化結果，能夠清晰地區分出兩種不同類型的白血病組織樣本。
圖3
白血病數據改進距離的LLE和DMLLE三維投影圖(o和*表示ALL和AML的樣本)
(a)白血病數據改進距離的LLE三維投影圖；(b)白血病數據的DMLLE三維投影圖
Figure3. Improved distance LLE and DMLLE projections of leukaemia data (o and * show the samples from ALL and AML)(a)Improved distance LLE projections of leukaemia data; (b) DMLLE projections of leukaemia data
5 結論
癌癥基因表達數據具有非線性的特點，并且存在大量的冗余基因，不能對數據的分析提供有用的信息，本文引入了一種DMLLE算法，該算法采用一種改進距離計算每個數據點的近鄰點,并且為每個近鄰引入多組線性無關的局部權向量進行線性重構，通過最小化重構誤差得到高維數據在低維空間的嵌入結果。DMLLE算法更適應了樣本分布不均勻的特點，能夠反映出數據集的局部幾何結構。實驗結果表明，DMLLE算法比改進距離的LLE算法可視化效果更好，能清晰地區分出正常和胃癌組織樣本，以及不同類型的白血病組織樣本。利用該算法對基因表達數據進行降維處理，更有利于發現癌癥基因表達數據中潛在的低維流形結構,有助于對癌癥基因表達數據更好地進行分類、聚類分析，為癌癥的臨床診斷和治療提供幫助。
引言
癌癥基因表達數據的出現，為癌癥的研究提供了一種重要的研究手段，在癌癥的基礎研究和臨床應用等領域得到了越來越多的關注。分析和研究癌癥基因表達數據，對于癌癥的早期預測和癌癥的亞型分型都非常有幫助[1]。癌癥基因表達數據的顯著特點是基因數多，樣本數少，并且數據量巨大、高噪聲、高冗余，且數據分布不均衡等[2]，這些特點對數據分析方法提出了更高的要求。一個基因芯片可以同時檢測的基因數一般都為幾千個，用基因芯片實驗得到的癌癥基因表達數據維數都很高，對如此高維數的數據直接進行處理分析有一定的困難。實際上，與疾病相關的基因數目并沒有那么多，基因表達數據中存在大量的冗余基因，它們并不能對數據的分析提供有用的信息，還會增加算法的時間復雜度[3]。因此，在分析癌癥基因表達數據之前，先降低數據維數是十分必要的。通過對基因表達數據降維，得到數據的低維嵌入結果，有助于對癌癥基因表達數據更好地進行分類、聚類分析，為癌癥的臨床診斷和治療提供幫助。
非線性降維方法近年來引起了越來越多學者的關注，其中最具有代表性的包括等距映射(isometric mapping，ISOMAP[4])、局部線性嵌入(locally linear embedding，LLE[5])、局部切空間排列(locally tangent space alignment，LTSA[6])等。ISOMAP算法的核心是用測地線距離表征流形上數據點的內在幾何關系。2003年，Dawson等[7]把ISOMAP應用到乳腺癌基因芯片數據集中，很好地顯示出了高維數據集中所隱藏的低維生物學相關結構。2004年，Nilsson等[8]用ISOMAP分析了淋巴瘤和肺癌的基因表達數據，證明了ISOMAP對研究淋巴瘤和肺癌的可視化有很好的效果，也暗示了基因之間的功能關系是非線性的。
LLE算法被認為是一種降維的很有效算法，已經被應用于解決信息處理、模式識別和數據挖掘中的各種各樣的問題。它的的主要思想是：高維數據集在投影到低維空間中后，局部鄰域點之間的線性關系應該是不變的。它最突出的特點就是用局部的線性來逼近全局的非線性，保持局部的幾何性質不變，通過相互重疊的局部鄰域來提供整體的信息，從而反映出數據集的局部幾何結構。 Li等[9]將LLE算法應用到淋巴瘤數據集中，先進行降維處理，然后用支持向量機(support vector machine，SVM)進行分類，當把48個基因降到至少11維的空間中時，SVM分類器的準確率接近百分之百。實驗結果表明了LLE算法對于這個癌癥基因表達數據集具有很好的降維效果，并且能提高分類的準確率。但是，LLE算法容易受到最近鄰數目的影響，對于噪聲和缺失值非常敏感。2011年，蔡先發等[10]提出了一種改進距離的局部線性嵌入算法，用一種改進的距離來度量樣本之間的距離，使得處于樣本分布稀疏區域的樣本間距離減小，降低了近鄰數目對實驗結果的影響。將改進的LLE算法應用到乳腺癌和卵巢癌基因表達譜數據集中，進行特征提取后用K最近鄰算法進行分類。實驗結果表明，改進距離的LLE算法分類正確率要比LLE算法更高。但是，這種改進的LLE算法仍不夠穩定，當數據集中噪音較大或鄰域之間的關聯較弱時，對高維數據的嵌入結果會發生扭曲[11]。
本文引入了一種改進距離的多組權局部線性嵌入(improved distance and multiple weights locally linear embedding,DMLLE)算法，首先采用蔡先發等人引用的改進距離來找到每個數據點的k個近鄰點，從而使得樣本集的整體分布更均勻，適用于數據分布不均衡的癌癥基因表達數據的降維處理。然后為每一個近鄰引入多組線性無關的局部權向量來代替LLE算法中的單一權向量，這樣構造出來的線性結構，要比用單一權向量構造的具有更好的穩定性。對于噪聲大、樣本點間關聯較弱的癌癥基因表達數據，能夠得到更好地嵌入結果。實驗結果表明，用DMLLE算法來處理癌癥基因表達數據，更能反映出數據集的局部幾何結構，有很好的可視化效果。
1 癌癥基因表達數據的表示
基因芯片的工作原理類似于核酸分子雜交方法，用已知核酸序列與互補的探針序列雜交，通過原位合成法或直接點樣法來制作[12]。在基因芯片的實驗中，首先制作熒光標記的探針，然后用選取的基因芯片與探針雜交，最后對芯片進行掃描，獲得熒光強度圖像，利用圖像分析軟件從圖像中提取出基因表達數據，也就是基因表達譜。
不同條件或狀態下的樣本(如不同時間，或正常組織與癌癥組織)實驗得到的癌癥基因表達數據構成一個矩陣M，矩陣的每一列代表在一個樣本中所有基因的表達值，每一行代表一個基因在所有樣本中的表達值。矩陣中的每一個值用xij表示，即第j個樣本的第i個基因的表達值。設G={g1,g2,…，gM},表示一個樣本中所有的基因組成的一個集合，其中gi(1≤i≤M)表示一個基因，｜G｜=M表示所有基因的個數。設S={s1,s2,…,sN}表示實驗樣本所構成的樣本集合，｜S｜=N表示樣本的數量，每一個樣本si(1≤i≤N)表示在某個條件下所有基因的表達值，即si是一個M維空間向量。基因表達矩陣M可以表現為下面這種形式：
| $M=\left[ \begin{matrix} {{x}_{1,1}} & {{x}_{1,2}} & \cdots & {{x}_{1,N}} \\ {{x}_{2,1}} & {{x}_{2,2}} & \cdots & {{x}_{2,N}} \\ \vdots & \vdots & \cdots & \vdots \\ {{x}_{M,1}} & {{x}_{M,2}} & \cdots & {{x}_{M,N}} \\ \end{matrix} \right]$ |
通常情況下，M≥N。
2 改進距離的LLE算法
LLE算法的過程就是將數據集X={x1,x2,…,xn}(其中xi是一個D維空間向量),映射到數據集Y={y1,y2,…,yn}(其中yi是一個d維空間向量，且d＜D)。改進距離的LLE算法步驟為：
第一步，找出每個樣本點的近鄰點。對于每一個樣本點xi，計算它和其他n-1個樣本點的距離，再根據距離的大小，選取k個與xj最近的點作為它的近鄰點。改進距離的LLE算法[10]中,引入了一種非線性降維方法Conformal-Isomap[13]中所定義的距離：
| ${{d}_{ij}}\left( {{x}_{i}},{{x}_{j}} \right)=\left| {{x}_{i}}-{{x}_{j}} \right|M\left( i \right)M\left( j \right)$ |
其中｜xi-xj｜是LLE算法中采用的歐式距離，分母中M(i),M(j)分別表示xi(i=1,2,…,n)，xj(j=1,2,…,n)和其他各個點之間距離的平均值，通過這個距離來找到每個點xi(i=1,2,…,n)的k個近鄰點。這個新的距離使得處于樣本分布稀疏區域的樣本點之間距離變小，樣本集的整體分布更均勻，這就降低了k值對于實驗結果的影響。
第二步，對每一個樣本點由其近鄰點進行線性重構。定義一個重構權值誤差函數：
| $\varepsilon \left( w \right)={{\sum\limits_{i=1}^{n}{\left\| {{x}_{i}}-\sum\limits_{j=1,j\ne i}^{k}{{{w}_{ij}}{{x}_{j}}} \right\|}}^{2}},$ |
其中wij是線性重構權值，當xj不是xi的近鄰點時wij=0，且。這些權值有著很重要的性質：在樣本點和它的鄰域點作平移、旋轉和縮放時，重構權值是不變的[11]。誤差函數越小，則重構權值矩陣建的越好，因此通過最小化這個誤差函數來選取重構權值矩陣。
第三步，根據第二步得到的重構權值矩陣w來計算低維嵌入結果Y。為了保持樣本嵌入點與其在低維空間嵌入點之間的權值和線性關系不變，Y通過最小化式(4) 來計算：
| $\omega \left( Y \right)={{\sum\limits_{i=1}^{n}{\left\| {{y}_{i}}-\sum\limits_{j=1}^{k}{{{w}_{ij}}{{y}_{j}}} \right\|}}^{2}},$ |
同時為了保證低維嵌入結果不影響重構權值誤差，還需要滿足兩個約束條件：和(I是一個d×d的單位矩陣)。最后，求解滿足這些約束條件下的優化嵌入結果。
改進距離的LLE算法具有參數少、計算復雜度低、容易求解的特點。但是它并不夠穩定，當數據集的噪音大、樣本點稀疏或鄰域關聯性較弱時，嵌入的結果會發生扭曲，不能很好的反映出高維流形的局部幾何結構。
3 DMLLE算法
本文采用一種多組重構權的方法[11]來代替改進距離的LLE算法中用單一的權向量構造線性結構。對于隱藏在高維空間中的一維流形，采用單一權向量總能得到很理想的嵌入結果。但是對于高于一維的流形，只采用單一的權向量來構造線性結構是不夠的。因為對于高于一維的流形，單個權值不足以反映出流形上復雜的幾何結構，而且采用單個權值建立的樣本點之間的關聯也較弱。而癌癥基因表達數據，不是簡單的一維流形，具有非線性的特點。如果采用多組線性無關的權值來構造局部線性結構，能夠得到更好的嵌入結果。
首先令Ji為xi鄰域的鄰域點的下標集，k=｜Ji｜表示xi的鄰域點個數。在第3節中，對于每個樣本點xi和它的鄰域集{xj,j∈Ji}，LLE通過求解最優化問題
| $\underset{{{w}_{ij}},j\in {{J}_{i}}}{\mathop{\min }}\,{{\left\| {{x}_{i}}-\sum\limits_{j\in {{J}_{i}}}^{k}{{{w}_{ij}}{{x}_{j}}} \right\|}^{2}},\sum\limits_{j\in {{J}_{i}}}{{{w}_{ij}}=1},$ |
構造xi同鄰域點之間局部線性關系。用wi表示由局部權wij，j∈Ji構成的局部權向量，用1k表示所有分量都是1的k維列向量，記Gi=[…,xj-xi,…]j∈Ji，由可以得到
| $\left\| \sum\limits_{j\in {{J}_{i}}}{{{w}_{ij}}{{\left( {{x}_{i}}-{{x}_{j}} \right)}^{2}}} \right\|={{\left\| {{G}_{i}}{{w}_{i}} \right\|}^{2}},$ |
當Gi的零空間不正交于1k時，wi可以通過單位化Gi的零空間向量來求得。否則，wi=fi/1kTfi，其中fi是線性系統
| $G_{i}^{T}{{G}_{i}}{{f}_{i}}={{1}_{k}}$ |
的解。LLE算法在這個線性系統中加入一個小的正數γ，然后通過求解這個正則化的線性系統
| $\left( G_{i}^{T}{{G}_{i}}+\gamma \left\| {{G}_{i}} \right\|_{F}^{2}I \right){{f}_{i}}={{1}_{k}},{{w}_{i}}={{f}_{i}}/1_{k}^{T}{{f}_{i}}$ |
得到局部權。
當Gi有小的奇異值向量時，下面的定理1[11]證明了一組線性無關且近似最優的權向量是存在的。
定理1： 若G∈Rm×k,σ1(G)≥L≥σk(G)是G的k個奇異值，那么對于r＜k，存在k-r個線性無關向量w(j),j=1,…,k-r使得
| $\left\| G{{w}^{\left( j \right)}} \right\|\le \underset{1_{k}^{T}w=1}{\mathop{\min }}\,\left\| Gw \right\|+{{\sigma }_{r+1}}\left( G \right),1_{k}^{T}=1$ |
并且對于W*=[w(1),…,w(k-r)]有
| ${{\left\| G{{w}_{*}} \right\|}_{F}}\le \sqrt{k-r}\underset{1_{k}^{T}w=1}{\mathop{\min }}\,\left\| Gw \right\|+\sqrt{\sum\limits_{j=r+1}^{k}{\sigma _{j}^{2}\left( G \right)}},$ |
將定理1中的G改成Gi，就可以得到ki-ri(ki=｜ji｜是鄰域點的個數)個線性無關的權向量wi(1)，…，w(ki-ri)即
| $w_{i}^{\left( 1 \right)}=\left( 1-{{\alpha }_{i}} \right)w_{i}^{*}+V_{2}^{i}{{H}_{i}}\left( :,l \right),\quad l\le {{k}_{i}}-{{r}_{i}},$ |
其中wi*是的最優解，V2(i)是對應于Gi的ki-ri個最小奇異值的右奇異向量，且hi如下構造
| ${{h}_{i0}}={{\alpha }_{i}}{{1}_{{{k}_{i}}-{{r}_{i}}}}-{{\left( V_{2}^{\left( i \right)} \right)}^{T}}{{1}_{{{k}_{i}}}},{{h}_{i}}=\left\{ \begin{matrix} \frac{{{h}_{i0}}}{\left\| {{h}_{i0}} \right\|}, & {{h}_{i0}}\ne 0 \\ 0, & {{h}_{i0}}=0 \\ \end{matrix} \right.$ |
尋找一個d維嵌入{y1,…，yn}，其中yi∈Rd能夠保持xi和其鄰域點之間更強的線性結構，也就是極小化下列的嵌入價值函數
| $\varepsilon \left( Y \right)={{\sum\limits_{i=1}^{n}{\sum\limits_{l=1}^{{{k}_{i}}-r}{\left\| \sum\limits_{j\in {{J}_{i}}}{w_{ij}^{\left( l \right)}{{y}_{j}}-{{y}_{i}}} \right\|}}}^{2}},$ |
記Wi=[wi(l),…,wi(ki-ri)]為局部權矩陣，將它嵌入到n維空間。記為Rn×(ki-ri)，有
| $\begin{align} & {{{\hat{W}}}_{i}}\left( {{J}_{i}},\,\!: \right)={{W}_{i}},\hat{W}\left( i,\,\!: \right)=-1_{{{k}_{i}}-{{k}_{r}}}^{T}, \\ & \hat{W}\left( j,\,\!: \right)=0,j\notin {{I}_{i}}, \\ \end{align}$ |
其中Ii=JiU{i}。式(13)可重新寫成：
| $\varepsilon \left( Y \right)=\sum\limits_{i}{\left\| Y{{{\hat{W}}}_{i}} \right\|}_{F}^{2}={{Y}_{r}}\left( Y\Phi {{Y}^{T}} \right),$ |
其中
| $\Phi =\sum\limits_{i}{{{{\hat{W}}}_{i}}}\hat{W}_{i}^{T}=\left\lceil {{{\hat{W}}}_{1}},\cdots ,{{{\hat{W}}}_{n}} \right\rceil {{\left\lceil {{{\hat{W}}}_{1}},\cdots ,{{{\hat{W}}}_{n}} \right\rceil }^{T}}。$ |
ε(Y)的極小值就是對應于Φ的從第2到第d+1個最小特征值的特征向量所構成的矩陣Y=[u2,…,ud+1]T。
4 DMLLE算法應用于癌癥基因表達數據
4.1 實驗數據集的預處理
原始的癌癥基因表達數據往往包含著大量的實驗隨機誤差和系統誤差，所以必須在降維處理之前對數據集進行預處理，以減少這些誤差對實驗數據的影響，得到更準確真實的分析結果。首先采用行平均值(row average)的方法[14]對每一個癌癥基因表達數據集進行丟失數據的修補，然后對數據進行對數轉換，最后按照基因對其進行平均值標準化。
4.2 胃癌基因表達數據的實驗結果及分析
胃癌基因表達數據集來源于美國國家生物技術信息中心(NCBI)http://www.ncbi.nlm.nih.gov/的GEO數據庫，它在GEO數據庫中公開的記錄編號為GDS1210。這個數據集是20個原發性晚期胃癌組織的表達譜數據，包括30個樣本的表達譜，其中有8個是正常組織樣本，22個是癌癥組織樣本，每一個樣本包括7 192個基因的表達數據。
分別采用改進距離的LLE和DMLLE算法對表達譜數據進行降維，改進距離的LLE算法中的鄰域參數k設置為7，DMLLE算法中的鄰域參數k設置為15。圖 1(a)是剩余方差隨壓縮維數逐漸增大的變化曲線，曲線在維數為3時出現了比較明顯的拐點，所以確定胃癌基因表達數據的本征維數是3。
圖1
胃癌和白血病數據的剩余方差曲線
(a)胃癌數據剩余方差曲線；(b)白血病數據剩余方差曲線
Figure1. Residual variance curve of gastric cancer and leukaemia data(a) the residual variance curve of gastric cancer data; (b) the residual variance curve of leukaemia data
圖 2是分別采用改進距離的LLE和DMLLE算法把胃癌基因表達數據降到3維的可視化結果。可見DMLLE算法有更好的可視化結果，將正常的和癌癥組織樣本區分的更明顯，而改進距離的LLE算法則差得多。
圖2
胃癌數據改近距離的LLE和DMLLE三維投影圖(o和*表示正常和患有胃癌的樣本)
(a)胃癌數據改進距離的LLE三維投影圖；(b)胃癌數據的DMLLE三維投影圖
Figure2. Improved distance LLE and DMLLE projections of gastric cancer data (o and * show the samples from normal persons or patient,respectively)(a) improved distance LLE projections of gastric cancer data; (b) DMLLE projections of gastric cancer data
4.3 白血病基因表達數據的實驗結果及分析
白血病基因表達數據來自于Getz等[15]實驗中用到的實驗數據集。共包括72個樣本組織，其中47個樣本組織被診斷是急性淋巴細胞白血病ALL，其他25個樣本組織被診斷是急性骨髓細胞白血病AML，實驗采用的基因表達矩陣是1 753個基因的表達數據。
分別采用改進距離的LLE和DMLLE算法對表達譜數據進行降維處理，其中鄰域參數設置為12。圖 1(b)是剩余方差隨壓縮維數的變化曲線，曲線在維數為3時出現了比較明顯的拐點，確定本征維數為3。
圖 3為分別用改進距離的LLE和DMLLE算法將白血病基因表達數據降到三維的可視化結果。可見DMLLE算法有更好的可視化結果，能夠清晰地區分出兩種不同類型的白血病組織樣本。
圖3
白血病數據改進距離的LLE和DMLLE三維投影圖(o和*表示ALL和AML的樣本)
(a)白血病數據改進距離的LLE三維投影圖；(b)白血病數據的DMLLE三維投影圖
Figure3. Improved distance LLE and DMLLE projections of leukaemia data (o and * show the samples from ALL and AML)(a)Improved distance LLE projections of leukaemia data; (b) DMLLE projections of leukaemia data
5 結論
癌癥基因表達數據具有非線性的特點，并且存在大量的冗余基因，不能對數據的分析提供有用的信息，本文引入了一種DMLLE算法，該算法采用一種改進距離計算每個數據點的近鄰點,并且為每個近鄰引入多組線性無關的局部權向量進行線性重構，通過最小化重構誤差得到高維數據在低維空間的嵌入結果。DMLLE算法更適應了樣本分布不均勻的特點，能夠反映出數據集的局部幾何結構。實驗結果表明，DMLLE算法比改進距離的LLE算法可視化效果更好，能清晰地區分出正常和胃癌組織樣本，以及不同類型的白血病組織樣本。利用該算法對基因表達數據進行降維處理，更有利于發現癌癥基因表達數據中潛在的低維流形結構,有助于對癌癥基因表達數據更好地進行分類、聚類分析，為癌癥的臨床診斷和治療提供幫助。
