收稿日期:2017-11-04摇摇摇摇摇摇修回日期:2018-03-13摇摇摇摇摇摇网络出版时间:2018-05-16基金项目:2015年教育部-中国移动科研基金项目(5-10);江苏省自然科学基金面上项目(BK20171447);江苏省高校自然科学研究面上项目(17JKB520024)

作者简介:张春焰(1992-),男,硕士,研究方向为数据挖掘;李摇涛,通讯作者,博士,美国佛罗里达国际大学正教授,研究方向为数据挖掘、机器学习和信息检索及生物信息学等。网络出版地址:http://kns.cnki.net/kcms/detail/61.1450.TP.20180515.1645.016.html

基于路径选择的层次多标签分类张春焰,李摇涛,刘摇峥(南京邮电大学计算机学院,江苏南京210046)

摘摇要:多标签分类为每一个实例分配多个标签,当这些标签存在一种预定义的层次化结构时,该机器学习任务称为层次多标签分类(HMC)。传统的分类问题(二分类和多标签分类)往往会忽略各标签之间的结构关系,而层次多标签分类充分考虑标签集之间的层次结构关系,并以此来提高分类的效果。层次多标签分类是输出结构化预测结果的分类任务,其中类标签被组织成某种预定义(树形或者有向无环图)的结构,并且一个实例可以属于多个类。在HMC中有基于全局标签集的分类方法和基于单个标签的局部分类方法。全局方法将整个问题作为一个整体来处理,但往往会随着数据集的增长而出现性能瓶颈,而局部方法将问题分解为基于单个标签的二分类方法,但未充分考虑层次结构信息,并且无法处理预测节点终止于层次标签树内节点的分类问题。在分类阶段,修剪掉概率较低的分支,达到预测标签不一定到达叶子节点的目的。基于路径选择的层次多标签分类充分考虑修剪后的层次标签树从根节点出发的所有可能路径,结合各节点的预测概率值和节点所在的层次来选出得分最高的标签路径。该方法和现有的层次多标签分类方法在三种不同的数据集上进行实验对比,结果表明该方法在处理层次较深且叶子节点稠密的层次结构时获得了较好的结果。关键词:层次多标签分类;多标签学习;路径选择;层次分类;文本分类;层次标签树;剪枝中图分类号:TP181摇摇摇摇摇摇摇文献标识码:A摇摇摇摇摇摇文章编号:1673-629X(2018)10-0037-07doi:10.3969/j.issn.1673-629X.2018.10.008

HierarchyMulti-labelClassificationBasedonPathSelection

ZHANGChun-yan,LITao,LIUZheng(SchoolofComputerScience,NanjingUniversityofPostsandTelecommunications,Nanjing210046,China)

Abstract:Multi-labelclassificationassignsmorethanonelabelforeachinstancewhenthelabelsareorderedinapredefinedstructure.Thetaskiscalledhierarchicalmulti-labelclassification(HMC).Traditionalclassificationproblems(binaryclassificationandmulti-la鄄belclassification)tendtoignorethestructuralrelationshipbetweenthelabels,andhierarchicalmulti-labelclassificationtakesfullaccountofthehierarchicalrelationshipbetweenthelabelsets,thusimprovingtheclassificationeffect.HMCisataskofstructuredoutputpredic鄄tionwheretheclassesareorganizedintoahierarchyandaninstancemaybelongtomultipleclasses.Thehierarchystructurethatorgani鄄zesthesetofclassescanassumetheformofatreeorofadirectedacyclicgraph(DAG).InHMCthereareglobalandlocalapproaches.Globalapproachestreattheproblemaswholebuttendtoexplodewithlargedatasets.Localapproachesdividetheproblemintolocalsub鄄problems,butusuallydonotexploittheinformationofthehierarchy.Thehierarchicalmulti-labelclassificationbasedonpathselectionstudiestheproblemthattheclassificationlabeldoesnotreachtheleafnodeofthelabeltree.Intheclassificationphase,thebrancheswithlowprobabilitytooccurarepruned,performingnon-mandatoryleafnodeprediction.Thismethodevaluateseachpossiblepathfromtherootofthehierarchy,takingintoaccountthepredictionvalueandthelevelofthenodes,selectingoneormorelabelpathswhosescoreisaboveathreshold.Ithasbeentestedinthreedatasetswithtreehierarchystructuredhierarchiesagainstanumberofstate-of-the-artmethods.Theexperimentshowsthatthismethodcanobtainsuperiorresultswhendealingwithdeepandpopulatedhierarchies.Keywords:hierarchicalmulti-labelclassification;multi-labellearning;pathselection;hierarchicalclassification;textclassification;hier鄄archicallabeltree;pruning

