文献综述部分参考写法

非负矩阵分解文献综述一、国内外研究现状近年来,技术传感器技术和计算机硬件的发展导致数据量的增加，许多经典数据分析工具被迅速压倒•因为信息采集设备只有有限的带宽，收集到的数据并不经常准确•其次,在很多情况下，从复杂现象观察到的数据，其往往代表几个相互关联的变量共同作用的综合结果•当这些变量更少的精确定义时，在原始数据中包含的实际信息往往是重叠的、模糊的.为了处理这些海量数据，科学家产生了新的关注•1999年,在刊物Nature上,DanielLee和SebastianSeung开始的一系列新的NMF的研究,数以百计的论文引用Lee和Seung的论文，但一些较不为人知的事实是,在Lee和Seung的论文发表之前,PenttiPaatero 开始了相关的工作.虽然Lee和Seung引用Paatero的论文丄ee和Seung将Paatero的工作称为正矩阵分解，然而，Paatero的工作很少被后来的作者所引用.这是因为Paatero将其工作称为正矩阵分解，这是误导Paatero创建NMF算法。实际上Paatero年前发表了他最初的分解算法⑴.2005年,Lin为了加速Lee和Seung的NMF迭代算法的收敛速度，最近提出使用投影梯度有约束的优化方法［2］，该方法与标准的（乘法更新规则）的方法相比，计算似乎有更好的收敛性.使用某些辅助约束，可以降低分解有约束的优化假设，降低投影梯度方法的局限性.2007年,V.BIondel等对标准NMF算法进行了加权改进，提出了加权NMF方法［3］。通过加权，更好的表述了数据中的重要区域.其加权方法是：首先，定义数据中的重要区域，然后，在优化过程中，如果在该重要区域中重建错误，就给他分配更多的权重.国内对NMF的研究相对开始的较晚.2001年，原微软中国研究院的李子青博士、张宏江博士等人发现Lee和Seung提出的经典NMF算法在人脸图像未得到配准的情况下，不能学习得到人脸的部件.并提出了局部非负矩阵分解来解决这个问题⑷.Chen等人将LNMF算法应用于人脸检测并取得了较好的效果.现为中科院自动化所生物识别与安全技术研究中心主任的李子青带领他的团队 ，于2009年,提出了基于吉布斯随机场的NMF算法［4］，该算法的收敛速度较快，并且得到的分解结果具有较好的稀疏性和可解释性.清华大学信息科学与技术国家实验室的章毓晋教授、李乐博士对非负矩阵分解的研究做了大量的工作 ，对NMF算法的研究现状进行了综述，对已有的NMF算法进行了很好的分类，指出各个NMF算法的缺点，并提出了改进的算.针对NMF的先天缺陷，即数据描述能不强、推广性差，提出了非负矩阵集分解的概念和相应的算法⑷.浙江大学计算机学院的蔡登教授等人针对流形数据提出了图正则非负矩阵分解算法gnmF,该方法在矩阵分解过程中明确考虑了数据集携带的几何信息： 如果数据点在原空间是邻近点，那么对应到新的基下也是邻近点•此外，他们还提出了局部保留NMF.可见，国内的研究机构和学者也逐渐加入NMF研究的行列，并取得了一定的成果•二、非负矩阵分解2.1非负矩阵分解原理信息或信号处理的许多数据具有非负性的特点[5],如灰度图像、物质成分含量、文章中单词出现的次数和统计学中的概率转移矩阵等•在用线性表示方法处理这类数据时，往往要求分解的结果都是非负的•此时若采用传统的因子分析方法,如主成份分析，因为其结果中含有负数而失去了物理意义，而采用非负矩阵分解方法就可以避免这一点•非负矩阵分解是一种多变量分析方法•它首先把高维的数据进行分解，得到低维的数据,然后再对低维的数据进行压缩，以得到理想的压缩效率•假设有m个n维空间的样本数据，用Xnm表示.该数据矩阵中各元素都是非负的，即X0,对矩阵Xnm进行线性分解,有XnmBnrCrm,其中Bnr称为基矩阵，Crm为系数矩阵•若选择r比n小，即r<n,用系数矩阵代替原数据矩阵，就可以实现对原数据矩阵的降维，得到数据特征的降维矩阵.然后对系数矩阵C进行压缩，从而减少存储空间,节约计算资源.2.2非负矩阵分解的算法为了实现矩阵的非负分解，首先需要定义一个损失函数来刻画分解前后的逼近程度,然后在非负性约束下求解•最早提出的正矩阵分解方法采用传统的梯度下降算法与加性迭代规则⑹.现在我们对这种方法进行了改进，在此基础上采用乘性迭代规则，更适合非负数据的特点，即在非负性初始化的基础上，在迭代过程中能简单地保持非负性，而加性迭代规则就需要一个强制将负值变为零的步骤 •2.3非负矩阵分解算法的目标函数目标函数又称为代价函数(CostFunction)是衡量分解前后矩阵相似度的量⑺.力求相似度最大亦即使得X与胡泊勺差异最小，两种方式来衡量⑹欧氏距离和K-L散度.1mn2minf(u,v)； (Xj(uv)j)欧氏距离： 2i1j1 (1)且UiaO,Vj0，i,a,b,j。上式等价于矩阵的范数如下式(Xj(Xj(UV)ij)XUV其中，l?F二是佛罗贝尼乌斯(Frobrnius)范数,两个矩阵中各个元素之差的平方,来衡量X与胡泊勺距离.很显然当且仅当X=UV寸为0,这是使用最多的目标函数,而且研究起来非常方便.一般情况下利用此公式.另一目标函数是K-L散度形式：且Uia0,Vbj0， i,a,b,j。由于X与UV并不是对称的，所以并不能称为距离，而称之为散度或者相对嫡•描述了UV相比X分散的程度.当ijXijjj(UV)ij1时散度为0而且此时的X与UV,为标准正态分布.目前，上述目标函数同时求解U和U时是不能得到最优解的，因为目标函数是非凸的,只有单独对于U或者V时目标函数才是凸的，才有最优解.2.4迭代规则以及算法的收敛性2.4.1迭代规则：我们的目的是要使f(U,V)最小，即求如下最大似然解：{U,V}argmaxP(f(U,V)|U,V)argmin{logP(f(U,V)|U,V)}⑷首先，假设噪声服从高斯分布,令E=f(W,H)(误差函数),则：1 Ej2p(E/U,V)^^=exp(^-4)可将问题转化为求下式iog(2j)L(U,V)2 (Xjiog(2j)2iiij的最小值.为了求出迭代规则，只需要求出Uij和Vj.假设所有数据点噪声的方差是相同的，即j,i,j。由矩阵运算规则:(UV)ij UikVkik (-7\

可以推导出以下偏导式：所以：(WH)jWik(UV)ijHkj,^^VkjUikL(U,V)Uikc[Vkj可以推导出以下偏导式：所以：(WH)jWik(UV)ijHkj,^^VkjUikL(U,V)Uikc[Vkj(Xjj(UV)ij]c[(XVT)ik(UVVT)ik](9)L(U,V)Vkjc[UikXjiC是常数.如此以来对U和U(UV)ijUik)]c[(UTX)kj(UTUV)kj]i(10)从负梯度方向进行迭代:Uikn°Uikn)[(XVT)ik(UVVT)ik](11)Vikn1)Vikn)[(UTX)kj(UVUT)kj](12)进而,令:U；(UVVT)ikVk：(UVUT)kj可得乘性迭代规则Uik可得乘性迭代规则Uik1:(13)(14)Poisson分布(14)Poisson分布(泊松分布)经过类(15)(16)然后，在散度目标函数形式下，假设噪声服从似的推导过程得迭代规则2:U U jVkjXij/(UV)ijUik UikjV—iUikXij/(UV)ijkjkjiuikiik242收敛性证明收敛性的证明需要用到辅助函数⑻，类似于EM(Expectation-Maximization，最大期望值)算法•G(v,vt) F(v),G(v,v)F(v)(17)定义1:设G(v,V)是F(h)的辅助函数G(v,vt) F(v),G(v,v)F(v)(17)引理1:假设G(v，V)是辅助函数,引理1:假设G(v，V)是辅助函数,那么函数F(v)在以下的更新规则下是非增的vt1argminG(v,vt)v可以非常容易的证明：(18)F(vt1)G(vt1,vt)G(vt,vt)F(vt)即证。三、NMF的问题给定一个非负矩阵，ARmn和一个正整数k<min{m,n},找到非负矩阵R和R的最小化功能[10]f(W,H)12AWH(19)乘积WF称为A的NMF虽然A不一定等于乘积WH乘积WH是至多秩为k的近似因子分解，但我们将省略“近似”这个词在本文的其余部分•适当的k的值决定在实践中至关重要，但k是通常的选择问题相关的.在大多数情况下，然而,k通常选择这样k>min(m,n)在这种情况下，WH可以被认为是一个压缩的形式的数据.NMF的另一个关键问题是计算问题(19)的极小值，来抽取作为基向量W的隐含特征,然后可以用于识别和分类•不允许W和H中出现负数,NMF使部分的部分的非负组合形成一个整体[11].特性可能是部分图像数据，主题或集群在文本数据，或特定吸收高光谱数据的特征•由于f(W,H)的非凸性,影响问题(19)的极小值的主要问题是局部最小值的存11在性.设D为任何非负可逆矩阵,且D也是非负的.进而,考虑WDDH,也可以看出问题(19)极小值计算的困难性.NMF在数据挖掘中有很好的应用，在实践中,即使局部最小值可以提供理想的属性数据压缩.四、基本算法(乘法更新算法)乘法更新NMF算法W=rand(m,k);%初始化W为随机稠密矩阵H=rand(k,n);%H 为随机稠密矩阵进行初始化Fori=1:maxiter(MU)HH.*(WtA)./(WtWH109);T T 9(MU)WW.*(AH)./(WHH 10);End

-9为了避免被零除,在每个更新的规则加入10丄ee和Seung利用梯度的连续下降性,断言上述算法收敛到局部最小，但后来该断言被证明是不正确的[12].事实上，由Lee和Seung仅仅证明显示一个连续下降性值,不排除下降到一个鞍点.要理解其中的原因,一个必须考虑Karush-Kuhn-Tucker最优性条件.首先,如果初始矩阵的W和H是严格的正，在整个迭代中，W和H保持为正，这由乘法原则很容易验证的.其次，如果迭代序列(WH)收敛到 (W*，H*),且W* 0,H* 0那么(f/W)(W*,H*) 0和(f/H)(W*,H*) 0第二点可以利用H更新规则的补充形式HH[H./(WtWH)].*[Wt(AWH)] (20)来验证.考虑到H中的(i,j)元素，假设H的极限点已经达到,H>0.然后从式(20),我们知道5

[WT5

[WTWH]ij([WTA]j[WTWH]j) 0由于Hij 这意味着何蚀[WTWH]j,这意味着[f/H]ij0将这两点结合起来,满足Karush-Kuhn-Tucker最优性条件下,这是唯一的极限点(W*H*),没有任何元素等于0.W0,H0,(WHA)HT0,WT(WHA)0,(WHA)HT.*W0WT(WHA).*H0.尽管事实，例如，比0对于所有的迭代，这个元素可以收敛到一个极限值在(W,H)时[f/H]j0即使山0.因此，Hj0是可能的,在这种情况下,必须证明相应的互补松弛条件，(f/H)(W*,H*) 0,没有明显的使用乘法更新规则来做这个.综上所述，我们只能对Lee和Seung乘法更新算法的收敛以下声明，当算法算法融合在可行区域内的一个极限点 ，这个点是一个固定的点.这个固定点可以或可能不是局部极小.当极限点在于可行域的边界，其平稳性无法确定.作为第一个著名的NM!算法,Lee和Seung乘法更新算法已成为基准的新算法进行了比较丄ee和Seung当他们收敛(这往往是在实践中),是出了名的慢收敛.他们需要的迭代次数比梯度算法和ALS算法要多的多.每次迭代高由于每次迭代需要0(mnk工作.然而,优秀的改进算法可以改善其情况.例如,在W的更新规则,这就要求乘积首先被建立•为了克服这些缺点,研究人员已经提出了修改原来的Lee和Seung算法.例如,给出了一个修改算法间，加速Lee和Seung算法，但不幸的是,仍然有相同的收敛问题.最近丄in创建了一个修改，解决了一个收敛问题.即Lin的改造IED算法保证收敛到一个稳定点[14].然而,该算法要求每次迭代的计算量比已经慢 Lee和Seung算法略多.此外Dhillon和SRA导出乘法更新规则，将权重在逼近要素的重要性[15].五、总结在本文中，我们试图勾勒出一些相关的非负矩阵分解的主要概念 .虽然非负矩阵分解理论提出不到二十年，但人们对其研究却是非常重视的，所以非负矩阵分解理论才能有了如此快的发展，并成功应用到其他领域,尤其在模式识别领域内的应用越来越活跃.通过结合其他理论使得非负矩阵分解算法具有更好的性能是今后主要的发展方向.但是,非负矩阵分解算法依然存在着许多没有解决的问题如：矩阵的初始化问题、算法的收敛性速度问题、迭代次数确定问题、降维数据维度的选择问题、评判算法好坏的标准问题等等.这些问题有时候对实验的结果有很大的影响，所以将来有必要对这些存在的问题做仔细的研究 ，我相信这些问题会很快得到解决的.参考文献：MichaelWBerry,MurrayBrowne,AmyN.Langville,V.PaulPauca,RobertJ.Plemmon,Algorithmsandapplications forapproximatenonnegativematrixfactorization[J],Computational Statistics&DataAnalysis,2007,52(27),2-3.MichaelWBerry,MurrayBrowne,AmyN.Langville,V.PaulPauca,RobertJ.Plemmon,Algorithmsandapplications forapproximatenonnegativematrixfactorization[J],Computational Statistics&DataAnalysis,2007,52(27),3-4.胡俐蕊,非负矩阵分解方法及其在选票图像识别中的应用 [D],安徽大学博士学位,2013.董云影,张慧，张红，非负矩阵分解的研究现状[J]，黑龙江科技信息，2015,28.⑸张永鹏，郑文超，张晓辉，非负矩阵分解及其在图像压缩中的应用[J],西安邮电学院学报,2008,13(3)，1-2.⑹李乐，章毓晋，非负矩阵分解算法综述[J],电子学报，2008,4(36),737-743胡学考,基于非负矩阵分解的图像表示和分类研究 [D],辽宁工业大学硕士学位，2015.LeeD,SeungH,AlgorithmsforNon-NegativeMatrixFactorization.AdvancesinNeurallnformationProcessingSystems[J],MITPress,2001杜世强，石玉清，王维兰,.基于图正则化的半监督非负矩阵分解.计算机工程与应用[J],2012,48(36),194-200.MichaelWBerry,MurrayBrowne,AmyN.Langville,V.PaulPauca,RobertJ.Plemmon,Algorithmsandapplicationsforapproximatenonnegativematrixfactorization[J],Computational Statistics&DataAnalysis,2007,52(27),155-173.LeeD,SeungH,Learningthepartsofobjectsbynon-negativematrixfactorization[J],1999,Natu