随着互联网的迅猛发展，产生了大量的高维数据，高维数据通常含有大量的冗余、噪声，会降低学习算法的性能。基于这一问题，特征选择和特征提取成为了降维的重要手段。特征提取通过将高维数据投影到低维子空间来减少数据的维度，特征选择是直接选择原始数据的特征子集作为降维后的特征。本文，从特征选择的角度展开研究。

特征选择方法包括有监督特征选择^[1]、半监督特征选择^[2]、无监督特征选择^[3-4]。有监督特征选择和半监督特征选择依赖于数据的标签信息，然而在实际应用中，类别标注的成本过高。因此，这就要求应用无监督特征选择方法选择更具价值的特征。常见的无监督特征选择方法可以分为了三类：过滤法^[3]、包裹法^[5]和嵌入法^[6]。过滤式特征选择方法独立于具体的学习算法，运算效率较高。它的主要思想是对每一维特征赋予权重，所得到的权重就代表着该特征的重要性，然后依据权重进行排序，把重要性相对较小的特征过滤掉，将重要性较大的特征作为原始数据的表示。例如，最大方差法^[7]以数据方差作为评价标准，将特征按重要性排序进行选择。除此之外，拉普拉斯评分法^[3](LapScore)也是常见的无监督的过滤式特征选择方法。包裹式特征选择方法从初始特征集合中不断地选择特征子集，训练学习器，根据学习器的性能进行评价，直到选择出最佳的子集。LVW(Las Vegas Wrapper)^[8]是一个典型的包裹式特征选择方法，它在拉斯维加斯(Las Vegas method)框架下使用随机策略来进行子集搜索，并以最终分类器的误差作为特征子集评级准则。嵌入式特征选择在学习器训练过程中自动地进行特征选择，其分类效果通常较好，同时该类方法可以实现对多个特征的选择。嵌入式选择最常用的是L₁正则化和L₂正则化^[6]，当正则化项增大到一定程度时，所有的特征系数都会趋于0，在这个过程中，会有一部分特征的系数先变为0，也就实现了特征选择过程。除此之外，近年来又研究出了更加有效且高效的无监督特征选择方法，例如Li等^[9]将局部几何一致性和冗余最小化结合到同一框架中，利用局部几何结构的一致性来提高聚类精度，并在此过程中进行特征选择。Liu等^[10]提出了一种嵌入式无监督特征选择方法，该方法通过局部线性嵌入(locally linear embedding, LLE)算法得到特征权重矩阵，并使用L₁-范数来描述重构误差最下化。大量的实验结果证明，以上这些方法均是有效的。

对于特征选择来说，保持局部几何数据结构显然比保持全局结构更为重要^[11]。最常用的局部几何结构保持方法有以下3种：基于L₂范数的局部线性嵌入(LLE)^[12]、局部保留投影(locality preserving projections, LPP)^[13]以及局部切空间对齐(local tangent space alignment, LTSA)^[14]。而传统的局部保留方法是基于 ${L_2}$ 范数，很容易受到噪声和冗余数据的影响，其次，L₂范数已经被应用于许多正则化项中，这使得传统方法对离群值十分敏感，导致特征选择效果不理想。

基于以上提出的问题，本文通过特征自表达、图正则化以及低秩约束，提出了一个鲁棒无监督特征选择模型，同时保留了数据的局部几何结构和全局结构。并在6个公开数据集上进行实验，且与5个对比算法进行对比，证明了该模型的有效性。

1.   相关工作

1.1   符号元素定义

对于任意矩阵 ${\boldsymbol{X}} \in {{\bf{R}}^{m \times n}}$ ， ${\boldsymbol{x}}{}_{ij}$ 表示的是该矩阵第 $i$ 行第 $j$ 列的元素。 ${\rm{tr}}({\boldsymbol{X}})$ 表示矩阵 ${\boldsymbol{X}}$ 的迹， ${{\boldsymbol{X}}^{ - 1}}$ 表示矩阵 ${\boldsymbol{X}}$ 的逆。矩阵 ${\boldsymbol{X}}$ 的 ${L_{2,1}}$ 范数被定义为

