基于雙正交非負(fù)矩陣三因式的腫瘤識別

譚青青，王 年，蘇亮亮，方正文

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

DNA微陣列是分子生物學(xué)在實驗領(lǐng)域的一項重大突破，它已經(jīng)成為分子診斷的一個重要手段.隨著DNA微陣列技術(shù)的出現(xiàn)和不斷發(fā)展，產(chǎn)生的基因表達(dá)譜數(shù)據(jù)規(guī)模日趨龐大，而這類數(shù)據(jù)的主要特點是基因維數(shù)大而樣本維數(shù)小.因此，如何對腫瘤基因進(jìn)行有效分析，繼而從海量的數(shù)據(jù)中提取出有意義的生物學(xué)信息就成了生物信息學(xué)研究的重點問題之一［1－2］.通過檢測基因表達(dá)的變化，可以為疾病的診斷和預(yù)測提供新的目標(biāo).到目前為止，已經(jīng)有很多算法適合于處理高維數(shù)據(jù)集，如支持向量機(jī)［3］、隨機(jī)森林［4］、貝葉斯法［5］等，這些算法都已經(jīng)應(yīng)用到了各種腫瘤樣本的分類和聚類中.各種特征選擇的方法也已經(jīng)被提出并不斷發(fā)展，以便于準(zhǔn)確鑒定相關(guān)疾病基因.當(dāng)前對于基因表達(dá)譜數(shù)據(jù)分析和挖掘的一般方法是對基因數(shù)據(jù)進(jìn)行特征提取后，再用相應(yīng)的分類或聚類方法對腫瘤樣本進(jìn)行識別［6－7］.1999年，Golub等［8］以“信噪比”為指標(biāo)對白血病的兩個亞型樣本進(jìn)行分類研究；Lee和Seung等首次提出了NMF［9］的概念，它是一種特征提取和降維的新方法.隨著NMF在現(xiàn)實生活中的廣泛應(yīng)用，NMF算法的缺點也顯現(xiàn)出來了.2008年，李樂等對各種非負(fù)矩陣分解算法進(jìn)行了總結(jié)［10］；Cichocki等把稀疏懲罰項和SED（square of euclidian distance）結(jié)合作為目標(biāo)函數(shù)，并對迭代規(guī)則進(jìn)行了修改，得到了稀疏性增強(qiáng)的NMF［11］；Hoyer提出了可精確控制稀疏性的算法 NMFSC（NMF with sparseness constraints）［12］.Wang等把Fisher鑒別信息作為懲罰項加入到目標(biāo)函數(shù)中，構(gòu)造了FNMF（Fisher NMF）算法［13］，使得分解結(jié)果中蘊含較多的分類信息.

論文所介紹的正交非負(fù)矩陣三因式分解算法是一種改進(jìn)的NMF方法［14］.一般的NMF算法采用隨機(jī)初始化，而論文將K－均值聚類作為BONMTF算法的初始化步驟，這樣做提高了算法的效率.實驗采用了4組具有代表性的腫瘤基因表達(dá)譜數(shù)據(jù)進(jìn)行研究，其結(jié)果證明了該方法的可行性和有效性.

1 NMF算法

1999年，Lee和Seung第一次提出了NMF的基本框架［9］.假設(shè)矩陣X＝（xij）m×n為一個m×n的矩陣，矩陣X中的所有元素值都是非負(fù)的.非負(fù)矩陣分解（NMF）算法就是將矩陣X分解成兩個非負(fù)矩陣其中：矩陣U∈Rm×k＋，V∈Rk×n＋，通常k的值要遠(yuǎn)遠(yuǎn)小于m和n，則獲得的子矩陣U和V的維數(shù)得到了降低，一個非負(fù)矩陣分解成了另外兩個非負(fù)矩陣相乘的形式.

矩陣X的一行可以寫成矩陣V的列的線性組合，即

其中：xj表示矩陣X的一行，vi表示矩陣V的一列，而uji表示矩陣U中的元素.此模型如圖1所示，在這個模型中，可以將矩陣V的k行作為基向量，而將矩陣U的行作為編碼系數(shù).此模型可以用于腫瘤分類的特征提取中，特征為矩陣U的行.經(jīng)過優(yōu)化U和V使之與矩陣X線性近似.

矩陣分解實際上是數(shù)據(jù)最優(yōu)化過程，因此需要定義一個目標(biāo)函數(shù)來量化近似度，并通過更新迭代規(guī)則來減小此函數(shù).此目標(biāo)函數(shù)可定義為

