基于关联规则和拓扑序列的分类器链方法.pdf

基于关联规则和拓扑序列的分类器链方法*丁家满1,2,周蜀杰1,2,李润鑫1,2,付晓东1,2,贾连印1,21(昆明理工大学信息工程与自动化学院,云南昆明650500)2(云南省人工智能重点实验室(昆明理工大学),云南昆明650500)通信作者:贾连印,E-mail:JL摘要:在分类器链方法中,如何确定标签学习次序至关重要,为此,提出一种基于关联规则和拓扑序列的分类器链方法(TSECC).首先结合频繁模式设计了一种基于强关联规则的标签依赖度量策略;接下来通过标签间依赖关系构建有向无环图,对图中所有顶点进行拓扑排序;最后将得到的拓扑序列作为分类器链方法中标签的学习次序,对每个标签的分类器依次迭代更新.特别地,为减少无标签依赖或标签依赖度较低的“孤独”标签对其余标签预测性能的影响,将“孤独”标签排在拓扑序列之外,利用二元关联模型训练.在多种公共多标签数据集上的实验结果表明,TSECC 能够有效提升分类性能.关键词:多标签学习;分类器链;标签依赖;强关联规则;拓扑序列;二元关联中图法分类号:TP18中文引用格式:丁家满,周蜀杰,李润鑫,付晓东,贾连印.基于关联规则和拓扑序列的分类器链方法.软件学报,2023,34(9):42104224.http:/ Chains Method Based on Association Rules and Topological SequencesDINGJia-Man1,2,ZHOUShu-Jie1,2,LIRun-Xin1,2,FUXiao-Dong1,2,JIALian-Yin1,21(FacultyofInformationEngineeringandAutomation,KunmingUniversityofScienceandTechnology,Kunming650500,China)2(ArtificialIntelligenceKeyLaboratoryofYunnanProvince(KunmingUniversityofScienceandTechnology),Kunming650500,China)Abstract:The order of label learning is crucial to a classifier chains method.Therefore,this study proposes a classifier chains methodbased on the association rules and topological sequence(TSECC).Specifically,a measurement strategy for label dependencies based onstrong association rules is designed by leveraging frequent patterns.Then,a directed acyclic graph is constructed according to thedependencyrelationshipsamongthelabelstotopologicallysortalltheverticesinthegraph.Finally,thetopologicalsequenceobtainedisusedastheorderoflabellearningtoiterativelyupdateeachlabelsclassifiersuccessively.Inparticular,toreducetheimpactof“lonely”labels with no or low label dependencies on the prediction performance on the other labels,TSECC excludes“lonely”labels out of thetopological sequence and uses a binary relevance model to train them separately.Experimental results on a variety of public multi-labeldatasetsshowthatTSECCcaneffectivelyimproveclassificationperformance.Key words:multi-labellearning;classifierchains;labeldependent;strongassociationrules;topologicalsequence;binaryrelevance传统监督学习通常假设每个实例与一个标签相关联,而在现实世界的应用中,一个实例通常有多个标签.例如,一篇关于奥运会的文档可能同时与“体育”“商业”和“经济”相关联.传统的基于每个实例一个标签的监督学习已经无法解决这一问题,而多标签学习处理与一组标签相关联的实例,现已成为机器学习和数据挖掘领域中的研究热点,并广泛应用于文本分类、图像标注和功能基因预测等领域中1,2.*基金项目:国家自然科学基金(61562054)收稿时间:2021-09-23;修改时间:2021-11-29,2022-01-08,2022-02-16;采用时间:2022-02-24;jos 在线出版时间:2022-12-22CNKI 网络首发时间:2022-12-26软件学报ISSN1000-9825,CODENRUXUEWE-mail:Journal of Software,2023,34(9):42104224doi:10.13328/ki.jos.006659http:/中国科学院软件研究所版权所有.Tel:[phone]处理多标签学习问题的常见策略是通过构造 n 个独立的二元分类器,将其转换成单标签分类问题.如二元关联法(binaryrelevance,BR),但这种方式忽略了标签间的隐含关系3.合理利用标签间的隐含关系可以提高多标签分类的性能,这也是近年来多标签学习研究的热点之一.为此,Read 等人4,5提出分类器链方法(classifierchains),将标签按照某种次序排成链,针对链上的标签依次训练分类器,并将目标标签前的所有标签学习结果添加到目标标签分类器的训练特征中.分类器链方法简单易实现,且利用标签间的隐含关系取得了相对二元关联法更好的预测性能.然而,分类器链方法在学习过程中需预先给定标签的学习次序,而良好的标签学习次序往往难以确定.此外,不当的标签学习次序会影响方法的预测性能,甚至可能传递错误的信息1.Read 等人4,5利用集成思想,提出了改进的集成分类器链方法(ensembleclassifierchains),它随机产生多个的不同标签学习次序,对多个次序的学习结果进行集成,削弱了由单个标签序列产生的随机性,在一定程度上缓解了分类器链方法性能受限的问题.然而,随着标签数量上升,标签次序的排列组合数量呈阶乘级增长,这极大地增加了集成分类器链方法预测的随机性和不确定性,集成分类器链方法仍面临着次序选择的困难6.针对上述问题,本文提出基于关联规则和拓扑序列的分类器链方法,方法首先结合频繁模式思想设计了一种基于强关联规则的标签依赖度量策略,接下来通过标签间依赖关系构建有向无环图,对其进行拓扑排序得到蕴含标签间依赖关系的拓扑序列,最后将得到的拓扑序列作为分类器链方法中标签的学习次序,对每个标签的分类器依次迭代更新.在多种公共多标签数据集上的实验结果表明,TSECC 能够有效提升分类性能.本文第 1 节介绍了多标签学习的相关工作.第 2 节给出了本文方法的原理和实现流程.第 3 节汇报实验结果及对比分析.第 4 节总结全文.1 相关工作分类器链(classifierchains)算法4,5是一种由二元关联(binaryrelevance)算法3发展而来的可解释性强、易实现的多标签分类算法.二元关联算法将多标签问题转换为多个独立的二分类问题,为每个标签分别训练独立的二元分类器,但这种算法忽略了标签关联信息,性能受限.分类器链算法在其基础上,把已训练的标签加入到当前待训练标签分类器的特征中,将多个相互独立的二元分类器串联起来,使当前标签学习到前若干个标签信息,提升了分类器的性能,是一种利用标签关联信息的“高阶策略”的多标签学习方法1.在多标签学习中,合理地利用标签间隐含关系可以带来更加理想的预测性能,这也是近年来多标签学习的研究重点.例如,Wang 等人结合深度信念网络和反向传播神经网络传递标签间信息7;Dai 等人提出了基于模糊互信息的标签间对称不确定性关联8;Lin 等人构建了一个投影矩阵模型来确定多个标签间的关系9;Xie 等人通过标签间的条件熵构建标签间的关联关系10;Sun 等人提出了多重树增强的分类器链模型,利用估计的条件互信息构建标签的多重树结构,通过灵活的多重树结构来建模标签间的关联信息11.从利用标签关联信息的角度,多标签学习方法可大致分成以下 3 类1.一阶方法,即考虑标签间相互独立,忽略标签的共存性.例如,Zhang 等人提出的 ML-KNN 算法12,通过计算样本 K 近邻,利用最大后验概率原则预测样本的标签集合,将 KNN 算法适应于多标签分类问题.这种方式概念简单,效率高,但忽略了标签间的隐含关系,学习性能受限.二阶方法,即学习标签间的成对关联关系,例如,Elisseeff 等人提出的 Rank-SVM 算法13,Ghamrawi 等人提出的 CML 算法等14,Zhang 等人提出的一种三路选择集成模型15.二阶方法简单有效,且获得了良好的泛化性能,但实际应用中标签间的隐含关系往往超出了二阶.高阶方法,即学习多个标签间的隐含关系.高阶方法更准确地刻画了标签间的隐含关系,具有相对更强的关联建模能力.例如,Huang 等人提出的一种新的成本敏感型 LE 算法16.此外,分类器链方法是一种属于高阶方法的简单有效的算法.对比二元关联算法,分类器链算法将独立的二元分类器由并行结构改为了串联结构,利用了标签关联信息,提升了模型性能,但其链式的串行结构使得模型对标签学习次序敏感,不同的标签学习次序决定了不同的标签关联信息的学习程度,因此分类器链算法性能不稳定,具有很强的随机性,大量实验结果表明,学习次序的选择会严重影响分类器链算法的学习性能6,17,针对此问题,Read 等人4,5提出了集成分类器链算法,该方法构造多条标签学丁家满等:基于关联规则和拓扑序列的分类器链方法4211习次序不同的分类器链,每条分类器链的标签学习次序随机产生,最终预测结果由多条分类器链集成得到.集成分类器链算法通过集成多条不同标签学习次序的分类器链以削弱单条链带来的随机性.但标签次序的排列组合数量随标签数量呈阶乘级增长,在面对高纬度数据集时仍具有较强的随机性.为此,王少博等人18提出分类器圈算法,将分类器链结构首尾链接,使用圈结构的模型避免学习次序选择的问题;李娜等人19提出基于多标签重要性排序的分类器链算法,将标签间相互作用程度的大小作为衡量标签重要程度的依据,用重要度排序结果作为分类器链模型的学习次序;Wang 等人20通过特征选择消除不相关特征的干扰,并在圈结构训练的基础上,将高耦合的标签加入到当前标签的训练特征中,提升标签关联信息的表达;胡天磊等人21提出双向分类器链的解决方案,通过引入逆向链,使标签再次提取不同的标签关联信息;Weng 等人22提出基于标签特征选择的分类器链方法,通过对每个标签进行特征选择,降低标签关联信息传递中冗余特征带来的干扰.此外,Liu 等人23考虑到不平衡问题,提出了基于随机欠采样的分类器链方法.Sun 等人24从条件似然最大化的角度对分类器链性能进行优化.针对分类器链算法对标签学习次序敏感的问题,分类器链相关改进算法多是通过多次迭代训练或改变模型结构克服标签学习次序问题的,仍具有一定的随机性.为了克服以上困难,本文提出一种基于关联规则和拓扑序列的分类器链方法.2 基于关联规则和拓扑序列的分类器链模型 2.1 算法思想方法首先挖掘多标签数据集中的标签间依赖信息,由依赖程度和依赖关系构建标签间依赖有向无环图,接着对其进行拓扑排序,求得标签次序,最后将标签次序用于改进的分类器链算法.如图 1 为本文方法的流程图.数据4 1 3 2 5训练预测421351.计算标签间依赖2.获取拓扑序列3.训练和预测图1本文基于关联规则和拓扑序列的分类器链方法的流程图方法分 3 个步骤,首先是标签间依赖关系及依赖程度的挖掘.本文提出一种计算标签间依赖的新方法,迁移频繁模式强关联规则的思想,将数据集中的一组组多标签向量类比一个个事务,探究标签项集间的关联规则,将其作为标签间依赖关系及依赖程度.接着是标签间依赖有向无环图的构建和其拓扑序列的求解.将标签间依赖关系看作标签间约束条件,以此构建有向无环图表示标签间依赖关系,从而将标签关联信息隐含在图的拓扑序列中.最后将求得的拓扑序列作为标签学习次序,按学习次序训练分类器链模型,并利用二元关联模型训练无标签依赖或标签依赖度较低的标签,提高模型的泛化能力.2.2 问题定义2.2.1基于关联规则的标签间依赖标签关联信息的挖掘是多标签分类问题的研究重点,现已有多种挖掘标签关联信息的方法应用到多标签学习中3,而余弦相似度量等25标签关系的度量方法多为计算标签间相关性,无法确定标签的相互依赖关系,为构造标签间依赖关系,需要一种不对称的标签间关联度量方式.频繁模式挖掘搜索给定数据集中反复出现的联系,一个典型的例子是购物篮分析.该过程通过发现顾客放入“购物篮”中的商品之间的关联,分析顾客的购物习惯.如果我们想象全域是商店中商品的集合,则每种商品有一个布尔变量,表示该商品是否出现,每个购物篮可用一个布尔向量表示.可以分析布尔向量,得到反映商品频繁关联或同时出现时的购买模式.这些模式可以用关联规则的形式表示26.同样,我们也可以将多标签分类问题中全体标签看作全域,每个样本的标签集合可用一个布尔向量表示,进而4212软件学报2023 年第 34 卷第 9 期通过分析布尔向量,得到反映标签频繁关联或同时出现时的模式.如图 2 为频繁模式思想从购物篮案例到多标签的迁移示意图.牛奶 面包麦片顾客 1顾客 2顾客 3顾客 4牛奶 面包牛奶面包糖鸡蛋黄油糖鸡蛋牛奶 面包糖 鸡蛋样本 1样本 3样本 4标签间频繁模式样本 2商品频繁模式挖掘商品间频繁模式挖掘标签 A标签 B多标签频繁模式挖掘标签 A 标签 B标签 C标签 A 标签 B标签 D 标签 E标签 A 标签 B标签 F标签 D 标签 E标签 D标签 E图2频繁模式迁移到标签间关联示意图=l1,l2,.,lqDYYY AYAA YA BA B A,B,AB,A BDYsupportsupportDYABABP(AB)A BDYconfidenceconfidenceDYABP(B|A)设是标签的集合,是数据集标签向量的集合,其中每个标签向量是一个非空标签项集(项集,即若干个项的集合),使得.设是一个标签项集,标签向量包含,当且仅当.关联规则是形如的蕴涵式,其中,并且.规则在数据集中成立,具有支持度,其中是数据集中标签向量包含(标签项集和的并集)的百分比,即概率.规则在数据集中具有置信度,其中是数据集中包含的标签向量同时也包含的标签向量的百分比,即条件概率.support(A B)=P(AB)(1)confidence(A B)=P(B|A)(2)min_supmin_confmin_supmin_confDY最小支持度阈值()和最小置信度阈值()是衡量关联规则有效性的最低重要性和最低可靠性,其中同时满足和的规则为强关联规则26.此外我们把标签的集合称为标签项集.包含 k 个标签的标签称为标签 k 项集.标签项集的出现频度是数据集中包含标签项集的标签向量数,简称为标签项集的频度、支持度计数或计数.由公式(2),有:confidence(A B)=P(B|A)=support(AB)support(A)=support_count(AB)support_count(A)(3)support_count(AB)ABsupport_count(A)其中,是包含标签项集的标签向量数,而是包含标签项集 A 的标签向量数.liftliftABP(AB)=P(A)P(B)ABABAB然而由支持度和置信度推导出的关联规则在特殊情况时具有一定的欺骗性,有时会产生无趣的关联26,因此,我们引入关联规则中的提升度()作为对强关联规则的鉴别.提升度()是一种简单的相关性度量,如果和出现概率独立,即,则独立于出现;否则,和是依赖和相关的26.和出现之间的提升度可以通过公式(4)得到:lift(A,B)=P(AB)P(A)P(B)=P(B|A)P(B)=confidence(A B)support(B)(4)liftliljliljljlililjliljljli通过标签一项集、标签二项集出现频度计算标签间提升度,提升度大于 1,则标签和标签是正相关的,意味着每一个标签()的出现都可能蕴含着标签()的出现;提升度小于 1,则标签和标签是负相关的,意味着每一个标签()的出现可能导致标签()不出现.2.2.2有向无环图和拓扑序列有向无环图(directedacyclicgraph,DAG)通常是描述一项工程或系统的进行过程的有效工具.除最简单的情况外,几乎所有的工程都可划分为若干个活动的子工程,而这些子工程之间,通常受着一定条件的约束,如其中某些子工程的开始必须在另一些子工程完成之后,因此 DAG 图常被用来表示事件之间的驱动依赖关系,管理任务之间的调度.与子工程之间的约束依赖关系相似,多标签问题中标签间依赖关系也可看作标签间约束条件.例如标签 A 依赖于标签 B、标签 C,即意味着标签 A 预测的开始需要在标签 B 和标签 C 的预测完成后.利用标签间依赖丁家满等:基于关联规则和拓扑序列的分类器链方法4213关系即可绘制标签间依赖的 DAG 图.对一个 DAG 图进行拓扑排序,是将图中所有节点排成一个线性序列,使得图中任意一对节点 u 和 v,若存在u 指向 v 的有向边,则 u 在序列中出现在 v 之前.通常,这样的线性序列称为满足拓扑次序的序列,简称拓扑序列.拓扑序列常用来确定一个依赖关系集中事件发生的顺序,通过对 DAG 图进行拓扑排序,得到拓扑序列,标签间的依赖关系即可隐含在序列中.min_conf然而在由最小置信度阈值()更新标签间依赖关系后,可能存在部分“孤独”标签,这部分标签不依赖任何标签,同时其他标签也都不依赖于这部分“孤独”标签(如图 3 所示,标签 4、标签 5 即为“孤独”标签).若以此排序,“孤独”标签可在拓扑序列中任意位置存在,将会导致拓扑序列数量大大增加.同时为了保证“孤独”标签与其他标签的预测不相互影响,故将这部分“孤独”标签统一排列在序列前部.541203图3含有“孤独”标签的标签间依赖关系图 2.3 模型建立2.3.1计算标签间依赖DY=Yi|1 i nL=l1,l2,.,lqs1s2首先统计数据集标签向量的集合中所有标签()、标签间两两组合出现的频度,得到标签一项集频度和标签二项集频度.定义为:sli1=support_count(li)=nj=11,Yij=10,other(5)sli,lj2=support_count(lilj)=nk=11,Yik=1 and Yjk=10,other(6)接着由公式(3)计算得到标签一项集间关联的置信度,由公式(4)计算得到标签一项集间关联的提升度,定义为:confidence(li lj)=support_count(lilj)support_count(li)=sli,lj2sli1(7)lift(li,lj)=confidence(li lj)support(lj)=support_count(lilj)/support_count(li)support(lj)=sli,lj2nsli1slj1(8)liljmin_conf其中,n 为样本数,提升度大于 1 的标志着标签和标签是正相关的,且二者的正相关度与提升度 lift 值成正比,此时认为二者的依赖关系是显著有效的.设置置信度阈值,小于置信度阈值的关联规则为弱关联规则,认为两标签一项集间关联确信度弱,将其置信度值置为 0.W Rqq最后将标签一项集间关联规则及其置信度作为标签间依赖情况及依赖度,得到不对称的标签间关联度量矩阵,即为标签依赖矩阵.2.3.2获取拓扑序列min_conf基于标签依赖矩阵即可构造标签间依赖有向无环图,为确保构造的有向图无环,将互有依赖的标签(相互依赖度值均大于 0)的两个依赖度值进行比较,依赖度弱的值置为 0,以此消除标签间相互依赖产生的环.但 3 个或 3 个以上的标签间相互依赖仍可能导致的环出现.因此需进行环检测,并调整值消除图中环结构.有向图环检测流程如下.1)遍历当前所有节点,计算每个节点入度(有向图中某点作为图中边的终点的次数之和).4214软件学报2023 年第 34 卷第 9 期2)统计入度为 0 的节点数量,若没有,则图有环结构,检测结束.3)删除入度为 0 的节点及这些节点指向其他节点的关联,若删除后剩余节点数为 0,则图无环结构,检测结束;否则跳转步骤 1).max_tplenmax_tplenmax_tplenT最后,根据标签间依赖有向无环图即可获取标签依赖的拓扑序列.因 DAG 图特点,得到的拓扑序列往往不止一条,故本文设置最大拓扑序列数阈值,若拓扑序列数量大于最大拓扑序列数阈值,则随机保留其中条序列.最终保留 k 条拓扑序列,得到拓扑序列集合,定义如下:T=t1,t2,.,tk,k max_tplentiL=l1,l2,.,lq,其中,是标签集的序列组合.2.3.3TSECC 模型的训练和预测TSECC 方法根据标签间依赖情况,将拓扑序列分为前后两段,前一段为“孤独”标签项,后一段为“非孤独”标签项.前一段使用独立的若干个二元分类器对“孤独”标签项进行训练和预测,后一段使用分类器链模型进行串联,充分利用标签间依赖关系,同时避免了无标签依赖或标签依赖程度较低的“孤独”标签与“非孤独”标签间的相互影响.图 4 给出了本文方法和传统分类器链方法的对比示意图.第 4 节给出的实验结果说明,这样的二元关联和分类器链结合的方法较完全的分类器链方法性能更好.1q2.lm+1qlm+21m.(a)分类器链方法(b)二元关联结合分类器链方法图4本文方法与分类器链方法结构示意图ltpi(1),ltpi(2),.,ltpi(q)ltpi(j)ltpi(1),.,ltpi(m)ltpi(m+1),ltpi(m+2),.,ltpi(q)ltpi(1),.,ltpi(m)BCXyltpi(j)ltpi(j)具体而言,本文方法将得到的拓扑序列(为第 i 条序列,第 j 个位置的标签)按照标签依赖程度划分为前后两部分、,前面部分为无标签依赖或标签依赖程度较低的“孤独”标签,后面部分为非“孤独”标签.方法首先对“孤独”标签构建独立的二元分类器,每一条序列由“孤独”标签得到 m 个独立的二元分类器.记为二元分类算法,为训练好的二元分类器,为训练数据集的特征空间,为标签对应的训练数据集的标签向量,即:ji BC(X,yltpi(j),j=1,2,.,m,i=1,2,.,k(9)ltpi(m+1),ltpi(m+2),.,ltpi(q)接着对非“孤独”标签构建二元分类器,并将每个分类器的学习结果加入下一个分类器学习的特征空间中,形成链式结构,每一条序列得到 qm 个依次串联的二元分类器.ji BC(Xji,yltpi(j),j=m+1,m+2,.,q,i=1,2,.,k(10)Xji其中,为非“孤独”标签构造分类器的特征空间,定义为:Xji=Xj1iyltpi(j1)(11)2.4 算法实现2.4.1计算标签间依赖算法标签间依赖关系是形成拓扑序列的依据.算法 1 给出了利用关联规则计算标签间依赖关系及依赖度的过程.W算法 1.获取标签依赖矩阵.DY=Yi|1 i nmin_conf输入:训练数据集标签向量集合,置信度阈值;W Rqq输出:标签依赖矩阵.s1 Oqs2 OqqO1)初始化标签一项集频度和标签二项集频度空间,代表全 0 向量W Rqq2)初始化标签依赖矩阵for i 1 to q3)for j 1 to n4)丁家满等:基于关联规则和拓扑序列的分类器链方法4215if Yij=1 then si1 si1+15)/*计算标签一项集频度*/for k 1 to q6)if Yij=1 and Ykj=1 then si,k1 si,k1+17)/*计算标签二项集频度*/endfor8)endfor9)for i 1 to q10)for j 1 to q11)if si,j2/si1 min_conf and si,j2n/si1sj1 1 then wij si,j2/si112)endfor13)endfor14)2.4.2获取拓扑全序列算法WW对标签依赖矩阵进行拓扑排序,其拓扑序列蕴含了标签间的依赖情况.算法 2 给出了由标签依赖矩阵生成拓扑排序全序列的过程.算法 2.获取拓扑排序全序列算法.W Rqqmax_tplen输入:标签依赖矩阵,最大拓扑序列数阈值;T=t1,t2,.,tk输出:拓扑排序全序列.T1)初始化空序列数组存储所有拓扑序列preList2)初始化空数组存储当前序列topologicalSort(W,preList,T)3)if length(preList)=q then T T preList4)if length(T)=max_tplen then end5)for i 1 to q6)ifsum(wi)=0 and i not in preList then preList preListi7)for j 1 to q8)wj,i 09)endfor10)topologicalSort(W,preList,T)11)endfor12)2.4.3改进的分类器链模型的训练和预测算法考虑到“孤独”标签易对标签关联信息传递造成影响,本文 TSECC 方法将“孤独”标签与“非孤独”标签分离,使用若干个独立的二元分类器训练.算法 3 和算法 4 分别给出了本文方法的训练和预测过程.算法 3.TSECC 训练过程.T=t1,t2,.,tkD=(Xi,Yi)|1 i n输入:拓扑排序全序列,训练数据集,“孤独”标签数量 m;kqji,i=1,2,.,k,j=1,2,.,q输出:个分类器.for i 1 to k1)for j 1 to m2)ji BC(X,yltpi(j)3)4216软件学报2023 年第 34 卷第 9 期endfor4)for j m+1 to q5)Xji Xj1iyltpi(j1)6)ji BC(Xji,yltpi(j)7)endfor8)endfor9)算法 4.TSECC 预测过程.D=(Xi)|1 i nkqjiT=t1,t2,.,tk输入:待预测数据集,个分类器,拓扑排序全序列,“孤独”标签数量 m;y=(Yi)|1 i n输出:预测结果.yZ1)初始化 k 个空间for i 1 to k2)for j 1 to m3)Zji ji(Xi)4)endfor5)for j m+1 to q6)(Xi)j(Xi)j1Zji7)Zji ji(Xi)j,yltpi(j)8)endfor9)endfor10)yZ1i1/2,Z2i1/2,.,Zqi1/211)3 实验与结果 3.1 实验数据本文对 5 个多标签数据集进行了实验,以探究本文算法的性能.这些数据集来自多标签的不同应用领域:Flags,Scene 来自图片分类,Birds,Emotions 来自音乐标注,Yeast 来自生物基因功能预测.这些数据集可以在开源项目 mulan27的主页(http:/mlkd.csd.auth.gr/multilabel.html)下载获得,表 1 给出了数据集的详细统计信息.表1实验数据集数据集领域示例数目特征维度标签数目标签基数标签密度标签多样性Flags图片1941973.3920.48554Scene图片240729461.0740.17915Birds音乐645260191.0140.053133Emotions音乐5937261.8690.31127Yeast生物2417103144.2370.303198CAL500音乐5026817426.0440.150502标签基数(labelcardinality),每个样本相关标签的平均个数:LCard(D)=1mmi=1qj=1yji(12)丁家满等:基于关联规则和拓扑序列的分类器链方法4217标签密度(labeldensity),标签基数相对于标签数目的比例:LDen(D)=1qLCard(D)(13)标签多样性(labeldistinct),样本相关标签集合的总数:LDis(D)=|y|x:(x,y)D|(14)3.2 评价指标及对比模型本文采用多标签学习领域 3 个常用的指标 hammingloss,macro-F1,micro-F11来衡量方法的预测性能.定义如下.1)hammingloss:衡量错分的标签比例,正确标签没有被预测以及错误标签被预测的标签占比.2)macro-F1:每个标签 F1 指标的平均.3)micro-F1:计算所有样本在所有标记上的总体精准度(micro-P)和召回率(micro-R),再计算 F1 分数.用于本文对比的方法为 4 个分类器链相关算法和 2 个其他多标签算法.1)BR(binaryrelevant)方法,该方法不考虑标签间关系,独立训练每个标签的二类分类器3.2)CC(classifierchains)方法,分类器链算法4,5.3)ECC(ensembleclassifierchains)方法,集成分类器链算法4,5.4)CCE(classifiercircle)方法,基于分类器链算法改进的分类器圈算法,使用圈结构避免标签序列的不确定18.5)LSF-CC(labelspecificfeatures-basedclassifierchains)方法,基于标签特征选择的分类器链算法,通过特征选择降低冗余特征对标签传递的干扰22.6)ML-KNN(multi-kabelK-nearestneighbor)方法,该方法拓展 K 近邻方法用于处理多标签学习问题12.7)TSECC(topologicalsequence-ensembleclassifierchains)方法,即本文的基于关联规则和拓扑序列的分类器链算法.3.3 实验结果实验过程中,对于每个数据集,本文随机选取 70%的实例作为训练样本,其余 30%的实例作为测试样本.为降低随机性影响,本文针对每个数据集的每个方法均重复实验 30 次,计算各项指标平均值及标准差作为实验最终结果.本文所有实验在 Python 平台完成,分类器链及其改进算法使用的二类分类器采用 AdaBoost、SVM 等基分类器,基分类器及评价指标(hammingloss、macro-F1、micro-F1)均由 Python 平台下的 scikit-learn 工具包实现.表 2 给出本文算法与 BR、CC、ECC、CCE、LSF-CC 和 ML-KNN 这 6 种对比算法(分类器链及其改进算法基于 AdaBoost 分类器)在 5 个数据集上关于 hammingloss、macro-F1 和 micro-F1 这 3 个评价指标的平均结果和标准差.评价指标中,hammingloss 指标为错误预测比例,该值越小算法性能越好;macro-F1 和 micro-F1 指标为算法“查全率”和“查准率”的综合指标,该值越大算法性能越好.其中,加粗字体表示该算法在该数据集及对应指标下取得最优值(成对 t 检验根据 95%置信度),()表示该评价指标越大(越小)对应方法性能越好.分析表 2 中数据可知,TSECC 在各项数据集中均取得了相对较好的性能,其中在 Emotions、Flags、Birds 数据集上的性能尤为突出,原因是这 3 个数据集皆具有标签关联程度高、标签维度低的特点,TSECC 算法充分利用了隐含在标签序列中的依赖关系.在 Scene 数据集中,BR 算法取得了最好的性能,分类器链及相关改进算法性能大致相同,原因是 Scene 数据集标签关联程度相对较弱.而在 Yeast 数据集中,利用样本相似性进行标签传播的ML-KNN 综合性能最优,同样未考虑标签相关的 BR 算法虽在 hammingloss 指标较好,但在综合考虑查全率和查准率的 macro-F1 和 micro-F1 指标中性能较差,原因是 Yeast 数据集标签维度较高,虽有较强的标签关联程度,但标签次序的排列组合数量大,依赖标签学习序列的分类器链相关算法随机性强,此时不考虑标签学习序列的 ML-KNN和 CCE 则拥有更好的性能,而 LSF-CC 的特征选择策略在标签维度较大时,能有效增强标签关联信息的传递,因此也取得了良好的性能.4218软件学报2023 年第 34 卷第 9 期表2TSECC 与对比方法实验结果(AdaBoost 基分类器)评价指标数据集EmotionsFlagsSceneYeastBirdshamminglossTSECC0.20130.0104(1)0.27960.0064(1)0.09430.0017(3)0.20630.0032(5)0.03950.0003(1)ECC0.21820.0116(5)0.28730.0126(2)0.09890.0037(6)0.21060.0026(6)0.04000.0004(5)CC0.22820.0111(6)0.28830.0124(4)0.09760.0040(5)0.21420.0041(7)0.03960.0005(3)BR0.21410.0099(3)0.29620.0054(6)0.08940.0014(1)0.19790.0019(1)0.04030.0001(6)ML-KNN0.25380.0112(7)0.31740.0132(7)0.09890.0058(7)0.19840.0046(2)0.11450.0003(7)CCE0.21820.0066(4)0.28960.0090(5)0.09360.0016(2)0.19950.0047(3)0.03950.0008(2)LSF-CC0.20570.0121(2)0.28790.0098(3)0.09690.0034(4)0.20230.0041(4)0.03990.0006(4)macro-F1TSECC0.65640.0191(1)0.63410.0073(2)0.73720.0041(2)0.35780.0064(4)0.33290.0088(1)ECC0.63600.0229(3)0.63430.0168(1)0.72840.0099(6)0.35320.0083(5)0.32220.0069(5)CC0.60870.0222(6)0.61600.0163(5)0.73580.0105(5)0.34360.0079(6)0.32660.0089(3)BR0.63540.0219(4)0.60440.0056(6)0.74850.0072(1)0.32900.0071(7)0.31660.0021(6)ML-KNN0.40180.0203(7)0.45720.0153(7)0.69160.0059(7)0.37430.0069(1)0.01110.0114(7)CCE0.63520.0171(5)0.62650.0111(3)0.74220.0047(3)0.35920.0073(3)0.32840.0016(2)LSF-CC0.65310.0216(2)0.62630.010