基于相关性分析的多标签特征选择方法

王 进，孙万彤

(重庆邮电大学 数据工程与可视计算重点实验室,重庆 400065)

0 引 言

近年来，多标签学习[1]在文本分类[2]、蛋白质功能预测[3]、图像标注[4]等领域得到了越来越多的应用，在各种各样的多标签应用中，最主要且最重要的就是对每个样本及其与之相对应的标签进行正确的分类；同传统的分类方法一样，多标签学习同样也面临着维度灾难的问题，尤其对于文本多标签数据，特征数量往往成千上万，其中存在大量冗余或不相关的特征[5]，极易引发“维数灾难”，使得模型复杂度和计算时间大大增加；而特征选择是从原始特征集中，按照某一评价准则[6-7]选择出一组具有良好区分特性的特征子集，能剔除冗余或不相关的特征，从而达到降低特征维度，缩小特征空间，提高模型精确度，减少运行时间的目的，同时，选取出的特征更有利于模型理解与数据分析。

传统的机器学习问题中，特征选择方法包括包裹式(嵌入式)、过滤式特征选择方法，其中包裹式(嵌入式)特征选择方法，采用分类器性能评价特征子集的优劣，具有较高的计算复杂度、较大的内存空间；过滤式特征选择方法采用特定评价标准评价特征子集的优劣，独立于分类器，计算快且简单，所以一般常用过滤式特征选择方法进行特征选择，常见单标签特征选择[8-9]框架如图1。

图1 特征选择框架Fig.1 Feature selection framework

在多标签特征选择[10-11]中，同样也存在以上几种特征选择方法，过滤式特征选择也是被用得最多的，在过滤式特征选择中,卡方检验[12](Avg.CHI)是通过计算所有特征和标签之间的方差，综合每个标签所选出来的特征的方差得出每个特征的重要性；在基于最大依赖和最小冗余的多标签特征选择[13](multi-label feature selection based on max-dependency and min-redundancy, MDMR)中，通过最大化特征和标签之间的依赖性选择出特征子集，同时，对于选择出的特征子集，最小化特征之间的相关性来选出最优特征子集。最后对于评价函数计算出来的分数进行求和，从而取得最优子集，与此同时，由于在多标签学习中，标签之间是存在相关性的，但以上方法并没有考虑到标签之间的相关性。在稀疏子特征发现[14](sub-feature uncovering with sparsity, SFUS)方法中，通过将特征空间和标签空间结合，考虑到了标签之间的相关性，但对于标签的差异性并没有考虑，容易导致选择出来的特征对于单个标签来说相关性很小甚至是负相关的；基于统计的标签对转换方法[15](label pairwise comparison transformation with chi-square statistics, PCT-CHI2)提出在原始标签空间的基础上构建新的标签空间；拉普拉斯流行学习[16](manifold-based constraint Laplacian score, MCLS)在此基础上运用基于拉普拉斯(Laplacian score)[17-20]的特征选择，不仅考虑到了标签和特征之间的依赖性，同时还考虑到了特征之间的几何信息，但对于特征之间的相关性并没有加以分析，容易选择出冗余特征，影响模型的准确度。其他的非过滤式特征选择方法，诸如半监督优化特征选择[21](convex semi-supervised multi-label feature selection, CSFS)等方法,存在时间复杂度较大的问题。

针对于现有多标签特征选择算法针对于特征空间的相关性和冗余性未进行较多的分析，仅仅考虑到特征和标签之间及其标签和标签之间的相关性，以及现有方法大多对于标签空间整体考虑(产生了每个标签的共享特征空间，对于标签空间中的每个标签来说，特征空间都是一样的，所以称为共享特征空间。而对于标签特定特征空间来说，标签空间中每个标签各自对应不同的特征空间，所以称为标签特定特征空间)，从而忽略了标签特定特征空间的问题，本文提出基于相关性分析的多标签特征选择方法(multi-label feature selection method based on correlation analysis，MFCA)，与现有的多标签特征选择算法相比，本文的主要贡献如下。

1)对于特征空间进行相关性和冗余性分析, 去除了特征空间中的冗余特征。解决了特征之间的相关性问题，从而达到提高分类效果的目的。后文(7)—(9)式为阐述本贡献所使用，其中(8)式和(9)式为引用，(7)式为作者所定义。

2)将共享特征空间和标签特定特征空间融合，考虑到多个标签之间的个性和关联性。解决了标签的差异性问题，有效地提高了预测的性能。

1相关工作

