基于依赖最大化和稀疏回归的多标签特征选择

吴喆君，黄 睿

(上海大学 通信与信息工程学院，上海 200444)

0 引 言

“维数灾难”是多标签学习面临的挑战之一[1-7]。通过特征选择对高维数据进行维数约简是克服该问题的有效手段[8-10]。基于稀疏回归的多标签特征选择算法利用优化得到的回归矩阵进行特征选择[11-14]。Ma等提出利用稀疏性来构建子空间(sub-feature uncovering with sparsity，SFUS)的多标签特征选择算法[12]，通过联合稀疏特征选择与多标签学习来获得特征的共享子空间。文献[13]提出非负稀疏表示的多标签特征选择方法(multi-label feature selection based non-negative sparse representation，MNMFS)，融合了非负约束问题和l2,1范数最小优化问题。Zhang等提出一种基于流形正则化的多标签特征选择方法(manifold regularized discriminative feature selection for multi-label lear-ning，MDFS)[14]，将数据空间和标签空间的流形正则化引入稀疏回归模型。

当前，多数基于稀疏回归的多标签特征选择算法认为数据的特征空间和标签空间之间存在线性关系，在回归模型中直接将数据从特征空间映射到标签空间。然而大部分情况下两者之间的线性关系并不成立。文献[15]通过依赖最大化对多标签数据进行特征提取。受此启发，本文提出一种基于依赖最大化和稀疏回归的多标签特征选择算法(multi-label feature selection with dependence maximization and sparse regression，DMSR)。该方法通过最大化投影子空间与标签空间之间的依赖性来构建数据的低维空间，利用希尔伯特-施密特独立性准则[15]来衡量两者之间的依赖性，然后把该低维空间引入稀疏回归模型中，将数据从特征空间映射到低维空间。相比于呈现稀疏性、二值性的标签空间，该低维空间包含了更丰富的信息。结合l2,1正则化得到目标函数，利用交替优化的方式进行求解，得到用于特征选择的回归系数矩阵。

1 本文算法

1.1 目标函数

假设有多标签数据集X=[x1,x2,…,xN]T∈RN×d，N是数据个数，d是特征个数，其中每个数据样本为xi=[xi1,xi2,…,xid]， 标签集合为L={l1,l2,…,lC}，C是总共的类别标签个数，数据集对应的标签为Y=[y1,y2,…,yN]T∈{0,1}N×C，xi的标签为yi=[yi1,yi2,…,yiC]， 如果xi含有标签lj，则yij=1， 否则yij=0。 令I表示单位矩阵，e表示全为1的向量。

所提算法DMSR源自稀疏回归模型，使用最小平方损失作为损失函数的稀疏回归模型的目标函数一般有如下形式

(1)

式(1)的目标函数直接将数据从原始特征空间映射到标签空间，但是特征空间和标签空间之间往往不存在线性关系，因此我们希望构建一个数据的m维子空间V=[v1,v2,…,vN]T∈RN×m， 把数据从原始特征空间映射到该低维子空间。受文献[15]的启发，DMSR最大化低维空间V和标签空间Y之间的依赖性，使用希尔伯特-施密特独立性准则(Hilbert-Schmidt independence criterion，HSIC)计算两者之间的依赖性，其定义如下

HSIC(V,Y)=(N-1)-2Tr(HK1HK2)

(2)

(3)

同时，对低维空间V的每个维度之间进行正交约束，用V代替式(1)中的标签空间Y， 再结合式(3)，则目标函数转变为

(4)

其中，α和β为平衡参数。关于正则项R(W)， 这里采用l2,1正则化来保证稀疏性和减少离群点的影响[7,12]，即令R(W) 等于W的l2,1范数，从而得到最终的目标函数

(5)

1.2 优化求解

(6)

式(6)对W求导，并且令导数为零，可以得到

2XT(XW-V)+2βQW=0

(7)

解得

W=(XTX+βQ)-1XTV

(8)

把式(8)代入式(6)中的优化项，可以得到

(9)

其中，A=XTX+βQ， 从而得到如下只含有一个优化变量V的目标函数

(10)

该优化问题可以通过对矩阵I-αHYYTH-XA-1XT进行特征分解来进行求解，取前m个最小特征值对应的特征向量构成V。

算法1：DMSR算法

输入：数据集X∈RN×d， 标签Y∈{0,1}N×C， 平衡参数α，β， 低维空间的维数m。

输出：特征排序。

(1) 初始化Q为单位矩阵Id×d；

(2) 迭代

(3) 求解式(10)得到V；

(4) 根据式(8)更新W；

(5) 根据W每一行的值更新Q；

(6) 直至收敛；

2 实 验

本文将所提算法DMSR与其它4种多标签特征选择算法进行了比较，实验结果表明所提算法能够取得较好的性能。

2.1 实验设置

为验证所提算法性能，在Emotions、Birds、Enron、Image、Scene和Yeast等6个多标签数据集上进行实验。这些数据集都可以从互联网上获得，涵盖了音频、音乐、图片、生物、文本等多种类型。表1列出了数据集的详细信息，包括样本数、特征数、标签数、所属领域以及URL链接。

表1 数据集信息

