張 旭,陳志奎,高 靜

(大連理工大學(xué) 軟件學(xué)院,遼寧 大連 116620)

1 引 言

隨著計(jì)算機(jī)科學(xué)的發(fā)展,傳統(tǒng)的數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)方法得以橫跨多個(gè)學(xué)科,在諸多領(lǐng)域得到重要的應(yīng)用.例如,醫(yī)學(xué)疾病的診療和生物學(xué)研究過程中,組織細(xì)胞的基因表達(dá)譜能夠以高維數(shù)據(jù)的形式導(dǎo)出,這為應(yīng)用數(shù)據(jù)挖掘手段對其進(jìn)行進(jìn)一步分析和處理提供了可能.然而受限于現(xiàn)有獲取方式,所有檢測到的基因全部被導(dǎo)出,實(shí)際起表達(dá)作用的基因可能在其中只占小部分.這導(dǎo)致得到的基因譜數(shù)據(jù)集往往規(guī)模龐大、形式復(fù)雜,維度遠(yuǎn)大于樣本實(shí)例數(shù);同時(shí)包含大量冗余,傳統(tǒng)數(shù)據(jù)挖掘算法難以發(fā)揮其性能.

為解決該問題,對原始基因表達(dá)譜數(shù)據(jù)進(jìn)行維數(shù)約簡[1]是最行之有效的方法之一.該方法通過對原始數(shù)據(jù)空間進(jìn)行數(shù)學(xué)投影變換以獲得新的特征空間.較之原始空間,該空間維度大幅精簡,概括能力更強(qiáng),因而可以更好地描述基因數(shù)據(jù).而基因數(shù)據(jù)通常以矩陣形式進(jìn)行存儲,對大規(guī)模數(shù)據(jù)的處理可直觀理解為高維矩陣的分析,這就為使用矩陣分解方法進(jìn)行維度約簡提供了條件.傳統(tǒng)含負(fù)分解方法由于分解結(jié)果中的負(fù)元素缺乏直觀的物理意義[2],在實(shí)際應(yīng)用中有著很大局限性.另一方面,因?yàn)榛驑颖疽?guī)模龐大,且樣本之間存在相互聯(lián)系,線性變換的過程中可能會破壞基因譜數(shù)據(jù)的內(nèi)部結(jié)構(gòu).故此,基于非負(fù)矩陣分解思想的方法由于實(shí)現(xiàn)了原始矩陣維數(shù)的非線性約減,且通過非負(fù)約束保證了分解后元素的物理意義,甫一提出便得到了廣大研究人員的重視.1999年,Lee和Seung在前人研究基礎(chǔ)上進(jìn)行總結(jié)歸納,于《Nature》上首次正式提出非負(fù)矩陣分解方法(Non-negative matrix factorization,NMF)[2]的概念,并證明了其收斂性,為矩陣分解問題開辟了新的思路.其后的十幾年里,非負(fù)矩陣分解研究方興未艾,廣大學(xué)者紛紛將NMF方法進(jìn)行推廣和改進(jìn).時(shí)至今日,NMF已被廣泛應(yīng)用到基因及細(xì)胞分析領(lǐng)域的研究中[3].并逐漸成為最受歡迎的多維數(shù)據(jù)處理工具之一.NMF在維數(shù)約簡上有著得天獨(dú)厚的優(yōu)勢:通過結(jié)合流形學(xué)習(xí),能夠較為完整地保持?jǐn)?shù)據(jù)原有的內(nèi)部空間結(jié)構(gòu);添加稀疏約束后,也可以較好地抑制噪聲.迄今為止,已有很多學(xué)者將稀疏的判別信息與流形思想相結(jié)合,對NMF算法進(jìn)行改進(jìn)[4,5].

流形學(xué)習(xí)(Manifold Learning)是近年來流行的機(jī)器學(xué)習(xí)方法.流形思想將高維數(shù)據(jù)映射至低維空間以揭示數(shù)據(jù)的本質(zhì)結(jié)構(gòu),在維數(shù)約簡上得到廣泛應(yīng)用[6].Cai等人將該思想引入,提出圖正則化非負(fù)矩陣分解(Graph Regularized nonnegative matrix factorization,GRNMF)[7],并在之后通過一系列研究對其應(yīng)用方式進(jìn)行拓展,進(jìn)一步提升了非負(fù)矩陣分解保存原始數(shù)據(jù)局部特征的能力[8].

