基于标记权重和mRMR的多标记特征选择

孙林，徐枫 ，王振 ，徐久成

（1.河南师范大学 计算机与信息工程学院，河南 新乡 453007；2.河南师范大学 智慧商务与物联网技术河南省工程实验室，河南 新乡 453007）

0 引言

随着大数据应用的快速发展，处理高维多标记数据已经成为数据挖掘领域亟需解决的关键问题之一［1-2］。在多标记数据中存在许多的冗余与不相关的特征，这些特征一方面给学习算法带来了较高的时间和空间开销，另一方面也降低了分类器的精度和泛化能力［3-4］。在多标记数据处理中，特征选择作为一种重要的预处理工具［5］，可以更好地消除冗余特征，对数据进行处理以获得更好的分类效果［6］。目前，多标记特征选择模型大致可以分为过滤式、封装式和嵌入式模型三种［7］。过滤式模型不需要关注其学习方法，是根据数据的共有属性来选择特征，由于其简捷性和效率上的优势，该模型得到了更多的应用［8］。封装式模型需要针对学习器进行多次特征选择训练，因而其计算开销较大［9］。嵌入式模型结合两者的优点，将特征选择的训练过程和学习算法联合，但缺点是对于某些特定的算法存在较大的局限性［10］。由于封装式与嵌入式模型在特征选择过程中会出现过拟合现象，且其效率并不如过滤式［11］。并且，针对高维数据过滤式模型会更容易实现［12］，本文采用基于过滤式策略进行多标记数据的特征选择。

作为一种非常有效的过滤式特征选择模型，最大相关最小冗余（mRMR）算法在筛选出与分类变量最相关特征的同时，能够使特征之间的差异最大化，进而获取最佳特征组合［13］。截止目前，利用最大相关最小冗余算法处理多标记数据的成果越来越多。张俐和王枞［14］使用互信息和交互信息定义相关性和冗余性，提出了基于mRMR联合互信息的多标记特征选择算法。但是，该算法处理数据的标记数偏少。Lin等［15］考虑多标记特征的依赖性和冗余性，结合互信息与mRMR设计了多标记特征选择算法。但是，该算法没有考虑标记之间的相关性和互依赖性。Huang等［16］将邻域分类精度与mRMR结合，提出了基于Relief和mRMR的邻域粗糙集多标记特征选择算法。Fan等［17］利用岭回归创建特征选择矩阵和低维嵌入，并通过余弦相似性分析特征冗余度，提出了一种基于标记相关性和特征冗余的多标记特征选择算法。但是，上述两种算法计算开销较大。Sun等［18］基于模糊邻域粗糙集和mRMR提出了一种缺失标记特征选择算法。但是，该算法并没有充分考虑标记与标记之间的权重。为解决该问题，本文利用标准互信息计算标记与标记之间的关联度，使用每个标记和标记集关联度占所有标记与标记集之间关联度之和的比例定义标记权重，进而计算特征与标记之间的关联度，结合标记权重改进最大相关性，使用新的mRMR算法进行多标记特征初选，获取候选特征子集。

尽管mRMR算法在多标记特征选择方面取得了一些研究成果，但是大多数算法并没有充分考虑标记之间以及特征与标记集之间的相关性。例如，李田力等［19］利用模糊熵计算特征与标记之间的相关性，提出了一种标记不平衡性的多标记粗糙互信息特征选择方法，但是该方法没有完全考虑到标记之间的相关性。唐莉等［20］利用样本的分类间隔及差异性度量特征的重要性，提出了一种基于样本差异性的多标记特征选择算法。王晶晶和杨有龙［21］提出了一种针对弱标记数据的多标签分类算法，通过迭代训练样本的权重并考虑标记之间的相关性恢复缺失的标记信息。但是上述两种算法没有涉及到特征与标记集之间的相关性。蔡亚萍和杨明［22］通过标记相似度衡量两个样本标记集的相似度，提出了结合局部标记相关性的多标记特征选择算法，但是该算法对于不同的测试样本有不同的标记相关，会增加时间开销。魏葆雅等［23］使用标记对样本的可分性赋予标记权重，基于核映射后的特征空间来度量特征对样本的可分性，但该模型未考虑特征与标记之间的相关性。针对此问题，计算特征与标记之间的标准互信息，结合关联度占比定义的标记权重，设计特征与标记集之间的相关度公式，在最初候选特征子集基础上进一步剔除冗余特征，以获取最优特征子集。

