基于链分解的多标签分类属性约简
Attribute Reduction for Multi-Label Classification Based on Chain Decomposition

作者: 张莹 :渤海大学数学系,辽宁 锦州;

关键词: 多标签分类属性约简粗糙集链分解Attribute Reduction Rough Set Multi-Label Classification Chain Decomposition

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

Abstract: In this paper, a new multi-label attribute reduction algorithm based on the chain decomposition is proposed. Considering the correlation between the labels, the labels are sorted. According to the sorting method, the multi-label problem is decomposed into a single-label problem chain. For each sub-problem, the lower approximation, the positive region and the dependency are redefined by the rough set method, and the attributes are reduced. Experimental results show that the algo-rithm can remove most of the redundant attributes without reducing the classification accuracy.

1. 引言

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

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

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

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

2. 多标签链分解

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

X = { x 1 , x 2 , x 3 , , x n } 为样本集, Y = { y 1 , y 2 , y 3 , , y m } 为标签集, A = { a 1 , a 2 , a 3 , , a d } 代表属性集合。我们可以将多标签数据集表示为 ( X , A , Y ) 。对每一个属性 a A ,样本 x i 在属性a上的取值记为 a ( x i ) 。对每个标签 y j Y ,样本 x i 的标签值为 y j ( x i ) ,如果 x i 具有标签 y j y j ( x i ) = 1 否则为0。下面我们给出两种标签排序的方法。

方法一:邻域法

该方法主要是利用邻域的概念,找出每个样本邻域内各个标签的出现次数,对于所有样本邻域内同一类标签出现次数相加并求其平均值,根据平均值确定标签排列顺序。接下来我们将给出邻域法的相关定义。

给定标签数据集 ( X , A , Y ) ,对于任意 ε > 0 ,样本 x i 的相似类定义如下:

[ x i ] A ε = { x X : | a ( x i ) a ( x ) | ε , a A }

对于任意 y j Y ,令

T j ( x i ) = x [ x i ] A ε y j ( x ) , j = 1 , 2 , , m , i = 1 , 2 , , n .

其中x是 x i 邻域内的任意一个样本, T j ( x i ) 表示样本 x i 邻域内标签 y j 出现次数。基于以上公式,将所有样本的邻域内标签 y j 出现的次数相加并求其平均值:

r a n k ( y j ) = i = 1 n T j ( x i ) n

根据平均数的大小,按照降序将标签进行排列。不妨设排序后的标签列为 ( y 1 , y 2 , , y m )

方法二:计数法

计数法就是找到所有与标签 y j 相关的样本,根据相关样本集基数的大小进行标签排序。接下来我们将给出相关定义。

给定标签数据集 ( X , A , Y ) ,令

X j = { x i | y j ( x i ) = 1 , 1 i n } , j = 1 , 2 , , m .

这里, X j X 是与标签 y j 相关的样本集,根据 X j 基数将标签降序排列,排序后的标签列仍然记为 ( y 1 , y 2 , , y m )

根据以上两种标签排序方法,对m个标签进行排序。将标签依次视为新的属性加入到原属性集中,令

A 1 = A { y 1 }

对于序列中的第j个标签新的属性集可以表示为:

A j = A j 1 { y j } , j = 2 , 3 , , m .

则有 A A 1 A 2 A j 1 A m

以上是将多标签问题分解为链式子问题的过程,其主要优势是考虑了标签之间的相关性,标签被当做属性添加到原始属性集A中用来为样本提供有效信息。此时,子问题的数据集记为 ( X , A j , y j ) , j = 1 , 2 , , m

3. 属性约简

在本节中根据以上多标签链分解的特点,对于每个子问题将重新定义下近似、正域并提出新的约简方法,在此之前我们将先给出标签信息集的定义。对于任意 y j Y ,标签信息集定义如下:

E j = { x X : y j ( x ) = 1 } , j = 1 , 2 , , m .

由所有标签信息集组成的集合族可以表示为:

E = { E j | j = 1 , 2 , , m } .

对于任意属性子集 B A ,根据属性集 A j 的特点,扩充后的属性集可以表示成如下形式:

B 1 = B { y 1 }

B j = B j 1 { y j } , j = 1 , 2 , , m .

定义2.1:对于多标签数据集 ( X , A j , Y ) ,样本 x i 的相似类可以被重新定义为。

[ x i ] B j ε = { x X : | a ( x i ) a ( x ) | ε , | y j ( x i ) y j ( x ) | ε , a , y j B j } .

