基于联合概率的多标签分类算法

　　传统分类主要研究如何把每条数据更加准确地分到某个预先定义的类别中。如果候选类别只有一个，问题转换为是否属于该类别；如果类别有多个，问题转换为选择一个类别作为输出。这类问题称作单标签问题。

　　多标签问题和单标签问题有着本质的区别：数据可同时属于多个类别。目前，解决多标签分类主要有两类途径[1]：问题转化和算法适应。k邻域（k Nearest Neighborhood， kNN是一类惰性学习方法。 张敏灵Zhang等[2]提出多标签k邻域（MultiLabel kNN，MLkNN算法，它基于二元关联（Binary Relevance， BR[3]，通过最大化后验概率（Maximum A Posteriori， MAP的方式处理多标签分类问题。然而这种方法在计算是否包含某个标签时只考虑实例k个近邻中该标签出现的个数，忽略了标签间的相关性。王霄等[4]改进了MLkNN算法，他们基于二阶策略，通过标签的共现性度量标签间的相关性，但这种方法的性能过度依赖阈值的选择，也并不能进行阈值的学习。

　　本文提出的RMLkNN （coRrelation MultiLabelkNN算法在通过训练集求解条件概率时，统计训练样本k个近邻中标签的联合概率分布，充分考虑了标签间的相关性。通过在多个数据集的实验结果表明，该算法优于MLkNN算法。

　　1相关工作

　　1.1多标签问题描述

　　为了获得多标签问题的形式化描述，下面给出以下定义。

　　定义1属性集A={A1，A2，…，An}。An 表示第n个属性，Ai的取值ai可以是离散的或数值的。

　　定义2标签集L={l1，l2，…，lq}。lq表示第q个标签，一个训练样本的标签取值是L的非空子集。

　　定义3训练集X={x1，x2，…，xm}，xm表示第m个训练样本，其中xm =（a1，a2，…an，ym， ym是样本xm的标签取值，它是L的非空子集。

　　多标签分类问题可以描述为：从训练集X中求得分类模型f

　　x→y，其中yL，即给定未知分类数据x得到标签集合y。

　　1.2多标签分类算法简述

　　1.2.1问题转化方法

　　这类方法通过将多标签问题转化成一个或一组单标签问题，从而使用单标签分类方法处理多标签问题。LP （Label Powerset 通过二进制编码的方式把训练集一组标签作为一个类别，将多标签问题转化为单标签分类任务。对于一条测试数据，LP产生一个最有可能的类别，也就是一组标签。但这种方法的复杂度上限达到了O（min（n， 2k，n是实例个数，k是转化前标签的个数[5]。BR是一种较流行的方法，它把每个标签作为一个独立的单分类问题处理，它为每个标签产生一个二分类器，每条未分类数据的结果是这些二分类器结果的并，这种方法假设标签相互独立，并未考虑标签间的相关性。Hullermeier等[6]提出了标签对比的方法，对k个标签生成Ck2个二分类器，然后以投票的方式决定两个标签λi和λj中的一个赋予未分类数据。Furnkranz等[7]指出了投票方式没有零点来区分相关标签和不相关标签，加入了人工校准，但增加了算法的复杂度。

　　1.2.2算法适应方法

　　算法适应的主要思想是改进常用单标签算法使其能够处理多标签问题。Clare等[8]用C4.5算法和扩展后的熵处理多标签问题，基于熵计算信息增益，从而建立决策树。AdaBoost.MH 和AdaBoost.MRSchapire等 [9]扩展了AdaBoost算法，AdaBoost.MH在每次迭代过程中对误分类标签提升，AdaBoost.MR在每次迭代过程中对误排序的标签进行提升。针对基于树的提升方法在小数据集上容易产生过拟合的问题[10]，Elisseeff 等[11]提出了一种支持向量机的方法。张敏灵Zhang等[2]2038-2048提出了MLkNN算法，算法通过统计k个近邻包含标签的信息，以最大化后验概率的方式预测未分类数据的标签组合，这种方法通过比较包含标签λi的概率和不包含标签λi的概率大小判断是否包含标签λi。算法独立地判断每个标签，并未考虑标签间的相关性。在多标签分类问题中，标签间的相关性不容忽视，本文提出的RMLkNN算法统计训练样本k个近邻中标签的联合概率分布，充分融合了标签间的相关性。

　　2RMLkNN算法

　　本文提出的RMLkNN算法基于Zhang等[2]提出的MLkNN算法，本章先简述MLkNN算法，然后详细介绍RMLkNN算法的基本思想并给出算法描述。

　　2.1MLkNN简述

　　MLkNN统计训练样本中每个实例的k个最邻近（kNN实例中每个标签的个数，用最大化后验概率预测未分类实例。