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