第28卷摇第10期2018年10月摇摇摇摇摇摇摇摇摇摇计算机技术与发展COMPUTERTECHNOLOGYANDDEVELOPMENT摇摇摇摇摇摇摇摇摇摇Vol.28摇No.10Oct.摇20180摇引摇言层次分类(hierarchicalclassification,HC)问题是分类问题的一个分支,在层次分类问题中类别是不相交的,而是以分层结果组织的。在该情况下,一个样本会与给定的类别标签及该标签的父标签相关联,而组织类的层次结构可以采用树或者有向无环图(directedacyclicgraph,DAG)的形式。存在复杂HC问题的子集,其中每个样本可以与类层次结构中的多个路径相关联,即层次多标签分类(HMC)[1-3]。典型的HMC问题是文本分类[4-6]和生物信息学任务,如蛋白质功能检测[7-8]、图像分类[9-12]等。HMC算法一般通过优化局部或者全局的损失函数来选择层次标签树上一条或者多条路径以标示实例[13]。执行局部学习的算法尝试挖掘类层次结构的区域特征,然后将预测结果进行组合得到最终分类结果。而基于全局的方法往往由单个分类器组成,并且能够一次性找出实例相关联的类标签。传统的分类任务主要解决的是一个样本e只会对应于单个标签y沂L的问题,其中L是标签的集合,标签的数量大于等于二,即通常所说的多类分类。然而,有些分类问题会更加复杂,因为一个样本可以对应多个标签。一个多标签数据集D由N个样本组成,每一个样本会对应一个标签集合Y,其中Y沂L。当这些标签之间存在某种预定义的结构(树形或者有向无环图)时,该任务称为层次多标签分类。树形结构与有向无环图的主要区别在于图形结构中一个节点可以有多于一个的父节点,为了简化问题,文中只考虑树形层次结构。基于局部分类方法,在层次结构中的每一个标签节点训练一个分类器的基础上提出新的HMC方法,通过分解问题来达到层次多标签分类。对比之前的层次多标签分类方法,该方法的主要改进有以下几点:·为层次树的节点加权,使得每个节点标签分类错误的权重随着层次标签树层次的下降而衰减。·通过组合各节点的概率值和节点在路径中的位置,对所有可能的预测路径进行打分,从而选出最佳路径,即预测标签集。·通过在寻找最优的预测路径之前对层次树进行裁剪,解决预测路径不在层次树叶子节点终止的层次多标签分类任务,即最具体的类别并未到达叶子节点。对层次标签树进行裁剪可以抛弃那些在真实标签集中不大可能出现的分支,减少了计算量和潜在的错误。1摇相关工作在HMC任务中,属于某个类的示例自动属于这个类的所有超类(层次约束)。这里有两种预测结果[1]:强制性叶节点预测,返回的是从根节点到叶子节点的完整路径;非强制性叶节点预测,预测出来的路径可能未到达叶子节点。HMC根据其用于解决分类问题的探测策略进行

分类,其中比较常见的方法为:直接法、全局法、自顶向下。直接法的分类策略借鉴于传统的多标签分类,只能预测层次树中的叶子节点,预测出一个叶子节点则到达该叶子节点路径上的所有节点都被标记为正,该方法有一个显著的缺点是完全忽略了标签之间的层次关系。然而,这种简单的分类策略必须解决的是,需要训练一个分类器来区分一个庞大的目标标签集(所有叶子节点),并且没有利用标签集提供的层次关系。当然,这种方法只能预测层次树中的叶子节点,所以对于非强制性叶节点的数据集也就无能为力。全局方法对标签集中的所有类学习一个单一的模型来预测层次树中的所有类,例如,对于一个深度为3的二叉树,总共有14个非叶子节点和叶子节点,所以基于全局的分类方法需要训练一个针对14个标签的分类器。该分类算法生成的模型在一次运行期间考虑了类层次结构上所有的类标签。基于全局方法的主要限制是随着数据集的增大,模型会过于复杂并且训练模型会花费大量时间。该方面已有不少研究成果,Vens[13],Blockeel