一种基于增量式超网络的多标签分类方法

2019-09-05 10:32陈知良李智星卜亚楠陈乔松

重庆邮电大学学报(自然科学版) 2019年4期

王进,陈知良,李航，李智星,卜亚楠,陈乔松,邓欣

(1.重庆邮电大学计算机科学与技术学院数据工程与可视计算重点实验室，重庆 400065；2.重庆邮电大学软件工程学院, 重庆 400065)

0 引言

多标签分类问题是数据挖掘和机器学习领域的研究热点。在多标签分类问题中，一个样本被同时赋予多个类别标签。层次多标签分类是一种特殊的多标签分类问题。在层次多标签分类问题中，一个样本不仅同时具有多个类别标签，而且这些类别标签被组织在一定的层次结构中。层次多标签分类方法被广泛应用于许多领域，如文本分类[1-2]，图像分类[3-4]，基因功能预测[5-8]等。

与多标签分类问题相比，层次多标签分类问题要求分类方法所预测的标签集合必须满足标签的层次约束。层次约束是指只有父节点出现，其子节点才有出现的可能性。目前，针对层次多标签约束问题主要有2种解决方法。一种是根据传统的多标签分类模型对层次样本数据进行分类，之后再对分类结果根据层次结构进行约束。由于父节点比其孩子标签更靠近根节点，且越靠近下层节点的标签不平衡性越高，预测出的父标签的置信度必定大于子标签的置信度，因此在分类后，一般根据父节点的预测结果对子节点进行层次约束。例如，当父标签预测为0，其所有孩子标签根据层次结构的约束全部为0。另一种是在分类过程中就考虑标签间层次结构的约束问题。文本数据标签层次结构示例如图1，只有“粮食”和“风景”标签节点出现后，再对“小麦”和“天空”标签节点是否出现进行预测。

图1 文本数据标签层次结构示例Fig.1 Example of textual data label hierarchy

此外，在层次标签结构中，越靠近下层节点的标签往往具有更为丰富的语义，具有更重要的分类意义和价值，因此，针对越靠近下层节点的标签分类价值越大。图1中，相比“粮食”和“风景”标签节点，“小麦”和“天空”标签节点具有更为丰富的语义，更重要的分类价值。但是，在层次多标签分类问题中，越靠近下层的标签节点出现的频率越低，造成类别标签分布不平衡的问题。图2为ImageCLEF07A[9]数据集的层次标签结构中，每层标签在训练集中出现频率的平均值。从图2中可以看出，该数据集的标签随着层数的增加，深层次的类别标签出现的频率急剧减少。在机器学习领域，类别不平衡问题对机器学习方法的性能造成很大的影响。所以，如何降低标签的不平衡性对分类性能起着决定性的作用。

图2 ImageCLEF07A数据层次标签的统计Fig.2 Statistics of ImageCLEF07A data level label

利用超网络模型处理多标签分类问题可以提高多标签分类问题性能、为解决多标签分类问题提供了新的理论和方法[10-12]。但由于层次多标签分类问题中，标签具有的特殊结构，传统的多标签超网络无法满足分类后层次标签之间的约束问题。针对层次多标签分类问题，本文对传统超网络模型进行改进，提出了一种基于增量式超网络的多标签分类方法。该方法首先考虑标签的层次结构以及标签的稀疏性，将超网络的超边按照给定的标签层次结构进行组织，构建层次多标签超网络模型；然后采用增量式的学习方法对层次多标签超网络模型进行演化学习；最后通过增量式超网络方法对未知样本进行标签预测。增量式超网络学习方法不仅可以满足层次多标签分类问题中的标签结构约束，而且还能够通过利用标签之间的关联关系，有效地减少不平衡问题对分类性能的影响。

1 相关工作