针对多标记高维数据集，为解决现有mRMR算法没有充分考虑标记之间和特征与标记集之间的相关性，以及没有有效计算标记与样本的可分度等问题，本文提出基于标记权重和mRMR的多标记特征选择方法。首先，运用标准互信息计算每个标记与标记集的关联度，由关联度占比定义新的标记权重；然后，计算特征与标记之间的关联度，结合标记权重改进最大相关性，基于标准互信息定义最小冗余性，构建新的mRMR评价准则，获取最初的候选特征子集；最后，计算特征与标记之间的标准互信息，结合标记权重，计算特征与标记集之间的相关度，进一步剔除冗余特征，筛选最优特征子集，提升算法的分类性能。

1 基础理论

假设 MLDS = 是一个多标记决策系统［24］，其中 U = ｛x1，x2，…，xn｝表示由n个样本构成的样本集；F表示特征集和L表示样本对应的标记集，T = ｛（xi，yi）|i = 1，2，…，n｝表示在标记上的映射关系。每个样本由f维表示，记为xi∈Rf，对应的标记集由向量yi∈｛0，1｝l表示，其中 l∈L。如果 xi有第 l个类别标记，则yi（l） = 1，否则yi（l）= 0；且∑yi≥ 1。

在MLDS = 中，任意样本xi∈X⊆U，i = 1，2，…，n，p（xi）为样本 xi的先验概率，则样本X的信息熵［25］可以表示为：

在MLDS = 中，任意样本子集 X 和 Y⊆U，xi∈X 和 yj∈Y，i，j = 1，2，…，n，p（yj|xi）为条件先验概率，Y在给定X下的条件熵［25］表示为：

X和Y的互信息量表示已知Y的条件下，X不确定性的改变量，从统计学角度反映了X和Y的关联程度，所以X和Y的互信息［25］可表示为：

2 基于mRMR的多标记特征选择算法

2.1 标记权重

在多标记数据中，每个样本可能同时隶属于多个类别标记，而每个类别标记对样本有着不同程度的可辨别性［26］。因此，本文通过对标记赋予一定的权重来探索各类别标记对样本的可区分性程度。

定义1 在 MLDS = 中，L = ｛l1，l2，…，lz｝表示含有 z个标记的集合，li∈L，i =1，2，…，z，基于标准互信息计算标记与标记集之间关联度，其计算公式为：

2.2 改进的mRMR

mRMR是基于互信息的特征选择方法，根据最大统计依赖性准则选择重要特征［13］。为解决传统mRMR算法没有充分考虑标记权重，从而导致去除最小相关冗余特征后带来的分类精度下降的问题，本文将标记权重与mRMR结合，并将其运用于多标记特征选择中。

定义3 在 MLDS = 中，F = ｛f1，f2，…，fn｝，fj∈F，j = 1，2，…，n，L =｛l1，l2，…，lz｝，li∈L，i =1，2，…，z，结合标准互信息计算特征与标记之间的关联度，其表达式为：

定义4 在 MLDS = 中，F = ｛f1，f2，…，fn｝，fj∈F，j = 1，2，…，n，L =｛l1，l2，…，lz｝，l∈L，结合特征与标记之间的关联度和标记权重定义最大相关性，其计算公式为：

定义2 在 MLDS = 中，L = ｛l1，l2，…，lz｝，li∈L，i =1，2，…，z，使用每个标记与标记集关联度占所有标记与标记集之间关联度之和的比例定义标记权重，其计算公式为：

定义5 在 MLDS = 中，F = ｛f1，f2，…，fn｝，fi，fj∈F，i，j = 1，2，…，n，基于特征与特征之间的标准互信息定义最小冗余性，其计算公式为：

定义6 在 MLDS = 中，F = ｛f1，f2，…，fn｝，L = ｛l1，l2，…，lz｝，l∈L，基于最大相关性和最小冗余性定义新的mRMR，其计算公式为：

2.3 相关度

为了解决没有考虑特征和标记之间的相关度而造成分类精度不高的问题，引入特征和标记之间的互信息并结合标记权重，计算特征与标记集之间的相关度，有效筛选与标记集相关度较高的特征子集。

