蔡 剑 牟甲鹏 余孟池 徐 建

（南京理工大学计算机科学与工程学院 南京 210094）

1 引言

传统的分类学习处理一个实例与单个类别标签相关的问题。但是在现实世界中，一个实例可能会具有多个类别标签。例如，一张图片可能会被标注上多个关键词；一篇文章可能属于多个主题；一个基因也可能与多个功能相关。为了表达这些对象拥有的多重语义，经常使用一个标签子集代替单个标签来标识该对象，这类使用标签子集来表达对象语义的学习模式称为多标签学习。多标签分类的目标就是为具有多重语义的对象建立分类模型，让该模型可以有效预测未知实例的相关标签子集。

解决多标签分类问题最经典的方法是BR（Bi⁃nary Relevance）算法［1］，BR将多标签分类问题转换成多个二分类问题，为每个标签分别训练一个二分类器，最后综合多个分类器结果作为最终的预测结果。BR算法具有简单直接的优点，但是也存在一些问题。Zhang等［2］提出标签相关性（label correla⁃tion）的概念，即标签间通常存在依赖关系，指出BR算法未考虑标签性的问题；Wu等［3］提出类属属性（label-specific feature）的概念，即每个标签具有其特有的属性特征，指出BR算法存在冗余属性的问题。

为了解决BR算法存在的冗余属性问题，现有的改进工作主要有两种：特征选择和特征转化。特征选择的目的是从原始特征空间中筛选出与标签相关性强的属性特征。相关算法有Qu等提出的MLSF算法［4］，该算法分别为正、负例集计算特征密度，以此作为特征选择的指标。特征转化的目的是将原始特征空间映射到类属属性空间中，相关算法有LIFT［5］和其改进算法ELIFT［6］。这些算法虽然都解决了BR算法的冗余属性问题，但最大的问题是没有考虑标签相关性。

为了解决BR未考虑标签相关性的问题，现有的改进工作主要分两种［7］：链结构（chaining struc⁃ture）和堆叠结构（stacking structure）。链结构是假定随机的标签相关性，每个标签的预测仅考虑链之前标签的影响。堆叠结构是假定所有标签的相关性，每个标签的预测需要考虑其他所有标签的影响。这两种策略虽然都考虑了标签相关性，但是未考察加入的特征与标签间的实际关系，因此都存在冗余依赖的问题。此外，由于预测过程需要加入其它标签的预测值，如果预测值有误，则还会引发错误传播的问题。

以上算法都只是单独解决了BR算法的一个问题，鉴于这种情况，本文提出基于特征选择和标签相关性的二元关联算法（Binary Relevance with Fea⁃ture selection and Label correlation，FLBR）。该算法先使用信息增益为每个标签选择与其相关的特征属性，然后引入新的“控制结构”（controlled struc⁃ture）的方式考察标签相关性，最后为每个标签训练二分类器。这里的控制结构指的是对加入特征空间的标签进行“控制”，仅添加与预测标签相关性强并且不容易被预测错误的标签，从而解决链结构和堆叠结构中存在的无关依赖和错误传播问题。实验结果表明，该算法的预测性能明显优于其它的BR改进算法。

2 相关工作

2.1 多标签问题的定义

在本文中，多标签学习描述如下：已知X=Rd表示实体的d维特征空间，标签空间L={y1，y2，…，yq}表示实体可能属于的q个标签。多标签学习的目标是从训练集L}中学习得到一个映射模型h:X→2L。对于每个待预测的未知实例x∈X，多标签分类器做出预测，所得结果即为与实体x相关的标签。

2.2 标签相关性的利用

在改进BR算法的研究工作中，针对标签相关性的改进是最多的，因此接下来对改进BR标签相关性问题常用的两种策略进行具体的介绍。

链结构的算法在BR算法中考虑了标签间链式的相关性，其代表算法是CC（Classifier Chains）算法［8～9］。图1表示标签链为y1，y2，y3时算法的分类预测过程，与BR算法类似，CC也会依次为每个标签训练分类器，但区别是CC训练每个分类器时需要添加标签链中在预测标签前的标签作为额外属性。由于使用的标签链顺序是随机的，算法性能会受到链顺序的影响。因此，算法作者在CC基础上使用集成学习的思想提出了ECC算法［8～9］，从而弱化标签链选取对性能的影响。此外，Cheng等［10］通过计算概率分布来选择最优的链顺序，提出PCC和EPCC算法。Huang等［11］通过构建有向无环图来寻找合适的链顺序，提出GCC算法。

图1 链结构代表算法CC分类示例

