开放科学（资源服务）标志码（OSID）：

0 概述

特征选择作为处理高维数据分类的主要方法，在算法学习过程中不仅能够减少训练时间，而且能避免维度灾难与过拟合等问题^[1-3]，同时是近年来机器学习领域的研究热点之一。与单标签数据一样，多标签数据存在多个特征^[4]，在分类问题中同样面临维度灾难问题，但与传统单标签特征选择不同，多标签特征选择不仅要考虑样本与标签间的关系，而且要考虑标签与标签间的关系。现有多标签特征选择方法大致可分为过滤式、封装式、嵌入式^[5]等3类，其中嵌入式方法是将特征选择过程嵌入学习过程中，综合了过滤式与封装式的优势。

由于多标签分类数据的连续性与标签的离散性，因此一些学者认为多标签数据中，数据与标签的关系可以用logistic回归模型来学习，并通过不同正则项的约束来改进算法的性能，从而进行多标签特征选择。文献[6]提出一种用于多标签图像分类的相关logistic回归模型（CorrLog），将传统的logistic回归模型扩展到多标签情况。文献[7]提出混合整数优化logistic回归的特征子集选择算法，给出一个混合整数线性优化问题，使用标准的整数优化软件求解，并对logistic回归的损失函数进行分段线性逼近。文献[8]提出一种基于$ {L}_{q}\left(0 < q < 1\right) $范数正则化的稳健逻辑回归方法，这是一种可行且有效的特征选择方法。

近年来，流形学习快速发展，并逐渐渗透到人们生活以及工业生产等各个领域。为了能够学习到数据特征的基层流形结构，文献[9-10]提出流形学习方法，发现在特征选择的过程中，特征流形结构能够促使特征选择学习到更优的回归系数矩阵。文献[11]提出一个图形学习框架来保持数据的局部和全局结构，该方法利用样本的自表达性来捕获全局结构，使用自适应邻域方法来保持局部结构。文献[12]提出一种新的鲁棒图学习方法，该方法通过自适应地去除原始数据中的噪声和错误，从真实的噪声数据中学习出可靠的图。文献[13]通过数据的自表示性质构建相似矩阵，并运用流形结构和稀疏正则项来约束相似矩阵，从而构建无监督特征选择模型。文献[14]通过将其定义的代价距离代入现有的特征选择模型中，并使用流形结构约束得到一个新的代价敏感特征选择方法。文献[15]使用logistic回归模型，并利用标签流形结构与$ {L}_{1} $-范数约束回归系数矩阵，构造半监督多标签特征选择模型。可见，流形学习不一定作为正则项来约束回归系数，标签流形学习也是一种学习数据与标签间关系的方法。为找出数据与标签间的关系，准确去除不相关的特征和冗余特征，本文融合logistic回归模型学习到的系数矩阵和标签流形模型学习到的权重矩阵，基于L_2，1-范数提出一种高效的柔性结合标签流形结构与logistic回归模型的多标签特征选择算法（FSML）。

1 模型建立 1.1 logistic回归模型

假设一个多标签数据集$ D={\left\{\left({d}_{i}, {y}_{i}\right)\right\}}_{i=1}^{n} $由n个独立同分布的样本组成，令$ \boldsymbol{X}=\left[{\boldsymbol{x}}_{1};{\boldsymbol{x}}_{2};\cdots ;{\boldsymbol{x}}_{n}\right] $为数据矩阵的增广矩阵，$ \boldsymbol{X}\in {\mathbb{R}}^{n\times d} $，$ \boldsymbol{Y}=\left[{\boldsymbol{y}}_{1};{\boldsymbol{y}}_{2};\cdots ;{\boldsymbol{y}}_{n}\right] $为标签矩阵，$ \boldsymbol{Y}\in {\mathbb{R}}^{n\times m} $，其中，$ {\boldsymbol{x}}_{i}=\left[1, {d}_{i}\right] $，$ {y}_{ij} $的值为0或1，表示第i个样本是否与第j个标签相关联。在logistic回归中定义样本$ {\boldsymbol{x}}_{i} $属于第j类的后验概率如下：

$ \mathrm{P}\mathrm{r}\left(\left.{y}_{ij}=1\right|{\boldsymbol{x}}_{i}\right)=g\left({\boldsymbol{x}}_{i}{\boldsymbol{w}}_{j}\right)=\frac{\mathrm{e}\mathrm{x}\mathrm{p}\left({\boldsymbol{x}}_{i}{\boldsymbol{w}}_{j}\right)}{1+\mathrm{e}\mathrm{x}\mathrm{p}\left({\boldsymbol{x}}_{i}{\boldsymbol{w}}_{j}\right)} $

(1)

样本$ {\boldsymbol{x}}_{i} $不属于第j类的后验概率如下：

