基于改進標記傳播算法的基因表達譜數據研究

葛芳，郭有強，王磊，馬程

(蚌埠學院 計算機科學與技術系 安徽 蚌埠 233030)

基于改進標記傳播算法的基因表達譜數據研究

葛芳，郭有強，王磊，馬程

(蚌埠學院 計算機科學與技術系 安徽 蚌埠 233030)

提出一種改進的標簽傳播算法，并將其應用于基因表達譜數據分析中．首先使用概率矩陣表示基因表達數據，將少量樣本標記為已知，同時定義一個標記序列表示樣本的類別屬性；然后通過迭代公式更新標記序列，得到標記序列的收斂解，并證明了該收斂解的唯一性；最后采用正負標記的方式，根據標記序列各分量的符號差異實現數據類別的劃分．經過癌癥數據集實驗的驗證，證明了提出的方法可以快速有效地實現基因表達數據的聚類．

半監(jiān)督學習；概率轉移矩陣； 標記傳播； 基因表達譜數據

DNA微陣列技術為腫瘤學提供了一種全新的研究手段．一次基因芯片實驗可以獲得成千上萬個基因的信息，而隨著DNA微陣列技術的進步和儀器設備的更新，基因表達譜數據將不斷積累，這類數據的主要特點是樣本少、維數高、冗余基因和噪聲多，因此，如何對這類“新型”數據進行分析，挖掘其中包含的有效信息，成為生物信息學研究的重點課題．

傳統的基因表達譜分析方法主要是對基因數據進行信息基因選取或特征屬性提取后，再用相應的分類或聚類方法對樣本進行識別[1-2]．其中，聚類是一種無監(jiān)督學習方法，傳統的聚類方法，如K均值[3]、模糊C均值[4]和自組織映射[5]等，都要求數據呈球狀分布，且這些算法易陷入局部最優(yōu)．禤世麗[6]等人針對上述問題，提出了基于粒子對(PPO)與差分進化(DE)混合算法，并結合K-means進行聚類.近年來，基于圖劃分理論的聚類方法成為機器學習領域的研究熱點．2001年，Meila和Shi[7]把圖的節(jié)點的相似性解釋為馬爾科夫鏈中的隨機游走，同時分析了這種隨機游走的概率轉移矩陣的特征向量，并提出了多個特征相似矩陣組合下的譜聚類算法；2006年，Zhu[8]用高斯隨機場的方法處理半監(jiān)督學習問題，提出了標記傳播算法，并根據隨機游走對標記傳播算法進行了概率解釋；2010年，Bai等人[9]將標記傳播進行了擴展，提出了基于上下文分析的圖傳導算法，并將其應用于圖像分割、形狀檢索和匹配等領域．

標記傳播是一種基于圖的半監(jiān)督學習方法，它利用少量已標記類別的樣本，通過傳播標記的方式來識別未知類別的樣本．標記傳播算法能在任意形狀的樣本空間中進行聚類，克服了傳統聚類方法易陷入局部最優(yōu)的缺點，但原始標記傳播算法迭代次數過大，每次迭代前都要重新標記已知類別的樣本，且最終的劃分準則也并不明確．針對上述問題，提出了一種改進的LP算法，并應用于實際的癌癥數據的分析中．癌癥數據集的實驗結果證明了該方法的有效性．

1 基因表達數據的概率轉移矩陣表示

(1)

其中，aij表示基因gj在樣本xi中的表達值．

(2)

其中，dij表示節(jié)點xi和xj之間的歐氏距離，σ是權重參數，通常，σ可以根據節(jié)點xi和xj的K個近鄰的平均距離來自適應調整大小[10]，K是一個經驗值．顯然，對于任意的xi,xj和σ，有0≤Wij≤1，反映了節(jié)點xi和xj之間的親近程度，Wij越大，則節(jié)點xi和xj越有可能屬于同一類．假設xi是一個已標記的節(jié)點，那么從節(jié)點xi轉移到節(jié)點xj的概率為

(3)

其中，di=∑kWik為節(jié)點xi的度，表示與其連接的所有節(jié)點的邊權之和．因此，概率轉移矩陣可表示為

P=D-1W

(4)

2 標記傳播算法

標記傳播的步驟如下：

Step1: 傳播標記，f=Pf；

Step2: 強化標記數據，fL=YL；

Step3: 返回Step1，直到f收斂．

通過第一步，將已標記樣本節(jié)點的標記傳播至相鄰的節(jié)點；此外，在標記的傳播過程中，為保證傳播過程的正確性，已知樣本的標記值不變，用以保持標記數據的強度；算法迭代終止后，標記序列f包含了樣本的類別信息．文獻[8]給出了標記傳播算法的收斂解