堆叠结构的算法在BR算法中考虑了其它所有标签的相关性，其代表算法是DBR（Dependent Bi⁃nary Relevance）算法［12］。DBR算法的分类预测过程如图2所示，需要首先用BR算法为每个标签训练一个二分类器作为基分类器，然后再依次为每个标签训练一个元分类器，元分类器的构建需要添加其它所有标签作为额外属性。由于某些标签之间并不存在依赖关系，DBR算法考虑所有标签相关性会来带冗余依赖的问题。针对这样的问题，Zhang等［13］提出一种基于DBR的剪枝算法（Correla⁃tion-Based Pruning of DBR，CPDBR），通过计算标签间相关性系数phi来量化标签相关性，最后通过阈值来排除冗余依赖的影响。此外，为了解决DBR算法仍会存在的错误传播问题，Alali等［14］提出Pru⁃Dent算法。

图2 堆叠结构代表算法DBR分类示例

3 本文算法

针对BR未考虑标签相关性以及存在冗余属性的问题，本文提出基于标签相关性和特征选择的FLBR算法。同时针对现有考察标签相关性方法存在的冗余依赖和错误传播问题，FLBR采用控制结构的方式考察标签相关性。以下是算法的具体介绍。

3.1 特征选择步骤

FLBR算法首先需要进行特征选择，考察标签和特征之间的关系，从而去除冗余属性。这里的特征选择使用信息增益法，用信息增益来量化两集合的相关程度，集合A、B之间的信息增益可以由式（1）计算。对于数值型的数据集需要先对数据进行离散化，这里使用基于信息熵的方法［15］进行数据的离散化。

其中，H(B)表示集合的熵，其值可以由式（2）计算。H(B|A)表示A集合发生的条件下，B集合的条件熵，其值可以由式（3）计算。

特征选择过程中需要先用公式（1）分别计算每个特征跟标签的信息增益值，然后根据值的大小产生特征排名，最后通过阈值法删除信息增益值小于给定阈值t1的特征，留下的特征集合即为标签的相关特征子集。这里标签yi的相关特征集合Fi可由式（4）得到。

3.2 基分类器构建步骤

经过上一步骤后可以得到每个标签的相关特征集合Fi，接下来使用该特征集合为每个标签分别构建基分类器h(i)←B({Fi，yi})，其中B表示二分类学习算法。

在训练元分类器之前，需要考察每个标签基分类器的预测性能，找出预测准确率低的标签集合。本文将这些标签称为“易错标签”，通过去除相关标签中的易错标签来避免错误传播问题。

为了考察每个标签被预测成功地难易程度，需要为每个标签分别训练分类器t(i)。首先从训练集选择一个子集Ds⊂D作为t(i)的训练集，然后使用测试集DDs对分类器进行验证。这里使用预测精确率作为评价指标，统计每个标签的预测精确率pi。预测概率小于阈值t的标签即为易错标签，易错标签集合记为Le。

3.3 元分类器构建步骤

在元分类器的构建阶段，FLBR使用控制结构的方式考察标签相关性，避免冗余依赖的影响。这里的标签相关性还是通过信息增益方法进行衡量，利用式（1）计算每个标签跟其它标签的信息增益值，标签间的相关性小于给定阈值将会判定为无关标签，无关标签集合记为Lu。这里相关标签的判定阈值仍选用式（4）中使用的t1。