$ \mathrm{P}\mathrm{r}\left(\left.{y}_{ij}=0\right|{\boldsymbol{x}}_{i}\right)=1-g\left({\boldsymbol{x}}_{i}{\boldsymbol{w}}_{j}\right)=\frac{1}{1+\mathrm{e}\mathrm{x}\mathrm{p}\left({\boldsymbol{x}}_{i}{\boldsymbol{w}}_{j}\right)} $

(2)

其中：$ {\boldsymbol{w}}_{j} $是系数矩阵$ \boldsymbol{W}\in {\mathbb{R}}^{d\times m} $的第j列向量。

使用极大似然估计法对系数矩阵进行估计，则logistic回归关于多标签数据集的似然函数（联合概率分布）如下：

$ P\left(\boldsymbol{W}\right)=\underset{\boldsymbol{W}}{\mathrm{m}\mathrm{a}\mathrm{x}}\prod \limits_{j=1}^{m}\prod \limits_{i=1}^{n}g{\left({\boldsymbol{x}}_{i}{\boldsymbol{w}}_{j}\right)}^{{y}_{ij}}{\left[1-g\left({\boldsymbol{x}}_{i}{\boldsymbol{w}}_{j}\right)\right]}^{1-{y}_{ij}} $

(3)

由于求解式（3）较为困难，因此可以将式（3）转化为利用求解logistic回归的负对数似然函数式（4）的极小值来求解W。

$ \begin{array}{l}L\left(\boldsymbol{W}\right)=\\ -\sum\limits _{j=1}^{m}\sum\limits _{i=1}^{n}\left[{y}_{ij}\mathrm{l}\mathrm{n}\left(g\left({\boldsymbol{x}}_{i}{\boldsymbol{w}}_{j}\right)\right)+\left(1-{y}_{ij}\right)\mathrm{l}\mathrm{n}\left(1-g\left({\boldsymbol{x}}_{i}{\boldsymbol{w}}_{j}\right)\right)\right]=\\ -\sum\limits _{j=1}^{m}\sum\limits _{i=1}^{n}\left[{y}_{ij}\cdot {\boldsymbol{x}}_{i}{\boldsymbol{w}}_{j}-\mathrm{l}\mathrm{n}\left(1+g\left({\boldsymbol{x}}_{i}{\boldsymbol{w}}_{j}\right)\right)\right]\end{array} $

(4)

又因为logistic回归模型可能会出现过拟合、多重共线性、无限解等不适定问题，所以导致系数矩阵估计不正确^[16]。为了解决这一问题，一种广泛使用的策略是在式（4）中引入稀疏惩罚项，因此带有惩罚项的logistic回归模型的表达式如下：

$ \underset{\boldsymbol{W}}{\mathrm{m}\mathrm{i}\mathrm{n}}L\left(\boldsymbol{W}\right)+\frac{\beta }{2}R\left(\boldsymbol{W}\right) $

(5)

其中：$ \beta $是惩罚因子；$ R\left(\mathrm{*}\right) $是惩罚函数，表示对$ \mathrm{*} $的相应约束惩罚。

1.2 流形学习

近年来，流形学习被广泛应用于协同聚类^[17]、特征选择、维数约简^[18]等任务中。在特征选择算法中，流形学习通常是被用作正则项来约束回归系数矩阵，以便回归系数矩阵拟合数据特征的基层流形结构，但流形学习在特征选择算法中的使用方式并不局限于此。

在本文研究中，将使用流形学习来拟合数据特征的权重矩阵，为学习得到更好的特征权重矩阵并更有效地利用标签信息，进行如下假设：

1）通过学习数据间的相似矩阵Z来探究数据基层结构。例如，标签相似矩阵Z可以通过核函数学习，如式（6）所示：

