基于流形学习与L2，1范数的无监督多标签特征选择

马盈仓,张 要,2，张 宁，朱恒东

(1.西安工程大学 理学院,陕西 西安 710600;2.山东华宇工学院 基础教学部，山东 德州 253034)

0 引 言

嵌入式多标签特征选择方法是目前性能良好并广泛使用的一类特征选择方法。多标签特征选择又称为多标签特征子集选择，是指适用于多标签数据集的特征选择算法，是从原始特征中选择出一些最有效的特征以降低数据集维度的过程。在学习算法中，多标签特征选择不仅能够缩短训练时间、降低成本要求，还能减少过拟合、避免维数灾难等[1-3]，是模式识别中关键的数据预处理步骤。与传统的特征选择相比，多标签特征选择往往更为复杂，既要考虑数据与数据间的关系、数据与标签间的关系，还要考虑标签与标签间的关系。现有的特征选择方法大致可分为过滤式[4-6]、封装式[7-8]、嵌入式[9-11]等3类，其中嵌入式是过滤式与封装式的折中体现。基于标签信息的有无，也可将特征选择方法分为有监督[12-13]、半监督[14-15]、无监督[16-17]等。然而，现有的嵌入式多标签特征选择方法，大多是基于最小二乘、逻辑回归、信息熵等，且隶属于有监督或半监督多标签特征选择方法。

文献[18]将传统的逻辑模型扩展到多标签分类中，使其能够适用于多标签数据集，同时也能进行多标签特征选择；文献[19]利用标签ω拖动思想，提出了一种包含标签信息的最小二乘多标签特征选择方法；文献[20]针对标签不平衡分布问题，提出了一种边缘标记弱化的多标签特征选择算法；文献[21]提出了一种新的扩展自适应最小绝对收缩选择算子特征选择方法(EALasso)。文献[22]提出了一种具有多重正则化的多标签特征选择方法(MDFS)。该方法不仅考虑了特征与标签的局部相关性，还通过L2,1范数约束目标函数。文献[23]将矩阵分解问题、非负约束问题和L2,1范数最小化问题相结合，构成了基于非负稀疏表示的多标签特征选择方法；文献[24]利用L2,1范数约束相关熵与流形学习，构造了一种基于相关熵和流形学习的多标签特征选择模型；文献[25]提出了一种基于光谱分析的半监督特征选择算法。然而，这些经典算法仅针对带标签数据集设计。文献[26]为了解决多标签问题，将多标签学习分解为多个独立的单标签问题，没有考虑到不同标签之间的相关性；文献[27]通过L1范数与标签流形学习共同约束逻辑回归的系数矩阵，解决特征选择问题；文献[28]提出了一种适用于大规模数据集的凸半监督多标签特征选择算法。

上述多标签特征选算法都是有监督或半监督的，或多或少都需要用到数据的标签，从而忽略了大量的廉价的无标签数据。此外，还有一些无监督特征选择算法。文献[29]提出了一种基于自编码器的无监督特征选择模型。该模型考虑了非负性、正交性和稀疏性，充分利用了其内部特征。文献[30]提出了无监督稀疏图嵌入特征选择方法；文献[31]利用酉不变性的深度随机游走学习鉴别特征，提出了一种有效的数据表示方法来解决大规模的特征表示问题。但这些无监督模型大多适用于单标签数据。针对嵌入式无监督多标签特征选择的挑战，本文将L2,1范数回归与流形学习结合，构成了新的无监督多标签特征选择模型，设计了一种高效的收敛性算法(UMLFS)，并通过在多个经典数据集上的对比实验证明其可行性。

1 模型建立

1.1 L2,1范数回归模型

给定多标签数据集X，其特征矩阵记为X=[x1,x2,…,xn]T，X∈Rn×d，根据问题特征作如下假设：拟合伪标签为F∈Rn×m(未知)，且在L2,1范数距离上有F=XW，其中W∈Rd×m是特征权重矩阵，能够体现特征的重要性，并且L2,1范数可以有效地约束权重矩阵W的行间稀疏、行内稳定，更有利于特征选择。从而有

(1)

式中：β为惩罚因子；R(W)为惩罚函数，表示对W的相应约束惩罚。

1.2 特征流形正则化

随着学者们的不断研究、扩展，将流形学习推广到维数简约[32]、协同聚类算法[33]、特征选择算法等各领域。

