在多标记学习框架下,对于现实世界中的一个对象,学习系统在输入空间用一个示例(属性向量)刻画该对象的性质,在输出空间使用类别标记表征该对象的语义信息.多标记学习的目标是为现实世界中同时具有多个语义信息的对象建立分类模型,使得该模型可以有效地预测未见示例的所有相关类别标记^[1].在实际应用中,存在很多同时具有多种语义信息的对象,例如:在文档分类应用中,一篇具有标记“科技”的文档,很有可能同时具有标记“经济”^[2,3,4];多媒体内容标注应用中,一幅图像可能同时具有标记“大海”、“天空”以及“帆船”等^[5,6,7].

形式化地,假设X=¡^d代表d维的示例空间,y={l₁,l₂,…,l_q}代表由q个类别标记组成的标记空间,多标记学

习系统的目标就是利用多标记训练集D={(x_i,Y_i)|1≤i≤m}学习得到一个分类器h:X®2^y.其中,对于每一个多标记样本(x_i,Y_i),x_iÎX为d维特征向量(x_i1,x_i2,…,x_id)^T,Y_iÍy为示例x_i的相关标记集合.对于任何一个未见示例xÎX,多标记分类器h(×)可以预测其相关标记集合h(x)Íy.在很多情况下,多标记学习系统的输出对应于一组实值函

数{f₁,f₂,…,f_q},其中,函数f_k:X®¡(1≤k≤q)的返回值用于确定标记l_k是否为当前待测示例的相关标记.此时,上述

的多标记分类器对应于h(x)={l_k|f_k(x)>0,1≤k≤q}.在过去的10年中,涌现出了大量的多标记学习算法^[8],这些算法采用的共同策略是使用相同的属性集合预测所有的类别标记.换句话说,多标记学习系统返回的q个实值函数{f₁,f₂,…,f_q}是由相同的属性集合训练得到的.

尽管上述策略在算法设计上取得了很大的成功,但是它可能并非最佳选择.举例来说,在图像语义标注系统中,直观上,我们可以认为颜色相关的属性(color-based feature)在判断“蓝天”这一标记上会有好的效果,而纹理相关的属性(texture-based feature)在判断“沙漠”这一标记上会有好的效果;在文本分类应用中,包含“政府”、“大选”等词汇的属性在判断“政治”这一标记上会有好的效果,而包含“GDP”、“纳税”等词汇的属性在判断“经济”这一标记上会有好的效果.上面的例子反映了一个事实,即,一个对象具有多种语义信息的原因在于该对象包含了描述这些语义信息的属性.换言之,每个标记可能具有其自身独特的属性特征,这些属性也是与该标记最相关、对该标记最具有判别能力的属性,称为类属属性(label-specific feature).基于此,文献^[9]中提出了一种基于类属属性的多标记学习算法LIFT.该算法分为两个步骤:类属属性构造与分类模型训练.首先,LIFT在每个标记l_kÎy的正类训练样本和负类训练样本上分别进行聚类分析,利用聚类结果构建标记l_k的类属属性;然后,利用每

个标记的类属属性为该标记训练一个二类分类模型f_k:X®¡(1≤k≤q),以此完成多标记学习任务.

本文在保留LIFT分类模型训练方法的同时,考察了另外3种多标记类属属性构造机制,从而实现LIFT的3种变体——LIFT-INSDIF,LIFT-MDDM以及LIFT-MLF.通过在12个数据集上进行的两组实验,验证了类属属性对多标记学习系统性能的影响以及LIFT采用的类属属性构造方法的有效性.

本文第1节介绍文献^[9]中提出的LIFT算法.第2节给出多标记学习中已有的3种属性转换方法,并基于此设计LIFT的3种变体算法.第3节是本文的实验部分,包括算法参数设置、数据集、结果分析等.最后一节对本文工作进行总结.

多标记学习的最大挑战在于其输出空间的类别标记集合数将随着标记个数的增加成指数规模增长.因此,为有效应对输出空间过大带来的挑战,如何利用标记之间的相关性提高系统的泛化性能,被认为是多标记学习取得成功的关键^[8,10].基于此,已有多标记学习算法的一个共同点在于:重点关注输出空间(标记空间)^[11,12],即考察标记之间的相关性,而较少关注输入空间(属性空间).与已有策略不同,文献^[9]通过构建类属属性对输入空间的性质进行了考察,提出了多标记学习算法LIFT.

给定多标记训练集D={(x_i,Y_i)|1≤i≤m},其中,对于每一个多标记样本(x_i,Y_i),x_iÎX为d维属性向量(x_i1,x_i2,…,x_id)^T,Y_iÍy是示例x_i的相关标记集合.基于此,LIFT算法的的两个步骤可按如下方式完成.