目前为止，已经提出了许多的多标签学习算法[22-24]。这些多标签学习算法可以被分为两大类：①问题转换法；②算法适应法。其中，问题转换法是将多标签学习转化为传统的单标签学习[23,25]，如二值相关[26](binary relevance, BR)、剪枝问题转化[27](pruned problem transformation, PPT)、标签幂集[28](label power, LP)等。BR将每个标签的预测看作一个独立的单分类问题，并为每个标签训练一个独立的分类器，用全部的训练数据对每个分类器进行训练。但是，这种方法忽略了标签之间的关系，容易产生不平衡的数据。PPT通过考虑具有预先定义的最小出现次数的标签集来删除出现频率太低的标签的模式，但这种不可逆的转换可能会导致类信息的丢失。LP将多标签任务转换为单标签任务。但是，由于新类的数量随着标签的增加而迅速增加，这种方法容易导致计算量的增加和预测精度的降低。

和问题转换法不同，算法适应法通过直接改进某种现存的单标签数据学习算法，使之能够适应多标签数据的处理[22,24,29]，如多标签通知潜在语义索[30](multi-label informed latent semantic indexing, MLSI)、依赖最大化减少多标签维度[31](multi-label dimensionality reduction via dependence maximization, MDDM); MLSI通过同时考虑标签空间和原始特征空间来获取潜在特征子空间。MDDM利用希尔伯特-施密特独立标准(Hilbert-schmidt independence criterion, HSIC)进行衡量特征和标签之间的依赖关系。同传统的分类方法一样，多标签学习同样也面临着维度灾难的问题，多标签特征选择的过程可以分为2个步骤：①利用诸如依赖性[25]，互信息[32]等相关评价指标去衡量候选特征子集的重要性；②确定选取候选子集的搜索策略，例如启发式搜索，贪心搜索等。

现有的多标签特征选择方法中，有些方法并没有保留原始的特征空间，而是将数据投影到新的空间，比如基于共享子空间的多标签分类方法[33](extracting shared subspace for multi-label classification, ESML)，它是提取标签空间共有特征。MDDM是通过最大化原始特征与相关标签的依赖性从而将原始数据转换为缩小的特征空间。ESML和MDDM方法考虑到了数据和标签之间的相关性，但是它们并没有考虑到不同标签之间的相关性。其他的一些特征选择方法，比如基于局部标签相关性的多标签学习[34](multi-label learning by exploiting label correlations locally, ML-LOC)，考虑到了标签空间中不同标签之间的相关性。SFUS提出了共享特征子空间，但是并没有明显到考虑到标签空间中不同标签之间的相关性。

2 基于相关性分析的多标签特征选择方法

2.1 符号定义

设X=[X1,X2,…XN]∈D×N用来表示训练集，其中，N表示样本数,Xi表示为第i个样本,特征集合为F=[f1,f2,…,fD]T，fd=[fd1,fd2,…,fdN]，其中，fdn表示第n个样本Xn的第d个特征,也就是第d个特征在所有样本中的值组成的向量；L=[l1,l2,…,ld]表示标签集合，其中有d个标签变量l1,l2,…,ld。

2.2 传统拉普拉斯评分

利用拉普拉斯特征评分方法[8]进行特征选择是传统的单标签特征选择算法，它既能考虑到样本和类标签之间的关联又保留了样本和样本之间的几何分布信息。如果一个样本点Xi是另一个样本点Xj的最近邻的k个样本之一，或者Xj是另一个样本点Xi的最近邻的k个样本之一，则Xi和Xj可以相连，可以通过这种方式对所有数据建立一个图。通常情况下k=5 ,则样本之间的相似性可以通过如下的公式来描述

(1)

令D=diag(Sl)，l=(1,1,…,1)T，L=D-S，其中，D表示对角矩阵；S表示样本之间的权重矩阵；t是常数，一般取值为1。

对fd做变形，可以得到中间变量

(2)

则第d个特征的拉普拉斯特征评分为

(3)

拉普拉斯特征评分越小则代表特征越重要；同样地，在多标签特征选择中，也可以基于拉普拉斯评分进行特征选择，与拉普拉斯在单标签中的特征选择不同的是，在多标签中，首先会对标签区间进行转换，然后利用流形学习将逻辑标签转化为数字标签[21],这样一来便可以基于特征空间的拓扑结构对标签空间进行分析，以便于能够对多标签进行拉普拉斯特征评分，具体步骤如下。

定义M={(Xi,Xj)|Xi,Xj属于同一个类}，表示属于同一个类。

定义C={(Xi,Xj)|Xi,Xj不属于同一个类}，表示不属于同一个类。则样本之间的相似性可以通过如下的公式来描述