对与UMLFS算法，由于是无监督的，无法利用标签信息，所以就更应该使用特征流形约束权重矩阵的学习，同时数据特征的拉普拉斯图矩阵，也能提供一个很好的参数调节过程，从而避免了所有特征的约束参数都一样的可能。根据问题特征再假设：

令X=[f1,f2,…,fd]，W=[W1,W2,…,Wd]T,其中fi是数据矩阵的第i列，表示数据的第i个特征向量，Wi是权重矩阵的第i行，表示第i个特征向量所对应的权重。由于权重矩阵W可以体现特征的权重，所以，若fi与fj距离相近，那么Wi与Wj的距离也应该相近。从而可以通过特征间相似性指导权重矩阵的学习，构建特征流形学习模型，其表达式如下：

tr(WTLW)

(2)

式中：L∈Rd×d为特征相似矩阵；Lij为L的第i行、第j列元素，表示特征fi与fj的相似度。文中是通过带平方约束的Pearson相关系数计算L的，其公式为

(3)

1.3 伪标签约束

在多标签学习中，学者们普遍认为标签矩阵是数据矩阵的一种映射，所以两者的结构极其相似。而在本文中，伪标签是真实标签的一种替换，理论上，其应该具有真实标签的所有属性。令伪标签矩阵F=[F1,F2,…,Fn]T，真实标签矩阵Y=[Y1,Y2,…,Yn]T，Y∈Rn×m，根据问题再假设：

1) 若样本xi与xj的相似度较高，那么真实标签Yi与Yj的相似度也应该较高;

2) 伪标签矩阵F基本与真实标签矩阵Y等价。

由于在本研究中只存在数据信息，所以可以用数据样本的相似矩阵约束伪标签矩阵的学习，从而提高伪标签矩阵的精确度。其公式为

tr(FTΛF)

(4)

式中：Λ∈Rn×n为数据样本的相似矩阵；Λij为Λ的第i行、第j列元素，表示样本xi与xj之间的相似度。与特征相似矩阵L类似，样本相似矩阵Λ同样是通过带平方约束的Pearson相关系数计算的，即

(5)

(6)

式中：B(*)为关于变量*的目标函数；α与β是正则项参数。

2 问题求解

2.1 问题优化

由于L2,1范数的非光滑性，根据文献[34]，当(XW-F)i≠0时，其中i=1,2,…,n。‖XW-F‖2,1关于W或F的导函数也可以看作是tr((XW-F)TH(XW-F))关于W或F的导函数。其中H∈Rn×n是对角矩阵，H的第i个对角元素为

(7)

使用L2,1范数的优化问题求B(W,F)的近似解：

(8)

对于式(8)，可以先给定W、H，计算出F；再利用F、H，更新W；最后通过W、F，更新H。

2.2 给定H、W求解F

(9)

求出B(F)关于F的导函数，并使导函数为0，即

(10)

从而可以计算出F，即

F=(H+βΛ)-1HXW

(11)

2.3 给定H、F求解W

(12)

求出B(W)关于W的导函数，并使导函数为0，即

(13)

从而可以计算出W，即

W=(XTHX+αL)-1XTHF

(14)

通过以上问题优化与求解，基于流形学习与L2,1范数的无监督多标签特征选择(unsupervised multi-label feature selection based on manifold learning andL2,1norm， UMLFS)算法如下：

算法1：UMLFS算法

输入：数据矩阵X∈Rn×d，正则化参数α与β，选取特征个数k，迭代次数t。

1) 根据式(3)计算特征相似矩阵L;

2) 根据式(5)计算样本相似矩阵Λ;

3) 令t=0，初始化对角矩阵Ht为单位矩阵;

4) 初系数矩阵Wt为元素全为1的矩阵。

重复：

根据式(11)计算Ft,

t=t+1,

根据式(14)更新Wt,

根据式(7)更新Ht。

直到收敛为止。

5) 计算并排序‖Wi‖2(i=1,2,…,d)，找出前k个最大的赋给I。

输出：特征选择结果I。

算法1主要更新W与F，每次迭代的时间复杂度是O(2d2n)，一共迭代了t次，所以算法1的总时间复杂度为O(2td2n)。t的值一般较小，所以对算法1的时间复杂度影响不大。然而，算法1的时间复杂度受数据的维数d和数据集样本个数n的影响较大。

2.4 收敛性分析

证明算法1的收敛性。令Q=XW-F，则

(15)

由算法1的t次迭代可知，当固定W时，有

B(W,Ft+1)≤B(W,Ft)

(16)