非負(fù)約束使得基于非負(fù)矩陣分解的方法其結(jié)果天然具有一定程度的稀疏性.從數(shù)據(jù)角度這意味著分解得到的矩陣中將包含很多0元素.NMF在稀疏性的作用下,得以使用更少元素表示原有數(shù)據(jù),節(jié)省存儲空間,為數(shù)據(jù)表達(dá)提供一種高效的策略[9].在實(shí)際應(yīng)用中,這種天然的稀疏性往往不夠充分,基于實(shí)際需求,研究人員常結(jié)合稀疏表示理論,在目標(biāo)函數(shù)中引入稀疏性約束,以合理控制NMF結(jié)果的稀疏程度,達(dá)到更優(yōu)的分解效果,使結(jié)果更具實(shí)際應(yīng)用意義.稀疏編碼思想與NMF相結(jié)合的方法由Hoyer在2002年首先提出,該方法利用歐氏距離的平方加上l1范數(shù),得到一種非負(fù)稀疏編碼(Nonnegative sparse coding,NNSC)算法,并通過實(shí)驗(yàn)證明了其分解結(jié)果在稀疏程度上的優(yōu)勢[10].隨后Hoyer對NNSC算法作了進(jìn)一步改良,利用非線性投影實(shí)現(xiàn)對稀疏性的精確控制,給出一種介于l1范數(shù)和l2范數(shù)之間的稀疏度計(jì)算準(zhǔn)則并提供相應(yīng)軟件包,極大地促進(jìn)了稀疏約束NMF研究和應(yīng)用的發(fā)展[9].

通常使用的l1約束在分解含噪聲數(shù)據(jù)時(shí),稀疏表示的有效性受到干預(yù),結(jié)果可能仍含有較多噪聲,影響降噪效果[11].徐宗本等人針對l1稀疏性問題提出了更加稀疏的l1/2正則理論,并對求解算法和收斂性進(jìn)行了分析[11].很多學(xué)者也對lq范數(shù)約束在q取不同值時(shí)對NMF算法稀疏性的影響進(jìn)行研究,驗(yàn)證了l1/2約束在稀疏性表示上的優(yōu)勢[12].近年來,已有更多算法使用了l1/2約束的思想[13,14].

綜上所述,針對基因表達(dá)譜數(shù)據(jù)高維度、高冗余的特點(diǎn),本文提出了一種基于非負(fù)矩陣分解的算法,結(jié)合圖正則化思想和使用l1/2范數(shù)的稀疏約束,進(jìn)一步加入了去噪處理,對NMF算法進(jìn)行改進(jìn),使之得以更好地應(yīng)用于腫瘤基因表達(dá)譜數(shù)據(jù)的維度約簡工作中.實(shí)驗(yàn)表明,相較傳統(tǒng)方法,該算法在處理含有大量冗余的腫瘤基因表達(dá)譜數(shù)據(jù)時(shí)更加有效.

2 非負(fù)矩陣分解理論

NMF的基本思想是任意給定一個(gè)高維非負(fù)矩陣X,可以找到兩個(gè)低維的非負(fù)矩陣W和H,使得W與H的乘積近似地逼近原始矩陣,從而將原矩陣分解成兩個(gè)非負(fù)矩陣的乘積.其數(shù)學(xué)模型為:

X≈WH

(1)

若原始矩陣X是L×P的矩陣,則W為L×N階矩陣,H為N×P階矩陣,其中N

(2)

在基本的NMF目標(biāo)函數(shù)加上范數(shù)約束的方法不僅表示簡單,易于理解,而且可以根據(jù)具體情況對不同變量附加稀疏性限制,從而得到期望的性質(zhì).此外,圖正則化方法,噪聲處理等方法和演化,都可以通過不同方式被添加到目標(biāo)函數(shù)中.為了將稀疏編碼理論與NMF算法相結(jié)合,通常對分解后的系數(shù)矩陣H進(jìn)行稀疏約束.稀疏約束的選擇一般采用范數(shù)約束的方法,常用的包括l1范數(shù)和l2范數(shù)[9,16],lp范數(shù)(0≤p<1)約束在p等于1/2的時(shí)候目前被認(rèn)為是一種行之有效的方法[14].

3 本文提出的算法

3.1 算法基本模型

使用傳統(tǒng)NMF及其衍生算法進(jìn)行基因表達(dá)譜數(shù)據(jù)集的維度約簡工作時(shí),由于原始數(shù)據(jù)維度較高且含有大量冗余和噪聲數(shù)據(jù),在沒有進(jìn)行對應(yīng)處理的情況下,算法性能難以發(fā)揮,效果并不夠盡如人意.針對基因表達(dá)譜數(shù)據(jù)高維度、高冗余的特點(diǎn),本文基于非負(fù)矩陣分解方法的思想,結(jié)合圖正則化思想和稀疏性約束,進(jìn)一步加入去噪處理,對NMF算法進(jìn)行改進(jìn),提出的算法對處理過度冗余的高維基因表達(dá)譜數(shù)據(jù)特別有效.此外,區(qū)別于傳統(tǒng)稀疏算法中使用的l1范數(shù)約束,我們選擇l1/2范數(shù)進(jìn)行稀疏性約束,進(jìn)一步提升了算法的性能.