定义7 在 MLDS = 中，F = ｛f1，f2，…，fn｝，f∈F，L = ｛l1，l2，…，lz｝，li∈L，i = 1，2，…，z，结合标准互信息和新的标记权重计算特征f和标记集L之间的相关度，其计算公式为：

2.4 算法描述

为了设计基于标记权重和mRMR的多标记特征选择算法（Multilabel Feature Selection Us⁃ing Label Weight and mRMR， MFSLM），首先计算每个标记与标记集之间的关联度，并根据关联度的占比计算标记权重；然后使用改进后的mRMR得到初选多标记特征子集；最后，结合互信息和标记权重计算每个特征与标记集之间的相关度，通过相关度降序排序特征，进而得到最终筛选的最优特征子集。其详细伪代码描述如算法1。

算法1 MFSLM算法

输入：MLDS =

输出：最优特征子集R0

步骤1. For 每个标记l∈L

步骤2. 通过式（5）计算标记权重W（li）

步骤3. End For

步骤4. For 特征子集R1

步骤5. 根据式（9）计算NMR（R1）

步骤6. End For

步骤7. 对NMR值进行排序并选择排序较前的作为最初筛选的特征子集R1

步骤8. For 每个特征f∈F

步骤9. For 每个标记l∈L

步骤10. 根据式（10）计算特征和标记集之间的相关度CDE（f， L）

步骤11. End For

步骤12. End For

步骤13. 根据特征和标记集之间的CDE（f， L）值筛选出最终特征子集 R0（|R1|≥2|R0|）

步骤14. Return 最优多标记特征子集R0

在MFSLM算法中，假设多标记数据集包括m个样本、n个特征和t个标记。在筛选模块1中，步骤1至步骤3计算标记权重的时间复杂度为O（mt），步骤4至步骤6计算新的mRMR值的时间复杂度为O（n2+nt）；在筛选模块2中，步骤8至步骤12计算特征与标记集之间的相关度的时间复杂度为O（nt），其中步骤7和步骤13为两次筛选特征子集的时间复杂度为O（nlogn）。由分析可知，该算法总的时间复杂度为 O（n2+nt+mt）。

3 实验结果及分析

3.1 实验准备

为验证本文MFSLM算法的有效性，在Mu⁃lan数据库（http：//mulan.sourceforge.net）中选取了8个多标记数据集，数据集的具体信息如表1所示。参考文献［19］和文献［26］，对这些多标记数据集进行了划分，分为训练数据集和测试数据集。

参照文献［27］，本文实验使用5个常用的多标记评价指标：平均分类精度（Average Preci⁃sion，AP）、汉明损失（Hamming Loss，HL）、1错误率（One Error，OE）、覆盖率（Coverage，CV）和排序损失（Ranking Loss，RL），验证对比算法的分类性能。其中，AP值越大效果越好（1为最优），其他指标越小效果越好（0为最优）。为后续结果的观察方便，使用“↑”表示实验结果越大越好，“↓”表示实验结果越小越好。使用多标记K最近邻（K Multilabel k-nearest neigh⁃bor， ML-KNN）作为多标记特征选择后的分类器，其中近邻个数为10，平滑参数为1，分类后的结果验证多标记特征选择算法的实验效果。实验环境为Windows 10、CPU inter i7-4790 3.60 GHz、8.00 GB和MATLAB R2019a。

3.2 ML-KNN分类器上的实验结果分析

在本节实验的第一部分是将MFSLM算法与其他4种多标记特征选择算法做对比分析，包括：基于AP聚类和互信息的弱标记特征选择 算 法 （Weak label feature selection method based on AP clustering and mutual information，WFSAM）［28］、基于标记相关性的多标记特征选择算法（Multi-label feature selection with label correlation algorithm， MUCO）［29］、基于最大相关性的多标记维数约简算法 （Multi-label dimen⁃sionality reduction algorithm via dependence maxi⁃mization， MDDMspc）［30］和基于阵营的多标记特征选择算法 （Alignment based feature selection algorithm for multi-label learning， MFS-KA）［31］。从表1中选择3个代表性数据集：Yeast、Enron和 Reference，采用 5个指标（AP、CV、OE、HL和RL）评估上述5种比较算法的分类性能。图1为实验结果对比图，其中横坐标和纵坐标分别表示所选特征的个数（Number of selected fea⁃tures， N）和5个评价指标的分类结果。为了更清晰地展示上述5种算法的最优结果，表2给出了在3个数据集上5种算法在5个评价指标上的最佳实验结果。

