基于路径选择的层次多标签分类

张春焰，李 涛，刘 峥

(南京邮电大学 计算机学院，江苏 南京 210046)

0 引 言

层次分类(hierarchical classification，HC)问题是分类问题的一个分支，在层次分类问题中类别是不相交的，而是以分层结果组织的。在该情况下，一个样本会与给定的类别标签及该标签的父标签相关联，而组织类的层次结构可以采用树或者有向无环图(directed acyclic graph，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和Bruynooghe[14]等都是基于预测聚类树(PCT)的决策树归纳算法来解决HMC问题，后者根据层次树中的多个节点的距离来导出预测类向量与真实类向量的距离度量。

基于局部分类器的HMC通过挖掘节点在层次结构中的局部信息来考虑类标签的层次关系，该方法可以根据局部上下文信息的组织方式和本地分类器构建方式的不同加以区分。特别地，主要有三种利用局部信息的方式：为每一个节点建立一个分类器(LCN)，为每一个父节点建立一个分类器(LCNP)，为每一个层次建立一个分类器(LCL)。这三种局部层次分类算法在模型训练阶段存在显著差异，但是在预测阶段都是基于相似的自顶向下方法。在预测阶段，这种自顶向下的方法先预测该层次树的根节点的类，然后根据预测出来的类缩小在下一层次所需预测的类的数目，如此循环直至所有特殊的节点都被预测出来。该自顶向下模式的限制是上层的分类错误将在层次结构中向下传播。

LCN方法为层次树中的所有节点都训练一个二分类器(除了根节点)。Bi和Kwok[15-16]提出了HIROM方法，该方法使用独立于局部模型的局部预测方法，同时使用贪心算法在层次标签树中搜索满足层次约束的结果标签集。采用贝叶斯决策理论，通过最小化条件风险来得出最优预测。该方法的局限性在于该优化指标在其他评估措施中不一定有效。LCNP方法为层次标签树中的所有父节点训练一个多标签分类器，以区分各个子节点。在预测阶段，该方法也可以结合上述自顶向下的预测方法。

2 路径选择

在机器学习领域，多标签分类[17-20]受到广泛关注，基于差别排名的方法已在文献[21]提出,同时通过标签之间的依赖性来优化分类结果，但是当标签分层次组织时，却很难发挥作用[2]。图1为一棵层次标签树，针对该任务，提出了基于路径选择的层次多标签分类(based on path seletion，BPS)。该方法通过探索层次树中标签节点和该节点的所有祖先节点的上下文关系来得到最优的分类结果，同时使用计算规则评估从根到叶或中间节点的每个可能路径，该计算规则考虑了预测标签节点所在的层次来计算各个路径的得分，并最终返回满足阈值条件和层次约束的最优节点集。

图1 层次标签树

2.1 训练分类器

令D为具有N个实例的训练集,Ee=(Xe,Ye)，其中Xe为d维特征向量，Ye∈L，L={y1,y2,…,y|l|}，表示|l|可能的标签或类组成的有限集合，即所有样本对应的标签集合。需要注意的是与L相比，Ye是一个较小的集合。Ye可以用一个0/1向量来表示，即Ye∈{0,1}|l|，当且仅当yi∈Ye时，yi=1，否则yi=0。基于路径选择的层次多标签分类算法，除了根节点外，在层次树中的所有其他节点都表示一个标签或者一个类，用yi表示，其中i为层次树按层次遍历的次序。对于每一个非叶子节点yi，训练一个标签多类分类器Ci，后面称之为基分类器。使用该方法对较大的层次结构具有很好的扩展性，只要返回与预测类相关联的概率值或其返回值可以转化为概率值的多类分类器都可以作为基分类器。对于多类分类器Ci所包含的预测类别标签有节点标签yi的所有孩子节点标签(child(yi)),再加上一个“unknown”标签代表那些不属于child(yi)的样本。

把多类分类器Ci的训练样本分成两部分，其中一部分样本由child(yi)=1的实例组成，即这些实例对应的标签集都含有yi的孩子节点标签(child(yi)∈Ye),用Tr+(Ci)表示。在这部分训练样本集中，每一个样本都会打上对应的child(yi)标签。另一部分样本由那些含有yi的兄弟节点标签(sib(yi))的不同样本组成，用Tr-(Ci)表示。如果yi没有兄弟节点，则在层次标签树中向上搜索，找到离yi最近的含有兄弟节点的祖先节点(sib(pa(yi)))，这些兄弟节点由yi父节点的所有子节点的集合除去节点yi的子集构成。Tr-(Ci)对应样本集的标签不会含有yi的孩子标签，把这部分样本标记为“unknown”标签。同时考虑到训练数据的平衡性，需要对这部分数据集进行欠采样，欠采样的数量与每个yi孩子节点对应训练样本的平均值成正比。图2描绘了构造标签节点y5局部分类器C5的训练集实例的过程。数据集Tr+(C5)由满足条件child(y5)={y6,y7}=1的样本组成，这些样本都标记为对应的child(y5)标签。而Tr-(C5)由sib(y5)={y8}的样本组成，该数据集的样本都标记为“unknown”。同时需要对该数据集进行欠采样，从而保证该样本集的数量与训练集中child(yi)的平均样本数成比例。

图2 基分类器

2.2 裁剪层次标签树

某些情况下根据现有的信息不能很有把握地估计一个样本在层次标签树底部的标签，为了让预测的标签节点路径在未到叶子节点前终止，需要对层次标签树进行裁剪。裁剪可以以自下而上或者自上而下的方式进行，这取决于层次结构如何遍历修剪，同时可以在分类阶段之前执行，或者首先修剪分类阶段所选择的路径，同时裁剪可以根据不同的条件进行。文献[2]中进行了几个实验评估裁剪的最优策略，根据该结果选用自顶向下测试标签节点的每条后代分支进行裁剪。为了对一个新的实例进行分类，实例的标签集对应于层次标签树的一条路径或者多条路径。为了选出对应的路径，需要为每条可能的路径计算出相应的概率值。对层次树裁剪需要在计算各路径得分之前进行，裁剪路径的条件是节点最可能的子节点的概率值小于“unkown”标签的概率。该方法的理由是，当一个分类器预测的最可能的类不是该分类器对应标签节点的孩子节点时，就有很大的把握对该路径进行剪枝。

裁剪过程由算法1进行描述，该过程发生在获得针对给定样本xi的情况下层次标签树中每个节点的概率值。从根节点开始，将节点yi最可能的孩子节点的概率值(maxConfidence)与节点未知的概率值(unknown)相继进行比较。如果maxConfidence大于unknown,则该过程在节点yi的各子节点上迭代进行，否则节点yi的子孙节点都将剪去，如果一个节点没有兄弟节点，则在层次标签树中向上搜索其祖先节点的兄弟节点。为了在修剪后的层次标签树中搜索出最优的一条或者多条路径，需要为层次标签树中的路径计算相应的得分。

2.3 计算层次标签树路径得分

该合并规则将路径上每个局部分类器的预测结果合并为一个分值，并且考虑标签节点在层次结构中的层次，以确定该节点在所有分值中的权重。错误的分类发生在层次标签树的顶部的代价往往比发生在层次标签树的底部大，在层次树的顶部有更多的训练样本并且类别之间也有更大的差异，对分类的贡献也就更大。

为了达到该目的，节点yi的权重定义如式1。

(1)

其中，level(yi)表示节点标签yi在层次标签树的层次，即该节点的父节点层次加1；maxlevel表示层次标签树中最长路径的长度。式1定义的节点权重可以随着节点层次的降低而线性衰减，从而保证权重沿层次分布均匀。使得较低层次节点的权重既不会快速下降为0[12]，也不会衰减得太慢[13]。

式2定义了每条路径的得分计算方法，它是沿着路径节点上预测概率的加权和。

(2)

其中，q为路径中的节点数；yi为路径中的第i个节点；p(yi|xe)为实例xe在节点yi被局部分类器预测为真的概率；下标k表示第k条路径，则scorek为第k条路径的得分。

图3描述了计算路径得分的执行过程。首先计算概率和权重，然后利用式2合并成一个分值，选定相应的阈值σ，分值大于σ的路径都作为最终预测返回。阈值σ可以根据测试数据集进行训练得出，返回路径上除了根节点以外的节点标签组成的集合就是预测样本对应的预测标签集。假设训练得到阈值σ为0.5,在图3的层次标签树各路径的得分中有两条路径得分大于0.5，故返回的集合为{y1,y2,y6,y7,y10}。

图3 路径得分计算示例

3 实验结果与分析

实验使用了三种数据集，其中两种来自功能基因组学领域[6,8],一种来自图像分类领域[22-23]，见表1，其中|L|为类别标签的个数，A为特征维度，N为样本个数，D为层次标签树的高度。

表1 实验数据

算法描述如下：

算法1：Prune裁剪层次标签树算法，LC(yi)表示在节点yi运行局部分类器

输入：confidences(一个由在位置j的标签节点yj的概率值p(yi|xe)组成的数组)，yi(层次标签树的根节点)，C(由层次标签树中除叶子节点外每个标签节点的基分类器组成的集合)

输出：裁剪之后的层次标签树

ifyiis not a left and has not been visited before then

if all pa(yi) have been visited then

markyivisited

maxConfidence=0

totalConfidence= 0

for allyj∈child(yi) do

totalConfidence=toalConfidence+confidences[j]

if confidences[j]>maxConfidence then

maxConfidence=confidences[j]

end if

end for

Unknown=1-totalConfidences

if maxConfidence>unknown then

for allyj∈child(yi) do

LC(yi)

end for

else

Prune descendants ofyi

end if

else

continue with another node

end if

end if

3.1 评估指标

在HMC的情况下，评估指标的定义并不像二分类那么直观，因为预测可以是部分正确的，对于该问题已提出相关针对多标签分类[24]和HMC[25]的特殊的评估指标。

Full-Match:式3表示测试集中预测的标签路径完全正确的样本占全部样本的比例，即预测的标签集和真实的标签集完全相同。

(3)

Accuracy[26]：式4表示预测标签集和真实标签集交集的大小与并集的大小的比例。

(4)

(5)

用向量Z替换向量Yi。对于多标签分类，有多种方法对F1-measure进行平均，主要取以下两种方法:

F1-macroD是对样本个数取平均：

(6)

其中，zi≡Yi，N为样本个数。

F1-macroL是对标签个数取平均：

(7)

F1-macroL指标对每一个标签节点的分类效果进行评估，而F1-macroD指标是对每一个样本的分类效果进行评估。

3.2 基分类器

该节设计了一个实验来分析不同基分类器对基于路径选择的层次多标签分类算法性能的影响,并选择最适合该数据集的基分类器对算法进行测试。使用十折交叉验证对三份数据集进行实验，根据3.1节介绍的四种不同的层次度量方法来比较该层次多标签分类算法的性能。使用四种常见的方法作为基分类器：支持向量机(SVM)，核函数使用多项式核函数；C4.5，用于剪枝的置信度设置为0.35，每个叶子的最小实例数设置为3；朴素贝叶斯(NB)；随机森林(RF)，生成十棵树。

实验结果见表2。

表2 不同基分类器的性能度量 %

可以观察到，随机森林在所有评估指标中表现最好，其次是朴素贝叶斯。因为随机森林能够处理比较大的不平衡数据，并且能够有效处理存在噪声的数据，所选择的验证数据都存在这些特征。因此，选用随机森林作为其余实验的基分类器。

3.3 与多类分类和多标签分类的比较

在该实验中，将文中方法与两个未考虑层次结构的替代方法进行对比。

(1)多类分类(multi-class classification，MC):一种仅预测层次结构叶子节点的多类分类器。

(2)链式分类器(classification chains，CC)：为层次标签树中每一个标签节点分别建立一个二分类器，并且各个分类器根据父子关系构成链式结构的多标签分类方法。在预测阶段，它根据链式结构将先前分类器的输出结果作为附加属性，然后在层次标签树中选择最优子树标签集作为最终结果输出[28-29]。

实验结果见图4。

图4 三种分类方法在数据集上的表现

所有数据都是在各个数据集上相应指标的平均值，同时记录了对应的标准差。从图中可以看出，尽管MC方法在大多数指标下都是较优的，并且有一些显著优越的结果，但是BPS在层次标签树较浅或者叶子节点较少的数据集中具有竞争力(Fun数据集层次结构为4层，大约15个叶子节点)。可以看到该方法在Accuracy和Full-match两个指标有较好的结果，这些指标对预测结果中出现的错误进行了度量。这意味着文中方法如果基分类器输出的概率值过低，会对层次标签树进行裁剪，而MC方法返回完整的路径可能是不正确的。对于层次标签树高度较高但标签节点不是很稠密的数据集(GO数据集层次结构为11层，大约24个叶子节点)，大多数情况下，文中方法比MC方法能获得更好的结果。

在基因组数据集中，文中方法和MC方法的性能差异很小，是因为在叶子节点较少的层次结构中，MC方法往往能返回良好的结果。然而，从Caltech数据集的实验结果可以看到，当层次标签树中有较多的叶子节点时就很难用单一的分类器来区分不同的路径。Caltech数据集含有256和84个叶子节点，五个度量指标数据都表明笔者的方法要优于MC方法。故在大型层次结构中文中方法要优于MC方法。同时基于路径选择的层次多标签分类(BPS)对于多标签链分类(CC)也是很有竞争力的，除了在Full-match指标下BPS要明显优于CC，其他指标都有相似的结果，但是BPS计算性能要优于CC。

4 结束语

提出了一种新颖的基于路径选择的层次多标签分类方法，可以用于解决标签节点路径在层次标签树内节点终止的数据集。BPS为层次标签树中每一个内节点训练一个多类分类器，同时用含有该节点兄弟节点标签的数据集构成未知标签样本，用于层次树的裁剪。该方法在层次标签树中选择路径得分超过一定阈值的一条或多条路径，其中路径得分是结合路径上对应标签节点基分类器的预测值和该节点在层次标签树中的层次赋予不同的权重计算得到。为了使预测的标签路径在层次标签树的内节点终止，需要根据各标签节点基分类器对应的子节点概率值进行层次标签树的裁剪，从而消除可能性较低的分支。使用三份不同的数据对基于路径选择的层次多标签分类方法进行验证，同时与现有方法进行比较，结果表明该方法均能取得较好的结果，并且在层次较深且叶子节点较多的层次结构表现更优。