多标记学习是一种针对实际生活中普遍存在的多义性现象的学习框架,在此框架下,样本由多个特征和多个标记构成,学习目的是将未知的实例对应上更多正确的标记^[16].

假设T是由n个特征组成的特征集合T={t₁, t₂, …, t_n}, L是由m个标记组成的标记集合L={l₁, l₂, …, l_m}, 在标记集合中,有该标记为1,否则为0,则含有z个样本的多标记数据集表示为

DataSet={(T_i, L_i)|1≤i≤z, T_i∈T,L_i∈L}(1)

定义1^[11] 若X={x₁, x₂, …, x_m}为随机变量, x_i的概率为p(x_i), 则X的不确定性期望为

H(X)=-∑^m_i=1p(x_i)lb p(x_i)(2)

H(X)亦被称为随机变量X的熵,其值越小表示X的期望和不确定性程度越小.

定义2^[11] 设随机变量X={x₁, x₂, …, x_m}和Y={y₁, y₂, …, y_n}, 则X和Y的联合熵为

H(X,Y)=-∑^m_i=1∑ⁿ_j=1p(x_i, y_j)lb p(x_i, y_j)(3)

定义3^[11] 设随机变量X={x₁, x₂, …, x_m}, Y={y₁, y₂, …, y_n}, 则Y在X条件下的条件熵为

H(Y|X)=-∑^m_i=1∑ⁿ_j=1p(x_i, y_j)lb p(y_j|x_i)(4)

H(Y|X)可用来度量Y在给定X时的不确定性程度.

定义4^[11] 若X和Y为已给定的随机变量,则定义X与Y之间的互信息为

I(X; Y)=-∑^m_i=1∑ⁿ_j=1p(x_i, y_j)lb(p(x_i, y_j))/(p(x_i)p(y_j))(5)

I(X; Y)用于衡量随机变量X和Y的相关性, I(X; Y)越大,表明X与Y之间的相关性越大.同时,互信息还满足以下关系

I(X; Y)=H(X)+H(Y)-H(X,Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)(6)

在多标记学习中,一个样本由多个特征和标记描述,则特征与标记集合之间的互信息可定义为:

定义5^[11] 对于给定描述样本的特征 f和标记集合L={l₁, l₂, …, l_m}, l_i∈L, i=1, 2,…, m, 若特征 f与标记l_i之间的互信息为I(f; l_i), 则特征 f与标记集合L之间的互信息为

IML(f; L)=∑^m_i=1I(f; l_i)(7)

由I(f; l_i)≥0可知, IML(f; L)≥0. 当f和L相互独立时,等号成立,此时特征与标记之间不提供任何信息,即该特征与标记空间互信息为最小值. 互信息值越大, 特征与标记之间的关系越密切.

同理,式(8)和式(9)成立.

IML(f; L)=IML(L; f)(8)

IML(f; L)=∑^m_i=1H(l_i)-∑^m_i=1H(l_i|f)(9)

根据式(9)可得,若

IML(f; L)=∑^m_i=1H(l_i)(10)

则表明标记集合L可完全由特征 f确定,两者的不确定度之和取得最大值.

在多标记数据集中,常因标记的不平衡性导致不同标记对样本描述程度有所不同,而目前多数算法并未考虑这种情况.为此,本研究根据标记空间中的每个标记下的正负样本个数对标记赋予权值,建立标记权值模型,具体定义为:

定义6 给定样本空间U={x₁, x₂, …, x_z}, 其特征空间T={t₁, t₂, …, t_n}, 标记空间L={l₁, l₂, …, l_m}. 对于l_i∈L, i=1, 2,…, m, 样本总数为z, 在第i个标记下的正标记和负标记数目分别为|l⁺_i|和|l^-_i|, 权值为ω⁺_i=|l⁺_i|/z和ω^-_i=|l^-_i|/z.