由图1可知，在AP指标下，在Yeast数据集上，当N = 10时，MFSLM算法略差于WFSAM算法，优于其他3种算法，但在其余情况下均为最优；在Enron数据集上，当N = 100时，MF⁃SLM算法差于MFS-KA算法，优于其他3种算法，当N = 300时略差于WFSAM算法，但在其余情况下均为最优；在Reference数据集上，当50 ≤ N ≤ 200时，MFSLM算法差于WFSAM、MUCO和MFS-KA这3种算法，当250 ≤ N ≤400时，MFSLM算法与MUCO和MFS-KA这2种算法基本持平，当N > 450时均为最优。在CV指标下，在Enron数据集上，MFSLM算法明显优于其他算法；在Yeast数据集上，当N > 30时，MFSLM算法均为最优；在Reference数据集上，仅在N = 450或N = 500时为最优。在HL指标下，在Yeast数据集上，MFSLM算法均优于其他算法；在Enron数据集上，当N = 200或N = 300时，MFSLM算法差于MFS-KA与WFSAM这2种算法，当N > 400时，MFSLM算法远优于其他4种算法；在Reference数据集上，当 50 ≤ N ≤ 450时，MFSLM 算法略差于MFS-KA与WFSAM这2种算法，与MUCO算法相差不大，当450 ≤ N ≤ 650时，MFSLM算法优于其他4种算法。在OE指标下，在Yeast数据集上，MFSLM算法与WFSAM算法基本持平，明显优于其他算法；在Enron数据集上，当N > 400时，MFSLM算法明显优于其他算法；在Reference数据集上，在N < 450时，MF⁃SLM算法略差于WFSAM、MUCO和MFS-KA这3种算法，但当N > 450时优于其他4种算法。在RL指标下，在Enron数据集上，MFSLM算法均为最优；在Yeast数据集上，当N > 10时，MFSLM算法优于其他算法；在Reference数据集上，当450 ≤ N ≤ 650时，MFSLM算法优于其他算法。从表2中看出，在CV、HL和RL这3个指标下，MFSLM算法均表现最优。在AP和OE指标下，在Yeast和Enron数据集上，MFSLM算法均为最优，但由于Reference数据集是稀疏矩阵数据集，说明MFSLM算法在稀疏矩阵上的效果表现不好，致使MFSLM算法略差于WFSAM算法。从整体来分析，MFSLM算法相对于其他4种比较算法是有效的。

基于最大相关性的多标记维数约简算法（MDDMproj）［30］、基于 ReliefF 的多标记特征选择算法（ReliefF for multilabel feature selection al⁃gorithm， RF-ML）［32］和基于标记权重的多标记特征选择算法 （Multilabel feature selection algo⁃rithm based on label weighting， LWMF）［26］。从表1中选择3个代表性数据集Yeast、Education和Arts，采用4个指标（AP、CV、HL和RL）评估比较算法的分类性能。图2是实验结果的对比图，其中纵坐标和横坐标含义与图1相同。为了更清晰地展示上述6种算法在这3个数据集上的最优结果，表3给出了在3个数据集上6种算法在4个评价指标下的最佳实验结果。

由图2可知，在AP指标下，在Yeast数据集上，当 40 ≤ N ≤ 100时，MFSLM 算法略差于WFSNR 算 法 ，在 30 ≤ N ≤ 70时 略 差 于LWMF算法，但优于其他算法；在Arts数据集上，MFSLM算法优于其他算法；对于Education数据集，当 50 ≤ N ≤ 300时，MFSLM 算法均优于其他算法。在CV指标下，在Yeast数据集上，当N = 30时，MFSLM算法为最优，在其他情况下略差于WFSNR算法和LWMF算法；在Education数据集上，当350 ≤ N ≤ 450时，MF⁃SLM算法差于LWMF算法，在400 ≤ N ≤ 500时略差于WFSNR算法，但优于其他算法；在Arts数据集上，MFSLM算法基本表现最优。在HL指标下，在Yeast和Education这2个数据集上，仅有少数情况MFSLM算法略差于LWMF算法，其余情况都优于其他算法；在Arts数据集上，MFSLM算法均为最优。在RL指标下，在Yeast数据集上，MFSLM算法与LWMF算法差距不大，在50 ≤ N ≤ 100时略差于WFSNR算法，但仍优于其他算法；对于Education数据集，当 50 ≤ N ≤ 300时，MFSLM 算法优于其它算法；在Arts数据集上，在450 ≤ N ≤ 500时，MFSLM算法略差于WFSNR算法和MFSR算法，但均优于其他算法。从表3中看出，在CV、HL和RL这3个指标下，MFSLM算法均为最优。在AP指标下，在Education和Arts这2个数据集上MFSLM算法为最优；但由于Yeast数据集是缺失数据填补常用数据集，WFSNR算法填补大部分缺失标记，致使MFSLM算法略差于WFSNR算法。从整体来看，MFSLM算法相比于其他5种算法是有效的。