(5)

其中，PUU和PUL是概率轉移矩陣P的子矩陣塊，即

(6)

因此，標記傳播算法的解將收斂于一個固定解，需要指出的是，根據式(5)可以直接求出未知樣本的標記．

3 改進的標記傳播算法

通過上述方法任意數據點xi都可以映射為相應的實數值fi，但本文算法在每次迭代前都要重新標記已知樣本，且由于標記傳播過程和標記強化過程的分離，造成算法迭代次數過大；同時，本文算法采用0-1標記，需要選取適合的閾值對樣本進行分類，Zhu等人[8]使用的0.5閾值缺乏穩(wěn)定性，應用于復雜數據時并不能取得很好的效果．

3.1 改進的標記傳播算法

令α表示標記傳播和標記強化的平衡參數，且滿足0<α<1，反映了數據點從其近鄰點獲取的標記信息的比例，將參數α加入迭代公式，在t+1次迭代后，數據點xi的標記為

(7)

其中，f0=(YL,0,…,0)，在每次迭代過程中，數據點從已標記節(jié)點中獲取一部分標記信息；同時，由于相似節(jié)點間的權重較大，數據點可以從其近鄰中獲取一部分標記信息，當傳播終止后，相似節(jié)點的分布情況也趨于一致．因此，迭代公式可以改寫為

(8)

利用式(8)來更新每個數據的標記，直至收斂．這里，并不采用原始LP算法中的0和1標記，而采用正負標記的方式，如對于兩類問題，將其中一類的若干個樣本標記為1，而另一類的若干個樣本標記為-1，對于最終的收斂結果，就能以零為分割點對未知類別的樣本進行劃分．

3.2 收斂性證明

本節(jié)將證明利用上述算法得到的f是收斂的，由式(8)可以得到是收斂的，由式(8)可以得到

(9)

由于Pij>0且∑jPij=1，根據Perron-Frobenius定理[11]，矩陣P的譜半徑小于1；同時，由于0<α<1，因此

(10)

(11)

其中，I為n×n的單位矩陣，因此，ft將收斂于

(12)

因此，本文算法的解也是收斂的．同樣，可以根據式(12)直接求出未知樣本的標記．

4 實驗結果與分析

4.1 實驗數據

選用兩組公開的癌癥數據集：白血病數據(leukemia)，共52個樣本，其中24個樣本被確定為急性淋巴白血病(ALL)，28個被確定為急性粒細胞白血病(AML)，每個樣本含有12564個基因表達數據；結腸癌數據(coloncancer)，共62個樣本，其中22個樣本被確定為正常樣本，40個被確定為腫瘤樣本，每個樣本含有2000個基因表達數據．實驗是在酷睿雙核主頻2.60GHz，內存2G的計算機上運行的．

癌癥基因表達譜數據的獲取過程十分復雜，所得到的數據含有大量的噪聲，同時每個樣本都記錄了組織細胞中所有可測基因的表達水平，但只有較少數基因包含與類別相關的信息，因此，對數據進行預處理是必要的，定義下式對基因表達譜數據進行篩選

(13)

其中，max(i)，min(i)和mean(i)分別表示第i個基因于所有樣本當中表達水平的最大值，最小值和平均值．T為給定的閾值．如果某個基因的表達情況符合式(13)便將該基因剔除．

4.2 白血病數據實驗

將白血病數據的第1號樣本(ALL)標記為1，第52號樣本(AML)標記為-1，分別進行5、10、50、200次迭代，更新每個樣本點的標記，觀察標記序列各分量的變化，結果如圖1所示：

圖1 白血病數據的標記傳播過程 圖2 白血病數據樣本均值

圖1中，標記序列的前24個分量對應的是白血病數據集的ALL樣本，后28個分量對應AML樣本．從圖1中可以看到，當進行5次迭代后，ALL樣本的標記都大于零，而AML樣本的標記都小于零，所有樣本被正確的劃分為兩類，說明該方法可以快速且有效的實現樣本類別的劃分；同時，圖1(c)和(d)變化不明顯，即表示較少次數的迭代便可得到最終結果．另外，ALL樣本中，第3號樣本的分布明顯不同于其他樣本，AML樣本中，第48、49、50、51和52號樣本也不同于其他樣本，這是由數據的分布特點決定的，圖2是白血病數據集中各樣本均值．

4.3 結腸癌數據實驗

將結腸癌數據的第1號樣本(正常組織樣本)標記為1，第62號樣本(腫瘤組織樣本)標記為-1，同樣分別進行5、10、50、200次迭代，結果如圖3所示.

圖3 結腸癌數據的標記傳播過程 圖4 異常樣本被標記為已知的迭代結果