$ {Z}_{ij}=\left\{\begin{array}{l}\mathrm{e}\mathrm{x}\mathrm{p}\left(-\frac{{‖{\boldsymbol{y}}_{i}-{\boldsymbol{y}}_{j}‖}_{2}^{2}}{t}\right), {\boldsymbol{y}}_{i}\subset {N}_{k}\left({\boldsymbol{y}}_{j}\right)\left|{\boldsymbol{y}}_{j}\subset {N}_{k}\left({\boldsymbol{y}}_{i}\right)\right.\\ 0, \mathrm{其}\mathrm{他}\end{array}\right. $

(6)

其中：$ {Z}_{ij} $是Z的第i行、第j列的元素，表示$ {y}_{i} $和$ {y}_{j} $之间的相似度。

2）通过学习得到标签F。因为F需要拟合原始标签Y的基层结构，所以$ \boldsymbol{F}\stackrel{\mathrm{结}\mathrm{构}\mathrm{相}\mathrm{似}\mathrm{于}}{\to }\boldsymbol{Y} $。

3）理论上认为：$ \boldsymbol{F}=\boldsymbol{X}\boldsymbol{U} $，其中$ \boldsymbol{U}\in {\mathbb{R}}^{d\times m} $是数据特征的权重矩阵。

根据以上假设构建标签流形学习模型，其表达式如下：

$ \begin{array}{l}\frac{1}{2}\sum\limits _{i=1}^{n}\sum\limits _{j=1}^{n}{‖{\boldsymbol{x}}_{i}\boldsymbol{U}-{\boldsymbol{x}}_{j}\boldsymbol{U}‖}_{2}^{2}{Z}_{ij}=\\ \sum\limits _{i=1}^{n}{\boldsymbol{x}}_{i}\boldsymbol{U}{\left({\boldsymbol{x}}_{i}\boldsymbol{U}\right)}^{T}{P}_{ii}-\sum\limits _{i=1}^{n}\sum\limits _{j=1}^{n}{\boldsymbol{x}}_{i}\boldsymbol{U}{\left({\boldsymbol{x}}_{j}\boldsymbol{U}\right)}^{\mathrm{T}}{Z}_{ij}=\\ \mathrm{T}\mathrm{r}\left({\boldsymbol{U}}^{\mathrm{T}}{\boldsymbol{X}}^{\mathrm{T}}\left(\boldsymbol{P}-\boldsymbol{Z}\right)\boldsymbol{X}\boldsymbol{U}\right)=\\ \mathrm{T}\mathrm{r}\left({\boldsymbol{U}}^{\mathrm{T}}\boldsymbol{\varLambda }\boldsymbol{U}\right)\end{array} $

(7)

其中：$ \boldsymbol{\varLambda }={\boldsymbol{X}}^{\mathrm{T}}\left(\boldsymbol{P}-\boldsymbol{Z}\right)\boldsymbol{X} $；$ \boldsymbol{P}=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}\left(\sum\limits _{j=1}^{n}{Z}_{ij}\right) $。

同样地，引入相应的惩罚项，以便在学习过程中约束特征权重矩阵，使其能够很好地拟合标签的基层流形结构。因此，标签流形学习模型也可写成以下形式：

$ \mathrm{O}\mathrm{b}\mathrm{j}=\mathrm{T}\mathrm{r}\left({\boldsymbol{U}}^{\mathrm{T}}\boldsymbol{\varLambda }\boldsymbol{U}\right)+\frac{\beta }{2}R\left(\boldsymbol{U}\right) $

(8)

1.3 柔性嵌入

通过式（5）和式（8）可以看出，针对特征选择中的惩罚函数$ R\left(\mathrm{*}\right) $，具有如下要求：

1）惩罚函数$ R\left(\mathrm{*}\right) $能够约束稀疏矩阵W和权重矩阵U的稀疏性。

2）惩罚函数$ R\left(\mathrm{*}\right) $能够根据特性结合稀疏矩阵W和权重矩阵U，且能使两者相互促进，相辅相成。

3）在一般情况下，在特征选择的过程中要能够清晰地区分特征的好坏，通常要求能够代表特征的矩阵要行内稳定、行间稀疏。因此，惩罚函数$ R\left(\mathrm{*}\right) $也要有这种约束性。

选取L_2，1-范数作为惩罚函数，即$ R\left(\mathrm{*}\right)={‖\mathrm{*}‖}_{\mathrm{2, 1}} $，不仅可以满足要求1和要求3，而且对奇异值比较敏感^[19]。

根据要求2，考虑到稀疏矩阵W和权重矩阵U较为相似，且都能用于进行特征选择，初步认为$ \mathrm{*}=\boldsymbol{W}-\boldsymbol{U} $，但$ \mathrm{*}=\boldsymbol{W}-\boldsymbol{U} $表示两者几乎完全相同，而实际上两者还是有一定的差别，仅基于不同的模型，W与U就会出现差别。引入偏置矩阵$ {\bf{1}}_{d}{\boldsymbol{b}}^{\mathrm{T}}\in {\mathbb{R}}^{n\times m} $来使模型变得更为合理，其中，$ {\bf{1}}_{d}\in {\mathbb{R}}^{d} $为使元素全为1的列向量，$ \boldsymbol{b}\in {\mathbb{R}}^{m} $为偏置向量。进一步认为$ \mathrm{*}=\boldsymbol{W}+{\bf{1}}_{d}{\boldsymbol{b}}^{\mathrm{T}}-\boldsymbol{U} $，因此$ R\left(\mathrm{*}\right)={‖\boldsymbol{W}+{\bf{1}}_{d}{\boldsymbol{b}}^{\mathrm{T}}-\boldsymbol{U}‖}_{\mathrm{2, 1}} $。

综上，本文设计柔性结合标签流形结构与logistic回归模型的多标签特征选择算法FSML，其目标优化问题可以改写如下：

$ \mathrm{O}\mathrm{b}\mathrm{j}=L\left(\boldsymbol{W}\right)+\frac{\alpha }{2}\mathrm{T}\mathrm{r}\left({\boldsymbol{U}}^{\mathrm{T}}\boldsymbol{\varLambda }\boldsymbol{U}\right)+\\ \ \ \ \ \ \ \ \frac{\beta }{2}{‖\boldsymbol{W}+{\bf{1}}_{d}{\boldsymbol{b}}^{\mathrm{T}}-\boldsymbol{U}‖}_{\mathrm{2, 1}} $