当固定F时，有

B(Wt+1,F)≤B(Wt,F)

(17)

从而有

B(Qt+1)≤B(Qt)

(18)

由此，可以推出

(19)

所以可以转换为

(20)

其中Qi表示Q的第i行向量。式(20)可以进一步转化为

(21)

(22)

对式(22)求和，可得到

(23)

从而推出

(24)

综上所述，算法1的收敛性得到证明。

图1为UMLFS算法在Yeast和Bibtex实验数据集上的收敛结果，其中参数设置为α=1，β=1。

(a) Yeast

(b) Bibtex图 1 UMLFS算法对Yeast和Bibtex数据集的收敛性Fig.1 Convergence results of UMLFS algorithm for Yeast and Bibtex data set

3 实 验

选取5个经典数据集，与4个经典的有监督多标签特征选择算法SCLS[35]、MDMR[36]、PMU[37]、FIMF[38]共同进行实验，并选择MLKNN[39]作为多标签分类算法的代表进行评价。

3.1 数据集与参数设置

实验中采用的5个经典数据集，来自4个不同的领域，包括图像数据集Image、Scene，音乐数据集Emotion，文本数据集Bibtex及生物数据集Yeast。这些数据均来自木兰图书馆(http://mulan.sourceforge.net/datasets.html)。各数据集的具体参数如表1所示。

表 1 数据集信息Tab.1 Data set information

实验环境为：Microsoft Windows7系统处理器为Intel(R) Core(TM) i5-4210U CUP @ 1.70 GHz 2.40 GHz，内存4.00 GB；采用Matlab R2016a编程软件。

将MLKNN算法的平滑参数设置为S=1，近邻参数设置为K=10。应用等宽区间对数据集进行离散化处理[40]，使其适用于MDMR、FIMF等算法，并将FIMF算法的参数设置为Q=10,b=2。以上是算法的默认参数。利用“网格搜索”策略，调整所有的多标签特征选择算法的正则化参数，设置为(0.001，0.01，0.1，1，10，100，1 000)，将选择的特征个数设置为(10，15，20，25，30，35，40，45，50)。

由于对比算法都是有监督的多标签特征选择算法，所以实验本身对UMLFS算法是严格的。

3.2 评价指标

1) 汉明损失LH：分错标签的占比，值越小越好。

(25)

式中：h(ci)Δyi为h(ci)和yi的对称差，LH(C)∈[0,1]。

2) 排序损失LR：反序标签对的占比，值越小越好。

(26)

3) 1-错误率RE：在“真实标签”中不存在“预测到的最相关的标签”的样本占比，值越小越好。

(27)

4) 覆盖率CV：要想覆盖真实的标签相关集，“排序后的标签”平均需要移动多少步，值越小越好。

(28)

式中：CV(C)∈[0,m-1]。

5) 平均精度PA：相关性高于特定标签的标签，在排名中的占比，值越大越好。

(29)

3.3 实验结果与分析

在5个经典数据集上，将UMLFS算法与4个对比算法进行了对比实验。利用汉明损失、排序损失、1-错误率、覆盖率、平均精度等5个评价指标评价各算法的性能；同时，以最优得1分、次优得0.5分、其他为0分(共7.5分)计分，根据各算法在对应指标上的性能分配，给出了各算法的得分情况。实验结果如表2～6所示，表中分别用粗体和下划线标出最优结果和次优结果，并且表中展示的都是对应算法在最优参数下的最优结果。

表 2 各数据集不同算法的汉明损失对比Tab.2 Hamming loss comparison of different algorithms under each data set

表 3 各数据集不同算法的排序损失对比Tab.3 Ranking loss comparison of different algorithms under each data set

表 4 各数据集不同算法的1-错误率对比Tab.4 One-error comparison of different algorithms under each data set

表 5 各数据集不同算法的覆盖率对比Tab.5 Coverage comparison of different algorithms under each data set

表 6 各数据集不同算法的平均精度对比Tab.6 Average precision comparison of different algorithms under each data set

从表2～6可以看出：UMLFS算法虽然在Yeast数据集上排序损失指标的最优结果略不如MDMR算法和PMU算法，在1-错误率指标的最优结果仅次于SCLS算法，在平均精度指标的最优结果仅次于MDMR算法，但在其他各指标的最优结果仍优于其他对比算法，并且在Emotion、Scene、Bibtex、Image数据集上的各指标的最优结果都明显优于所有对比算法。

