基于动态图拉普拉斯的多标签特征选择

李永豪，胡亮，张平，高万夫,3

（1.吉林大学计算机科学与技术学院，吉林 长春 130012；2.吉林大学符号计算与知识工程教育部重点实验室，吉林 长春 130012；3.吉林大学化学学院，吉林 长春 130012）

1 引言

进入大数据时代后，万物互联产生了海量的数据，其中高维数据导致的维度诅咒问题非常引人注意，处理这些高维数据对现有的方法来说是一个巨大的挑战[1-2]。更进一步地，在这些高维数据中存在的多标签数据也越来越凸显其现实应用价值[3-4]。与早期的单标签数据不同，多标签数据中每个样例都可能与多个不同的标签有关联[5-7]。例如，各类音乐软件中对歌曲进行分类时，同一首歌曲可能标记不同风格的标签。如何有效地对各类多标签数据进行分类逐渐成为研究的热点[6]。然而，高维多标签数据中存在大量特征，这些特征中包含的不相关信息严重削弱了多标签学习算法的分类性能[1,8]。如何找到一个紧凑的、与标签相关的特征子集是一个棘手而紧迫的问题。特征选择算法可以从原始数据中获得一个最优特征子集，它不仅实现了特征降维，而且保留了原始数据的直观意义和物理解释[9]。因此，特征选择技术成为图像、视频、文本和基因等存在大量多标签数据的领域的热门预处理方法[10]。一般来说，多标签特征选择分为过滤式模型、包装式模型和嵌入式模型[11-13]。过滤式模型与后续学习算法无关[14]，而包装式模型依赖于学习算法。与过滤式和包装式模型不同，嵌入式模型将特征选择嵌入学习算法中。本文重点研究嵌入式模型。

在嵌入式模型的特征选择方法中，基于图的特征选择方法备受关注。传统的基于图的特征选择方法严格依赖于固定的图拉普拉斯矩阵，其通常采用两步策略[15-17]：1)构造对称亲和矩阵；2)利用对称亲和矩阵指导特征选择过程，得到图拉普拉斯矩阵。然而，这种策略忽略了图拉普拉斯矩阵在算法执行过程中的动态变化。具体地，在特征选择算法执行过程中，算法的每一次更新迭代应该依赖本次迭代的图拉普拉斯矩阵。传统基于图的特征选择算法在每次算法迭代过程中，并没有选择适合本次迭代的图拉普拉斯矩阵，前一次更新造成的误差会被后续的更新不断放大。因此，特征选择方法无法获得令人满意的分类性能。另外，在有监督的多标签特征选择方法中还存在一个问题，大多数基于图的特征选择方法利用逻辑标签来指导特征选择[18-19]，然而逻辑标签不能很好地反映相应标签的重要性，即逻辑标签无法刻画标签本身的重要程度，而且多标签数据涉及大量不同标签，这些标签之间相关性复杂，这些问题导致多标签特征选择方法无法获得令人满意的分类性能。本文针对上述问题，设计了一种动态图拉普拉斯的多标签特征选择方法。首先，本文构造了一个稳健的低维空间；其次，利用基于低维空间的动态图拉普拉斯矩阵指导特征选择过程；最后，通过在不同领域数据上的实验证明了所提方法的分类优势。本文主要贡献如下。

1) 设计了一种基于特征矩阵的稳健低维空间的动态变化图拉普拉斯矩阵来指导特征选择。

2) 在所获得的图拉普拉斯动态更新基础上，为避免逻辑标签造成的信息丢失，将逻辑标签转化为实值标签。

3) 设计了一种基于动态图拉普拉斯矩阵和实值标签的多标签特征选择方法，针对该方法提出一种有效的优化方案，并证明了该方案的收敛性。

4) 通过在9个多标签基准数据集上与3 个多标签特征选择方法的对比实验验证了该方法的分类优越性。

2 相关工作

2.1 相关符号

2.2 相关工作