矩阵 ${\boldsymbol{X}}$ 的F范数被定义为

1.2   特征自表达

特征自表达已经被广泛地应用于无监督特征选择之中。例如Zhu等^[15]提出了一种用于无监督特征选择的正则化自表达(regularized self-representation, RSR)模型。在RSR中， ${\boldsymbol{X}} = [{{\boldsymbol{x}}^1}\;{{\boldsymbol{x}}^2}\; \cdots $ $ \;{{\boldsymbol{x}}^n}] = [{{\boldsymbol{x}}_1}\;{{\boldsymbol{x}}_2}\; \cdots \;{{\boldsymbol{x}}_d}] \in {{\bf{R}}^{n \times d}}$ 表示特征矩阵，其中样本数和特征数分别是n和d， ${\boldsymbol{X}}$ 的每一行代表一个样本，每一列代表一个特征维度。样本的特征自表达定义为

式中：权重矩阵 ${\boldsymbol{W}} \in {{\bf{R}}^{d \times d}}$ 的元素 ${{\boldsymbol{w}}_{ji}}$ 表示第i个特征 ${{\boldsymbol{x}}_i}$ 和第j个特征 ${{\boldsymbol{x}}_j}$ 之间的权重。在式(1)中，每一个特征的特征表示项都是由其余重要的特征组成的，而不重要的特征应该从特征表示项中移除。

特征表示系数可通过以下模型来求解

式中： $\lambda $ 为一个平衡参数，基于 ${L_{2,1}}$ 范数的正则化项可得到行稀疏的权重矩阵 ${\boldsymbol{W}}$ ，从而实现特征选择。

从式(1)、(2)可以看出，所有训练样本的每一个特征(即式(1)左侧的 ${{\boldsymbol{x}}_i}$ )都是由其他特征的线性组合所表示的，相应的权重向量是式(2)中 ${\boldsymbol{W}}$ 的第i列 ${w_i}$ 。显然， ${w_i}$ 中的值越大，其对应的特征在 ${{\boldsymbol{x}}_{\boldsymbol{i}}}$ 的表示中所占的比重越多。除此之外，如果 ${\boldsymbol{W}}$ 的某一行的元素全为0，则相应的特征不出现在特征自表达中，即所有参与特征自表达的特征应该是重要的，而那些不重要的特征将通过 ${\left\| {\boldsymbol{W}} \right\|_{2,1}}$ 来去除。

1.3   局部保留投影(LPP)

局部保留投影(LPP)^[13]通过获得线性投影来最优地保持数据的邻域结构，即样本之间的某种非线性关系在降维后仍然保留着这种关系。假设 ${\boldsymbol{W}}$ 是将样本数据投影到子空间的投影矩阵，则可以通过优化以下目标函数得到 ${\boldsymbol{W}}$ 的最优解：

式中： ${\boldsymbol{W}}$ 是投影矩阵； ${\boldsymbol{s}}$ 是相似矩阵，关于 ${\boldsymbol{s}}$ 的元素定义如下：

${N_k}({{\boldsymbol{x}}^j})$ 是 ${{\boldsymbol{x}}^i}$ 的k个近邻的集合， $\sigma $ 是宽度参数。

2.   基于特征自表达和图正则化模型

2.1   模型建立

为了给出基于特征自表达的鲁棒联合图正则化无监督特征选择(feature self-representation and graph regularization, FSRGR)模型，首先引入以下图正则化特征自表达无监督特征选择一般模型：

式中： ${\rm{\varphi }}({\boldsymbol{W}})$ 是图正则化项，用于保留数据的局部几何结构。 $\lambda $ 和 $\beta $ 是用于平衡 ${L_{2,1}}$ 范数和正则化项的两个参数。

2.1.1   基于 ${L_2}$ 范数图正则化项的无监督特征选择

