非负矩阵分解毕业论文.docx

Error! No text of specified style in document.摘 要在需求处理大量高维数据的今天，需要优秀的降维技术来解决数据问题，如主成分分析，奇异值分解等等，这些数据分析方法的共同点是无法保证数据的非负性，而负值往往没有物理意义。非负矩阵分解（Non-negative Matrix Factorization）是一种保证非负属性的优秀降维方法。本文中先对非负矩阵分解做一个简短的介绍，讲述了非负矩阵分解的一些算法。而这些算法都可以在效率或其他属性上进行改进，故本文的主要目的在于获取更高效率的非负矩阵分解算法，数值实验证明，改进后的算法PCGSNMF算法在效率和稀疏度上展现出优越性。最后，对文章进行了总结。矚慫润厲钐瘗睞枥庑赖。关键词：非负矩阵分解 降维技术 梯度 ALS算法AbstractWith the processing of large amounts of high dimensional data, we need good dimensionality reduction techniques to solve this problem, such as PCA, SVD, and so on, because these methods cant guarantee the non-negative property, so it has a guarantee of non-negative constraints of the dimensionality reduction method, that is, non-negative matrix factorization (NMF) algorithm. 聞創沟燴鐺險爱氇谴净。In this paper, we first do a brief introduction summarized, The main purpose of this paper is to put forward to a new NMF algorithm which has higher efficiency. The numerical experiments will demonstrate the superiority of the new algorithm. And then briefly introduces some of the NMF application now. Finally, some conclusions about NMF algorithm are described.残骛楼諍锩瀨濟溆塹籟。Keywords: nonnegative matrix factorization Dimensionality reduction techniques Gradient alternating nonnegative least squares method酽锕极額閉镇桧猪訣锥。Error! No text of specified style in document.i目 录第一章 绪论11.1 NMF发展概况和研究现状11.2 NMF的数学问题介绍31.3 NMF的应用介绍41.4 KKT条件61.5 本文的研究内容及结构安排7第二章 NMF算法92.1 LS基础NMF算法92.2 ALS交替最小二乘102.3 Lin的投影梯度法112.3.1 梯度逼近设想112.3.2 改进的投影梯度法122.4 BBNMF算法13第三章 PCGSNMF算法153.1 改进的下降算法153.2 算法的停止条件173.3 收敛性分析173.4 稀疏约束183.5 PCGSNMF算法19第四章 数值实验214.1 中小型问题对比214.2 大型问题对比224.3 复杂型问题对比234.4 图片重组对比25第五章 总结与展望275.1 本文总结275.2 进一步的工作27致 谢29参考文献31Error! No text of specified style in document.37第一章 绪论 本章主要介绍课题的发展概况及研究现状，非负矩阵分解所要解决的数学问题，非负矩阵分解的部分应用，有关非负矩阵分解算法收敛性分析的KKT条件。本章还概述了本文的主要研究工作和论文的结构安排。彈贸摄尔霁毙攬砖卤庑。1.1 NMF发展概况和研究现状有一个基础的概念被根植于科学研究中，即在表面混乱而复杂的问题之下一定有简单抽象优雅的基础规则。这同样是信号处理，数据分析，数据挖掘，图像识别的案例。随着越来越多的原始数据在计算机领域的发展，获取有效途径选择适当的降维技术已经成为必要且重要的多元数据分析的挑战。通常来说两种基本方法是令人满意的，第一，对原始数据进行降维。第二，数据的主要部分，隐藏概念，突出结构，依赖于其应用环境来确定其有效性。謀荞抟箧飆鐸怼类蒋薔。现如今如何构造一个能使多维数据被更好描述与观测的变换方法始终是一个非常重要的问题，降维的技术的优越性主要在两个方面：（1）它正确的代表数据，使不精确性的削弱和可行性条件的满足。（2）它能精确的定义变量，当转换被数据收集机器所产生的初始重叠数据变为清楚地数据。因此，它们来到了许多应用的最前部，比如数据挖掘等等。在很多情况下，原始数据被以数据矩阵的形式建立或观察，或者被建立为线性组合数学模型，于是从代数的角度，原始数据矩阵可以被视为两因子矩阵，古典的数据分析法比如LLE(locally-linear embedding，局部线性嵌入)，PCA（principal component analysis，主成分分析），SVD(奇异值分解)因被所具备的约束的不同而有着本质的区别，然而，它们有两个共同的特点:(1)允许带有负数的分解量存在(允许有减性的描述)；(2)实现线性的维数约减，然而当出现非负约束时，它们就不能完美解决这些数据。因此，具有非负约束的优秀降维技术在数据分析领域被广泛关注。在这些应用中，被分析的数据通常是非负的。为了有更精确的物理意义，被加工的数据也是非负的。古典工具既然不能够保证这些非负的属性，自然而然，一个降序逼近技术，非负矩阵分解，它使得被加工的数据都是非负的。厦礴恳蹒骈時盡继價骚。非负矩阵分解第一次是被Paatero和Tapper在文献1中用正矩阵分解来命名的。直至1999年在非负矩阵分解领域的两位先驱科学家D.D.Lee和H.S.Seung在著名的科学杂志Nature中展现了非负矩阵研究的突出成果。文章给出了一种矩阵分解的新思路，即非负矩阵分解(Non-negative Matrix Factorization，NMF)算法，通俗的说，非负矩阵分解就是在矩阵中所有元素均为非负数约束条件之下的矩阵分解方法。非负矩阵分解自其产生以来就迅速引起了各个领域中的科学研究人员的重视原因在于：第一，大量的高维数据基本都可以通过模型转化为对数据矩阵处理的形式，之后就可以非负矩阵分解算法的思想来处理这些矩阵化过后的数据；第二，非负矩阵分解算法相较于传统的一些降维算法而言，简洁明了易于操作、其分解结果可以被解释为一种可加的线性组合。第三，非负矩阵分解算法分解后的结果一般具有自然的稀疏性，稀疏过后的矩阵不但易于表示，还有占用存储空间少等诸多优点。由此而产生了基础非负矩阵分解（LS）算法。LS算法与其他算法相比较相对简单实用，它是许多非负矩阵分解算法后来扩展的基础。茕桢广鳓鯡选块网羈泪。这个基础的算法说明了非负矩阵分解是一个非凸的优化问题，即此问题可能会出现数个极小值，然而一个普遍的错误理解优化问题的极限点是局部极小点。实际上，许多非凸优化问题不能保证极限点是稳定点。极限点是局部极小点这个属性效果会很好。同时这个算法的迭代公式使得收敛很慢，而且并不稳定。除此以外，算法也不像Lee和Seungs描述的那样，此非负矩阵分解算法不能保证收敛到最小。为了修改这个非负矩阵分解算法的缺点，Lin在文献3中提出的投影梯度法，此算法通过求解子问题，运用了投影加最速下降法的思想，算法收敛比LS算法收敛快，同时解决了收敛点是稳定点的问题，然而Lin的算法由于采用了梯度法，在接近极值时收敛速度会变的很慢，同时时间复杂度略高。鹅娅尽損鹌惨歷茏鴛賴。非负矩阵分解在近几年来由于没有统一的约束标准，出现了大量的算法和讨论，解决最优化问题的BB算法，梯度法，牛顿法，即大量的改进算法被提出，它们都具有各自的优势，Cichocki在2009年文献4中对近几年的非负矩阵分解算法进行了总结。籟丛妈羥为贍偾蛏练淨。根据非负矩阵分解问题中对分解结果的限制是否仅限于非负约束, 现有算法被分为基本的NMF算法( Basic NMF,BNMF, 基于基本NMF 模型) 和改进的NMF算法( Improved NMF，INMF，基于改进NMF 模型，要依具体的期望特性对分解结果施加除非负外的其他的限制) 两大类。BNMF在以往的( 或最初的) 文献中常就称为NMF, 这里用BNMF命名为强调与INMF 间的区别。BNMF 算法又可分为基于单个目标函数的算法和基于目标函数族的算法两类，本文中，NMF 同时指代两者。預頌圣鉉儐歲龈讶骅籴。非负矩阵分解虽然在近年来取得了很多的成果，但大部分非负矩阵分解算法的效率均不高且应用难度较大，部分算法可能会出现震荡，而有些算法则需几百步上千步的迭代，故仍需要更好的高效率同时收敛的算法的产生，同时更广泛的应用于实践中。渗釤呛俨匀谔鱉调硯錦。1.2 NMF的数学问题介绍在数学上，从计算的观点看，矩阵正常的分解过程中都会产生负值，但负值元素在实际中往往是毫无意义的。在现今海量的数据中，有用的数据往往都是非负的。因此，非负矩阵分解算法是一个很有意义的问题，正是如此，Lee和Seung两位科学家的NMF方法才得到人们的如此关注。 非负矩阵分解被用于寻找有代表性的非负数据，给出一个的非负矩阵,其中的每个元素都大于等0，一个预先特定的正整数,NMF寻找两个矩阵，通常r要选择远小于n或m的数，这样和的初值会小于原始矩阵，这就可以产生了压缩降维后的数据矩阵，最后使得 铙誅卧泻噦圣骋贶頂廡。它能够被列分块为,这里的和是矩阵和之中的每一列。换句话说，每一个矢量都是的列的线性组合，通过的分量加权。因此可以被认为是一个中数据线性近似优化的基础。由于相对较少的基向量来代表许多数据载体，要想产生良好的逼近，只能通过发现数据中潜在的基础矢量结构来解决。擁締凤袜备訊顎轮烂蔷。传统方法是通过缩小与之间的差异来寻找,一种方法是缩小与间的欧氏距离即 (1-1)满足，这些不等式是变量的约束，我们有时也把上公式记为 (1-2) 其中的是f范数的含义。另一个受欢迎的NMF优化公式是缩小与之间的Kullback-Leibler差异， (1-3)满足，严谨的来说，公式（1-2）并不是一个边界约束问题，它要求目标函数在任何有界区域有定义，而当等于0，或时等于0，log函数无定义，因此在本文中我们不使用此公式。贓熱俣阃歲匱阊邺镓騷。1.3 NMF的应用介绍 文档聚类通常使用SVD奇异值分解，潜在语义索引等，然而进几年的实验表明，非负矩阵分解得到的结果，通过每个轴捕捉特定的基本主题文档聚类，每个文档表示作为一种新的线性组合。文档集中的每个文件成员可以很容易确定的寻找主题轴）。表明该文档聚类方法超过了潜在语义索引和谱聚类方法不仅容易和可靠的推导文档聚类的结果，而且在文档聚类中精度很好。坛摶乡囂忏蒌鍥铃氈淚。文档聚类技术受到了更多的关注作为一个基本的高效的组织工具，导航，检索，总结大量的文本文件。一个好的文档聚类方法，计算机可以自动文档主体组织成一个有意义的集群层次，从而使一个有效的浏览和导航的语料库。蜡變黲癟報伥铉锚鈰赘。概括来说，文档聚类的简易步骤如下：给出一个文档库，建立一个文档矩阵，用i代表文档的权值。将PCG算法用在矩阵X上，通过算法迭代，得到两个矩阵,。通过公式 和公式标准化。用矩阵决定数据点的类标签。更精确的说，检测的每i行，如果,则将文档归类为x类。下图分别为NMF与LSI在文档聚类上的效果：買鲷鴯譖昙膚遙闫撷凄。 图4-1 NMF（非负矩阵分解） 图4-2 LSI（潜在语义索引）对比图4-1与图4-2，LSI所产生的潜在语义空间是正交的，每个文档在空间的一些方向会出现负值。首先，NMF并不需要潜在语义空间的必须正交。同时它可以保证数据在语义空间中每个方向都没有负值。这两个特征就使得NMF优于LSI方法。当出现重复文档时，NMF仍然可以寻找到一个潜在语义方向为每一个文档类，而SVD则需要正交性要求，特征向量计算则会使每个类无关联。第二，用NMF算法，一个文档可以添加许多基础语义，这样就可以产生更多的文档域。第三，在以上所提及的LSI的两个有益特点下，每个类的文档成员可以被很容易的辨认，而LSI的潜在语义空间不能提供这样的辨认，最后，传统的数据聚类方法像K-means方法必须申请特征向量空间来存放最终的文档类。綾镝鯛駕櫬鹕踪韦辚糴。我们再对比一下NMF算法与SVD奇异值分解在文档聚类上的效果：图4-3 NMF（非负矩阵分解） 图4-4 SVD（奇异值分解）显然，在NMF的空间，每一个文件以非负的值在所有三个方向，而在奇异值空间，每个文件可以取负值在一些方向。此外，在NMF空间，每个轴对应一个簇，并将所有数据点属于沿同一轴线相同的集群传播。确定每个数据点的聚类标签一样简单如发现轴与数据点的最大投影值。然而，在奇异值分解的空间，虽然三轴做单独的数据点属于不同的集群，轴（特征向量）和集群之间没有直接的关系。驅踬髏彦浃绥譎饴憂锦。人脸识别也是NMF算法研究中的一个非常活跃的领域，在非负矩阵分解算法受到重要关注的近年来，人脸识别技术的研究因为NMF算法的发展也受到很大影响,文献17中对己有的人脸识别技术进行了分类，描述和比较，指出了现存许多种人脸识别技术的优点和缺陷,对现存人脸识别技术的研究进行了总结与展望。实际上，如果在光照环境可控的条件下,现有的大部分人脸识别算法基本都可以取得很好的识别率,但是,假如在人脸识别过程中,用户故意做出一些干扰动作或者主动用遮蔽物进行遮挡。如果这些干扰动作使得人脸的特征受到影响,将导致现有的大部分识别算法的识别率急剧下降，效果不佳。在现存的人脸识别算法中属性优越的方法是子空间分析法，由于子空间分析法便于解释，因此在人脸识别领域被广泛的关注和欢迎。猫虿驢绘燈鮒诛髅貺庑。其中有一种非常重要的子空间分析方法,是现存比较成熟的人脸识别方法之一就是在文献18中所提到的特征脸方法，使用特征脸法进行人脸识别的方法首先由Sirovich and Kirby (1987)提出，并由Matthew Turk和Alex Pentland用于人脸分类。该方法被认为是第一种有效的人脸识别方法。这些特征向量是从高维矢量空间的人脸图像的协方差矩阵计算而来。但是,特征脸法存在着以下几点缺陷,首先，特征脸法所得到的结果可解释性较差;其次,特征脸法并不直观实用;第三,当人脸特征被影响后,特征脸法的识别率下降较为严重，故特征脸法缺乏好的人脸图像区分能力,在实际意义方面有不足之处。锹籁饗迳琐筆襖鸥娅薔。而NMF得到的图像恰好相反,其分解所得到的图像可解释为人的面部器官的特征，因而可以将人脸表示成基图像矩阵的纯加性线性组合，比较直观实用。在多数基于子空间分析的算法中,人脸识别基本通过提取图片的全局信息来实现近似，然而在很多应用中,局部的面部图像如面部器官，效果要远比全局实现的效果好。比如在部分遮挡的情形下,局部特征比全局实现具有更好的稳定性和简便性。文献21中己有的心理学研究表明,人面部的器官特征对于正确识别人的身份所起的作用非常大,而这些器官近似地分布在人面部的中心区域，此外，一些问题还会在提取特征时有不一样的要求。由于NMF能够提取人脸的局部特征这一优点,己被成功应用于人脸识别在19,20中,人脸表情识别19NMF提取的人脸特征对人脸识别中的部分遮挡问题不敏感。構氽頑黉碩饨荠龈话骛。2001年,李子青教授提出了局部非负矩阵分解图像表示方法(LNMF),并将其成功应用于人脸识别，LNMF方法较Lee和Seung的经典NMF算法相比,能得到局部特征更明晰的基图像,用此方法提取的人脸更有利于人脸识别，但是LNMF方法也有其缺点，其计算时间复杂度要比Lee和Seung的经典NMF算法高出很多。輒峄陽檉簖疖網儂號泶。1.4 KKT条件在通常的最优化问题中，有一个收敛性判别标准，Karush-Kuhn-Tucker 最优化条件 (KKT条件)，我们通常用此条件来判别最优化问题的收敛点是否为稳定点，此属性为判别算法优越性的重要一点，许多非凸最优化问题算法无法保证这一属性，NMF优化方法产生一个迭代序列，问题（1-2）是非凸的并且可能有数个极小值，故尧侧閆繭絳闕绚勵蜆贅。在本文中我们可将KKT条件简单描述如下：的梯度函数是由两部分组成： 这分别是在和元素的偏导数，从KKT优化情况，是（1-2）的不动点，当且仅当 (1-4) (1-5) 和 (1-6) 1.5 本文的研究内容及结构安排本文的主要工作是获取快速高效收敛的NMF算法。本文从目前广受欢迎的LS算法及投影梯度法入手，介绍了它们各自算法的优缺点。在ALS算法基础上进行了些许改进，使得算法更加高效简单。论文提出了基于改进的下降算法的PCGSNMF算法，实现了高效率的分解及收敛，及应用实例，最后提出了对未来非负矩阵分解算法的设计改进的一些设想。论文内容按以下结构安排：识饒鎂錕缢灩筧嚌俨淒。（1）NMF算法介绍（第二章）（2）PCGS算法（第三章）（3）数值对比（第四章）（4）总结与展望（第五章）其中第二章对与课题研究相关的LS算法作了完整描述，包括其使用的乘积更新规则及其迭代方式，又简要介绍了Lin投影梯度法，BB算法，优越性及不足，其中ALS算法是本章的关键，本章是后面各章的铺垫。第三章是文章的核心，在两种算法的优缺点的基础上，提出了改进的PCGNMF算法，改进了算法的效率。第四章展现了数值结果。第五章是对非负矩阵分解现存成果及问题的总结，以便获取更高效收敛的算法应用。凍鈹鋨劳臘锴痫婦胫籴。第二章 NMF算法本章通过讲述几个BNMF算法来为下一章的铺垫，通过这些算法可以对NMF有更好的理解，其中的LS算法为非负矩阵分解的先驱算法，ALS算法是现存许多算法的框架，Lin的投影梯度法是一个经典的算法，BBNMF算法是高效的非负矩阵分解算法。恥諤銪灭萦欢煬鞏鹜錦。2.1 LS基础NMF算法这个非负矩阵分解算法的标准是由Lee和Seung提出的，是目前解决非负矩阵分解实际问题最受欢迎的算法。Lee和Seung选择固定因素之一， 或，然后通过迭代公式对另一个因素进行缩小，或。细节的证明被在文献2中提供。此非负矩阵分解算法开始于对非负矩阵,的初始化，而后应用了每一步的更新规则，并进行循环。细节描述也在文献2中，能够清楚的看到迭代过程以及维持了,的非负属性。具体细节如下：鯊腎鑰诎褳鉀沩懼統庫。乘积更新规则（LS算法） 1：初始化 2：循环k=1,2， （2-1） （2-2）Lee和Seung证明了函数的值是非增的在每次迭代之后：以及 （2-3）因为此算法是第一个被大家知晓的算法，与其他算法相比较，它是许多NMF扩展算法的基础。这个基础NMF算法的数值实验展现了这个算法收敛很慢，而且不稳定。硕癘鄴颃诌攆檸攜驤蔹。Lee和Seung声明迭代序列极限是一个稳定点(在KKT条件下的一个点）。然而，Gonzales和Zhang指出这个声明是错误的，此方法是一个定点型算法，如果并且，而后推出阌擻輳嬪諫迁择楨秘騖。故其只是满足KKT条件的一部分，因此乘积更新算法依旧缺乏最优属性。要使此算法有定义，必须保证（2-1）和（2-2）为正，此外如果在k步迭代之后，那么在剩下的每一步迭代中都将有，因此必须保证在任意k情况下，和，当这些条件被满足时，现在考虑计算的复杂度，在式（2-1）和（2-2）中，和的计算复杂度都为。氬嚕躑竄贸恳彈瀘颔澩。可以计算（2-1）（2-2）的分母通过 或者 (2-4) 前一个计算也是，后一个复杂度是 。由于rmin(m,n)，故后一个更好。同样的对于（2-4），要使用。这个讨论指出了不论在任何NMF代码中时间复杂度小于 计算的重要性。釷鹆資贏車贖孙滅獅赘。总结：算法1所有的成本为迭代次数*另注：本文中，所有时间复杂度分析假定,与为稠密矩阵。2.2 ALS交替最小二乘LS算法得出，虽然非负矩阵分解的问题函数对变量,都是凸函数，但对于总体并不是凸函数。所以，当确定或，我们可以采用最小二乘法（LSM）,来解决和的改变，在每次最小二乘法后，为了避免出现负数在矩阵与中，所有的负数将会被用0替代。可以很容易的看到，这个算法的本质是趋于稀疏，结果会拥有较多的零元素在与矩阵中，这种方法是一种最优化问题的“块坐标下降法”，即其中一块变量在约束条件下最小化，而其余剩余块固定。怂阐譜鯪迳導嘯畫長凉。对于非负矩阵分解问题来说，这是最简单的情况，即块变量只有两个即W和H。交替非负最小二乘法：1：初始化2：循环k=1,2， (2-5) (2-6) 现在我们考虑（2-5）和（2-6）作为ALS算法的子问题，当一个变量固定后，一个子问题可以变为数个最小二乘问题可得出： 谚辞調担鈧谄动禪泻類。 的每一列= 这里的v是的第j列并且h是矢量变量。Cichocki (2005)4建议用投影牛顿法（Lawson and Hanson,1974)来解决分解后的每一个问题。嘰觐詿缧铴嗫偽純铪锩。现在关注ALS算法的收敛性，可能有人认为它会是一个琐碎的结果。举例来说，Paatero(1999)5表述了交替非负最小二乘，无论它有多少的块变量，收敛性都可以得到保证。然而，这个问题获得了一些关注。块坐标下降法的收敛性分析要求子问题有唯一解，但这个属性在这里并不支持，子问题（2-5）和（2-6）是凸的，但它们并不是严格凸的。故这些子问题有数个最优解。举例来说，当是0矩阵是，任何的都是(2-5）的最优解。幸运的是当有两个块变量时，Grippo and Sciandrone证明了这种独一无二的情况是不需要的。我们有下列的收敛定理：熒绐譏钲鏌觶鷹緇機库。定理：任何序列由算法而产生的极限点，都是式（1-2）中的稳定点。剩下的问题是是否序列至少有一个极限点（这里至少有一个收敛结果）。在最优化分析中，这个属性通常来自可行域的有界性，但我们约束条件下的和区域是无界的。在问题（1-2）中可以很容易添加一个所有变量的上界，这个改变仍然是一个约束问题，由于定理成立ALS算法可以应用，如果在式（1-2）中有上界。相比之下目前尚不清楚如何轻松地修改乘法更新规则。鶼渍螻偉阅劍鲰腎邏蘞。清楚的说比起相对简单的LS算法，解决子问题（2-5）和（2-6）的每一步迭代花费很大。其次，ALS算法可能较慢，即使它函数值在每步迭代都会减少。然而用此方法来解决子问题是潜在有效的。在接下来的2.3部分使用了梯度法，并讨论了它为什么适合用来解决ALS算法。纣忧蔣氳頑莶驅藥悯骛。概括的说，相对于缺乏收敛结果的LS算法，ALS算法有较好的优化属性。如何正确地执行非负在迭代约束仍在讨论中。第一个为NMF设计的ALS算法被Paatero2所提出，然后一些ALS算法的修改在56中，这增加了一些限制，我们将以进一步提高ALS算法的效率为本文的下面讨论的重点,本文的新算法也是基于ALS算法所产生的。颖刍莖蛺饽亿顿裊赔泷。2.3 Lin的投影梯度法2.3.1 梯度逼近设想Chu曾提出了数个投影类型逼近的方法，作为本章的子部分，我们简短的介绍一下步长的选择，和负梯度方向。在求解最优化问题中，最速下降法是简便的，即沿负梯度方向下降，是函数最优选择。濫驂膽閉驟羥闈詔寢賻。 (2-7) (2-8)这里的为步长，这个方法基本上已经就是投影梯度法的主要部分了，只是在上述文献中并没有对它进行细致的讨论。銚銻縵哜鳗鸿锓謎諏涼。我们可以看出，如果选择特定的步长， (2-9) (2-10)可得到LS算法的迭代公式。Lin在文献3中提出了一种改进的投影梯度法，此方法具有很要的优化性质。2.3.2 改进的投影梯度法 Lin提出的算法具体如下，通常我们解决界约束优化问题，定义l和u为上下界，假定k为迭代次数，通过投影梯度法更新规则为： (2-11)这里的投影P为 使用Armijo条件来线搜索，投影梯度法每步使用不同的步长，通过解决ALS算法的一个子问题来实现迭代，挤貼綬电麥结鈺贖哓类。1：给定，初始化矩阵变量x（或）。设定初始步长为。2：循环k=1,2 若步长并满足 （2-12） 直至不满足式（2-12），反之若步长不满足式（2-12），则 直至满足式（2-12） 3： (2-13)投影梯度法成功的将问题进行了转化，并证明了算法的极限点是稳定点，在NMF应用求最优解中有极大的帮助。然而PG算法虽然效果很好，但也有其自身的缺点，第一，梯度下降也许是最容易实现的技术，但收敛性慢。其他方法，如共轭梯度法有更快的收敛速度，至少在局部极小值附近，但比梯度下降更复杂的实现。基于梯度的方法也有缺点对步长的选择敏感，这是很不方便的大型应用程序，Lin的算法解决子问题时采用了梯度法。第二，Lin的方法使用单调线搜索技巧（2-12）来搜索步长，又通过简单乘除固定小数来改变步长，步骤繁琐，这又增加了算法的复杂性。赔荊紳谘侖驟辽輩袜錈。2.4 BBNMF算法在介绍解决非负矩阵分解问题的BBNMF算法之前，我们先讨论解决一般最优化问题的常用算法BB算法。1988年，Barzilia和Borwein提出了一种两点步长梯度算法，其基本思想是利用迭代当前点和前一点的步长信息来得到下一步的步长因子，步长满足塤礙籟馐决穩賽釙冊庫。 （2-14)或者 (2-15) 通过上面的（2-14）与（2-15）分别得到步长， (2-16) (2-17)其中，为内积，为了提高收敛速度，尽量使步长不要靠近0。BB方法每次迭代只需要复杂度0（n）的浮点运算和梯度评价。同时没有矩阵计算和线搜索过程中的需要。这样的BB方法具有近似的准牛顿性，因此是有利有效的方法。由于NMF问题可以转化为一个界优化问题，它是通常使用一个简单的有利法BB的方法。这项工作的目的是将BB梯度法运用在解决非负矩阵分解的子问题的策略上，尽可能频繁的接受给定的步长，只需一阶信息的存储过程。裊樣祕廬廂颤谚鍘羋蔺。Dai和Flecther指出交替使用上面的公式效果会更好。即 BB算法有着优秀的收敛效率，下降速度明显，远大于梯度法，ALS算法与BB算法结合产生了一种BBNMF算法，BBNMF算法是一个较新的算法，其基本思想是当ALS算法将NMF原问题分解为两个子问题后，两个子问题分别矩阵W和矩阵H的凸函数，那么就可以较容易通过投影的获得适合子问题的迭代结果，故BBNMF算法收敛速率很快，迭代效果好，本章提到BBNMF算法的目的在于比较BBNMF算法与本文第三章的改进算法进行比较。仓嫗盤紲嘱珑詁鍬齊驁。下面介绍BBNMF算法的步骤：采取与投影梯度法类似的停止条件，可以选择采用线搜索或者不采用来提升效果。绽萬璉轆娛閬蛏鬮绾瀧。当满足时，作为算法的停止条件。而后通过分别对ALS算法的两个子问题进行迭代循环，得到更新过后的基矩阵和系数矩阵，每一步后令自增1，最终可得到迭代结果。在本文第三章中，我们可以看到有关BBNMF算法的数值实验。骁顾燁鶚巯瀆蕪領鲡赙。第三章 PCGSNMF算法本章是本文的核心重点，在第二章中我们大致介绍了ALS算法，而第三章的基本思想为先通过ALS算法将NMF问题分解子问题(子问题是凸的)，故可以通过求解优化问题的思想得到其最优解，再运用本章3.1部分的改进的下降算法求解其子问题而得到结果。本章的4,5部分讲述了在稀疏约束条件下的算法实现。最终的数值实验结果证明了本算法的优越性。瑣钋濺暧惲锟缟馭篩凉。3.1 改进的下降算法通过文献6和8的启发，解决NMF的子问题可以使用本节的改进的下降算法。在通常解决无约束最优化问题时，我们通常使用梯度法（最速下降法），共轭梯度法，牛顿法，变尺度法等。梯度法虽然开始时收敛速度还令人较为满意，但由于梯度法之字形收敛的特点，在迭代一定步数后算法会收敛很慢，若使用本节的改进的下降算法，即解决了最速下降法在特殊情况下收敛慢的问题，又加快了共轭梯度法的收敛速度。鎦诗涇艳损楼紲鯗餳類。如无约束优化问题其通常的迭代求解的方法为 (3-1) 但NMF问题是有界约束的最优化问题而并非无约束的最优化问题，无法直接将解决一般无约束优化问题的方法应用于NMF问题，故我们考虑先将问题进行转化，可以采用构造子空间的方法，将指标集进行划分。再利用划分后的子空间确定下降方向，因为有非负约束的存在，直接运用混合算法构造下降方向并不一定是可行的，需要证明所构造的方向是下降的，在本章中已给出证明。 栉缏歐锄棗鈕种鵑瑶锬。 (3-2)当时，下降方向定为 先使得，再令 得到 (3-3) (其中的，在时，当时， ）当时有下降方向当时有下降方算法1：1：假定以矩阵为例，同理，设定初始矩阵，容限，令，。2：为了获得更高的收敛速度,在这里使用非单调的线性搜索技巧。需要计算满足下式的步长， ()其中，（是一个固定的整数）。令化简 计算出为了使算法有一个较高的收敛速度,选择。3：。4： 转入步骤2。注：的选择对算法的效率与收敛影响很大，也可以考虑对每步进行变化。可以令。其中的为投影， 3.2 算法的停止条件算法的停止条件选取与投影梯度法相同的条件： 在给定初值，初值，容限，初始矩阵,，后；定义 (3-4) (3-5)当满足：时算法停止。3.3 收敛性分析在这一部分讨论算法的可行性与收敛性：现证明是一个下降方向，当时， (3-6) 当， (3-7) 当， (3-8)辔烨棟剛殓攬瑤丽阄应。故是一个下降方向。已经证明了是一个下降方向，且有，故为优化问题的可行点，同时函数为有界函数，若序列有限，则明显有界，若序列无限，但其在函数f中的每一步迭代都是非增的，即，故只需证明其收敛点是否为稳定点即可。峴扬斕滾澗辐滠兴渙藺。若是稳定点，则其满足KKT条件。引理1：，当且仅当是式（1-2）的一个稳定点。证明： 所以故是稳定点。 ， 所以。由引理可知，时，是问题（1-2）的稳定点；反之，根据的定义及KKT条件，容易证明是稳定点，则。因此算法是稳定的。詩叁撻訥烬忧毀厉鋨骜。故算法满足KKT条件，算法的收敛点是稳定点，最终结果将不会出现震荡。3.4 稀疏约束稀疏就是利用少量的元素有效地代替大量的数据或向量。通俗地讲，就是大多数元素为零而只有少量元素不为零。很多文献资料中都提出了度量矩阵稀疏度的方法，这些方法通常都是建立一个从的映射。按标准来讲，向量中仅含有一个非零元素是最稀疏的，其稀疏度为1，而如果向量所有元素都相等且不为零，则其稀疏度就是零。则鯤愜韋瘓賈晖园栋泷。为了更好的提升算法的属性，故考虑给算法添加稀疏性的约束。将NMF问题中加入惩罚因子，这样将会使效率更快。在本文第一章提到，NMF被目前被划分为BNMF与INMF两种，而INMF中最受欢迎的一种就是添加稀疏约束的INMF问题， SNMF（稀疏非负矩阵分解）。稀疏通俗的来讲，就是通过用更少的元素来代表大量的数据，NMF算法本身在无监督条件下就有不错的稀疏属性，分解过后的结果矩阵有一些零元素的存在，目前希望使得结果中的稀疏越来越好。Hoyer在文献12中指出是要求有更好的稀疏度，还是要求有更好的稀疏度，或者两者同时产生更好的稀疏度没有明确的要求，这取决于问题的实际情况。例如，某位医生分析疾病模式，假设大部分病症都是罕见的（因此也就是稀疏的），但是每种病症都可能引起大量的症状。现假设矩阵的的列代表每一个不同的个体，行代表不同的症状，那么在此种情况下，分析得到系数矩阵应当越稀疏越好，而对基矩阵没有作任何约束。再举另外一个例子，当需要从图像数据库中学习有用的特征时，可能需要基矩阵和系数矩阵都应当越稀疏越好，这样也才会有意义。上述实例说明任何给定的对象都是在当前的几张图像中并且或多或少影响着一小部分的图像。胀鏝彈奥秘孫戶孪钇賻。本文对两者都添加了稀疏约束，稀疏的方法通常有添加1-范数，添加2-范数，增加惩罚因子，增加控制矩阵的许多种方法。本文采用度量稀疏的方法是用1-范数和2-范数的结合后的函数，用这两种方法来约束基矩阵和系数矩阵。鳃躋峽祷紉诵帮废掃減。3.5 PCGSNMF算法在原始问题上现在加入新的稀疏约束条件，首先对基矩阵进行约束，要求非负矩阵的元素之和等于1，即的1-范数等于1的基础上最大化的2-范数，用数学描述即当的条件下，使得最大，再对系数矩阵进行约束，考虑对加1-范数约束条件，即最小化的1-范数，数学描述为，将这两个条件都加入到原问题中，目标函数将更新为：稟虛嬪赈维哜妝扩踴粜。 (3-13)使得,，。现将PCG算法中的与用如下的梯度替换， 可得用新算法解决SNMF问题算法， (3-14) (3-15)算法结束时，可以通过公式来计算矩阵的稀疏度，为或矩阵，可以看出PCGS算法属性更优。第四章 数值实验本部分通过对各算法进行实验，来对比各算法的效率，对比的数据有，迭代次数iter，运行时间cputime，函数（与的差异），最终投影梯度P-G,H矩阵的稀疏度H-spa。通过对比结果，来证明PCGS算法的一些优点。陽簍埡鲑罷規呜旧岿錟。参数设定：尽量保证函数数值的相近，而后对比迭代次数，运行时间与最终梯度的差异。容限tol=1e-7，要求最大迭代步数Maxiter（M）小于等于1000次，取值为0.5，取值为0.9，。沩氣嘮戇苌鑿鑿槠谔應。4.1 中小型问题对比Problemalgorithmitercputimef(W,H)P-GH-spaV=rand(100,50)PG1830.27291.22E+020.03170.2654W0=rand(100,10)BB1190.36741.22E+020.02920.3655H0=rand(10,50)PCGS1070.36511.22E+020.02810.5321V=rand(200,200)PG1523.39998.21E+020.15710.2024W0=rand(200,50)BB1131.89748.21E+020.15320.3176H0=rand(50,200)PCGS1052.20238.21E+020.15930.4235V=rand(300,500)PG1937.66874.26E+030.42890.3142W0=rand(300,50)BB290.98254.26E+030.44950.4539H0=rand(50,500)PCGS270.84924.26E+030.43850.5031V=rand(300,500)PG1406.58572.81E+032.24580.3417W0=rand(300,150)BB121.99812.81E+032.26270.4375H0=rand(150,500)PCGS122.23732.81E+032.21450.5623表3-1：PCGSNMF与其他算法在小中型NMF问题上的比较图3-1-1：迭代次数对比图3-1-2：运行时间对比图3-1-3：H矩阵稀疏度对比由表3-1及三幅图可以看出在处理小中型NMF问题时，PG的优点是算法简单易于实现，缺点则是当迭代到一定步数后，计算时间较慢，迭代步数多。而PCGS算法优点在于精度较高，迭代步数少，稀疏表现好，而程序计算时间稍长。BBNMF算法，迭代步数最少，误差少，收敛快，程序运行时间慢。若中小型问题程序不限制迭代步数，对误差要求不高可以仍使用PG算法，若要求减小误差，则PCGS算法,BBNMF算法均有好的属性，同时PCGS可以保证优秀的稀疏属性，接下来我们看NMF算法在解决大型矩阵问题上的差异。钡嵐縣緱虜荣产涛團蔺。4.2 大型问题对比Problemalgorithitercputimef(W,H)P-GH-spaV=rand(2000,1000)PG22428.10387.42E+0420.980.3107W0=rand(2000,50)BB11417.18487.42E+042.94530.3896H0=rand(50,1000)PCGS9713.20547.42E+042.88910.4572V=rand(3000,2000)PG5257.32022.19E+0534.870.2659W0=rand(3000,150)BB3534.88162.19E+055.98650.3451H0=rand(150,2000)PCGS3228.54972.19E+054.43620.4448V=rand(3000,5000)PG60122.685.44E+05283.350.2323W0=rand(3000,350)BB2086.12725.44E+0525.570.2787H0=rand(350,5000)PCGS1890.20215.44E+0520.8340.3542V=rand(5000,5000)PG60331.9519.36E+05691.560.2528W0=rand(5000,500)BB19152.2549.36E+0590.070.2842H0=rand(500,5000)PCGS18158.5239.36E+0578.3630.3697表3-2：PCGSNMF与其他算法在大型NMF问题上的比较图3-2-1：迭代次数对比图3-2-2：运行时间对比图3-2-3：H矩阵稀疏度对比由表3-2可以看出，PG算法在处理大型问题时其自身问题较为明显，计算时间过长，迭代步骤过多，并不推荐PG算法来解决大型NMF问题，以上的数据展现了这个现象， Lin的方法是单调递减方法，而BBNM