多标签(multi-label)数据问题常用的分类器或者分类策略

多标签（multi-label）数据问题常用的分类器或者分类策略

多标记分类和传统的分类问题相比较，主要难点在于以下两个方面：

(1)类标数量不确定，有些样本可能只有一个类标，有些样本的类标可能高达几十甚至上百个。

(2)类标之间相互依赖，例如包含蓝天类标的样本很大概率上包含白云，如何解决类标之间的依赖性问题也是一大难点。

对于多标记学习领域的研究，国外起步较早，起源于2000年Schapire R E等人提出的基于boost方法的文本多分类，著名的学者有G Tsoumakas、Eyke Hüllermeier、Jesse Read，Saso Dzeroski等等。在国内，南京大学的周志华和张敏灵和哈工大的叶允明等等学者在这一领域较都有很好研究成果。

目前有很多关于多标签的学习算法，依据解决问题的角度，这些算法可以分为两大类：一是基于问题转化（Problem Transformation）的方法，二是基于算法适应的方法和算法适应方法（Algorithm Adaptation）。基于问题转化的多标记分类是转化问题数据，使之适用现有算法；基于算法适应的方法是指针对某一特定的算法进行扩展，从而能够直接处理多标记数据，改进算法，适应数据。基于这两种思想，目前已经有多种相对成熟的算法被提出，如下图所示：

问题转化方法（Problem Transformation）：该类方法的基本思想是通过对多标记训练样本进行处理，将多标记学习问题转换为其它已知的学习问题进行求解。代表性学习算法LP[1]，Binary Relevance[2]，Calibrated Label Ranking[3]，Random k-labelsets[4]。总体来说，这类方法有考虑类标之间的联系，但是对于类标较多、数据量较大的数据集，这类方法的计算复杂度是一个很明显的缺陷。

算法适应方法与问题转化方法不同，问题转化方法是将多标记问题转化成一个或者多个单类标问题，算法适应方法是在多标记的基础上研究算法。近年来，用于多标记的算法适应的算法越来越多，代表性学习算法ML-kNN[5]，Rank-SVM[6]，LEAD[7]，CML。

对于分类策略，基于考察标记之间相关性的不同方式，已有的多标记学习算法的策略思路大致可以分为以下三类[8]：

a) “一阶（first-order）”策略：该类策略通过逐一考察单个标记而忽略标记之间的相关性，如将多标记学习问题分解为个独立的二类分类问题，从而构造多标记学习系统。该类方法效率较高且实现简单，但由于其完全忽略标记之间可能存在的相关性，其系统的泛化性能往往较低。

b) “二阶（second-order）”策略：该类策略通过考察两两标记之间的相关性，如相关标记与无关标记之间的排序关系，两两标记之间的交互关系等等，从而构造多标记学习系统。该类方法由于在一定程度上考察了标记之间的相关性，因此其系统泛化性能较优。

c) “高阶（high-order）”策略：该类策略通过考察高阶的标记相关性，如处理任一标记对其它所有标记的影响，处理一组随机标记集合的相关性等等，从而构造多标记学习系统。该类方法虽然可以较好地反映真实世界问题的标记相关性，但其模型复杂度往往过高，难以处理大规模学习问题。

[1] Madjarov G, Kocev D, Gjorgjevikj D, et al. An extensive experimental comparison

of methods for multi-label learning[J]. Pattern Recognition, 2012, 45(9): 3084-3104.

[2] Boutell M R, Luo J, Shen X, Brown C M. Learning multi-label scene classification.

Pattern Recognition, 2004, 37(9): 1757-1771.

[3] Fürnkranz J, Hüllermeier E, LozaMencía E, Brinker K. Multilabel classification via

calibrated label ranking. Machine Learning, 2008, 73(2): 133-153.

[4] Tsoumakas G, Vlahavas I. Random k-labelsets: An ensemble method for multilabel

classification. In: Kok J N, Koronacki J, de Mantaras R L, Matwin S, Mladenič D, Skowron A, eds. Lecture Notes in Artificial Intelligence 4701, Berlin: Spr inger,

2007, 406-417.

[5] Zhang M-L, Zhou Z-H. ML-kNN: A lazy learning approach to multi-label learning.

Pattern Recognition, 2007, 40(7): 2038-2048.

[6] Elisseeff A, Weston J. A kernel method for multi-labelled classification. In: Dietterich

T G, Becker S, Ghahramani Z, eds. Advances in Neural Information Processing Systems 14 (NIPS’01), Cambridge, MA: MIT Press, 2002, 681-687.

[7] Zhang M-L, Zhang K. Multi-label learning by exploiting label dependency. In: Pro

ceedings of the 16th ACM SIGKDD International Conference on Knowledge Discov ery and Data Mining (KDD’10), Washington, D. C., 2010, 999-1007.

[8] Zhang M L, Zhang K. Multi-label learning by exploiting label dependency[C]// ACM

SIGKDD International Conference on Knowledge Discovery and Data Mining.

ACM, 2010:999-1008.