1) 类属属性构建

在该步骤中,LIFT的目的在于构建每个标记的类属属性,以提高多标记学习系统的学习性能.为了达到这个目的,需要考察每个标记所对应样本的内在性质.具体来说,对于标记l_kÎy,其正类示例集合与负类示例集合分别为

换句话说,P_k与N_k分别是由具有标记l_k的示例与不具有标记l_k的示例组成的集合.

为了考察集合P_k与N_k的内在性质,LIFT在两个集合上分别进行聚类分析(clustering analysis).文献^[9]中采

用简单且高效的k-means算法进行聚类分析.在此,将集合P_k的个聚类中心记为.相应地,将集合N_k的个聚类中心记为.为了应对可能存在的类别不平衡问题(即|P_k|<<|N_k|)^[8],LIFT将P_k与N_k的聚类中心个数设置为相等,即.如此,可以认为是对正类示例与负类示例的聚类信息赋

予相同的权重.具体来说,LIFT将示例集合P_k与N_k上的聚类个数设定为

其中,|·|返回集合的势,且rÎ[0,1]是控制聚类个数的参数.

由聚类的性质可知,P_k与N_k的聚类中心刻画了这两个集合中数据的内在结构.因此,聚类中心可以被用于构建标记的类属属性.本质上,类属属性的构建对应于一个从原d维属性空间X到新的d¢维属性空间Z_k的映射j_k:X®Z_k(1≤k≤q).LIFT按如下公式定义映射j_k:

其中,d(×,×)返回两向量之间的距离,文献^[9]中设置为欧氏距离.

2) 分类模型训练

在该步骤中,LIFT使用上一步中构造的类属属性分别训练q个分类模型{f₁,f₂,…,f_q}.参照形式化定义,对于标记l_kÎy,首先根据映射j_k从原训练集D构造其相应的二类训练集BT_k:

其中,若l_kÎY_i,则f(Y_i,l_k)返回+1;否则,返回-1.基于二类训练集BT_k,可以使用任何一种二类分类算法B学习得到

标记l_k对应的分类模型f_k:Z_k®¡.

对于未见示例uÎX,其相关标记按如下方式预测:

LIFT的伪码见文献^[9].

直观上看,解决多标记学习问题最简单的方法是:将多标记学习问题转换成为q个相互独立的二类分类问题,每一个二类分类问题对应于标记空间中的一个类别标记^[5].基于此,Boutell等人在文献^[5]中提出了多标记学习算法Binary Relevance(BR).针对第k个标记l_k,BR首先构建该标记的二类训练集D_k={(x_i,f(Y_i,l_k))|1≤i≤m}.

基于此,使用某种已有的二类分类算法B训练一个二类分类器g_k:X®¡.在预测阶段,对于未见示例x,BR将q个

二类分类器上的预测结果作为该未见示例的相关标记集合,即,Y={l_k|g_k(x)>0,1≤k≤q}.

由此可见,BR中各二类分类模型的训练均基于相同的属性向量,即针对每个标记的类属属性映射为j_k:X®X(1≤k≤q).因此,BR可以看作LIFT算法的一个退化版本(degenerated version).

如第1节所述,多标记类属属性机制本质上对应于构建从原d维属性空间X到新的d¢维属性空间Z_k的映射j_k:X®Z_k(1≤k≤q).下面,本文将给出3种基于多标记类属属性机制的LIFT变体算法——LIFT-INSDIF,LIFT-MDDM以及LIFT-MLF.其中,对应于每个标记的二类分类模型使用不同的属性向量进行训练,而其二类分类模型的训练过程与LIFT保持一致.

·  LIFT-MDDM

多标记降维是一种常用的多标记属性转换方式.在此,我们使用已提出的一种基于过滤策略的多标记降维算法MDDM^[13]构建LIFT的变体算法LIFT-MDDM.MDDM使用希尔伯特-施密特独立标准(Hilbert- schmidt independence criterion,简称HSIC)度量原始属性空间X和标记空间y的关联度(dependency),通过最大化该关联度求得dxd¢维线性转换矩阵P(d¢<<d).最终,LIFT-MDDM针对每个标记的类属属性映射可通过矩阵P构建,即

·  LIFT-INSDIF