(4)

(5)

令DM=diag(SMl)

DC=diag(SCl),l=(1,1,…,1)T

l=(1,1,…,1)T,LM=DM-SM

LC=DC-SC

则第d个特征的拉普拉斯特征评分为

(6)

2.3 共享特征空间中的相关性和冗余性

因为特征向量集合用fd=[fd1,fd2,…,fdN]来表示，则特征之间的相关性可以用以下公式来描述

(7)

(7)式中，H(X)表示信息熵，公式描述如下

(8)

IG(X|Y)表示信息增益，公式描述如下

IG(fx|fy)=H(fx)-H(fx|fy)=

H(fx)+H(fy)-H(fx|fy)

(9)

SU(fx,fy)是用来衡量2个离散变量相关度的，取值为0～1，值越大表示fx和fy之间的相关性越大。当取值为0时，表示2个变量之间是完全不相关的，反之，取值为1时，则表示2个变量之间有着较强的相关性。

对于特征空间中特征之间的相关性，设定一个阈值θ(0<θ<1, 取θ=0.8)，如果特征p和q之间的相关性Rpq>θ大于某一个阈值，则将p和q分为一组，记为Spq,否则p和q各为一组,记为Sp和Sq，对于新的特征m，分别计算m和之前所有特征分组内重要性为前e(取e=20%)的各个特征的相关性，特征评分由拉普拉斯计算得出。

算法1共享特征空间整体流程伪代码

输入：特征集合F=[f1,f2,…,fD]T，fd=[fd1,fd2,…,fdN]。

输出：最终模型所需要的特征空间向量。

1：拉普拉斯算法计算出特征空间中每个特征的评分,生成新的特征向量F

2：ford=1:F

3： 利用公式7计算第d个特征fd和第d+1个特征fd+1之间的相关度Rd,d+1

4： 定义集合S表示特征组，用来存放特征，定义FG表示特征分组及其所放特征

5： 定义Sd={fd},Sd+1={fd+1},如果相关度Rd,d+1>θ,Sd∪Sd+1，反之Sd,Sd+1

6： forC=1:FG

7： 计算新的特征和特征分组内特征重要性为前20%的特征的相关度

如果相关度Rd,ci>θ,C∪Sd,反之Sd为新特征分组

8: end for

9：FG表示最终的特征空间向量

10：end

对于其中某一个分组，如果新来的特征和该分组中特征的相关性都大于某个阈值，则加入该特征分组，反之，则不加入，对于所有的分组，都进行这样的计算；如果存在有2个或者多个特征分组都满足以上情况，那么分别计算特征m和每个分组里的特征的相关度，然后求和，新来的特征m最终加入相关度和最大的分组内；如果都小于某个阈值θ，则该特征独自成为一个新的组，记为Sm；对于特征空间中的每一个特征，都进行这样的操作；最终，特征空间中的特征将会分为很多个组，并且对于每个分组来说，组内的特征都存在较强的相关性，组间则相关性较弱，这样一来，即完成了特征空间中的相关性和冗余性分析。其过程伪代码如算法1，算法流程描述如图2，其中，Rmn表示特征m和特征n之间的相关性；fn表示样本特征空间的第n个特征。

2.4 共享特征空间和标签特定特征空间融合

对于标签特定特征空间来说，在多标签学习中，虽然存在一些标签，他们之间是有关联性和相关性的，但是关联性和相关性不代表它们之间是相等的，也就说对于每一个标签来说，都存在每一个标签的特定特征，例如目前存在的一些标签特定特征空间转换算法[20]，它是首先对单个标签做一个特征转换，使得每个标签的特定特征空间都存在差异性，这样一来即把标签的差异性考虑进去。具体方法如下，首先对训练集中的正负样本分别聚类，聚类个数可以通过人为进行指定；然后对于每一个样本来说，分别计算该样本到聚类中心的距离，将该距离作为特征，对测试集也进行同样的操作，这样，即完成了多标签中标签特定特征空间的转换，使得对于每一个标签来说，都存在不同的特征。

图2 特征相关性分析流程图Fig.2 Feature correlation analysis flow chart

