基于链分解的多标签分类属性约简

本文提出了基于链分解的多标签属性约简方法。通过考虑标签之间的相关性，将标签进行排序，根据排序方法，多标签问题被分解成单标签链的形式，对于链中每一个子问题通过粗糙集方法重新定义下近似、正域、依赖度，并进行属性约简。实验结果表明，该方法能在不降低分类精度的情况下去除大部分冗余属性。

在传统监督学习中一个样本只与一个标签相关，这类问题被称为单标签问题。但是在现实生活中往往并非如此，一个样本也可以与多个标签相关联，比如一篇文章可能存在多个关键词，一幅图像可以拥有多个主题，我们把这类问题称为多标签问题。与单标签分类不同，多标签分类问题会更加复杂。

问题转换是处理多标签问题的方法之一。其主要思想是将多标签问题转化为一个或多个单标签问题进行处理。BR (binary relevance)是最常见的问题转换方法，实现方法简单，容易理解。但在考虑标签之间的相关性时，最终构建模型的泛化能力会比较弱。而Read 等[1]在2009 年提出的分类器链算法，在一定程度上克服了这个问题。分类器链同样是将多标签问题转化为单标签问题[2]，但与传统二分类方法不同的是，分类器链算法把标签当作额外信息添加到属性集中，即每个已知标签都可以看作是属性空间的子集。实际上就是样本属性在不断的扩充。在这一过程中考虑了标签之间的相关性，特别是在训练样本很少的情况，缺少有用的信息时，考虑标签之间的相关性就显得尤为重要。

粗糙集是一种新的软计算方法，近年来受到越来越多的关注。它的有效性已经在许多科学和工程领域的成功应用中得到了证明。最早由波兰科学家Pawlak 在1982 年[3]提出。此后，粗糙集理论逐渐应用于单标签数据的属性约简中[4]，并取得了令人满意的效果。近年来，粗糙集被广泛地应用于多标签数据属性约简中[5] [6] [7] [8]。然而，在约简过程中考虑标签之间的相关性，降低计算复杂度是需要解决的主要问题。本文主要根据多标签链分解的特点，将其与粗糙集方法相结合，在考虑标签间相关性的基础上进行属性约简。

本文剩余部分结构如下：在第二节中，提出了两种标签排序方法，并将多标签分解成链的形式。在第三节中，对于每个分解之后的子问题给出了新的相似类、正域、依赖度的定义，并设计了一种新的属性约简算法。在第四节中，在给定的五个数据集上进行了数值实验，并对于实验结果进行了分析。在第五节中，对本文所得的结论和实验结果进行总结。

2. 多标签链分解 基于链分解的多标签问题本质上是将多标签问题转化为链的形式。在分解过程中，已知标签依次作为额外的属性为样本提供分类信息，所以标签的排序非常重要。本节主要提出两种标签排序方法，建立了链式分解。在此之前给出多标签分类问题的基本框架。

令{}123, , , , nXx xxx=为样本集， {}123, , , , mYy yyy′′′′=为标签集， {}123, , , , dAa a aa=代表属性集合。

我们可以将多标签数据集表示为(), , X A Y 。

对每一个属性aA∈， 样本ix 在属性a 上的取值记为()ia x。

对每个标签jyY′ ∈，样本ix 的标签值为( )jiyx′，如果ix 具有标签jy′ ， ( )1jiyx′= 否则为0。下面我们给出两种标签排序的方法。

方法一：邻域法