圖3中，標記序列的前22個分量對應的是結腸癌數據集的正常組織樣本，后40個分量對應腫瘤組織樣本．從圖3中可以看到，當經過5次迭代后，兩類樣本標記的區(qū)別并不明顯，但經過10次迭代后，就可以看出兩類樣本的標記的差異性，在正常組織樣本中，第18和20號樣本被錯誤標記，而在腫瘤組織樣本中，第52、55和58號樣本被錯誤標記，分類準確率達到91.94%，實際情況中，這些樣本中含有較多的偏離值和異常點；同時，進行50次和200迭代后，樣本標記的變化已經不明顯，同樣說明了該方法可以快速實現標記序列的收斂．

為了觀察初始標記點對最終迭代結果的影響，分別將結腸癌數據中被錯誤標記的第18、55和58號樣本標記為已知，結果如圖4所示．

圖4(a)中僅標記了第1和62號樣本；圖4(b)除標記第1和62號樣本外，同時將第18號樣本標記為1；圖4(c)、(d)除標記第1和62號樣本外，分別將第55號和58號樣本標記為-1．由圖4(b-c)可知，當將第18或55號樣本標記為已知，那么與第18或55樣本相似的樣本，其標記值也趨向于與第18或55樣本相似(實際表現為樣本標記值的絕對值減小)．由圖4(d)可知，當將第58號樣本標記為已知，第13至22號樣本全部被錯誤標記，同時第1至12號樣本的標記值的絕對值減小，這同樣是由于在標記傳播過程中，某個樣本的標記是根據其近鄰樣本點的標記進行更新的．因此得出結論，在試驗中，若把異樣表達的樣本標記為已知，與該樣本表達相似的樣本趨向于已標記的異樣表達樣本，便會出現樣本被錯誤標記的現象．

4.4 對比驗證

為進一步驗證該方法的正確性，設計了兩組對比實驗：

第一組實驗：將該方法與局部線性嵌入(LLE)算法[12-13]和NJW譜聚類算法[14]進行對比．LLE是一種非線性特征提取算法，先以LLE進行特征提取，再用KNN對樣本進行分類；NJW算法采用規(guī)范化相似矩陣的前K個最大特征值對應的特征向量作為數據的特征表示，再用K均值等對特征空間的樣本點進行聚類．結果如表1所示：

表1 本文方法與基于圖的方法的實驗結果比較

由表1可知，從準確率方面，本文方法明顯優(yōu)于另外兩種基于圖的方法，LLE算法是一種有效的可視化方法，但要求數據服從流形分布，其提取的特征并不具有很強的分類能力；NJW算法屬于無監(jiān)督學習，提取的特征向量未必能反映數據結構；而本文方法利用已知樣本的類別標記對未知樣本的標記進行傳播，在傳播過程中，某個樣本的標記是根據其近鄰樣本點的標記進行更新的，最后得到的收斂結果也更符合原始數據分布的特點．同時，在時間效率上，本文方法并不具有明顯的優(yōu)勢，這是因為這幾種方法都是利用構圖的方法將高維樣本映射到低維空間，構造的矩陣規(guī)模是相同的．

第二組實驗：將本文方法與傳統的S2N_KNN法[1]和CLUSTER_S2N[4]進行對比，S2N_KNN以“信噪比”為指標選取特征基因，再用K-近鄰(KNN)分類器對樣本進行分類；CLUSTER_S2N先用K均值將數據聚類，再以“信噪比”選取特征基因，最后用支持向量機(SVM)實現樣本的分類．結果如表2所示：

表2 本文方法與傳統方法的實驗結果比較

由表2可知，無論從準確率還是運算效率等方面，本文方法都優(yōu)于另外兩種傳統方法，由于基因之間普遍存在相關性，傳統方法以降維來提取特征基因勢必會丟失部分含有分類信息的基因，而本文方法將樣本數據作為高維空間中的點，所構造的概率轉移矩陣反映了樣本之間的關系，使得原來的樣本分類信息完全映射到低維的概率轉移矩陣中．同時，在時間效率上，提出的方法同樣優(yōu)于后兩種方法，這是因為傳統方法在前期處理中對高維數據進行復雜運算，進行一次甚至多次降維處理，而提出的方法首先以樣本為節(jié)點構圖，其低樣本特性決定了構造的矩陣規(guī)模較小，從而具有較低的運算復雜度，有利于基因表達數據的快速分類．

5 結 語

基于圖的半監(jiān)督學習是當前模式識別領域的研究熱點．提出一種改進的標記傳播算法，本文算法通過引入標記傳播過程和標記強化過程的平衡參數，克服了傳統標記傳播算法迭代次數過大和重復標記數據點的缺點；同時在數據類別劃分時使用正負標記的方式，避免了采用0-1標記時閾值選取的不確定性．通過癌癥數據的實驗，證明了該方法可快速且有效地實現基因表達譜數據的聚類．