如本文引言所述,一个对象具有多种语义信息的原因在于,该对象同时包含了描述这些语义的属性.因此,相比于使用单示例描述方式,使用多个示例描述一个对象能够更好地刻画该对象的多重语义信息^[14].基于此,我们使用多标记学习算法INSDIF^[15]中提出的属性转换方法构建LIFT的变体算法LIFT-INSDIF.通过将示例x与每个标记的正类样本集P_k={x_i|(x_i,Y_i)ÎD,l_kÎY_i}的中心求差&l t;/ span>,INSDIF将示例x转换成为由q个示例组成的示例包,

即,{x^(k)|1≤k≤q},其中,.由此可得LIFT-INSDIF中针对每个标记的类属属性映射:

·  LIFT-MLF

另一种多标记属性转换机制是由原属性空间X构建元级属性(meta-level feature),以此刻画示例和标记之间的关系.在此,我们使用算法MLF^[16]中的元级属性构建方法,实现LIFT的变体算法LIFT-MLF.MLF将每个示例x转换为q×(3r+2)维的元级属性向量[y(x,l₁),…,y(x,l_q)],其中y(x,l_k)(1≤k≤q)是由示例x与P_k中的r个近邻样本构造的3r+2维元级属性.具体来说,y(x,l_k)是示例x与其r个近邻样本的L2距离、L1距离、余弦距离以及与P_k中心的L2距离、余弦距离的结合.由此可得LIFT-MLF中针对每个标记的类属属性映射:

由此可见,以上介绍的BR,LIFT-MDDM,LIFT-INSDIF,LIFT-MLF以及LIFT都是一阶算法^[8],未考虑标记之间的相关性.同时,上述算法的区别在于类属属性的映射方式不同,其二类分类模型的训练过程完全一致.

对于数据集S={(x_i,Y_i)|1≤i≤p},我们使用|S|,dim(S),L(S)及F(S)分别表示样本个数、属性个数、标记个数以及属性类型.除此之外,在此还给出了几种描述多标记数据集性质的统计量^[8,17]:

·  :标记基数(label cardinality),即每个样本具有的平均相关标记个数;

·  :标记密度(label density),即由标记个数归一化的标记基数;

·  :标记多样性(label diversity),即数据集中不同标记集合的个数;

·  :归一化标记多样性,即由样本个数归一化的相异标记集.

表 1按照样本数的多少概括了本文实验所用的数据集,其中包括6个常规规模的数据集(|S|≤5000)以及6个大规模的数据集(|S|>5000).此外,根据惯例对文本数据集rcv1(subset1),rcv1(subset2),eurlex(subject matter)以及tmc2007按照文档频率^[18]进行了降维处理.其中,文档频率最高的2%的属性被保留作为最终属性.

表 1(Table 1)

Table 1 Characteristics of experimental data sets 表 1 实验数据集性质 Data set |S| dim(S) L(S) F(S) LCard(S) LDen(S) LDiv(S) PLDiv(S) Domain URL * enron 1 702 1 001 53 nominal 3.378 0.064 753 0.442 text URL 2 image 2 000 294 5 numeric 1.236 0.247 20 0.010 image URL 3 scene 2 407 294 6 numeric 1.074 0.179 15 0.006 image URL 1 yeast 2 417 103 14 numeric 4.237 0.303 198 0.082 biology URL 3 slashdot 3 782 1 079 22 nominal 1.180 0.054 156 0.041 text URL 2 corel5k 5 000 499 374 nominal 3.522 0.009 3 175 0.635 image URL 1 rcv1 (subset1) 6 000 944 101 numeric 2.880 0.029 1 028 0.171 text URL 1 rcv1 (subset2) 6 000 944 101 numeric 2.634 0.026 954 0.159 text URL 2 bibtex 7 395 1 836 159 nominal 2.402 0.015 2 856 0.386 text URL 3 corel16k (sample 1) 13 766 500 153 nominal 2.859 0.019 4 803 0.349 image URL 4 eurlex (subject matter) 19 348 100 201 numeric 2.213 0.011 2 504 0.129 text URL 5 tmc2007 28 596 981 22 nominal 2.158 0.098 1 341 0.047 text URL 6 URL 1: http://mulan.sourceforge.net/datasets.html URL 2: http://meka.sourceforge.net/#datasets URL 3: http://cse.seu.edu.cn/PersonalPage/zhangml/index.htm

Table 1 Characteristics of experimental data sets 表 1 实验数据集性质

从表 1可以看出:这12个数据集涵盖了很多实际应用领域,且其多标记性质各不相同.由此可见,本文实验所用的数据集是比较充分且全面的,具有较强的概括性.