在多标签特征选择中，对于标签空间整体考虑，选择出共享特征空间，并基于此对共享特征空间中的相关性和冗余性加以分析；而标签特定特征空间转换是一种有效的对于标签进行转换的方法，对于每一个标签来说，可以选择出该标签的特定特征空间。本文提供了一种方法，通过将共享特征空间和标签特定特征空间融合，有效地提升了分类性能，同时考虑到了多个标签之间的个性和关联性，解决了标签的差异化存在，具体步骤：①对标签进行特定特征空间转换；②对于标签进行共享特征空间转换，在进行共享特定特征空间转换的时候，同时对于共享特征空间中的特征之间的相关性和冗余性进行分析；③共享特征空间和标签特定特征空间进行融合以提高分类器预测性能。具体描述过程如图3，其过程伪代码如算法2。

图3 特征空间结合流程图Fig.3 Feature space combined flow chart

算法2共享特征空间融合标签特定特征空间伪代码

输入：特征集合F=[f1,f2,…,fD]T，fd=[fd1,fd2,…,fdN]。

输出：最终预测模型。

1：拉普拉斯算法计算出特征空间中每个特征的评分,生成新的特征向量F

2：ford=1:F

3： 利用公式7计算第d个特征fd和第d+1个特征fd+1之间的相关度Rd,d+1

4： 定义集合S表示特征组，用来存放特征，定义FG表示特征分组及其所放特征

5： 定义Sd={fd},Sd+1={fd+1},,如果相关度Rd,d+1>θ,Sd∪Sd+1，反之Sd,Sd+1

6： forC=1:FG

7： 计算新的特征和特征分组内特征重要性为前20%的特征的相关度

如果相关度Rd,ci>θ,C∪Sd,反之Sd为新特征分组

8: end for

9：FG表示最终的特征空间向量

10：标签特定特征空间生成

11：g(x,yi)=c1fi(x,yi)+c2h(x,yi)

fi(x,yi)表示基于共享特征空间模型，h(x,yi)表示基于标签特定特征空间模型

g(x,yi)表示最终特征空间融合模型,c1和c2取值为0.5

12：end

3 实验结果与分析

3.1 数据集与对比方法

为了验证本文算法的有效性，我们选取了Mulan(1)http://mulan.sourceforge.net/datasets-mlc.html中的9个多标签数据集进行实验，这些数据集来自新增文本、图像等领域，且已经被划分为训练集和测试集，其详细信息如表1。本文选取的多标签特征选择对比方法分别是PCT-CHI2，CSFS，SFUS，Avg.CHI，MCLS。

表1 数据集描述

3.2 评估指标

在本节中，将介绍用于评估多标签分类模型预测性能的评价指标。在2个方面考察，根据测试集每个实例的预测标签与其真实标签的比较来测量多标签分类的性能。①基于实例的分类精度的考察，包括：Micro-F1，Macro-F1；②基于标签排名的精度考察，包括：Coverage，Average Precision，Ranking loss。其中，Micro-F1、Macro-F1以及Average Precision值越大表示分类越准确，而Ranking loss、Coverage都是越小表示分类越准确。它们分别定义如下。

3.2.1 排序损失

(10)

3.2.2 覆盖

表示所有样本中排序最靠后的真实标签的排序均值，计算公式为

(11)

3.2.3 平均精度

平均精度(average precision)指标反映了所有样本的预测标签排序中，排在相关标签前面的也是相关标签的概率的平均，计算公式为

(12)

(12)式中，ri(λ)表示第i个样本中标签λ的排位。

3.2.4 微观F1值

真正例、假正例、真负例、假负例分别表示传统机器学习中单标签下的4个数量特征，B∈(accuracy, precision, recall,Fβ)表示对4个数量特征进行相关运算得到常规的二分类指标。

Micro表示对多个标签下的数量特征取平均，再根据数量特征计算得到常规指标。

(13)

(14)

3.2.5 宏观F1值

Macro表示对单个标签下的数量特征计算得到常规指标，然后对多个标签取平均。

(15)

(16)

3.3 参数取值分析

对特征进行分组以后，会存在多个组，且每个组内有多个特征，为了降低本算法的时间复杂度，同时也为了能得到特征组内较多特征重要性比较大的特征，所以取e为20%，以便于同时照顾到时间复杂度和准确率，在兼顾二者的基础上，尽可能地提高模型分类效果。若小于20%，分类效果不尽然好，若大于20%，时间复杂度会升高。选取依据如表2，在表2中，分别取e=10%,20%,30%,40%进行试验对比，从实验结果可以看出，选择20%时，分类效果较为好；并且从算法1的流程可以很明显看出来，时间复杂度会随着所选取比例的增大而变大。所以参数e取20%时，可以在时间复杂度不大的情况下取到较好的分类效果。

