基于标记增强和模糊辨识度的标记分布特征选择
2021-06-22熊传镇钱文彬王映龙
熊传镇，钱文彬，2，王映龙
（1.江西农业大学计算机与信息工程学院，南昌330045；2.江西农业大学软件学院，南昌330045）
引 言
在传统的监督学习框架中，训练数据中的示例是由单个标记所描述。这种监督学习被称作单标记学习。然而，在现实应用领域中，许多数据往往同时含有多个类别标记，即每个示例可能存在多个语义与之相关联。例如，一个人在某个时刻的表情可能包含多种复杂情绪（快乐、悲伤和愤怒等）；一幅美丽的风景画可能描绘了多重的景色（天空、海水和沙滩等）；一本杂志中可能包含着丰富多样的内容（时尚、运动和科技等）。由于数据的语义多义性，使得传统的单标记学习方法具有局限性。为此，多标记学习作为机器学习的重要范式［1］，它能有效处理语义丰富的多标记数据。近年来，多标记学习已经成为了文本分类［2］、图像识别［3］等多种应用领域中的研究热点。对于多标记数据而言，示例的特征往往呈现高维性特点。在多标记数据的高维特征中，可能存在某些不相关或者冗余的特征，这些特征使得模型的复杂度和计算的时间消耗显著提升，从而影响多标记学习的分类性能和泛化能力。为了有效地解决高维多标记数据存在的维度灾难问题，可在学习任务前采用特征选择方法来分析高维特征中的无关或冗余特征，可缩短学习模型的计算时间，并使模型更具有可解释性和可扩展性。在多标记分类中，特征选择已成为数据预处理的重要步骤。
粗糙集理论作为代表性的粒计算模型［4］，一直以来在特征选择任务中受到广泛关注和研究［5⁃6］，其特点是无需提供数据本身以外的任何先验知识，可直接从数据中剔除大量冗余或不相关的特征，对知识的描述和分析也更客观。由于经典的粗糙集只能处理名义型数据，难于直接处理连续型数据。为此，Dubois和Prade提出了模糊粗糙集用以处理混合型数据问题［7］。与粗糙集中的逻辑等价关系不同，模糊粗糙集使用模糊相似关系进行信息粒度的划分，无需对数据离散化，可直接描述连续型数据中示例的相似性。由于模糊粗糙集模型的灵活性和普适性，在知识发现领域中取得了许多有意义的研究成果［8⁃10］。
对于多标记学习而言，假定数据中示例的相关标记之间的重要度都是相等，标记是以逻辑值的形式描述；然而，在许多应用领域中，每个示例含有的标记的重要程度往往不同。为解决上述问题，耿新等提出了标记分布学习的机器学习范式［11⁃12］，能有效地解决重要程度不同的标记多义性问题。相较于传统的逻辑值标记，标记分布数据中包含更丰富的分类信息。但由于现实世界中往往难以直接获取标记的分布信息，需利用标记增强方法把多标记数据的逻辑标记转化为标记分布数据。为此，本文提出了一种基于模糊相似性的标记增强算法，将传统的多标记数据转化为标记分布数据；分析了标记分布数据中标记的差异性和特征的模糊相对辨识关系，给出了在标记空间和特征空间上的模糊辨识度，并构造了衡量特征关于标记分布数据辨识能力的特征辨识重要度；在此基础上，设计了面向标记分布数据的特征选择算法。在多个Mulan数据集上的实验分析表明，经过标记增强后的特征选择算法能够有效地提升分类效果。
通过对多标记高维数据进行特征选择，可以减少算法的训练时间和增强学习算法的分类性能。近年来，多标记特征选择方面已取得许多有意义的研究成果。Spolaor等将ReliefF算法应用于多标记学习中，提出了Relief⁃ML特征选择算法［13］。Zhang等通过利用最大化特征和相关类之间的依赖关系，构造了MDDM算法用以实现特征选择［14］。此外，Lee等通过所选特征与标记间的互信息设计了PMU特征选择算法［15］。Xu等基于排序损失提出了标记对比转换方法，并与卡方统计结合设计了特征选择方法［16］。Teisseyre基于马尔科夫网络构建了标记与特征之间的依赖关系来获得特征子集［17］。近年来，模糊粗糙集作为粒计算理论中的重要工具，在多标记学习中也受到了越来越多研究人员的关注。例如，为解决LIFT算法中特征冗余的问题，Xu等将LIFT算法与模糊粗糙集结合，提出了FRS⁃LIFT特征选择算法［18］。同时，Lin等引入模糊互信息用以评估多标记数据中特征的重要性，并设计了一种考虑标记相关性的多标记特征选择算法［19］。可知，模糊粗糙集是一种有效的多标记特征选择模型。
上述的多标记特征选择的研究中，对于多标记数据采取的都是均匀分布假设，即每个示例含有的标记重要程度相同。事实上，对于现实生活中的每个示例来说，不同的标记对于示例的描述程度是不一样的。为此，耿新等［11］提出了标记分布学习的概念，主要研究现实世界的多标记学习中更深一层的学习问题“每个标记如何描述该示例？”，即每个示例中相关标记的相对重要度该如何描述。在文献［12］中，Xu等归纳总结了多种标记增强算法，将多标记数据中的逻辑标记转换为由实值表达的标记分布数据。相较于传统的逻辑标记，标记分布能够在多标记数据中挖掘出更多隐藏的监督信息，能够有效地提升多标记特征选择中的分类效果。作为一种新的机器学习学习范式，标记分布学习已在各个领域中受到越来越多的关注。在文献［20］中，He等提出了一种完全数据驱动的标记分布学习方法来自适应地学习潜在的标记分布，该方法能够根据人脸示例的局部上下文结构，发现跨年龄相关分析中的内在年龄分布模式。与此同时，Liu等采用结构化的低秩逆协方差方法来预测视觉情感的标记分布［21］。此外，Zhao等提出了一种基于最优传输理论的标记分布学习和标记相关性挖掘的方法［22］，并基于Sink⁃horn距离提出了标记分布学习的数据依赖风险的边界分析。这些研究表明，标记分布能够挖掘出更加深层的潜在信息，能更好描述现实数据中的相对关系。
1 基础知识
1.1 多标记学习与标记增强
在标记分布学习中，通过对标记的更加丰富的描述，不仅能够最大限度地描述数据和标记之间的关联性，而且能够挖掘出更多的潜在信息。由于难以直接获取标记的分布信息，这些标记分布主要是在多标记数据集上通过标记增强获得。对于多标记数据集T={(x i，Y i)|1≤i≤n}，标记增强的目标是通过标记之间的相关性将原先的逻辑标记Y i转化为标记分布D i，获得标记分布数据S={(x i，D i)|1≤i≤n}。
1.2 模糊粗糙集与模糊辨识矩阵
在传统的粗糙集理论中，主要是通过等价关系IND(B)={(x，y)|∀a∈B，a(x)=a(y)}将论域划分为多个等价类[x]B={y|(x，y)∈IND(B)}。然而，在许多现实应用中，数据往往是数值型或混合型的。使得等价关系IND(B)的处理能力存在一定局限性。为此，模糊粗糙集可有效处理此类数据。
定义1定义决策表为
结合模糊隶属度，对于任意特征a∈C，可定义其对应模糊二元关系R a。如果模糊二元关系R a满足下列条件，可称之为模糊相似关系［8］：（1）自反性：R a(x，x)=1；（2）对称性：R a(x，y)=R a(y，x)。
2 模糊标记增强和相对模糊辨识关系
2.1 基于模糊相似性的标记增强
为了将原始的逻辑标记空间转化成标记分布空间，需利用标记增强方法对原始的标记集合进行转换。为此，本文引入了不同示例间关于标记的模糊相似性来刻画原逻辑标记的模糊性。
定义4设多标记决策表为
2.2 模糊辨识相对关系和特征评价指标
不同于传统辨识矩阵，在模糊辨识矩阵中，通常使用辨识度从不同的角度来衡量特征的重要性，如最大可辨识对［23］、最小元素［24］等方法。这些方法的核心思想都是衡量特征在不同示例对中的辨识能力。为此，本文提出了一种泛化的模糊辨识模型，通过计算特征关于每个示例对的相对辨识能力（模糊相对辨识度FRD），获得特征在论域上的整体辨识能力。
定义5设多标记决策表
可知，模糊相对辨识度FRDa(x，y)满足对称性，且随模糊辨识度disa(x，y)单调递增，其值域为［0，1］。给定阈值λ，可以定义多标记数据中示例对上具有强辨识能力的特征集合，记为相对辨识特征RDFλ(x，y)，其描述如下
性质1多标记决策表
证明：（1）由模糊相对辨识度的对称性可知。
（2）由定义5可知，设阈值为0≤λ1≤λ2≤1，对于相对辨识特征RDFλ2(x，y)中的任意特征a，其模糊相对辨识度FSDa(x，y)>λ2，其一定也满足模糊相对辨识度FSDa(x，y)>λ1，可得a∈RDFλ1(x，y)；反之，则不成立。故可得出RDFλ1(x，y)⊇RDFλ2(x，y)。
对于任意特征a∈C，统计其所在的相对辨识特征集合，可定义相对辨识关系
通过矩阵RDM，可以衡量特征a对于论域U上的示例对的相对辨识能力。辨识能力依靠的是每个示例对的模糊相对辨识度，故减少了数据不平衡性带来的影响，从而能够合理刻画特征对于不同示例对的辨识能力。
然而，由于在标记分布数据中不同的示例对之间的标记差异性往往不同，为此需要在标记分布中定义标记的差异性（disL），用于衡量不同示例对之间在标记空间上的差异性，定义如下。
定义6设U={x1，x2，…，x n}为示例空间，L={l1，l2，…，l q}为标记空间的集合。对于任意示例对(x，y)∈U×U，其标记差异性disL(x，y)定义为
在论域U上，给定标记差异矩阵LDM，其大小为|U|×|U|，其描述如下
通过标记差异性矩阵LDM，可以得到整个标记空间上的示例对之间的差异性。结合示例空间关于特征a的相对辨识度和在标记空间上的标记差异性，可以衡量特征a对于不同标记差异性的示例对之间的相对辨识能力，记作RDAλ(a)。
定义7给定非空论域U，条件特征集合C。对于任意特征a∈C，其特征相对辨识能力RDAλ(a)为
性质3设特征集合为C。对于任何特征a∈C，其辨识重要度DSλ(a)满足如下性质：（1）0≤DSλ(a)≤1；（2）0≤λ1≤λ2≤1，DSλ1(a)>DSλ2(a)。
对于标记分布数据而言，特征的辨识重要度DSλ(a)能够适应标记分布学习中的实值标记，并在特征空间和标记空间上综合考虑特征的辨识能力。对于特征a而言，其辨识重要度DSλ(a)的值越大，其在特征集合中的重要程度越高。
3 算法描述
基于上述方法，可通过基于模糊相关性的标记增强方法将传统多标记数据转化为标记分布数据；在此基础上，结合模糊相对辨识关系和标记之间的差异性，可计算特征在标记分布数据上的辨识重要度；最后，构造了一种基于标记增强和模糊辨识关系的标记分布特征选择算法（Label enhancement and fuzzy discernibility based label distribution feature selection algorithm，LDFS），算法根据辨识重要度排序，可获得具有强辨识能力的特征选择结果。算法的具体描述如下：
算法 基于标记增强和模糊辨识度的标记分布特征选择算法。
输入：多标记决策表
输出：特征排序集合S。
（1）对多标记数据进行标记增强
①∀x i∈U，计算其模糊标记相似性集合FLS(x i)；
②构建标准化的模糊标记关联强度矩阵SFLA；
③对关联度矩阵SFLA进行规约和约简，获得每个示例x i关于标记l k∈L的标记分布d k x i；
（2）构建标记差异性矩阵LDM；
（3）对于∀a∈C，计算其关于示例对模糊相对辨识度，执行如下操作：
①∀(x，y)∈U×U，计算其在特征a∈C的模糊辨识度disa(x，y)；
②将每个示例对(x，y)中的模糊辨识度归一化得模糊相似度FRD(x，y)；
（4）根据阈值λ，计算每个特征a∈C的相对辨识关系RDPλ(a，U*)，并构建其相对辨识矩阵RDMλa；
（5）计算每个特征a∈C，计算其相对模糊辨识能力RDAλ(a)；
（6）计算每个特征a∈C的辨识重要度DSλ(a)；
（7）将特征按照辨识重要度降序排列；
（8）输出特征排序集合S。
（9）结束
步骤1主要是进行对多标记数据进行标记增强，首先计算示例模糊相似性向量，其时间复杂度为O(|U|2)，在此基础上构建关联度矩阵SFLA，时间复杂度为O(|U||L|)，在进行规约和约简后，可获得了示例的标记分布信息，时间复杂度为O(|U||L|)。在步骤2中，构建标记分布数据的标记差异性矩阵LDM，时间复杂度为O(|U|2)。在步骤3与步骤4中，计算了每个特征的模糊相对辨识度和相对辨识矩阵，时间复杂度为O(|C||U|2)。然后，在步骤5中运用矩阵运算计算每个特征的相对模糊辨识能力RDAλ(a)，时间复杂度为O(|C||U|2)。最后，在步骤7和步骤8中获得了每个特征的辨识重要度，按重要度对特征进行排序，时间复杂度为O(|C|)。综上所述，算法的时间复杂度为O(|C||U|2)。
4 实验与结果分析
4.1 实验数据集
为了验证算法的可行性与有效性，在Mulan数据集中选取了8个数据集，这些多标记数据来自不同的应用领域，其数据描述如表1所示。表中的数据集都为数值型数据或混合型数据。其中，Types中的Continuous表示数据集中的数据皆为连续型数据；Both表示数据集中的数据为离散或连续的混合型数据。为了实验的规范性，对连续型数据进行归一化处理，使其值域在范围［0，1］中，离散型数据则无需处理。归一化公式定义如下
表1 实验数据集描述Table 1 Description of experimental datasets
式中：表示样本x i在连续型特征a上的值；n表示论域的大小。
算法运行的硬件配置为Inter（R）Core（TM）i5⁃6500 CPU@3.20 GHz处理器，8 GB内存，操作系统为Windows 10，编程环境为Python 3.7。
4.2 评价指标
由于多标记学习标注结构的复杂性，本文选取了5个通用的多标记评价指标来分析算法的分类性能，包括汉明损失（Hamming loss）、1⁃错误率（One⁃error）、平均准确率（Average precision）、覆盖率（Cov⁃erage）及排序损失（Ranking loss）。通过这些评价指标，可以从多个不同的角度来评价算法的分类性能。
在多标记训练集为T={(x i，Y i)|1≤i≤n}，Y i表示与示例x i相关联的真实标记集合。设在多标记学习中示例x i的预测标记集合为Y'i，多标记评价指标定义如下。其中，符号“↑”（“↓”）表示分类性能随指标值增大而提升（降低）。
（1）汉明损失：衡量示例的预测标记中标记错误的平均个数
式中：符号⊕表示两个集合之间的对称差，L表示所有标记的集合，|⋅|表示集合的大小。汉明损失值越小，分类性能越好。
（2）1⁃错误率：统计满足预测标记排名中的最优标记不在真实标记集合里的示例占总体示例的比例，即
式中：r(x i，l)表示通过算法对标记预测获得的排序值，值越小，排名越前；
（3）平均准确率：计算预测标记中排在特定真实标记前面的标记同时也是真实标记的比例，即有
平均准确率值越大，分类性能越高。
（4）覆盖率：表示在预测标记序列中搜索到所有真实标记所需要的平均搜索深度
在上述的5个评价指标中，除了覆盖率，其余各项指标的值域都为［0，1］。在这些指标中，平均准确率与分类效果呈正相关，其他的4个指标都为指标值越小分类性能越优。根据评价的视角，可以将上述的指标分为两类：一类主要关注的是真实标记与预测标记之间的排序对比，包括1⁃错误率、平均准确率、覆盖率、排序损失；而汉明损失主要关注的是真实标记与预测标记之间差异性。
4.3 实验设置
本节对实验步骤和参数设置做详细描述。首先定义数据集上的模糊相似关系。对于数值型特征，其模糊相似关系定义为
对于符号型特征，其模糊相似关系定义为
在实验过程中，选取了4个多标记特征选择方法：Relief⁃ML［13］、MDDMproj［14］、MDDMspc［14］和PMU［15］，与本文的算法LDFS进行比较分析。同时选择MLKNN［25］作为多标记分类器，设置其邻域粒度k=10，平滑参数σ=1。并采用10折交叉验证的方式来获取对应的实验结果。另外，为了保证所有算法之间的统一性，设原始特征空间大小的r%作为特征子集的大小，其特征选取比例r%定义为［26］：（1）如果d<100，r=40；（2）如果100≤d≤500，r=30；（3）如果500≤d≤1 000，r=20；（4）如果d≥1 000，r=10。其中d表示原始特征空间大小。
考虑到参数对特征选择算法的影响，对经典特征选择算法的参数设置如下：对于MDDMproj和MDDMspc算法，参考文献［14］所示的默认参数设置，设置正则化参数为0.5；对于算法PMU，按照等宽策略将连续值数值进行两折离散［15］。
与此同时，对本文算法LDFS中的阈值λ进行分析，为了获取合适的阈值，将阈值按步长0.05从0到1进行实验分析以选出合适的阈值。在分析的过程中，当算法在多个评价指标上表现最优时，认定对应的阈值λ为最佳阈值。图1描绘了数据集Emotions随着阈值变化时分类性能的变化情况。综合考量多标记学习中的5个评价指标，Emotions数据集在阈值λ=0.6时能获取最佳的分类性能。依据类似的实验分析，可以得到关于其他数据集的最佳阈值参数。
图1 Emotions数据集分类效果随阈值变化情况Fig.1 Variation of the classification performance with the threshold for Emotions dataset
4.4 实验分析
通过分类器MLKNN，可得出5个特征选择算法在8个数据集上的分类性能。按照汉明损失、1⁃错误率、平均准确率、覆盖率和排序损失的评价指标，表2～6给出实验的对比结果。
表2 8个数据集上的汉明损失对比Table 2 Comparison of Hamming loss（↓）on eight datasets
表3 8个数据集上的1⁃错误率对比Table 3 Comparison of One⁃error（↓）on eight datasets
表5 8个数据集上的覆盖率对比Table 5 Comparison of Coverage（↓）on eight datasets
表6 8个数据集上的排序损失对比Table 6 Comparison of Ranking loss（↓）on eight datasets
在每个表所示的评价指标中，使用了特定的符号表示指标值与分类性能的关系：“↑”表示值越大算法性能越佳，“↓”表示值越小算法性能越佳，并对每个数据集上的算法进行排序，其最佳算法性能指标使用黑体表示。此外，将各个算法在8个数据集上的平均排序列在最后，排序值越小，算法性能越高。
通过表2～6中的实验结果，可得实验的分析对比结果如下：
（1）由表2可知，算法LDFS在6个数据集上的汉明损失的分类指标均优于其他4个算法，算法PMU和MDDMspc分别在数据集Birds与Flags上获得了汉明损失的最小值。在数据集Birds和Flags上，算法LDFS取得了汉明损失次优值。在8个数据集上的算法排序，算法LDFS的平均排序排在首位。
（2）由表3中的1⁃错误率可知，算法LDFS也在6个数据集上取得较优的表现，在其他的两个数据集Birds和Yeast上，算法LDFS的1⁃错误率取得了次优值。另外，在数据集Yeast上，算法LDFS与算法PMU的1⁃错误率相等。依据在8个数据集上的平均排序，算法LDFS在1⁃错误率上性能最优。
（3）由表4中的数据可知，算法LDFS在7个数据集上平均准确率的值都好过其他对比算法，仅在数据集Gnegative上次于算法MDDMproj，在其他多标记数据集上，算法LDFS的平均准确率要明显优于算法MDDMproj。
（4）对于表5中的覆盖率，算法LDFS、MDDMproj和Relief⁃ML分别在5、2和1个数据集上获得最小值，覆盖率在所有数据集上的排序，依次为算法LDFS、MDDMproj、Relief⁃ML、PMU和MDDMspc。
（5）由表6可知，算法LDFS在大部分数据集上取得排序损失的最小值，除了数据集Gnegative，其排序损失的最优值由算法MDDMproj取得。在平均排序上，算法LDFS的表现最为出色。
由上可知，在8个数据集和5种评价指标，算法LDFS在77.5%的情况下取得了较明显优势，在其他的9种情况中获得了8次次优值。而算法MDDMproj、MDDMspc、PMU和Relief⁃ML分别在4、1、2、2种情况下取得较优情况。且算法LDFS均能在至少5个数据集上要优于其他算法。由此可见，相对于其他的多标记特征选择算法，算法LDFS的优势性能更明显且稳定。
为了进一步研究算法的有效性，选取数据集Gpositive，在5个评价指标下分析了各个算法的分类性能随特征子集的数目的变化趋势，实验的具体情况如图2所示。
图2 Gpositive数据集分类效果随特征数量变化情况Fig.2 Variation of the classification performance with the number of feature for datasets Gpositive
在图2中，使用颜色不同的曲线代表各个算法。由图2可知，对5个评价指标而言，当特征子集的数量变化时，各个算法的分类效果也随之变化。从总体趋势上来看，随着特征子集的增大，不同算法的分类效果都在不断优化并趋于稳定。对比其他多标记特征选择算法，算法LDFS在特征数量相对较少时优势并不明显，这是由于算法考虑的是特征之间的辨别能力排序，在特征数量较少时特征之间的冗余性对分类性能的影响较大。随着特征数量的增长，算法LDFS与其他算法的分类性能之间的差距逐渐缩小并实现超越。当特征子集规模在76左右时，算法LDFS在5个评价指标上取得较明显优势，进一步验证了算法LDFS能够提高学习模型的分类性能。
综上所述，相对于其他多标记特征选择算法，本文中的算法通过标记增强能够获得比多标记数据中更加丰富的标记分布信息，并利用在标记上的标记差异性和在特征上的模糊相对辨识关系，这些信息能够对特征辨识能力的刻画更加合理，使得算法能够在特征数量较少的情况下获得稳定且较优的分类性能。
5 结束语
在传统的多标记学习中，示例的相关标记假定为同等重要；然而，对于现实生活中的示例而言，其相关标记之间的相对重要度是不同的。为此，将示例关于标记的模糊相似性融入到原多标记数据的标记关系上，提出了基于模糊相似性的标记增强算法，将逻辑标记转化为标记分布。在此基础上，结合示例对之间的辨识度和标记差异性，提出了基于标记增强和模糊辨识度的标记分布特征选择算法。算法通过对模糊辨识关系的拓展，提出了模糊相对辨识关系以衡量不同特征对于示例对的辨识能力；然后，结合模糊相对辨识关系和标记差异性，并定义了对特征辨识能力的衡量指标。依据此衡量指标获得特征排序集合。在多个数据集上的对比实验表明，相较于其他多标记特征选择算法，算法能获得优势较明显的分类性能，并验证了算法的可行性和稳定性。在未来的研究中，将研究标记分布信息的差异性，构造基于不同搜索策略的特征选择方法，扩展其应用领域。
