平滑l0范數(shù)約束的β-NMF及其在聚類中的應(yīng)用

崔 建， 游春芝

(山西醫(yī)科大學(xué)汾陽學(xué)院 基礎(chǔ)醫(yī)學(xué)部， 山西 呂梁 032200)

0 引 言

近年來隨著基因技術(shù)的快速發(fā)展，通過腫瘤基因表達(dá)數(shù)據(jù)來發(fā)掘基因路徑、基因聚類和基因功能預(yù)測已經(jīng)成為生物學(xué)家研究的熱門領(lǐng)域。而就目前來說，人們對腫瘤基因表達(dá)數(shù)據(jù)的研究大致可以分為3個階段：第一階段，采用統(tǒng)計的相關(guān)方法對單個基因進(jìn)行差異性判斷；第二階段主要集中于根據(jù)基因之間的相似或者內(nèi)在的相互作用來實現(xiàn)對基因的分組；第三階段一般采用反向工程預(yù)測潛在的腫瘤基因表達(dá)控制網(wǎng)絡(luò)。現(xiàn)在生物學(xué)家得到的數(shù)據(jù)很大一部分是基于無監(jiān)督的，因此對腫瘤基因表達(dá)數(shù)據(jù)的研究主要集中在第二階段，也就是通過聚類的方法來挖掘腫瘤基因表達(dá)數(shù)據(jù)中具有相似功能的基因。

目前，常用的聚類方法大致有基于K-means聚類[1、2]、主成分(PCA)[3]聚類法、獨立成分分析[4](ICA)聚類等。但是這些算法的聚類效果與實驗時所用的數(shù)據(jù)以及聚類時所用的相似度函數(shù)有很大的相關(guān)性。雖然主成分分析和獨立成分分析都能進(jìn)行數(shù)據(jù)的特征提取以及聚類，但是他們只能是提取到整體的特征，而且對數(shù)據(jù)進(jìn)行描述時允許數(shù)據(jù)中存在負(fù)數(shù)。而非負(fù)矩陣分解(NMF)[5]不但能夠提取數(shù)據(jù)的整體特征而且也可以提取部分特征并對原數(shù)據(jù)進(jìn)行純加性的線性組合來描述。NMF被認(rèn)為是一種對數(shù)據(jù)分析很有用的技術(shù)，它被廣泛地應(yīng)用到語音信號處理[6]、數(shù)據(jù)聚類[7]、圖像分析[8]等研究領(lǐng)域。對于基因表達(dá)數(shù)據(jù)這種高維、高噪聲、高冗余性等特點，應(yīng)用傳統(tǒng)的非負(fù)矩陣分解聚類效果都不是很理想，隨著矩陣分解理論的完善，為了適應(yīng)這個領(lǐng)域的需求，很多改進(jìn)的算法相繼被提出，如在文獻(xiàn)[9]中改進(jìn)的基于限制性非負(fù)矩陣分解(CNMF)、文獻(xiàn)[10]提出了一種非平滑的非負(fù)矩陣分解(SNNMF)。目前提出的相關(guān)非負(fù)矩陣分解目標(biāo)函數(shù)主要集中在歐式距離、KL散度、α散度、最大熵準(zhǔn)則[11]等。本文針對基因聚類提出了一種平滑l0范數(shù)約束的β散度[12]矩陣分解結(jié)合K均值的聚類算法。

1 非負(fù)矩陣分解

非負(fù)矩陣分解(NMF)的原理是把一個m×n矩陣V分解為一個m×k非負(fù)矩陣W和一個k×n的非負(fù)矩陣H的乘積，即

V≈WH

(1)

其中k需滿足(m+n)k

而對于NMF來說對應(yīng)的目標(biāo)函數(shù)主要有兩種形式：一種是基于歐氏距離(ED)分解的；而另一種目標(biāo)函數(shù)則是基于廣義KL散度的。

基于歐氏距離的分解:

(2)

當(dāng)且僅當(dāng)V=WH時達(dá)到最小值0。

基于KL散度的非負(fù)矩陣分解:

(3)

基于KL散度的目標(biāo)函數(shù)實際表示的是V和WH的相對熵，因為它是非對稱的，所以并不表示一個距離。式(3)是在約束條件W>0，H>0下對目標(biāo)函數(shù)D(V‖WH)最小化。對于式(2)、式(3)兩個目標(biāo)函數(shù)只能取W或者H中一個為凸，而不是同時取到，所以式(3)只能取到局部的最優(yōu)解。