层次多标签分类问题是一类特殊的多标签分类问题。国内外学者对其进行了深入的研究[13-16]。层次多标签分类方法大致可以分为局部方法和全局方法2类。局部层次分类策略通过自上而下的方式[17]在标签层次结构中的每一层训练一个多标签分类器。局部层次分类策略总结为以下几种[18]：①对每个节点建立一个二分类器(local classifier per node, LCN)；②对每个节点的孩子建立一个多分类器(local classifier per parent node, LCPN)；③对每一层训练一个多分类器(local classifier per level, LCL)。LCN方法[19]旨在对每个节点建立一个二分类器，然后再进行节点的分类预测；LCPN是每个父节点为了区分其子类类别建立的多分类器[20]；LCL策略采用为层次标签的每一层建立一个多标签分类器，这样就可以考虑到每一层预测类别之间都可能存在着一定的关联性。由Cerri等[21]提出的HMC_LP是一种非分层的层次多标签分类方法。HMC_LP采用标签组合的方法，将原问题转化为一个分层的HMC的单标签问题。这个标签组合过程考虑同一层兄弟标签之间的关系。文献[22]中提出了一种基于决策树的层次多标签分类方法Clus，主要基于决策树为基分类器对层次多标签分类模型进行训练。根据不同的层次分类策略分为Clus-SC，Clus-HSC和Clus-HMC，而Clus-ens是该方法的集成模型。由于该方法对每个节点或每层节点都使用一个树形分类器进行分类。全局层次分类策略不同于局部层次分类策略，该方法只训练一个分类器来处理所有层次结构类。新实例的分类仅在一步中实现。由于全局层次分类策略的分类器必须考虑层次多标签分类问题的标签结构特殊性，因此，除非算法适合处理类层次结构，否则一般不可能使用传统的多标签分类算法。HMC_predict是基于神经网络的一个改进算法，分别使用RP和BP作为不同神经网络基分类器进行方法思路的讨论，旨在将学习过程分成若干个步骤，结合神经网络模型降低损失函数来训练模型[23]。该方法最大的优点是学习过程中渗入增广特征矢量来增加标签的依赖，通过使用真实标签作为特征向量的一部分，保证标签之间的关联性。该方法由于使用神经网络作为基分类器，因此不具有层次可解释性。

多标签超网络是一种结构灵活、模型简单的多标签分类方法[24-25]。该方法能够有效地挖掘类别标记之间的关联关系，并利用类别标记之间的关联提高多标签分类问题的分类性能。在文献[24]中，提出一种利用协同演化的学习方法，挖掘利用标签之间高阶关联关系。文献[10]中提出一种2阶段演化学习方法，通过利用标签之间关联关系，处理多标签分类问题中的标签分布不平衡问题。虽然超网络方法可以利用标签的关联性有效地解决多标签分类问题，但在层次多标签分类问题中，标签之间的关联关系是通过标签层次结构体现的，而一般的多标签超网络方法并没有考虑这种具有层次结构的关联关系，因此，一般的多标签超网络分类方法并不能直接用于解决层次多标记分类问题。

2 层次多标签增量式超网络分类方法

2.1 层次多标签定义

图3 标签层次结构示例Fig.3 Example of the label hierarchy

2.2 多标签超网络模型

根据人类认知学习的3个基本准则：持续性、Glolity准则以及组合准则，B.T.Zhang[26]提出了一种基于概率统计的超网络模型，其结构灵活、分类模型简单、能够有效地表示对象之间的高阶关联。在多标签问题中，超网络模型同样发挥着很好的作用。文献[24-25]中分别提出了2种多标签超网络算法MLHN和Co-MLHN。通过将传统的超网络模型针对多标签分类问题进行改进，多标签超网络可以有效地表示和利用标签之间的关联来提高多标签分类的性能。此外，与大多数多标签分类方法相比，多标签超网络算法的时间复杂度较低，它能以标签数量的线性时间复杂度，有效地挖掘标记之间的关联。超网络[24]是一种基于超图的认知学习模型，是由大量超边组成的概率超图模型，通过超边库表达模式空间中数据的分布概率，以达到预测的效果。多标签超网络模型是一种基于加权的随机超图模型，不仅分类效果较好，而且超边可以反映顶点之间的高阶可关联性。图4表示多标签超网络模型，多标签超网络可以用一个3元组H={V,E,W}表示，其中，V={x1,x2,…,xn}为顶点集，E为超边集合，其由顶点子集，标签和权重3部分组成，W为超边对应标签权重。通过类别标签向量和权值向量，多标签超网络分类模型能够表示标签类别之间任意阶关联。

图4 多标签超网络模型Fig.4 Multi-labelhypernetwork model

给定一个具有m个类别标签的多标签训练样本数据集，多标签超网络模型通过含有大量超边的超边集合及其类别标签向量和权值向量，表示数据样本与类别标签向量之间的联合概率分布P(x,yi|W)(1≤i≤m)为