本文使用5种常用的评价指标来评估所提算法的性能，分别是汉明损失、排序损失、覆盖率、1-错误率和平均精度[7,14]。假设T={(xi,yi)|1≤i≤p} 表示含有p个数据样本的测试数据集以及其对应的标签，某种算法对样本xi的预测标签为y′i，fk(xi)(1≤k≤C,1≤i≤p) 表示分类器输出的样本xi在第k个标签上的分值，各评价指标的含义和定义如下：

汉明损失(Hamming loss，HL)：考察数据样本被错误分类的情况，即分类器没有预测相关的标签或者预测了不相关的标签

(11)

其中，Δ表示两个集合之间的对称差。

1-错误率(one-error，OE)：考察分类器输出分值最高的标签不属于数据实际标签的次数

(12)

覆盖率(coverage，CV)：考察在分类器给出的标签排序中，覆盖样本所有实际标签所需的平均标签个数

(13)

排序损失(ranking loss，RL)：考察出现排名颠倒的标签对的情况，即不相关标签的排名高于相关标签的排名

(14)

平均精度(average precision，AP)：考察排名高于某个特定相关标签的相关标签的平均个数

(15)

这5种评价指标的取值范围均为0到1，汉明损失、1-错误率、覆盖率和排序损失取值越小，算法性能越好，平均精度则相反。

实验采用如下4种多标签特征选择算法作为对比算法：

MDMR[8]：利用最大化依赖和最小化冗余(max-dependency and min-redundancy)实现多标签特征选择。

GMBA[9]：基于图边界的多标签特征选择算法(graph-margin based multi-label feature selection)，利用大边界理论来衡量特征的重要程度。

SFUS[12]：通过联合稀疏特征选择与多标签学习来获得特征的共享子空间，并且将子空间引入稀疏回归模型，完成特征选择。

MDFS[14]：基于流形正则化的多标签特征选择算法，在优化模型中加入了数据空间和标签空间的流形正则化项。

2.2 实验结果与分析

图1(a)～图1(f)分别给出了在6个数据集上，不同算法的平均精度指标随选择特征个数改变的变化情况，其中，横坐标轴表示选择的特征个数，纵坐标轴表示平均精度。除了上述提到的4种对比算法，我们还采用了全特征进行实验，将其结果作为比较基准，记为Baseline。从图中可以看出，随着选择特征个数的增加，各个算法的性能先逐步提升，然后趋于平缓，一些算法的性能还出现了下降，而DMSR算法的性能超过了Baseline，这表明DMSR能够选择优秀的特征，提升分类器的性能。与其它对比算法相比，DMSR在大多数情况下表现出更优异的性能。在Emotions、Yeast和Image数据集上，选择特征的个数变化时，DMSR的性能始终能够高于其它算法，在Birds、Scene和Enron数据集上，虽然DMSR没有在所有情况中均领先其它算法，但是其性能一直排名前3。

图1 不同数据集上算法的性能

此外，为了对算法性能做进一步的定量分析，我们在每个数据集上利用各个算法选择最重要的30个特征进行实验。表2～表6列出了在5种评价指标上的实验结果，各表中的最后一行“AvgRank”表示每个算法在不同数据集上的平均排名，不同算法中最优的结果加粗表示，↓表示评价指标越小，性能越好，↑表示评价指标越大，性能越好。从表中可以看出，由于实验采用了5种评价指标和6种数据集，因此总共有30种比较情况，DMSR算法在其中的24种情况排名第一，6次排名第二，尽管在个别情况下DMSR的性能不如MDFS和SFUS，但整体上看DMSR仍然优于其它对比算法。综合分析各个算法在5种评价指标上的平均排名，我们可以得到各个算法的性能排序：DMSR>MDFS>SFUS>MDMR>GMBA。DMSR、MDFS和SFUS都是基于稀疏回归的多标签特征选择算法，而MDMR和GMBA是过滤式多标签特征选择算法，这验证了利用稀疏回归模型进行特征选择的有效性。在大多数情况下DMSR的性能要优于MDFS和SFUS，这说明基于HSIC构建数据的低维空间并将其引入回归模型，能够选择出更具有判别力的特征，从而有效提升多标签分类器的性能。

表2 不同算法的汉明损失(↓)

表3 不同算法的排序损失(↓)

表4 不同算法的覆盖率(↓)

表5 不同算法的1-错误率(↓)

表5(续)

表6 不同算法的平均精度(↑)

3 结束语

多标签学习面临“维数灾难”的问题，利用稀疏回归模型的多标签特征选择方法能够有效去除冗余特征，提升算法性能，但是回归模型中数据的特征空间和标签空间之间通常不存在线性关系。本文提出一种基于依赖最大化和稀疏回归的多标签特征选择算法DMSR，首先构建数据的低维空间，最大化低维空间和标签空间之间的依赖性，该依赖性使用希尔伯特-施密特独立性准则来衡量，然后将低维空间加入含有l2,1正则项的回归模型，最后设计了一种交替优化的方法进行求解，利用得到的回归系数矩阵选择特征。在6个公共多标签数据集上的特征选择与分类实验结果表明所提算法DMSR的性能优于其它对比算法。

DMSR算法没有考虑标签相关性，后续的研究工作将关注如何将标签相关性引入回归模型，从而进一步提高算法性能。