(9)

其中：$ \alpha $为标签流形参数。

2 问题求解 2.1 问题优化

针对L_2，1-范数的求解，根据文献[20]，当$ {\left(\boldsymbol{W}+{\bf{1}}_{d}{\boldsymbol{b}}^{\mathrm{T}}-\boldsymbol{U}\right)}_{i}\ne 0 $时，其中$ i=\mathrm{1, 2}, \cdots , d $。$ {‖\boldsymbol{W}+{\bf{1}}_{d}{\boldsymbol{b}}^{\mathrm{T}}-\boldsymbol{U}‖}_{\mathrm{2, 1}} $对W或对U的求导也可以看作$ \mathrm{T}\mathrm{r}\left({\left(\boldsymbol{W}+{\bf{1}}_{d}{\boldsymbol{b}}^{\mathrm{T}}-\boldsymbol{U}\right)}^{\mathrm{T}}\boldsymbol{H}\left(\boldsymbol{W}+{\bf{1}}_{d}{\boldsymbol{b}}^{\mathrm{T}}-\boldsymbol{U}\right)\right) $对W或对U的求导，其中$ \boldsymbol{H}\in {\mathbb{R}}^{d\times d} $是对角矩阵，H的第i个对角元素如下：

$ {H}_{ii}=\frac{1}{2{‖{\left(\boldsymbol{W}+{\bf{1}}_{d}{\boldsymbol{b}}^{\mathrm{T}}-\boldsymbol{U}\right)}_{i}‖}_{2}} $

(10)

因此，可以利用上述优化问题来求出式（9）的近似解，从而将目标函数转变如下：

$ \begin{array}{l}\mathrm{O}\mathrm{b}\mathrm{j}=L\left(\boldsymbol{W}\right)+\frac{\alpha }{2}\mathrm{T}\mathrm{r}\left({\boldsymbol{U}}^{\mathrm{T}}\boldsymbol{\varLambda }\boldsymbol{U}\right)+\\ \frac{\beta }{2}\mathrm{T}\mathrm{r}\left({\left(\boldsymbol{W}+{\bf{1}}_{d}{\boldsymbol{b}}^{\mathrm{T}}-\boldsymbol{U}\right)}^{\mathrm{T}}\boldsymbol{H}\left(\boldsymbol{W}+{\bf{1}}_{d}{\boldsymbol{b}}^{\mathrm{T}}-\boldsymbol{U}\right)\right)\end{array} $

(11)

对于该问题，可给定一个H，将W、U与当前的H进行计算，然后根据当前计算出的W、U对H进行更新。

2.2 给定H、W的U求解

根据式（11），当固定H和W时，关于U和b的目标函数可改写如下：

$ \begin{array}{l}\mathrm{O}\mathrm{b}\mathrm{j}\left(\boldsymbol{U}, \boldsymbol{b}\right)=\frac{\alpha }{2}\mathrm{T}\mathrm{r}\left({\boldsymbol{U}}^{\mathrm{T}}\boldsymbol{\varLambda }\boldsymbol{U}\right)+\\ \frac{\beta }{2}\mathrm{T}\mathrm{r}\left({\left(\boldsymbol{W}+{\bf{1}}_{d}{\boldsymbol{b}}^{\mathrm{T}}-\boldsymbol{U}\right)}^{\mathrm{T}}\boldsymbol{H}\left(\boldsymbol{W}+{\bf{1}}_{d}{\boldsymbol{b}}^{\mathrm{T}}-\boldsymbol{U}\right)\right)\end{array} $

(12)

利用$ \mathrm{O}\mathrm{b}\mathrm{j}\left(\boldsymbol{U}, \boldsymbol{b}\right) $对b求导并使导函数为0：

$ \frac{\partial \left(\mathrm{O}\mathrm{b}\mathrm{j}\left(\boldsymbol{U}, \boldsymbol{b}\right)\right)}{\partial \boldsymbol{b}}=\boldsymbol{b}{\bf{1}}_{d}^{\mathrm{T}}\boldsymbol{H}{\bf{1}}_{d}+{\boldsymbol{W}}^{\mathrm{T}}\boldsymbol{H}{\bf{1}}_{n}-{\boldsymbol{U}}^{\mathrm{T}}\boldsymbol{H}{\bf{1}}_{d}=0 $

(13)

根据式（13）可计算得出：

$ \boldsymbol{b}=\left({\boldsymbol{U}}^{\mathrm{T}}\boldsymbol{H}{\bf{1}}_{d}-{\boldsymbol{W}}^{\mathrm{T}}\boldsymbol{H}{\bf{1}}_{d}\right){\left({\bf{1}}_{\mathrm{d}}^{\mathrm{T}}\boldsymbol{H}{\bf{1}}_{d}\right)}^{-1} $

(14)