由于每个样本可能具有多个标记,故传统的单标记评价指标如精度(accuracy)、查准率(precision)、查全率(recall)等在多标记学习中不再适用^[8].假设多标记测试集为T={(x_i,Y_i)|1≤i≤t},多标记学习系统返回的q个实值函数为{f₁,f₂,…,f_q}.在本文的实验中,我们使用5种基于样本的多标记评价指标^[3,19,20]来评价学习系统的性能:

·  Hamming Loss

其中,h(x_i)={l_k|f_k(x_i)>0,1≤k≤q}对应于示例x_i的相关标记集合,Δ返回两集合之间的对称差(symmetric difference).该评价指标考察样本在单个标记上的误分类情况,即:相关标记被预测为无关标记,或者无关标记被预测为相关标记.该评价指标取值越小,则系统性能越优,其最优值为0.

·  Ranking Loss

该评价指标衡量错误排序的标记对的比例,即,无关标记排在相关标记之前的比例.该评价指标取值越小,则系统性能越优,其最优值为0.

·  One-Error

其中,当谓词p成立时,§p¨返回1;否则返回0.该评价指标衡量在样本的类别标记排序中,排在第1位的标记不是

相关标记的样本所占的比例.该评价指标越小,则系统性能越优,其最优值为0.

·  Coverage

其中,rank_f(x_i,l)对应于标记l根据{f₁(x_i),f₂(x_i),…,f_q(x_i)}的值降序排序后所处的位置.该评价指标衡量在测试集T上遍历到样本所有相关标记的平均查找深度.该评价指标取值越小,则系统性能越优,其最优值为1.

·  Average Precision

该评价指标考察在样本的标记排序序列中,排在该样本相关标记之前的标记仍为相关标记的比例.该评价指标取值越大,则系统性能优越,其最优值为1.

为便于对比,本文通过除以标记个数L(S)将评价指标Coverage规格化到区间^[0,1].上述基于样本的评价指标首先衡量学习系统在每个测试样本上的分类性能,然后返回整个测试集的均值作为最终结果.

此外,本文还采用一种基于标记的评价指标Macro-averaging AUC^[21].与基于样本的评价指标不同,基于标记的评价指标首先衡量学习系统在每个标记上分类性能,然后返回在所有标记上的均值作为最终结果.

·  Macro-averaging AUC

其中,分别对应于含有标记l_k的测试样本集合与不含有标记l_k的测试样本集合.值得注意的是,上述公式可由AUC与Wilcoxon-Mann-Whitney统计量的相互关系导出^[22].此外,该评价指标取值越大,系统的性能越优,其最优值为1.

本文将给出6种算法在上述12个数据集上的实验结果,包括BR,ML-kNN,LIFT,LIFT-MDDM,LIFT-INSDIF以及LIFT-MLF.根据文献^[9],设定LIFT的参数r=0.1;根据文献^[23],设定ML-kNN的近邻个数k=10;对于LIFT-MDDM,为与原文保持一致,控制转换后特征空间维度(即d¢)的参数thr设定为99.9%;对于LIFT-MLF,我们采取原文的策略,对近邻个数r在区间^[10,100]进行调节,并最终设定为10.此外,为了对比的公平,所有算法的基二类分类器均使用线性核LIBSVM^[24].

在每个数据集中,我们采用无放回抽样选取50%的样本构成训练集,余下的50%样本构成测试集,抽样过程重复10次并记录10次实验的均值和方差.

本文共有两组实验:第1组将没有使用类属属性机制的BR以及常用的ML-kNN算法与采用类属属性机制的算法LIFT,LIFT-MDDM,LIFT-INSDIF以及LIFT-MLF进行对比,目的在于验证类属属性机制对多标记学习的影响;第2组将LIFT与算法LIFT-MDDM,LIFT-INSDIF,LIFT-MLF进行对比,目的在于验证LIFT所采用的类属属性构建方法的有效性.

表 2与表 3给出了6个算法在12个数据集上的实验结果,实验结果采用均值±方差(mean±std)的形式表示.对于每个评价指标,­表示其值越大,性能越优;相应地,¯表示其值越小,性能越优.此外,对比算法中性能的最好的结果使用黑体标出.

表 2(Table 2)