在多标签学习中，已有许多行之有效的方法处理来自不同领域的多标签数据。基于不同程度的标签相关性可以将这些方法分为一阶策略、二阶策略和高阶策略[3]。一阶策略利用传统的单标签方法处理多标签数据，忽略了标签相关性，其中代表性方法有二元关联（BR,binary relevance）[20]等。由于注意到标签相关性的重要性，研究者开始考虑二阶策略，即利用标签之间的成对关系，相关多标签视频标注（CMLVA,correlative multi-label video annotation）和校准标签排名（CLR,calibrated label ranking）是二阶策略的代表方法[21-22]。高阶策略通常考虑标签子集或所有标签的相关性，其优点是充分考虑了标签相关性，缺点是时间复杂度高且计算量大，如LLSFC-DL（learning label-specific features and class-dependent label）[23]为高阶策略。本文中采用二阶策略。

近年来，图模型在数据结构挖掘方面取得显著成就，受到研究者的广泛关注。典型的图模型是流形学习，其目的是在高维空间嵌入低维空间时，保持数据的几何结构[24]。许多方法都是从样例的角度来考虑流形结构的，即如果Xi.与Xj.具有很强的相似性，那么Yi.与Yj.的相似性也会很强。Ren 等[25]提出了一种无监督特征选择方法来保持实例关联的局部和全局结构。Huang 等[26]提出了一种考虑样例相关性的基于流形的约束拉普拉斯评分方法。Xu等[27]提出了一种半监督多标签特征选择方法，考虑保持特征空间与标签空间的一致性。Chen 等[28]提出的半监督多标签学习方法考虑了样例关联和标签关联。但是，这些利用图模型的方法都严重依赖于固定的图拉普拉斯矩阵，而忽略了特征选择中图拉普拉斯矩阵的动态变化，图拉普拉斯矩阵的不同设定会对后续的更新策略产生不同的影响，尤其是前一次更新造成的误差会被后续的更新不断放大。上述方法也存在利用逻辑标签来指导标签分类的问题，逻辑标签并不能很好地反映相应标签的重要性，而且多标签数据涉及大量标签，导致标签相关性更加复杂，因此特征选择方法无法获得令人满意的分类性能[29]。

多标签特征选择方法广泛采用了一些不同的标准，如基于互信息的方法和基于稀疏学习的方法[8]。本文回顾了几种有代表性的多标签特征选择方法。Lee 等[30]采用可扩展的相关性评估标准来评估条件相关性，提出了一种新的多标签特征选择方法，即大标签集的可扩展准则（SCLS,scalable criterion for large label set）。然而，SCLS 的特征和标签组合呈指数式增长，可能导致性能下降。Jian 等[17]设计了一种基于稀疏化的多标签信息特征选择（MIFS,multi-label informed feature selection）方法，利用标签的局部几何结构和低秩潜在标签矩阵来消除无关特征。MIFS 的形式为

其中，X∈ℝn×d，Y∈ℝn×l，W∈ℝd×c分别表示特征矩阵、标签矩阵和权重矩阵；V∈ℝn×c和B∈ℝc×l分别表示潜在标签矩阵和系数矩阵；L∈ℝn×n表示拉普拉斯矩阵；α、β和γ表示MIFS 方法的3 个正则化超参数；c表示标签的聚类簇数。

Cai 等[31]提出了一种基于稀疏学习的特征选择方法，该方法被称为稳健的增光拉格朗日乘子特征选择（RALM-FS,robust augmented Lagrange multiplier for feature selection）。RALM-FS 对权重矩阵施加l2,0范数，从而获得目标函数如式(2)所示。

其中，1表示元素全为1 的列向量，b表示偏置列向量，q表示所选特征数目。

3 动态图拉普拉斯多标签特征选择方法描述

3.1 设计方法

本节提出一种新的多标签特征选择算法，考虑到图拉普拉斯的动态变化能够提供更有效的指导，并且为避免逻辑标签造成的性能退化，将逻辑标签转化为实值标签，加强挖掘特征选择过程中的标签相关性，使用式(3)所示的学习框架。

其中，第一项表示损失函数；第二项和第三项表示对该损失函数进行正则化处理，帮助减少损失函数造成的损失；F∈ℝn×c表示重构的标签矩阵。