经过上面的处理后，可以得到每个标签中的相关标签集合Li=L-Le-Lu，结合特征选择的结果可以得到新的特征集合为每个标签训练元分类器h′(i)←B(Fi')。FLBR算法的训练过程描述如下。

算法1 FLBR算法的训练过程

判定易错标签的阈值t

二分类学习算法B

输出：为每个标签yi训练的两个分类器hi，h'i

算法步骤：

1）fοr i=1tοq dο

2）根据公式（4）得到每个标签i的相关特征集合Fi；

3）为标签i训练基分类器h(i)←B({Fi，yi})；

4）end for

5）对训练集D随机采样得到子集Ds⊂D；

6）fοr i=1tοq dο

7）为每个标签i训练验证分类器t(i)←B(Ds)；

8）end for

9）根据公式（5）得到易错标签集合ye；

10）fοr i=1tοq dο

11）根据公式（6）得到标签新的特征集合

12）为标签i训练元分类器

13）end for

14）返回每个标签的分类器(h'1，h'2，…，h'q)。

在对实例x分类时，需要先去除其特征集合中的冗余特征，得到其基分类器的预测结果。然后将每个标签相关的正确标签加入到特征集合中，最后获取元分类器的最终分类结果。

4 实验分析

4.1 数据集介绍

本文在六个多标签基准数据集上进行实验对比。所选数据集涉及多标签学习的音乐标注、基因功能预测、文本分类和声学分类四个不同应用领域。表1给出了数据集的统计信息，这些数据集可以从http：//mulan.sourceforge.net/上获取。

表1 实验数据集信息

4.2 评价指标

在给出各个评价指标的数学定义之前，先介绍使用到的数学符号。给定一个测试实例xi，h表示分类器，f表示排序函数，rank f则表示指定标签的排名，p表示实例个数，Δ表示两个集合中不同元素的数量。本实验所使用的评价指标主要包括以下五种：

1）汉明损失（Hamming Loss）：实例被误判的次数，包括属于所给实例的标签未被预测，以及预测出的标签不属于所给实例，其定义如下：

2）单一错误（One-Error）：排名第一的标签不属于所给实例的次数，其定义如下：

3）覆盖距离（Coverage）：预测标签序列中，平均走多少步才能覆盖所给实例的所有相关标签，其定义如下：

4）平均精确度（Average Precision）：统计标签在预测的标签序列中排名在其前面的相关标签的个数，其定义如下：

5）排序损失（Ranking Loss）：考察标签排名中出现排序错误的情况，其定义如下：

上述五种评价指标中，除平均准确率是取值越大了算法性能越好外，其他四个指标都是取值越小越好。

4.3 实验结果及分析

实验主要包括两部分：第一部分是特征选择过程的实验，用以确定最佳的特征选择百分比；第二部分是FLBR算法和其他BR改进算法的对比实验，用以验证FLBR算法的有效性。

首先进行第一部分实验，研究特征选择百分比t对算法结果的影响。这里选择C4.5分类器作为基础分类器，在6个数据集上进行实验。实验采用10重交叉验证方法，统计10次交叉验证结果的均值作为最终结果，实验结果如图3所示。

图3 特征选择阈值t1的实验结果

从以上结果可以看出，随着t1的增大，CAL500和Yeast数据集的各项评价指标都明显变差，Emo⁃tion、Enron和Medical数据集的各项评价指标有变差的趋势，变化幅度相对较小，这五个数据集最佳的特征选择百分比在0.1～0.2之间。Birds数据集的各项指标一直在小范围内波动，没有明显的变化趋势，但是其在0.2处的评价指标优于多数其他取值。因此，当t1取0.2时，各个数据集都具有较好的表现。

接下来进行第二部分的实验，将FLBR算法和典型的BR改进算法进行对比。实验中采用的对比算法有BR，MLSF，FBR，DBR和CPDBR算法。其中FBR是第一部分实验所用算法，仅进行了特征选择。FBR和MLSF是针对冗余特征问题的改进方法，DBR、CPDBR和GCC是针对标签相关性问题的改进方法。本文算法在Weka-3.7.10系统平台上设计和实现，各算法统一使用C4.5分类器作为基础分类器。FLBR算法中涉及到两个参数，易错标签的判定阈值t取0.6，特征选择百分比使用上文得到的结果0.2。其他算法涉及到的阈值均使用原文中选取的阈值。各算法统一使用10重交叉验证后的结果，各算法在6个基准数据集上的实验结果如表2～表6所示。

表2 各算法在数据集上的汉明损失

表6 各算法在数据集上的排序损失

表3 各算法在数据集上的平均准确率

表4 各算法在数据集上的覆盖距离

表5 各算法在数据集上的单一错误

在特征选择方面，MLSF算法在4个数据集上的表现比BR算法好，而FBR算法在6个数据集上的表现都优于BR算法，并且FBR在每个指标上的提升效果更明显。这一方面表明通过解决冗余属性问题可以有效提升算法性能，另一方面也说明FBR是一种有效的特征选择方法。

在考虑标签相关性方面，DBR算法仅在Yeast数据集上优于BR算法，说明无关依赖的引入会误导分类结果。CPDBR算法除了Yeast外，各项指标都优于DBR，但是相较于BR算法并未有明显提升，说明其并未彻底解决冗余属性的问题。而FL⁃BR算法在4个数据集上的表现优于FBR算法，说明FLBR算法通过控制结构考察标签相关性的方式有效解决了冗余属性和错误传播问题，从而验证了控制结构的有效性。在Emotion和Enron数据集中，FLBR算法的表现比FBR略差。究其原因，第一部分实验结果表明Enron和Emotions数据集最佳的特征选择百分比在0～0.1之间，因此使用0.2作为阈值仍会引入无关依赖，从而导致FLBR算法的预测性能变差。

总体来看，算法在6个基准数据集上的总体表现都优于其他典型的BR改进算法。这说明FLBR算法通过同时解决BR存在的冗余属性和未考虑标签相关性两个问题，更有效地提升了BR算法的性能。

5 结语

改进BR算法的方法主要有两种：考虑标签和特征间关系以及考虑标签间相关性，现有的改进工作大多只考虑其中一个方面。针对这样的问题，本文提出基于特征选择和标签相关性的FLBR算法。算法首先进行特征选择，而后将相关标签加入特征集合中，通过这两步操作较好地解决了BR算法存在的问题。此外，针对现有标签相关性改进工作中存在的无关依赖和错误传播问题，FLBR算法使用控制结构的考察方式予以解决。实验表明，FLBR算法取得了比BR的相关改进算法更好的性能。算法在考察标签依赖关系时未考虑其他标签影响，未来将研究更有效的考察方式，以期获得更好的分类效果。