Table 2 Predictive performance of each comparing algorithm (mean±std) on the six regular-scale data sets 表 2 对比算法在6个常规规模数据集上的实验结果(mean±std) Criteria Algorithms enron image scene yeast slashdot corel5k Hamming loss ¯ BR 0.060±0.001 0.185±0.004 0.111±0.003 0.201±0.003 0.049±0.001 0.012±0.001 ML-kNN 0.055±0.001 0.186±0.005 0.092±0.003 0.206±0.001 0.053±0.001 0.009±0.001 LIFT-INSDIF 0.053±0.001 0.184±0.002 0.109±0.002 0.201±0.002 0.048±0.001 0.010±0.001 LIFT 0.048±0.001 0.163±0.003 0.084±0.002 0.197±0.002 0.040±0.001 0.010±0.001 LIFT-MDDM 0.049±0.001 0.205±0.004 0.107±0.002 0.206±0.003 0.046±0.001 0.010±0.001 LIFT-MLF 0.102±0.019 0.245±0.002 0.151±0.005 0.224±0.002 0.120±0.018 0.010±0.001 Ranking loss ¯ BR 0.308±0.007 0.285±0.009 0.171±0.005 0.315±0.005 0.216±0.005 0.655±0.004 ML-kNN 0.100±0.002 0.194±0.008 0.085±0.004 0.182±0.003 0.178±0.005 0.137±0.002 LIFT-INSDIF 0.091±0.002 0.177±0.007 0.094±0.006 0.174±0.003 0.120±0.003 0.135±0.002 LIFT 0.084±0.003 0.155±0.007 0.069±0.002 0.169±0.004 0.100±0.003 0.131±0.003 LIFT-MDDM 0.095±0.003 0.223±0.016 0.089±0.003 0.180±0.004 0.117±0.005 0.142±0.002 LIFT-MLF 0.350±0.070 0.364±0.067 0.154±0.012 0.197±0.003 0.311±0.031 0.230±0.008 One-Error ¯ BR 0.498±0.012 0.406±0.012 0.348±0.007 0.256±0.008 0.501±0.007 0.849±0.008 ML-kNN 0.328±0.013 0.356±0.010 0.246±0.009 0.247±0.010 0.670±0.017 0.744±0.012 LIFT-INSDIF 0.289±0.018 0.333±0.013 0.269±0.015 0.234±0.008 0.439±0.006 0.696±0.009 LIFT 0.254±0.005 0.289±0.012 0.212±0.011 0.229±0.011 0.430±0.013 0.706±0.012 LIFT-MDDM 0.262±0.016 0.422±0.026 0.263±0.009 0.236±0.007 0.406±0.010 0.697±0.004 LIFT-MLF 0.627±0.084 0.515±0.077 0.407±0.027 0.252±0.008 0.789±0.075 0.728±0.014 Coverage ¯ BR 0.595±0.010 0.280±0.008 0.158±0.004 0.641±0.005 0.238±0.005 0.898±0.003 ML-kNN 0.265±0.006 0.209±0.008 0.084±0.004 0.465±0.005 0.191±0.005 0.312±0.004 LIFT-INSDIF 0.249±0.006 0.194±0.006 0.093±0.004 0.458±0.005 0.117±0.003 0.294±0.005 LIFT 0.245±0.007 0.178±0.007 0.071±0.002 0.458±0.007 0.115±0.003 0.313±0.008 LIFT-MDDM 0.266±0.007 0.232±0.013 0.088±0.002 0.472±0.006 0.117±0.005 0.309±0.004 LIFT-MLF 0.654±0.064 0.318±0.047 0.142±0.010 0.477±0.004 0.271±0.030 0.496±0.016 Average precision ­ BR 0.449±0.011 0.709±0.008 0.771±0.005 0.672±0.005 0.572±0.005 0.101±0.003 ML-kNN 0.609±0.010 0.769±0.007 0.853±0.005 0.744±0.005 0.481±0.012 0.240±0.005 LIFT-INSDIF 0.648±0.007 0.785±0.008 0.838±0.009 0.756±0.005 0.666±0.005 0.267±0.002 LIFT 0.685±0.005 0.811±0.007 0.875±0.006 0.763±0.006 0.671±0.008 0.280±0.004 LIFT-MDDM 0.677±0.007 0.731±0.016 0.844±0.005 0.747±0.007 0.687±0.006 0.267±0.002 LIFT-MLF 0.352±0.067 0.635±0.056 0.750±0.017 0.721±0.006 0.339±0.014 0.248±0.006 Macro-Avg AUC ­ BR 0.579±0.007 0.705±0.007 0.801±0.003 0.565±0.003 0.656±0.009 0.518±0.001 ML-kNN 0.606±0.007 0.813±0.006 0.927±0.003 0.645±0.007 0.586±0.006 0.530±0.003 LIFT-INSDIF 0.650±0.016 0.818±0.005 0.910±0.003 0.642±0.014 0.834±0.013 0.600±0.007 LIFT 0.688±0.018 0.844±0.006 0.943±0.002 0.673±0.007 0.847±0.009 0.679±0.006 LIFT-MDDM 0.659±0.015 0.782±0.010 0.914±0.004 0.629±0.012 0.826±0.019 0.631±0.007 LIFT-MLF 0.498±0.002 0.610±0.031 0.828±0.007 0.574±0.007 0.496±0.001 0.586±0.009