局部线性嵌入(LLE)^[12]、局部保留投影(LPP)^[13]和局部切线空间对齐(LTSA)^[14]等均是基于 ${L_2}$ 范数的图正则化方法。将LPP思想应用于模型(5)中，则可得到以下模型：

式(6)也可以表示为

式中： ${\boldsymbol{L}}$ 是一个拉普拉斯矩阵，且 ${\boldsymbol{L}} = {\boldsymbol{D}} - {\boldsymbol{S}}$ ， ${\boldsymbol{D}}$ 是一个对角矩阵，其对角元素为 ${D_{ii}} = {\displaystyle\sum\limits_{j = 1}^{n} } {{{\boldsymbol{s}}_{ij}}}$ ， ${\boldsymbol{S}}$ 由式(4)定义。

2.1.2   基于 ${L_{2,1}}$ 范数图正则化项的无监督特征选择

在式(7)中，最后一项图正则化项用于保留数据的局部几何结构，然而，基于 ${L_2}$ 范数的正则化函数容易受到噪声数据的影响。为减少噪声的影响，下面介绍一种基于 ${L_{2,1}}$ 范数的图正则化方法，使得模型对噪声数据更加鲁棒。

由于拉普拉斯矩阵 ${\boldsymbol{L}}$ 是实对称的，故设矩阵 ${\boldsymbol{L}}$ 特征分解为

于是，式(7)中的图正则化项可以改写为

其中 ${\boldsymbol{G}} = {{\boldsymbol{V}}^{\frac{1}{2}}}{{\boldsymbol{U}}^{\rm{T}}}{\boldsymbol{X}}$ 。为了使模型对噪声数据更加鲁棒，使用 ${L_{2,1}}$ 范数代替F范数，可以得到基于 ${L_{2,1}}$ 范数的图正则化项：

于是式(7)可改写为

2.1.3   目标函数

式(11)通过特征自表达和图正则化来保留数据的局部几何结构，但该模型却缺少了全局结构信息，无法准确地捕捉特征的全局结构信息。因此本文采用低秩约束来保留数据的全局结构。区别于传统的特征自表达，此处将特征自表达以及图正则化项与低秩约束相结合，分别考虑了局部特征相关性和全局特征相关性，从而得到局部特征自表达和全局特征自表达。具体来说，就是对 ${\boldsymbol{W}}$ 施加一个低秩假设，即 ${\boldsymbol{W}} = {\boldsymbol{AB}}$ ，所得目标函数为

式中： ${\boldsymbol{A}} \in {{\bf{R}}^{d \times k}}$ 为投影矩阵； ${\boldsymbol{B}} \in {{\bf{R}}^{k \times d}}$ 为恢复矩阵。 $\lambda $ 和 $\beta $ 均是平衡参数。

该模型利用特征自表达保留了特征的局部结构，并采用了低秩约束(即用A和B代替W)来保留样本以及特征的全局结构。此外，对传统LPP模型中的拉普拉斯矩阵进行特征分解，建立基于 ${L_{2,1}}$ 范数的图正则化项，增强其鲁棒性和稀疏性，并保留了数据的局部几何结构。

2.2   优化算法

虽然式(12)中的目标函数是凸的，但很难联合地求解所有变量。这里使用交替迭代优化策略去优化它，即交替地迭代每一个变量，直至算法收敛。

首先，式(12)可以改写为

式中： ${\boldsymbol{P}}$ 为对角矩阵，将其第i个对角元素定义为

${\boldsymbol{D}}$ 为对角矩阵，其第i个对角元素定义为

式中： ${({\boldsymbol{AB}})^i}$ 是矩阵 ${\boldsymbol{AB}}$ 的第i行； ${({\boldsymbol{GAB}})^i}$ 是矩阵 ${\boldsymbol{GAB}}$ 的第i行。

对式(13)中目标函数关于 ${\boldsymbol{B}}$ 求导数并设令其等于0，可以得到：

其中， ${{\boldsymbol{S}}_1} = {{\boldsymbol{X}}^{\rm{T}}}{\boldsymbol{X}} + \lambda {\boldsymbol{P}} + \beta {{\boldsymbol{G}}^{\rm{T}}}{\boldsymbol{DG}}$ 。