从公式(7)及算法1中可以看出来，阈值θ取0时，特征之间完全不相关，阈值θ取1时，特征之间具有强相关性。当θ越小时，分配到同一组内的特征的相关度也会比较小，导致最终选择出的特征集合存在较多冗余特征，影响模型分类效果。若θ过大，选择出的特征较少，也会影响模型分类效果。所以将阈值θ设置为0.8。选取依据如表3。在表3中，分别取θ=0.6,0.7,0.8,0.9进行试验对比，从实验结果可以看出，θ=0.8时，分类效果较好。

3.4 实验结果与分析

在实验中，对每个数据集采用5个评价指标，分别是Micro-F1，Macro-F1，Average Precision，Coverage，Ranking loss。其中，Micro-F1,Macro-F1,Average Precision表示值越大效果越好，性能越佳；Coverage、Ranking loss表示值越小，效果越好，性能越佳。本文将从预测性能、选取特征个数的不同来对算法进行分析和评估。

表2 参数θ取不同数值时算法的对比实验结果

表3 参数e取不同数值时算法的对比实验结果

1)验证同一个数据集下在选用不同特征数的预测效果情况。数据集在不同特征下的5个评价指标的对比分别如图4到图8;其中，↓表示指标越小分类效果越好；↑表示指标越大分类效果越好。由于在其余4个数据集上，MFCA所对比的一些算法未提供对比实验结果，所以我们在有对比实验结果的5个数据集上进行测试。

通过对图4—图8的5组对比实验的分析，可以明显看出来，数据集在不同特征个数的情况下， MFCA算法和其余算法相比，在大多数评价指标上性能超过其余算法。这也从侧面证明了MFCA算法较好的分类效果。

2)验证不同数据集下的预测效果，其中包括最优对比实验和平均对比实验。

最优对比实验：即比较一些数据集在某一个特征上取得各个指标最优值的对比实验，在最优对比实验中，MFCA算法在大多数评价指标上显著优于其他算法。

平均对比实验：即比较一些数据集在所选取的各个特征上取得各个指标值的平均值的对比实验。

在平均对比实验中，MFCA算法在大多数评价指标上显著优于其他算法。其中，表4—表8表示最优对比实验，表9—表13表示平均对比实验,表14,表15表示MFCA算法在其余4个数据集上的最优对比试验和平均对比试验，最优结果均加下划线表示。由于在其余4个数据集上，MFCA所对比其余算法未提供对比实验结果，所以在表14和表15中，只能对比提供实验结果的算法。其中，↓表示指标越小分类效果越好，↑表示指标越大分类效果越好。

图4 数据集flags在不同特征个数下的各个评价指标的变化情况Fig.4 Change of each evaluation index of the data set flags under different feature numbers

图5 数据集scene在不同特征个数下的各个评价指标的变化情况Fig.5 Change of each evaluation index of the data set scene under different feature numbers

图7 数据集yeast在不同特征个数下的各个评价指标的变化情况Fig.7 Change of each evaluation index of the data set yeast under different feature numbers

图8 数据集education在不同特征下的各个评价指标的变化情况Fig.8 Change of each evaluation index of the data set education under different feature numbers

表4 算法在yeast上的最优对比实验结果

表5 算法在flags上的最优对比实验结果

表6 算法在scene上的最优对比实验结果

表7 算法在recreation上的最优对比实验结果

表8 算法在education上的最优对比实验结果

表9 算法在yeast上的平均对比实验结果

表10 算法在flags上的平均对比实验结果

表11 算法在scene上的平均对比实验结果

表12 算法在recreation上的平均对比实验结果

表13 算法在education上的平均对比实验结果

表14 算法在其余4个数据集上的最优对比实验结果

表15 算法在其余4个数据集上的平均对比实验结果

通过对以上一系列的最优对比实验和平均对比实验进行分析，可以明显看出来，MFCA算法在不同数据集下的对比结果也远优于其余算法。在最优对比实验中，MFCA在大部分评价指标中超过其余算法，验证了MFCA算法较好的分类效果；在平均对比实验中，MFCA在大部分评价指标中超过其余算法，验证了MFCA算法的稳定性。

4 总 结

本文提出了一种基于相关性分析的多标签特征选择方法MFCA,首先通过对共享特征空间进行相关性和冗余性的分析，达到去除共享特征空间中冗余特征的目的，从而提高分类性能。同时对于共享特征空间来说，由于其未考虑到标签的个性和关联性，所以提出针对单标签的标签特定特征空间，将其与共享特征空间进行融合。通过在多个数据集上进行测试，并进行不同特征个数下的预测性能的分析，可以发现该算法有效提高了算法的预测性能并具有较强的稳定性。