【人工智能基础】图正则化稀疏判别非负矩阵分解

第14卷第6期 智能系统学报 Vol.14 No.6 2019年11月 CAAI Transactions on Intelligent Systems Nov.2019 D0:10.11992/tis.201811021 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20190902.1105.004html 图正则化稀疏判别非负矩阵分解 徐慧敏，陈秀宏 (江南大学数字媒体学院.江苏无锡214000) 摘要：非负矩阵分解是一种流行的数据表示方法，利用图正则化约束能有效地揭示数据之间的局部流形结 构。为了更好地提取图像特征，给出了一种基于图正则化的稀疏判别非负矩阵分解算法(graph regularization sparse discriminant non--negative matrix factorization,GSDNMF-L2,i)。利用同类样本之间的稀疏线性表示来构建对 应的图及权矩阵：以L2,!范数进行稀疏性约束；以最大间距准则为优化目标函数，利用数据集的标签信息来保 持数据样本之间的流形结构和特征的判别性，并给出了算法的迭代更新规则。在若干图像数据集上的实验表 明，GSDNMF-L2!在特征提取方面的分类精度优于各对比算法。 关键词：非负矩阵分解；特征提取；降维：流形学习：最大间距准则；判别信息：稀疏约束：线性表示 中图分类号：TP391.4文献标志码：A文章编号：1673-4785(2019)06-1217-08 中文引用格式：徐慧敏，陈秀宏.图正则化稀疏判别非负矩阵分解J机.智能系统学报，2019,14(6)：1217-1224 英文引用格式：XUHuimin,CHEN Xiuhong.Graph-regularized,.sparse discriminant,,non-negative matrix factorizationJ.CAAI transactions on intelligent systems,2019,14(6):1217-1224. Graph-regularized,sparse discriminant,non-negative matrix factorization XU Huimin,CHEN Xiuhong (School of Digital Media,Jiangnan University,Wuxi 214000,China) Abstract:Non-negative matrix factorization is a popular data representation method.Using graph regularization con- straints can effectively reveal the local manifold structure between data.In order to better extract image features,a graph-regularized,sparse-discriminant,non-negative matrix factorization algorithm is proposed in this paper.The sparse linear representation between similar samples was used to construct the corresponding graph and weight matrix.The ob- jective function using the maximum margin criterion with L2.-norm constraint was optimized,using the tag informa- tion of the dataset to maintain the manifold structure of samples and discrimination of characteristics,and the iterative update rules of the algorithm are given.Experiments were carried out on the ORL,AR,and COIL20 datasets.Com- pared with other algorithms,GSDNMF-L2 showed higher classification accuracy in feature extraction. Keywords:non-negative matrix factorization;feature extraction;dimensionality reduction;manifold learning:maxim- um margin criterion;discriminant information:sparse constraints;linear representation 有效的数据低维表示不仅能够发现数据集中 包含负值元素，这在实际的应用中缺少合理的解 的潜在信息，还能去除原始数据中的冗余特征， 释；而NMF是一种非负约束下的矩阵分解方法， 快速处理高维数据，其中最具代表性的方法包括 仅允许原始数据的加法而非减法组合，因此它有 主成分分析四、线性判别分析四及非负矩阵分解。 利于稀疏的且基于部分的表示，比非稀疏的全局 然而PCA和LDA得到的数据低维表示中可能会 表示更稳健。 收稿日期：2018-11-26.网络出版日期：2019-09-02 基金项目：2018年江苏省研究生科研创新计划项目KYCX181871) 经典的NMF是一种无监督学习算法，不能充 通信作者：徐慧敏.E-mail:1215625771@qq.com 分利用原始数据的类别信息。为了提高NMF的

DOI: 10.11992/tis.201811021 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20190902.1105.004.html 图正则化稀疏判别非负矩阵分解 徐慧敏，陈秀宏 （江南大学 数字媒体学院，江苏 无锡 214000） 摘 要：非负矩阵分解是一种流行的数据表示方法，利用图正则化约束能有效地揭示数据之间的局部流形结 构。为了更好地提取图像特征，给出了一种基于图正则化的稀疏判别非负矩阵分解算法 (graph regularization sparse discriminant non-negative matrix factorization，GSDNMF-L2,1)。利用同类样本之间的稀疏线性表示来构建对 应的图及权矩阵；以 L2,1 范数进行稀疏性约束；以最大间距准则为优化目标函数，利用数据集的标签信息来保 持数据样本之间的流形结构和特征的判别性，并给出了算法的迭代更新规则。在若干图像数据集上的实验表 明，GSDNMF-L2,1 在特征提取方面的分类精度优于各对比算法。 关键词：非负矩阵分解；特征提取；降维；流形学习；最大间距准则；判别信息；稀疏约束；线性表示 中图分类号：TP391.4 文献标志码：A 文章编号：1673−4785(2019)06−1217−08 中文引用格式：徐慧敏, 陈秀宏. 图正则化稀疏判别非负矩阵分解 [J]. 智能系统学报, 2019, 14(6): 1217–1224. 英文引用格式：XU Huimin, CHEN Xiuhong. Graph-regularized, sparse discriminant, non-negative matrix factorization[J]. CAAI transactions on intelligent systems, 2019, 14(6): 1217–1224. Graph-regularized, sparse discriminant, non-negative matrix factorization XU Huimin，CHEN Xiuhong (School of Digital Media,Jiangnan University,Wuxi 214000,China) Abstract: Non-negative matrix factorization is a popular data representation method. Using graph regularization con￾straints can effectively reveal the local manifold structure between data. In order to better extract image features, a graph-regularized, sparse-discriminant, non-negative matrix factorization algorithm is proposed in this paper. The sparse linear representation between similar samples was used to construct the corresponding graph and weight matrix. The ob￾jective function using the maximum margin criterion with L2,1 -norm constraint was optimized, using the tag informa￾tion of the dataset to maintain the manifold structure of samples and discrimination of characteristics, and the iterative update rules of the algorithm are given. Experiments were carried out on the ORL, AR, and COIL20 datasets. Com￾pared with other algorithms, GSDNMF-L2,1 showed higher classification accuracy in feature extraction. Keywords: non-negative matrix factorization; feature extraction; dimensionality reduction; manifold learning; maxim￾um margin criterion; discriminant information; sparse constraints; linear representation 有效的数据低维表示不仅能够发现数据集中 的潜在信息，还能去除原始数据中的冗余特征， 快速处理高维数据，其中最具代表性的方法包括 主成分分析[1] 、线性判别分析[2] 及非负矩阵分解[3]。 然而 PCA 和 LDA 得到的数据低维表示中可能会 包含负值元素，这在实际的应用中缺少合理的解 释；而 NMF 是一种非负约束下的矩阵分解方法， 仅允许原始数据的加法而非减法组合，因此它有 利于稀疏的且基于部分的表示，比非稀疏的全局 表示更稳健。 经典的 NMF 是一种无监督学习算法，不能充 分利用原始数据的类别信息。为了提高 NMF 的 收稿日期：2018−11−26. 网络出版日期：2019−09−02. 基金项目：2018 年江苏省研究生科研创新计划项目 (KYCX18_1871). 通信作者：徐慧敏. E-mail：1215625771@qq.com.. 第 14 卷第 6 期 智 能 系 统 学 报 Vol.14 No.6 2019 年 11 月 CAAI Transactions on Intelligent Systems Nov. 2019