Table 2 Predictive performance of each comparing algorithm (mean±std) on the six regular-scale data sets 表 2 对比算法在6个常规规模数据集上的实验结果(mean±std)

表 3(Table 3)

Table 3 Predictive performance of each comparing algorithm (mean±std) on the six large-scale data sets 表 3 对比算法在6个大规模数据集上的实验结果(mean±std) Criteria Algorithms rcv1 (subset1) rcv1 (subset2) bibtex corel16k (sample1) eurlex (subject matter) tmc2007 Hamming loss ¯ BR 0.031±0.001 0.028±0.001 0.015±0.001 0.020±0.001 0.008±0.001 0.071±0.001 ML-kNN 0.028±0.001 0.025±0.001 0.014±0.001 0.019±0.001 0.008±0.001 0.075±0.001 LIFT-INSDIF 0.027±0.001 0.024±0.001 0.013±0.001 0.019±0.001 0.008±0.001 0.066±0.001 LIFT 0.026±0.001 0.023±0.001 0.013±0.001 0.019±0.001 0.008±0.001 0.061±0.001 LIFT-MDDM 0.027±0.001 0.024±0.001 0.013±0.001 0.019±0.001 0.009±0.001 0.063±0.001 LIFT-MLF 0.027±0.001 0.024±0.001 0.014±0.001 0.020±0.001 0.033±0.009 0.115±0.018 Ranking loss ¯ BR 0.279±0.004 0.251±0.004 0.303±0.004 0.422±0.001 0.463±0.003 0.216±0.003 ML-kNN 0.089±0.002 0.098±0.003 0.226±0.006 0.175±0.001 0.054±0.001 0.098±0.002 LIFT-INSDIF 0.066±0.001 0.066±0.002 0.091±0.002 0.163±0.001 0.052±0.001 0.064±0.001 LIFT 0.048±0.001 0.050±0.002 0.082±0.003 0.165±0.002 0.057±0.001 0.051±0.001 LIFT-MDDM 0.064±0.002 0.065±0.002 0.104±0.002 0.171±0.002 0.060±0.001 0.060±0.003 LIFT-MLF 0.076±0.006 0.074±0.002 0.191±0.006 0.191±0.005 0.202±0.045 0.684±0.282 Criteria Algorithms rcv1 (subset1) rcv1 (subset2) bibtex corel16k (sample1) eurlex (subject matter) tmc2007 One-Error ¯ BR 0.602±0.011 0.522±0.009 0.559±0.004 0.920±0.006 0.492±0.005 0.339±0.003 ML-kNN 0.510±0.007 0.524±0.013 0.610±0.005 0.747±0.006 0.339±0.004 0.320±0.004 LIFT-INSDIF 0.470±0.011 0.470±0.008 0.413±0.003 0.726±0.007 0.345±0.005 0.248±0.003 LIFT 0.412±0.008 0.421±0.009 0.407±0.008 0.691±0.008 0.329±0.006 0.213±0.004 LIFT-MDDM 0.430±0.009 0.431±0.007 0.416±0.004 0.713±0.015 0.370±0.005 0.234±0.006 LIFT-MLF 0.467±0.015 0.464±0.010 0.545±0.008 0.715±0.055 0.732±0.064 0.511±0.185 Coverage ¯ BR 0.448±0.005 0.383±0.006 0.461±0.006 0.673±0.002 0.639±0.003 0.380±0.003 ML-kNN 0.188±0.003 0.201±0.004 0.365±0.009 0.339±0.003 0.092±0.001 0.195±0.002 LIFT-INSDIF 0.150±0.001 0.145±0.003 0.167±0.002 0.318±0.003 0.093±0.002 0.148±0.001 LIFT 0.120±0.002 0.123±0.005 0.149±0.006 0.326±0.003 0.101±0.002 0.129±0.001 LIFT-MDDM 0.155±0.004 0.147±0.002 0.190±0.004 0.329±0.003 0.106±0.002 0.142±0.004 LIFT-MLF 0.183±0.011 0.173±0.004 0.318±0.008 0.385±0.008 0.321±0.091 0.683±0.146 Average precision ­ BR 0.383±0.007 0.434±0.005 0.363±0.004 0.085±0.002 0.358±0.003 0.643±0.002 ML-kNN 0.513±0.003 0.515±0.008 0.327±0.006 0.279±0.002 0.650±0.003 0.712±0.003 LIFT-INSDIF 0.537±0.006 0.562±0.004 0.526±0.004 0.283±0.004 0.606±0.007 0.781±0.002 LIFT 0.605±0.003 0.617±0.006 0.542±0.008 0.311±0.003 0.626±0.004 0.814±0.002 LIFT-MDDM 0.580±0.004 0.600±0.004 0.518±0.004 0.289±0.005 0.580±0.005 0.795±0.004 LIFT-MLF 0.544±0.009 0.566±0.006 0.376±0.007 0.301±0.018 0.167±0.013 0.222±0.091 Macro-Avg AUC ­ BR 0.609±0.003 0.599±0.004 0.624±0.002 0.516±0.001 0.558±0.002 0.724±0.002 ML-kNN 0.727±0.007 0.698±0.005 0.654±0.007 0.566±0.003 0.765±0.005 0.785±0.003 LIFT-INSDIF 0.862±0.007 0.854±0.008 0.868±0.003 0.653±0.006 0.855±0.005 0.873±0.001 LIFT 0.917±0.004 0.901±0.007 0.902±0.004 0.695±0.002 0.837±0.010 0.908±0.001 LIFT-MDDM 0.859±0.006 0.840±0.003 0.847±0.003 0.657±0.003 0.828±0.013 0.890±0.003 LIFT-MLF 0.801±0.007 0.791±0.013 0.749±0.006 0.573±0.007 0.500±0.001 0.503±0.013