為了引入噪聲項(xiàng)的定義,我們將原始數(shù)學(xué)模型定義為:

X=WH+E

(3)

之后為了得到最優(yōu)解,目標(biāo)函數(shù)定義為:

(4)

其中λα是調(diào)整稀疏程度的參數(shù);λβ∈R+是一個(gè)標(biāo)量,用于調(diào)整流形約束的權(quán)重.λγ是控制降噪的參數(shù).Tr(·)是矩陣的跡.L是一個(gè)拉普拉斯(Laplacian)矩陣,可以由圖權(quán)重矩陣G和對角矩陣D由以下公式計(jì)算得到:

L=D-G

(5)

對于給定的兩個(gè)實(shí)例yi和yj,使用高斯核度量計(jì)算實(shí)例間的相似度,從而得到權(quán)重矩陣G:

(6)

之后可以計(jì)算對角矩陣D:

Dii=∑i=1Gij

(7)

3.2 優(yōu)化過程

對目標(biāo)函數(shù)的優(yōu)化過程等價(jià)于如下公式的最小化問題.

(8)

可以使用迭代更新的辦法解決.基本思路是固定其他變量,對W,H,E分別進(jìn)行更新.具體的更新優(yōu)化過程如下:

3.2.1 更新E

首先我們需要證明噪聲項(xiàng)的引入不會影響分解過程中非負(fù)性的保持,以便采用非負(fù)矩陣分解的經(jīng)典思想對該問題進(jìn)行優(yōu)化求解.當(dāng)固定W,H時(shí),對E的更新優(yōu)化問題變?yōu)?

(9)

這是一個(gè)帶l1范數(shù)約束的最小化問題,可以通過軟閾值操作符的方式進(jìn)行求解.其更新規(guī)則如下:

(10)

通過該更新規(guī)則可以保證X-E≥0.證明如下:

綜上,在上述更新規(guī)則下,可以保證X-E≥0.

通過證明,我們可以保證加入去噪處理后矩陣元素的非負(fù)性.由此我們在接下來的工作中,就可以利用一般非負(fù)矩陣分解的方法來進(jìn)行對W,H的迭代更新.

3.2.2 更新W

為了方便說明,因?yàn)槲覀円呀?jīng)證明了X-E≥0,我們令Z=X-E.

當(dāng)固定H,E時(shí),對W的更新優(yōu)化問題變?yōu)?

(11)

由于我們已經(jīng)知道Z非負(fù),則該優(yōu)化問題屬于一個(gè)非負(fù)二次規(guī)劃問題,和傳統(tǒng)非負(fù)矩陣分解模型類似,可以參考傳統(tǒng)非負(fù)矩陣分解模型的迭代更新規(guī)則[16]進(jìn)行處理.相應(yīng)的,我們得到用于迭代更新W的更新規(guī)則如下:

(12)

3.2.3 更新H

固定W,E時(shí),對H的更新優(yōu)化問題變?yōu)?

(13)

H可以看作是實(shí)例在低維空間中的表示,圖正則化思想為了在低維空間保持實(shí)例的原始結(jié)構(gòu),需要用下面的式子對低維表示的平滑性進(jìn)行度量:

(14)

對R進(jìn)行變換,可得:

=Tr(HLHT)

(15)

因此在對H進(jìn)行更新時(shí),需要考慮正則化項(xiàng)Tr(HLHT).參照Cai提出的圖正則化優(yōu)化理論[8],我們使用梯度下降的方法對H進(jìn)行優(yōu)化:

設(shè)更新H的目標(biāo)函數(shù)為O,有如下的加法更新規(guī)則:

(16)

其中δi,j是步長參數(shù).

令δi,j=-hi,j/2(WTWH+λβHDT)i,j,可得:

(17)

對于l1/2稀疏約束項(xiàng),我們參照已有的添加稀疏約束的方法[13].

綜上,我們可以得到用于迭代更新H的更新規(guī)則如下:

(18)

3.3 算法描述

本節(jié)結(jié)合前文對算法模型和優(yōu)化過程的介紹,給出本文提出算法過程的簡要描述(見表1).

4 實(shí) 驗(yàn)

4.1 數(shù)據(jù)集

我們使用兩個(gè)取自真實(shí)采樣的常用基因數(shù)據(jù)集,ALL-AML和Colon[17],用于衡量算法的性能.ALL-AML數(shù)據(jù)集包含38個(gè)實(shí)例的5000個(gè)基因,包括27個(gè)ALL細(xì)胞和11個(gè)AML細(xì)胞.Colon數(shù)據(jù)集中包含62條實(shí)例,表示62個(gè)組織的2000個(gè)基因,其中40個(gè)組織是腫瘤,另外22個(gè)活檢是從同一患者健康的組織部分收集而來.

4.2 評估指標(biāo)