[1]GULOBTR,SLONIMDK,TAMAYOP,etal.Molecularclassificationofcancer:classdiscoveryandclasspredictionbygeneexpressionmonitoring[J].Science, 1999, 286(5439):531-537.

[2]KANCHERLAK,MUKKAMALAS.FeatureselectionforlungcancerdetectionusingSVMbasedrecursivefeatureeliminationmethod[J].MachineLearningandDataMininginBioinformatics, 2012, 7246:168-176.

[3] 禤浚波, 吳小霞, 王珍珍,等. 基于粒子對和極值優(yōu)化的基因聚類混合算法研究[J]. 計算機應用研究, 2011, 28(10):3675-3677，3680.

[4]TARIL,BARALC,KIMS.Fuzzyc-meansclusteringwithpriorbiologicalknowledge[J].JournalofBiomedicalInformatics, 2009, 42(1):74-81.

[5]PATTERSONAD,LIH,EICHLERGS,etal.UPLC-ESI-TOFMS-basedmetabolomicsandgeneexpressiondynamicsinspectorself-organizingmetabolomicmapsastoolsforunderstandingthecellularresponsetoionizingradiation[J].AmericanChemicalSociety, 2008, 80(3):665-674.

[6] 禤世麗,楊秋葉，張超英,等. 基于粒子對和差分進化的基因表達數據聚類[J]. 計算機應用研究, 2012, 29(7):2484-2487.

[7]MELIAM,SHIJin-bo.Learningsegmentationbyrandomwalks[J].InAdvancesinNeuralInformationProcessing，2000, 10(2):873-879.

[8]ZHUXiao-jin.Semi-Supervisedlearningwithgraphs[D].Doctoraldissertation,CarnegieMellonUniv,CMU-LTI-05-192,2005.

[9]BAIXiang,YANGXing-wei,LATECKILJ,etal.Learningcontext-sensitiveshapesimilaritybygraphtransduction[J].IEEETransactionsonPatternAnalysisandMachineIntelligence, 2010, 32(5):861-874.

[10]ZELNIK-MANORL,PERONAP.Self-tuningspectralclustering[J].AdvancesinNeuralInformationProcessingSystems, 2004, 17(2):1601-1608.

[11]GOLUBGH,VANLOANCF.Matrixcomputatio[M].Baltimore:TheJohnsHopkinsUniversityPress, 1996.

[12]PILLATIM,VIROLIC.Supervisedlocallylinearembeddingforclassication[A].anapplicationtogeneexpressiondataanalysis[C].Proceedingsof29thAnnualConferenceoftheGermanClassicationSociety(GfKl2005), 2005.15-18.

[13]ZHAOLing-xiao,ZHANGZheng-yue.Supervisedlocallylinearembeddingwithprobability-baseddistanceforclassification[J].ComputersandMathematicswithApplications, 2009, 57: 919-926.

[14]NGAY,JORDANMI,WEISSY.Onspectralclustering：analysisandanalgorithm[C].DIETTERICHTG,BECKERS,GHAHRAMANIZ.AdvancesinNeuralInformationProcessingSystems,Cambridge,MA:MITpress, 2002,849-85.

[責任編輯：王軍]

The analysis of gene expression profiles based on improved label propagation algorithm

GE Fang，GUO Youqiang, WANG Lei, MA Cheng

(Department of Computer Science and technology, Bengbu College, Bengbu 233030, China)

In this paper, an improved label propagation algorithm was proposed and introduced into the analysis of gene expression profiles. First, the probability transition matrix was constructed with gene expression profiles. Meanwhile, the label sequence which indicates the class information was defined and several samples were marked as labeled data. Then, the label sequence was updated by an iterative formula and the convergence solution of the label sequence was obtained, which was proved to be the unique solution. Finally, the clustering problem was solved by using plus-minus label which was on the basis of the signs of the label sequence. Experiments on the cancer data demonstrate our method is feasible and effective.

semi-supervised learning; probability transition matrix; label propagation; gene expression profile data

2015-03-02

安徽省自然科學基金資助項目(No.11040606M151)；蚌埠學院自然科學基金資助項目(No.2014ZR26，No.2013ZR06)

葛芳(1986-), 女, 安徽亳州人, 蚌埠學院助教, 碩士研究生, 主要從事模式識別、計算生物學的研究; 郭有強(1966-), 男, 蚌埠學院教授,博士, 碩士生導師, 主要從事為數據挖掘、機器學習的研究.

TP 18

A

1672-3600(2015)06-0063-06