·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 卷

第6期 徐慧敏，等：图正则化稀疏判别非负矩阵分解 ·1219· 相应的稀疏表示系数越大，越接近标注样本。所 阵；DH为对角矩阵且对角元素为Dm=∑So 以，基于同类样本的稀疏表示方法构建的权重矩 以NMF中的基矩阵W为投影矩阵，使得投 阵不仅包含了样本的类别信息，而且还包含了样 本间的局部邻域结构，从而具有良好的判别性质。 影后同类样本之间的散度最小而不同类样本之间 的散度最大9，以保留训练样本的判别特征，从而 回國 有以下基于MMC准则的判别约束项： (a)ORL数据集的第一类人脸图像 tr(WT(S&-Sw)W) (9) 下网 为满足NMF的非负约束的要求，式(9)可改 写为 (b)k近邻法确定的邻域样本 tr(W((Si-S)-(Sw-Sim))W) (10) 0.5 ■ ■ 式中：Ss表示由所有训练样本的类间散度矩阵； 345678910 (©)由同类样本稀疏表示的表示系数 S和S分别表示SB的正元素和非正元素的绝 对值构成的矩阵；Sw表示类内散度矩阵；S和S 分别表示Sw的正元素和非正元素的绝对值构成 的矩阵。 图 对于图像数据，其特征维度和冗余程度都很 (d)利用稀疏表示确定的近邻样本（前5幅） 高，基于稀疏编码的思想2，将样本x表示为基 和同类的其他样本（后5幅） 图像的稀疏线性表示，可以减少高维样本的计算 图1k近邻法与稀疏表示法确定的近邻 量，得到更具鲁棒性的特征： Fig.1 Neighbor samples determined by k-nearest neigh- xi≈w1h1d+w2h2u+…+w,hd (11) bor method and sparse representation 通常使用L范数对系数矩阵进行稀疏性约 对于某一类数据样本x,将它表示为所有同 束，但Lo范数的求解属于NP难问题，常用L范 类的其他样本的稀疏线性组合，这可以用以下优 数作为其凸近似进行近似求解： 化模型来表示： min s I=∑∑h (12) (6) s.t.xi=Xsi,c(xi)=c 式中：X。为第c类所有样本组成的矩阵，表示系 系数矩阵H的每一列可看作原始数据X在 数向量s中的每一个分量描述了与x同类的其 子空间中的低维表示，L范数使得系数矩阵H整 他相应样本在表示x时的贡献大小，从而可以用 体保持稀疏，本文使用L21范数对系数矩阵H进 来表示样本之间的相似性。c(x)表示样本x的 行列稀疏约束，使得每一个低维表示保持稀 类标签，表示第c类样本的数量，且n=∑n。 疏，能够在特征空间中用尽可能少的特征重构原 =1 始数据： 从而，有以下基于稀疏表示的样本权矩阵： Sa=(S）n=diag{S,S2,…,Sc (7) (13) 其中：子矩阵SC∈Rm是由第c类中每个训练样 本x的稀疏表示系数s所组成的分块矩阵。 其中五为矩阵H的第j列向量。 2.3 2.2正则化约束 优化模型与求解 图正则化是基于邻域保持嵌入的，它将训练 由以上分析，利用图正则化约束来保持样本之 样本之间的局部邻域关系通过权矩阵S在由NMF 间的邻域结构：以最大间距准则保持数据集的判别 的系数矩阵H的列向量h,所张成的子空间中得 性：以L2,范数进行稀疏性约束四，建立优化模型： 到保持，因此得到以下图正则化约束项： min X-WHi+atr(HLnH)+ S-u(D)-u(aS)- r(wr(S-S)-(Ss-Ss》W）+μH: s.t.W≥0，H≥0 (14) tr(HLaH) (8) 令Φ与平为拉格朗日乘子，构造拉格朗日 式中：Sa为权矩阵；La=Da-Sa为拉普拉斯矩 函数：

相应的稀疏表示系数越大，越接近标注样本。所 以，基于同类样本的稀疏表示方法构建的权重矩 阵不仅包含了样本的类别信息，而且还包含了样 本间的局部邻域结构，从而具有良好的判别性质。 (a) ORL数据集的第一类人脸图像 (b) k-近邻法确定的邻域样本 (c) 由同类样本稀疏表示的表示系数 (d) 利用稀疏表示确定的近邻样本(前5幅) 和同类的其他样本(后5幅) 1 0 0.5 3 4 5 6 7 8 9 10 图 1 k-近邻法与稀疏表示法确定的近邻 Fig. 1 Neighbor samples determined by k-nearest neigh￾bor method and sparse representation x c 对于某一类数据样本 i ，将它表示为所有同 类的其他样本的稀疏线性组合，这可以用以下优 化模型来表示： min s c i 1 s.t. xi = Xc s c i , c (xi) = c (6) Xc s c i x c i x c i c(xi) x c i nc ∑C c=1 nc 式中： 为第 c 类所有样本组成的矩阵，表示系 数向量 中的每一个分量描述了与 同类的其 他相应样本在表示 时的贡献大小，从而可以用 来表示样本之间的相似性。 表示样本 的 类标签， 表示第 c 类样本的数量，且 n = 。 从而，有以下基于稀疏表示的样本权矩阵： SH = ( Si j ) n×n = diag{ S 1 ,S 2 ,··· ,S C } (7) S C ∈ R nc×nc x c i s c i 其中：子矩阵 是由第 c 类中每个训练样 本 的稀疏表示系数 所组成的分块矩阵。 2.2 正则化约束 图正则化是基于邻域保持嵌入的，它将训练 样本之间的局部邻域关系通过权矩阵 S 在由 NMF 的系数矩阵 H 的列向量 hj 所张成的子空间中得 到保持，因此得到以下图正则化约束项： 1 2 ∑n i, j=1 hi − hj 2 2 Si j =tr( HDH H T ) −tr( HSH H T ) = tr( HLH H T ) (8) 式中： SH 为权矩阵； LH = DH −SH 为拉普拉斯矩 DHii = ∑ j 阵；DH 为对角矩阵且对角元素为 SHi j。 以 NMF 中的基矩阵 W 为投影矩阵，使得投 影后同类样本之间的散度最小而不同类样本之间 的散度最大[19]，以保留训练样本的判别特征，从而 有以下基于 MMC 准则的判别约束项： tr( WT (SB −SW)W ) (9) 为满足 NMF 的非负约束的要求，式 (9) 可改 写为 tr( WT ((S + B −S − |B| ) − ( S + W −S − |W| ))W ) (10) SB S + B S − |B| SB SW S + W S − |W| SW 式中： 表示由所有训练样本的类间散度矩阵； 和 分别表示 的正元素和非正元素的绝 对值构成的矩阵； 表示类内散度矩阵； 和 分别表示 的正元素和非正元素的绝对值构成 的矩阵。 xi 对于图像数据，其特征维度和冗余程度都很 高，基于稀疏编码的思想[20] ，将样本 表示为基 图像的稀疏线性表示，可以减少高维样本的计算 量，得到更具鲁棒性的特征： xi ≈ w1h1,i +w2h2,i +···+wrhr,i (11) L0 L0 L1 通常使用 范数对系数矩阵进行稀疏性约 束，但 范数的求解属于 NP 难问题，常用 范 数作为其凸近似进行近似求解： ∥H∥1 = ∑r i=1 ∑n j=1   hi j    (12) H X L1 H L2,1 H hj 系数矩阵 的每一列可看作原始数据 在 子空间中的低维表示， 范数使得系数矩阵 整 体保持稀疏，本文使用 范数对系数矩阵 进 行列稀疏约束，使得每一个低维表示 保持稀 疏，能够在特征空间中用尽可能少的特征重构原 始数据： H T 2,1 = ∑n j=1 hj 2 = ∑n j=1 vt∑r i=1 h 2 i j (13) 其中 hj 为矩阵 H 的第 j 列向量。 2.3 优化模型与求解 L2,1 由以上分析，利用图正则化约束来保持样本之 间的邻域结构；以最大间距准则保持数据集的判别 性；以 范数进行稀疏性约束[21] ，建立优化模型： min ∥X−WH∥ 2 F +λtr( HLH H T ) + βtr( WT ((S + W −S − |W| ) − ( S + B −S − |B| ))W ) +µ H T 2,1 s.t. W ⩾ 0, H ⩾ 0 (14) 令 Φik 与 Ψk j 为拉格朗日乘子，构造拉格朗日 函数： 第 6 期 徐慧敏，等：图正则化稀疏判别非负矩阵分解 ·1219·

·1220· 智能系统学报 第14卷 L=IIX-WHIl+itr(HLnH)+ 数。算法GSDNMF-L21主要由1)、2)和4)组成， Btr(WT((Sw-Sm)-(Si-Si))W)+ (15) 其中步骤1)是构建数据图的权矩阵，其复杂度为 O(n2m);步骤2)则是计算类内散度Sw和类间散 tr(H'QH）-r(ΦWT）-tr(H) 度SB,其复杂度为O(m2);对步骤4)，一次迭代计 式中：Q为对角矩阵，且：= 四明为系数矩 算W和H的复杂度O(mnk),假设算法在T。次迭 阵H的转置的第i列。 代后收敛，则整个步骤4)的复杂度为O(Tomnk)。 使用交替迭代方法求解。先固定H,更新 综上可知，GSDNMF-L21算法的总体时间复杂度为O W:然后固定W,更新H。式(15)对W求偏导并 (Tomnk+n'm+m2) 令导数等于0，得： 3实验分析 0W=-2XH+2wH日+ aL (16) 为了说明GSDNMF-L2:算法在图像特征提取 2(S#-S)-(落-S)w-Φ=0 中的有效性，分别在ORL和AR人脸数据集和 由互补松驰条件中W=0,得： COIL20实物数据集上进行实验，并将之与NMF (-XH+WHH+B((Sw-Sm)-(Sk-S m)W)Wik=0 GNMF1O、NDMF等算法进行比较，同时比较利 (17) 用L,范数进行稀疏约束的模型(GSDNMF-L)。 于是，有以下关于W的更新规则： 将数据集按0.5的比例随机划分为训练集和测试 W←W (xH+B(Sim+S)) 集，利用训练集进行特征提取，获得基矩阵W。 (WHH+B(Sw+Sm)) (18) 利用测试集计算分类精度：测试样本x∈Rm在低 同理，得到关于H的更新规则： 维子空间中的表示为y≈W+x∈R,其中W+= H对 (WW)~WT为矩阵W的Pseudo逆，使用传统的k (WX+HSn+BVntr(W(Sm+S)W)) 近邻分类器(k-NN)预测类标签。每次实验独立 WWH+HD+BV(w(S+m)w)+H 随机，重复20次取平均识别率和方差作为最后实 验结果。 (19) 在每次迭代得到基图像矩阵W后，对其每一 31数据集 列进行归一化处理，使非负矩阵分解得到的结果 ORL人脸数据库包含了40个人的人脸图像， 保持缩放不变性。设置最大迭代次数T,使算法 每个人有10张，图像具有不同面部表情（睁/闭 在最大迭代次数下收敛。 眼，笑/不笑)、面部细节（眼镜/无眼镜）及不同光 综合以上讨论，得到图正则化稀疏判别非负 照条件。 矩阵分解法： AR数据集包含了120个人的人脸图像，每个 算法1图正则化稀疏判别非负矩阵分解算 人有26张图像，图像具有不同的面部表情、照明 法(GSDNMF-L2) 条件和遮挡（太阳眼镜/围巾）。 输入训练样本X∈R,样本类别Y,特征 COIL20数据集包含了20个不同的物体（玩 数r,正则化参数1、B、山，最大迭代次数To。 具小鸭、招财猫、杯子等)，其中，每个物体在水平 1)利用式(6)和式（⑦）计算权重矩阵S: 面上每隔5拍摄一张图片，因此每个物体一共有 2)利用式(9)计算类内散度Sw和类间散度 72幅图片，整个数据集共计1440幅图片。 SB: 实验中，所有图像均压缩成32×32大小的灰 3)随机初始化W。∈Rm,H。∈R; 度图，将其每列相连构成大小为1024维的向量， 4) For 1:To 并做归一化处理。如图2所示。 利用式(18)得到更新后的W,并对W的每 一列进行归一化处理，利用公式(19)得到更新后 的H; (a)ORL数据集 End 输出基矩阵W和系数矩阵H。 2.4算法复杂度 设m为样本维度，n为样本个数，k为特征 (b)AR数据集

L = ∥X−WH∥ 2 F +λtr( HLH H T ) + βtr( WT ((S + W −S − |W| ) − ( S + B −S − |B| ))W ) + µtr( H TQH) −tr( ΦWT ) −tr(ΨH) (15) Q Qii = 1 2 HT i 2 HT i H i 式中： 为对角矩阵，且 ， 为系数矩 阵 的转置的第 列。 H W W H W 使用交替迭代方法求解。先固定 ，更新 ；然后固定 ，更新 。式 (15) 对 求偏导并 令导数等于 0，得： ∂L ∂W = −2XH T +2WHHT+ 2β ((S + W −S − |W| ) − ( S + B −S + |B| ))W −Φ = 0 (16) 由互补松驰条件 ΦikWik = 0 ，得： ( −XH T +WHHT +β ((S + W −S − |W| ) − ( S + B −S − |B| ))W ) ik Wik = 0 (17) 于是，有以下关于 W 的更新规则： Wt+1 ik ← Wt ik ( XHT +β ( S − |W| +S + B )) ik ( WHHT +β ( S + W +S − |B| )) ik (18) 同理，得到关于 H 的更新规则： H t+1 k j ← H t k j ( WTX+λHSH +β∇Htr( W ( S − |W| +S + B ) WT )) k j ( WTWH +λH DH +β∇Htr( W ( S + W +S − |B| ) WT ) +µHQ) k j (19) W T0 在每次迭代得到基图像矩阵 后，对其每一 列进行归一化处理，使非负矩阵分解得到的结果 保持缩放不变性。设置最大迭代次数 ，使算法 在最大迭代次数下收敛。 综合以上讨论，得到图正则化稀疏判别非负 矩阵分解法： 算法 1 图正则化稀疏判别非负矩阵分解算 法 (GSDNMF-L2,1) X ∈ R m×n + Y r T0 输入 训练样本 ，样本类别 ，特征 数 ，正则化参数 λ、β、μ，最大迭代次数 。 1) 利用式 (6) 和式 (7) 计算权重矩阵 SH； SW SB 2) 利用式 (9) 计算类内散度 和类间散度 ； W0 ∈ R m×k + H0 ∈ R k×n 3 + ) 随机初始化 ， ； 4) For t= 1: T0 W W H 利用式 (18) 得到更新后的 ，并对 的每 一列进行归一化处理，利用公式 (19) 得到更新后 的 ； End 输出 基矩阵 W 和系数矩阵 H。 2.4 算法复杂度 设 m 为样本维度，n 为样本个数， k 为特征 O ( n 2m ) SW SB O ( m 2 ) W H O(mnk) T0 O(T0mnk) ( T0mnk+n 2m+m 2 ) 数。算法 GSDNMF-L2,1 主要由 1)、2) 和 4) 组成， 其中步骤 1) 是构建数据图的权矩阵，其复杂度为 ；步骤 2) 则是计算类内散度 和类间散 度 ，其复杂度为 ；对步骤 4)，一次迭代计 算 和 的复杂度 ，假设算法在 次迭 代后收敛，则整个步骤 4) 的复杂度为 。 综上可知，GSDNMF-L2,1 算法的总体时间复杂度为 O 。 3 实验分析 W x ∈ R m y ≈ W+ x ∈ R r W+ = (WTW) −1WT W 为了说明 GSDNMF-L2,1 算法在图像特征提取 中的有效性，分别在 ORL 和 AR 人脸数据集和 COIL20 实物数据集上进行实验，并将之与 NMF[3] 、 GNMF[10] 、NDMF[9] 等算法进行比较，同时比较利 用 L1 范数进行稀疏约束的模型 (GSDNMF-L1 )。 将数据集按 0.5 的比例随机划分为训练集和测试 集，利用训练集进行特征提取，获得基矩阵 。 利用测试集计算分类精度：测试样本 在低 维子空间中的表示为 ，其中 为矩阵 的 Pseudo 逆，使用传统的 k- 近邻分类器 (k-NN) 预测类标签。每次实验独立 随机，重复 20 次取平均识别率和方差作为最后实 验结果。 3.1 数据集 ORL 人脸数据库包含了 40 个人的人脸图像， 每个人有 10 张，图像具有不同面部表情 (睁/闭 眼，笑/不笑)、面部细节 (眼镜/无眼镜) 及不同光 照条件。 AR 数据集包含了 120 个人的人脸图像，每个 人有 26 张图像，图像具有不同的面部表情、照明 条件和遮挡 (太阳眼镜/围巾)。 COIL20 数据集包含了 20 个不同的物体 (玩 具小鸭、招财猫、杯子等)，其中，每个物体在水平 面上每隔 5°拍摄一张图片，因此每个物体一共有 72 幅图片，整个数据集共计 l 440 幅图片。 实验中，所有图像均压缩成 32×32 大小的灰 度图，将其每列相连构成大小为 1 024 维的向量， 并做归一化处理。如图 2 所示。 (a) ORL数据集 (b) AR数据集 ·1220· 智 能 系 统 学 报 第 14 卷