将式(16)代入到式(13)中，式(13)可以变为以下形式：

它等价于以下问题：

其中 ${{\boldsymbol{S}}_2} = {{\boldsymbol{X}}^{\rm{T}}}{\boldsymbol{X}}{{\boldsymbol{X}}^{\rm{T}}}{\boldsymbol{X}}$ 。

对式(18)关于A求导并令其等于零可得：

如设广义特征方程 ${{\boldsymbol{S}}_2}{\boldsymbol{a}} = \lambda {{\boldsymbol{S}}_1}{\boldsymbol{a}}$ 的前k个最大特征值分别为 ${\lambda _1},{\lambda _2}, \cdots ,{\lambda _k}$ ，对应的特征向量分别为 ${{\boldsymbol{a}}_1}, {{\boldsymbol{a}}_2}, \cdots ,{{\boldsymbol{a}}_k}$ ，并令 ${\boldsymbol{A}} = [{{\boldsymbol{a}}_1}\; {{\boldsymbol{a}}_2}\; \cdots \;{{\boldsymbol{a}}_k}]$ ，则有

此时，式(18)中 ${\rm{tr}}({({{\boldsymbol{A}}^{\rm{T}}}{{\boldsymbol{S}}_1}{\boldsymbol{A}})^{ - 1}}{{\boldsymbol{A}}^{\rm{T}}}{{\boldsymbol{S}}_2}{\boldsymbol{A}})$ 达到最大。

这样，通过求解式(18)得到 ${\boldsymbol{A}}$ ，再式(16)得到 ${\boldsymbol{B}}$ 。此过程可迭代进行，直到终止条件满足。算法给出了更新 ${\boldsymbol{A}}$ 和 ${\boldsymbol{B}}$ 的具体步骤。

算法　FSRGR

输入　数据矩阵 ${\boldsymbol{X}} \in {{\bf{R}}^{n \times d}}$ ， ${\boldsymbol{L}} \in {{\bf{R}}^{n \times n}}$ ,k, $\lambda $ , $\beta $ 。

输出　 ${\boldsymbol{A}} \in {{\bf{R}}^{d \times k}}$ ，计算 ${\left\| {{{\boldsymbol{A}}^i}} \right\|_2}(i = 1,2, \cdots ,d)$ 并按照降序排列，然后从X中选择与前k个最大值所对应的特征。

对L进行特征分解： ${\boldsymbol{L}} = {\boldsymbol{UV}}{{\boldsymbol{U}}^{\rm{T}}}$ ;

计算G： ${\boldsymbol{G}} = {{\boldsymbol{V}}^{\frac{1}{2}}}{{\boldsymbol{U}}^{\rm{T}}}{\boldsymbol{X}}$ ;

初始化：对角矩阵 ${\boldsymbol{P}} = {\boldsymbol{I}} \in {{\bf{R}}^{d \times d}},{\boldsymbol{D}} = {\boldsymbol{I}} \in {{\bf{R}}^{n \times n}}$ ，投影矩阵A,恢复矩阵B,迭代次数t=0。

重复：

1) 求解问题(18)更新 ${\boldsymbol{A}}$ ;

2) 根据式(16)更新 ${\boldsymbol{B}}$ ;

3) 根据式(14)更新 ${\boldsymbol{P}} = \dfrac{{\rm{1}}}{{{\rm{2}}{{\left\| {{{({\boldsymbol{AB}})}^i}} \right\|}_2}}}$ ;

4) 根据式(15)更新 ${\boldsymbol{D}} = \dfrac{{\rm{1}}}{{{\rm{2}}{{\left\| {{{({\boldsymbol{GAB}})}^i}} \right\|}_2}}}$ ;

5) $t = t + 1$ ;

直到收敛。

2.3   复杂度分析

