渤海大学数学系，辽宁 锦州

收稿日期：2020年9月4日；录用日期：2020年9月18日；发布日期：2020年9月27日

摘要

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

关键词

多标签分类，属性约简，粗糙集，链分解

Attribute Reduction for Multi-Label Classification Based on Chain Decomposition

Ying Zhang

Department of Mathematics, Bohai University, Jinzhou Liaoning

Received: Sep. 4^th, 2020; accepted: Sep. 18^th, 2020; published: Sep. 27^th, 2020

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 algorithm can remove most of the redundant attributes without reducing the classification accuracy.

Keywords:Attribute Reduction, Rough Set, Multi-Label Classification, Chain Decomposition

Copyright © 2020 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

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

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

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

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

2. 多标签链分解

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

令 $X=\left\{x_1,x_2,x_3,\cdots ,x_n\right\}$ 为样本集， $Y=\left\{{y^{\prime }}_1,{y^{\prime }}_2,{y^{\prime }}_3,\cdots ,{y^{\prime }}_m\right\}$ 为标签集， $A=\left\{a_1,a_2,a_3,\cdots ,a_d\right\}$ 代表属性集合。我们可以将多标签数据集表示为 $\left(X,A,Y\right)$。对每一个属性 $a\in A$，样本 $x_i$ 在属性a上的取值记为 $a\left(x_i\right)$。对每个标签 ${y^{\prime }}_j\in Y$，样本 $x_i$ 的标签值为 ${y^{\prime }}_j\left(x_i\right)$，如果 $x_i$ 具有标签 ${y^{\prime }}_j$，${y^{\prime }}_j\left(x_i\right)=1$ 否则为0。下面我们给出两种标签排序的方法。

方法一：邻域法

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

给定标签数据集 $\left(X,A,Y\right)$，对于任意 $\epsilon >0$，样本 $x_i$ 的相似类定义如下：

${\left[x_i\right]}_A^{\epsilon }=\left\{x\in X:\left|a\left(x_i\right)-a\left(x\right)\right|\le \epsilon ,a\in A\right\}$

对于任意 ${y^{\prime }}_j\in Y$，令

$T_j\left(x_i\right)={\displaystyle \underset{x\in {\left[x_i\right]}_A^{\epsilon }}{\sum }{y^{\prime }}_j}\left(x\right),j=1,2,\cdots ,m,i=1,2,\cdots ,n.$

其中x是 $x_i$ 邻域内的任意一个样本， $T_j\left(x_i\right)$ 表示样本 $x_i$ 邻域内标签 ${y^{\prime }}_j$ 出现次数。基于以上公式，将所有样本的邻域内标签 ${y^{\prime }}_j$ 出现的次数相加并求其平均值：

$rank\left({y^{\prime }}_j\right)=\frac{{\displaystyle {\sum }_{i=1}^n{T}_j\left(x_i\right)}}{n}$

根据平均数的大小，按照降序将标签进行排列。不妨设排序后的标签列为 $\left(y_1,y_2,\cdots ,y_m\right)$。

方法二：计数法

计数法就是找到所有与标签 ${y^{\prime }}_j$ 相关的样本，根据相关样本集基数的大小进行标签排序。接下来我们将给出相关定义。

给定标签数据集 $\left(X,A,Y\right)$，令

$X_j=\left\{x_i|{y^{\prime }}_j\left(x_i\right)=1,1\le i\le n\right\},j=1,2,\cdots ,m.$

这里， $X_j\subset X$ 是与标签 ${y^{\prime }}_j$ 相关的样本集，根据 $X_j$ 基数将标签降序排列，排序后的标签列仍然记为 $\left(y_1,y_2,\cdots ,y_m\right)$。

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

$A_1=A\cup \left\{y_1\right\}$

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

$A_j=A_{j-1}\cup \left\{y_j\right\},j=2,3,\cdots ,m.$

则有 $A\subset A_1\subset A_2\subset \cdots \subset A_{j-1}\subset A_m$。

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

3. 属性约简

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

$E_j=\left\{x\in X:y_j\left(x\right)=1\right\},\text{}j=1,2,\cdots ,m.$

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

$E=\left\{E_j|j=1,2,\cdots ,m\right\}.$

对于任意属性子集 $B\subset A$，根据属性集 $A_j$ 的特点，扩充后的属性集可以表示成如下形式：

$B_1=B\cup \left\{y_1\right\}$

$B_j=B_{j-1}\cup \left\{y_j\right\},j=1,2,\cdots ,m.$

定义2.1：对于多标签数据集 $\left(X,A_j,Y\right)$，样本 $x_i$ 的相似类可以被重新定义为。

${\left[x_i\right]}_{B_j}^{\epsilon }=\left\{x\in X:\left|a\left(x_i\right)-a\left(x\right)\right|\le \epsilon ,\left|y_j\left(x_i\right)-y_j\left(x\right)\right|\le \epsilon ,a,y_j\in B_j\right\}.$

