基于稀疏自表示及流形正则化的无监督特征选择

Unsupervised Feature Selection Based on Sparse Self-representation with Manifold Regularization

摘要

基于自表示的无监督特征选择能够处理未标记数据且不受伪标签影响.为了令此类方法同时具有良好的鲁棒性、保留样本局部结构、能选出最具代表性的特征,提出了一种新的方法,并设计了一个对应的迭代优化算法来计算其目标函数.该方法先对样本异常值进行识别和处理,然后将传统的自表示模型与非凸稀疏约束和流形正则结合形成目标模型,再将预处理后的数据放入模型进行特征选择,最后使用所选特征进行聚类.将所提方法在9个真实数据集上与7种方法进行对比实验,实验结果表明,所提方法可以有效解决无监督特征选择问题.

Abstract

Self‑representation based unsupervised feature selection can handle unlabeled data without being affected by pseudo‑labeling. To ensure that such methods simultaneously achieve good robustness， preserve the local structure of samples， and select the most representative features， a new approach is proposed， and a corresponding iterative optimization algorithm is designed to compute its objective function. The method first identifies and processes outliers of samples， then combines the traditional self‑representation model with non‑convex sparse constraint and manifold regularization to form the target model， and puts the preprocessed data into the model for feature selection. Finally， the method uses the selected features for clustering. The proposed method is compared with seven methods on nine real data sets for experiments， and the experimental results show that the proposed method can effectively solve the unsupervised feature selection problem.

Graphical abstract

关键词

无监督特征选择 / 自表示 / 鲁棒 / 稀疏 / 流形正则化

Key words

unsupervised feature selection / self‑representation / robust / sparse / manifold regularization

在机器学习、数据挖掘等领域，特征选择有助于减少维数诅咒的影响，提高预测性能.根据数据是否被标记，特征选择方法分为有监督的、半监督的和无监督的^［1］.数据标签在现实中通常不可用或成本较高，因此没有先验知识也表现较好的无监督特征选择（unsupervised feature selection，UFS）得到了广泛关注.

就选择策略而言，特征选择方法可分成3种类型：过滤式^［2-5］、包裹式^［6］和嵌入式^［7-9］.嵌入式算法结合了前两种方法的优点，在一定程度上统一了特征选择和学习算法，可以获得更好的结果.GSR_SFS（graph self‑representation sparse feature selection）^［7］将子空间学习与稀疏的特征级自表示（self‑representation，SR）方法相结合，使特征选择过程更稳定并获得更好的解释能力.SOCFS（structured optimal graph feature selection）^［8］在进行特征选择和局部结构学习时自适应地确定相似性矩阵，并使用l_{\mathrm{2,1}}范数来实现稀疏性.在UFS领域的嵌入式方法中，有专注于数据全局结构的^［9］，但大多数方法都会关注数据的局部几何结构，该结构在无监督情况下已被证明比全局结构更关键^［10］.

根据使用的基本模型，UFS的嵌入式方法可以分为两类^［11］.一类是基于回归的模型，其本质上是通过学习样本的伪标签将UFS转变为有监督的特征选择，如SCFS（subspace clustering unsupervised feature selection）^［12］在一个集成的框架中应用子空间学习、聚类分析和稀疏学习，采用矩阵分解得到聚类标签矩阵，并利用回归模型优化系数矩阵选择最重要的特征.另一类是基于表示学习的模型，其核心思想是学习数据的低维表征，为特定的任务（如分类）保留最重要的信息，可以避免不准确的伪标签导致选择的特征不可靠^［11］.

作为表示学习的一个特例，基于SR的UFS方法利用原始数据固有的自我表示特性，对高维无标签数据进行降维. RSR（regularized self‐representation）^［13］是这类方法中的代表之一，它为了选择更具代表性的特征并提高算法的鲁棒性，对误差函数和稀疏项同时使用l_{\mathrm{2,1}}范数.近些年基于RSR提出了各种改进算法. NOVRSR（non‐convex regularized self‑representation）^［14］相较于RSR使用了效果更好的l_{\mathrm{2,1}-\mathrm{2}}范数^［15］作为稀疏项，并验证了其有效性，但该方法没有考虑到样本原有的结构信息.基于NOVRSR，本文提出了一种新的方法SSRMR（sparse self‑representation with manifold regularization），并设计了对应的算法.

SSRMR同时利用了l_{\mathrm{2,1}-\mathrm{2}}稀疏约束和数据的流形结构信息，在获得稀疏解的同时，更加充分利用数据的局部结构信息来提高准确率，选出最具有代表性的特征.此外，为了提升算法鲁棒性，所提方法对原始数据中的异常值进行了识别处理，以获得更好的结果.本文的主要工作：①提出了一个基于SR模型的UFS方法SSRMR.其使用l_{\mathrm{2,1}-\mathrm{2}}范数进行稀疏约束，并使用流形正则化保留原始样本结构以提升准确率；②对原始数据中的异常值进行识别处理；③设计了对应的优化迭代算法计算目标函数.

1 相关工作

1.1 特征自表示