第6期 徐慧敏，等：图正则化稀疏判别非负矩阵分解 ·1221· 3.2参数选择 GSDNMF-.L21算法包含了图正则化约束参数 入、判别约束参数B和稀疏参数μ等3个关键参 数。为说明3个参数对识别率的影响，分别在两 个数据集上采取固定两个参数来确定另一个参数 的方法进行讨论，设参数的取值范围为[0,1]，取 (c)COL20数据集 数据集的类别数作为基图数(ORL取40，AR取120， 图2数据集示例 C0IL20取20)，最大迭代次数为300次，实验所得 Fig.2 The instances of datasets 的平均识别率与正则化参数的关系如图3所示。 1.0 1.0 1.0 0.9 0.9 -ORL 0.5 -ORL 0.8 98L20 C0L20 0.8 -ORL 0.7 -0AR 0.7 C0L20 0.6 LLd 0.6 10× 10-3 10-2 10 10 10 10-3 102 10-1 10o 10-4 10 102 10-1109 P (a)参数对识别率的影响 (b)参数B对识别率的影响 (c)参数u对识别率的影 图3参数对识别率的影响 Fig.3 The influence of parameters 3.3实验结果及分析 化的情况。在大多数情况下，GSDNMF-L21的识 由图3可知，图正则化参数1对识别率的影 别率要优于其他几种算法，且方差更小，说明在 响较大，在[0,0.01]的范围内，识别率随参数的增 NMF的目标函数中结合图正则化约束和判别约 大而增大，在[0.01,1]的范围内，识别率随参数的 束能够有效提高图像特征提取的准确率和稳定 增大而减少。判别约束参数和稀疏参数对识别率 性。图4比较了在ORL数据集上5种算法的训 的影响较小，在[0,1]范围内一直保持较高识别 练时间（取类别数40作为基图数目），可以发现 率。经过多次实验，最终确定算法的最优参数组 NMF和GNMF的训练时间较短，NDMF训练时 合为=0.005，=1,4=0.5。 间最长，GSDNMF-L2,1和GSDNMF-L,比ND 取基图数分别为3、4、5、6、7、8的平方，在 MF时间短。可知，利用稀疏编码的思想对系数 3种数据集上独立随机地进行20次实验，计算平 矩阵H添加稀疏性约束，在每一迭代更新的过程 均识别率及方差。表1~3给出了5种算法在3种 中能够尽可能少地选择基图像重构训练样本，提 数据集上的平均识别率随基图像个数的增加而变 高了运算速度。 表1ORL数据集上的平均识别率（方差） Table 1 Average recognition rate(variance)on ORL dataset 特征维数 NMF GNMF NDMF GSDNMF-LI GSDNMF-L2,1 9 79.30(2.36) 79.48(1.73) 79.702.83) 82.052.34) 82.25(1.51) 16 85.15(1.69) 85.96(1.35) 86.18(1.58) 90.831.58) 90.83(1.38) 25 86.33(1.52) 85.00(2.14) 85.90(1.67) 89.83(1.36) 92.13(1.25) 36 87.18(1.50) 87.30(1.30) 86.85(1.69) 92.50(1.06) 93.131.03) 49 90.141.04) 90.85(1.17 90.63(0.69 95.43(0.69) 95.430.56

(c) COIL20数据集 图 2 数据集示例 Fig. 2 The instances of datasets 3.2 参数选择 β µ GSDNMF-L2,1 算法包含了图正则化约束参数 λ、判别约束参数 和稀疏参数 等 3 个关键参 数。为说明 3 个参数对识别率的影响，分别在两 个数据集上采取固定两个参数来确定另一个参数 的方法进行讨论，设参数的取值范围为 [0,1]，取 数据集的类别数作为基图数 (ORL 取 40，AR 取 120， COIL20 取 20)，最大迭代次数为 300 次，实验所得 的平均识别率与正则化参数的关系如图 3 所示。 1.0 0.5 0 识别率 10−4 10−3 10−2 10−1 100 λ 1.0 0.9 0.8 0.7 0.6 识别率 10−4 10−3 10−2 10−1 100 β 1.0 0.9 0.8 0.7 0.6 识别率 10−4 10−3 10−2 10−1 100 μ ORL AR COIL20 ORL AR COIL20 ORL AR COIL20 (a) 参数λ对识别率的影响 (b) 参数β对识别率的影响 (c) 参数 μ对识别率的影 图 3 参数对识别率的影响 Fig. 3 The influence of parameters 3.3 实验结果及分析 由图 3 可知，图正则化参数 λ 对识别率的影 响较大，在 [0,0.01] 的范围内，识别率随参数的增 大而增大，在 [0.01,1] 的范围内，识别率随参数的 增大而减少。判别约束参数和稀疏参数对识别率 的影响较小，在 [0,1] 范围内一直保持较高识别 率。经过多次实验，最终确定算法的最优参数组 合为 λ=0.005，β=1，μ=0.5。 取基图数分别为 3、4、5、6、7、8 的平方，在 3 种数据集上独立随机地进行 20 次实验，计算平 均识别率及方差。表 1~3 给出了 5 种算法在 3 种 数据集上的平均识别率随基图像个数的增加而变 化的情况。在大多数情况下，GSDNMF-L2,1 的识 别率要优于其他几种算法，且方差更小，说明在 NMF 的目标函数中结合图正则化约束和判别约 束能够有效提高图像特征提取的准确率和稳定 性。图 4 比较了在 ORL 数据集上 5 种算法的训 练时间 (取类别数 40 作为基图数目)，可以发现 NMF 和 GNMF 的训练时间较短，NDMF 训练时 间最长，GSDNMF-L2 , 1 和 GSDNMF-L1 比 ND￾MF 时间短。可知，利用稀疏编码的思想对系数 矩阵 H 添加稀疏性约束，在每一迭代更新的过程 中能够尽可能少地选择基图像重构训练样本，提 高了运算速度。 表 1 ORL 数据集上的平均识别率 (方差) Table 1 Average recognition rate (variance) on ORL dataset 特征维数r NMF GNMF NDMF GSDNMF-L1 GSDNMF-L2,1 9 79.30(2.36) 79.48(1.73) 79.70(2.83) 82.05(2.34) 82.25(1.51) 16 85.15(1.69) 85.96(1.35) 86.18(1.58) 90.83(1.58) 90.83(1.38) 25 86.33(1.52) 85.00(2.14) 85.90(1.67) 89.83(1.36) 92.13(1.25) 36 87.18(1.50) 87.30(1.30) 86.85(1.69) 92.50(1.06) 93.13(1.03) 49 90.14(1.04) 90.85(1.17) 90.63(0.69) 95.43(0.69) 95.43(0.56) 第 6 期 徐慧敏，等：图正则化稀疏判别非负矩阵分解 ·1221·

·1222· 智能系统学报 第14卷 表2AR数据集上的平均识别率（方差） Table 2 Average recognition rate(variance)on AR dataset 特征维数 NMF GNMF NDMF GSDNMF-LI GSDNMF-L21 6 62.68(1.86) 67.80(2.66) 61.12(2.17 76.01(1.80) 76.10(1.83) 25 74.66(1.57) 77.92(1.94) 74.01(1.98) 85.31(1.17) 85.83(1.02) 36 77.570.84) 80.48(1.25) 76.741.10) 85.96(0.81) 86.49(1.02) 49 78.291.49) 80.92(0.96) 77.84(1.15) 88.42(0.75) 88.79(0.81) 64 90.62(1.03) 93.05(0.70) 90.47(0.91) 94.92(0.51) 94.91(0.28) 表3C0ⅡL20数据集上的平均识别率（方差） Table 3 Average recognition rate(variance)on COIL20 dataset 特征维数 NMF GNMF NDMF GSDNMF-LI GSDNMF-L2,1 9 90.45(1.07) 91.97(1.32) 91.03(1.43) 90.56(1.67 92.05(1.35) 16 95.05(0.81) 96.62(0.83) 95.26(0.90) 95.35(1.43) 97.11(0.74) 25 98.19(0.49) 98.76(0.39) 97.93(0.64) 98.97(0.47) 99.23(0.38) 36 98.440.87) 98.650.59) 98.37(0.63) 98.91(0.83) 99.340.35) -·-NMF 1010 20 -eGNMF A—NDMF _GSDNMF-LI GSDNMF-L2 -ORL ....AR 三10 COIL20 10 0 50 100150200250300 =9-9-0-0-90 迭代次数 10 20 30 40 图5损失函数的变化曲线 特征维度 Fig.5 Variation curve of loss function 图4训练时间随基图数变化的曲线 Fig.4 Variation curve of training time 其中向量：是其第i个分量。稀疏度值域是 图5给出了GSDNMF-L2!算法在3种数据集 [0,1],值越大，说明向量越稀疏。表4比较了5种 上的收敛情况，当迭代次数小于10次时损失函数 算法在3种数据集上迭代300次后生成的基图的 值迅速下降：而当迭代次数大于100时，随着迭代 平均稀疏度（基矩阵的每一列表示一个基图）。 次数的增加其损失函数值的下降趋于平缓，并收 图6比较了3种具有判别性质的NMF算法：ND 敛于一个固定值。本文所有实验均设置最大迭代 MF9、GSDNMF-L1和GSDNMF-L2,1得到的基图。 次数为300次，以保证算法收敛。 对比发现，3种算法都能得到的图像的局部化表 为了刻画和评价基图像矩阵的特点，Hoyer2ol 示，且都包含了每类物体的判别信息，但GSDN 提出采用向量的L,范数和L2范数的差异来度量 MF-L21和GSDNMF-L,得到的基图比NDMF得 向量的稀疏度，其计算方式为 到的基图更稀疏。由实验结果可知，本文提出的 算法，能够在保证稀疏性的条件下，保持良好 分类水平，说明算法分解得到了更有效的基图 (x)= Vn-1 (20) 特征

