第5卷第4期 智能系统学报 Vol.5 No.4 2010年8月 CAAI Transactions on Intelligent Systems Aug.2010 doi:10.3969/i.issn.1673-4785.2010.04.006 动态学习的非负矩阵分解算法 杨志君，叶东毅 (福州大学数学与计算机科学学院，福建福州350108) 摘要：为在对现有增量型非负矩阵分解算法存在的一些缺陷进行改进.给出了一个基于误差判断的增量算法有效 性准则.在此基础上，利用增加样本前的非负矩阵分解结果进行增量分解初始化，提出了一种新的动态非负矩阵分 解算法.在多个数据集上的实验结果表明该算法可以实现对基矩阵和编码矩阵的即时更新，且具有较低的计算复杂 度，在处理动态数据集时，还可有效识别噪声点，是一个可行有效的动态分解算法. 关键词：非负矩阵分解；动态学习；初始化；误差准则 中图分类号：TP181文献标识码：A文章编号：16734785(2010)04032007 A dynamic learning algorithm based on non-negative matrix factorization YANG Zhi-jun,YE Dong-yi College of Mathematics and Computer Science,Fu Zhou University,Fu Zhou 350108,China) Abstract:To improve the performance of the incremental non-negative matrix factorization algorithm,error estima- tion criteria for judging the effectiveness of the incremental algorithm was presented.Then,a new dynamic non- negative matrix factorization algorithm was proposed whereby incremental factorization was initialized with the al- ready factorized matrices before adding new samples.Experimental results on a number of data sets showed that the proposed algorithm is capable of instantly updating both the base matrix and the code matrix.Another benefit of the method is that the computational complexity is relatively low.The proposed algorithm can also identify noise points when dealing with dynamic data.So it is a feasible and effective dynamic factorization algorithm. Keywords:non-negative matrix factorization;dynamic learning;initialization error criteria 近年来非负矩阵分解方法(nonnegative matrix需要随样本数的动态增加做相应的调整.例如，在分 factorization,NMF)l14在聚类分析、人脸识别、语音析疫情的病例时，将每个病人所需测量的生理参数 识别、声音分离等领域取得了很好的应用.但NMF 是否异常作为二值(0,1)样本，则分解产生的基矩 也存在一些缺陷，如不能动态地、实时地处理加入的 阵和编码矩阵分别为各个症状（包含若干个有可能 数据向量，当加入新的数据向量时只能将所有的数 异常的生理参数)和每个病例可能具有的若干症 据向量重新计算得到基矩阵和编码矩阵，这在大规 状.当出现新的病例时，应重新调整对各个病人的诊 模数据的处理中显得不太合理。 断，即他们的症状.保持编码矩阵不变显然是不合理 针对以上问题，人们已经提出了若干增量型 的.Co[61等人在满足矩阵分解惟一性的条件下，使 NMP算法.例如，Bucak等人[S1提出了一种增量非负 用原基矩阵和新样本来更新基矩阵，得到一种新的 矩阵分解算法(incremental nonnegative matirx factori- 动态非负矩阵分解算法（online nonnegative matrix zation,INMF).该算法在增加新样本时，保持原样本 factorization,ONMF),但它是以NMF满秩分解为前 数据集编码不变，通过一个加权目标函数来控制矩 提的.因此，该算法不适用于要求基向量的个数小于 阵分解的无记忆性.但在实际应用中样本编码经常 样本矩阵的秩时的情况.文献[7]中提出一种动态 分块非负矩阵分解算法BNMF,该算法运用分块的 收稿日期：2009-0608. 基金项目：国家自然科学基金资助项目(60805042) 思想对NMP算法进行修改.将大矩阵按每类进行分 通信作者：叶东毅.E-mail:yicd@zu.cdu.cn. 块，即同一类的训圳练样本形成一块小矩阵，然后对每
第4期 杨志君，等：动态学习的非负矩阵分解算法 ·321· 块小矩阵进行分解，最后再将分解后的小矩阵合成1.2在处理动态数据集上的不足 大矩阵.当每类的训练样本数较多时，BNMF也会存 在处理动态数据集上，当增加样本时，其影响在 在和NMF一样的缺点. 分解结果中应有适当的表现，即分解产生的基矩阵和 上述增量型NMF算法均未给出判断动态非负 编码矩阵应随之更新.NMF算法在诸如此类的批处 矩阵分解算法优劣的标准，使算法的有效性无法得 理应用中存在一些问题。由于V的每一列对应于一个 到衡量.鉴于此，本文给出一条误差准则用于判断增 不同的样本，每增加一个样本即增加V的度.NMF每 量型NMF算法的有效性.详细的定义在第3部分中 次迭代的复杂度是O(mr),显然随着维度增加其复 给出.此外，考虑到在一些应用中，当增加样本时，需 杂度呈线性增长因此，每增加一个样本即重新对V 对编码矩阵和基矩阵均进行动态更新，且算法的执 进行NMF分解是不现实的.再者，NMF分解的计算 行时间应尽可能短，同时具有较小的剩余误差.在 复杂度和迭代次数呈线性关系，增加新样本时迭代次 NMF的许多实际应用中，通常在相邻的2次迭代产 数相应增加使动态处理数据不具有可行性 生的剩余误差之差小于预设的阈值时中止迭代过 2几个典型的增量型算法分析 程.据此，本文提出一种新的动态非负矩阵分解算法 (DNMF).当增加样本时，用原样本集分解产生的编 2.1 ONMF[6算法及其不足 码矩阵和基矩阵对新样本集的分解进行初始化，使 该算法对其定义的目标函数加上如下限制， 迭代从接近于阈值的位置开始.实验表明该方法有 8.t.h:Xh:=0,j≠i. 效的减少了迭代次数，缩短了收敛时间. 并将目标函数表示为 1非负矩阵分解 J=之V-wHIB+aHH 1.1数学定义 式中：T为对角元素为零，其余元素均大于零的矩 给定一个n行m列的非负矩阵V,将其近似地 阵，α是一个正数.后根据KKT条件得迭代公式： 分解成2个非负矩阵之积，分别记为W与H,使得 (VH)黄 (4) V≈WH,即 w与←wg(wHH)与 (Wv) Vg≈(WH)g=∑WaH (1) a hg←hy(wwE+aH)g (5) 分解之后的矩阵W与H的维数分别为n×r和 最后算法利用U和H通过式(4)和式(5)来计 r×m.r的选取满足r<min{m,n}. 算而和，实现增量分解. 如果用v和h分别表示矩阵V与H中对应的 该算法是以满秩分解为前提的，因此不适用于 列向量，由式(1)可得V≈Wh.由此可见，原始矩阵 要求基向量的个数小于样本矩阵的秩时的情况，且 V中的列向量v以通过矩阵W以一定的权重h表 算法中要求W1可逆，这2点较大地限制了算法的 示出来.因此，矩阵W可以看作是基矩阵，其中的每 应用范围.另外文中的2个参数α和T并未给出明 一列代表基向量，而矩阵丑中的每一列代表与矩阵 确的定义，代码也无法获得，使实验不能重现， W中基向量相对应的编码系数为了找到一个矩阵 2.2INMF51算法及其不足 分解W与H,使得IV-WH‖最小，且满足W≥0， 算法用参数α和(1-α)来控制前k个样本和 H≥0可以使用如下的规则进行迭代计算11： 第(k+1)个样本对目标函数的影响： (WV) Fxel =aF+(1-a)fi. Hg←Hg(wwH)。 (2) 接着使用梯度下降算法得出h+1和W+1的更 (VE) 新规则. wn←Wa(wHH)a (3) INMF算法是在假定新样本对前k个样本的编 在计算过程中，随机选取非负的初始矩阵W与 码影响不大的前提下提出的，而在许多实际应用中， H,定义适当的迭代运算次数之后，按照式(2)和 如视频监控，在原来静止的画面中，出现一个移动的 (3)进行迭代计算即可得到最优的W和H. 物体，则在少量的几个新增样本出现后，应对基矩阵
322 智能系统学报 第5卷 和编码矩阵均做适度的调整，以使剩余误差尽量小 果的基础上通过对原编码矩阵和原基矩阵进行某种 DNMF算法在调整基矩阵的同时，将新增样本的影 修正得到的新基矩阵、新编码矩阵为W和丑.则可 响即时施加到原样本的编码中，即随着样本的持续 得增量差的定义如下： 加入，编码矩阵随之做相应的调整， 定义2增量差 INMF算法使用a和(1-a)来控制前k个样本 e=‖Vn+1-Win+1‖. 和第(k+1)个样本对目标函数的影响.若α接近于 式中：”+1为新增样本向量，五.+1为日中v。+1所对应 1,则第(k+1)个样本的影响可以忽略.而文献[5] 的编码向量。 所进行的实验中，均削弱了新增样本的影响.如在第 在实际应用中，为保证增量型NMF算法的有效 1项实验中，为比较NMF和INMF算法分解背景样 性，应保证分解结果有一定的准确度，避免因算法本 本数据集所产生的剩余误差，将α分别设为0.2及 身导致分解的质量下降或下降太大，为此提出判断 0.3,均接近于0，降低了新增样本的影响.显然，即 增量型NMF算法有效性的误差准则： 使比较结果INMF的剩余误差较NMF小，也是没多 准则1当增量型NMF算法的分解结果满足 大意义的.文献[5]中第2和第3项实验也存在同 e≤e·时，算法是比较合理的. 样的问题 由于e'是对V"重新进行NMF分解得到的最大 样本差，因此最好的情况是通过某种增量型算法得 3本文算法的基本思想 到的最大样本差不超过”，而通常增量型算法都是 DNMF的目标是增加新样本时，将其影响即时 对原编码矩阵和原基矩阵进行某种修正得到新的分 施加到编码矩阵W和基矩阵H上，且尽量减少迭 解结果，难以达到这样的准确度.鉴于此，提出以上 代次数，即具有较低的计算复杂度.另外，增加样本 准则，当增量差满足e≤e·时，结果即是可接受的. 时，对W和H的更新应使DNMF分解具有较低的 3.2算法的设计思路 重构误差且算法不需要满秩分解的限制，即应具有 对于动态数据集，新增样本和原先的样本集通 更广泛的应用.以下描述DNMF的基本思想及算法 常具有一定的相似性，即具有许多共同特征.因此， 步骤 新增样本对原先个样本分解产生的基矩阵W。和 3.1相关定义 编码矩阵H,进行的更新通常是不显著的.鉴于此， 假设W.和H,为原k个样本进行NMP分解产生 将W.用于(k+1)个样本时W1的初始化，H.用 的编码矩阵和基矩阵，Ck为代价函数，即重构误差 于H+前k列的初始化.相对于随机初始化，该初 Ck=‖V-WH.‖2= 始化方法使迭代过程从较接近于局部最优收敛点的 k }∑∑(V,-(wa)) 地方开始进行，且保证增加样本前后算法能以较大 2台台 概率收敛于同一收敛点，有效的减少了迭代次数.同 增加一个样本时，将编码矩阵和基矩阵定义为 时，保证了分解的准确度，实现对W+!和Hk+1的即 W+和H+1,”为样本矩阵.此时代价函数为 时更新。 Ck+1=‖V”-W+1H+1‖2= 3.3算法设计 号2Σ(v,-(wAg)只 本节具体给出DNMF算法.该算法是在NMF算 2台台 法的基础上对其初始化方式进行改进得到的.当新 为判断增量算法的有效性，进行如下定义： 增一个样本时， 定义1最大样本差 1)保存k个样本时分解产生的基矩阵W.和编 ema=max‖：-Wh:l,i=1,2,…,n 码矩阵H: 式中：”：是第i个样本向量，W是分解产生的基矩 2)用W。初始化W+1,H.初始化H+前k列. 阵，h:是第个样本的编码向量，n为样本数。 3)对Hk+1第k+1列进行随机初始化. 当增加一个样本时，对新的样本数据矩阵重新 4)使用2)、3)的迭代规则进行计算 进行NMF分解，设得到的最大样本差为e.同时， 5)符合迭代停止条件，算法结束，否则转4)， 设新样本数据矩阵V”在原样本或者原样本分解结 新增样本时，和INMF相比，DNMF对编码矩阵
第4期 杨志君，等：动态学习的非负矩阵分解算法 ·323· 和基矩阵均进行了调整，减小了剩余误差.且从3.2 平均到样本向量中的各个元素（元素个数为向量维 节的分析可知，算法第2)步使得DNMF从较接近于 数)，误差约为0.088，相较于上限1，误差较小 收敛点的位置开始迭代过程，降低了计算复杂度.当 4.2PET2001数据集 增加样本时，若该类的训练样本数较大，相比 PET2001数据集是某道路视频监控的各帧图像 DNMF,BNMF的计算复杂度较高， 的集合，其中包含不同光照条件下的背景图像和某 些时刻人、车等的移动画面.静态背景和随时间变化 4实验结果与分析 的移动物体使该数据集较适合于评价非负分解算法 为评价DNMF算法在动态数据集上的效果，进 的动态学习能力. 行了5项实验.第1个实验的数据集由Matlab生 为便于处理，从中选取800张图像(dataset1, 成；接下来的3个实验分别使用PET200181、tempo- 0350-1150)并将其转换为134×100的jPg格式的灰 ral image6和swimmers[9]数据集；第5个实验展示 度图.由于相邻帧的图像没有太大的变化，从每10 了在分离的swimmers数据集上DNMF识别噪声点 帧中取一帧以更好的评价算法的动态学习能力，共 的能力 80帧 实验在Windows XP环境下进行，Cpu为赛扬 实验中，以前35张为初始样本集，接着每隔6 2.40GHz,内存512M,Matlab为7.0版. 张分别使用DNMF和INMF对图片构成的数据矩阵 4.1使用Matlab生成的不同规模数据集 进行增量分解，取「为20，迭代中止条件为 DNMF算法使用前k个样本分解产生的基矩阵 T-T:+1≤5，INMF的a参数取0.3. W和编码矩阵H来初始化W+1和Hk+1,可使迭 图1为实验中NMF的最大样本差、DNMF的增 代以较大概率收敛于原收敛点，同时使迭代从较接 量差和INMF的增量差随样本数的变化情况.可看 近于收敛点的位置开始，减少了中止所需的迭代次 出在该数据集中NMF的增量差均高于NMF的最 数.实验中用Matlab随机生成函数生成不同规模的 大样本差，随着样本数持续增加，INMF算法的增量 数据矩阵，当增加一个随机样本时分别测试DNMF 差大幅增长.而DNMF算法的增量差均低于NMF的 的增量差和NMF的最大样本差.设样本数为m时， 最大样本差，证实DNMF的有效性.DNMF相对于 第次迭代各样本所产生的平均误差为 INMF具有更好的准确率是由于INMF在增加新图 T:=‖V-WH:‖2/m 像时，原先的编码矩阵没有随之变化，而基图像已经 设置迭代中止条件为T:-T:+1≤0.0001， 更新，使增量差加大.另外，随着样本数的增加， 表1中的次数指算法中止时经过的迭代次数. DNMF的增量差同样有较大增长，这和r有着密切 基向量个数取10. 的关系，具体研究留待以后的工作 表1不同数据规模DNMF和NMF的样本差和迭代次数 12x10 Table 1 Sample error and iteration times of DNMF and INMF 10 DNME NMF with different data scales -NMF 未增加样 增加后 增加后增加后 增加后 6 本前的数 NMF所 NMF最大 DNMF所 DNMF 据规模 需次数样本差 需次数增量差 100×100 524 8.623 67 7.285 40 50 60 70 300×300 732 26.29 72 样本数 22.50 500×500 894 44.17 43 41.81 图1最大样本差和增量差随帧数的变化情况 800×8001005 71.51 76 67.69 Fig.1 The biggest sample error and incremental error chan- 1500×10001247 129.8 124.4 3000×10001660 261.1 80 244.2 ging with the frame number 图2为实验中各算法执行时间随帧数的变化情 表1的实验结果表明DNMF在该数据集上符 况.在实验的大部分过程中，DNMF算法的执行时间 合准则1，是有效算法.且由于迭代从接近于收敛点 低于INMF.由于DNMF总是以接近于收敛点的位置 的位置开始，使DNMF和NMF相比减少了迭代次 开始迭代，因此有效的减少了算法的执行时间.随着 数，缩短了算法执行时间.表1中所示的最大样本差
·324 智能系统学报 第5卷 样本数的持续增加，DNMP的执行时间超过NMF,这 种情况同样和r的取值有较为密切的关系， 300 NME DNMF 200 INMF 图5样本数为100时的部分生成因子 Fig.5 Some of the factors with 100 samples 100 可看出图4中最左边的4个生成因子均出现在 DNMF分解产生的基图像中.说明NMF具有较强的 30 40506070 提取线性样本集各组成成份的能力.而DNMF在处 样本数 理动态数据集时同样具有这样的功能.当样本集增 图2各算法执行时间随帧数的变化情况 至200时，分解产生的部分基图像如图6， Fig.2 Run time of the algorithms changing with the frame number 4.3 temporal image数据集 文献[6]中使用temporal image数据集来验证 ONMF算法在满秩分解条件下处理动态数据集的有 效性.由于暂时无法获得ONMF算法的代码进行实 验对比，因此本文也采用该数据集来验证DNMF的 动态学习能力.图3给出了数据集的部分生成因子， 图6样本数为200时的部分生成因子 每个生成因子对应于一张10×10像素的图片，图片 Fig.6 Some of the factors with 200 samples 中包含一条横线或竖线.该数据集中的每张图片均 同样可看出有8个生成因子出现在基图像中， 是生成因子的某种线性组合.为验证算法的动态学 其中图6的第一个图像和最后一个图像是由2个生 习能力，图3中最左边的2个生成因子随时间左右 成因子部分重叠产生的.当样本集为300时算法生 或上下移动，其他生成因子保持不变，如图4. 成的部分基图像如图7. 图3 temporal image数据集的生成因子 Fig.3 Factors of temporal image dataset 图7样本数为300时的部分基图像 Fig.7 Some of the factors with 300 samples 可以看出，在分解结果中，各生成因子均有不同 程度的体现.另外，最后分解得到DNMF算法的最 图4随时间变化的生成因子 大样本差为0.4425，对300张图像进行NMF分解 Fig.4 Factors changing with the time 得到的最大样本差为0.3034.可见DNMF分解具有 根据图4中6种不同的情况各生成50张图片， 较高的准确率。 共300张.实验中r取30，迭代中止条件为 4.4 Swimmer数据集 T:-T:+1≤0.0001.将前50张图片作为初始样本 Swimmer数据集包含一系列的黑白图像，每个 集，剩下的250张图片每增加1张均进行DNMF分 图像有4个可移动的部分（四肢），每个部分可以旋 解，观察分解产生因子的变化过程.当样本集增至 转到4个不同的位置（关节）.且每个黑白图像的中 100张时，分解产生的部分基图像如图5所示. 心有一个包含12个像素的躯干和4个包含6个像
第4期 杨志君，等：动态学习的非负矩阵分解算法 325. 素的可移动部分，每个可移动部分可位于4个不同 数据矩阵Vs·对Vs使用DNMF进行分解，所需迭 位置.因此总共有256张图像包括所有的肢体位置 代次数为591次，各样本产生的平均误差为0.996. 组合.每张图像包含32×32个像素.图8给出了该 DNMF产生的基图像如图10. 数据集的一个子集， 可以看出图9中去掉的部分完整的出现在若干 个基图像中，表明DNMF对基矩阵和编码矩阵进行 个不个下 了即时更新. 4.5DNMF识别噪声的能力 文献[l0]中分析了NMF和K-means聚类之间 个八个少 的关系，得出2种算法具有相同的目标函数.DNMF 作为NMF的改进算法同样具有聚类效果.在这个小 图8 Swimmer数据集 节里检验了DNMF在识别噪声方面的效果.和上个 Fig.8 Swimmer dataset 实验一样从swimmers数据集的4个活动部分中去 该数据集在文献[9]中是用来展示NMF算法 掉其中一个，产生64种组合V4.把4个活动部分组 发现局部特征（四肢）的能力.它遵守一些预定义的 成的256张图像设为V.2组图像若定义为图像识 规则，如可分性和完全因子取样，即它是通过一种具 别问题，显然它们应分别对应于不同的聚类 有NMF样式的模型产生的. 对其中一组V4进行NMF分解，设为2，产生的 首先从4个可移动的部分中去掉1个，则剩余 编码矩阵中每一列有2个元素，将其作为2维空间 部分可产生43=64种位置组合，用V4表示。 的坐标得图11.从图中可以看出64张图像根据其 对V4进行NMF分解，取r为17，可产生17个 编码分成了4类，表明NMF具有聚类效果. 基图像，如图9， 从另一组图像V中取出一副图像放入V4,得 到新的一组图像V”.该图像包含4个可活动的部 分，显然，可以将其视为噪声点.对V"进行DNMF分 解，产生的编码矩阵，同样可得其2维空间的坐标如 图12. 200 1509 100 50 图9NMF分解产生的基图像 0 Fig.9 Base images decomposed by NMF 50 100 150 200 编码第一维 图11NMF分解产生的聚类 Fig.11 Clusters decomposed by NMF 200 1509 100 0 50 1001%200 图10DNMF分解产生的基图像 绵码筇一维 Fig.10 Base images decomposed by DNMF 图12DNMF分解产生的聚类 显然基图像中不包含去掉的部分.接着从图8 Fig.12 Clusters decomposed by DNMF 所示的数据集中抽取一个样本加入V4,产生新的
.326 智能系统学报 第5卷 观察图12可知新加入的图像和其他聚类相比 ing[C]//ICEIS International Workshop on Pattern Recogni- 处于分离的位置，可以判断该点为噪声点.另外，从 tion in Information Systems.Funchal,Portugal,2007:107- 实验结果可以看出新增图像对其他图像的编码并未 116. 产生较大影响，表明DNMF在动态数据集上具有抗 [6]CAO Bin,SHEN Dou,SUN Jiantao,et al,Detect and 噪性。 track latent factors with online nonnegative matrix factoriza- tion[C]//The 20th Intemational Joint Conference on Artifi- 5结束语 cial Intelligence.Hyderabad,India,2007:2689-2694. [7]CHEN W S,PAN BB,FANG B,et al.A novel constraint 在NMF算法的基础上提出了一种新的动态学 non-negative matrix factorization criterion based incremental 习算法DNMF.实验表明该算法符合本文提出的准 learning in face recognition[C]//Proceedings of Interna- 则1，合理有效，且较NMF提高了分解准确率.由于 tional Conference on Wavelet Analysis and Pattern Recogni ONMF算法的2个参数未给出明确的定义，代码无 tion.Hong Kong,2008:292-297. 法获得，不能重现文中的实验，因此本文未能对 [8]PETS Video Database[EB/OL].http://ftp.pets.rdg.ac. ONMF和DNMF进行实验对比，但验证了DNMF在 uk/. temporal image数据集上的有效性.在动态数据集的 [9]DONOHO D,Stodden V.When does non-negative matrix 处理中，DNMF对基矩阵和编码矩阵均进行了即时 factorization give a correct decomposition into parts?[C] Proceedings of the Seventeenth Annual Conference on Neu- 更新.此外，DNMF在识别噪声、抗噪方面具有一定 ral Information Processing Systems,Vancouver and Whis- 的用途 tler.British Columbia,Canada,2003:101-108. 参考文献： [10]LI T,DING C.The relationships among various nonnega- tive matrix factorization methods for clustering[C]//Sixth [1]LEE DD,SEUNG H S.Leamning the parts of objects by IEEE International Conference on Data Mining.Hong nonnegative matrix factorization[J].Nature,1999 (401): Kong,2006:362-371. 788-791. 作者简介： [2]XU Wei,LUU Xin,GONG Yihong.Document clustering 杨志君，男，1985年生，硕士研究 based on non-negative matrix factorization[C]//proceedings 生，主要研究方向为数据挖掘。 of the 26th annual international ACM SIGIR conference, Toronto,Canada,2003:267-273. [3]GUILLAMET D,VITRIA J.Nonnegative matrix factoriza- tion for face recognition[C]//Proc Conf Topics in Artificial Intelligence.Alberta,Canada,2002:336-344. [4]VIRTANEN T.Monaural Sound source separation by non- 叶东毅，男，1964年生，教授，博士生 negative matrix factorization with temporal continuity and 导师，主要研究方向为计算智能、数据挖 sparseness criteria [J].IEEE Transactions on Audio, 掘.曾获得1988年度国家科技进步二等 Speech,and Language Processing,2007,15(3):1066- 奖（主要成员）、1项福建省科学技术二 1074. 等奖和2项福建省科学技术三等奖.出 [5]BUCAK SS,GUNSEL B,GURSOY O.Incremental non- 版著作和教材6部，发表论文70余篇。 negative matrix factorization for dynamic background model-