(1)

(1)式中Z(W)为规范化项；yi∈{0,1}；ε为能量函数，其计算方法定义为

(2)

(2)式中wji为超边ej中类别标签i的权值；I为匹配函数，表达式为

(3)

(3)式中dist(x,ej)表示产生超边ej的样本特征数据与该条样本特征数据x之间的距离；δj表示设定的阈值δj。

多标签超网络模型输出：给定一个待分类多标签数据样本x，多标签超网络首先计算该样本与各类别标签的条件概率，输出一个概率向量P=[P(y1=1|x),P(y2=1|x),…,P(ym=1|x)]，P中的每一维向量表示相应类别标签被预测给待分类样本的概率，最后选取条件概率大于阈值t(t一般设置成0.5)的类别标签作为预测类别标签。多标签超网络算法主要分成训练阶段和测试阶段，训练阶段主要步骤：①超边库的生成；②超边替代；③权重更新。测试阶段主要对输入的样本进行标签预测。

2.3 基于增量式超网络的多标签分类方法

改进的层次多标签增量式超网络分类算法的输出结果能满足层次分类的限制条件，由于层次结构的递增出现标签不平衡问题，该算法在分类中能够巧妙地降低下一层标签的不平衡程度，因此，在标签层次分类中表现出较好的效果。层次多标签增量式超网络模型通过演化学习，可以使多标签超网络模型解决层次分类的问题。针对层次多标签结构，在初始化标签向量的时候，根据其父节点的标签与近邻样本的概率权重和进行设置与调整。由于每次预测该层的标签是基于父节点结果的分类基础上，因此，基于该父节点的子标签的正负样本数据概率差异减少，在对样本进行分类时，很大程度地减少了不平衡标签造成的分类精度差。当层次多标签增量式超网络模型演化学习完成后，根据学习模型，对测试样本数据进行预测。只有当父节点的权重值大于阈值t，即父节点预测为1的前提下，才对其子节点进行预测，所以层次多标签增量式超网络分类方法的输出结果满足层次结构的约束。考虑到每个样本中出现标签的概率占整个标签集合的极小部分，因此，层次多标签增量式超网络分类方法在演化学习时，把标签向量分成正(PW)、负标签向量(NW)。正标签向量表示该标签的权重信息对于出现该标签起积极作用，负标签向量则反之。这样设定可以减少空间复杂度的开销，显示了算法的优势。正、负标签的组织结构相同，只是在计算时，一个权重对标签预测为1产生正影响(PW)，一个产生负影响(NW)。基于增量式超网络的多标签分类模型流程图如图5，只有当label1的父节点预测为1(即yi1m)时，label2的子节点(yi2)才能进行下一步的预测，以此类推。

接下来将分别详细介绍增量式超网络多标签分类方法的分类学习与预测阶段。

1)增量式超网络多标签分类方法分类阶段。主要对未知样本进行标签分类。对于增量式超网络多标签分类方法分类阶段的具体步骤如下。

算法1分类阶段的伪代码。

输入：增量式超网络模型H=(V,E,W)；未知标签的特征数据：x；匹配临界值&；阈值标签向量：t=|t1,t2,…,tn|；k近邻样本个数K；标签层次数m；

输出：预测的阈值P；标签向量y；

1.查找该条测试样本x的K近邻样本

2.从该样本的k近邻样本所产生的超边集合中选取与其小于临界值&所匹配的超边集M

3.for eachei∈M

4. 把yj加入集合countlabel(y)中，并对其统计数加1

5. 根据yj属于ei的正向集pos(y)或负向集neg(y)，对相应的正向集权重Wneg(yj)或者负向集Wneg(yj)权重统计

6. for each yq∈countlabel(y)

7. pro(yq)=pos(yq)/(pos(yq)+neg(yq))

8. end

9. end

10.for pro (hj)∈pro &P(y)=1≤hpy(hj)

11.ifpro(hj)>t

12.yhj=1

13. else

14.yhj=0

15. end if

16.end

2)增量式超网络多标签分类方法学习阶段。具体步骤如下。

算法2演化学习层次多标签超网络模型伪代码。

输入：训练样本集合D={(xi,xj)|1≤i≤N|}；学习速率μ；标签层次关系P；学习次数T；每条样本的k近邻样本；阈值δ；

输出：演化层次多标签超网络模型H*。