对象具有自相似性的特点，即SR属性，比如数据的每个特征都可以由其他特征表示^［13］.设\{{\mathit{f}}_{\mathrm{1}},{\mathit{f}}_{\mathrm{2}},\dots ,{\mathit{f}}_d\}是特征集合，并且假设特征{\mathit{f}}_i和{\mathit{f}}_j是相互依赖的且可以表示为其他特征的线性组合.在此基础上，SR模型的定义如下：

\left.\begin{array}{c}{\mathit{f}}_{\mathrm{1}}=w_{\mathrm{11}}{\mathit{f}}_{\mathrm{1}}+w_{\mathrm{21}}{\mathit{f}}_{\mathrm{2}}+\dots +w_{d\mathrm{1}}{\mathit{f}}_d+{\epsilon }_{\mathrm{1}},\\ {\mathit{f}}_{\mathrm{2}}=w_{\mathrm{12}}{\mathit{f}}_{\mathrm{1}}+w_{\mathrm{22}}{\mathit{f}}_{\mathrm{2}}+\dots +w_{d\mathrm{2}}{\mathit{f}}_d+{\epsilon }_{\mathrm{2}},\\ ⋮\\ {\mathit{f}}_d=w_{\mathrm{1}d}{\mathit{f}}_{\mathrm{1}}+w_{\mathrm{2}d}{\mathit{f}}_{\mathrm{2}}+\dots +w_{dd}{\mathit{f}}_d+{\epsilon }_d.\end{array}\right\}（1）

其中：w_{ij}是特征表示系数；{\epsilon }_j\in {\mathbf{R}}^n是误差.

1.2 流形正则化

局部几何结构可以通过流形学习获得，它在无监督学习中起着至关重要的作用^［10］.一般来说，基于某种相似度量的无向图可以代表数据流形结构，图的顶点代表实例，边的权重是成对样本之间的相似度.可以预见的是，特征选择后的相似样本也应该有相似的对应数据.在数学上，流形正则化的应用可以表示为

\mathrm{a}\mathrm{r}\mathrm{g}\underset{\mathit{W}}{\mathrm{m}\mathrm{i}\mathrm{n}}{\displaystyle \sum _{i,j=\mathrm{1}}^n}{S}_{ij}\Vert {\mathit{x}}_i\mathit{W}-{\mathit{x}}_j\mathit{W}{\Vert }_{\mathrm{2}}^{\mathrm{2}}.（2）

其中： W 为特征系数矩阵；S_{ij}是{\mathit{x}}_i和{\mathit{x}}_j之间的相似度，可以根据各种评价指标获得.常用的相似性指标有0～1加权、高斯核、余弦相似度.通过式（2）可以看出，如果高维空间中的实例{\mathit{x}}_i和{\mathit{x}}_j是相似的，\Vert {\mathit{x}}_i\mathit{W}-{\mathit{x}}_j\mathit{W}{\Vert }_{\mathrm{2}}^{\mathrm{2}}作为嵌入样本{\mathit{x}}_i\mathit{W}和{\mathit{x}}_j\mathit{W}之间的距离应该很小，那么相似度S_{ij}的值就应该很大.这与期望的保留局部流形结构的策略是一致的.

1.3 无监督特征选择算法

谱特征选择SPEC（spectrum decomposition）^［4］是基于图谱理论提出的一个统一的特征选择框架，可同时用于有监督和无监督特征选择，该框架首先根据数据的相似集构造其图表示，然后基于构建的图谱来评估特征；拉普拉斯分数LS（Laplacian score）^［2］是SPEC的一个特例，它倾向于选择类中的特征；多聚类特征选择MCFS（multi‑cluster feature selection）^［5］首先使用图拉普拉斯算子实现低维嵌入，然后使用Lasso回归模型找到最佳特征子集；无监督判别特征选择UDFS（unsupervised discriminative feature selection）^［3］使用散度矩阵来维护数据结构，以选择最具判别力的特征子集. RSR^［13］中的每个特征都表示为其相关特征的线性组合，其目标函数的误差项和稀疏正则项都是l_{\mathrm{2,1}}范数. SCFS^［12］通过子空间学习得到相似度矩阵，再利用该矩阵和l_{\mathrm{2,1}}范数得到稀疏变换矩阵.子空间学习也是一种SR的机制，但相较于基于特征级SR的RSR，SCFS是基于样本级的重构，且SCFS在重构的低维空间中保持了聚类相似性. NOVRSR^［14］与RSR使用了一样的特征级SR，但与RSR不同的是，其误差项通过F-范数约束，其特征表示矩阵的稀疏正则采用了非凸的l_{\mathrm{2,1}-\mathrm{2}}范数.

2 SSRMR

2.1 异常值处理

为了使相似度矩阵更加准确，同时减少由粗差导致的结果偏差，基于拉依达准则，首先检查数据经过稳健标准化后的值是否超过3，根据此找到离群点.本文中，判断x_{ij}是某一变量的离群值的标准是

\frac{\left|x_{ij}-\mathrm{a}\mathrm{v}\mathrm{g}\left(\mathit{X}\right)\right|}{\mathrm{1.48}\times \mathrm{a}\mathrm{v}\mathrm{g}\left(\left|{\mathit{x}}_i-\mathrm{a}\mathrm{v}\mathrm{g}\left(\mathit{X}\right)\right|\right)}>\mathrm{3}.（3）

