平滑l0范数约束的β-NMF及其在聚类中的应用

崔 建， 游春芝

(山西医科大学汾阳学院 基础医学部， 山西 吕梁 032200)

0 引 言

近年来随着基因技术的快速发展，通过肿瘤基因表达数据来发掘基因路径、基因聚类和基因功能预测已经成为生物学家研究的热门领域。而就目前来说，人们对肿瘤基因表达数据的研究大致可以分为3个阶段：第一阶段，采用统计的相关方法对单个基因进行差异性判断；第二阶段主要集中于根据基因之间的相似或者内在的相互作用来实现对基因的分组；第三阶段一般采用反向工程预测潜在的肿瘤基因表达控制网络。现在生物学家得到的数据很大一部分是基于无监督的，因此对肿瘤基因表达数据的研究主要集中在第二阶段，也就是通过聚类的方法来挖掘肿瘤基因表达数据中具有相似功能的基因。

目前，常用的聚类方法大致有基于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)只能取到局部的最优解。

对于式(2)Lee和Seung提供了一种基于梯度下降迭代算法。其规则迭代为

(4)

(5)

对于式(3)的迭代规则为

(6)

(7)

其中i=1…m，j=1…n，⊗表示对应的元素乘积。

2 基于平滑l0范数约束的β-NMF

2.1 β散度的非负矩阵分解(β-NMF)

β散度的非负矩阵分解准则函数为

(8)

在W>0，H>0的限制条件下，要使得准则函数也就是目标函数达到最小，通过梯度下降法得出如下乘积迭代规则：

(9)

(10)

2.2 基于平滑l0范数约束的β-NMF

对矩阵W定义如下函数：

(11)

当σ→0时，有JW→‖W‖0，其中‖W‖0表示l0范数，其对应的值为W中非零元素的个数，用于表示它的稀疏性。当σ越小，相似程度越高。

将式(11)代入式(8)，就得到了一种基于平滑l0范数的β散度的非负矩阵分解，其目标函数归结为以下的优化问题：

(12)

(13)

(14)

(15)

用标准的梯度下降法有：

(16)

(17)

取步长ηW和ηH为

(18)

(19)

分别代入得到如下更新规则：

(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]以及聚类稳定性等。而本文中取聚类准确率作为实验的结果。聚类准确率的计算是通过对比获得的样本标签与已知数据集的标签一致性来实现。对于给定的包含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中不难发现基于平滑l0范数的β散度的非负矩阵分解新方法(S(β-NMF))平均聚类精度达到70%，比β-NMF高出3%，比传统的NMF(ED)高出11%，相比较本文提出的算法聚类效果显著。

表2 聚类精度

4 结 论

近年来NMF算法被广泛用于图像识别、分类、基因聚类等方面。本文在平滑l0范数约束的β散度非负矩阵分解算法对肿瘤基因表达数据进行特征提取，并进行聚类。通过最后的实验效果可看出该算法的有效性和可行性。尽管该算法在实际应用中取得一定的成功，但是由于初始矩阵的随机选择，导致得到的分解矩阵结果不稳定，所以如何提高分解的稳定性还有待研究。

[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