通常，损失函数利用最小二乘回归模型学习从特征空间到标签空间的映射矩阵W，但这种模型对于数据中存在的异常值非常敏感，特别是基于图模型的学习模型对异常值的抗干扰能力非常弱。为获得一个更加稳健的损失函数，本文设计了如式(4)所示的形式。

其中，Θ(W,F)表示关于W和F的函数；W∈ℝd×c表示特征权重矩阵，用于度量特征矩阵X中每一个特征的重要性，即值越大，第i个特征的影响越大；表示l2,1范数，可以有效减少异常值的干扰[18]；Tr(WLF WT)的设计受文献[32]启发，即在多标签学习中保持标签的局部几何结构是至关重要的，本文利用上述图模型来保持标签的局部几何结构。与传统的图模型不同，本文设计的拉普拉斯矩阵LF与重构标签矩阵F紧密相关，L F随F的更新而变化。Tr(WLF WT)的构造过程如下

其中，(N)p(F·j)表示F·j的p个最近邻集合，σ表示热核函数的带宽参数。根据文献[29]可知，传统的有监督多标签方法利用逻辑标签评价输入数据与输出数据之间的相关性，不能很好地反映相应标签的重要性，因此将式(3)中的第二项设计为式(7)所示形式。

其中，α和β表示正则超参数；F∈ℝn×c与逻辑标签矩阵Y同型，但F显然是连续数值型的，这种连续性可以较好地刻画标签的重要程度。将F作为一个更新变量时，为了保证F和Y之间的结构一致性，本文采用常规的图模型对F进行约束。根据W可度量特征矩阵X中每一个特征的重要性这一特性，本文方法能够有效实现特征选择。式(3)中的第三项被设计为可有效实现稀疏化的特征筛选。最终目标函数被构造为式(8)所示形式。

其中，γ表示稀疏化正则超参数，用于调整目标函数的稀疏程度；控制W的行稀疏性[18]。但是行稀疏性并不能总被保证[33]，同时，Y中仅包含0 和1 这2 种非负元素，因此需要避免F的元素负值化。根据上述原因，本文对W和F实施了非负约束，最终的目标函数构造如下

3.2 优化方案

本节设计了一套针对式(9)所示目标函数的简单有效的优化方案。根据分析可以得出，目标函数关于W和F是联合非凸的。由于l2,1范数的存在，导致目标函数存在非光滑性问题。因此，本节提出了一种交替迭代的方法来解决非凸问题，同时引入了一种松弛化方法来处理非光滑问题[18]，获得了拉格朗日函数，如式(10)所示。

其中，L(W,F)表示关于W和F的拉格朗日函数；表示2 个与W和F同型的拉格朗日乘子，这2 项同时将非负约束条件整合到目标函数中，从而方便了优化方案的设计；D1和D2是2 个对角矩阵，其第i个对角元素分别为

其中，ϵ是一个非负的极小常数。对式(10)分别求W和F的偏导数，可得

算法1 中核心步骤为第7)～8)行，这2 个步骤促使算法逐步收敛于最终状态。第12)行中k的取值主要依据文献参考经验值，如MIFS 中所采纳的k值。

3.3 收敛性证明

显然，可以推导出式(20)。

4 实验分析

为了验证所提方法的分类效果，本文在9 个多标签基准数据集上与3 个先进的多标签特征选择算法进行比较。所有实验均在内存为16 GB 的3.4 GHz的英特尔酷睿i7-6700 计算机上进行。

4.1 数据集描述及实验设置

本文实验所用数据均来自MulanLibrary[37]。这些属于不同领域的数据集已经被众多文献使用[11-15]。例如，Birds 数据集是野外条件下采集的鸟类声音数据，其中包括645 个音频记录，与19 种未压缩WAV 格式的鸟类声音相关。Yeast 数据集来自生物领域，该数据集包含2 417 个数据样例，每个样例有103 个特征和14 个标签。Enron 数据集属于文本领域，是安然电子邮件语料库的一个子集。数据集的参数如表1所示。