當(dāng)UV與X偏離越大時，R的值也隨之增大；當(dāng)UV越接近于X時，R的值隨之減小.從而R的大小能夠衡量UV與X的近似程度.使用迭代逼近的方法找到滿足式（1）的兩個矩陣，并使得R為非增的，則可使用如下的迭代規(guī)則

2 雙正交非負(fù)矩陣三因式分解BONMTF

2.1 BONMTF算法

針對NMF算法的缺點，2006年，Chris Ding和Tao Li等第一次提出了雙正交三因式非負(fù)矩陣分解和對稱三因式非負(fù)矩陣分解的概念［14］，并給出了BONMTF迭代公式的計算規(guī)則.論文主要將正交非負(fù)矩陣三因式分解用于文件聚類，并給出了二因式NMF迭代規(guī)則的詳細(xì)證明.

假設(shè)X＝（xij）m×n為一個m×n的矩陣，其每一行代表在同一樣本中所有基因的表達(dá)值，X中的所有元素值都為非負(fù)的.而每一列代表了一個基因在不同樣本中的表達(dá)值.BONMTF分解就是分解成3個矩陣相乘的形式

使得

然而只有當(dāng)三因式NMF不能轉(zhuǎn)化為二因式NMF時，此研究才有意義.也就是說需要給三因式NMF施加一定的約束.顯然式（7）沒有與之相對應(yīng)的二因式，稱之為雙正交三因式分解，且其為論文的研究重點.可以通過使用以下的更新規(guī)則來計算D的值

2.2 論文算法

論文將BONMTF算法應(yīng)用于基因表達(dá)譜數(shù)據(jù)的分析.論文算法的基本步驟為：

（1）利用Fisher判別準(zhǔn)則對基因表達(dá)譜數(shù)據(jù)進(jìn)行預(yù)處理，得到去除無關(guān)基因后的基因子集，并對所得的基因子集數(shù)據(jù)進(jìn)行歸一化處理.

對基因表達(dá)譜數(shù)據(jù)進(jìn)行深入分析和挖掘，是基因表達(dá)譜數(shù)據(jù)分析的根本內(nèi)容［1］.但是，由于癌癥基因表達(dá)譜數(shù)據(jù)的復(fù)雜性，所得的微陣列數(shù)據(jù)中只有較少的基因包含和類別相關(guān)的信息，因此要對基因表達(dá)譜數(shù)據(jù)進(jìn)行預(yù)處理.簡單的處理方法即按照某種記分準(zhǔn)則來對每一個基因進(jìn)行記分，所得分值越大則說明該基因越重要；再按照分值的大小對基因進(jìn)行降序排列，選取排在前面的一定數(shù)量的基因作為篩選的基因子集，從而初步去除了無關(guān)基因和噪聲，即實現(xiàn)了樣本維數(shù)的約減.論文選取Fisher判別準(zhǔn)則對基因表達(dá)譜數(shù)據(jù)進(jìn)行預(yù)處理，其基因的記分準(zhǔn)則表示為

（2）利用BONMTF算法提取特征向量，以此來進(jìn)一步剔除冗余基因，得到能夠表征樣本屬性的矩陣.

3 用SVM分類器實現(xiàn)腫瘤樣本類型的識別

在二因式NMF的基礎(chǔ)上，給出了BONMTF算法的正確性和收斂性的證明，即旨在解決以下優(yōu)化問題

使得

其中：X為非負(fù)輸入矩陣.

根據(jù)約束優(yōu)化問題的標(biāo)準(zhǔn)理論，引入了拉格朗日乘數(shù)λ，并最小化拉格朗日函數(shù)L1（F），如下式

L1（F）的梯度為

由非負(fù)Fik的KTT互補條件，得

為了求解式（15）的耦合方程以及求解滿足約束條件FTF＝I的F和λ，可以利用非線性的方法如牛頓法求解.然而非線性方程一般是很難解的，在這里可以利用一個更簡單的算法即利用式（9）的更新規(guī)則來求解.但是在這里出現(xiàn)了兩個問題，即該算法是否是正確且收斂的.因此，下面給出了該算法正確性和收斂性的證明.

正確性：首先給出F的一個初始化預(yù)測，然后通過利用以下公式的連續(xù)更新而收斂到一個局部最小值.

正確性是由收斂性來保障的，其解將滿足式（15），拉格朗日乘數(shù)λ將在接下來的式（27）中給出.