1．初始化超网络模型H0=(E,Y,W)；

2．替换层次多标签超网络模型中fitness较低超边；

3．fort=1 toTdo

4． forn=1 toNdo

5．获取第n条训练样本(xn,yn)

6．根据算法1对当前超网络模型H进行分类，预测该条样本标签y*=[y1,y2,…,yn]

7．从超边集合M中选取近邻超边集合Mk

8． forj=1 tom

9． if (yij≠yj) &yj>δ

10． for eachek∈Mk

11．更新权重Wpos(yj)=Wpos(yj)-ΔWpos(yj)

12．更新权重Wneg(yj)=Wneg(yj)+ΔWneg(yj)

13． end

14． end if

15． if (yij≠yj) &yj<δ

16． for eachek∈Mk

17．更新权重Wpos(yj)=Wpos(yj)+ΔWpos(yj)

18．更新权重Wneg(yj)=Wneg(yj)-ΔWneg(yj)

19． end

20． end if

21． end

22． Ht= H(t-1)+DH(t-1)

23． end

24．end

3 实验

本文采用的实验环境为2.30 GHz CPU，8.0 GB内存，Windows7操作系统，Java语言，Eclipse环境。实验部分主要包括：①包括实验数据；②评价指标以及参数的说明；③实验结果及分析。

3.1 实验数据

本次实验的数据集如表1所示，数据来源于公开数据集[9]，除了WIPO标签数据具有4层结构外，其余数据的标签都具有3层的层次结构。因为WIPO数据集标签结构含有根节点，因此，该数据的标签结构为树形结构，其余数据的标签层次结构为森林。文本数据集Reuters和Enron为多路径层次标签集合，其余数据集都为单路径层次标签结合。

表1 实验数据集介绍

3.2 评价指标以及参数的说明

1)层次损失[27](hierarchical loss, H-loss) 。H-loss是专门针对HMC任务提出来的，假设层次标签满足树形结构。该度量基于汉明损失或对称损失返回一个层次多标签向量的预测值与真实值之间的对称差。在该度量中，如果已经惩罚了超类的错误，就不再惩罚子类中的错误。例如，当已经惩罚了层次结构中的某个标签，那么该评测指标不再对其标签的子类产生任何损失。

(4)

(4)式中，anc(i)表示节点i的超类集合；c1,c2,…,ck表示固定成本系数。Cesa-Bianchi等[28]提出了2种计算成本系数的方法：均匀损失和归一化损失。本文采用的是均匀损失方法来计算成本系数。

2)层次多标签分类损失(HMC-loss)[27]。由于层次损失(H-loss)没有考虑到相同的假阳性预测在较低层比较高层产生更大的损失，因此，提出了层次多标签分类损失(HMC-loss)为

(5)

(5)式中，c1,c2,…,ck表示在标准的树状层次结构中定义的H-loss固定成本系数。对于DAGs结构来说，非根节点的损失定义为ci=∑jcj/|child(j)|，j为i的父亲节点。对于假正例(FP)和假反例(FN)的不同权重系数α和β，进行损失敏感设置。当α=β=1，层次多标签分类损失(HMC-loss)就等于等权重值的汉明损失，或者说是均匀损失。层次多标签分类损失(HMC-loss)有效地解决了层次损失(H-loss)的空预测问题，因为该评测指标不是只惩罚预测错的根节点，同时考虑了每个节点预测错误所导致的损失。

3)层次F1值。该评价措施是对每个标签分类结果精度和召回率信息的一个融合。

(6)

3.3 实验结果及分析

本节主要根据上述评价指标对层次多标签分类和不平衡数据标签的分类进行实验并进行结果分析。HMC_MLHN方法是利用传统的超网络对层次数据进行分类，由于输出结果不满足层次约束的限制条件，文献[23]对第3步方法进行了纠正，对传统的超网络进行层次约束。因为增量式超网络方法输出的是测试样本的置信度，而置信度由近邻超边的正负权重产生，如果标签预测出的置信度大于阈值t(本文设置为0.5)，则表明近邻超边产生的正影响大于负影响，则增量式超网络分类器对该标签的预测值为1，反之为0。由于LMLP和clus_HMC方法针对不同的阈值产生不同的实验结果，本文在对比试验中，采用步长以0.02为增量，从0到1的范围内，选取该方法最优F1值的实验结果进行对比，不同层次分类方法参数阈值的选择如表2所示。本文采用的增量式超网络方法的具体实验参数如表3。从实验结果可以看出，比较bp_LMLP, rp_LMLP以及clus_HMC, clus_HMC_ens, HMC_MLHN方法，增量式超网络方法具有较好的分类性能，并且对不平衡数据标签的分类性能也是比较好的。