利用$ \mathrm{O}\mathrm{b}\mathrm{j}\left(\boldsymbol{U}, \boldsymbol{b}\right) $对U求导并使导函数为0：

$ \frac{\partial \left(\mathrm{O}\mathrm{b}\mathrm{j}\left(\boldsymbol{U}, \boldsymbol{b}\right)\right)}{\partial \boldsymbol{U}}=\partial \boldsymbol{\varLambda }\boldsymbol{U}+\beta \boldsymbol{H}\boldsymbol{D}\boldsymbol{U}-\beta \boldsymbol{H}\boldsymbol{D}\boldsymbol{W}=0 $

(15)

其中：D为中心矩阵，$ \boldsymbol{D}={\bf{1}}_{d}-{\left({\bf{1}}_{d}^{\mathrm{T}}\boldsymbol{H}{\bf{1}}_{d}\right)}^{-1}\cdot {\bf{1}}_{d}{\bf{1}}_{d}^{\mathrm{T}} $。根据式（15）可计算得出：

$ \boldsymbol{U}={\left(\alpha \boldsymbol{\varLambda }+\beta \boldsymbol{H}\boldsymbol{D}\right)}^{-1}\beta \boldsymbol{H}\boldsymbol{D}\boldsymbol{W} $

(16)

2.3 给定H、U的W求解

根据式（11），当固定H和U时，关于W的目标函数可改写如下：

$ \begin{array}{l}\mathrm{O}\mathrm{b}\mathrm{j}\left(\boldsymbol{W}\right)=L\left(\boldsymbol{W}\right)+\\ \frac{\beta }{2}\mathrm{T}\mathrm{r}\left({\left(\boldsymbol{W}+{\bf{1}}_{d}{\boldsymbol{b}}^{\mathrm{T}}-\boldsymbol{U}\right)}^{\mathrm{T}}\boldsymbol{H}\left(\boldsymbol{W}+{\bf{1}}_{d}{\boldsymbol{b}}^{\mathrm{T}}-\boldsymbol{U}\right)\right)\end{array} $

(17)

由于式（17）是可微的，因此可以通过Newton-Raphson算法进行求解，式（17）对W的一阶导如下：

$ \frac{\partial \left(\mathrm{O}\mathrm{b}\mathrm{j}\left(\boldsymbol{W}\right)\right)}{\partial \boldsymbol{W}}=-\boldsymbol{X}\boldsymbol{T}\left[\boldsymbol{Y}-g\left(\boldsymbol{X}\boldsymbol{W}\right)\right]+\beta \boldsymbol{H}\boldsymbol{D}\left(\boldsymbol{W}-\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \boldsymbol{U}\right) $

(18)

式（17）对W的二阶导如下：

$ \frac{{\partial }^{2}\left(\mathrm{O}\mathrm{b}\mathrm{j}\left(\boldsymbol{W}\right)\right)}{\partial \boldsymbol{W}\partial {\boldsymbol{W}}^{\mathrm{T}}}={\boldsymbol{X}}^{\mathrm{T}}\boldsymbol{V}\boldsymbol{X}+\beta \boldsymbol{H}\boldsymbol{D} $

(19)

$ \boldsymbol{V}=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}\sum\limits _{j=1}^{m}\left[\left(1-g\left({x}_{i}{w}_{j}\right)\right)g\left({x}_{i}{w}_{j}\right)\right] $

(20)

其中：$ i=\left[\mathrm{1, 2}, \cdots , n\right] $。

W更新公式如下：

$ {\boldsymbol{W}}^{t+1}={\boldsymbol{W}}^{t}-{\left(\frac{{\partial }^{2}\left(\mathrm{O}\mathrm{b}\mathrm{j}\left(\boldsymbol{W}\right)\right)}{\partial \boldsymbol{W}\partial {\boldsymbol{W}}^{T}}\right)}^{-1}\frac{\partial \left(\mathrm{O}\mathrm{b}\mathrm{j}\left(\boldsymbol{W}\right)\right)}{\partial \boldsymbol{W}} $

(21)

通过以上问题的优化与求解，柔性结合标签流形结构与logistic回归模型的多标签特征选择算法FSML具体描述如下：

算法1  FSML算法

输入  数据矩阵$ \boldsymbol{X}\in {\mathbb{R}}^{n\times d} $，标签矩阵$ \boldsymbol{Y}\in {\mathbb{R}}^{n\times m} $，正则化参数$ \alpha $与$ \beta $，选取特征个数k

输出  特征选择结果I

1）根据式（6）计算特征相似矩阵Z并计算$ \boldsymbol{\varLambda }={\boldsymbol{X}}^{\mathrm{T}}\left(\boldsymbol{P}-\boldsymbol{Z}\right)\boldsymbol{X} $。

2）初始化中心矩阵D；令$ t=0 $，初始化对角矩阵$ {\boldsymbol{H}}^{t} $为单位矩阵。

