1. 引言
在传统监督学习中一个样本只与一个标签相关,这类问题被称为单标签问题。但是在现实生活中往往并非如此,一个样本也可以与多个标签相关联,比如一篇文章可能存在多个关键词,一幅图像可以拥有多个主题,我们把这类问题称为多标签问题。与单标签分类不同,多标签分类问题会更加复杂。
问题转换是处理多标签问题的方法之一。其主要思想是将多标签问题转化为一个或多个单标签问题进行处理。BR (binary relevance)是最常见的问题转换方法,实现方法简单,容易理解。但在考虑标签之间的相关性时,最终构建模型的泛化能力会比较弱。而Read等 [1] 在2009年提出的分类器链算法,在一定程度上克服了这个问题。分类器链同样是将多标签问题转化为单标签问题 [2],但与传统二分类方法不同的是,分类器链算法把标签当作额外信息添加到属性集中,即每个已知标签都可以看作是属性空间的子集。实际上就是样本属性在不断的扩充。在这一过程中考虑了标签之间的相关性,特别是在训练样本很少的情况,缺少有用的信息时,考虑标签之间的相关性就显得尤为重要。
粗糙集是一种新的软计算方法,近年来受到越来越多的关注。它的有效性已经在许多科学和工程领域的成功应用中得到了证明。最早由波兰科学家Pawlak在1982年 [3] 提出。此后,粗糙集理论逐渐应用于单标签数据的属性约简中 [4],并取得了令人满意的效果。近年来,粗糙集被广泛地应用于多标签数据属性约简中 [5] [6] [7] [8]。然而,在约简过程中考虑标签之间的相关性,降低计算复杂度是需要解决的主要问题。本文主要根据多标签链分解的特点,将其与粗糙集方法相结合,在考虑标签间相关性的基础上进行属性约简。
本文剩余部分结构如下:在第二节中,提出了两种标签排序方法,并将多标签分解成链的形式。在第三节中,对于每个分解之后的子问题给出了新的相似类、正域、依赖度的定义,并设计了一种新的属性约简算法。在第四节中,在给定的五个数据集上进行了数值实验,并对于实验结果进行了分析。在第五节中,对本文所得的结论和实验结果进行总结。
2. 多标签链分解
基于链分解的多标签问题本质上是将多标签问题转化为链的形式。在分解过程中,已知标签依次作为额外的属性为样本提供分类信息,所以标签的排序非常重要。本节主要提出两种标签排序方法,建立了链式分解。在此之前给出多标签分类问题的基本框架。
令
为样本集,
为标签集,
代表属性集合。我们可以将多标签数据集表示为
。对每一个属性
,样本
在属性a上的取值记为
。对每个标签
,样本
的标签值为
,如果
具有标签
,
否则为0。下面我们给出两种标签排序的方法。
方法一:邻域法
该方法主要是利用邻域的概念,找出每个样本邻域内各个标签的出现次数,对于所有样本邻域内同一类标签出现次数相加并求其平均值,根据平均值确定标签排列顺序。接下来我们将给出邻域法的相关定义。
给定标签数据集
,对于任意
,样本
的相似类定义如下:
对于任意
,令
其中x是
邻域内的任意一个样本,
表示样本
邻域内标签
出现次数。基于以上公式,将所有样本的邻域内标签
出现的次数相加并求其平均值:
根据平均数的大小,按照降序将标签进行排列。不妨设排序后的标签列为
。
方法二:计数法
计数法就是找到所有与标签
相关的样本,根据相关样本集基数的大小进行标签排序。接下来我们将给出相关定义。
给定标签数据集
,令
这里,
是与标签
相关的样本集,根据
基数将标签降序排列,排序后的标签列仍然记为
。
根据以上两种标签排序方法,对m个标签进行排序。将标签依次视为新的属性加入到原属性集中,令
对于序列中的第j个标签新的属性集可以表示为:
则有
。
以上是将多标签问题分解为链式子问题的过程,其主要优势是考虑了标签之间的相关性,标签被当做属性添加到原始属性集A中用来为样本提供有效信息。此时,子问题的数据集记为
。
3. 属性约简
在本节中根据以上多标签链分解的特点,对于每个子问题将重新定义下近似、正域并提出新的约简方法,在此之前我们将先给出标签信息集的定义。对于任意
,标签信息集定义如下:
由所有标签信息集组成的集合族可以表示为:
对于任意属性子集
,根据属性集
的特点,扩充后的属性集可以表示成如下形式:
定义2.1:对于多标签数据集
,样本
的相似类可以被重新定义为。
定义2.2:给定多标签数据集
,对于属性子集
,关于标签信息集
的下近似定义如下:
定义2.3:给定原始多标签数据集
,对于属性子集
,其正域定义为:
引理2.1:对于任意的属性子集
,如果
,则有
证明:对于任意
从定义2.3可知
。故存在
,使得
根据下近似定义
,由
可以得到
,因此
,则有
,即
,所以
成立。
定义2.4:对于多标签数据
,当且仅当
满足以下条件
1)
,
2)
其中
,
则称集合B是多标签数据集的链式正域约简。
接下来,我们将介绍链式依赖性约简。在此之前,将依赖函数定义为:
其中
表示相应集合的基数。由引理2.1可以直接得到依赖度的单调性引理。
引理2.2:对于任意的
,有
定义2.4:对于多标签数据
,对于任意的
如果属性子集
满足以下条件:
1)
,
2) 对于任意的
,
,
则称集合B是多标签数据集的链式依赖度约简。
在样本空间中,每个样本包含多个属性,而且每个属性的重要度不同。接下来,我们将使用上面定义的依赖函数来评估每个属性的重要性。
定义2.5:给定多标签数据
,令属性子集
,则属性
关于属性子集B的重要性度定义为:
这里我们使用重要性的概念来给出算法的伪代码。
参数
用来构造终止准则,当待选属性的重要度小于
时,算法停止运行并输出约简属性。
第2步到第6步是计算属性集B中各属性的重要度,根据定义2.5,将值最大的属性添加到集合Red。第7步到第11步,判断算法的终止条件,当待选属性的重要度小于
时输出约简,否则返回第2步。
4. 实验结果
为了评估本文约简算法的性能,选择5个多标签数据集。在每一个数据集上与其他3种算法进行对比,如表1,其中PRR代表正域约简、MLFRS代表多标签模糊粗糙集属性约简 [9]、NLDR代表邻域标签依赖度约简 [10]、CDDR是本文提出的链式依赖度约简,将不同算法的约简数据输入到分类器中。为了比较约简效果,对每个数据集采用统一的约简比,即不同算法约简的数据包含相同数量的属性。同时,计算未约简数据的度量作为参考。根据样本个数将数据集随机分成10等份,每部分80%作为训练集,20%作为测试集,取10次独立实验的平均值作为实验的最终结果。
Hamming Loss表示测试样本中被误分类的标签在样本所有标签中占的比例。值越小分类能力越强。显然,评价指标与数据集中原始标签的数量密切相关,当数据集中标签数量增加时,其值可能会增加。因此,对于不同的数据集,它是不可比较的。表2的第2列给出了原始数据的Hamming Loss值。第3至第6列中分别是五种算法的简化数据值。从表中可以看出,该算法在数据集CAL500、Yeast、Genbase上的性能明显优于其他算法。而在数据集Medical上与最优算法也仅相差0.004。
Coverage用于考察在样本的类别标签排序序列中,覆盖所有相关标签所需要的搜索深度情况,该指标取值越小性能越优。表3对于Coverage在给定的5个数据集中取得较好的效果,特别是在数据集Yeast上算法CDDR显示出较大的优势,同时在其他2个数据上CDDR的性能与最优算法性能也是非常接近的,没有太多差异。
根据表2、表3可以看出,CDDR与其他多标签属性约简算法相比具有很强的竞争力,其性能优势更明显地验证了基于CDDR的属性约简的有效性。
5. 总结
本文主要介绍了一种新的基于链分解的多标签约简方法。首先针对不同标签所提供信息的重要程度不同,给出了两种标签排序方法固定标签序列以避免错误信息的传递。其次根据固定的序列将多标签问题分解成链的形式,将分解的链与模糊方法相结合,对于每个子问题重新给出定义。最后在不影响精度的基础上,除去冗余属性进行约简。由实验范围广泛的数据集表明,我们的方法具有高度可比性。
值得注意的是,约简本身是一个不连续优化问题,很多算法不能应用。而CDDR算法又只适用于小型数据集,存在计算复杂度高的问题。对于标签之间的关系本文主要从标签出现次数上进行考虑其相关性,但是标签之间的固有联系是一个比较复杂的问题。未来,我们将继续优化模型,寻求更好的排序方法。同时将更深入地研究如何解决标签间相关性问题。