其中：\mathrm{a}\mathrm{v}\mathrm{g}(\cdot )表示列平均值； X 为数据矩阵.分母的系数1.48确保了这种稳健的尺度收敛于正态分布下的标准差^［16］.本文将满足上述条件的值视为缺失值，并用平均值代替，这样可以最大限度利用原始信息，同时减少异常值的影响，整体上增强了模型的鲁棒性.

2.2 目标模型

式（1）中的SR模型对应的优化问题为

\underset{\mathit{W}}{\mathrm{m}\mathrm{i}\mathrm{n}}\frac{\mathrm{1}}{\mathrm{2}}{‖\mathit{X}-\mathit{X}\mathit{W}‖}_F^{\mathrm{2}}.（4）

其中{\mathit{f}}_i的表示参数对应于{\mathit{w}}_i的值.因此，可以对 W 使用稀疏约束来提高特征选择效率.具体地说，如果{\mathit{f}}_i不重要，那么其相应的权重值将减少到0或接近0，上述目标通常由稀疏正则实现.

l_{\mathrm{2,1}-\mathrm{2}}范数相比于其他范数的优越性已经在以往的工作中^［15］得到了证明，其数学定义为

{‖\cdot ‖}_{\mathrm{2,1}-\mathrm{2}}={‖\cdot ‖}_{\mathrm{2,1}}-{‖\cdot ‖}_F.（5）

将{‖\mathit{W}‖}_{\mathrm{2,1}-\mathrm{2}}作为稀疏约束项，优化问题（4）可以化为

\underset{\mathit{W}}{\mathrm{m}\mathrm{i}\mathrm{n}}\frac{\mathrm{1}}{\mathrm{2}}{‖\mathit{X}-\mathit{X}\mathit{W}‖}_F^{\mathrm{2}}+{\lambda }_{\mathrm{1}}{‖\mathit{W}‖}_{\mathrm{2,1}-\mathrm{2}}.（6）

其中，{\lambda }_{\mathrm{1}}>\mathrm{0}是正则化参数.式（6）中的最小化问题可以评估与 W 参数相对应的特征的重要性.

考虑到样本局部结构对UFS结果的影响，本文决定使用流形正则.其通过线性代数变换后为

R_{\mathrm{L}}=\frac{\mathrm{1}}{\mathrm{2}}{\displaystyle \sum _{i,j=\mathrm{1}}^n}{S}_{ij}{‖{\mathit{x}}_i\mathit{W}-{\mathit{x}}_j\mathit{W}‖}_{\mathrm{2}}^{\mathrm{2}}=

{\displaystyle \sum _{i=\mathrm{1}}^n}\left({\mathit{x}}_i\mathit{W}\right){\left({\mathit{x}}_i\mathit{W}\right)}^{\mathrm{T}}{D}_{ii}-{\displaystyle \sum _{i,j=\mathrm{1}}^n}\left({\mathit{x}}_i\mathit{W}\right){\left({\mathit{x}}_j\mathit{W}\right)}^{\mathrm{T}}{S}_{ij}=

\mathrm{T}\mathrm{r}\left({\mathit{W}}^{\mathrm{T}}{\mathit{X}}^{\mathrm{T}}\mathit{D}\mathit{X}\mathit{W}\right)-\mathrm{T}\mathrm{r}\left({\mathit{W}}^{\mathrm{T}}{\mathit{X}}^{\mathrm{T}}\mathit{S}\mathit{X}\mathit{W}\right)=

\mathrm{T}\mathrm{r}\left({\mathit{W}}^{\mathrm{T}}{\mathit{X}}^{\mathrm{T}}\mathit{L}\mathit{X}\mathit{W}\right).（7）

其中：\mathit{S}\in {\mathbf{R}}^{n\times n}是基于余弦相似的相似性矩阵^［11］； D 是一个对角元素为D_{ii}={\displaystyle \sum _{j=\mathrm{1}}^n}{S}_{ij}的对角矩阵；\mathit{L}=\mathit{D}-\mathit{S}是拉普拉斯矩阵.将R_L与式（4）结合得到最终的优化目标模型，其中{\lambda }_{\mathrm{2}}>\mathrm{0}，是调节参数.

\underset{\mathit{W}}{\mathrm{m}\mathrm{i}\mathrm{n}}\frac{\mathrm{1}}{\mathrm{2}}{‖\mathit{X}-\mathit{X}\mathit{W}‖}_F^{\mathrm{2}}+{\lambda }_{\mathrm{1}}{‖\mathit{W}‖}_{\mathrm{2,1}-\mathrm{2}}+{\lambda }_{\mathrm{2}}\mathrm{T}\mathrm{r}({\mathit{W}}^{\mathrm{T}}{\mathit{X}}^{\mathrm{T}}\mathit{L}\mathit{X}\mathit{W}).（8）

2.3 优化算法

式（8）中的非凸目标函数很难直接求解，但代入式（5）后，可以将其转换为如下两个凸函数相减的模型：