表 2 AR 数据集上的平均识别率 (方差) Table 2 Average recognition rate (variance) on AR dataset 特征维数r NMF GNMF NDMF GSDNMF-L1 GSDNMF-L2,1 16 62.68(1.86) 67.80(2.66) 61.12(2.17) 76.01(1.80) 76.10(1.83) 25 74.66(1.57) 77.92(1.94) 74.01(1.98) 85.31(1.17) 85.83(1.02) 36 77.57(0.84) 80.48(1.25) 76.74(1.10) 85.96(0.81) 86.49(1.02) 49 78.29(1.49) 80.92(0.96) 77.84(1.15) 88.42(0.75) 88.79(0.81) 64 90.62(1.03) 93.05(0.70) 90.47(0.91) 94.92(0.51) 94.91(0.28) 表 3 COIL20 数据集上的平均识别率 (方差) Table 3 Average recognition rate (variance) on COIL20 dataset 特征维数r NMF GNMF NDMF GSDNMF-L1 GSDNMF-L2,1 9 90.45(1.07) 91.97(1.32) 91.03(1.43) 90.56(1.67) 92.05(1.35) 16 95.05(0.81) 96.62(0.83) 95.26(0.90) 95.35(1.43) 97.11(0.74) 25 98.19(0.49) 98.76(0.39) 97.93(0.64) 98.97(0.47) 99.23(0.38) 36 98.44(0.87) 98.65(0.59) 98.37(0.63) 98.91(0.83) 99.34(0.35) 10 0 5 10 15 20 25 20 30 40 特征维度 训练时间/s NMF GNMF NDMF GSDNMF-L1 GSDNMF-L2,1 图 4 训练时间随基图数变化的曲线 Fig. 4 Variation curve of training time 图 5 给出了 GSDNMF-L2,1 算法在 3 种数据集 上的收敛情况，当迭代次数小于 10 次时损失函数 值迅速下降；而当迭代次数大于 100 时，随着迭代 次数的增加其损失函数值的下降趋于平缓，并收 敛于一个固定值。本文所有实验均设置最大迭代 次数为 300 次，以保证算法收敛。 L1 L2 为了刻画和评价基图像矩阵的特点，Hoyer[20] 提出采用向量的 范数和 范数的差异来度量 向量的稀疏度，其计算方式为 s(x) = √ n−   ∑ i xi/ √∑ i x 2 i   √ n−1 (20) 其中向量 xi 是其第 i 个分量。稀疏度值域是 [0,1]，值越大，说明向量越稀疏。表 4 比较了 5 种 算法在 3 种数据集上迭代 300 次后生成的基图的 平均稀疏度 (基矩阵的每一列表示一个基图)。 图 6 比较了 3 种具有判别性质的 NMF 算法：ND￾MF[9] 、GSDNMF-L1 和 GSDNMF-L2,1 得到的基图。 对比发现，3 种算法都能得到的图像的局部化表 示，且都包含了每类物体的判别信息，但 GSDN￾MF-L2,1 和 GSDNMF-L1 得到的基图比 NDMF[9] 得 到的基图更稀疏。由实验结果可知，本文提出的 算法，能够在保证稀疏性的条件下，保持良好 分类水平，说明算法分解得到了更有效的基图 特征。 50 104 106 108 1010 100 150 200 250 300 损失函数值 迭代次数 ORL AR COIL20 0 图 5 损失函数的变化曲线 Fig. 5 Variation curve of loss function ·1222· 智 能 系 统 学 报 第 14 卷