Table 3 Predictive performance of each comparing algorithm (mean±std) on the six large-scale data sets 表 3 对比算法在6个大规模数据集上的实验结果(mean±std)

对于第1组实验,我们分别统计了BR,ML-kNN与LIFT及其变体算法在12个数据集、6个评价指标上的72个对比结果.与LIFT和LIFT-INSDIF相比,BR没有胜出的情况;与LIFT-MDDM相比,胜出的情况仅占5.56%;与LIFT-MLF相比,胜出的情况占44.44%.与LIFT,LIFT_INSDIF以及LIFT_MDDM相比,ML-kNN胜出的情况分别仅占6.9%,15.3%以及30.6%;与LIFT_MLF相比,胜出的情况占66.7%.从BR,ML-kNN与LIFT,LIFT-INSDIF,LIFT-MDDM的对比结果可以看出,有效的类属属性可以较大程度地提高多标记学习算法的学习性能.值得注意的是,LIFT-MLF的性能在一些数据集上比BR,ML-kNN的性能差.一个可能的原因是,该算法使用近邻样本构造元级属性的方式不能有效地构造标记的类属属性.可见,并非所有的属性转换机制都能十分有效地地构造类属属性.

如第2节所述,BR可认为是LIFT及其变体算法的退化(degenerated)版本.为了进一步验证类属属性对多标记学习算法的影响,对于每个评价指标,本文使用成对T检验(检验水平a=0.05)对BR与LIFT及其变体算法进行统计分析(见表 4(a)).表 4(a)中的结果进一步证实了上述结论,即:类属属性是提高多标记学习系统泛化性能的可行途径,但并非所有的多标记属性转换机制都能有效地构建类属属性.

表 4(Table 4)

Table 4(a) Paired T-test results (win/tie/lose) of comparing BR against algorithms with label-specific features mechanism in terms of each criteria on the total twelve data sets at significance level a=0.05 表 4(b) 对于每个评价指标,LIFT与其变体算法在12个数据集上的成对T检验(a=0.05)结果(win/tie/lose) Criteria BR versus LIFT-INSDIF LIFT LIFT-MDDM LIFT-MLF Hamming loss 1/2/9 0/0/12 3/0/9 7/1/4 Ranking loss 0/0/12 0/0/12 0/0/12 3/1/8 One-Error 0/0/12 0/0/12 0/1/11 6/0/6 Coverage 0/0/12 0/0/12 0/0/12 3/1/8 Average precision 0/0/12 0/0/12 0/0/12 6/0/6 Macro AUC 0/0/12 0/0/12 0/0/12 5/0/7

Table 4(a) Paired T-test results (win/tie/lose) of comparing BR against algorithms with label-specific features mechanism in terms of each criteria on the total twelve data sets at significance level a=0.05 表 4(a) 对于每个评价指标,BR与使用类属属性机制算法在12个数据集上的成对T检验(a=0.05)结果(win/tie/lose)