3）初始化系数矩阵$ {\boldsymbol{W}}^{t} $为0矩阵，并重复：（1）计算$ {\boldsymbol{U}}^{t+1}={\left(\alpha \boldsymbol{\varLambda }+\beta {\boldsymbol{H}}^{t}\boldsymbol{D}\right)}^{-1}\beta \boldsymbol{H}\boldsymbol{D}{\boldsymbol{W}}^{t} $；（2）根据式（18）~式（20）计算$ \mathrm{O}\mathrm{b}\mathrm{j}\left(\boldsymbol{W}\right) $的一阶导函数和二阶导函数，（3）计算$ {\boldsymbol{W}}^{t+1}={\boldsymbol{W}}^{t}-{\left(\frac{{\partial }^{2}\left(\mathrm{O}\mathrm{b}\mathrm{j}\left({\boldsymbol{W}}^{t}\right)\right)}{\partial {\boldsymbol{W}}^{t}\partial {{\boldsymbol{W}}^{t}}^{\mathrm{T}}}\right)}^{-1}\frac{\partial \left(\mathrm{O}\mathrm{b}\mathrm{j}\left({\boldsymbol{W}}^{t}\right)\right)}{\partial {\boldsymbol{W}}^{t}} $和$ {\boldsymbol{b}}^{t+1}= $ $ {\left({\bf{1}}_{d}^{\mathrm{T}}{\boldsymbol{H}}^{t}{\bf{1}}_{d}\right)}^{-1} $ $ \left({{\boldsymbol{U}}^{t+1}}^{\mathrm{T}}{\boldsymbol{H}}^{t}{\bf{1}}_{d}-{{\boldsymbol{W}}^{t+1}}^{\mathrm{T}}{\boldsymbol{H}}^{t}{\bf{1}}_{d}\right) $；（4）计算对角矩阵H，其第i个对角元素为$ {\boldsymbol{H}}_{ii}^{t+1}=\frac{1}{2{‖{\left({\boldsymbol{W}}^{t+1}+{\bf{1}}_{d}{{\boldsymbol{b}}^{t+1}}^{T}-{\boldsymbol{U}}^{t+1}\right)}_{i}‖}_{2}} $，直到目标函数收敛为止。

4）计算并排序$ {‖{\boldsymbol{W}}_{i}‖}_{2}\left(i=\mathrm{1, 2}, \cdots , d\right) $，其中$ {\boldsymbol{W}}_{i} $是W的第i个行向量；找出W中前k个最大的行向量的索引赋给I。

FSML算法的目的主要是计算并更新W与U，每次迭代的时间复杂度为$ O\left(2{d}^{2}n\right) $，共迭代t次，因此总的时间复杂度为$ O\left(2t{d}^{2}n\right) $。由于t值一般不大，因此FSML算法处理数据的运行时间受数据维数d和数据集样本个数n的影响较大。

FSML算法的收敛性分析类似于$ {L}_{\mathrm{2, 1}} $-范数的收敛性分析，图 1给出了参数$ \alpha =1 $、$ \beta =1 $、$ K=5 $时，FSML算法在生物数据集Yeast、文本数据集Health和Computers、音乐数据集Emotion、图像数据集Scene等5个经典数据集上的收敛性结果。

3 实验与结果分析

采用5个经典数据集进行FSML算法有效性验证，并将其与SCLS^[21]、MDMR^[22]、PMU^[23]、FIMF^[24]、CMLS^[25]算法以及Baseline（选择所有特征）进行性能比较，同时选择ML-KNN^[26]算法作为代表性的多标签分类算法进行实验。

3.1 数据集与实验设置

实验中采用的5个经典数据集来自木兰图书馆（http://mulan.sourceforge.net/datasets.html），具体信息如表 1所示。

实验操作系统环境为Microsoft Windows 7，处理器为Intel^® Core^TM i5-4210U CPU @ 1.70 GHz 2.40 GHz，内存为4.00 GB，编程软件为Matlab R2016a。

实验参数设置如下（设置1和设置2均为对应算法的默认设置）：

1）在ML-KNN算法中，设置平滑参数$ S=1 $，近邻参数$ K=10 $。

2）在FIMF、MDMR和PMU算法中，利用等宽区间对数据集进行离散化处理^[27]，并且在FIMF算法中，设置$ Q= \ 10 $、$ b=2 $。

3）将所有特征选择算法（除ML-KNN算法以外）的最近邻参数设为$ K=5 $，最大迭代次数设为50。

4）所有算法的正则化参数通过网格搜索策略进行调整，搜索范围设置为$ \left[\mathrm{0.001, 0.01, 0.1}, \right.\mathrm{1, 10}, $ $ 100, \left.1 \ 000\right] $，并将选择的功能数量设置为$ \left[\mathrm{10, 15}, \right. $ $ \mathrm{20, 25}, \left.\mathrm{30, 35, 40, 45, 50}\right] $。

3.2 评价指标