\underset{\mathit{W}}{\mathrm{m}\mathrm{i}\mathrm{n}}\left[\frac{\mathrm{1}}{\mathrm{2}}{‖\mathit{X}-\mathit{X}\mathit{W}‖}_F^{\mathrm{2}}+{\lambda }_{\mathrm{1}}{‖\mathit{W}‖}_{\mathrm{2,1}}+\right.\left.{\lambda }_{\mathrm{2}}\stackrel{}{\underset{}{\mathrm{T}\mathrm{r}}}\left({\mathit{W}}^T{\mathit{X}}^T\mathit{L}\mathit{X}\mathit{W}\right)\right]-{\lambda }_{\mathrm{1}}{‖\mathit{W}‖}_F.（9）

这种凸函数相减函数（difference of convex functions，DC）可以通过收敛的凹凸过程^［17］（concave‑convex procedure，CCCP）来求解，下面简单介绍其步骤.设f\left(x\right)为可导的DC函数，存在凸函数a\left(x\right)和b\left(x\right)使f\left(x\right)=a\left(x\right)-b\left(x\right).目标函数为\underset{x\in {\mathbf{R}}^n}{\mathrm{m}\mathrm{i}\mathrm{n}}f\left(x\right)，其中f_i\left(x\right)\le \mathrm{0},i=\mathrm{1},\dots ,m.设b\left(x\right)是可微的，CCCP本质上是求解这样的一组迭代子问题^［18］：x^{(t+\mathrm{1})}\in \mathrm{a}\mathrm{r}\mathrm{g}\underset{x}{\mathrm{m}\mathrm{i}\mathrm{n}}a\left(x\right)-\nabla b(x^{(t)})，其中t为迭代次数.

参考上述求解过程，式（9）可被转换为如下一系列凸子问题：

{\mathit{W}}^{(t+\mathrm{1})}=\mathrm{a}\mathrm{r}\mathrm{g}\underset{{\mathit{W}}^{(t)}}{\mathrm{m}\mathrm{i}\mathrm{n}}\frac{\mathrm{1}}{\mathrm{2}}\Vert \mathit{X}-\mathit{X}{\mathit{W}}^{\left(t\right)}{\Vert }_F^{\mathrm{2}}+{\lambda }_{\mathrm{1}}\Vert {\mathit{W}}^{\left(t\right)}{\Vert }_{\mathrm{2,1}}+

{\lambda }_{\mathrm{2}}\mathrm{T}\mathrm{r}((\mathit{X}{\mathit{W}}^{\left(t\right)}{)}^{\mathrm{T}}\mathit{L}\mathit{X}{\mathit{W}}^{\left(t\right)})-{\lambda }_{\mathrm{1}}\mathrm{T}\mathrm{r}(({\mathit{W}}^{\left(t\right)}{)}^{\mathrm{T}}{\mathit{C}}^{\left(t\right)}).（10）