为进一步展示MFSLM算法在不同数据集上的有效性，选择文献［19］中的5种对比的多标记特征选择算法：标记不平衡性的多标记粗糙互信息特征选择算法（Multilabel feature selec⁃tion use rough mutual information with imbalance lable，MFS-RMI-IL）［19］、基于多变量互信息的多标记特征选择算法（Pairwise multivariate mu⁃tual information，PMU）［33］、基于最大相关性的多标记约简算法（MDDMspc和 MDDMproj）［30］和基于局部子空间的多标记特征选择算法（Multilabel feature selection algorithm base on lo⁃cal subspace， MFSLS）［34］，从表 1 中选择 4 个代表性数据集：Arts、Health、Society和Science。表4描述了6种算法在4个指标下的实验结果。

从表4中看出，在AP指标下，MFSLM算法表现均优于其他5种算法；尤其在Society数据集上，MFSLM算法比次优的MFS-RMI-IL算法高0.030 6；在OE指标下，MFSLM算法结果均最为优异；尤其是在Society和Science这2个数据集上，MFSLM算法比次优的MFS-RMI-IL算法分别低0.032 7和0.038。在HL指标下，MFSLM算法在Health和Society数据集上均优于其他算法；在Arts和Science数据集上，MF⁃SLM算法与最优的MFS-RMI-IL算法仅差0.000 3和0.000 1。究其原因是：HL指标的重点可能只是针对单个标记的分类效果，没有考虑标记间的相关性和标记间的分布，而MF⁃SLM算法考虑了标记间的相关性。在RL指标下，MFSLM算法都取得了最优值；尤其是在Society数据集上，MFSLM算法比次优的MFSRMI-IL算法低0.012 9。

从上述实验结果分析可知，MFSLM算法在对多标记数据进行特征选择时表现出优异的分类性能。

3.3 统计分析

使用 Firedman 检验［24］和 Nemenyi测试［35］分析所有实验结果的统计意义。Firedman检验的计算公式为：

参考文献［35］的统计计算方法，表2中的实验结果对应的统计结果如表5所示，CD图如图3所示。在显著水平α = 0.1时，则qa=2.459，CD = 3.174 6，其中s = 5和 T = 3。从图3可以看出，MFSLM算法在5个指标上均为最优。表3中的实验结果对应的统计结果如表6所示，CD图如图4所示。在显著水平α = 0.1时，则 qa= 2.589，CD = 3.756 2，其中 s = 6和T = 3。从图4看出，MFSLM算法在4个指标上均为最优。表4中的实验结果的统计结果如表7所示，CD图如图5所示。在显著水平α =0.1时，则qa= 2.589，CD = 3.253 0，其中s = 6和T = 4。由图5可知，MFSLM算法在4个指标上均为最优。

4 结论

为有效处理多标记数据，本文提出了一种基于标记权重和mRMR的多标记特征选择算法。算法首先基于标准互信息计算标记之间关联度，结合特征与标记之间的关联度和标记权重，定义了新的最大相关性，构建新的mRMR算法，初次筛选特征子集；然后，计算特征与标记之间的标准互信息，结合标记权重计算特征与标记集之间的相关度，在最初候选特征子集基础上进一步剔除冗余特征，筛选最优特征子集，提高特征与标记之间的相关性，从而提升算法的分类性能。在8个多标记数据集上的实验结果表明，MFSLM算法在对多标记数据进行特征选择时，其分类性能得到了有效提升。但是，本文算法未充分考虑特征与特征集之间的关联性，因此在处理大规模多标记数据集时仍然存在一定的缺陷。在未来工作中，针对大规模多标记数据集，如何提升多标记特征选择的时效性是今后研究的方向。