一种非负矩阵分解的快速稀疏算法

摘要: 提出了一种非负矩阵分解的快速稀疏算法，该算法有利于处理高维小样本数据.在非负矩阵分解的过程中，通过代数变换，将原高维n×m阶的非负矩阵分解转化成低维m×m阶非负矩阵分解，大大提高了分解速度.在目标函数中加入了约束稀松度的项，通过控制稀松度，提高分解得到的潜在语义信息，改进文档集的话题划分，并能快速提取主题相关的语句生成文摘.

关键词: 非负矩阵分解；快速稀疏；文本文摘

中图分类号:TP 391.41

文献标志码:A文章编号:1672-8513(2011)04-0262-05

A Fast and Sparse Algorithm for Nonnegative Matrix Factorization

SONG Jinge, YANG Jing, CHEN Ping，SHE Yumei

(School of Mathematics and Computer Science, Yunnan University of Nationalities, Kunming 650031, China)

Abstract: A fast and sparse algorithm for nonnegative matrix factorization（NMF） is introduced. The algorithm is conducive to deal with the high-dimension-small-sample data. In the nonnegative matrix factorization processing, by some algebra formulation, the n×m high-dimension matrix to be factorized is changed into a m×m low-dimension matrix, which greatly improves the rate of decomposition. The sparseness item is also added to the objective function in the algorithm, by controlling the sparseness in the factors, the proposed method extracts more meaningful latent features and improves topic identification, which can be used in sentence extraction for summarization.

Key words: nonnegative matrix factorization; fast and sparse; document summarization

1999年，Lee和Seung[1]首次提出了非负矩阵分解，为人们处理大规模数据提供了一种新的方法.2001年，Lee和Seung[2]给出了非负矩阵分解的乘性迭代公式，有效地保持了数据的非负性.由于非负矩阵分解算法易于实现，存储空间小，分解形式的可解释性好，所以被应用于文本分析与聚类、数字水印、人脸识别、图像检索、基因特征提取等研究中[3].目前，人们对于非负矩阵的研究主要集中在3个方面：稀疏性增强的NMF算法；鉴别性NMF算法；加权NMF算法.

本文提出了一种非负矩阵分解的快速稀疏算法，通过代数变换把对原矩阵分解转化成对维数较低的对角矩阵的分解，在分解的过程中加入了对系数矩阵稀疏度的控制.给出了此算法的迭代规则以及收敛性证明过程，将其应用在文本文摘中.

1 非负矩阵分解问题

11 问题描述

给定一个n×m阶非负矩阵V，找到2个n×r和r×m阶的非负矩阵因子W和H，使得V=WH.将矩阵W称为基矩阵，矩阵H称为系数矩阵.

在矩阵V中列向量可以表示为：V*j=∑rl=1HljW*l，其中基向量W*l是矩阵W中的列向量，权重系数Hlj是矩阵H中对应的列向量中的元素.所以矩阵V中的列向量可看作是基向量W*l与权重系数Hlj的一个线性组合.因此，矩阵W中的问题就可以转化为在矩阵W的列向量所形成的新的线性空间中的问题.矩阵H中的列可看作是矩阵V中对应列在该特征空间中的新的特征向量.

12 算法步骤

非负矩阵的分解是一种低秩逼近算法，常用V和WH间的欧几里德距离平方作为目标函数来达到最佳逼近.目标函数为：

由于（1）式和（4）式都含有权重系数矩阵H，所以可以把对矩阵V的分解转化为对矩阵X的分解，同样可以得到矩阵H.矩阵V是n×m阶的，而矩阵X是m×m阶的，对于高维小样本数据来说n>>m，所以此转化在矩阵分解过程中起到了降维的作用，使矩阵分解的复杂度降低.

对于非负矩阵稀疏度的约束，Hoyer[5]提出:约束矩阵W的稀疏度好，还是约束矩阵H的稀疏度好，还是约束两者的稀疏度好，取决于问题定的应用情况.比如，一个医生分析疾病模式，假设大部分疾病是稀有的（因此稀疏）.但是每种疾病都能引起大量的症状.假设矩阵的行代表症状，列代表不同的个体，这种情况下系数矩阵应该稀疏而基矩阵可以不受约束.另如，当需要学习图像数据库中有用的特征时，可能需要约束W和H的稀疏性才更有意义.这表明任何给定的对象是在当前的几张图像中并影响一少部分的图像.

对于处理行表示特征词，列表示句子的文本矩阵的分解来讲，采用约束矩阵H的稀疏度.所以在对上述对角矩阵X分解时，在目标函数中采用了1-范数形式来约束矩阵H的稀疏度.目标函数为：

由表2我们可以看出，适当的λ值能够得到矩阵[WTHX]H[WTBX]较高的稀疏性，合适的稀疏度有利于保留数据的主要特征，学习更清楚的局部特征，还可以减少储存空间.

243 文本文摘举例

给定一段文章如下：教学具有多种形态，是共性和多样性的统一.教学作为学校进行全面发展教育的一个基本途径，具有课内、课外、班级、小组、个别化等多种形态.教师和学生共同进行的课前准备、上课、作业、练习、辅导、评定等都属于教学活动.随着社会的发展，教学既可以通过师生间、学生间的各种交往进行，也可以通过印刷、广播、电视、录音、录像等远距离教学手段开展.教学作为一种活动，一个过程，是共性与多样性的统一.

对这段文章运用Lee等[6]提出的文摘方法，并把求[WTHX]H[WTBX]矩阵的算法部分改为本文提出的FSNMF算法去求[WTHX]H[WTBX]矩阵，最后得到的每个句子的相关度为：

GRS =(1.0e-003)×〔0.4751 0.1186 0.0291 0.0112 0.3080〕.

由此，可以判断出第1句是最重要的句子，其次是第5句.所以这一段的文摘句就为：教学具有多种形态，是共性和多样性的统一.

由此例，可以看到将非负矩阵分解的快速稀疏算法应用于文本分析能够快速准确地得到文章的文本文摘.

3 结语

本文提出的非负矩阵分解的快速稀疏算法，通过代数变换使得数据进行降维，在目标函数中附加约束稀疏度的稀疏项从而定义了目标函数，并且给出了迭代规则和收敛性证明.并且举例说明了此算法使得矩阵的分解速度和稀疏度都有所提高，又进一步利用此算法进行了一个简单的文本文摘，准确地得到了文摘的结果.

参考文献:

［1］LEE D D, SEUNG H S.Learning the parts of objects by non-negative matrix factorization［J］. Nature, 1999,401(6755):788-791.

［2］LEE D D,SEUNG H S. Algorithms for non-negative matrix factorization［C］//Advances in Neural Information Processing Systems 13.Cambridge:MIT Press,2001:556-562.

［3］李乐,章毓晋.非负矩阵分解算法综述［J］.电子学报,2008, 37(4):737-743.

［4］王文俊，张军英.一种非负矩阵分解的快速方法［J］.计算机工程与应用,2009,45(25):1-2,6.

［5］HOYER P O. Non-negative matrix factorization with sparseness constraints ［J ］.J Mach Learning Res, 2004, 5(9): 1457-1469.

［6］LEE J H, PARK S , AHN C M, et al. Automatic generic document summarization based on non-negative matrix factorization［J］. Information Processing and Management,2009,45: 20-34.