定义2.2:给定多标签数据集 ( X , A j , Y ) ,对于属性子集 B j A j ,关于标签信息集 E j 的下近似定义如下:

R _ B j ε ( E j ) = { x i X : [ x i ] B j ε E j } .

定义2.3:给定原始多标签数据集 ( X , A , Y ) ,对于属性子集 B A ,其正域定义为:

P O S B ε ( E ) = E j E R _ B j ε ( E j ) .

引理2.1:对于任意的属性子集 B A , B A ,如果 B B ,则有

P O S B ε ( E ) P O S B ε ( E )

证明:对于任意 x P O S B ε ( E ) 从定义2.3可知 x E j E R _ B 1 ε ( E j ) 。故存在 E j E ,使得 x R _ B ε ( E j ) 根据下近似定义 [ x ] B ε E j ,由 B B 可以得到 [ x ] B ε [ x ] B ε E j ,因此 x R _ B ε ( E j ) ,则有 x E j E R _ B ε ( E j ) ,即 x P O S B ε ( E ) ,所以 P O S B ε ( E ) P O S B ε ( E ) 成立。

定义2.4:对于多标签数据 ( X , A , Y ) ,当且仅当 B A 满足以下条件

1) P O S B ε ( E ) = P O S A ε ( E )

2) P O S B ε ( E ) P O S A ε ( E ) 其中 B B

则称集合B是多标签数据集的链式正域约简。

接下来,我们将介绍链式依赖性约简。在此之前,将依赖函数定义为:

γ B ε ( E ) = 1 m j = 1 m | R _ B ε ( E j ) | | X |

其中 | | 表示相应集合的基数。由引理2.1可以直接得到依赖度的单调性引理。

引理2.2:对于任意的 B B A ,有

γ B ε ( E ) γ B ε ( E )

定义2.4:对于多标签数据 ( X , A , Y ) ,对于任意的 B B 如果属性子集 B A 满足以下条件:

1) γ B ε ( E ) = γ A ε ( E )

2) 对于任意的 B B γ B ε ( E ) γ A ε ( E )

则称集合B是多标签数据集的链式依赖度约简。

在样本空间中,每个样本包含多个属性,而且每个属性的重要度不同。接下来,我们将使用上面定义的依赖函数来评估每个属性的重要性。

定义2.5:给定多标签数据 ( X , A , Y ) ,令属性子集 B A ,则属性 a i B 关于属性子集B的重要性度定义为:

S i g i n ( a i , B ) = γ B ε ( E ) γ ( B a i ) ε ( E ) .

这里我们使用重要性的概念来给出算法的伪代码。

参数 φ 用来构造终止准则,当待选属性的重要度小于 φ 时,算法停止运行并输出约简属性。

第2步到第6步是计算属性集B中各属性的重要度,根据定义2.5,将值最大的属性添加到集合Red。第7步到第11步,判断算法的终止条件,当待选属性的重要度小于 φ 时输出约简,否则返回第2步。

4. 实验结果

为了评估本文约简算法的性能,选择5个多标签数据集。在每一个数据集上与其他3种算法进行对比,如表1,其中PRR代表正域约简、MLFRS代表多标签模糊粗糙集属性约简 [9]、NLDR代表邻域标签依赖度约简 [10]、CDDR是本文提出的链式依赖度约简,将不同算法的约简数据输入到分类器中。为了比较约简效果,对每个数据集采用统一的约简比,即不同算法约简的数据包含相同数量的属性。同时,计算未约简数据的度量作为参考。根据样本个数将数据集随机分成10等份,每部分80%作为训练集,20%作为测试集,取10次独立实验的平均值作为实验的最终结果。

Table 1. Multi-label data sets

表1. 多标签数据集

Hamming Loss表示测试样本中被误分类的标签在样本所有标签中占的比例。值越小分类能力越强。显然,评价指标与数据集中原始标签的数量密切相关,当数据集中标签数量增加时,其值可能会增加。因此,对于不同的数据集,它是不可比较的。表2的第2列给出了原始数据的Hamming Loss值。第3至第6列中分别是五种算法的简化数据值。从表中可以看出,该算法在数据集CAL500、Yeast、Genbase上的性能明显优于其他算法。而在数据集Medical上与最优算法也仅相差0.004。

Table 2. Hamming loss

表2. 汉明损失

Table 3. Coverage