为了证明所提方法的有效性，将其与MIFS、RALM-FS 和SCLS 这3 种先进的方法进行比较。此外，一些参数需要提前设定。首先，在构造近邻矩阵的热核函数中，参数p和σ分别被设置为c−1和1。为了方便，涉及超参数的各个对比方法中的参数统一在网格{0.01,0.1,0.3,0.5,0.7,0.9,1.0}范围下进行搜索。然后，在五折交叉验证过程中记录参数的最佳值。根据文献，使用BR 模型[20]将多标签问题转化为几个二进制问题，使用线性支持向量机（SVM,support vector machines）分类器和K 最近邻（KNN，K-nearest neighbor）分类器（K=3）进行分类处理，本文采用相同的方式以确保公平性。所有方法的分类性能由2 个评价标准来评估，即基于F1 度量的Micro-F1 和Macro-F1[38]。

其中，z和i分别表示标签数和第i个标签，TP、FP和FN 分别表示真阳性、假阳性和假阴性。Micro-F1和Macro-F1 均是值越大表示相应的方法分类性能越好。为评估所提方法的分类性能，本文在9 个不同的多标签数据集上进行实验。根据一些经验方法[17]，本文使用每个数据集中总特征的前20%来计算不同方法的平均结果和标准偏差。

4.2 实验结果及分析

表2～表5 记录了4 个多标签特征选择方法在9 个数据集上的实验结果。表中每一行最优值用黑色粗体表示。最后一行计算每个特征选择方法下所有数据集的平均值。从表2～表5 可以看出，与其他方法相比，所提方法在所有数据集下分类效果更好。在SVM 分类器的基础上，分别使用评估指标Micro-F1 和Macro-F1 获得所有算法的分类结果，如表2 和表3 所示。从表2 和表3 可以看出，与其他方法相比，所提方法的Micro-F1和Macro-F1在所有数据集平均值均为最优值，分别为0.315 和0.097。

表1 数据集参数

表2 特征选择方法在SVM 分类器上的Micro-F1 结果

表3 特征选择方法在SVM 分类器上的Macro-F1 结果

表4 征选择方法在3NN 分类器上的Micro-F1 结果

表5 特征选择方法在3NN 分类器上的Macro-F1 结果

在3NN 分类器上所有方法的Micro-F1 和Macro-F1 如表4 和表5 所示。从表4 可以看出，所提方法的Micro-F1 平均值为0.325，相对于MIFS、RALM-FS 和SCLS，分别提升了13.6%、21.3%和16.5%。从表5 可以看出，所提方法的Micro-F2 平均值为0.124，相对于MIFS、RALM-FS 和SCLS，分别提升了17.0%、27.8%和22.8%。综上所述，所提方法在不同评估条件下均取得优异的分类表现。为了进一步展示所提方法的分类优势，本文选取6 个代表性的数据集（Arts、Yeast、Enron、Science、Education 和Social）绘制折线分析图，如图1～图4 所示。

通过分析图1～图4，可以直观地看到所提方法相比其他3 个多标签特征选择方法具有最佳分类表现。随着所选特征数目的增加，不同方法的分类性能都总体先增加，后趋于稳定。图1～图4 的曲线都是振荡上升的，产生这种现象的原因如下。所提方法属于序列前向搜索方式的嵌入式特征选择，这种策略通过一定的标准对所有特征进行排序，然后选择k个排名靠前的特征。图1～图4 中，横轴表示所选排名靠前的特征的占比。举例说明如下，通常选择前k个特征导致的分类性能可能会高于选择k−1 个特征，而低于k+1 个特征的性能，这是因为不同的特征子集的组合导致的分类性能是不同的，即前k个单独排名靠前的特征联合导致的分类性能可能低于相互有关联的k个特征组成的子集的分类性能。因此，前k个特征导致的分类性能可能会低于k+1 个特征的性能，但随着特征数目的增加，依然可以导致整体分类性能的提升。这也就导致了曲线振荡上升的现象。同时，可以观察到，图1～图4 中所提方法对应折线总是在最上部，说明所提方法取得了更优异的性能。总体来说，所提方法取得优于对比方法的分类性能，原因是其考虑了特征选择过程中图拉普拉斯矩阵的动态变化，保证每次更新过程中所利用的图拉普拉斯优于上一次的更新，并考虑数值标签刻画标签的重要程度，以便更好地选择特征。

图1 6 个数据集在Micro-F1(SVM)上的实验结果