收斂性：單調(diào)性定理保證了收斂性.論文利用命題1和定理1［14］來證明收斂性.

證明 令Sip＝S′ipuip，則差值Δ＝LHS－RHS可以寫成

由于矩陣A和B都為對稱矩陣，則上式等價于

當(dāng)B＝I，S為一個列向量.命題1為證明定理1做好了準(zhǔn)備.

定理1 根據(jù)式（16）的迭代規(guī)則，假定SGTGSΤ＋λ≥0時，拉格朗日函數(shù)L1（F）為單調(diào)遞減（非增）函數(shù).

證明 在這里使用輔助函數(shù)的方法［15］，一個函數(shù)Z（H，H，）若滿足以下條件，則被稱為L（H）的輔助函數(shù)

對于任意的H和，定義

Z（F，F(xiàn)′）為L1（F）的一個輔助函數(shù).由命題1可得，其滿足式（20）的條件.現(xiàn)在，根據(jù)式（21）可知，需要找到固定F′時，f（F）＝Z（F，F(xiàn)′）的全局最小值，而局部極小值可由下式給出

求解Fik，極小值為

由于海賽矩陣?Z（F，F(xiàn)′）／Fik?Fjl是正定的.因此，這是一個凸函數(shù)，且極小值即為全局最小值.在式（16）中，有（－FΤXGSΤ＋SGΤGSΤ＝λ）kk＝0.因此，可以獲得拉格朗日的對角元素為

拉格朗日因子的非對角元素是通過設(shè)定?L／?Fik＝0近似獲得的，由式（14），可以得出下式

結(jié)合式（25）和（26），可以得到拉格朗日乘數(shù)

將式（27）代入式（16）中，可以獲得式（9）的迭代規(guī)則.

這里值得注意的是，由于拉格朗日因子Λ＝λkl的非對角元素是近似獲得的，因此最后的解F并不恰好滿足FΤF＝I.這實際上卻是一個優(yōu)勢，如果FΤF正好等于I，根據(jù)非負(fù)性，F(xiàn)的每一行只能有一個非零元素.而對FΤF＝I的輕微偏離卻能夠允許一行中的所有元素非零（盡管大多數(shù)值都很小）.

類似地，對于給定的F和S，可以使用式（8）的迭代規(guī)則來更新G，證明的方法與上述方法類似.綜上所述，論文可以通過式（8）、（9）來證明式（7）的最小化過程；對于給定的F和G，可使用式（10）來更新矩陣S的迭代規(guī)則，下文給出了證明［14］.

定理2 令F和G為固定的矩陣，則

是單調(diào)遞減的.

證明 首先需要證明正確性.利用Sik的非負(fù)性和KTT互補條件，可以得出

由于式（10）的迭代規(guī)則滿足上式，則證明了式（10）的正確性.接下來需要考慮式（10）的收斂性.

定理3 目標(biāo)函數(shù)J2（S）在式（10）的迭代規(guī)則下是為非增的.

證明 同樣可以使用輔助函數(shù)的方法來證明.其中

為J2（S）的一個輔助函數(shù)，根據(jù)式（21），當(dāng)固定S′＝S（t）時，通過最小化J（S，S′）可以得到S（t＋1），最小值為

根據(jù)式（21），可以更新式（10）.在這個更新規(guī)則下，J2（S）為單調(diào)遞減的.

由于一般的NMF算法采用隨機(jī)初始化，這導(dǎo)致算法的效率低，且算法的復(fù)雜度較高.為了提高算法的效率及降低算法復(fù)雜度，論文算法是首先使用K－均值聚類作為BONMTF的初始化步驟，即利用K－均值聚類產(chǎn)生矩陣F和G的初始矩陣，這樣做的好處是減小了最優(yōu)解的尋找區(qū)間，即可以節(jié)省時間，且使得結(jié)果更加穩(wěn)定.對矩陣S，采用下式來進(jìn)行初始化

由于在初始化過程中，F(xiàn)、G以及矩陣X都是已知的，從而根據(jù)上式可以求得初始矩陣S.

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

4.1 數(shù)據(jù)實驗