對于式(2)Lee和Seung提供了一種基于梯度下降迭代算法。其規(guī)則迭代為

(4)

(5)

對于式(3)的迭代規(guī)則為

(6)

(7)

其中i=1…m，j=1…n，?表示對應(yīng)的元素乘積。

2 基于平滑l0范數(shù)約束的β-NMF

2.1 β散度的非負(fù)矩陣分解(β-NMF)

β散度的非負(fù)矩陣分解準(zhǔn)則函數(shù)為

(8)

在W>0，H>0的限制條件下，要使得準(zhǔn)則函數(shù)也就是目標(biāo)函數(shù)達(dá)到最小，通過梯度下降法得出如下乘積迭代規(guī)則：

(9)

(10)

2.2 基于平滑l0范數(shù)約束的β-NMF

對矩陣W定義如下函數(shù)：

(11)

當(dāng)σ→0時，有JW→‖W‖0，其中‖W‖0表示l0范數(shù)，其對應(yīng)的值為W中非零元素的個數(shù)，用于表示它的稀疏性。當(dāng)σ越小，相似程度越高。

將式(11)代入式(8)，就得到了一種基于平滑l0范數(shù)的β散度的非負(fù)矩陣分解，其目標(biāo)函數(shù)歸結(jié)為以下的優(yōu)化問題：

(12)

(13)

(14)

(15)

用標(biāo)準(zhǔn)的梯度下降法有：

(16)

(17)

取步長ηW和ηH為

(18)

(19)

分別代入得到如下更新規(guī)則：

(20)

(21)

如上基于平滑l0范數(shù)約束的β-NMF算法實現(xiàn)可歸納為

(1) 初始化。首先輸入V，k待定，初始矩陣W1和H1，參數(shù)β，σ，aW；

(2) 迭代更新。將初始矩陣W1和H1帶入式(20)和式(21)求解W和H；

(3) 終止條件。當(dāng)?shù)螖?shù)或者目標(biāo)函數(shù)值小于閾值則算法終止；否則返回(2)。

3 實 驗

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

對于腫瘤基因選擇5種公開的常用數(shù)據(jù)；數(shù)據(jù)1(Brain_Tumors)腦部腫瘤表達(dá)數(shù)據(jù)，共5個種類，80個樣本；數(shù)據(jù)2(Leukemial)是3類白血病基因表達(dá)數(shù)據(jù)共72個樣本組成；數(shù)據(jù)3(9_Tumors)的9種腫瘤基因組成；數(shù)據(jù)4(SRBCT)兒童校園藍(lán)細(xì)胞腫瘤；數(shù)據(jù)5(DLBCL)彌漫性大B細(xì)胞淋巴瘤。實驗數(shù)據(jù)如表1所示：

表1 腫瘤基因表達(dá)數(shù)據(jù)

3.2 基因表達(dá)數(shù)據(jù)聚類效果評價方法

目前，對數(shù)據(jù)聚類效果進(jìn)行評價的方法有很多種：聚類準(zhǔn)確率(Accuracy)、歸一化互信息[8]以及聚類穩(wěn)定性等。而本文中取聚類準(zhǔn)確率作為實驗的結(jié)果。聚類準(zhǔn)確率的計算是通過對比獲得的樣本標(biāo)簽與已知數(shù)據(jù)集的標(biāo)簽一致性來實現(xiàn)。對于給定的包含m個樣本的屬于c類的微陣列數(shù)據(jù)集，假設(shè)c是給定的，對于給定樣本V，cn是通過各種聚類算法得到的樣本標(biāo)簽，rn是數(shù)據(jù)集中附帶的類別標(biāo)簽。聚類的準(zhǔn)確率如下：

(22)

其中，I(X，Y)表示一個符號函數(shù)，當(dāng)X=Y時，I(X，Y)=1，否則I(X，Y)=0，map(cn)是一個從聚類實驗所得標(biāo)簽到已知標(biāo)簽之間的一個映射。

3.3 實驗數(shù)值設(shè)置及結(jié)果分析

實驗中所得到的矩陣為W和H，W作為特征矩陣，其大小為n×k，其中n為樣本個數(shù)，k為提取的特征維數(shù)，取值為10。實驗中用K-means對所提取的特征矩陣進(jìn)行聚類。考慮初始值對實驗的影響，在每個數(shù)據(jù)上隨機取不同的初始值，重復(fù)進(jìn)行20次實驗。其中aW的選擇是根據(jù)指數(shù)原則[13]選取，aW=γWexp(ιW*L)，其中L表示迭代次數(shù)，根據(jù)文獻(xiàn)[13]，實驗中取參數(shù)γW、ιW、β、σ分別為100、0.01、0.2、0.05。