其中\mathit{C}=\nabla \Vert \mathit{W}{\Vert }_F=\left\{\begin{array}{cc}\Vert \mathit{W}{\Vert }_F^{-\mathrm{1}}\mathit{W},& \mathit{W}\ne \mathrm{0}\\ \mathrm{0},& \mathit{W}=\mathrm{0}\end{array}\right. .根据式（10），需要解决的问题可简化为

\underset{\mathit{W}}{\mathrm{m}\mathrm{i}\mathrm{n}}\frac{\mathrm{1}}{\mathrm{2}}\Vert \mathit{X}-\mathit{X}\mathit{W}{\Vert }_F^{\mathrm{2}}+{\lambda }_{\mathrm{1}}\Vert \mathit{W}{\Vert }_{\mathrm{2,1}}-{\lambda }_{\mathrm{1}}\mathrm{T}\mathrm{r}({\mathit{W}}^{\mathrm{T}}\mathit{C})+{\lambda }_{\mathrm{2}}\mathrm{T}\mathrm{r}\left({\mathit{W}}^{\mathrm{T}}{\mathit{X}}^{\mathrm{T}}\mathit{L}\mathit{X}\mathit{W}\right).（11）

式（11）中的优化问题是非光滑的，基于交替乘子法（alternating direction method of multipliers，ADMM）^［19］的思想提出解决该问题的算法.首先，引入辅助变量\mathit{V}=\mathit{W}，将问题（11）转化为如下等式约束优化问题：

\underset{\mathit{W},\mathit{V}}{\mathrm{m}\mathrm{i}\mathrm{n}}\frac{\mathrm{1}}{\mathrm{2}}\Vert \mathit{X}-\mathit{X}\mathit{W}{\Vert }_F^{\mathrm{2}}+{\lambda }_{\mathrm{1}}\Vert \mathit{V}{\Vert }_{\mathrm{2,1}}-{\lambda }_{\mathrm{1}}\mathrm{T}\mathrm{r}({\mathit{W}}^{\mathrm{T}}\mathit{C})+{\lambda }_{\mathrm{2}}\mathrm{T}\mathrm{r}\left({\mathit{W}}^{\mathrm{T}}{\mathit{X}}^{\mathrm{T}}\mathit{L}\mathit{X}\mathit{W}\right).（12）

\mathrm{s}.\mathrm{t}.\mathit{W}-\mathit{V}=\mathrm{0}.

构造式（12）的拉格朗日函数如下：

\mathrm{ℒ}(\mathit{W},\mathit{V})=\frac{\mathrm{1}}{\mathrm{2}}\Vert \mathit{X}-\mathit{X}\mathit{W}{\Vert }_F^{\mathrm{2}}+{\lambda }_{\mathrm{1}}\Vert \mathit{V}{\Vert }_{\mathrm{2,1}}+〈\sum ,\mathit{W}-\mathit{V}〉+\frac{{\lambda }_{\mathrm{3}}}{\mathrm{2}}\Vert \mathit{W}-\mathit{V}{\Vert }_F^{\mathrm{2}}+{\lambda }_{\mathrm{2}}\mathrm{T}\mathrm{r}({\mathbf{W}}^{\mathrm{T}}{\mathit{X}}^{\mathrm{T}}\mathit{L}\mathit{X}\mathit{W})-{\lambda }_{\mathrm{1}}\mathrm{T}\mathrm{r}({\mathit{W}}^{\mathrm{T}}\mathit{C}).（13）

其中\sum \in {\mathbf{R}}^{d\times d}是约束\mathit{W}-\mathit{V}=\mathrm{0}的拉格朗日乘子，{\lambda }_{\mathrm{3}}>\mathrm{0}是惩罚参数.根据ADMM的交替迭代原理，所提算法本质上由以下3组迭代组成：

{\mathit{W}}^{(h+\mathrm{1})}=\mathrm{a}\mathrm{r}\mathrm{g}\underset{\mathit{W}}{\mathrm{m}\mathrm{i}\mathrm{n}}\mathrm{ℒ}\left(\mathit{W},{\mathit{V}}^{(h+\mathrm{1})}\right),（14a）

{\mathit{V}}^{(h+\mathrm{1})}=\mathrm{a}\mathrm{r}\mathrm{g}\underset{\mathit{V}}{\mathrm{m}\mathrm{i}\mathrm{n}}\mathrm{ℒ}\left({\mathit{W}}^{(h+\mathrm{1})},\mathit{V}\right),（14b）

{\sum }^{(h+\mathrm{1})}={\sum }^{(h)}+{\lambda }_{\mathrm{3}}\left({\mathit{W}}^{(h+\mathrm{1})}-{\mathit{V}}^{(h+\mathrm{1})}\right).（14c）

其中h是迭代索引.

2.3.1 更新\mathit{W}

将变量\mathit{V}视为常数，式（14a）去掉与\mathit{W}无关的常数项后可简化为以下问题：

\underset{\mathit{W}}{\mathrm{m}\mathrm{i}\mathrm{n}}\frac{\mathrm{1}}{\mathrm{2}}{‖\mathit{X}-\mathit{X}\mathit{W}‖}_F^{\mathrm{2}}+〈\sum ,\mathit{W}-\mathit{V}〉+\frac{{\lambda }_{\mathrm{3}}}{\mathrm{2}}{‖\mathit{W}-\mathit{V}‖}_F^{\mathrm{2}}+{\lambda }_{\mathrm{2}}\mathrm{T}\mathrm{r}({\mathit{W}}^{\mathrm{T}}{\mathit{X}}^{\mathrm{T}}\mathit{L}\mathit{X}\mathit{W})-{\lambda }_{\mathrm{1}}\mathrm{T}\mathrm{r}({\mathit{W}}^{\mathrm{T}}\mathit{C}).（15）

利用式（15）中函数对 W 一阶求导的最优解条件，即

-{\mathit{X}}^{\mathrm{T}}\mathit{X}+{\mathit{X}}^{\mathrm{T}}\mathit{X}\mathit{W}-{\lambda }_{\mathrm{1}}\mathit{C}+\sum +{\lambda }_{\mathrm{3}}(\mathit{W}-\mathit{V})+\mathrm{2}{\lambda }_{\mathrm{2}}{\mathit{X}}^{\mathrm{T}}\mathit{L}\mathit{X}\mathit{W}=\mathrm{0}.（16）

设\mathit{B}={\mathit{X}}^{\mathrm{T}}\mathit{X}+{\lambda }_{\mathrm{1}}\mathit{C}-\sum +{\lambda }_{\mathrm{3}}\mathit{V}，代入等式（16）得到

\mathit{W}={\left({\mathit{X}}^{\mathrm{T}}\mathit{X}+\mathrm{2}{\lambda }_{\mathrm{2}}{\mathit{X}}^{\mathrm{T}}\mathit{L}\mathit{X}+{\lambda }_{\mathrm{3}}\mathit{I}\right)}^{-\mathrm{1}}\mathit{B}.（17）

其中\mathit{I}\in {\mathbf{R}}^{d\times d}是单位矩阵.

2.3.2 更新\mathit{V}

与更新\mathit{W}同理，只留下\mathit{V}的相关项后，式（14b）被简化为

\underset{\mathit{V}}{\mathrm{m}\mathrm{i}\mathrm{n}}{\lambda }_{\mathrm{1}}\Vert \mathit{V}{\Vert }_{\mathrm{2,1}}+〈\sum ,\mathit{W}-\mathit{V}〉+\frac{{\lambda }_{\mathrm{3}}}{\mathrm{2}}\Vert \mathit{W}-\mathit{V}{\Vert }_F^{\mathrm{2}}.（18）

对式（18）进行数学变换后可以得到如下等价问题：

\underset{\mathit{V}}{\mathrm{m}\mathrm{i}\mathrm{n}}\frac{{\lambda }_{\mathrm{1}}}{{\lambda }_{\mathrm{3}}}{‖\mathit{V}‖}_{\mathrm{2,1}}+\frac{\mathrm{1}}{\mathrm{2}}{‖\mathit{V}-\left(\mathit{W}+\frac{\sum }{{\lambda }_{\mathrm{3}}}\right)‖}_F^{\mathrm{2}}.（19）

令\mathit{M}=\mathit{W}+\frac{\sum }{{\lambda }_{\mathrm{3}}}，问题（19）可以转化为d个子问题：

\underset{{\mathit{v}}_i}{\mathrm{m}\mathrm{i}\mathrm{n}}{\displaystyle \sum _{i=\mathrm{1}}^d}\left(\frac{\mathrm{1}}{\mathrm{2}}\Vert {\mathit{v}}_i-{\mathit{m}}_i{\Vert }_{\mathrm{2}}^{\mathrm{2}}+\frac{{\lambda }_{\mathrm{1}}}{{\lambda }_{\mathrm{3}}}\Vert {\mathit{v}}_i{\Vert }_{\mathrm{2}}\right).（20）

基于已有工作^［15］可知，问题（20）的最优解为

（21）

2.3.3 算 法

\mathit{W}和\mathit{V}每次迭代使用上述更新规则，所提算法如下.

算法1 SSRMR算法

输入：原始数据\mathit{X}，拉普拉斯矩阵\mathit{L}，调节参数{\lambda }_{\mathrm{1}}>\mathrm{0},{\lambda }_{\mathrm{2}}>\mathrm{0},{\lambda }_{\mathrm{3}}>\mathrm{0}；

输出：特征表示矩阵最优解{\mathit{W}}^{\mathrm{*}}；

1.初始化 {\mathit{W}}^{\mathrm{0}}=\mathrm{0},{\mathit{V}}^{\mathrm{0}}=\mathrm{0},{\sum }^{\mathrm{0}}=\mathrm{0} and t=\mathrm{0}；

2.根据式（3）识别处理 X 中的异常值；

3.While 不满足迭代停止条件do

4. 根据式（17）更新{\mathit{W}}^{(t+\mathrm{1})}；

5. 根据式（21）更新{\mathit{V}}^{(t+\mathrm{1})}；

6. 根据式（14c）更新{\sum }^{(t+\mathrm{1})}；

7. t=t+1；

8.End while

9.返回{\mathit{W}}^{\mathrm{*}}.

2.4 计算复杂度分析

设样本数为n，每个实例的特征数为d，迭代次数为t.所提出的优化方法有3个子问题，即更新\mathit{W}，更新\mathit{V}和更新\sum.求解\mathit{W}主要的计算成本是求解式（17）中的d\times d矩阵的逆，复杂度为O（d ³）.求解\mathit{V}等价于求解式（20）中的d个子问题，每个子问题的复杂度为O（n），因此在每次迭代中求解\mathit{V}的复杂度是O（nd）.很明显每次迭代求解\sum的复杂度为O（d ²）.因此所提算法的计算复杂度可粗略认为是O（td ³）.

3 实 验

3.1 实验数据集

为证明SSRMR相较于一些现有算法的优越性，本文选择在9个公开可用的数据集上进行实验验证，表1展示了这些数据集的样本大小、特征维度和实际分类数.

3.2 对比算法

为了验证所提出算法的有效性，将其与基线方法和其他7种算法进行了比较.基线方法直接使用所有数据，不进行选择特征.其他对比算法为：LS^［2］，SPEC^［4］，MCFS^［5］，UDFS^［3］，RSR^［13］，SCFS^［12］，NOVRSR^［14］.

3.3 实验设置

涉及到k最近邻算法的，根据先前的经验^［13］将k设为5.各算法中涉及到的正则项系数调整范围为\left\{{\mathrm{10}}^{-\mathrm{3}},{\mathrm{10}}^{-\mathrm{2}},{\mathrm{10}}^{-\mathrm{1}},\mathrm{1,10},{\mathrm{10}}^{\mathrm{2}},{\mathrm{10}}^{\mathrm{3}}\right\}.特征维度取值范围为\left\{\mathrm{20,40,60},\dots ,\mathrm{200}\right\}.为评估所选特征的质量，最后把不同算法选择后的特征应用到K-means聚类算法中，K-means结果受初始化影响，因此将20次实验输出的平均值作为最终结果.

实验运行的环境是Windows 11上的Python 3.9.12，计算机CPU为Intel Core i5-12400F，内存16 GB.

3.4 实验结果与分析

聚类性能通过准确率（accuracy，ACC）和归一化互信息（normal mutual information，NMI）进行评估.

图1和图2显示了NOVRSR和本文所提方法SSRMR在各个数据集上的聚类结果，X坐标轴是所选特征数量，Y坐标轴是聚类结果（ACC和NMI）.另外，为了排除参数的影响，图中所有结果对应的相关参数都设置为1.

设实例数为n.当时，预处理的作用不大；时，预处理的贡献更为显著，但效果随着所选特征数量的增加而减少；在n>\mathrm{1}\mathrm{600}的情况下，随着所选特征的增加，预处理始终发挥着重要作用，这是由于高维数据中所选特征的百分比相对较低，因此尚未达到预处理效果开始下降的阶段.此外，在Isolet数据集上，预处理的结果不佳，但如果将参数设置为与最优解相对应的参数（{\lambda }_{\mathrm{1}}=\mathrm{10},{\lambda }_{\mathrm{2}}=\mathrm{0.1},{\lambda }_{\mathrm{3}}=\mathrm{1}），如图3所示，预处理后可以得到更好的结果.总体而言，数据经过预处理后的结果更好，证明对异常数据的处理步骤是有效的.

从图1和图2中可以发现，SSRMR所选特征进行聚类的结果总体优于NOVRSR.在小样本数据集上选择少量特征时，两种方法的结果差异很大，NOVRSR因为能利用的数据信息有限而表现不佳，SSRMR考虑了数据的局部结构信息，获得了更好的结果，这表明通过流形正则化来保持样本间的局部结构是有助于特征选择的.

表2和表3展示了在不同数据集上所有算法在其最优参数下的聚类结果的平均值和标准差.其中最佳的结果用粗体标记，次佳的结果用下划线标记，括号里是所选特征的数量.通过分析表2和表3，可以得出以下结论：① SSRMR总体上优于NOVRSR.验证了保存样本间的局部结构是有助于特征选择的； ② 在大多数数据集中，SSRMR相较对比方法表现更好，证明了其有效性.在某些情况下，SSRMR的结果不是最佳的，但也和最佳结果接近.此外，SSRMR在某些情况下有显著的改善，例如在nci9上，其ACC和NMI分别比次佳的结果高6%左右，在warpPIE10P上的NMI比次佳的结果高11%； ③ 基线方法和UFS方法的比较说明了特征选择的有效性.基线方法总体表现并不差，但它需要所有原始特征，当数据的维度很高时使用此法并不是一个明智的选择.相比之下，UFS方法只需要很少的特征就可以获得类似甚至更好的结果.

表4给出了SSRMR和另外两种UFS方法（SCFS，NOVRSR）在9个数据集上的运行时间.所提算法在部分数据集上表现较好.其中，SSRMR在TOX171数据集上花费了较多时间，是受到了参数的影响，在该数据集上实际执行的迭代次数较高.相反，在nci9花费的时间非常少，是因为实际进行的迭代次数少.

3.5 参数影响分析

固定{\lambda }_{\mathrm{3}}=\mathrm{1}，讨论参数{\lambda }_{\mathrm{1}}和{\lambda }_{\mathrm{2}}以及所选特征数量K对特征选择性能的影响.

从图4~图7中可以发现，在大多数情况下，随着所选特征数量K的增加，聚类表现会更好，但在达到峰值后开始下降.这种现象是因为太少的特征不能很好地代表原始特征空间，而选择太多的特征会有冗余或不相关的特征影响结果.

显然，{\lambda }_{\mathrm{1}}和{\lambda }_{\mathrm{2}}的不同取值会产生不同的结果.当{\lambda }_{\mathrm{1}}小于或等于1时结果更好.当{\lambda }_{\mathrm{1}}太大时，会导致其调节的项（即特征自表示项）出现过拟合，影响最终结果.但总体而言，SSRMR在各数据集中对参数{\lambda }_{\mathrm{2}}更敏感.这表明，由{\lambda }_{\mathrm{2}}调节的项（用于保存数据的局部结构）发挥了有价值的作用.在DBworld，lymphoma和nci9中，由于它们的样本量小，可用的数据结构信息有限，其结果随着{\lambda }_{\mathrm{2}}的增大整体有小幅度提升.但是，对于样本数较多的数据集，随着{\lambda }_{\mathrm{2}}取值变大，ACC会出现明显的下降，这是因为{\lambda }_{\mathrm{2}}过大导致的过拟合使模型性能降低.由上述分析可知，对于大样本的数据集，需要更加注意{\lambda }_{\mathrm{2}}的取值.TOX171数据集是一个例外，首先，因为其特征数较少，{\lambda }_{\mathrm{1}}取较大值时结果会更好；其次，TOX171受{\lambda }_{\mathrm{1}}的影响明显大于{\lambda }_{\mathrm{2}}，这是因为TOX171除了特征数少，分类数也少，这使得模型中每个特征对表示参数的变化会更敏感，因此受控制特征自表示项的{\lambda }_{\mathrm{1}}的影响更大.相比而言，特征数同样不多的Isolet因为分类较多，数据局部结构信息的保持起到了更大的作用，因此在此数据集上{\lambda }_{\mathrm{1}}对结果的影响并不明显大于{\lambda }_{\mathrm{2}}.

4 结 语

本文提出了一种新的基于SR模型的UFS方法.考虑到所选特征的稀疏性，使用非凸范数作为稀疏正则项.此外，为了充分利用数据的局部结构，利用了基于样本之间余弦相似性的流形正则性约束.在模型鲁棒性增强方面，采取了对原始数据进行预处理的方法来减少粗差干扰.因为目标函数很难直接求解，本文还设计了定制的迭代算法来寻找最优解.在9个数据集上将所提方法与基线方法及其他7种特征选择方法进行了比较.实验结果表明，SSRMR在各类数据集上的表现都优于其他算法.

本文的研究也有一定局限性，使用的SR模型要求每个特征都可以用其他特征的线性组合来表示，这对真实世界的数据的适用性有限，在后续研究中将寻求具有更广泛适用性的方法模型.此外，本文使用的数据都是非张量数据，为了保持最原始的多维数据结构信息，面向张量的特征选择更有优势.最后，张量数据所需的计算资源通常较大，如何使用较低的计算成本实现也是进一步研究的方向.

参考文献

[1] Solorio‑Fernández S， Ariel J， Martínez‑Trinidad J.A review of unsupervised feature selection methods［J］.The Artificial Intelligence Review，2020，53（2）：907-948.

[2] He X F， Cai D， Niyogi P.Laplacian score for feature selection［C］// Proceedings of the 18th International Conference on Neural Information Processing Systems.Vancouver，2005：507-514.

[3] Yang Y， Shen H T， Ma Z G，et al .L 2，₁‑norm regularized discriminative feature selection for unsupervised learning［C］// Proceedings of the Twenty‑Second International Joint Conference on Artificial Intelligence-Volume Two.Menlo Park：AAAI Press，2011：1589-1594.

[4] Zhao Z， Liu H.Spectral feature selection for supervised and unsupervised learning［C］// Proceedings of the 24th International Conference on Machine Learning.Corvalis，2007：1151-1157.

[5] Cai D， Zhang C， He X F.Unsupervised feature selection for multi‑cluster data［C］// Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Washington DC，2010：333-342.

[6] 李占山，刘兆赓，俞寅，等.量子化信息素蚁群优化特征选择算法［J］.东北大学学报（自然科学版），2020，41（1）：17-22.

[7] Li Zhan‑shaan， Liu Zhao‑geng， Yu Yin，et al.A quantized pheromone ant colony optimization algorithm for feature selection［J］.Journal of Northeastern University（Natural Science），2020，41（1）：17-22.

[8] Hu R Y， Zhu X F， Cheng D B，et al.Graph self‑representation method for unsupervised feature selection［J］.Neurocomputing，2017，220：130-137.

[9] Nie F P， Zhu W， Li X L.Unsupervised feature selection with structured graph optimization［C］//Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence.Phoenix，2016：1302-1308.

[10] Lim H， Kim D.Pairwise dependence‑based unsupervised feature selection［J］.Pattern Recognition，2021，111：107663.

[11] Liu X W， Wang L， Zhang J，et al.Global and local structure preservation for feature selection［J］.IEEE Transactions on Neural Networks and Learning Systems，2013，25（6）：1083-1095.

[12] Li W Y， Chen H M， Li T R，et al.Unsupervised feature selection via self‑paced learning and low‑redundant regularization［J］.Knowledge‑Based Systems，2022，240：108150.

[13] Parsa M， Zare H， Ghatee M.Unsupervised feature selection based on adaptive similarity learning and subspace clustering［J］.Engineering Applications of Artificial Intelligence，2020，95：103855.

[14] Zhu P F， Zuo W M， Zhang L，et al.Unsupervised feature selection by regularized self‑representation［J］.Pattern Recognition，2015，48（2）：438-446.

[15] Miao J Y， Ping Y， Chen Z S，et al.Unsupervised feature selection by non‑convex regularized self‑representation［J］.Expert Systems with Applications，2021，173：114643.

[16] Shi Y， Miao J Y， Wang Z Y，et al.Feature selection with l 2,1 - 2 regularization［J］.IEEE Transactions on Neural Networks and Learning Systems，2018，29（10）：4967-4982.

[17] Bottmer L， Croux C， Wilms I.Sparse regression for large data sets with outliers［J］.European Journal of Operational Research，2022，297（2）：782-794.

[18] Yuille A L， Rangarajan A.The concave‑convex procedure［J］.Neural Computation，2003，15（4）：915-936.

[19] Sriperumbudur B， Lanckriet G.On the convergence of the concave-convex procedure［C］// Proceedings of the 22nd International Conference on Neural Information Processing Systems.Vancouver，2009：1759-1767.

[20] Boyd S， Parikh N， Chu E，et al.Distributed optimization and statistical learning via the alternating direction method of multipliers［J］.Foundations and Trends® in Machine Learning，2011，3（1）：1-122.

基金资助

国家自然科学基金资助项目(62276060)

吉林省发展和改革委员会资助项目(2019C053-9)