選用4組公開的且具有代表性的數(shù)據(jù)集：① 白血病數(shù)據(jù)（Leukemia），共52個樣本，其中24個樣本被確定為急性淋巴白血?。╝cute lymphoblastic leukemia，簡稱ALL），28個樣本被確定為急性粒細(xì)胞白血?。╝cute myelold leukemia，簡稱AML），每個樣本含有12 564個基因表達(dá)數(shù)據(jù)；② 前列腺癌數(shù)據(jù)集（prostate cancer），共102個樣本，其中50個樣本為正常樣本，52個樣本被確定為腫瘤樣本，每個樣本含有12 600個基因表達(dá)數(shù)據(jù)；③ 彌漫大B細(xì)胞淋巴瘤（diffuse large B－cell lymphoma，簡稱DLBCL）數(shù)據(jù)集，共77個樣本，其中58個樣本為正常樣本，19個樣本被確定為腫瘤樣本，每個樣本含有5 469個基因；④ 結(jié)腸癌數(shù)據(jù)（colon cancer），共62個樣本，其中22個樣本為正常樣本，40個被確定為腫瘤樣本，每個樣本含有2 000個基因表達(dá)數(shù)據(jù).

利用Fisher準(zhǔn)則分別對白血病、前列腺癌、結(jié)腸癌以及彌漫大B細(xì)胞瘤的基因表達(dá)譜數(shù)據(jù)計算每個基因的得分，如圖2所示.由圖2可以看出有些基因的得分高而有些基因的得分低，而分值越高則表明含有越多的分類信息，所以需要保留得分高的基因，去除得分低的基因，以此來對基因集合進(jìn)行初選，去除無關(guān)基因.

4.2 實驗分析

論文采用留一法進(jìn)行測試，即在整個數(shù)據(jù)集中，始終保留一個樣本作為測試樣本，剩下的樣本作為訓(xùn)練樣本，直至所有的樣本都作為一次測試樣本為止.

癌癥數(shù)據(jù)集的實驗按照如下步驟進(jìn)行：先利用Fisher準(zhǔn)則計算所有基因的得分，并通過對所計算的得分進(jìn)行降序排列，再選取排在前面的一定數(shù)量的基因作為篩選的基因子集.通過大量實驗發(fā)現(xiàn)選取前90個基因作為基因子集時，可以獲得較好的實驗結(jié)果；將所得的基因子集數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理，再利用BONMTF提取特征向量，以此來進(jìn)一步剔除冗余基因，得到能夠表征樣本屬性的矩陣F，然而F的維數(shù)k的不同將會影響最終的分類結(jié)果.因此要選擇合適的k值，這樣不僅使得類別信息得到凸顯，還使得冗余信息得到消除.圖3給出了在不同k值的情況下4個癌癥數(shù)據(jù)集的分類情況.最后利用SVM分類器實現(xiàn)樣本腫瘤類型的識別.

由圖3可知，對于白血病、結(jié)腸癌和彌漫大B細(xì)胞淋巴瘤而言，當(dāng)k值為2時，在實驗中取得的樣本分類的正確識別率相對較高，隨著k值的增加，樣本分類的正確識別率慢慢降低，最終趨于穩(wěn)定.而對前列腺癌來說，當(dāng)k值為3時分類正確率相對較高.這表明，當(dāng)k值為2和3時，樣本屬性矩陣F最能反映樣本的分類特性.如在白血病的實驗中，正確識別率接近100%，這說明在樣本屬性矩陣F中包含了完整的分類信息，可以對樣本集合中的所有樣本進(jìn)行正確分類.因此此時利用BONMTF算法獲得的矩陣F為最佳的分類特征矩陣.

然而在基因表達(dá)譜數(shù)據(jù)分類的方法中，很多方法并沒有普遍適用性，即可能針對某種數(shù)據(jù)的分類效果很好，但是對于其他數(shù)據(jù)，其分類效果并不理想.為了進(jìn)一步驗證論文的可行性、有效性以及普遍適用性，作者將論文方法與傳統(tǒng)的S2N－SVM［16］法、Cluster－S2N［17］方法以及傳統(tǒng)的 NMF法進(jìn)行比較.S2N－SVM以“信噪比”為指標(biāo)來選取特征基因，再利用SVM分類器對樣本進(jìn)行分類.Cluster－S2NSVM方法中的特征選取和分類器有關(guān)，先從初始特征集合中選擇一個特征子集，并在此子集所包含的信息的基礎(chǔ)上構(gòu)建新的特征集合，最后結(jié)合SVM實現(xiàn)分類.如表1所示.

表1 論文方法與另外3種方法的實驗結(jié)果比較Tab.1 Comparisons of experiment results with other three methods