对于传统的单标记运用互信息进行特征选择过程中,假使用两个特征 f₁和 f₂对样本进行刻画,则对于特征与特征之间的冗余性用I(f₁; f₂)进行有效表示; 倘若样本的特征用给定的 f表示,样本的类别标记用l表示,则对于特征与标记类别之间的相关程度用I(f; l)进行有效表示.而在现有的多标记学习中,各个样本可用1个特征向量来表示,也可能隶属于多个类别标记,同时,充分考虑到标记权值模型下的各样本所含有的有用信息,因此需对加权特征和标记集合之间的相关性进行更深层次的探究.定义7给出了加权特征与标记集合之间的互信息定义.

定义7 对于给定样本空间U={x₁,x₂,…,x_z}, 标记空间L={l₁, l₂, …, l_m}, l_i∈L, i=1,2,…,m, 由定义6和式(7)可知,加权特征 f与标记之间的互信息为

IML(f; L^*)=1/m∑^m_i=1ω^*_iI(f; l_i)(11)

其中,“*”可为“+”(正标记)或“-”(负标记),则ω⁺_i和ω^-_i分别为定义6中的正负标记的权值.

考虑到标记对样本的描述存在一定的差异性,为使描述的样本实例更准确,同时也为了更充分地挖掘存在于少量样本中但包含众多有用信息的一些标记,首先计算标记空间中同一标记下正负标记的权值; 其次,利用加权信息熵度量特征与标记空间之间的相关性,并由此得出两组不同的特征重要度排序; 最后,将两组重要度不同的特征进行融合排序,得出最终特征序列.MSIO算法伪代码如图1.

图1 MSIO算法伪代码
Fig.1 Pseudocode of MSIO algorithm

分析图1的算法可见,MSIO算法先通过统计标记空间中类标记下的正负标记密度,然后计算标记空间与特征空间的相关性,并按照标记密度对特征进行赋权得分输出两组序列,再按照一定关系对两组序列加权得出最终序列.此方法简单易行且运行快速,既考虑了多种因素,又能有效提高分类器的分类精度.MSIO算法流程图如图2.

图2 MSIO算法流程图
Fig.2 Flowchart of MSIO algorithm

采用Mulan数据库^[16]中11个常用的公开实验数据集(表1),来验证算法MSIO的有效性.

表1 多标记数据集[17]
Table 1 Multi-label datasets[17]

利用平均准确率(average precision, AP)、排位损失(ranking loss, RL)、1-错误(one-error, OE)和海明损失(Hamming loss, HL)4个评价指标^[18]对多标记实验实验结果进行验证和评价度量.

测试集为{(x_i, Y_i)}^m_i=1R^d{+1,-1}^L. 其中, Y_i为隶属于样本x_i的相关标记集合,经算法预测得到的标记集合记为h(x); 符号表示维度相乘.根据预测函数 f_l(x)定义排序函数为rank_f(x,l)∈{1, 2,…,L}.

AP为评估预测标记排在前列且正确存在于相关样本标记的平均概率,如式(12).该值越大表示分类效果越好,最优值为1.

AP(f)=1/m∑^m_i=1(1/(|Y_i|)∑_l∈Yi((k|rank_f(x_i, k)≤rank_f(x_i, l), k∈Y_i))/(rank_f(x_i, l))))(12)

其中, Y_i为隶属于样本x_i的相关标记集合.

RL用于评估无关标记在相关标记的样本前列的多少,如式(13).该值越小表示分类效果越好,最优值为0.

RL(f)=1/m∑^m_i=1(1/(|Y_i||Y^-_i|)|{(l, k)|rank_f,(x_i, l)≥rank_f(x_i, k),(l, k)∈Y_iY^-_i}|)(13)

其中, Y^-_i为集合Y_i在标记空间中的补集.

HL用于衡量样本在单一标记上的非正确匹配情况,如式(14).该值越小,分类效果越好,最优值为0.

HL(h)=1/m∑^m_i=11/L|h(x_i)≠Y_i|(14)

其中, Y_i为隶属于x_i的相关标记集合; h(·)为分类器,即可得x_i的预测标记向量.