(a) Yeast (b) Bibtex (c) Image图 3 3种数据集不同算法间的排序损失比较Fig.3 Ranking loss comparison between different algorithms on three data set

(a) Yeast (b) Bibtex (c) Image图 4 3种数据集不同算法间的1-错误率比较Fig.4 One-error comparison between different algorithms on three data set

(a) Yeast (b) Bibtex (c) Image图 5 3种数据集不同算法间的覆盖率比较Fig.5 Coverage comparison between different algorithms on three data set

(a) Yeast (b) Bibtex (c) Image图 6 3种数据集不同算法间的平均精度比较Fig.6 Average precision comparison between different algorithms on three data set

可见，UMLFS算法除在Yeast数据集上的性能略不理想外，在其他理想数据集上各指标的性能都是最优的。从得分情况(表2～6)可以看出，UMLFS算法的分值最低为4，最高为5，始终优于对比算法。所以，UMLFS算法在解决无监督多标签特征选择问题上是有效的。

为了能更直观地对比各算法的汉明损失、排序损失、1-错误率、覆盖率、平均精度等指标的性能，以及选择的特征个数对算法的影响，图2～6以选择的特征个数为横坐标，以各指标的结果值为纵坐标，展示了数据集Yeast、Bibtex和Image的实验结果。

从图2～6可以看出，UMLFS算法在Bibtex数据集上的汉明损失、排序损失、1-错误率、覆盖率等指标明显低于对比算法的对应指标，而平均精度明显高于对比算法平均精度；UMLFS算法在Image数据集上各指标相对于对比算法的结果，形成了一层包络，较优于对比算法。虽然表2～6中UMLFS算法在Yeast数据集上的一些指标的最优结果不如MDMR算法和SCLS算法，但由图2～6可以清楚地看出，UMLFS算法各指标的整体结果还是较优的。可见，UMLFS算法整体上优于各对比算法，说明UMLFS算法能够更好地利用数据信息进行特征选择，以及UMLFS算法在解决无监督多标签特征选择问题上的可行性。

关于参数α、β的变化对UMLFS算法性能的影响，做了针对性的实验。固定选择的特征个数为50，利用“网格搜索”的策略，对参数α与β进行调整，其中搜索值分别设置为0.001、0.01、0.1、1、10、100、1 000。计算UMLFS算法平均精度评价指标的性能变化，结果如图7所示。

(a) Yeast (b) Bibtex (c) Image图 7 不同参数α、β对于UMLFS算法平均精度的影响Fig.7 Effect of different parameters α and β on average precision of UMLFS algorithm

从图7可以看出，对于不同的数据集，参数的敏感程度不同。如在Image数据集上，参数α与β的变化对UMLFS算法的影响程度较大；而在Yeast和Bibtex数据集上，UMLFS算法对参数的变化不敏感。这可能与特征相似矩阵和样本相似矩阵的学习方法不能适用于所有数据集有关。

图8展示了各算法间的显著性差异和排名。在图8中，以排名为横坐标，从左到右，算法的性能依次变好。同时，图8还以平均秩图的形式展示了Bonferroni-Dunn测试结果，并将无显著差异(p<0.1)的算法组连接，如果平均排名达到差异的临界值，则有显著差异[41]。从图8可以看出：UMLFS算法的汉明损失、平均精度等指标，虽然与SCLS算法和MDMR算法无显著性差异，但与PMU算法和FIMF算法之间存在显著差异；在覆盖率指标上虽然与SCLS算法、FIMF算法和MDMR算法无显著差异，但与PMU算法存在显著差异。而且UMLFS算法在各指标的排名始终在最右侧的第1位。因此，与对比算法相比，UMLFS算法的性能表现更好。

(a) 汉明损失

(b) 覆盖率

(c) 平均精度图 8 Bonferroni-Dunn检验结果的平均秩图的形式Fig.8 The form of average rank graph of Bonferroni-Dunn test results

4 结 语

使用带平方约束的Pearson相关系数学习特征和样本的基层流形结构；分别用特征流形和样本流形约束特征权重矩阵和伪标签矩阵；结合L2,1范数构建了无监督多标签特征选择模型(UMLFS)。该模型在多个数据集上与多个经典的有监督多标签特征选择模型进行对比实验，结果表明UMLFS算法的有效性。学得一个精确的基层结构，才能更好地进行特征选择。所以，下一步将继续研究相似矩阵的学习，并对UMLFS算法进行改进，使其能够更好地适用于无监督多标签特征选择。