多标记分类方法比较 - Home - LAMDA

多标记分类方法比较

徐兆桂

(南京大学计算机科学与技术系, 南京210093)

A Comparative Study of Multi-label Classification Approaches

Zhao-GUI Xu

(Department of Computer Science and Technology, Nanjing University, Nanjing 210093, China)

Abstract: Multi-label learning is a common problem in real application, and till now many approaches have been proposed to solve it. Generally, these approaches can be divided into two kinds, problem transformation methods and algorithm adaptation methods. In this paper, a structural overview has been given based on these two kinds of approaches, and some of which have been chosen to make empirical comparisons as well. In the experiment part of this paper, approaches are separated into two groups, BR, CC and RAkEL a group, and MLkNN, BRkNN and BPMLL a group. Different real-world datasets and various evaluation measures are used to explore advantages and disadvantages of each approach.

Key words: multi-label; problem transformation; algorithm adaptation; BR; CC; RAkEL; MLkNN; BRkNN; BPMLL 摘要: 多标记学习是现实运用中的一类常见的问题，目前已经有很多种方法来解决多标记分类问题。这些方法大致可以分为两类分别是问题转换和算法改造。本文针对这两类方法作了结构性的介绍并且对其中的一些方法作实际比较。在文章的实验部分中，这些方法被分成两组进行比较，BR、CC和RAkEL为一组，MLkNN、BRkNN 和BPMLL为一组。实验利用不同的数据集和不同的评价指标来探索这些方法的优缺点。

关键词: 多标记学习；问题转换；算法改造；BR；CC；RAkEL；MLkNN；BRkNN；BPMLL

1 引言

传统的分类学习中，每个样本只属于一个类别。然而在很多实际问题当中，一个样本可能同时属于多个类别。例如，在文档分类[1]问题中，每篇文档可能属于多个预定义的主题，在图片分类[2]中，每个图片可能含有不同的语义，在生物信息学[3]问题中，每个基因可能同时具有多种功能。由此引出了多标记学习（Multi-label learning）的研究。至今，研究者们已经提出了多种多标记学习的方法，比如基于支持向量的方法，基于BP神经网络的方法，基于概率生成模型的方法等。这些算法在文档分类、生物信息学以及场景分类等许多领域得到了成功的运用。

本文首先选择两种基于K近邻的惰性学习方法进行比较，并选择其中相对较好的与基于BP神经网络的

方法BPMLL，以及基于转换的学习方法LP相比较，最后给出了一些比较之后的总结。

2 多标记分类简介

多标记学习问题可以描述如下：设样本的特征属性X=x i:i=1…m，有限标记集合Y= λj:j=1…q，给定学习样本集S=x i,L i:i=1…k，其中x i∈X,L i⊆Y。要求构造分类器h，能够对未知样本集T=x k+i,?:i=1…p进行标记。

2.1 分类算法描述

解决多标记学习的思路主要有两种：一是算法独立，亦即通过对样本集进行分解，将多标记学习转化为多个单标记学习问题来处理；二是算法依赖，亦即通过对原有算法进行改造，使其能够处理多标记问题。下面将分别回顾基于这两种思想的一些常见方法。

2.1.1 问题转换方法

（1）基于标记转换方法

假设样本实例的标记总数为q，针对每个标记分类出属于这个标记的为一类，不属于的为另一类。这样的二分转换思想可以直观的参考图1所示。

典型的利用这种思想的多标记分类方法是Binary Relevance (BR)。BR方法将原来的数据集分成了q个,j=1…q，其中每个数据集包含了所有原数据集中的样本实例。但是这每个数据集都属于单个二分数据集Dλ

j

数据集中的每个实例要么标记为Positive，标记集并且标记仅为Positive和Negative，根据原数据集得出的Dλ

j

要么为Negative。分类一个新的实例，BR 输出一个合集，这个合集是由q个基分类器输出中包含的Positive 例组成的。从上文分析看来BR算法的好处是它的计算复杂度相对其他算法而言较小。对于实例固定的样本而言，BR的时间复杂度和样本标记集L的标记数量q成正比，它的复杂度为q×O C，其中O C为基础分类算法的复杂度。因此，BR算法针对标记数量q比较小的情况下适用。然而，在很多领域中是存在大量标记的，甚至这些标记是有树状的层次的关联的。对于这种情况，BR算法的局限性就比较大，因为它没有考虑到这些标记之间的关联性。

Classifier Chain(CC)[4]方法成功克服了BR没考虑标记之间的关联性这一缺点。CC方法依然使用BR所使用的二叉分类。与BR不同的是，它将这些基分类器C j,j=1…q串联起来形成一条链。CC方法可以大致描述如下：一个分类器C j对应一个标记λj。假设一个新的实例x需要分类，分类器C1判断x是否属于标记λ1，设其值为y∈{0,1}，得出Pr⁡(λ1|x)。分类器C2判断x是否属于标记λ2，但是此时会将上y1作为输入得到Pr⁡(λ2x,λ1)。以此类推，当C j判断x是否属于标记λj时，会将y1,…,y j−1作为额外的信息输入得到Pr⁡(λ2|x,λ1,…,λj−1)。这种链的方式使得标记信息在分类器之间传递，考虑到了标记之间的关联性，克服了BR的缺点，并且仍然保持了BR的计算复杂度低的优点。

为了提高整体的精确度，并且实现并行，研究者们还为BR、CC等提出了Ensemble的框架，得到了EBR、ECC等的算法。这些算法表现出了很好的性能，在此不作详述。

图1 基于标记转换方法示例