在每次迭代中，FSRGR算法的时间主要花费在式(10)中 ${{\boldsymbol{X}}^{\rm{T}}}{\boldsymbol{X}} + \lambda {\boldsymbol{P}} + \beta {{\boldsymbol{G}}^{\rm{T}}}{\boldsymbol{DG}}$ 和 ${({{\boldsymbol{A}}^{\rm{T}}}{{\boldsymbol{S}}_1}{\boldsymbol{A}})^{ - 1}}{{\boldsymbol{A}}^{\rm{T}}}{{\boldsymbol{X}}^{\rm{T}}}{\boldsymbol{X}}$ 以及特征分解的计算上，相应的复杂度为max{O(n²d),O(nd²)}，O(nd²)及O(n³)，其中n和d代表样本数及特征数。在本次实验中，所提出的算法一般在10次迭代内收敛，所以算法的时间复杂度为max{O(n²d),O(nd²), O(n³)}。

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  部分数据集的图片

Fig.  1  Visualization of some data sets with different noise

下载: 全尺寸图片

3.2   对比算法

为了验证所研究算法的有效性，考虑以下对比方法：

1) NDFS^[22]：联合学习数据的局部几何结构和基于 ${L_{2,1}}$ 范数正则化项的稀疏线性回归。

2) JELSR^[4]：同时考虑了拉普拉斯正则化器和权重矩阵对特征的得分进行了排序。

3) SOGFS^[23]：从低维空间中学习样本的全局结构来选择重要特征。

4) L1-UFS^[24]：将特征自表达以及基于L₁范数的图拉普拉斯正则化融入到同一框架中。

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中可以看出，同其他5个对比算法相比，FSRGR算法对于图像的重构效果更好。而在6种算法中，JELSR算法的重构效果最差，可以明显看出，随着所选特征数量的增加，该算法所选择的特征均为不重要的面部特征，而重要的人脸的五官特征并没有被选择。

图  2  不同算法对部分AR数据集的重构图像

Fig.  2  Reconstructed images of partial AR data sets by different algorithms

下载: 全尺寸图片

3.4   分类精度和聚类精度

将在不同数据集上比较FSRGR算法同其他5种对比算法，分别评估它们的聚类及分类性能。具体的结果见图3和图4。其中图3展示了所有算法在6个数据集上关于分类精度的对比结果。如图3所示，其横轴表示所选择的特征数，纵轴代表不同的特征数所对应的分类精度(ACC)。由于不同数据集的特征数通常是不相同的，因此对于YALE、ORL、AR和LEAVES数据集，我们所选择的特征数的范围为 $\{ 50,100,150,200, 250, $ $ 300\}$ ，而对于MSRA及USPS数据集，将所选择的特征数的范围设置为 $ \left\{20, 40, 60, 80, 100, 120\right\}$ 。并且对于每一个算法，为了呈现出最真实的比较结果，均将其参数调至为最佳参数，即所呈现出的实验结果均为其最好的结果。首先从图3可以看出，在大多数情况下，本文所提出的FSRGR算法均优于其他对比算法。尤其在AR数据集上，相比其他5种对比算法，FSRGR所取得的分类效果明显更加优越。还可以看出，在5种对比算法中，分类性能最好的是LRLMR算法，分类效果最差的是NDFS算法。其次，图4比较了FSRGR算法同其他对比算法在不同数据集上的聚类性能。从图中可以看出，随着所选特征数的增加，通过FSRGR算法所得到的聚类效果可以稳定地优于其他对比算法。这是因为本文所提出的方法既保留了数据的局部几何结构，又保留了数据的全局结构，并且通过对权重矩阵施加低秩约束，使得所学习到的投影向量的数量不受限制，从而可以得到足够多的投影向量。

图  3  6种算法在6种数据集上的分类精度

Fig.  3  Classification accuracies of six methods on six data sets

下载: 全尺寸图片

图  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算法对于不同的数据集，运行时间并不稳定。

3.6   收敛性分析