OE用于衡量最高排序中样本的标记不存在于相关标记集合中的情况,如式(15).该值越小,表示分类效果越好,最优值为0.

OE(h)=1/m∑^m_i=1{[arg max_l∈L f(x_i,l)]Y_i}(15)

在4个评价指标中,除去AP值越大越优,其余的越小越优.

本研究实验代码均在Matlab2016a中运行,硬件环境Inter^ Core^TM i7-7700HQ CPU @ 2.80 GHz,8 Gbyte内存; 操作系统为Windows 10.以多标记k近邻(multi-label k-nearest neighbor, ML-kNN)^[19]作为基础分类器,对基于最大相关性的多标记维数约简(multi-label dimensionality reduction via dependence maximization, MDDM)算法^[20-21]、基于多变量互信息的多标记特征选择算法PMU(pairwise multivariate mutual information)^[22]、 多标记朴素贝叶斯分类的特征选择(feature selection for multi-label naive Bayes classification, MLNB)算法^[23]、 基于标记相关性的多标记特征选择(multi-label feature selection with label correlation, MUCO)算法^[13]和MSIO算法的AP、RL、OE和HL值进行排序.其中,MDDM算法按照参数所选择的不同分为MDDMspc与MDDMproj算法.由于MDDM、PMU、MUCO和MSIO算法得到的是一组特征序列,于是设置特征子集的个数与MLNB算法一致,并设ML-kNN中的平滑系数s=1, 近邻个数k=10. 表2至表5列举了6种算法在数据集中的AP、RL、OE和HL值.

表2 六种算法在11个数据集中的平均准确率排序1)
Table 2 Average precision ranking of 6 algorithms in 11 datasets

表3 六种算法在11个数据集中的排位损失排序1)
Table 3 Ranking loss of 6 algorithms in 11 datasets

表4 六种算法在11个数据集中的1-错误上排序1)
Table 4 One-error ranking of 6 algorithms in 11 datasets

表5 六种算法在11个数据集中的海明损失排序1)
Table 5 Hamming loss ranking of 6 algorithms in 11 datasets

由表2至表5可见:

1)MSIO算法在4种评价指标中的最优数目和平均值均位列第1,且在Art、Computer、Rec和Ref数据集中的所有评价指标均优于其他算法.

2)在AP指标上,仅MUCO算法在部分数据集上占优,但最优的Cal500数据集也仅提高了2.15%; 在RL指标上,6种算法各有千秋,其中,在Emotions数据集中MDDMspc算法占优最大,为11.12%; 在OE和HL指标上,最优的分别高7.46%和3.58%.

图3为6种算法在不同评价指标上的箱型图.由图3可见,6种算法在4种评价指标上展现的分类性能对比中,MSIO算法在箱形图中的中位数表现明显占优.可见,MSIO算法稳定性更好的,且分类精度更高,性能优于其他特征选择算法.

图3 六种算法在不同评价指标上的箱型图
Fig.3 Box-plot of six algorithms on different evaluation indexes

运用统计学知识,对在11个数据集上的实验结果进行显著性水平为5%的Nemenyi统计假设检验,若在所有数据集上两个对比算法平均排序的差低于临界差(critical difference, CD),则认为它们无显著性差异,否则,认为这两个对比算法有显著性差异.本研究设显著性水平α=0.05, q_α=2.850(第k个对应数), 算法个数k=6, 数据集个数N=11,则

CD=q_α(k(k+1)/6N))^1/2=2.274(16)

图4给出了各个算法在不同评价指标下的对比.坐标轴上的刻度描述了各种算法在不同指标中的平均排序,轴上数字越小,表明算法性能越优.不同线型相接的算法表示在性能之间无显著性差异.由图4可见,MSIO算法排名除在RL指标上比MUCO稍微逊色,在其余指标中均明显较优.

图4 各算法Nemenyi检验的性能对比
Fig.4 Performance comparison of Nemenyi test of each algorithm