實驗中取標(biāo)準(zhǔn)的NMF(ED)、KL散度的NMF、β-NMF、S(β-NMF)4種方法進(jìn)行對比，實驗結(jié)果如表2顯示。從表2中不難發(fā)現(xiàn)基于平滑l0范數(shù)的β散度的非負(fù)矩陣分解新方法(S(β-NMF))平均聚類精度達(dá)到70%，比β-NMF高出3%，比傳統(tǒng)的NMF(ED)高出11%，相比較本文提出的算法聚類效果顯著。

表2 聚類精度

4 結(jié) 論

近年來NMF算法被廣泛用于圖像識別、分類、基因聚類等方面。本文在平滑l0范數(shù)約束的β散度非負(fù)矩陣分解算法對腫瘤基因表達(dá)數(shù)據(jù)進(jìn)行特征提取，并進(jìn)行聚類。通過最后的實驗效果可看出該算法的有效性和可行性。盡管該算法在實際應(yīng)用中取得一定的成功，但是由于初始矩陣的隨機選擇，導(dǎo)致得到的分解矩陣結(jié)果不穩(wěn)定，所以如何提高分解的穩(wěn)定性還有待研究。

[1] DHILLON I S， MODHA D S. Concept Decomposition for Large Sparse Text Data Using Clustering[J].Machine Learning， 2001， 42(1-2): 143-175

[2] 但漢輝 ，張玉芳 ，張世勇.一種改進(jìn)的K-均值聚類算法[J].重慶工商大學(xué)學(xué)報(自然科學(xué)版)，2009，26(2):144-147

DAN H H，ZHANG Y F，ZHANG S Y.An Improved K-Means Clustering Algorithm[J].Journal of Chongqing Technology and Business University(Naturnal Science Edition)，2009，26(2);144-147

[3] JOLLIFFE I T. Principal Component Analysis[M].New York： Springer-Verlag，1989: 151-156

[4] SHENG J H， DENG H W， CALHOUN V D，et al.Integrated Analysis of Gene Expression and Copy Number Data on Gene Shaving Using Independent Component Analysis [J]. Computation Biology and Bioinformatics， IEEE/ACM-Transactions，2011，8(6):1568-1579

[5] LEE D D，SEUNG H S.Learning the Parts of Objects by Non-negative Matrix Factorization[J].Nature，1999， 40(1):788-791

[6] SHAHNAZ F B，MICHAEL W， PAUCA V P， et al.Document Clustering Using Non-negative Matrix Factorization[J]. Information Processing and Management，2006，42 (2) : 373-386

[7] LIU W X，YE D T，YUAN K H.On Alpha Divergence Based Non-negative Matrix Factorization for Clustering Cancer Gene Expression Data[J].Artificial Intelligence in Medicine，2008，44 (1):1-5

[8] LIU C， ZHOU J L， LANG F G， et al. Generalized Discriminant Orthogonal Non-negative Matrix Factorization and Its Applications[J].Systems Engineering and Electronics，2011， 33(10)：2327-2330

[9] LIU H F.Constrained Non-negative Matrix Factorization for Image Representation[J]. IEEE Transactions Pattern Analysis and Machine Intelligence，2012，34(7):1299-1311

[10] CARMONA-SAEZ P， PASCUAL-MARQUI R，TIRADO F，et al. Clustering of Gene Expression Data by Non-smooth Non-negative Matrix Factorization[J].Transactions Pattern Analysis and Machine Intelligence：2006，28(3):403-415

[11] 唐曉芬，陳莉.最大相關(guān)熵非負(fù)矩陣分解在基因表達(dá)數(shù)據(jù)中的應(yīng)用[J].計算機與應(yīng)用化學(xué):2013 ，30(11):1375-1378

TANG X F，CHEN L.Clustering of Gene Expression Data Based on Non-negative Matrix Factor-ization by Maximizing Entropy[J].Computers and Applied Chemistry，2013，30(11): 1375 -1378

[12] JOHN W，SONS L.Non-negative Matrix and Tensor factorization[M]. Singapore：Fabulous，2009:154-155

[13] ZDUNEK R，CICHOCKIA A． Non-negative Matrix Factorization with Constrained Second Order Opti-mization[J].Signal Processing，2007，87(8);1904-1916