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