与单标签学习系统的性能评价不同，多标签学习系统的评价指标更为复杂。假设一个测试数据集$ D={\left\{\left({d}_{i}, {y}_{i}\right)\right\}}_{i=1}^{n} $，给定测试样本$ {d}_{i} $，多标签分类器预测的二进制标签向量记为$ \boldsymbol{h}\left({d}_{i}\right) $，第l个标签预测的秩记为$ \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{i}\left(l\right) $。

1）汉明损失（Hamming Loss）。度量的是错分的标签比例，即正确标签没有被预测以及错误标签被预测的标签占比。值越小，表现越好。Hamming Loss计算公式如下：

$ {H}_{\mathrm{H}\mathrm{a}\mathrm{m}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{g} \ \mathrm{L}\mathrm{o}\mathrm{s}\mathrm{s}}\left(D\right)=\frac{1}{n}\sum\limits _{i=1}^{n}\frac{1}{m}{‖\boldsymbol{h}\left({d}_{i}\right)\mathrm{\Delta }{\boldsymbol{y}}_{i}‖}_{1} $

(22)

其中：$ \mathrm{\Delta } $表示两个集合的对称差，返回只在其中一个集合中出现的那些值；$ {H}_{\mathrm{H}\mathrm{a}\mathrm{m}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{g} \ \mathrm{L}\mathrm{o}\mathrm{s}\mathrm{s}}\left(D\right)\in \left[\mathrm{0, 1}\right] $。

2）排名损失（Ranking Loss）。度量的是反序标签对的占比，即不相关标签比相关标签的相关性还要大的情况。值越小，表现越好。Ranking Loss计算公式如下：