与第1组实验相同,我们统计了LIFT及其3个变体算法在12个数据集、6个评价指标上的72个对比结果.其中,LIFT排在第1位的情况占87.5%,排在第2位和第3位的情况分别仅占11.11%和1.39%,且没有排在最后一位与倒数第2位的情况发生.由以上统计可以看出,LIFT的学习性能优秀,进而说明LIFT的类属属性构造方法是非常有效的.

参考第1组实验,本文使用成对T检验(检验水平a=0.05)对LIFT及其3种变体算法在每个数据集上的实验结果进行统计分析(见表 4(b)).从表 4(b)中可以看出:

表 4(Table 4)

Table 4(b) Paired T-test results (win/tie/lose) of comparing LIFT against its variants in terms of each criteria on the total twelve data sets at significance level a=0.05 表 4(b) 对于每个评价指标,LIFT与其变体算法在12个数据集上的成对T检验(a=0.05)结果(win/tie/lose) Criteria LIFT versus LIFT-INSDIF versus LIFT-INSDIF LIFT-MDDM LIFT-MLF LIFT LIFT-MDDM LIFT-MLF Hamming loss 10/0/2 11/0/1 11/1/0 2/0/10 5/4/3 10/2/0 Ranking loss 10/0/2 12/0/0 12/0/0 2/0/10 7/0/5 12/0/0 One-Error 9/3/0 9/2/1 11/1/0 0/3/9 2/4/6 9/3/0 Coverage 7/2/3 11/1/0 12/0/0 3/2/7 9/1/2 12/0/0 Average precision 12/0/0 11/0/1 11/1/0 0/0/12 4/1/7 9/1/2 Macro AUC 11/0/1 12/0/0 12/0/0 1/0/11 5/3/4 12/0/0 Criteria LIFT-MDDM versus LIFT-MLF versus LIFT LIFT-INSDIF LIFT-MLF LIFT LIFT-INSDIF LIFT-MDDM Hamming loss 1/0/11 3/4/5 10/2/0 0/1/11 0/2/10 0/2/10 Ranking loss 0/0/12 5/0/7 12/0/0 0/0/12 0/0/12 0/0/12 One-Error 1/2/9 6/4/2 11/1/0 0/1/11 0/3/9 0/1/11 Coverage 0/1/11 2/1/9 12/0/0 0/0/12 0/0/12 0/0/12 Average precision 1/0/11 7/1/4 11/0/1 0/1/11 2/1/9 1/0/11 Macro AUC 0/0/12 4/3/5 12/0/0 0/0/12 0/0/12 0/0/12

Table 4(b) Paired T-test results (win/tie/lose) of comparing LIFT against its variants in terms of each criteria on the total twelve data sets at significance level a=0.05 表 4(b) 对于每个评价指标,LIFT与其变体算法在12个数据集上的成对T检验(a=0.05)结果(win/tie/lose)

(a) 在绝大多数情况下,LIFT的分类性能优于其他3种变体算法——LIFT-INSDIF,LIFT-MDDM以及LIFT-MLF.在很少数据集的个别评价指标上,LIFT的性能差于LIFT-INSDIF以及LIFT-MDDM;

(b) 除了评价指标One-Error及Coverage,LIFT-INSDIF与LIFT-MDDM在其余4个评价指标上的结果相当.LIFT与LIFT-INSDIF的性能优于或至少相当于LIFT-MDDM的性能,这说明相比于通过属性选择赋予每个标记相同的类属属性(即公式(6)),为每个标记构造不同的类属属性(即公式(3)与公式(7))是一种更有效的属性转换机制;

(c) 与表 4(a)中得到的结论一致,在每个评价指标上,LIFT-MLF的性能都要差于其余3种算法.可能的原因是,该算法使用近邻样本构造元级属性(即公式(8))的方式不能有效地构造标记的类属属性.

概括来说,表 4(b)中的成对T检验统计结果证明了LIFT中的属性转换机制能非常有效地构造类别标记的类属属性.因此,LIFT的类属属性机制可以作为很多多标记学习算法的预处理(pre-processing)部分,以提高学习系统的学习性能.

与许多关注标记空间的算法不同,本文考察在属性空间进行操作对多标记学习算法学习性能的影响.本文在12个数据集上进行了大量的实验,将LIFT及其变体算法与BR进行对比分析,结果显示:有效的类属属性构造,的确能较大程度地提高多标记学习算法的学习性能.同时,LIFT与其变体算法的统计检验结果表明,LIFT的属性转换机制可有效地构造类别标记的类属属性.

值得注意的是,本文中所有算法均忽略标记之间的相关性.未来,我们可以尝试将类属属性和标记之间的相关性相结合,一种直观的方式是,为与标记配对相关的分类器^[25]设计对应的二阶类属属性.