·1218· 智能系统学报 第14卷 判别能力，Wang等提出了Fisher-NMF(FNMF), non-negative matrix factorization.,GNMF)9考虑了 而Zafeiriou等和Kotsia等在NMF的目标函 数据样本之间的流形结构，希望数据样本在低维 数中增加了散度差项，建立起判别子空间法。由 空间中尽可能多地保持其近邻结构，从而寻找数 于LDA)中Fisher准则的比值形式很难处理，集 据在低维空间中的紧致嵌入。该问题可用以下优 成在NMF模型中会出现“小样本问题”。为此，可 化模型表示： 考虑最大间距准则(max margin criterion,.MMCy, min X-WH呢+r(HLH W.H (3) 该准则是以类中心及类散度为度量依据，使得降 st.W≥0，H≥0 维后不同类样本之间距离越远而同类样本之间距 其中L=D-S为拉普拉斯矩阵，S是权矩阵，D为 离越近，在充分使用原始数据类别信息的基础上使 得改进后的NMF(如NDMF网具有良好的判别性质。 对角矩阵，D=∑S,。 另外，为了揭示和利用数据的内在几何结构， 求解该问题的乘性迭代规则为 出现了许多基于流形特征的NMF,例如GNMFI0 GDNMF、LCGNMF2I和NLMFU3]等，这些方法 (XHA,H←HwwH+AHDa Wk←WwH在 (WTX+AHSB)& 通过添加图拉普拉斯正则化项达到了提高图像聚 (i=1,2,…,m:k=1,2,…,r:j=1,2,…,n） (4) 类或分类性能的目的。Shang等w同时考虑数据 1.3最大间距准则(MMC) 流形和特征流形，提出了图对偶正则化NMF(DN- MF)。而Meng等则在图对偶模型中加入了稀 设有C类样本，最大间距准则的主要思想是 寻找一个投影矩阵P使得投影后同类样本之间 疏性(DSNMF)和正交性的约束，有效地简化了 的散度最小而不同类样本之间的散度最大，达到 高维计算，揭示数据和特征之间的双流形结构。 保持原始数据判别信息的目的，它可表示为以下 由于NDMFI91具有良好的判别性质，而 优化问题： NLMF]又利用了数据的图结构来提升其分类性 maxtr(P(S.-S.)P) (5) 能，故本文将两种方法结合起来提出一种基于图 正则化的稀疏判别非负矩阵分解算法(GSDNMF- 式中：S。=∑（任--，》”为类间散度矩阵：S.= L2),在充分利用数据的类别信息的同时，不仅保 持了数据样本之间的局部流形结构，而且能提取 立g--可为类内散度矩阵：工表示所 =1=1 稀疏的特征，进而提升了其分类性能。若干图像 有样本的均值，而x。为c类样本的均值，n。为c 数据集上的实验结果表明，该方法在特征提取与 类样本数。 分类性能等方面优于其他各对比算法。 2本文算法 1相关工作 根据流形学习的图嵌入思想网，数据在高维 1.1非负矩阵分解NMF) 空间中的局部邻域关系在低维样本空间中应得到保 假设由n个非负样本数据x,∈Rm(i=1,2,…,m) 持，同时也希望原始数据集的散度关系得到保持， 组成的非负数据矩阵X=[x1x2…x]∈Rm,非 因此在NMF的目标函数中通过添加图正则化约 负矩阵分解]的目标是将非负数据矩阵X分解 束和判别约束可达到提高算法分类性能的目的。 为基矩阵W=[w1w2…w,]∈R,m和系数矩阵H= 2.1构建权重矩阵 [hh2…hJeR,m的乘积，即X≈WH,当r≤min 基于图嵌入的流形学习法其前提是构建相应 (m,n)时，矩阵X就达到了有效压缩。NMF可表 的邻接图及权矩阵。传统的流形学习方法通常是 示为以下最小化问题： 利用k-近邻法或ε-邻域法来构建图和权矩阵，但 密K-WH呢 此类方法的性能依赖于参数k或ε。本文利用基 (1) s.tW≥0，H≥0 于同类样本的稀疏表示方法选择邻域样本，该方 其中llr表示Frobenius范数。该问题的求解采用 法是自适应且与参数无关的，对噪声数据具有鲁 以下乘性迭代规则： 棒性。 Ws←WaCa (WX) 图1比较了两种方法选择的邻域样本。其 (WHH) ，H←Hw(WTWH (2) 中，k-近邻法选择的邻域样本包含了数据集中不 (i=1,2,…,m:k=1,2,…,r:j=1,2,…,n) 同类别的人脸，人脸角度变化与标注图像一致。 1.2图正则化非负矩阵分解(GNMF) 相比而言，本文方法所选的样本不仅和标注人脸 图正则化非负矩阵分解(graph regularized 具有相似角度，而且最接近其正面的人脸图像，且判别能力，Wang 等 [4] 提出了 Fisher-NMF(FNMF)， 而 Zafeiriou 等 [5] 和 Kotsia 等 [6] 在 NMF 的目标函 数中增加了散度差项，建立起判别子空间法。由 于 LDA[2] 中 Fisher 准则的比值形式很难处理，集 成在 NMF 模型中会出现“小样本问题”。为此，可 考虑最大间距准则 (max margin criterion，MMC)[7-8] ， 该准则是以类中心及类散度为度量依据，使得降 维后不同类样本之间距离越远而同类样本之间距 离越近，在充分使用原始数据类别信息的基础上使 得改进后的 NMF(如 NDMF[9] ) 具有良好的判别性质。 另外，为了揭示和利用数据的内在几何结构， 出现了许多基于流形特征的 NMF，例如 GNMF[10] 、 GDNMF[11] 、LCGNMF[12] 和 NLMF[13] 等，这些方法 通过添加图拉普拉斯正则化项达到了提高图像聚 类或分类性能的目的。Shang 等 [14] 同时考虑数据 流形和特征流形，提出了图对偶正则化 NMF(DN￾MF)。而 Meng 等 [15] 则在图对偶模型中加入了稀 疏性 (DSNMF) 和正交性的约束[16] ，有效地简化了 高维计算，揭示数据和特征之间的双流形结构。 由 于 NDMF [ 9 ] 具有良好的判别性质， 而 NLMF[13] 又利用了数据的图结构来提升其分类性 能，故本文将两种方法结合起来提出一种基于图 正则化的稀疏判别非负矩阵分解算法 (GSDNMF￾L2,1)，在充分利用数据的类别信息的同时，不仅保 持了数据样本之间的局部流形结构，而且能提取 稀疏的特征，进而提升了其分类性能。若干图像 数据集上的实验结果表明，该方法在特征提取与 分类性能等方面优于其他各对比算法。 1 相关工作 1.1 非负矩阵分解 (NMF) n xi ∈ R m (i = 1,2,··· ,n) X = [x1 x2 ··· xn] ∈ R+ m×n X W = [w1 w2 ··· wr] ∈ R+ m×r H = [h1 h2 ··· hn] ∈ R+ r×n X ≈ WH r ⩽ min X 假设由 个非负样本数据 组成的非负数据矩阵 ，非 负矩阵分解[3] 的目标是将非负数据矩阵 分解 为基矩阵 和系数矩阵 的乘积，即 ，当 (m,n) 时，矩阵 就达到了有效压缩。NMF 可表 示为以下最小化问题： min W,H ∥X−WH∥ 2 F s.t. W ⩾ 0, H ⩾ 0 (1) 其中 ∥·∥F 表示 Frobenius 范数。该问题的求解采用 以下乘性迭代规则： Wik ← Wik ( XHT ) ik (WHHT )ik , Hk j ← Hk j ( WTX ) k j (WTWH)k j (i = 1,2,··· ,m；k = 1,2,··· ,r；j = 1,2,··· ,n) (2) 1.2 图正则化非负矩阵分解 (GNMF) 图正则化非负矩阵分解 (graph regularized non-negative matrix factorization，GNMF)[9] 考虑了 数据样本之间的流形结构，希望数据样本在低维 空间中尽可能多地保持其近邻结构，从而寻找数 据在低维空间中的紧致嵌入。该问题可用以下优 化模型表示： min W,H ∥X−WH∥ 2 F +λtr( HLHT ) s.t. W ⩾ 0, H ⩾ 0 (3) L = D−S S D Dii = ∑ j Si j 其中 为拉普拉斯矩阵， 是权矩阵， 为 对角矩阵， 。 求解该问题的乘性迭代规则为 Wik ← Wik ( XHT ) ik (WHHT )ik , Hk j ← Hk j ( WTX+λHSH ) k j (WTWH +λHDH)k j (i = 1,2,··· ,m；k = 1,2,··· ,r；j = 1,2,··· ,n) (4) 1.3 最大间距准则 (MMC) C P 设有 类样本，最大间距准则的主要思想是 寻找一个投影矩阵 使得投影后同类样本之间 的散度最小而不同类样本之间的散度最大，达到 保持原始数据判别信息的目的，它可表示为以下 优化问题： maxtr( P T (Sb −Sw)P ) (5) Sb = ∑C c=1 (x¯ − x¯ c)(x¯ − x¯ c))T Sw = ∑C c=1 ∑nc j=1 (x c j − xc)(x c j − xc) T x xc c nc c 式中： 为类间散度矩阵； 为类内散度矩阵； 表示所 有样本的均值，而 为 类样本的均值， 为 类样本数。 2 本文算法 根据流形学习的图嵌入思想[17-19] ，数据在高维 空间中的局部邻域关系在低维样本空间中应得到保 持，同时也希望原始数据集的散度关系得到保持， 因此在 NMF 的目标函数中通过添加图正则化约 束和判别约束可达到提高算法分类性能的目的。 2.1 构建权重矩阵 基于图嵌入的流形学习法其前提是构建相应 的邻接图及权矩阵。传统的流形学习方法通常是 利用 k-近邻法或 ε-邻域法来构建图和权矩阵，但 此类方法的性能依赖于参数 k 或 ε。本文利用基 于同类样本的稀疏表示方法选择邻域样本，该方 法是自适应且与参数无关的，对噪声数据具有鲁 棒性。 图 1 比较了两种方法选择的邻域样本。其 中，k-近邻法选择的邻域样本包含了数据集中不 同类别的人脸，人脸角度变化与标注图像一致。 相比而言，本文方法所选的样本不仅和标注人脸 具有相似角度，而且最接近其正面的人脸图像，且 ·1218· 智 能 系 统 学 报 第 14 卷