由表1可知，對于4組不同的腫瘤數(shù)據(jù)集，論文算法的識別率都達(dá)到了90%以上，明顯優(yōu)于其他3種方法.這是因為該算法能夠提取到1組數(shù)量更少卻更具樣本分類能力的特征基因.雖然傳統(tǒng)NMF方法對于白血病的識別率也接近100%，但是對于其他3組數(shù)據(jù)集，其分類效果不如論文的方法.這說明論文算法具有相當(dāng)?shù)目尚行砸约捌毡檫m用性.

5 結(jié)束語

NMF已經(jīng)被廣泛地用于圖像分析、論本聚類以及癌癥的發(fā)現(xiàn)與分類.論文結(jié)合雙正交和三因式的思想，提出了一種改進(jìn)的NMF算法，稱之為BONMTF算法，并將其應(yīng)用于基因表達(dá)數(shù)據(jù)分析.該方法包括高維基因表達(dá)數(shù)據(jù)的基因選擇和特征提取兩個步驟，最后利用SVM進(jìn)行分類.論文計算了BONMTF算法的更新規(guī)則，并證明了此算法的收斂性和正確性.通過4組癌癥數(shù)據(jù)的實驗，證明了該方法在預(yù)測人體組織中正常樣本和腫瘤樣本的有效性和高效性，即有效地提高了預(yù)測的精度并降低了算法的時間復(fù)雜度，具有廣泛的應(yīng)用前景.

［1］黃德雙.基因表達(dá)譜數(shù)據(jù)挖掘方法研究［M］.北京：科學(xué)出版社，2009：20－66.

［2］莊振華，王年，李學(xué)俊，等.癌癥基因表達(dá)數(shù)據(jù)的熵度量分類方法［J］.安徽大學(xué)學(xué)報：自然科學(xué)版，2010，34（2）：73－76.

［3］Buturovic L J.PCP：aprogram for supervised classification of gene expression profiles［J］.Bioinformatics，2006，22（2）：245－247.

［4］Nannapaneni P，Hertwig F，Depke M，et al.Defining the structer of the general stress regulon of Bacillus subtilis using targeted microarray analysis and random forest classification［J］.Microbiology，2012，158（3）：696－707.

［5］Nanni L，Brahnam S，Lumini A.Combining multiple approaches for gene microarray classification［J］.Bioinformatics，2012，28（8）：1151－1157.

［6］阮小剛，李曉明，王金蓮.邊介數(shù)聚類算法在腫瘤基因表達(dá)譜中的應(yīng)用［J］.北京工業(yè)大學(xué)學(xué)報：自然科學(xué)版，2008，34（7）：696－700.

［7］Ancherla K，Mukkamala S.Feature selection for lung cancer detection using SVM based recursive feature elimination method［M］.Berlin Heidelberg：Springer，2012，168－176.

［8］Golub T R，Slonim D K，Tamayo，et al.Class discover and class prediction by gene expression monitoring［J］.Molecular classification of Cancer，1999，256（5439）：531－527.

［9］Lee D D，Seung H S.Learning the parts of objects by nonnegative matrix factorization［J］.Nature，1999，401（6755）：788－791.

［10］李樂，章毓晉.非負(fù)矩陣分解算法綜述［J］.電子學(xué)報，2008，36（4）：737－743.

［11］Cichocki A，Amory S，Zdunek R，et al.Extended SMART algorithms for non－negative matrix factorization［M］.Berlin Heidelberg：Springer，2006：548－562.

［12］Hoyer P O.Non－negative factorization with sparseness constraints［J］.J of Mach Learning Res，2004，5（9）：1457－1469.

［13］Wang Y，Jia Y，Hu C，et al.Fisher non－negative matrix factorization for learning local features［C］／／Proc of Asian Conf on Comp Vision，2004：27－30.

［14］Ding C，Li T，Peng W，et al.Orthogonal nonnegative matrix tri－factorization for clustering［C］／／Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2006：126－135.

［15］Lee D D，Seung H S.Algorithms for non－negative matrix factorization［J］.Advances in Neural Information Processing Systems，2001，13（1）：556－562.

［16］Singh D，F(xiàn)ebbo P G，Ross K，et al.Gene expression correlates of clinical prostate cancer behavior［J］.Cancer Cell，2002，1（2）：203－209.

［17］阮小剛，晁浩.腫瘤識別過程中特征基因的選?。跩］.控制工程，2007，14（4）：373－375.