該理論已經(jīng)得到證明:當(dāng)維度約簡處理后的維度等于實(shí)際類標(biāo)簽數(shù)量時(shí),后續(xù)聚類中得到的結(jié)果無論從開銷和性能上都相對優(yōu)秀[18].因此我們選擇聚類領(lǐng)域常用的評價(jià)標(biāo)準(zhǔn),包括正確率(Accuracy,ACC)、標(biāo)準(zhǔn)互信息(Normalized Mutual Information,NMI)和蘭德指數(shù)(Adjusted Rand Index,ARI[19])進(jìn)行評估.它們的取值范圍都在[0,1]之間.ACC用于描述點(diǎn)和簇的一一對應(yīng)關(guān)系,其原理是使聚類的結(jié)果和真實(shí)的結(jié)果盡可能匹配,ACC越大,代表聚類的效果越好.令qi為數(shù)據(jù)實(shí)例xi使用聚類算法得到的簇標(biāo)簽,pi為數(shù)據(jù)實(shí)例xi的真實(shí)簇標(biāo)簽,則ACC定義如下:

(19)

NMI[20]基于互信息的方法來衡量聚類效果,需要實(shí)際類別信息.它代表當(dāng)一個(gè)類的信息已知的時(shí)候,對推測出關(guān)于另一個(gè)類的信息有多少幫助.若兩個(gè)類沒有共同的信息,即互信息為0.值越大意味著聚類結(jié)果與真實(shí)情況越吻合.令算法得到的聚類結(jié)果為C,給定聚類標(biāo)簽為R,H是來自聚類集合的熵信息,可以得到NMI的定義.

(20)

表1 算法描述

類似的,ARI的計(jì)算方式可以由如下公式定義:

(21)

在對比算法的選擇方面,由于我們的算法結(jié)合了這兩類算法的思想,我們選擇GNMF[11]和l1/2NMF[8]進(jìn)行對比.GNMF是圖正則化的基本非負(fù)矩陣分解方法,通過在分解過程中添加幾何分布信息提高算法性能;l1/2NMF對分解后的系數(shù)矩陣添加l1/2范數(shù)的稀疏約束.

實(shí)驗(yàn)中我們隨機(jī)產(chǎn)生數(shù)據(jù)集實(shí)例的輸入順序,進(jìn)行多組實(shí)驗(yàn),并在每組內(nèi)進(jìn)行多次重復(fù)實(shí)驗(yàn).為了公平地對比算法在理想情況下可能表現(xiàn)的最佳性能,對于所有的算法,我們都使用并記錄它們的參數(shù)為最優(yōu)值時(shí),所能得到的最好結(jié)果.算法需要提供維度約簡處理后產(chǎn)生的新的特征空間的維度,該維度設(shè)置為與實(shí)際類標(biāo)簽數(shù)目相同.維度約簡完成后,使用k-means算法進(jìn)行聚類,并與實(shí)際類標(biāo)簽進(jìn)行比對,以衡量算法性能.實(shí)驗(yàn)結(jié)果如表2和表3所示.

表2 ALL-AML數(shù)據(jù)集上的平均結(jié)果

表3 Colon數(shù)據(jù)集上的平均結(jié)果

圖1 算法在ALL-AML數(shù)據(jù)集上的對比結(jié)果

圖2 算法在Colon數(shù)據(jù)集上的對比結(jié)果

可以看出,我們的算法應(yīng)用于腫瘤細(xì)胞基因數(shù)據(jù)集時(shí),在準(zhǔn)確率和可區(qū)分度上,相較已有算法都存在顯著的優(yōu)勢.

5 結(jié)論和展望

本文提出了一種基于非負(fù)矩陣分解思想,結(jié)合圖正則化理論和l1/2范數(shù)稀疏約束的算法,該方法可以用于對細(xì)胞基因表達(dá)譜數(shù)據(jù)進(jìn)行維度約簡.算法結(jié)合了已有工作的優(yōu)勢,在保證對數(shù)據(jù)局部和全局結(jié)構(gòu)的描述能力和對稀疏性的約束能力基礎(chǔ)上,針對基因表達(dá)譜數(shù)據(jù)經(jīng)常存在過度冗余的問題,通過引入去噪處理,大幅提高了算法性能.實(shí)驗(yàn)結(jié)果證明,算法在基因數(shù)據(jù)聚類上的表現(xiàn)整體優(yōu)于傳統(tǒng)基于非負(fù)矩陣分解的算法.

在使用稀疏約束的NMF方法中,控制稀疏度的參數(shù)(本文為λα)大多根據(jù)實(shí)驗(yàn)經(jīng)驗(yàn)得來.如何通過理論上的推導(dǎo)和證明,從而合理控制參數(shù)以達(dá)到最優(yōu)效果,將是未來一個(gè)有價(jià)值的研究思路.