第17卷第2期 智能系统学报 Vol.17 No.2 2022年3月 CAAI Transactions on Intelligent Systems Mar.2022 D0L:10.11992tis.202012043 网络出版地址：https:/kns.cnki.net/kcms/detail/23.1538.TP.20210622.0900.002.html 特征自表达和图正则化的鲁棒无监督特征选择 陈彤，陈秀宏 (江南大学人工智能与计算机学院，江苏无锡214122) 摘要：为了在揭示数据全局结构的同时保留其局部结构.本文将特征自表达和图正则化统一到同一框架中， 给出了一种新的无监督特征选择(unsupervised feature selection,UFS)模型与方法。模型使用特征自表达，用其余 特征线性表示每一个特征，以保持特征的局部结构：用基于乙2：范数的图正则化项，在保留数据的局部几何结 构的同时可以降低噪声数据对特征选择的影响：除此之外，在权重矩阵上施加了低秩约束，保留数据的全局结 构。在6个不同的公开数据集上的实验表明，所给算法明显优于其他5个对比算法，表明了所提出的UFS框架 的有效性。 关键词：特征选择：鲁棒；图拉普拉斯：特征自表达；低秩约束；无监督：L21范数；降维 中图分类号：TP181文献标志码：A 文章编号：1673-4785(2022)02-0286-09 中文引用格式：陈彤，陈秀宏.特征自表达和图正则化的鲁棒无监督特征选择.智能系统学报，2022,17(2)：286-294. 英文引用格式：CHEN Tong,.CHEN Xiuhong.Feature self--representation and graph regularization for robust unsupervised fea- ture selection Jl.CAAI transactions on intelligent systems,2022,17(2):286-294 Feature self-representation and graph regularization for robust unsupervised feature selection CHEN Tong,CHEN Xiuhong (School of Artificial Intelligence and Computer Science,Jiangnan University,Wuxi 214122,China) Abstract:In order to reveal the global structure of data and preserve its local structure,this paper proposes a new unsu- pervised feature selection(UFS)method,which puts feature self-representation and graph regularization into the same framework.Specifically,the model uses the self-representation of the features to represent each feature through other features for preserving the local structure of the features.An L2.-norm based graph regularization term is used to re- duce the effect of noisy data on feature selection while preserving the local geometric structure.Furthermore,the model uses a low-rank constraint on the weight matrix to preserve the global structure.Experiments on six different public datasets show that the algorithm is clearly superior to the other five algorithms,which demonstrates the effectiveness of the proposed UFS framework. Keywords:feature selection;robust;graph Laplacian;feature self-representation;low-rank constraint;unsupervised, L2-norm;dimension reduction 随着互联网的迅猛发展，产生了大量的高维 特征选择方法包括有监督特征选择川、半监 数据，高维数据通常含有大量的冗余、噪声，会降 督特征选择)、无监督特征选择B。有监督特征 低学习算法的性能。基于这一问题，特征选择和 选择和半监督特征选择依赖于数据的标签信息， 特征提取成为了降维的重要手段。特征提取通过 然而在实际应用中，类别标注的成本过高。因 将高维数据投影到低维子空间来减少数据的维 此，这就要求应用无监督特征选择方法选择更具 度，特征选择是直接选择原始数据的特征子集作 价值的特征。常见的无监督特征选择方法可以分 为了三类：过滤法)、包裹法和嵌入法。过滤 为降维后的特征。本文，从特征选择的角度展开 式特征选择方法独立于具体的学习算法，运算效 研究。 率较高。它的主要思想是对每一维特征赋予权 收稿日期：2020-12-28.网络出版日期：2021-06-22 基金项目：江苏省研究生科研与实践创新计划项目(NKYI9074). 重，所得到的权重就代表着该特征的重要性，然 通信作者：陈秀宏.E-mail:xiuhongc(@jiangnan..edu.cn 后依据权重进行排序，把重要性相对较小的特征
DOI: 10.11992/tis.202012043 网络出版地址: https://kns.cnki.net/kcms/detail/23.1538.TP.20210622.0900.002.html 特征自表达和图正则化的鲁棒无监督特征选择 陈彤，陈秀宏 （江南大学 人工智能与计算机学院，江苏 无锡 214122） L2,1 摘 要：为了在揭示数据全局结构的同时保留其局部结构，本文将特征自表达和图正则化统一到同一框架中， 给出了一种新的无监督特征选择 (unsupervised feature selection，UFS) 模型与方法。模型使用特征自表达,用其余 特征线性表示每一个特征，以保持特征的局部结构；用基于 范数的图正则化项，在保留数据的局部几何结 构的同时可以降低噪声数据对特征选择的影响；除此之外，在权重矩阵上施加了低秩约束，保留数据的全局结 构。在 6 个不同的公开数据集上的实验表明，所给算法明显优于其他 5 个对比算法，表明了所提出的 UFS 框架 的有效性。 关键词：特征选择；鲁棒；图拉普拉斯；特征自表达；低秩约束；无监督； L2,1 范数；降维 中图分类号：TP181 文献标志码：A 文章编号：1673−4785(2022)02−0286−09 中文引用格式：陈彤, 陈秀宏. 特征自表达和图正则化的鲁棒无监督特征选择 [J]. 智能系统学报, 2022, 17(2): 286–294. 英文引用格式：CHEN Tong, CHEN Xiuhong. Feature self-representation and graph regularization for robust unsupervised feature selection[J]. CAAI transactions on intelligent systems, 2022, 17(2): 286–294. Feature self-representation and graph regularization for robust unsupervised feature selection CHEN Tong，CHEN Xiuhong (School of Artificial Intelligence and Computer Science, Jiangnan University, Wuxi 214122, China) L2;1 Abstract: In order to reveal the global structure of data and preserve its local structure, this paper proposes a new unsupervised feature selection (UFS) method, which puts feature self-representation and graph regularization into the same framework. Specifically, the model uses the self-representation of the features to represent each feature through other features for preserving the local structure of the features. An -norm based graph regularization term is used to reduce the effect of noisy data on feature selection while preserving the local geometric structure. Furthermore, the model uses a low-rank constraint on the weight matrix to preserve the global structure. Experiments on six different public datasets show that the algorithm is clearly superior to the other five algorithms, which demonstrates the effectiveness of the proposed UFS framework. L2,1 Keywords: feature selection; robust; graph Laplacian; feature self-representation; low-rank constraint; unsupervised; -norm; dimension reduction 随着互联网的迅猛发展，产生了大量的高维 数据，高维数据通常含有大量的冗余、噪声，会降 低学习算法的性能。基于这一问题，特征选择和 特征提取成为了降维的重要手段。特征提取通过 将高维数据投影到低维子空间来减少数据的维 度，特征选择是直接选择原始数据的特征子集作 为降维后的特征。本文，从特征选择的角度展开 研究。 特征选择方法包括有监督特征选择[1] 、半监 督特征选择[2] 、无监督特征选择[3-4]。有监督特征 选择和半监督特征选择依赖于数据的标签信息， 然而在实际应用中，类别标注的成本过高。因 此，这就要求应用无监督特征选择方法选择更具 价值的特征。常见的无监督特征选择方法可以分 为了三类：过滤法[3] 、包裹法[5] 和嵌入法[6]。过滤 式特征选择方法独立于具体的学习算法，运算效 率较高。它的主要思想是对每一维特征赋予权 重，所得到的权重就代表着该特征的重要性，然 后依据权重进行排序，把重要性相对较小的特征 收稿日期：2020−12−28. 网络出版日期：2021−06−22. 基金项目：江苏省研究生科研与实践创新计划项目 (JNKY19_074). 通信作者：陈秀宏. E-mail: xiuhongc@jiangnan.edu.cn. 第 17 卷第 2 期 智 能 系 统 学 报 Vol.17 No.2 2022 年 3 月 CAAI Transactions on Intelligent Systems Mar. 2022
第2期 陈形，等：特征自表达和图正则化的鲁棒无监督特征选择 ·287· 过滤掉，将重要性较大的特征作为原始数据的表 第i行第j列的元素。r(X)表示矩阵X的迹，X- 示。例如，最大方差法)以数据方差作为评价标 表示矩阵X的逆。矩阵X的L21范数被定义为 准，将特征按重要性排序进行选择。除此之外， 拉普拉斯评分法(LapScore)也是常见的无监督 的过滤式特征选择方法。包裹式特征选择方法从 矩阵X的F范数被定义为 初始特征集合中不断地选择特征子集，训练学习 器，根据学习器的性能进行评价，直到选择出最 佳的子集。LVW(Las Vegas Wrapper)⑧是一个典 型的包裹式特征选择方法，它在拉斯维加斯(Ls 1.2 特征自表达 Vegas method)框架下使用随机策略来进行子集搜 特征自表达已经被广泛地应用于无监督特征 索，并以最终分类器的误差作为特征子集评级准 选择之中。例如Zu等1提出了一种用于无监 则。嵌入式特征选择在学习器训练过程中自动地 督特征选择的正则化自表达(regularized self-rep 进行特征选择，其分类效果通常较好，同时该类 resentation,RSR)模型。在RSR中，X=[r'x2. 方法可以实现对多个特征的选择。嵌人式选择最 x]=x1x2…xeRm表示特征矩阵，其中样本 常用的是L,正则化和L2正则化，当正则化项增 数和特征数分别是n和d,X的每一行代表一个 大到一定程度时，所有的特征系数都会趋于0，在 样本，每一列代表一个特征维度。样本的特征自 这个过程中，会有一部分特征的系数先变为0，也 表达定义为 就实现了特征选择过程。除此之外，近年来又研 x≈∑xwni=l,2,…,d (1) 究出了更加有效且高效的无监督特征选择方法， 1 例如L等将局部几何一致性和冗余最小化结 式中：权重矩阵W∈Rd的元素wn表示第i个特 合到同一框架中，利用局部几何结构的一致性来 征x:和第j个特征x之间的权重。在式(1)中， 提高聚类精度，并在此过程中进行特征选择。Lu等网 每一个特征的特征表示项都是由其余重要的特征 提出了一种嵌入式无监督特征选择方法，该方法 组成的，而不重要的特征应该从特征表示项中移除。 通过局部线性嵌人(locally linear embedding,.LLE) 特征表示系数可通过以下模型来求解 算法得到特征权重矩阵，并使用L~范数来描述重 minX-XWI呢+AWIl2i (2) 构误差最下化。大量的实验结果证明，以上这些 式中：入为一个平衡参数，基于L2:范数的正则化项 方法均是有效的。 可得到行稀疏的权重矩阵W,从而实现特征选择。 对于特征选择来说，保持局部几何数据结构 从式(1)、(2)可以看出，所有训练样本的每 显然比保持全局结构更为重要山。最常用的局部 个特征（即式(1）左侧的)都是由其他特征的线 几何结构保持方法有以下3种：基于L2范数的局 性组合所表示的，相应的权重向量是式(2) 部线性嵌入(LLE)、局部保留投影(locality pre- 中W的第1列w。显然，w:中的值越大，其对应 serving projections,LPP)]以及局部切空间对齐 的特征在x的表示中所占的比重越多。除此之 (local tangent space alignment,LTSA)。而传统的 外，如果W的某一行的元素全为0，则相应的特 局部保留方法是基于L2范数，很容易受到噪声和 征不出现在特征自表达中，即所有参与特征自表 冗余数据的影响，其次，L,范数已经被应用于许 达的特征应该是重要的，而那些不重要的特征将 多正则化项中，这使得传统方法对离群值十分敏 通过WI2:来去除。 感，导致特征选择效果不理想。 1.3局部保留投影(LPP) 基于以上提出的问题，本文通过特征自表达、 局部保留投影(LPP))通过获得线性投影来 图正则化以及低秩约束，提出了一个鲁棒无监督特 最优地保持数据的邻域结构，即样本之间的某种 征选择模型，同时保留了数据的局部几何结构和 非线性关系在降维后仍然保留着这种关系。假设 全局结构。并在6个公开数据集上进行实验，且与 W是将样本数据投影到子空间的投影矩阵，则可 5个对比算法进行对比，证明了该模型的有效性。 以通过优化以下目标函数得到W的最优解： 1相关工作 min∑wrx-Wxs (3) ij=l 1.1符号元素定义 式中：W是投影矩阵；s是相似矩阵，关于s的元 对于任意矩阵X∈Rm”,x)表示的是该矩阵 素定义如下：
过滤掉，将重要性较大的特征作为原始数据的表 示。例如，最大方差法[7] 以数据方差作为评价标 准，将特征按重要性排序进行选择。除此之外， 拉普拉斯评分法[3] (LapScore) 也是常见的无监督 的过滤式特征选择方法。包裹式特征选择方法从 初始特征集合中不断地选择特征子集，训练学习 器，根据学习器的性能进行评价，直到选择出最 佳的子集。LVW(Las Vegas Wrapper)[8] 是一个典 型的包裹式特征选择方法，它在拉斯维加斯 (Las Vegas method) 框架下使用随机策略来进行子集搜 索，并以最终分类器的误差作为特征子集评级准 则。嵌入式特征选择在学习器训练过程中自动地 进行特征选择，其分类效果通常较好，同时该类 方法可以实现对多个特征的选择。嵌入式选择最 常用的是 L1 正则化和 L2 正则化[6] ，当正则化项增 大到一定程度时，所有的特征系数都会趋于 0，在 这个过程中，会有一部分特征的系数先变为 0，也 就实现了特征选择过程。除此之外，近年来又研 究出了更加有效且高效的无监督特征选择方法， 例如 Li 等 [9] 将局部几何一致性和冗余最小化结 合到同一框架中，利用局部几何结构的一致性来 提高聚类精度，并在此过程中进行特征选择。Liu 等 [10] 提出了一种嵌入式无监督特征选择方法，该方法 通过局部线性嵌入 (locally linear embedding, LLE) 算法得到特征权重矩阵，并使用 L1 -范数来描述重 构误差最下化。大量的实验结果证明，以上这些 方法均是有效的。 L2 对于特征选择来说，保持局部几何数据结构 显然比保持全局结构更为重要[11]。最常用的局部 几何结构保持方法有以下 3 种：基于 L2 范数的局 部线性嵌入 (LLE)[12] 、局部保留投影 (locality preserving projections, LPP)[13] 以及局部切空间对齐 (local tangent space alignment, LTSA)[14]。而传统的 局部保留方法是基于 范数，很容易受到噪声和 冗余数据的影响，其次，L2 范数已经被应用于许 多正则化项中，这使得传统方法对离群值十分敏 感，导致特征选择效果不理想。 基于以上提出的问题，本文通过特征自表达、 图正则化以及低秩约束，提出了一个鲁棒无监督特 征选择模型，同时保留了数据的局部几何结构和 全局结构。并在 6 个公开数据集上进行实验，且与 5 个对比算法进行对比，证明了该模型的有效性。 1 相关工作 1.1 符号元素定义 X ∈ R m×n 对于任意矩阵 ，xi j 表示的是该矩阵 i j tr(X) X X −1 X X L2,1 第 行第 列的元素。 表示矩阵 的迹， 表示矩阵 的逆。矩阵 的 范数被定义为 ∥X∥2,1 = ∑m i=1 ∥xi∥2 = ∑m i=1 vt∑n j=1 x 2 i j 矩阵 X 的 F 范数被定义为 ∥X∥F = vt∑m i=1 ∑n j=1 x 2 i j 1.2 特征自表达 X = [x 1 x 2 ··· x n ] = [x1 x2 ··· xd] ∈ R n×d X 特征自表达已经被广泛地应用于无监督特征 选择之中。例如 Zhu 等 [15] 提出了一种用于无监 督特征选择的正则化自表达 (regularized self-representation, RSR) 模型。在 RSR 中， 表示特征矩阵，其中样本 数和特征数分别是 n 和 d， 的每一行代表一个 样本，每一列代表一个特征维度。样本的特征自 表达定义为 xi ≈ ∑d j=1 xjwji, i = 1,2,··· ,d (1) W ∈ R d×d wji xi xj 式中：权重矩阵 的元素 表示第 i 个特 征 和第 j 个特征 之间的权重。在式 (1) 中， 每一个特征的特征表示项都是由其余重要的特征 组成的，而不重要的特征应该从特征表示项中移除。 特征表示系数可通过以下模型来求解 min W ∥X− XW∥ 2 F +λ∥W∥2,1 (2) λ L2,1 W 式中： 为一个平衡参数，基于 范数的正则化项 可得到行稀疏的权重矩阵 ，从而实现特征选择。 xi W wi wi xi W ∥W∥2,1 从式 (1)、(2) 可以看出，所有训练样本的每一 个特征 (即式 (1) 左侧的 ) 都是由其他特征的线 性组合所表示的，相应的权重向量是 式 (2) 中 的第 i 列 。显然， 中的值越大，其对应 的特征在 的表示中所占的比重越多。除此之 外，如果 的某一行的元素全为 0，则相应的特 征不出现在特征自表达中，即所有参与特征自表 达的特征应该是重要的，而那些不重要的特征将 通过 来去除。 1.3 局部保留投影 (LPP) W W 局部保留投影 (LPP)[13] 通过获得线性投影来 最优地保持数据的邻域结构，即样本之间的某种 非线性关系在降维后仍然保留着这种关系。假设 是将样本数据投影到子空间的投影矩阵，则可 以通过优化以下目标函数得到 的最优解： min W ∑n i, j=1 WT x i −WT x j 2 si j (3) 式中： W 是投影矩阵； s 是相似矩阵，关于 s 的元 素定义如下： 第 2 期 陈彤，等：特征自表达和图正则化的鲁棒无监督特征选择 ·287·
·288· 智能系统学报 第17卷 llx-xl2 exp x是x的k近邻或x是x的k近邻 minllX-XWIle+allWll2 +BIIGWIl2 (11) ii- 2r2 2.1.3目标函数 0. 其他 (4) 式(11)通过特征自表达和图正则化来保留数 N(x)是x的k个近邻的集合，σ是宽度参数。 据的局部几何结构，但该模型却缺少了全局结 构信息，无法准确地捕捉特征的全局结构信息。 2基于特征自表达和图正则化模型 因此本文采用低秩约束来保留数据的全局结构。 区别于传统的特征自表达，此处将特征自表达以 2.1模型建立 及图正则化项与低秩约束相结合，分别考虑了局 为了给出基于特征自表达的鲁棒联合图正则 部特征相关性和全局特征相关性，从而得到局部 化无监督特征选择(feature self-representation and 特征自表达和全局特征自表达。具体来说，就是 graph regularization,FSRGR)模型，首先引入以下 对W施加一个低秩假设，即W=AB,所得目标函 图正则化特征自表达无监督特征选择一般模型： 数为 minllX-XWl+lWll1+B(W) (5) minllX-XAB+lABIk:+BIGABIl (12) 式中：(W是图正则化项，用于保留数据的局部 式中：A∈Rt为投影矩阵；B∈Rxd为恢复矩阵。 几何结构。入和B是用于平衡L2:范数和正则化 入和B均是平衡参数。 项的两个参数。 该模型利用特征自表达保留了特征的局部结 2.1.1基于L2范数图正则化项的无监督特征选择 构，并采用了低秩约束（即用A和B代替来保 局部线性嵌人(LLE)回、局部保留投影(LPP 留样本以及特征的全局结构。此外，对传统LPP 和局部切线空间对齐(LTSA)等均是基于L2范 模型中的拉普拉斯矩阵进行特征分解，建立基于 数的图正则化方法。将LPP思想应用于模型 L21范数的图正则化项，增强其鲁棒性和稀疏性， ()中，则可得到以下模型： 并保留了数据的局部几何结构。 minK-Xw形+Awk+B∑lwx-wxr(⑥ 2.2优化算法 虽然式(12)中的目标函数是凸的，但很难联 式(6)也可以表示为 合地求解所有变量。这里使用交替迭代优化策略 minlX-XWl+lWlk+Btr(WTXLXW) (7) 去优化它，即交替地迭代每一个变量，直至算法 式中：L是一个拉普拉斯矩阵，且L=D-S,D是 收敛。 一个对角矩阵，其对角元素为D,-乃，S由式 首先，式(12)可以改写为 =1 (XX-2XXAB+BAXXAB)+ (4)定义。 (13) At(BTATPAB)+Btr(BTATGDGAB) 2.1.2基于L21范数图正则化项的无监督特征 式中：P为对角矩阵，将其第i个对角元素定义为 选择 1 在式（⑦）中，最后一项图正则化项用于保留数 2lA0i=12…,n (14) 据的局部几何结构，然而，基于L2范数的正则化 D为对角矩阵，其第i个对角元素定义为 函数容易受到噪声数据的影响。为减少噪声的影 1 d=2GAB1=12” (15) 响，下面介绍一种基于L2!范数的图正则化方法， 使得模型对噪声数据更加鲁棒。 式中：(ABy是矩阵AB的第i行；(GABy是矩阵 由于拉普拉斯矩阵L是实对称的，故设矩阵 GAB的第i行。 L特征分解为 对式(13)中目标函数关于B求导数并设令其 L=UVUT (8) 等于0，可以得到： 于是，式()中的图正则化项可以改写为 B=(ATSA)ATXX (16) (WTXLXW)=t(WTXUVUTXW)= 其中，S1=XX+P+BGDG。 (9) HvU'Xw=IGWI呢 将式(16)代入到式(13)中，式(13)可以变为 其中G=VUX。为了使模型对噪声数据更加鲁 以下形式： 棒，使用L21范数代替F范数，可以得到基于L2 mint(XX-XTXA(ATS A)ATXTX) (17) 范数的图正则化项： 它等价于以下问题： (W)=lIGWIl2. (10) 于是式()可改写为 max tr((ATSA)-ATS2A) (18)
si j = exp( − ∥x i − x j ∥2 2σ2 ) , x i是x j的k近邻或x j是x i的k近邻 0, 其他 (4) Nk(x j ) x i 是 的 k 个近邻的集合，σ 是宽度参数。 2 基于特征自表达和图正则化模型 2.1 模型建立 为了给出基于特征自表达的鲁棒联合图正则 化无监督特征选择 (feature self-representation and graph regularization, FSRGR) 模型，首先引入以下 图正则化特征自表达无监督特征选择一般模型： min W ∥X− XW∥ 2 F +λ∥W∥2,1 +βφ(W) (5) φ(W) λ β L2,1 式中： 是图正则化项，用于保留数据的局部 几何结构。 和 是用于平衡 范数和正则化 项的两个参数。 2.1.1 基于 L2 范数图正则化项的无监督特征选择 L2 局部线性嵌入 (LLE)[12] 、局部保留投影 (LPP)[13] 和局部切线空间对齐 (LTSA)[14] 等均是基于 范 数的图正则化方法。将 LPP 思想应用于模型 (5) 中，则可得到以下模型： min W ∥X− XW∥ 2 F +λ∥W∥2,1 +β ∑n i, j=1 WT x i −WT x j 2 si j (6) 式 (6) 也可以表示为 min W ∥X− XW∥ 2 F +λ∥W∥2,1 +βtr(WTX T LXW) (7) L L = D−S D Dii = ∑n j=1 si j S 式中： 是一个拉普拉斯矩阵，且 ， 是 一个对角矩阵，其对角元素为 ， 由式 (4) 定义。 2.1.2 基于 L2,1 范数图正则化项的无监督特征 选择 L2 L2,1 在式 (7) 中，最后一项图正则化项用于保留数 据的局部几何结构，然而，基于 范数的正则化 函数容易受到噪声数据的影响。为减少噪声的影 响，下面介绍一种基于 范数的图正则化方法， 使得模型对噪声数据更加鲁棒。 L L 由于拉普拉斯矩阵 是实对称的，故设矩阵 特征分解为 L = UVUT (8) 于是，式 (7) 中的图正则化项可以改写为 tr(WTX T LXW) = tr(WTX TUVUTXW) = V 1 2 U TXW 2 F = ∥GW∥ 2 F (9) G = V 1 2 U TX L2,1 L2,1 其中 。为了使模型对噪声数据更加鲁 棒，使用 范数代替 F 范数，可以得到基于 范数的图正则化项： φ(W) = ∥GW∥2,1 (10) 于是式 (7) 可改写为 min W ∥X− XW∥ 2 F +λ∥W∥2,1 +β∥GW∥2,1 (11) 2.1.3 目标函数 W W = AB 式 (11) 通过特征自表达和图正则化来保留数 据的局部几何结构，但该模型却缺少了全局结 构信息，无法准确地捕捉特征的全局结构信息。 因此本文采用低秩约束来保留数据的全局结构。 区别于传统的特征自表达，此处将特征自表达以 及图正则化项与低秩约束相结合，分别考虑了局 部特征相关性和全局特征相关性，从而得到局部 特征自表达和全局特征自表达。具体来说，就是 对 施加一个低秩假设，即 ，所得目标函 数为 min W ∥X− XAB∥ 2 F +λ∥AB∥2,1 +β∥GAB∥2,1 (12) A ∈ R d×k B ∈ R k×d λ β 式中： 为投影矩阵； 为恢复矩阵。 和 均是平衡参数。 L2,1 该模型利用特征自表达保留了特征的局部结 构，并采用了低秩约束 (即用 A 和 B 代替 W) 来保 留样本以及特征的全局结构。此外，对传统 LPP 模型中的拉普拉斯矩阵进行特征分解，建立基于 范数的图正则化项，增强其鲁棒性和稀疏性， 并保留了数据的局部几何结构。 2.2 优化算法 虽然式 (12) 中的目标函数是凸的，但很难联 合地求解所有变量。这里使用交替迭代优化策略 去优化它，即交替地迭代每一个变量，直至算法 收敛。 首先，式 (12) 可以改写为 min A,B tr(X TX−2X TXAB+ B TA TX TXAB)+ λtr(B TA T PAB)+βtr(B TA TG T DGAB) (13) 式中： P 为对角矩阵，将其第 i 个对角元素定义为 pii = 1 2∥(AB) i ∥2 , i = 1,2,··· ,n (14) D 为对角矩阵，其第 i 个对角元素定义为 dii = 1 2 (GAB) i 2 ,i = 1,2,··· ,n (15) (AB) i AB (GAB) i GAB 式中： 是矩阵 的第 i 行； 是矩阵 的第 i 行。 对式 (13) 中目标函数关于 B 求导数并设令其 等于 0，可以得到： B = (A TS1A) −1A TX TX (16) S1 = X TX+λP+βG T 其中， DG。 将式 (16) 代入到式 (13) 中，式 (13) 可以变为 以下形式： min A tr(X TX− X TXA(A TS1A) −1A TX TX) (17) 它等价于以下问题： max A tr((A TS1A) −1A TS2A) (18) ·288· 智 能 系 统 学 报 第 17 卷
第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·
·290· 智能系统学报 第17卷 图2中可以看出，同其他5个对比算法相比，FSR- 3.4分类精度和聚类精度 G算法对于图像的重构效果更好。而在6种算 将在不同数据集上比较FSRGR算法同其他 法中，JELSR算法的重构效果最差，可以明显看 5种对比算法，分别评估它们的聚类及分类性 出，随着所选特征数量的增加，该算法所选择的 能。具体的结果见图3和图4。其中图3展示了 特征均为不重要的面部特征，而重要的人脸的五 所有算法在6个数据集上关于分类精度的对比结 官特征并没有被选择。 果。如图3所示，其横轴表示所选择的特征数，纵 轴代表不同的特征数所对应的分类精度(ACC)。 由于不同数据集的特征数通常是不相同的，因此 (a)原始图像 对于YALE、ORL、AR和LEAVES数据集，我们 所选择的特征数的范围为{50,100,150,200,250， 3001,而对于MSRA及USPS数据集，将所选择的 (b)NDFS 特征数的范围设置为(20,40,60,80,100,120)。并且 对于每一个算法，为了呈现出最直实的比较结 果，均将其参数调至为最佳参数，即所呈现出的 (c)JELSR 实验结果均为其最好的结果。首先从图3可以看 出，在大多数情况下，本文所提出的FSRGR算法 均优于其他对比算法。尤其在AR数据集上，相 (d)SOGFS 比其他5种对比算法，FSRGR所取得的分类效果 明显更加优越。还可以看出，在5种对比算法中， 分类性能最好的是LRLMR算法，分类效果最差 (e)L1-UFS 的是NDFS算法。其次，图4比较了FSRGR算法 同其他对比算法在不同数据集上的聚类性能。从 (f)LRLMR 图中可以看出，随着所选特征数的增加，通过FS RGR算法所得到的聚类效果可以稳定地优于其 他对比算法。这是因为本文所提出的方法既保留 (g)FSRGR 了数据的局部几何结构，又保留了数据的全局结 构，并且通过对权重矩阵施加低秩约束，使得所 图2不同算法对部分AR数据集的重构图像 Fig.2 Reconstructed images of partial AR data sets by dif- 学习到的投影向量的数量不受限制，从而可以得 ferent algorithms 到足够多的投影向量。 0.55 0.90r 0.85 0.50 0.85 0.80 0.45 0.80 0.40 NDFS 0.75 NDFS NDFS JELSR 0.35 SOGFS 0.70 0.30 0.65 FSRGR 0.65 FSRGR FSRGR 0.2 50 100150200 250 0.6 0.60 300 50 100150200 250 300 40 60 80 100 120 选择的特征数 选择的特征数 选择的特征数 (a)YALE (b)ORL (c)MSRA 0.90 -NDFS 。JELSR 0.74 0.56 0.80 SOGFS 0.54 ◆-L1-UFS 0.70 0.52 0.70 NDES 0.60 0.50 LRLMR 0.48 0.50 FSRGR 0.58 0.46 0.40 0.5 0.44 0100150200250300 20 406080100120 0100150200250300 选择的特征数 选择的特征数 选择的特征数 (d)AR (e)USPS (f)LEAVES 图36种算法在6种数据集上的分类精度 Fig.3 Classification accuracies of six methods on six data sets
图 2 中可以看出，同其他 5 个对比算法相比，FSRGR 算法对于图像的重构效果更好。而在 6 种算 法中，JELSR 算法的重构效果最差，可以明显看 出，随着所选特征数量的增加，该算法所选择的 特征均为不重要的面部特征，而重要的人脸的五 官特征并没有被选择。 (a) 原始图像 (b) NDFS (c) JELSR (d) SOGFS (e) L1-UFS (f) LRLMR (g) FSRGR 图 2 不同算法对部分 AR 数据集的重构图像 Fig. 2 Reconstructed images of partial AR data sets by different algorithms 3.4 分类精度和聚类精度 {50,100,150,200,250, 300} {20,40,60,80,100,120} 将在不同数据集上比较 FSRGR 算法同其他 5 种对比算法，分别评估它们的聚类及分类性 能。具体的结果见图 3 和图 4。其中图 3 展示了 所有算法在 6 个数据集上关于分类精度的对比结 果。如图 3 所示，其横轴表示所选择的特征数，纵 轴代表不同的特征数所对应的分类精度 (ACC)。 由于不同数据集的特征数通常是不相同的，因此 对于 YALE、ORL、AR 和 LEAVES 数据集，我们 所选择的特征数的范围为 ，而对于 MSRA 及 USPS 数据集，将所选择的 特征数的范围设置为 。并且 对于每一个算法，为了呈现出最真实的比较结 果，均将其参数调至为最佳参数，即所呈现出的 实验结果均为其最好的结果。首先从图 3 可以看 出，在大多数情况下，本文所提出的 FSRGR 算法 均优于其他对比算法。尤其在 AR 数据集上，相 比其他 5 种对比算法，FSRGR 所取得的分类效果 明显更加优越。还可以看出，在 5 种对比算法中， 分类性能最好的是 LRLMR 算法，分类效果最差 的是 NDFS 算法。其次，图 4 比较了 FSRGR 算法 同其他对比算法在不同数据集上的聚类性能。从 图中可以看出，随着所选特征数的增加，通过 FSRGR 算法所得到的聚类效果可以稳定地优于其 他对比算法。这是因为本文所提出的方法既保留 了数据的局部几何结构，又保留了数据的全局结 构，并且通过对权重矩阵施加低秩约束，使得所 学习到的投影向量的数量不受限制，从而可以得 到足够多的投影向量。 50 100 150 200 250 300 选择的特征数 NDFS JELSR SOGFS LRLMR FSRGR L1-UFS NDFS JELSR LRLMR FSRGR SOGFS L1-UFS NDFS JELSR SOGFS LRLMR FSRGR L1-UFS NDFS JELSR SOGFS LRLMR FSRGR L1-UFS NDFS JELSR SOGFS LRLMR FSRGR L1-UFS NDFS JELSR SOGFS LRLMR FSRGR L1-UFS ACC 0.55 0.50 0.45 0.40 0.35 0.30 0.25 (a) YALE 50 100 150 200 250 300 选择的特征数 0.60 0.65 0.70 0.75 0.80 0.85 0.90 ACC (b) ORL 20 40 60 80 100 120 选择的特征数 0.60 0.65 0.70 0.75 0.80 0.85 ACC (c) MSRA 50 100 150 200 250 300 选择的特征数 0.40 0.50 0.60 0.70 0.80 0.90 ACC 20 40 60 80 100 120 选择的特征数 0.54 0.58 0.62 0.66 0.70 0.74 ACC (d) AR 50 100 150 200 250 300 选择的特征数 0.44 0.46 0.48 0.50 0.52 0.54 0.56 ACC (e) USPS (f) LEAVES 图 3 6 种算法在 6 种数据集上的分类精度 Fig. 3 Classification accuracies of six methods on six data sets ·290· 智 能 系 统 学 报 第 17 卷