崔 建， 游春芝

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

0 引 言

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

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

1 非負矩陣分解

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

V≈WH

(1)

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

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

基于歐氏距離的分解:

(2)

當且僅當V=WH時達到最小值0。

基于KL散度的非負矩陣分解:

(3)

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

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

(4)

(5)

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

(6)

(7)

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

2 基于平滑l0范數約束的β-NMF

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

β散度的非負矩陣分解準則函數為

(8)

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

(9)

(10)

2.2 基于平滑l0范數約束的β-NMF

對矩陣W定義如下函數：

(11)

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

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

(12)

(13)

(14)

(15)

用標準的梯度下降法有：

(16)

(17)

取步長ηW和ηH為

(18)

(19)

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

(20)

(21)

如上基于平滑l0范數約束的β-NMF算法實現可歸納為

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

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

(3) 終止條件。當迭代次數或者目標函數值小于閾值則算法終止；否則返回(2)。

3 實 驗

3.1 實驗數據

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

表1 腫瘤基因表達數據

3.2 基因表達數據聚類效果評價方法

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

(22)

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

3.3 實驗數值設置及結果分析

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

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

表2 聚類精度

4 結 論

近年來NMF算法被廣泛用于圖像識別、分類、基因聚類等方面。本文在平滑l0范數約束的β散度非負矩陣分解算法對腫瘤基因表達數據進行特征提取，并進行聚類。通過最后的實驗效果可看出該算法的有效性和可行性。盡管該算法在實際應用中取得一定的成功，但是由于初始矩陣的隨機選擇，導致得到的分解矩陣結果不穩(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] 但漢輝 ，張玉芳 ，張世勇.一種改進的K-均值聚類算法[J].重慶工商大學學報(自然科學版)，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] 唐曉芬，陳莉.最大相關熵非負矩陣分解在基因表達數據中的應用[J].計算機與應用化學: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