$ \begin{array}{l}{R}_{\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{k}\mathrm{i}\mathrm{n}\mathrm{g} \ \mathrm{L}\mathrm{o}\mathrm{s}\mathrm{s}}\left(D\right)=\frac{1}{n}\sum\limits _{i=1}^{n}\frac{1}{{\bf{1}}_{m}^{\mathrm{T}}{y}_{i}{\bf{1}}_{m}^{\mathrm{T}}\overline{{y}_{i}}}\cdot \\ \sum\limits _{l:{y}_{i}^{l}=1}^{}\sum\limits _{l':{y}_{i}^{l'}=0}\left(\delta \left(\mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{i}\left(l\right)\right.\right.\left.\left.\ge \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{i}\left(l'\right)\right)\right)\end{array} $

(23)

其中：$ \overline{{\boldsymbol{y}}_{i}} $为$ {\boldsymbol{y}}_{i} $在Y上的补集；$ {R}_{\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{k}\mathrm{i}\mathrm{n}\mathrm{g} \ \mathrm{L}\mathrm{o}\mathrm{s}\mathrm{s}}\left(D\right)\in \left[\mathrm{0, 1}\right] $。

3）1-错误率（One-Error）。度量的是预测到的最相关的标签不在真实标签中的样本占比。值越小，表现越好。One-Error计算公式如下：

$ {O}_{\mathrm{O}\mathrm{n}\mathrm{e}-\mathrm{E}\mathrm{r}\mathrm{r}\mathrm{o}\mathrm{r}}\left(D\right)=\frac{1}{n}\sum\limits _{i=1}^{n}\delta \left({y}_{i}^{{l}_{i}}=0\right) $

(24)

其中：$ {l}_{i}=\underset{l\in \left[1, m\right]}{\mathrm{a}\mathrm{r}\mathrm{g} \ \mathrm{m}\mathrm{i}\mathrm{n}} \ \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{i}\left(l\right) $；$ \delta \left(z\right)=\left\{\mathrm{0, 1}\right\} $是指示函数；$ {O}_{\mathrm{O}\mathrm{n}\mathrm{e}-\mathrm{E}\mathrm{r}\mathrm{r}\mathrm{o}\mathrm{r}}\left(D\right)\in \left[\mathrm{0, 1}\right] $。

4）覆盖率（Coverage）。度量的是排序好的标签列表平均需要移动多少步才能覆盖真实的相关标签集。值越小，表现越好。Coverage计算公式如下：

$ {C}_{\mathrm{C}\mathrm{o}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{g}\mathrm{e}}\left(D\right)=\frac{1}{n}\sum\limits _{i=1}^{n}\underset{l:{y}_{i}^{l}=1}{\mathrm{a}\mathrm{r}\mathrm{g} \ \mathrm{m}\mathrm{a}\mathrm{x}} \ \text{ran}{k}_{i}\left(l\right)-1 $

(25)

其中：$ {C}_{\mathrm{C}\mathrm{o}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{g}\mathrm{e}}\left(D\right)\in \left[0, m-1\right] $。

5）平均精度（Average Precision）。度量的是比特定标签更相关的那些标签的排名占比。值越大，表现越好。平均精度计算公式如下：

$ {A}_{\mathrm{A}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{g}\mathrm{e} \ \mathrm{P}\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n}}\left(D\right)=\frac{1}{n}\sum\limits _{i=1}^{n}\frac{1}{{\bf{1}}_{m}^{\mathrm{T}}{\boldsymbol{y}}_{i}}\sum\limits _{l:{y}_{i}^{l}=1}^{}\frac{\mathrm{p}\mathrm{r}\mathrm{e}{\mathrm{c}}_{i}\left(l\right)}{\mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{i}\left(l\right)} $

(26)

其中：$ \mathrm{p}\mathrm{r}\mathrm{e}{\mathrm{c}}_{i}\left(l\right)=\sum\limits _{l\mathrm{'}:{y}_{i}^{'}=1}^{}\delta \left(\mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{i}\left(l'\right)\le \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{i}\left(l\right)\right) $；A_{Average Precision}（D）∈[0, 1]。

3.3 实验结果

本文提出的FSML算法在5个经典数据集上进行实验，并考虑Hamming Loss、Ranking Loss、One-Error、Coverage、Average Precision评价指标对FSML算法与对比算法的性能进行比较。表 2~表 6给出了所有特征选择算法在最优参数时的最优结果，其中，最优结果用粗体标出，次优结果用下划线标出。从表 2~表 6可以看出：大多数的最优结果出现在FSML算法上，从而证明FSML算法的可行性；具体而言，FSML算法虽然在Scene数据集上的所有指标相对于Baseline均略有不足，但在Computers、Health、Scene数据集上的所有指标，以及Yeast数据集上的Ranking Loss、One-Error、Coverage、Average Precision均优于对比算法，并且在Emotion、Computers、Health、Yeast数据集上的所有指标甚至优于Baseline。

综上，FSML算法在各种实验指标上的性能均明显优于FIMF算法、PMU算法、MDMR算法和SCLS算法，在Computers、Health、Scene数据集上明显优于CMLS算法，在Emotion数据集上略优于CMLS算法，并在除Scene数据集以外的其他实验数据集上的指标均优于Baseline。

为能更直观地展示FSML算法与对比算法以及Baseline的性能对比，图 2~图 6给出了所有算法在各种数据集上的性能评价指标。从图 2~图 6可以看出：FSML算法在Scene数据集上的性能表现虽然略次于Baseline，但在其他数据集上的性能表现很好，尤其是在Health数据集上的性能表现最好，明显优于对比算法和Baseline。通过FSML算法与对比算法的比较结果可以看出，FSML算法的实验结果通常优于对比算法，可见将logistic回归模型与流形结构柔性结合，能更准确地学习到数据与标签间的关系；通过与Baseline的比较结果可以看出，FSML算法在大多数数据集上的实验结果都优于Baseline，能够有效去除不相关的特征和冗余特征。

为研究FSML算法对参数的敏感程度：一方面，设置近邻参数$ K=5 $，通过网格搜索策略来调整$ \alpha $与$ \beta $的数值，探究FSML算法在取不同参数时，Average Precision评价指标的变化情况，如图 7所示，可以看出在一定范围内Average Precision评价指标值会随参数的变化而变化，并且不同的实验数据对参数的敏感程度不同，当$ \alpha < 1 $、$ \beta < 1 $时FSML算法性能对参数的变化不是很敏感；另一方面，设置参数$ \alpha =10 $、$ \beta =100 $，在$ \left[\mathrm{5, 6}, \mathrm{7, 8}, \mathrm{9, 10}\right] $内调整近邻参数K的值，探究近邻参数K的变化对FSML算法性能的影响，如图 8所示，可以看出在Yeast、Scene数据集上FSML算法对近邻参数K的变化不太敏感，而在其他数据集上则较为敏感，可见FSML算法对近邻参数K的变化是否敏感与数据本身的基层结构特征有关。

如图 9所示，横坐标轴表示在各评价指标下各多标签特征选择算法的排序，从左到右，算法的性能越来越好，同时还给出了Bonferroni-Dunn测试结果的平均秩图，并将无显著差异$ \left(p < 0.1\right) $的算法组连接，如果平均排名达到差异的临界值（Critical Distance），则有显著差异^[28]。在One-Error指标下，FSML算法性能明显优于对比算法，并具有显著性差异；在其他指标下，FSML算法的性能明显优于SCLS、FIMF、MDMR和PMU算法，并具有显著性差异，虽然与CMLS算法之间没有显著性差异，但FSML算法的排序始终在第一位。因此，与其他算法相比，FSML算法具有更好的性能。

4 结束语

本文基于L_2，1-范数将标签流形结构与logistic回归模型柔性结合，构建多标签特征选择算法FSML，并在多个经典多标签数据集上与现有多标签特征选择算法进行性能对比。实验结果证明了FSML算法的有效性。但由于近邻参数K不能自适应学习，导致同一个K值不一定能够较好地学习到每个数据标签的基层流形结构，从而限制了FSML算法的应用范围。下一步将对相似矩阵学习进行研究，使近邻参数K能够实现自适应学习，并扩展该自适应学习方法在半监督多标签特征选择中的应用与研究。