第2期 陈形，等：特征自表达和图正则化的鲁棒无监督特征选择 ·289· 其中S2=XXXX。 每类中随机选取10个样本组成训练集，剩余的样 对式(18)关于A求导并令其等于零可得： 本组成测试集进行实验。 S2A=SA((ASA)ATS2A) (19) 表1数据集具体信息 如设广义特征方程S2a=S1a的前k个最大 Table 1 Specific information of data sets 特征值分别为，2，…，d,对应的特征向量分别 数据集 样本数 类别数 特征数 为a1,a2…,ak,并令A=[a12…aJ,则有 Yale 165 5 1024 S2A=S Adiag(2,..,) (20) ORL 400 10 1024 此时，式(18)中r(ATS1A)ATS2A)达到最大。 MSRA 1799 12 256 这样，通过求解式(18)得到A,再式(16)得到 AR 3120 120 1024 B。此过程可迭代进行，直到终止条件满足。算 USPS 2007 0 256 法给出了更新A和B的具体步骤。 LEAVES 400 10 1024 算法FSRGR 输入数据矩阵X∈Rm4,L∈Rmm,k,入，B。 国國國婴图盟蟹墅恩围 (a)YALE数据集 输出A∈R,计算Ai=1,2,…,d)并按 照降序排列，然后从X中选择与前k个最大值所 國固涵圈图圈國国画國 对应的特征。 (b)ORL数据集 对L进行特征分解：L=UVU 腦國匿题圖閻閣慝監闔 计算G:G=VUX (C)MSRA数据集 初始化：对角矩阵P=I∈Rd,D=I∈Rm,投 影矩阵A,恢复矩阵B,迭代次数=0。 服国星里2型里叉里显 重复： (d)AR数据集 1)求解问题(18)更新A: 2见四☑包四四四图 2)根据式(16)更新B, (e)USPS数据集 3)根据式(14)更新P= 1 弟冬桌染·山少® 2K(ABY (f)LEAVES数据集 4)根据式(15)更新D= 2GAB) 图1部分数据集的图片 5)t=t+1 Fig.1 Visualization of some data sets with different noise 直到收敛。 3.2对比算法 2.3复杂度分析 为了验证所研究算法的有效性，考虑以下对 在每次迭代中，FSRGR算法的时间主要花费 比方法： 在式(I0)中XX+P+BGDG和(ATS1A)'AXX 1)NDFS:联合学习数据的局部几何结构和 以及特征分解的计算上，相应的复杂度为max{Oid, 基于L2:范数正则化项的稀疏线性回归。 Ond)},O(nd及On),其中n和d代表样本数及 2)JELSR:同时考虑了拉普拉斯正则化器和 特征数。在本次实验中，所提出的算法一般在 权重矩阵对特征的得分进行了排序。 10次迭代内收敛，所以算法的时间复杂度为 3)SOGFS!21:从低维空间中学习样本的全局 max(o(n'd),o(nd),O(n) 结构来选择重要特征。 3 实验与分析 4)L1-UFS2:将特征自表达以及基于L,范数 的图拉普拉斯正则化融入到同一框架中。 将在6个公开数据集上对FSRGR算法进行 5)LRLMR21:在低维子空间中进行学习，使 评估，并且与5个特征选择算法进行比较。以验 得对噪声更加鲁棒；通过图的流形正则化项来保 证该算法的有效性。 持原始数据的局部结构。 3.1数据集 3.3重构图像 实验中使用的6个公开数据集中，包括4个 图2展示了6种不同的算法(NDFS、JELSR 人脸数据集YALEUS、ORL、MSRAUS图以及AR, SOGFS、LI-UFS、LRLMR、FSRGR)关于AR数据 2个手写数字数据集USPS2o1和LEAVES2I。这 集得到的部分重构图像。以图2(g)为例，共展示 些数据集的具体信息如表1所示，数据集的部分 了7张图像，从左至右分别选取了200、250、300、 图像如图1所示。并且对于每一个数据集，均从 350、400、450、500个特征进行图像的重构。从S2 = X TXXT 其中 X。 对式 (18) 关于 A 求导并令其等于零可得： S2A = S1A((A TS1A) −1A TS2A) (19) S2 a = λS1 a λ1, λ2,··· , λk a1, a2,··· , ak A = [a1 a2 ··· ak] 如设广义特征方程 的前 k 个最大 特征值分别为 ，对应的特征向量分别 为 ，并令 ，则有 S2A = S1Adiag(λ1, λ2,··· , λk) (20) tr((A TS1A) −1A T 此时，式 (18) 中 S2A) 达到最大。 A B A B 这样，通过求解式 (18) 得到 ，再式 (16) 得到 。此过程可迭代进行，直到终止条件满足。算 法给出了更新 和 的具体步骤。 算法 FSRGR X ∈ R n×d L ∈ R 输入 数据矩阵 ， n×n ,k,λ,β。 A ∈ R d×k A i 2 输出 ，计算 (i = 1,2,··· ,d) 并按 照降序排列，然后从 X 中选择与前 k 个最大值所 对应的特征。 L = UVU 对 T L 进行特征分解： ; G = V 1 2 U T 计算 G： X ; P = I ∈ R d×d , D = I ∈ R 初始化 n×n ：对角矩阵 ，投 影矩阵 A ,恢复矩阵 B ,迭代次数 t=0。 重复： 1) 求解问题 (18) 更新 A ; 2) 根据式 (16) 更新 B ; P = 1 2 (AB) i 2 3) 根据式 (14) 更新 ; D = 1 2 (GAB) i 2 4) 根据式 (15) 更新 ; 5) t = t+1 ; 直到收敛。 2.3 复杂度分析 X TX+λP+βG T DG (A TS1A) −1A TX TX 在每次迭代中，FSRGR 算法的时间主要花费 在式 (10) 中 和 以及特征分解的计算上，相应的复杂度为 max{O(n 2 d), O(nd2 )}，O(nd2 ) 及 O(n 3 )，其中 n 和 d 代表样本数及 特征数。在本次实验中，所提出的算法一般在 10 次迭代内收敛，所以算法的时间复杂度 为 max{O(n 2 d),O(nd2 ), O(n 3 )}。 3 实验与分析 将在 6 个公开数据集上对 FSRGR 算法进行 评估，并且与 5 个特征选择算法进行比较。以验 证该算法的有效性。 3.1 数据集 实验中使用的 6 个公开数据集中，包括 4 个 人脸数据集 YALE[16] 、ORL[17] 、MSRA[18] 以及 AR[19] ， 2 个手写数字数据集 USPS[20] 和 LEAVES[21]。这 些数据集的具体信息如表 1 所示，数据集的部分 图像如图 1 所示。并且对于每一个数据集，均从 每类中随机选取 10 个样本组成训练集，剩余的样 本组成测试集进行实验。 表 1 数据集具体信息 Table 1 Specific information of data sets 数据集 样本数 类别数 特征数 Yale 165 15 1 024 ORL 400 10 1 024 MSRA 1799 12 256 AR 3120 120 1 024 USPS 2007 10 256 LEAVES 400 10 1 024 (a) YALE 数据集 (b) ORL 数据集 (c) MSRA 数据集 (d) AR 数据集 (e) USPS 数据集 (f) LEAVES 数据集 图 1 部分数据集的图片 Fig. 1 Visualization of some data sets with different noise 3.2 对比算法 为了验证所研究算法的有效性，考虑以下对 比方法： L2,1 1) NDFS[22] ：联合学习数据的局部几何结构和 基于 范数正则化项的稀疏线性回归。 2) JELSR[4] ：同时考虑了拉普拉斯正则化器和 权重矩阵对特征的得分进行了排序。 3) SOGFS[23] ：从低维空间中学习样本的全局 结构来选择重要特征。 4) L1-UFS[24] ：将特征自表达以及基于 L1 范数 的图拉普拉斯正则化融入到同一框架中。 5) LRLMR[25] ：在低维子空间中进行学习，使 得对噪声更加鲁棒；通过图的流形正则化项来保 持原始数据的局部结构。 3.3 重构图像 图 2 展示了 6 种不同的算法 (NDFS、JELSR、 SOGFS、L1-UFS、LRLMR、FSRGR) 关于 AR 数据 集得到的部分重构图像。以图 2(g) 为例，共展示 了 7 张图像，从左至右分别选取了 200、250、300、 350、400、450、500 个特征进行图像的重构。从 第 2 期 陈彤，等：特征自表达和图正则化的鲁棒无监督特征选择 ·289·