表2 不同层次多标签算法阈值选择

表3 多标签增量式超网络方法实验参数

3.3.1 层次多标签分类精度以及时间复杂度分析

本文分别采用上述3种评价指标进行试验。实验结果如表4～表6所示，从不同层次多标签分类算法在不同指标进行对比结果可以看出，相对于其他5种多标签分类方法，HMC_IMLHN和bp_LMLP,rp_LMLP,clus_HMC,clus_HMC_ens,HMC_MLHN,HMC_IMLHN具有很好的层次分类效果，整体效果较好优于其他算法，尤其是F1值指标具有很好的实验结果。其中，需要说明的是对于WIPO数据来说，由于其标签结构与其他数据集的标签结构不同，为一棵单一的树，因此，根节点默认预测全部为1且正确。

表4 不同层次多标签算法在H_loss指标下的实验对比结果

表5 不同层次多标签算法在HMC_loss指标下的实验对比结果

表6 不同层次多标签算法在F1指标下的实验对比结果

表7 不同层次多标签算法运行时间

设定训练集的有N个样本，测试集样本有T个，平均有m个标签，数据样本平均有L层，c为超边的维度，层次多标签增量式超网络方法训练阶段的时间复杂度O(N2+L(cKN+mN))，测试样本的时间复杂度为O(TN+L(cKN+mN))。表7展示的是不同的层次分类方法在不同的数据集上的运行时间。

3.3.2 不平衡指标分析

该部分主要对层次标签数据集的不平衡性进行分析，探究各种方法对缓解不平衡性标签的性能影响。通过统计HMC_IMLHN和bp_LMLP,rp_LMLP,clus_HMC,clus_HMC_ens,HMC_MLHN层次多标签分类方法在不同数据集中的平均层次F1值，区别于上述3.3.1部分中对层次F1值的统计，该部分主要是统计实验结果中，每层标签的平均层次F1值。具体结果如图6～图11所示，横轴表示某层次标签，纵轴表示每层标签的平均层次F1值。

针对多标签层次数据中标签具有的不平衡性问题，HMC_IMLHN首先在训练阶段的超边初始化过程中，对超边的结构进行了调整，在分类中能够有效降低下一层标签的不平衡程度；其次，预测过程中针对标签存在不平衡因素的问题，加入了缓解不平衡的措施，使得子标签的正负样本数据概率差异减少，在预测阶段，很大程度地减少了不平衡标签造成的分类精度差；最后，HMC_IMLHN方法利用标签之间的关联减少子标签存在不平衡性问题对分类性能的影响。根据结果可以看出HMC_IMLHN在缓解不平衡性标签的分类性能上具较好的分类效果。

图6 ImageCLEF07A每层标签的平均F1值Fig.6 Average F1 value of ImageCLEF07A per layer

图7 ImageCLEF07D每层标签的平均F1值Fig.7 Average F1 value of ImageCLEF07D per layer

图8 Diatoms每层标签的平均F1值Fig.8 Average F1 value of Diatoms per layer

图9 Enron每层标签的平均F1值Fig.9 Average F1 value of Enron per layer

3.3.3 部分标签的分类精确度分析

该部分的工作主要是分别对实验结果数据集中的部分标签进行概率统计以及不同层次多标签分类方法对该标签的正确度统计，选出部分标签进行图表展示，图12～图17的横轴表示某个标签，左纵轴表示该标签的分类精确度，右纵轴表示该标签的出现概率。

HMC_IMLHN方法对传统的多标签超网络方法进行改进，满足层次标签约束的同时，考虑了层次标签之间的不平衡性，并且在初始化标签向量的时候，根据其父节点的标签与近邻样本的概率权重和进行设置与调整，使得在分类中能够巧妙地降低下一层标签的不平衡程度，提高方法的分类性能。从图12～图17中可以看出，相比较其他层次多标签分类方法，HMC_IMLHN在不同数据集上都具有较好的稳定性以及分类精确度。