第6期 徐慧敏，等：图正则化稀疏判别非负矩阵分解 ·1223· 表4比较基图像W的稀疏度 ent analysis[J].Chemometrics and intelligent laboratory Table 4 Comparison of sparsity of the base matrix W systems,.1987,2(1/2/3):37-52 数据集NMF GNMF NDMF GSDNMF-L,GSDNMF-L2 [2]BELHUMEUR PN.HESPANHA JP.KRIEGMAN D J 0RL0.250.320.26 0.30 0.33 Eigenfaces vs.Fisherfaces:recognition using class specif- AR0.520.550.52 0.55 0.56 ic linear projection[C]//Proceedings of the 4th European C0L0.490.560.49 0.54 0.65 Conference on Computer Vision.Cambridge,UK,1996: 45-58 [3]LEE DD,SEUNG H S.Learning the parts of objects by non-negative matrix factorization[J].Nature,1999. 401(6755):788-791. [4]WANG Yuan,JIA Yunde.HU Changbo,et al.Fisher non- (a)3种算法在ORL数据集上的基图 negative matrix factorization for learning local features[Cl//Proceedings of the 6th Asian Conference on Computer Vision.Jeju,Korea,2004. [5]ZAFEIRIOU S,TEFAS A,BUCIU I,et al.Exploiting dis- criminant information in nonnegative matrix factorization (b)3种算法在AR数据集上的基图 with application to frontal face verification[J].IEEE trans. actions on neural networks.2006.17(3):683-695 [6]KOTSIA I,ZAFEIRIOU S,PITAS I.A novel discrimin- ant non-negative matrix factorization algorithm with ap- plications to facial image characterization problems[J]. (c)3种算法在COIL数据集上的基图 IEEE transactions on information forensics and security 2007,2(3:588-595 图6比较NDMF,GSDNMF-L,和GSDNMF-L21算法 在ORL、AR和COL20数据集上得到的基图 [7]GU Quanquan,ZHOU Jie.Two dimensional maximum Fig.6 Comparison of basic images computed by NDMF, margin criterion[C]//IEEE International Conference on GSDNMF-L and GSDNMF-L2.1 algorithm on Acoustics,Speech and Signal Processing.Taipei,Taiwan, ORL,AR and COIL20 dataset 2009:1621-1624 4结束语 [8]LI Haifeng.JIANG Tao,ZHANG Keshu.Efficient and ro- bust feature extraction by maximum margin criterion[J]. 本文给出了一种新的图正则化稀疏判别 IEEE transactions on neural networks,2006,17(1): NMF算法(GSDNMF-L2)。该方法在对图像进行 157-165. 特征提取时，充分利用了数据集的标签信息来构 [9]LU Yuwu,LAI Zhihui,XU Yong,et al.Nonnegative dis- 造权重矩阵和判别约束项。与已有的图正则化方 criminant matrix factorization[J].IEEE transactions on cir- 法不同的是，GSDNMF-L21算法用同类样本的稀 cuits and systems for video technology,2017,27(7): 疏线性组合来构建权重矩阵，很好地保持了样本 1392-1405 内的相似性和样本间的差异性，在最大间距准则 [10]CAI Deng,HE Xiaofei,HAN Jiawei,et al.Graph regular- 下使得类内离散性最小而类间分离性最大，从而 ized nonnegative matrix factorization for data representa- 获得很强的判别能力。另外，GSDNMF-L2,1在稀 tion[J].IEEE transactions on pattern analysis and ma- 疏性约束条件下得到了稀疏系数矩阵，从而提高 chine intelligence,2011,33(8):1548-1560. 了矩阵分解的速度。下一步研究的方向是如何处 [11]LONG Xianzhong,LU Hongtao,PENG Yong,et al. 理新样本，及自动选择最佳特征数量，使算法更 Graph regularized discriminative non-negative matrix fac- 加完善。 torization for face recognition[J].Multimedia tools and 参考文献： applications,2014,72(3y2679-2699. [12]LIAO Qing,ZHANG Qian.Local coordinate based [1]WOLD S,ESBENSEN K,GELADI P.Principal compon- graph-regularized NMF for image representation[J].Sig-

