试论增量式非负矩阵分解方法的研究

《试论增量式非负矩阵分解方法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、复旦大学硕士学位论文增量式非负矩阵分解方法的研究姓名：郭立申请学位级别：硕士专业：计算机软件与理论指导教师：张守志20090425摘要：非负矩阵分解方法是一种近年来被广泛研究的降维方法，现有的非负矩阵分解算法在应用于问题规模逐渐增大的情形时，运算规模随之增大、空间和时间效率不高。本文对此提出一种增量式非负矩阵分解算法，它使用分块矩阵的思想降低了运算规模，利用上一步的分解结果参与运算从而避免重复运算，文章从理论角度对算法的性质进行了分析，包括存在性、唯一性、稳定性、收敛性等性质，证明了算法的有效性，并与类

2、似的增量式非负矩阵分解算法进行了比较，最后通过实验结果表明了新算法节约计算资源的显著效果。主题词：非负矩阵分解j矩阵分解；增量式算法中图法分类号：TPl8文献标识码：A[Abstract]Non-negativeMatrixFactorizationalgorithmisarecentlydevelopedandstudiedtechniqueforfindinglincarrepresentationsofnon-negativedata．WhenexistingNon-negativeMatrixF

3、actorizationalgorithmappliestoaproblemofincrementalscale，theconsumptionofspaceandtimebehavesine伍ciency．Inthispaper,arlIncrementalNonnegativeMatrixFactorizafionalgorithiniSproposed，whichusespartitionedmatrixtheorytoreducethecomputingscale，andusesdecomposi

4、tionresultsalreadyderivedtoavoidre-calculatingeverytime．Weanalyzethepropertiesofthisincrementalalgorithm．proveitscorrectnessandcompareittothesimilaralgorithms．Expcrimeritsshowthatthenewalgorithmperformsefficientforsavingcomputingresources．[Keywords]Non-n

5、egativeMatrixFactorization；matrixfactorization；incrementalalgorithm¨第1章引言我们在科研和生产的各个领域一直都面对着大量的数据和信息，矩阵已经成为这些数据信息最常用的载体之一，矩阵分解随之成为处理和分析这些数据的有力工具。在实际问题中，我们经常还会碰到所有元素非负的矩阵，这种非负性源自很多数据是具有确切意义的物理量，此时我们通常也希望分解的结果仍然是由所有元素非负的矩阵构成，以保留它们所具有的可解释性和某些物理意义。因此，在矩阵中所有元

6、素均为非负数的约束下的分解方法一直是很有意义的研究问题。1999年，Lee和Setmg在Nature上所发表的文献[21，阐述了非负矩阵分解(NonnegativeMatrixFactorization，NMF)的基本思想，并在2000年提出一种迭代算法【3】，使得相关研究蓬勃展开。近几年中，非负矩阵分解成功的应用于图像、语音等多媒体信息的分析与处理，文本聚类与挖掘，生物医学、遗传学和化学的各种研究，以及环境数据处理、信号分析与目标识别等诸多方面。但由Lee和Seung提出的算法【3】在应用于实际问题时

7、碰到的一个情景是当前的各种应用中数据量显著变大，像网络数据以及大型的图像数据库所形成的矩阵规模都非常之大，在处理问题规模逐渐增大的情形时，直接使用现有的算法每次都重新运算全部数据，则参与运算的矩阵规模太大，在保证效果的同时效率就比较低下。因此增量情形下如何对现有算法进行优化就是有必要研究的一个问题。本文主要工作如下：■介绍了非负矩阵分解方法的意义、特点、研究现状及应用。■在分析了现有非负矩阵分解方法的不足之后，提出增量式非负矩阵分解算法(IncrementalNonnegafiveMatrixFacto

8、fizationalgorithm，INMF)的研究意义，并介绍了已有的相关工作。■提出了一种增量式非负矩阵分解算法，使得非负矩阵分解算法在应用于逐渐增大的矩阵时能利用上一步的分解结果，从而达到节省内存资源和时间消耗的效果。一对提出的方法从理论角度进行分析，包括存在性、唯一性、稳定性、收敛性等方面，并与同类增量式算法进行了比较。■通过实验验证了算法的性能，包括分解精度，时间消耗，初始化与收敛速度等方面，并对实验结果进行了分析。本文结构安排如