第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. 物体，则在少量的几个新增样本出现后，应对基矩阵