图2 6 个数据集在Macro-F1(SVM)上的实验结果

图3 6 个数据集在Micro-F1(3NN)上的实验结果

图4 6 个数据集在Macro-F1(3NN)上的实验结果

4.3 参数敏感性分析

为了研究3 个超参数(α,β,γ)在多标签特征选择过程中产生的影响，本文通过搜索网格{0.01,0.1,0.3,0.5,0.7,0.9,1.0}来调整这些超参数。然而，网格搜索策略时间成本过高，为此本文参考文献[17]中的策略，即固定其他超参数，仅调整其中一个超参数。本文设定被固定的超参数值为0.5，选择Education数据集通过SVM 分类器进行超参数敏感性分析，分析结果如图5 所示。图5 中，超参数α在选择的特征数目相同的情况下，在网格范围内波动幅度较小，仅在α=0.1～0.5 时会对模型的分类性能产生影响，根据文献[15,17]，这种程度的影响在实验中是可以接受的，即算法对超参数α的变化不敏感，而且随着选择的特征数目的增加，影响更小。超参数β在选择特征数目相同的情况下，在网格范围内波动幅度较大，即非常敏感，这种敏感程度对算法性能的影响是不能忽略的。因此，超参数β在实际应用中可使用更大范围的网格进行搜索以获得令人满意的性能。相对于超参数α和β，超参数γ选择的特征数目相同情况下，在给定的网格范围内波动幅度最小，因此与超参数α一样，算法对超参数γ的变化不敏感。

图5 在Education 数据集上所提算法关于α,β 和γ 的Micro-F1 和Macro-F1 (SVM)

4.4 收敛性分析与时间复杂度

本节对所提方法的收敛性和时间复杂度进行分析。首先，通过6 个代表性的数据集（Arts、Yeast、Enron、Science、Education 和Social）对所提方法的收敛性进行验证，实验结果如图6 展示。从图6 可以看出，所提方法的迭代收敛速度很快。在前2～3 次迭代中目标函数的损失值快速下降，然后下降速度开始变缓。特别是数据集Yeast 和Enron，仅迭代2 次之后，已无法直接观察到目标函数损失值的变化，但根据分析可知，后面的迭代结果依然接近给定的迭代停止触发条件。同样地，数据集Arts、Science、Education 和Social 上的目标函数损失值也随着迭代次数的增加迅速减小，并最终趋于稳定。实验结果证明所提方法在3.2 节中所设计的优化方案下可有效收敛，同时验证了3.3 节理论证明的正确性。

图6 所提方法的收敛曲线

下面分析所提方法和对比方法的时间复杂度。设p、d、n和c分别表示已选特征数量、特征总数、样例数和标签总数。、SCLS 的时间复杂度为O(dc+pd)；MIFS 在每次迭代的时间复杂度为O(ndl+n2)；由于涉及矩阵的逆运算，RALM-FS的时间复杂度为O(d3)；所提方法的时间复杂度为O(dn2+d2n)。

5 结束语

针对多标签分类和特征选择的结合这一开放性问题，本文提出了一种基于动态图拉普拉斯矩阵的多标签特征选择方法。该方法不同于以往基于图的多标签特征选择方法依赖于固定的图拉普拉斯矩阵，而是利用特征选择过程中可以动态变化的图拉普拉斯矩阵。在图拉普拉斯矩阵的动态变化过程中，由于逻辑标签导致标签信息丢失，而其对应的实值标签能够更好地反映相应标签的重要性，因此在新设计的动态图拉普拉斯矩阵变化下，本文将逻辑标签重构为实数值标签，同时，利用l2,1范数减少动态构造拉普拉斯矩阵时异常值产生的影响。最后，本文设计了一套针对所提方法的简单有效的优化方案。为了验证所提方法的优越性，将其与3 个多标签特征选择方法在9 个不同领域的多标签数据集上进行实验对比。实验结果表明，所提方法性能显著优于对比方法，且可得到高质量的特征子集。下一阶段，将进一步研究在非凸优化问题下的多标签特征选择方法。由于非凸优化问题和多标签问题在现实生活中广泛存在，因此多标签特征选择具有巨大的研究价值。