非负矩阵分解文献综述一、国内外研究现状近年来,技术传感器技术和计算机硬件的发展导致数据量的增加,许多经典数据分析工具被迅速压倒.因为信息采集设备只有有限的带宽,收集到的数据并不经常准确.其次,在很多情况下,从复杂现象观察到的数据,其往往代表几个相互关联的变量共同作用的综合结果.当这些变量更少的精确定义时,在原始数据中包含的实际信息往往是重叠的、模糊的.为了处理这些海量数据,科学家产生了新的关注.1999年,在刊物Nature上,Daniel Lee 和Sebastian Seung开始的一系列新的NMF的研究,数以百计的论文引用Lee 和Seung的论文,但一些较不为人知的事实是,在Lee 和Seung 的论文发表之前,Pentti Paatero开始了相关的工作. 虽然Lee和Seung引用Paatero的论文,Lee和Seung将Paatero的工作称为正矩阵分解，然而，Paatero的工作很少被后来的作者所引用.这是因为Paatero 将其工作称为正矩阵分解,这是误导Paatero创建NMF算法。
实际上Paatero年前发表了他最初的分解算法[1].2005年,Lin为了加速Lee和Seung的NMF迭代算法的收敛速度，最近提出使用投影梯度有约束的优化方法[2]，该方法与标准的(乘法更新规则)的方法相比，计算似乎有更好的收敛性.使用某些辅助约束,可以降低分解有约束的优化假设,降低投影梯度方法的局限性.2007年,V.Blondel等对标准NMF算法进行了加权改进，提出了加权NMF方法[3]。
通过加权,更好的表述了数据中的重要区域.其加权方法是：首先,定义数据中的重要区域,然后，在优化过程中，如果在该重要区域中重建错误,就给他分配更多的权重.国内对NMF的研究相对开始的较晚.2001 年,原微软中国研究院的李子青博士、张宏江博士等人发现Lee和Seung提出的经典NMF算法在人脸图像未得到配准的情况下,不能学习得到人脸的部件.并提出了局部非负矩阵分解来解决这个问题[4].Chen 等人将LNMF算法应用于人脸检测并取得了较好的效果.现为中科院自动化所生物识别与安全技术研究中心主任的李子青带领他的团队,于2009 年,提出了基于吉布斯随机场的 NMF 算法[4],该算法的收敛速度较快，并且得到的分解结果具有较好的稀疏性和可解释性.清华大学信息科学与技术国家实验室的章毓晋教授、李乐博士对非负矩阵分解的研究做了大量的工作,对 NMF 算法的研究现状进行了综述，对已有的NMF算法进行了很好的分类,指出各个NMF算法的缺点,并提出了改进的算.针对NMF的先天缺陷,即数据描述能不强、推广性差,提出了非负矩阵集分解的概念和相应的算法[4].浙江大学计算机学院的蔡登教授等人针对流形数据提出了图正则非负矩阵分解算法 GNMF [4],该方法在矩阵分解过程中明确考虑了数据集携带的几何信息：如果数据点在原空间是邻近点,那么对应到新的基下也是邻近点.此外，他们还提出了局部保留 NMF.可见,国内的研究机构和学者也逐渐加入 NMF 研究的行列,并取得了一定的成果.二、非负矩阵分解2.1非负矩阵分解原理信息或信号处理的许多数据具有非负性的特点[5],如灰度图像、物质成分含量、文章中单词出现的次数和统计学中的概率转移矩阵等.在用线性表示方法处理这类数据时,往往要求分解的结果都是非负的.此时若采用传统的因子分析方法,如主成份分析,因为其结果中含有负数而失去了物理意义,而采用非负矩阵分解方法就可以避免这一点.非负矩阵分解是一种多变量分析方法.它首先把高维的数据进行分解,得到低维的数据,然后再对低维的数据进行压缩,以得到理想的压缩效率.假设有m 个n维空间的样本数据,用m n X ⨯表示.该数据矩阵中各元素都是非负的,即0≥X ,对矩阵m n X ⨯进行线性分解,有m r r n m n C B X ⨯⨯⨯≈,其中r n B ⨯称为基矩阵,m r C ⨯为系数矩阵.若选择r 比n 小,即r<n ，用系数矩阵代替原数据矩阵,就可以实现对原数据矩阵的降维,得到数据特征的降维矩阵.然后对系数矩阵C 进行压缩,从而减少存储空间,节约计算资源.2.2非负矩阵分解的算法为了实现矩阵的非负分解,首先需要定义一个损失函数来刻画分解前后的逼近程度,然后在非负性约束下求解.最早提出的正矩阵分解方法采用传统的梯度下降算法与加性迭代规则[6].现在我们对这种方法进行了改进,在此基础上采用乘性迭代规则,更适合非负数据的特点,即在非负性初始化的基础上,在迭代过程中能简单地保持非负性,而加性迭代规则就需要一个强制将负值变为零的步骤.2.3非负矩阵分解算法的目标函数目标函数又称为代价函数( Cost Function)是衡量分解前后矩阵相似度的量[7].力求相似度最大亦即使得X 与胡泊勺差异最小,两种方式来衡量[8] 欧氏距离和K-L 散度.欧氏距离:∑∑==-=m i nj ij ij v u uv X v u f 112,)) ((21),(min （1）且。
，j b a i V U bj ia ,,,0,0∀≥≥上式等价于矩阵的范数如下式:∑∑==-=m i n j F ij ij UVX UV X 1122)-(）（ （2）其中，F ∙二是佛罗贝尼乌斯(Frobrnius)范数,两个矩阵中各个元素之差的平方,来衡量X 与胡泊勺距离.很显然当且仅当X=UV 时为0,这是使用最多的目标函数,而且研究起来非常方便.一般情况下利用此公式.另一目标函数是K-L 散度形式:∑∑==+-=n i m j ij ij ij ij V U UV X UV X X V U f 11,))()(log (),(m in （3）且 。
，j b a i V U bj ia ,,,0,0∀≥≥由于X 与UV 并不是对称的,所以并不能称为距离,而称之为散度或者相对嫡.描述了UV 相比X 分散的程度.当∑∑==ij ij ij ij UV X 1)(时散度为0而且此时的X与UV,为标准正态分布.目前,上述目标函数同时求解U 和U 时是不能得到最优解的,因为目标函数是非凸的,只有单独对于U 或者V 时目标函数才是凸的,才有最优解.2.4迭代规则以及算法的收敛性2.4.1迭代规则：我们的目的是要使f(U,V)最小,即求如下最大似然解:)},|),((log min{arg ),|),((max arg },{V U V U f P V U V U f P V U -== (4)首先,假设噪声服从高斯分布,令E=f (W,H)(误差函数),则:)2exp(21),/(22ij ij ij E V U E p σπσ-= (5)可将问题转化为求下式:∑∑+-=ij ij ij ij ij ij UV X V U L )2log())((21),(22σπσ (6)的最小值.为了求出迭代规则,只需要求出ij U L ∂∂和ij V L ∂∂.假设所有数据点噪声的方差是相同的,即。
j i ij ,,∀=σσ由矩阵运算规则: ∑=k kiik ij V U UV )( (7)可以推导出以下偏导式: kj ik ij kj ikijV U UV H W WH =∂∂=∂∂)(,)( (8)所以： ])()[(])(([),(ik T ik T j ij ij kj ik UVV XV c UV X V c U V U L -=-=∂∂∑ (9)∑∑-=-=∂∂i i kj T kj T ik ij ij ik kj UV U X U c U UV X U c V V U L ])()[()])([),( (10)其中C 是常数.如此以来对U 和U 从负梯度方向进行迭代: ])()[(1)()1(ik T ik T n ik n ik UVV XV U U -*+←+λ (11)])()[(2)()1(kj T kj T n ik n ik UVU X U V V -*+←+λ (12)进而,令：kj T n kjikT n ik UVU V UVV U )()(21==λλ可得乘性迭代规则1:ik T ik T ik ik UVV XV U U )()(← (13) kj T kj T kj kj UV U XU V V )()(← (14)然后,在散度目标函数形式下,假设噪声服从Poisson 分布(泊松分布)经过类似的推导过程得迭代规则2:kj j ij ij kj j ik ik V UV X V U U ∑∑←)/( (15)ik i ij ij ik i kj kj U UV X U V V ∑∑←)/( (16)2.4.2收敛性证明收敛性的证明需要用到辅助函数[9],类似于EM (Expectation-Maximization ，最大期望值)算法.定义1:设),(t v v G 是F(h)的辅助函数,且满足 )(),(),(),(v F v v G v F v v G t =≥ (17)引理1:假设),(t v v G 是辅助函数,那么函数F(v)在以下的更新规则下是非增的: ),(min arg 1t v t v v G v =+ (18)可以非常容易的证明:)(),(),()(11t t t t t t v F v v G v v G v F =≤≤++即证。
三、NMF 的问题给定一个非负矩阵,n m R A ⨯∈和一个正整数k<min{m,n},找到非负矩阵k m R W ⨯∈和n k R ⨯的最小化功能[10].221),f F WH A H W -=（ （19）乘积WH 称为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)的极小值的主要问题是局部最小值的存在性.设D 为任何非负可逆矩阵,且1-D 也是非负的.进而,考虑H WDD 1-,也可以看出问题(19)极小值计算的困难性.NMF 在数据挖掘中有很好的应用,在实践中,即使局部最小值可以提供理想的属性数据压缩.四、基本算法(乘法更新算法)乘法更新NMF 算法W =rand(m,k);%初始化W 为随机稠密矩阵H =rand(k,n);% H 为随机稠密矩阵进行初始化For i= 1: maxiter);10/().(*.)(9-+=W H W A W H H MU T T);10/().(*.)(9-+=T T W HH AH W W MUEnd 。