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

Attribute Reduction for Multi-Label Classification Based on 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=\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次独立实验的平均值作为实验的最终结果。

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算法又只适用于小型数据集，存在计算复杂度高的问题。对于标签之间的关系本文主要从标签出现次数上进行考虑其相关性，但是标签之间的固有联系是一个比较复杂的问题。未来，我们将继续优化模型，寻求更好的排序方法。同时将更深入地研究如何解决标签间相关性问题。