表 4 比较基图像 W 的稀疏度 Table 4 Comparison of sparsity of the base matrix W 数据集 NMF GNMF NDMF GSDNMF-L1 GSDNMF-L2,1 ORL 0.25 0.32 0.26 0.30 0.33 AR 0.52 0.55 0.52 0.55 0.56 COIL 0.49 0.56 0.49 0.54 0.65 (a) 3种算法在ORL数据集上的基图 (b) 3种算法在AR数据集上的基图 (c) 3种算法在COIL数据集上的基图 图 6 比较 NDMF，GSDNMF-L1 和 GSDNMF-L2,1 算法 在 ORL、AR 和 COIL20 数据集上得到的基图 Fig. 6 Comparison of basic images computed by NDMF, GSDNMF-L1 and GSDNMF-L2,1 algorithm on ORL,AR and COIL20 dataset 4 结束语 本文给出了一种新的图正则化稀疏判 别 NMF 算法 (GSDNMF-L2,1)。该方法在对图像进行 特征提取时，充分利用了数据集的标签信息来构 造权重矩阵和判别约束项。与已有的图正则化方 法不同的是，GSDNMF-L2,1 算法用同类样本的稀 疏线性组合来构建权重矩阵，很好地保持了样本 内的相似性和样本间的差异性，在最大间距准则 下使得类内离散性最小而类间分离性最大，从而 获得很强的判别能力。另外，GSDNMF-L2,1 在稀 疏性约束条件下得到了稀疏系数矩阵，从而提高 了矩阵分解的速度。下一步研究的方向是如何处 理新样本，及自动选择最佳特征数量，使算法更 加完善。 参考文献： [1] WOLD S, ESBENSEN K, GELADI P. Principal compon￾ent analysis[J]. Chemometrics and intelligent laboratory systems, 1987, 2(1/2/3): 37–52. BELHUMEUR P N, HESPANHA J P, KRIEGMAN D J. Eigenfaces vs. Fisherfaces: recognition using class specif￾ic linear projection[C]//Proceedings of the 4th European Conference on Computer Vision. Cambridge, UK, 1996: 45-58. [2] LEE D D, SEUNG H S. Learning the parts of objects by non-negative matrix factorization[J]. Nature, 1999, 401(6755): 788–791. [3] WANG Yuan, JIA Yunde, HU Changbo, et al. Fisher non￾negative matrix factorization for learning local features[C]//Proceedings of the 6th Asian Conference on Computer Vision. Jeju, Korea, 2004. [4] ZAFEIRIOU S, TEFAS A, BUCIU I, et al. Exploiting dis￾criminant information in nonnegative matrix factorization with application to frontal face verification[J]. IEEE trans￾actions on neural networks, 2006, 17(3): 683–695. [5] KOTSIA I, ZAFEIRIOU S, PITAS I. A novel discrimin￾ant non-negative matrix factorization algorithm with ap￾plications to facial image characterization problems[J]. IEEE transactions on information forensics and security, 2007, 2(3): 588–595. [6] GU Quanquan, ZHOU Jie. Two dimensional maximum margin criterion[C]// IEEE International Conference on Acoustics, Speech and Signal Processing. Taipei, Taiwan, 2009: 1621−1624. [7] LI Haifeng, JIANG Tao, ZHANG Keshu. Efficient and ro￾bust feature extraction by maximum margin criterion[J]. IEEE transactions on neural networks, 2006, 17(1): 157–165. [8] LU Yuwu, LAI Zhihui, XU Yong, et al. Nonnegative dis￾criminant matrix factorization[J]. IEEE transactions on cir￾cuits and systems for video technology, 2017, 27(7): 1392–1405. [9] CAI Deng, HE Xiaofei, HAN Jiawei, et al. Graph regular￾ized nonnegative matrix factorization for data representa￾tion[J]. IEEE transactions on pattern analysis and ma￾chine intelligence, 2011, 33(8): 1548–1560. [10] LONG Xianzhong, LU Hongtao, PENG Yong, et al. Graph regularized discriminative non-negative matrix fac￾torization for face recognition[J]. Multimedia tools and applications, 2014, 72(3): 2679–2699. [11] LIAO Qing, ZHANG Qian. Local coordinate based graph-regularized NMF for image representation[J]. Sig- [12] 第 6 期 徐慧敏，等：图正则化稀疏判别非负矩阵分解 ·1223·