通过计算不同迭代次数对应的目标函数值来观察FSRGR算法的收敛曲线。并且最大迭代次数设置为10。由于FSRGR算法在不同的数据集上有相似的收敛性，因此在收敛性分析的部分只展示了在YALE数据集上的实验结果。从图5中可以发现：1)所提出的算法优化了式(12)所提出的目标函数，单调地减少了目标函数值直至算法收敛。2)所提出的算法需要经过数次迭代来有效地达到收敛。

3.7   参数设置

重点研究参数 $\beta $ 和 $\lambda $ 的取值对于聚类精度的影响。首先参数 $\beta $ 是用于平衡 $\left\| {{\boldsymbol{X}} - {\boldsymbol{XAB}}} \right\|_F^2$ 和 ${\left\| {{\boldsymbol{GAB}}} \right\|_{2,1}}$ ，其次是参数 $\lambda $ ，用于控制 ${\boldsymbol{AB}}$ 的稀疏性。并且这两个参数的取值范围均被设置为 ${\rm{\{ 1}}{{\rm{0}}^{{\rm{ - 6}}}},{\rm{1}}{{\rm{0}}^{{\rm{ - 4}}}}, $ $ {\rm{1}}{{\rm{0}}^{{\rm{ - 2}}}},{\rm{1}},{\rm{1}}{{\rm{0}}^{\rm{2}}},{\rm{1}}{{\rm{0}}^{\rm{4}}},{10^6}\}$ 。实验采用了K-means算法，呈现出了不同的参数组合在不同的数据集上对于聚类精度的影响。具体的实验结果见图6。

从图6可以看出，本文所提出的方法对参数的设置较为敏感，不同的参数组合具有不同的聚类结果。举例说明，对于人脸数据集YALE,当 $\lambda = {\rm{1}}{{\rm{0}}^{{\rm{ - 2}}}},\beta = 1{0^{ - 6}}$ 时，FSRGR的聚类精度达到了36.89%的最好效果；而对于手写字数据集USPS，当 $\lambda = {\rm{1}}{{\rm{0}}^{\rm{4}}},\beta = 1{0^{ - 4}}$ 时，FSRGR的聚类精度达到了57.70%的最好效果。

图  5  FSRGR在YALE数据集上的收敛性

Fig.  5  Convergence of FSRGR on YALE data sets

下载: 全尺寸图片

3.8   低秩约束的影响

式(12)中不同秩( $ k\in \left\{3，6，9，12，15\right\}$ )在数据集AR、ISOLET、PIE、LUNG、USPS、YALE上对聚类精度的影响。图7中给出了FSRGR在不同数据集上满秩和低秩下的聚类精度。其中横轴代表所选定的秩的范围，纵轴代表不同的秩所对应的分类精度。

从图7中可以观察到，低秩约束下的聚类性能在大多数情况下都优于满秩。例如，在数据集AR和USPS上，同全秩的情况下相比，低秩约束下所得到的平均分类精度分别高出了12.43%和17.88%。这说明在特征选择中，对高维数据进行低秩约束是有效的。

图  6  不同 $\beta $ 和 $\lambda $ 组合下的FSRGR聚类精度

Fig.  6  Clustering accuracy of FSRGR algorithm with different combination of $\beta $ and $\lambda $

下载: 全尺寸图片

图  7  FSRGR在不同秩上的ACC结果

Fig.  7  ACC results of FSRGR at different number of ranks

下载: 全尺寸图片

4.   结束语

本文提出了一种新的鲁棒无监督特征选择模型，它将特征自表达、低秩约束、图正则化以及 ${L_{2,1}}$ 范数正则化项统一在同一框架中,将传统的基于 ${L_2}$ 范数的图正则化项通过特征分解改为基于 ${L_{2,1}}$ 范数的正则化项，并对权重矩阵施加了一个低秩约束。该方法能够降低噪声数据对特征选择的影响，并且在保留了数据局部几何结构的同时又很好地保留了数据的全局结构。理论分析和实验结果均表明，与现有的特征选择方法相比，所给出的方法具有更好的效果。

在未来的研究中，将对所提出的框架进行扩展，以对不完整的高维数据进行特征选择，因为在许多实际应用中经常会发现不完整的数据集。