第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 卷
第2期 陈形，等：特征自表达和图正则化的鲁棒无监督特征选择 ·291· 0.40 0.50 0.56 0.38 0.48 0.52 0.36 0.46 NDES NDES 0.44 JFLSR 0.44 0.32 SOGES 0.42 SOGFS I L-TES 0.30 LRLMR 0.40 LRLMR 0.40 FSRGR 0.28 FSRGR 0.38 0.36 0 100150200 250300 0 100150200 250 300 0 406080100120 选择的特征数 选择的特征数 选择的特征数 (a)YALE (b)ORL (c)MSRA 0.5 -NDES 0.65 NDFS 0.50 JELSR 0.4 0.55 、-女 0.46 -b-SOGFS --SOGFS <0.2 当 ” LI-UFS LI-UFS LI-UFS 0.1 LRLMR 0.25 0.34 LRLMR -FSRGR -FSRGR FSRGR 0 0.1 0.30 50 100150200250 300 20 40 6080 100120 50 100150 200250 300 选择的特征数 选择的特征数 选择的特征数 (d)AR (e)USPS (f)LEAVES 图46种算法在6种数据集上的聚类精度 Fig.4 Clustering accuracies of six methods on six data sets 3.5 运行时间 从表2可以看出，在所有方法中运行时间最 为了比较不同算法的运行时间，在YALE、 短的是LRLMR算法，本文所提出的FSRGR算法 MSRA、ORL和USPS数据集上进行了聚类实验， 同L1-UFS.LRLMR及NDFS算法相比，运行时间 所有算法均在MATLAB中实现。具体的实验结 较长。而ELSR与SOGFS算法对于不同的数据 果位于表2中。 集，运行时间并不稳定。 表2不同方法的运行时间 Table 2 Running time of different methods 数据集 FSRGR JELSR L1-UFS LRLMR NDFS SOGFS YALE 1.2050±0.0087 0.4319±0.0022 0.8064±0.0975 0.3943±0.1185 0.1782±0.098 2.1252±0.2921 MSRA 1.4480±0.0015 3.0495±0.0032 0.2080±0.0413 0.2080±0.0895 1.0388±0.0895 1.4380±0.1261 ORL 1.1572±0.0024 0.5262±0.0023 1.0063±0.0516 0.5111±0.1063 0.2211±0.0982 2.2545±0.0073 USPS 1.1509±0.0075 3.7314牡0.0039 0.1315±0.0558 0.0995±0.0467 1.3163±0.0741 0.1380±0.0030 3.6收敛性分析 影响。首先参数B是用于平衡X-XABI和IIGABIL2 通过计算不同迭代次数对应的目标函数值来 其次是参数A,用于控制AB的稀疏性。并且这 观察FSRGR算法的收敛曲线。并且最大迭代次 两个参数的取值范围均被设置为{10-6,10-4， 数设置为10。由于FSRGR算法在不同的数据集 10-2,1,102,10,101。实验采用了K-means算法，呈 上有相似的收敛性，因此在收敛性分析的部分只 现出了不同的参数组合在不同的数据集上对于聚 展示了在YALE数据集上的实验结果。从图5中 类精度的影响。具体的实验结果见图6。 可以发现：1)所提出的算法优化了式(12)所提出 从图6可以看出，本文所提出的方法对参数 的目标函数，单调地减少了目标函数值直至算法 的设置较为敏感，不同的参数组合具有不同的聚 收敛。2)所提出的算法需要经过数次迭代来有效 类结果。举例说明，对于人脸数据集YALE,当 地达到收敛。 A=10-2,B=106时，FSRGR的聚类精度达到了 3.7参数设置 36.89%的最好效果；而对于手写字数据集USPS, 重点研究参数B和入的取值对于聚类精度的 当A=10,B=10~4时，FSRGR的聚类精度达到了
NDFS NDFS JELSR SOGFS JELSR SOGFS LRLMR FSRGR L1-UFS 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 (a) YALE (b) ORL (c) MSRA (d) AR (e) USPS (f) LEAVES 50 100 150 200 250 300 选择的特征数 0 0.1 0.2 0.3 0.4 0.5 ACC NDFS JELSR SOGFS LRLMR FSRGR L1-UFS 50 100 150 200 250 300 选择的特征数 0.30 0.34 0.38 0.42 0.46 0.50 ACC 20 40 60 80 100 120 选择的特征数 0.36 0.40 0.44 0.48 0.52 0.56 ACC 50 100 150 200 250 300 选择的特征数 0.38 0.40 0.42 0.44 0.46 0.48 0.50 ACC 20 40 60 80 100 120 选择的特征数 0.15 0.25 0.35 0.45 0.55 0.65 ACC 50 100 150 200 250 300 选择的特征数 0.28 0.30 0.32 0.34 0.36 0.38 0.40 ACC 图 4 6 种算法在 6 种数据集上的聚类精度 Fig. 4 Clustering accuracies of six methods on six data sets 3.5 运行时间 为了比较不同算法的运行时间，在 YALE、 MSRA、ORL 和 USPS 数据集上进行了聚类实验， 所有算法均在 MATLAB 中实现。具体的实验结 果位于表 2 中。 从表 2 可以看出，在所有方法中运行时间最 短的是 LRLMR 算法，本文所提出的 FSRGR 算法 同 L1-UFS,LRLMR 及 NDFS 算法相比，运行时间 较长。而 JELSR 与 SOGFS 算法对于不同的数据 集，运行时间并不稳定。 表 2 不同方法的运行时间 Table 2 Running time of different methods s 数据集 FSRGR JELSR L1-UFS LRLMR NDFS SOGFS YALE 1.205 0±0.0087 0.4319±0.0022 0.8064±0.0975 0.394 3±0.1185 0.178 2±0.098 2.1252±0.292 1 MSRA 1.448 0±0.0015 3.0495±0.0032 0.2080±0.0413 0.208 0±0.0895 1.0388±0.0895 1.4380±0.126 1 ORL 1.157 2±0.0024 0.5262±0.0023 1.0063±0.0516 0.511 1±0.1063 0.221 1 ±0.098 2 2.2545±0.007 3 USPS 1.150 9±0.0075 3.731 4± 0.003 9 0.1315±0.0558 0.099 5±0.0467 1.3163±0.0741 0.1380±0.003 0 3.6 收敛性分析 通过计算不同迭代次数对应的目标函数值来 观察 FSRGR 算法的收敛曲线。并且最大迭代次 数设置为 10。由于 FSRGR 算法在不同的数据集 上有相似的收敛性，因此在收敛性分析的部分只 展示了在 YALE 数据集上的实验结果。从图 5 中 可以发现：1) 所提出的算法优化了式 (12) 所提出 的目标函数，单调地减少了目标函数值直至算法 收敛。2) 所提出的算法需要经过数次迭代来有效 地达到收敛。 3.7 参数设置 重点研究参数 β 和 λ 的取值对于聚类精度的 β ∥X− XAB∥ 2 F ∥GAB∥2,1 λ AB {10−6 ,10−4 , 10−2 ,1,102 ,104 ,106 } 影响。首先参数 是用于平衡 和 ， 其次是参数 ，用于控制 的稀疏性。并且这 两个参数的取值范围均被设置为 。实验采用了 K-means 算法，呈 现出了不同的参数组合在不同的数据集上对于聚 类精度的影响。具体的实验结果见图 6。 λ = 10−2 , β = 10−6 λ = 104 , β = 10−4 从图 6 可以看出，本文所提出的方法对参数 的设置较为敏感，不同的参数组合具有不同的聚 类结果。举例说明，对于人脸数据集 YALE,当 时 ， FSRGR 的聚类精度达到了 36.89% 的最好效果；而对于手写字数据集 USPS， 当 时，FSRGR 的聚类精度达到了 第 2 期 陈彤，等：特征自表达和图正则化的鲁棒无监督特征选择 ·291·
·292· 智能系统学报 第17卷 57.70%的最好效果。 3.8低秩约束的影响 1.8*10 式(12)中不同秩(k∈{3,6,9,12,15)在数 据集AR、ISOLET、PIE、LUNG、USPS、YALE上 1.7 1.6 对聚类精度的影响。图7中给出了FSRGR在不 同数据集上满秩和低秩下的聚类精度。其中横轴 代表所选定的秩的范围，纵轴代表不同的秩所对 13 2 应的分类精度。 从图7中可以观察到，低秩约束下的聚类性 1.0 能在大多数情况下都优于满秩。例如，在数据集 0.9 23 45678910 AR和USPS上，同全秩的情况下相比，低秩约束 迭代次数 下所得到的平均分类精度分别高出了12.43%和 图5 FSRGR在YALE数据集上的收敛性 17.88%。这说明在特征选择中，对高维数据进行 Fig.5 Convergence of FSRGR on YALE data sets 低秩约束是有效的。 0.40 0.60 0.50 0.38 0.55 0.48 0.36 0.50 0.46 0.34 0.45 0.44 0.32 0.42 0.30 0.40 0.40 子 10 10 10 B 10N 10 10 10 10 104 10s (a)YALE (b)ORL (c)MSRA 0.5 0.60 0.50 0.45 0.35 0.40 0.30 10s 105 10 B 102 10 102 B 102 10s 106 心心 10s10 (d)AR (e)USPS (f)LEAVES 图6不同B和A组合下的SRGR聚类精度 Fig.6 Clustering accuracy of FSRGR algorithm with different combination of B and A 0.40 0.50 0.435 0.38 0.46 0.430 0.425 0.42 0.34 0.415 0.32 士钙秩 0.34 0.410 0.3 0.30 0.40 3 6 9 2 15 6 9 12 15 3 6 9 1215 秩 秩 (a)YALE (b)ORL (c)MSRA
57.70% 的最好效果。 1 2 3 4 5 6 7 8 9 10 迭代次数 0.9 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 目标函数值 ×108 图 5 FSRGR 在 YALE 数据集上的收敛性 Fig. 5 Convergence of FSRGR on YALE data sets 3.8 低秩约束的影响 式 (12) 中不同秩 ( k ∈ {3，6，9，12，15} ) 在数 据集 AR、ISOLET、PIE、LUNG、USPS、YALE 上 对聚类精度的影响。图 7 中给出了 FSRGR 在不 同数据集上满秩和低秩下的聚类精度。其中横轴 代表所选定的秩的范围，纵轴代表不同的秩所对 应的分类精度。 从图 7 中可以观察到，低秩约束下的聚类性 能在大多数情况下都优于满秩。例如，在数据集 AR 和 USPS 上，同全秩的情况下相比，低秩约束 下所得到的平均分类精度分别高出了 12.43% 和 17.88%。这说明在特征选择中，对高维数据进行 低秩约束是有效的。 10−6 10−6 10−2 102 106 10−4 10−2 100 102 104 106 10−6 10−4 10−2 100 102 104 106 0.40 0.5 0.4 0.3 0.2 0.1 0.38 0.36 0.34 0.32 0.30 聚类精度 聚类精度 0.60 0.55 0.50 0.45 0.40 0.50 0.45 0.40 0.35 0.30 聚类精度 聚类精度 聚类精度 聚类精度 λ 10−6 10−2 102 106 λ 10−6 10−2 102 106 λ β 10−6 10−4 10−2 100 102 104 106 β 10−6 10−4 10−2 100 102 104 106 β 10−6 10−4 10−2 100 102 104 106 β β 10−6 10−4 10−2 100 102 104 106 β 10−6 10−2 102 106 λ 10−6 10−2 102 106 λ 10−6 10−2 102 106 λ 0.60 0.55 0.50 0.45 0.40 0.50 0.48 0.46 0.44 0.42 0.40 (a) YALE (b) ORL (c) MSRA (d) AR (e) USPS (f) LEAVES 图 6 不同 β 和 λ 组合下的 FSRGR 聚类精度 Fig. 6 Clustering accuracy of FSRGR algorithm with different combination of β and λ 3 6 9 12 15 秩 3 6 9 12 15 秩 3 6 9 12 15 秩 0.30 0.32 0.34 0.36 0.38 0.40 ACC 低秩 满秩 低秩 满秩 低秩 满秩 0.30 0.34 0.38 0.42 0.46 0.50 ACC 0.405 0.410 0.415 0.420 0.425 0.430 0.435 ACC (a) YALE (b) ORL (c) MSRA ·292· 智 能 系 统 学 报 第 17 卷
第2期 陈形，等：特征自表达和图正则化的鲁棒无监督特征选择 ·293· 0.61 0.8 0.48r 0.7 一低秋 0.5 0.46◆满秩 0.6 0.445 80.5 80.42 0.4 0.40 02 一联 0.3 →低秩 ◆满秩 0.38 0.1 0.2 0.36 3 6 9 15 6 91215 6 1215 秩 秩 秩 (d)AR (e)USPS (f)LEAVES 图7 FSRGR在不同秩上的ACC结果 Fig.7 ACC results of FSRGR at different number of ranks 4结束语 [6]CAI Deng,ZHANG Chiyuan,HE Xiaofei.Unsupervised feature selection for multi-cluster data[Cl//Proceedings of 本文提出了一种新的鲁棒无监督特征选择模 the 16th ACM SIGKDD International Conference on 型，它将特征自表达、低秩约束、图正则化以及 Knowledge Discovery and Data Mining.Washington, L21范数正则化项统一在同一框架中，将传统的基 USA.2010:333-342. 于L2范数的图正则化项通过特征分解改为基于 [7]ADHIKARY J R,MURTY M N.Feature selection for L2:范数的正则化项，并对权重矩阵施加了一个低 unsupervised learning[C]//Proceedings of 19th Interna- 秩约束。该方法能够降低噪声数据对特征选择的 tional Conference on Neural Information Processing. 影响，并且在保留了数据局部几何结构的同时又 Doha,Qatar,2012:382-389. 很好地保留了数据的全局结构。理论分析和实验 [8]周志华.机器学习[M.北京：清华大学出版社，2016： 结果均表明，与现有的特征选择方法相比，所给 1-425 出的方法具有更好的效果。 [9]LI Hao,WANG Yongli,LI Yanchao,et al.Joint local 在未来的研究中，将对所提出的框架进行扩 structure preservation and redundancy minimization for 展，以对不完整的高维数据进行特征选择，因为 unsupervised feature selection[J].Applied intelligence, 在许多实际应用中经常会发现不完整的数据集。 2020,50(12)4394-4411. [10]LIU Yanfang,YE Dongyi,LI Wenbin,et al.Robust 参考文献： neighborhood embedding for unsupervised feature selec- [1]NIE Feiping,HUANG Heng,CAI Xiao,et al.Efficient tion[J].Knowledge-based systems,2020,193:105462. and robust feature selection via joint (i-norms minimization [11]LIU Xinwang,WANG Lei,ZHANG Jian,et al.Global [Cl//Proceedings of the 23rd International Conference on and local structure preservation for feature selection[J]. Neural Information Processing Systems.Vancouver, IEEE transactions on neural networks and learning sys- Canada.2010:1813-1821. tems,2014,25(6):1083-1095. [2]ZHAO Jidong,LU Ke,HE Xiaofei.Locality sensitive [12]ROWEIS S T.SAUL L K.Nonlinear dimensionality re- semi-supervised feature selection[J].Neurocomputing, duction by locally linear embedding[J].Science,2000, 2008,71(10/12):1842-1849 290(5500):2323-2326. [3]HE Xiaofei,CAI Deng,NIYOGI P.Laplacian score for [13]HE Xiaofei,NIYOGI P.Locality preserving projections feature selection[C]//Proceedings of the 18th Internation- [C]/Proceedings of the 16th International Conference on al Conference on Neural Information Processing Systems. Neural Information Processing Systems.Whistler, Vancouver,Canada,2005:507-514. Canada,.2003:153-160. [4]HOU Chenping,NIE Feiping,LI Xuelong,et al.Joint em- [14]ZHANG Tianhao,YANG Jie,ZHAO Deli,et al.Linear bedding learning and sparse regression:a framework for local tangent space alignment and application to face re- unsupervised feature selection[J].IEEE transactions on cognition[J].Neurocomputing,2007,70(7/8/9): cybernetics,.2014,44(6):793-804 1547-1553 [5]TABAKHI S,MORADI P,AKHLAGHIAN F.An unsu- [15]ZHU Pengfei,ZUO Wangmeng,ZHANG Lei,et al.Un- pervised feature selection algorithm based on ant colony supervised feature selection by regularized self-repres- optimization[J].Engineering applications of artificial in- entation[J].Pattern recognition,2015,48(2):438-446. telligence,2014,32:112-123 [16]BELHUMEUR P N.HESPANHA J P.KRIEGMAN D
3 6 9 12 15 秩 3 6 9 12 15 秩 3 6 9 12 15 秩 低秩 满秩 低秩 满秩 (d) AR (e) USPS (f) LEAVES 0.1 0.2 0.3 0.4 0.5 0.6 ACC 0.2 0.3 0.4 0.5 0.6 0.7 0.8 ACC 0.36 0.38 0.40 0.42 0.44 0.46 0.48 ACC 低秩 满秩 图 7 FSRGR 在不同秩上的 ACC 结果 Fig. 7 ACC results of FSRGR at different number of ranks 4 结束语 L2,1 L2 L2,1 本文提出了一种新的鲁棒无监督特征选择模 型，它将特征自表达、低秩约束、图正则化以及 范数正则化项统一在同一框架中,将传统的基 于 范数的图正则化项通过特征分解改为基于 范数的正则化项，并对权重矩阵施加了一个低 秩约束。该方法能够降低噪声数据对特征选择的 影响，并且在保留了数据局部几何结构的同时又 很好地保留了数据的全局结构。理论分析和实验 结果均表明，与现有的特征选择方法相比，所给 出的方法具有更好的效果。 在未来的研究中，将对所提出的框架进行扩 展，以对不完整的高维数据进行特征选择，因为 在许多实际应用中经常会发现不完整的数据集。 参考文献： NIE Feiping, HUANG Heng, CAI Xiao, et al. Efficient and robust feature selection via joint ℓ2, 1-norms minimization [C]//Proceedings of the 23rd International Conference on Neural Information Processing Systems. Vancouver, Canada, 2010: 1813−1821. [1] ZHAO Jidong, LU Ke, HE Xiaofei. Locality sensitive semi-supervised feature selection[J]. Neurocomputing, 2008, 71(10/12): 1842–1849. [2] HE Xiaofei, CAI Deng, NIYOGI P. Laplacian score for feature selection[C]//Proceedings of the 18th International Conference on Neural Information Processing Systems. Vancouver, Canada, 2005: 507−514. [3] HOU Chenping, NIE Feiping, LI Xuelong, et al. Joint embedding learning and sparse regression: a framework for unsupervised feature selection[J]. IEEE transactions on cybernetics, 2014, 44(6): 793–804. [4] TABAKHI S, MORADI P, AKHLAGHIAN F. An unsupervised feature selection algorithm based on ant colony optimization[J]. Engineering applications of artificial intelligence, 2014, 32: 112–123. [5] CAI Deng, ZHANG Chiyuan, HE Xiaofei. Unsupervised feature selection for multi-cluster data[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington, USA, 2010: 333−342. [6] ADHIKARY J R, MURTY M N. Feature selection for unsupervised learning[C]//Proceedings of 19th International Conference on Neural Information Processing. Doha, Qatar, 2012: 382−389. [7] 周志华. 机器学习 [M]. 北京: 清华大学出版社, 2016: 1−425. [8] LI Hao, WANG Yongli, LI Yanchao, et al. Joint local structure preservation and redundancy minimization for unsupervised feature selection[J]. Applied intelligence, 2020, 50(12): 4394–4411. [9] LIU Yanfang, YE Dongyi, LI Wenbin, et al. Robust neighborhood embedding for unsupervised feature selection[J]. Knowledge-based systems, 2020, 193: 105462. [10] LIU Xinwang, WANG Lei, ZHANG Jian, et al. Global and local structure preservation for feature selection[J]. IEEE transactions on neural networks and learning systems, 2014, 25(6): 1083–1095. [11] ROWEIS S T, SAUL L K. Nonlinear dimensionality reduction by locally linear embedding[J]. Science, 2000, 290(5500): 2323–2326. [12] HE Xiaofei, NIYOGI P. Locality preserving projections [C]//Proceedings of the 16th International Conference on Neural Information Processing Systems. Whistler, Canada, 2003: 153−160. [13] ZHANG Tianhao, YANG Jie, ZHAO Deli, et al. Linear local tangent space alignment and application to face recognition[J]. Neurocomputing, 2007, 70(7/8/9): 1547–1553. [14] ZHU Pengfei, ZUO Wangmeng, ZHANG Lei, et al. Unsupervised feature selection by regularized self-representation[J]. Pattern recognition, 2015, 48(2): 438–446. [15] [16] BELHUMEUR P N, HESPANHA J P, KRIEGMAN D 第 2 期 陈彤，等：特征自表达和图正则化的鲁棒无监督特征选择 ·293·
·294· 智能系统学报 第17卷 J.Eigenfaces vs.Fisherfaces:recognition using class [23]NIE Feiping,ZHU Wei,LI Xuelong.Unsupervised fea- specific linear projection[].IEEE transactions on pat- ture selection with structured graph optimization[C]// tern analysis and machine intelligence,1997,19(7): Proceedings of the Thirtieth AAAl Conference on Artifi- 711-720. cial Intelligence.Phoenix,Arizona,2016:1302-1308. [17]SAMARIA F S.HARTER A C.Parameterisation of a stochastic model for human face identification[C]//Pro- [24]TANG Chang,ZHU Xinzhong,CHEN Jiajia,et al.Ro- ceedings of 1994 IEEE Workshop on Applications of bust graph regularized unsupervised feature selection[J]. Computer Vision.Sarasota,USA,1994:138-142 Expert systems with applications,2018,96:64-76. [18]NIE Feiping,HUANG Heng.Subspace clustering via [25]TANG Chang,BIAN Meiru,LIU Xinwang,et al.Unsu- new low-rank model with discrete group structure con- pervised feature selection via latent representation learn- straint[C]//Proceedings of the Twenty-Fifth Internation- ing and manifold regularization[J].Neural networks. al Joint Conference on Artificial Intelligence.New York, 2019,117:163-178. USA,2016. [19]MARTINEZ A M,BENAVENTE R.The AR face data- 作者简介： base:CVC Technical Report #24[R].Barcelona,Com- 陈彤，女，硕士研究生，主要研究 puter Vision Center,1998. 方向为数字图像处理和模式识别。 [20]HULL J J.A database for handwritten text recognition research[J].IEEE transactions on pattern analysis and machine intelligence,1994,16(5):550-554 [21]DU Jixiang,WANG Xiaofeng,ZHANG Guojun.Leaf shape based plant species recognition[J].Applied math- ematics and computation,2007,185(2):883-893. 陈秀宏，男，教授，博士后，主要研 [22]LI Zechao,YANG Yi,LIU Jing,et al.Unsupervised fea- 究方向为数字图像处理和模式识别 优化理论与方法。发表学术论文 ture selection using nonnegative spectral analysis[C// 120余篇。 Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence.Toronto,Canada,2012:1026- 1032
J. Eigenfaces vs. Fisherfaces: recognition using class specific linear projection[J]. IEEE transactions on pattern analysis and machine intelligence, 1997, 19(7): 711–720. SAMARIA F S, HARTER A C. Parameterisation of a stochastic model for human face identification[C]//Proceedings of 1994 IEEE Workshop on Applications of Computer Vision. Sarasota, USA, 1994: 138−142. [17] NIE Feiping, HUANG Heng. Subspace clustering via new low-rank model with discrete group structure constraint[C]//Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. New York, USA, 2016. [18] MARTÍNEZ A M, BENAVENTE R. The AR face database: CVC Technical Report #24[R]. Barcelona, Computer Vision Center, 1998. [19] HULL J J. A database for handwritten text recognition research[J]. IEEE transactions on pattern analysis and machine intelligence, 1994, 16(5): 550–554. [20] DU Jixiang, WANG Xiaofeng, ZHANG Guojun. Leaf shape based plant species recognition[J]. Applied mathematics and computation, 2007, 185(2): 883–893. [21] LI Zechao, YANG Yi, LIU Jing, et al. Unsupervised feature selection using nonnegative spectral analysis[C]// Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence. Toronto, Canada, 2012: 1026− 1032. [22] NIE Feiping, ZHU Wei, LI Xuelong. Unsupervised feature selection with structured graph optimization[C]// Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence. Phoenix, Arizona, 2016: 1302−1308. [23] TANG Chang, ZHU Xinzhong, CHEN Jiajia, et al. Robust graph regularized unsupervised feature selection[J]. Expert systems with applications, 2018, 96: 64–76. [24] TANG Chang, BIAN Meiru, LIU Xinwang, et al. Unsupervised feature selection via latent representation learning and manifold regularization[J]. Neural networks, 2019, 117: 163–178. [25] 作者简介： 陈彤，女，硕士研究生，主要研究 方向为数字图像处理和模式识别。 陈秀宏，男，教授，博士后，主要研 究方向为数字图像处理和模式识别、 优化理论与方法。发表学术论 文 120 余篇。 ·294· 智 能 系 统 学 报 第 17 卷