·1224· 智能系统学报 第14卷 nal processing,2016,124:103-114. [19]LI H,LIU D,WANG D.Manifold regularized reinforce- [13]LI Xuelong,CUI Guosheng,DONG Yongsheng.Graph ment learning[J.IEEE transactions on neural networks regularized non-negative low-rank matrix factorization for &learning systems,2017,29(4):932-943. image clustering[J].IEEE transactions on cybernetics, [20]HOYER P O.Non-negative matrix factorization with 2017,4711):3840-3853 sparseness constraints[J].Journal of machine learning re- [14]SHANG Fanhua,JIAO L C,WANG Fei.Graph dual reg- search,2004,5:1457-1469 ularization non-negative matrix factorization for co-clus- [21]NIE Feiping,HUANG Heng,CAI Xiao,et al.Efficient tering[J].Pattern recognition,2012,45(6):2237-2250. and robust feature selection via joint (2,I-norms minim- ization[C]//Proceedings of the 23rd International Confer- [15]MENG Yang,SHANG Ronghua,JIAO Licheng,et al. ence on Neural Information Processing Systems.Van- Feature selection based dual-graph sparse non-negative couver,British Columbia,Canada,2010:1813-1821 matrix factorization for local discriminative clustering[J]. 作者简介： Neurocomputing,2018,290:87-99. 徐慧敏，女，1994年生，硕土研究 [16]EGGERT J,KORNER E.Sparse coding and NMF[C]// 生，主要研究方向为数字图像处理、模 Proceedings of 2004 IEEE International Joint Conference 式识别。 on Neural Networks.Budapest,Hungary,2004:2529- 2533. [17]BELKIN M,NIYOGI P,SINDHWANI V.Manifold reg- ularization:a geometric framework for learning from 陈秀宏.男，1964年生.教授.博 labeled and unlabeled examples[J].Journal of machine 士后，主要研究方向为数字图像处理 learning research,2006,7(1):2399-2434 和模式识别、优化理论与方法等。发 [18]HOU C,JING W.YI W,et al.Local linear transforma- 表学术论文120余篇。 tion embedding[J].Neurocomputing,2009,72(10-12): 2368-2378

nal processing, 2016, 124: 103–114. LI Xuelong, CUI Guosheng, DONG Yongsheng. Graph regularized non-negative low-rank matrix factorization for image clustering[J]. IEEE transactions on cybernetics, 2017, 47(11): 3840–3853. [13] SHANG Fanhua, JIAO L C, WANG Fei. Graph dual reg￾ularization non-negative matrix factorization for co-clus￾tering[J]. Pattern recognition, 2012, 45(6): 2237–2250. [14] MENG Yang, SHANG Ronghua, JIAO Licheng, et al. Feature selection based dual-graph sparse non-negative matrix factorization for local discriminative clustering[J]. Neurocomputing, 2018, 290: 87–99. [15] EGGERT J, KORNER E. Sparse coding and NMF[C]// Proceedings of 2004 IEEE International Joint Conference on Neural Networks. Budapest, Hungary, 2004: 2529- 2533. [16] BELKIN M, NIYOGI P, SINDHWANI V. Manifold reg￾ularization: a geometric framework for learning from labeled and unlabeled examples[J]. Journal of machine learning research, 2006, 7(1): 2399–2434. [17] HOU C, JING W, YI W, et al. Local linear transforma￾tion embedding[J]. Neurocomputing, 2009, 72(10-12): 2368–2378. [18] LI H, LIU D, WANG D. Manifold regularized reinforce￾ment learning[J]. IEEE transactions on neural networks &learning systems, 2017, 29(4): 932–943. [19] HOYER P O. Non-negative matrix factorization with sparseness constraints[J]. Journal of machine learning re￾search, 2004, 5: 1457–1469. [20] NIE Feiping, HUANG Heng, CAI Xiao, et al. Efficient and robust feature selection via joint ℓ2, 1-norms minim￾ization[C]//Proceedings of the 23rd International Confer￾ence on Neural Information Processing Systems. Van￾couver, British Columbia, Canada, 2010: 1813-1821. [21] 作者简介： 徐慧敏，女，1994 年生，硕士研究 生，主要研究方向为数字图像处理、模 式识别。 陈秀宏，男，1964 年生，教授，博 士后，主要研究方向为数字图像处理 和模式识别、优化理论与方法等。发 表学术论文 120 余篇。 ·1224· 智 能 系 统 学 报 第 14 卷