定义2.2：给定多标签数据集 $\left(X,A_j,Y\right)$，对于属性子集 $B_j\subset A_j$，关于标签信息集 $E_j$ 的下近似定义如下：

${\underset{\_}{R}}_{B_j}^{\epsilon }\left(E_j\right)=\left\{x_i\in X:{\left[x_i\right]}_{B_j}^{\epsilon }\subseteq E_j\right\}.$

定义2.3：给定原始多标签数据集 $\left(X,A,Y\right)$，对于属性子集 $B\subset A$，其正域定义为：

$PO{S}_B^{\epsilon }\left(E\right)={\displaystyle \underset{E_j\in E}{\cup }{\underset{\_}{R}}_{B_j}^{\epsilon }}\left(E_j\right).$

引理2.1：对于任意的属性子集 $B\subset A,B^{\prime }\subset A$，如果 $B^{\prime }\subset B$，则有

$PO{S}_{B^{\prime }}^{\epsilon }\left(E\right)\subseteq PO{S}_B^{\epsilon }(\; E\; )$

证明：对于任意 $x\in PO{S}_{B^{\prime }}^{\epsilon }\left(E\right)$ 从定义2.3可知 $x\in {\displaystyle \underset{E_j\in E}{\cup }{\underset{\_}{R}}_{B_1}^{\epsilon }\left(E_j\right)}$。故存在 $E_j\in E$，使得 $x\in {\underset{\_}{R}}_{B^{\prime }}^{\epsilon }\left(E_j\right)$ 根据下近似定义 ${\left[x\right]}_{B^{\prime }}^{\epsilon }\subseteq E_j$，由 $B^{\prime }\subset B$ 可以得到 ${\left[x\right]}_B^{\epsilon }\subseteq {\left[x\right]}_{B^{\prime }}^{\epsilon }\subseteq E_j$，因此 $x\in {\underset{\_}{R}}_B^{\epsilon }\left(E_j\right)$，则有 $x\in {\displaystyle \underset{E_j\in E}{\cup }{\underset{\_}{R}}_B^{\epsilon }\left(E_j\right)}$，即 $x\in PO{S}_B^{\epsilon }\left(E\right)$，所以 $PO{S}_{B^{\prime }}^{\epsilon }\left(E\right)\subseteq PO{S}_B^{\epsilon }\left(E\right)$ 成立。

定义2.4：对于多标签数据 $\left(X,A,Y\right)$，当且仅当 $B\subseteq A$ 满足以下条件

1) $PO{S}_B^{\epsilon }\left(E\right)=PO{S}_A^{\epsilon }\left(E\right)$，

2) $PO{S}_{B^{\prime }}^{\epsilon }\left(E\right)\ne PO{S}_A^{\epsilon }\left(E\right)$ 其中 $B^{\prime }\subset B$，

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

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

${\gamma }_B^{\epsilon }\left(E\right)=\frac{1}{m}{\displaystyle \underset{j=1}{\overset{m}{\sum }}\frac{\left|{\underset{\_}{R}}_B^{\epsilon }\left(E_j\right)\right|}{\left|X\right|}}$

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

引理2.2：对于任意的 $B^{\prime }\subset B\subset A$，有

${\gamma }_{B^{\prime }}^{\epsilon }\left(E\right)\le {\gamma }_B^{\epsilon }(\; E\; )$

定义2.4：对于多标签数据 $\left(X,A,Y\right)$，对于任意的 $B^{\prime }\subset B$ 如果属性子集 $B\subseteq A$ 满足以下条件：

1) ${\gamma }_B^{\epsilon }\left(E\right)={\gamma }_A^{\epsilon }\left(E\right)$，

2) 对于任意的 $B^{\prime }\subset B$，${\gamma }_{B^{\prime }}^{\epsilon }\left(E\right)\ne {\gamma }_A^{\epsilon }\left(E\right)$，

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

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

定义2.5：给定多标签数据 $\left(X,A,Y\right)$，令属性子集 $B\subseteq A$，则属性 $a_i\in B$ 关于属性子集B的重要性度定义为：

$Si{g}_{in}\left(a_i,B\right)={\gamma }_B^{\epsilon }\left(E\right)-{\gamma }_{\left(B-a_i\right)}^{\epsilon }\left(E\right).$

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

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

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

4. 实验结果

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

表1. 多标签数据集

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

表2. 汉明损失

表3. 覆盖率

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

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

5. 总结

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

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

文章引用

张莹. 基于链分解的多标签分类属性约简
Attribute Reduction for Multi-Label Classification Based on Chain Decomposition[J]. 数据挖掘, 2020, 10(04): 240-246. https://doi.org/10.12677/HJDM.2020.104025

参考文献