表3. 覆盖率

Coverage用于考察在样本的类别标签排序序列中,覆盖所有相关标签所需要的搜索深度情况,该指标取值越小性能越优。表3对于Coverage在给定的5个数据集中取得较好的效果,特别是在数据集Yeast上算法CDDR显示出较大的优势,同时在其他2个数据上CDDR的性能与最优算法性能也是非常接近的,没有太多差异。

根据表2表3可以看出,CDDR与其他多标签属性约简算法相比具有很强的竞争力,其性能优势更明显地验证了基于CDDR的属性约简的有效性。

5. 总结

本文主要介绍了一种新的基于链分解的多标签约简方法。首先针对不同标签所提供信息的重要程度不同,给出了两种标签排序方法固定标签序列以避免错误信息的传递。其次根据固定的序列将多标签问题分解成链的形式,将分解的链与模糊方法相结合,对于每个子问题重新给出定义。最后在不影响精度的基础上,除去冗余属性进行约简。由实验范围广泛的数据集表明,我们的方法具有高度可比性。

值得注意的是,约简本身是一个不连续优化问题,很多算法不能应用。而CDDR算法又只适用于小型数据集,存在计算复杂度高的问题。对于标签之间的关系本文主要从标签出现次数上进行考虑其相关性,但是标签之间的固有联系是一个比较复杂的问题。未来,我们将继续优化模型,寻求更好的排序方法。同时将更深入地研究如何解决标签间相关性问题。

文章引用: 张莹 (2020) 基于链分解的多标签分类属性约简。 数据挖掘, 10, 240-246. doi: 10.12677/HJDM.2020.104025

参考文献

[1] Read, J., Pfahringer, B., Holmes, G. and Frank, E. (2009) Classifier Chains for Multi-Label Classification. In: Buntine, W., Grobelnik, M. and Shawe-Taylor, J., Eds., Lecture Notes in Artificial Intelligence 5782, Springer, Berlin, 254-269.
https://doi.org/10.1007/978-3-642-04174-7_17

[2] Read, J., Pfahringer, B., Holmes, G. and Frank, E. (2011) Classifier Chains for Multi-Label Classification. Machine. Learning, 85, 333-359.
https://doi.org/10.1007/s10994-011-5256-5

[3] Pawlak, Z. (2011) Rough Sets. International Journal of Computer and Information Sciences, 11, 34l-356.
https://doi.org/10.1007/BF01001956

[4] Hu, Q.H., Yu, D.R., Liu, J.F. and Wu, C. (2008) Neighborhood Rough Set Based Heterogeneous Feature Subset Selection. Information Sciences, 178, 3577-3594.
https://doi.org/10.1016/j.ins.2008.05.024

[5] Li, H., Li, D., Zhai, Y., Wang, S. and Zhang, J. (2016) A Novel At-tribute Reduction Approach for Multi-Label Data Based on Rough Set Theory. Information Sciences, 367-368, 827-847.
https://doi.org/10.1016/j.ins.2016.07.008

[6] Lin, Y., Li, Y., Wang, C. and Chen, J. (2018) Attribute Reduction for Multi-Label Learning with Fuzzy Rough Set. Knowledge-Based Systems, 152, 51-61.
https://doi.org/10.1016/j.knosys.2018.04.004

[7] Liu, J., Lin, Y., Li, Y., Weng, W. and Wu, S. (2018) Online Multi-Label Streaming Feature Selection Based on Neighborhood Rough Set. Pattern Recognition, 84, 273-287.
https://doi.org/10.1016/j.patcog.2018.07.021

[8] Lin, Y., Hua, Q., Liu, J., Chen, J. and Duan, J. (2016) Mul-ti-Label Feature Selection Based on Neighborhood Mutual Information. Applied Soft Computing, 38, 244-256.
https://doi.org/10.1016/j.asoc.2015.10.009

[9] Lin, Y., Li, Y., Wang, C. and Chen, J. (2018) Attribute Reduction for Multi-Label Learning with Fuzzy Rough Set. Knowledge-Based Systems, 152, 51-61.
https://doi.org/10.1016/j.knosys.2018.04.004

[10] Fan, X., Chen, Q., Qiao, Z., Wang, C. and Ten, M. (2020) At-tribute Reduction for Multi-Label Classification Based on Labels of Positive Region. Soft Computing, 24, 14039-14049.
https://doi.org/10.1007/s00500-020-04780-4

分享
Top