基于全局和局部目标点相关性的多标签学习

Multi-Label Learning Based on Global and Local Target Point Correlation

摘要: 传统单标签学习一般都是假设一个示例仅仅与一个标签相关。然而，随着科技的发展和数据形式的日益复杂，现实中的学习问题，往往一个示例同时与多个标签相关，面对这种情况，多标签学习框架被提出。现有的多标签学习大多都是从标签相关性的角度考虑，而目标点的相关性也是一个值得研究的问题。目前目标点相关性算法都是只从全局角度，或者只是从局部角度研究多标签学习问题，这对实际情况并不完全适用。本文提出一种新的同时利用全局目标点相关性和局部目标点相关性的多标签学习算法。首先运用深度神经网络学习得到全局目标点的相关性，再使用k近邻算法将全局目标点划分为局部目标点，进而运用欧式距离度量局部目标点的相关性。最后，将全局目标点相关性和局部目标点相关性结合在一起得到一个最优解。8个多标签数据集上的实验结果验证了本文所提出算法的有效性和可行性。

Abstract: Traditional single-label learning generally assumes that an example is related to only one label. However, with the development of technology and the increasingly complex form of data, an example is often related to multiple labels at the same time in real life scenarios. In the face of this situation, the multi-label learning framework is proposed. Most of the existing multi-label learning is considered from the perspective of label correlation, however, the correlation of target points is also a problem worth studying. At present, the target point correlation algorithms are all from the global perspective, or only from the local perspective to study the multi-label learning problem, which is not completely applicable to the actual situation. In this paper, we propose a new multi-label learning algorithm that utilizes both global object point correlation and local object point correlation. Firstly, the correlation of global target points is obtained by deep neural network, then the global target points are divided into local target points by K-nearest neighbor algorithm, and the correlation of local target points is measured by Euclidean distance. Finally, the global target point correlation and local target point correlation are combined to get an optimal solution. Experimental results on 8 multi-label data sets validate the effectiveness and feasibility of the proposed algorithm.

1. 引言

多标签学习[1]-[3]旨在学习到示例与多个标签间的对应关系。由于其在图像识别、自然语言处理和复杂网络等领域的应用价值，使其受到广泛关注。例如，眼底图像或其他生物信息的多标签学习可以有效提高诊断的准确性[4]-[6]；在线文本的多标签学习可以提高检索的准确率[7]-[10]；而用户档案上的多标签学习可以帮助在社交网络上进行针对个人更加精确的推荐和营销[11]。

为了更好地处理多标签学习问题，越来越多的学者将注意力转移到如何更好地利用目标点相关性这一方面[12] [13]。因为在对数据集进行采集时，我们通常假设全部示例都是“独立同分布”的。现实情况是，数据集中的不同示例，也就是多标签学习中不同的目标点，它们在某些方面可能存在相关性，这种相关性会影响它们在标记空间的差异。例如，在对图像数据进行处理时，如图1所示，图像(a)和图像(b)的风格、轮廓、颜色、季节以及像素点等特征信息可以说明两张图片非常相关，由此可以判断出与这两张图片相关的标签也非常相关，比如“雪纳瑞”和“树叶”。但是观察图像(a)和图像(c)，二者没有很多相关的特征，那么可以说明这两张图片相关的标签很大程度上应该是不一样的。研究对象之间的相关性通常对标记空间的结构产生深远影响。因此，我们在模型训练时，特意引入了目标点之间的相关性因素。这样做可以确保标签的预测受到目标点相关性的制约，从而在一定程度上增强模型的分类性能。通过这种方式，我们不仅能够利用数据之间的内在联系，还能进一步提升模型的预测精度和稳定性。

因此，本文创新地提出了一种在多标签学习过程中能够同时捕捉到目标点的全局相关性和局部相关性的算法(multi-label learning using similarity of global and local target points, ML-GAL)。对于全局目标点相关性，通过深度神经网络学习得到。计算局部目标点相关性时，首先对于给定的一个目标点，利用k近邻算法来求其最近的几个目标点，然后用欧式距离计算出它们的相关性。最后，在不同领域共8个数据集上，对本文算法与其他主流方法进行仿真实验，证明了ML-GAL的性能在解决多标签问题时的有效性。

(a) (b) (c)

Figure 1. A picture used to illustrate the relevance of the image

图1. 用于说明图像相关性的图片

本文的主要贡献包括3个方面：

1) 提出了一种新的全局与局部目标点信息融合算法，更适用于现实中的多标签问题；

2) 利用深度学习方法，通过神经网络的不断迭代，得到多标签问题的最优解；

3) 与4种主流的多标签学习算法进行充分实验仿真，结果证明本文算法的有效性。

2. 相关工作

多标签学习算法可以分为两大类别，一类是“问题转换”策略，另一类是“算法适应”策略。

“问题转换”策略的核心思路在于通过对多标签训练样本进行处理，能够将多标签学习问题转化为其他熟悉并解决的问题，再进行求解。其中，单标签学习问题就属于经过“问题转换”策略解决后的结果。具有代表性的学习算法有binary relevance (BR) [14]和LP [15]算法，其中BR是将多标签学习问题转化为多个二分类问题，即单标签问题。

“算法适应”策略的核心思路在于对传统的监督学习算法进行适应性改造，使其能够直接适应并处理多标签数据的学习内容。具有代表性的学习算法是ML-KNN [12]、基于支持向量机(SVM)的方法[16]、基于决策树的方法[17] [18]和基于AdaBoost的方法[19]。其中，ML-KNN [12]先应用“k近邻”算法来识别与目标样本最相近的k个样本，并获取这些近邻样本的标签信息，随后采用“最大化后验概率”的策略为目标样本选择最符合的标签。

以上述两类算法为基础，许多学者正在考虑如何进一步利用目标点的相关性来提高模型性能。如上文说到的ML-KNN [12]算法中就提出了利用数据集中k近邻的目标点相关性来提高性能。WELL [20]在针对多标签问题中的弱标签建模时，计算了每个标签所对应的目标点的相关性。此外，LSF-CI [21]建模过程中也运用到了示例的相关性矩阵。然而现有的多标签学习大多都只考虑目标点全局相关性或只考虑目标点局部相关性，限制了多标签学习模型的性能。本文提出一种同时利用全局目标点相关性和局部目标点相关性的多标签学习算法，并验证了该算法的有效性。

3. 基于全局和局部目标点相关性算法

在本节中，主要介绍本文提出的同时利用目标点的全局相关性和局部相关性的多标签算法(ML-GAL)。

3.1. 多标签学习

在详细介绍本文的算法之前，先对多标签学习做一个最基础的解释。

在多标签学习中，模型最后预测的结果通常会用+1来表明某个标签与目标示例是相关的，而0或−1则用来表明该标签与目标示例不相关，这种结果也称为逻辑标记值。图2给出了多标签学习的一般流程图，也就是使用了逻辑标记值的训练数据训练的一个多标签模型，先是对未知示例使用训练之后的多标签模型来预测与之匹配的标签，然后使用评价指标作为判断预测值与真实值之间的差距大小的一个衡量标准。多标签学习自被提出以来，“独立同分布”这一假设就一直存在于数据集的采集过程中。实际情况却是数据集中的不同样本之间可能存在相关性，如果在训练模型时考虑到检测目标点之间存在的相关关系，将在一定程度上提高模型的性能。

Figure 2. Multi-label learning flowchart

图2. 多标签学习流程图

3.2. 全局目标点相关性

在已有的多标签学习中，以流形为基础，相关的示例通常处于较小的局部领域，因此标签也十分相关。所以本文利用近邻的样本信息来帮助优化多标签模型。

Figure 3. The Sigmoid function

图3. Sigmoid函数示意图

假设示例集合为X = {x₁,x₂,…,x_n}，其中n表示示例的个数。每个示例x都可以与标签集合L的一个子集相对应。标签集合L = {l₁,l₂,..,l_k}，其中k为标签的总数。根据这些示例的标签可以获得指示向量y，该向量是一个长度为k的二进制向量。若x属于第i个标签，那么y_i = 1，否则y_i = 0。多标签问题就是找到一个函数f: X→{0,1}^k，使f(x) = y。这也是本文算法要完成的任务。

在考虑如何将全局目标点相关性加入到本文模型中时，运用神经网络，通过其强大的学习和处理能力，来更准确地捕捉和解析目标点之间的关联。示例x可以为一个输入向量$\chi ={ℝ}^{\alpha }$ ，其中α为输入向量的维度。神经网络[22] $ℍ$ 为β层的网络，每当信号从一层传递至下一层时，它都会先于特定的权重相乘，随后加上一个偏置值。然后，这些经过调整的信号会经过一个激活函数，以增强网络的能力。为了优化网络性能，网络会利用误差反传算法来逐步调整这些权重和偏置参数，直到达到理想的结果。$h^{\beta }=\sigma \left(W^{\beta }{h}^{\beta -1}+b^{\beta }\right)$ ，其中$W^{\beta }$ 和$b^{\beta }$ 分别为第$\beta$ 层的权重矩阵和偏置矩阵。σ为激活函数，可以为ReLU或者是Sigmoid函数。值得注意的是，对于第一层输入层，$h^0=x$ 。

对于最后一层，$\widehat{y}={\sigma }^{*}\left(W^o{h}^m+b^o\right)$ ，其中W^o为输出层的权重，b^o为输出层的偏置，h^m是最后一个隐藏层的输出。σ^*为Sigmoid函数(如图3)，即${\sigma }^{*}\left(z\right)=\frac{1}{1+e^{-z}}$ 。$\widehat{y}\in {\left[0,1\right]}^k$ 为模型预测的概率向量。(这一段行距设置不是按照要求的16磅，否则公式显示不完全)

为了训练上述构建的神经网络，我们定义一个损失函数来衡量预测值与真实值之间的差异，如下所示：

$L\left(y,\widehat{y}\right)=-{\displaystyle \sum _{i=1}^k\left[y_i\log \left({\widehat{y}}_i\right)+\left(1-y_i\right)\log \left(1-{\widehat{y}}_i\right)\right]}$ (1)

本文在这里使用的是二元交叉熵损失，其中L为所有标签的平均损失。

3.3. 局部目标点相关性

如前所述，从特征空间考虑，当样本的特征相关程度较高时，往往样本的标签集相关程度较高，因此，关注目标点的局部相关性是必要的。虽然已有很多学者在研究过程中利用到了目标点及其临近样本的信息，但是要么根据这些信息直接推断未知样本的标签集合，或者使用由局部信息计算的相关度作为权重。本文考虑从局部目标点相关性出发，用于约束对应标签空间中标签的相关性。

局部目标点相关性是指在一个特定样本的近邻范围内，目标点之间的关联程度。这种相关性通常体现在部分数据中，即相关的目标点往往具有相关的标签。局部目标点相关性和全局目标点相关性的主要区别在于它们的关注范围和影响方式。局部目标点相关性关注特定目标点及其近邻点的关系，有助于提高模型的局部预测精度；而全局目标点相关性关注整个数据集，有助于理解数据的整体结构和发现潜在的模式。在实际应用中，根据数据特点和任务需求，需要综合考虑这两种相关性来优化模型性能。

综上所述，局部目标点相关性和全局目标点相关性在多标签学习中各有优劣，将二者结合可以扬长避短。所以下面介绍本文对于局部目标点相关性的计算以及将其和全局目标点相关性融合的过程。

在计算局部范围内目标点的相关性时，假设一个查询点$q\in X$ ，我们的目标就是在X中找到与q点最近的num个点。首先利用欧式距离，公式为：

$dist\left(x_i,q\right)=\sqrt{{\displaystyle \sum _{j=1}^p{\left(x_{ij}-q_j\right)}^2}}$ (2)

其中x_ij表示向量x_i的第j个分量，q_j表示查询点q的第j个分量。利用k近邻算法求距离q最近的num个点，并把它们保存到集合N^q中，过程如下式所示：

$\begin{array}{c}{N}^q=\arg \underset{S\subset X,\left|S\right|=num}{\min }\arg \underset{S\subset X,\left|S\right|=num}{\min }{\displaystyle \sum _{d_i\in S}dist\left(d_i,q\right)}\end{array}$ (3)

这里$N^q=\left\{N_1^q,N_2^q,\cdots ,N_{num}^q\right\}$ 表示数据集X中与查询点q最近的num个点的集合，$\left|S\right|$ 则为集合S的大小。

此时，最近的num个点中，经过上述神经网络输出的结果应该相近。即如下式所示：

$argmin{\displaystyle \sum _{i=0}^n{\displaystyle \sum _{j=0}^{num}L\left({\widehat{y}}_i,N_j^{{\widehat{y}}_i}\right)}}$ (4)

其中${\widehat{y}}_i$ 表示神经网络$ℍ$ 输入x_i得到的预测值，$N_j^{{\widehat{y}}_i}$ 表示神经网络$ℍ$ 输入第j个x_i的最近邻点得到的预测值。

3.4. 优化目标及优化方法

结合上述(1)~(4)式，在同时考虑了全局目标点相关性及局部目标点相关性后，我们可以把最终需要优化的目标函数整理为下式：

$\begin{array}{c}G\left(y\right)=J\left(y\right)\\ -{\lambda }_1{\displaystyle \sum _{i=1}^k\left[y_i\log \left({\widehat{y}}_i\right)+\left(1-y_i\right)\log \left(1-{\widehat{y}}_i\right)\right]}\\ \begin{array}{c}+{\lambda }_2{\displaystyle \sum _{i=0}^n{\displaystyle \sum _{j=0}^{num}L\left({\widehat{y}}_i,N_j^{{\widehat{y}}_i}\right)}}+{\lambda }_{2}J\left(y\right)\end{array}\end{array}$ (5)

在公式(5)中，λ₁和λ₂是平衡因子。目标函数中的第一项是为了防止过拟合的正则化项。第二项是预测值与真实值之间的全局差距，利用到了全局目标点的相关性。第三项是对不同示例的局部目标点的相关性进行约束。

由于目标函数呈现出非凸和不光滑的特性，它的梯度变化并不稳定。因此，传统的梯度下降方法在这种情况下无法有效工作。本文中，使用了拟牛顿下降法L-BFGS [23]算法。L-BFGS算法以其卓越的性能，成为求解目标函数G(y)的最小值的理想选择。有关L-BFGS算法的信息不再赘述，详情可以参考文献[23]。

4. 实验结果

4.1. 数据集

本文在8种真实的多标签数据集上进行了充分的对比实验，来验证所提算法的有效性。实验中所使用的数据集详细信息如表1所示。

Table 1. Multi-label data set details

表1. 多标签数据集详细信息

名称	样本数	特征数	标签数	标签密度	数据类型
art	5000	462	26	1.64	text
business	5000	438	30	1.59	text
cal500	502	68	174	26.04	music
enron	1702	1001	53	3.38	text
image	2000	294	5	1.24	image
llog	1460	1004	75	1.18	text
medical	978	1449	45	1.25	text
yeast	2417	103	14	4.237	biology

实验中，本文采用了5个广泛使用的多标签评价指标来全面评估各算法的表现。这5个评价指标包括Average precision、Ranking loss、Hamming loss、One error和Coverage。其中Ranking loss、Hamming loss、One error和Coverage [1]这4个指标在评估时，其数值越小，意味着算法的性能越出色。而Average precision这一指标则相反，其数值越大，表明算法的性能越优越。通过这5个指标的综合考量，我们能够更准确地比较各个算法在多标签任务中的性能表现。具体各指标的运算方法可以参考文献[1]。

4.2. 实验设置

本文将ML-GAL的性能与四种算法做对比，分别是BR [14]、ML-LOC [24]、ML-kNN [12]和GLOCAL [25]。其中，BR [14]是问题转换方法中具有代表性的算法之一，它将多标签学习问题转化为多个二分类问题。ML-LOC [24]是利用样本局部相关性的多标签学习方法。ML-kNN [12]算法用到了k近邻信息，GLOCAL [25]算法利用的则是全局和局部的标签相关性。

本文所提出的算法参数λ₁、λ₂的取值范围是$\left\{2^{-5},2^{-4},\cdots ,2^6\right\}$ 。此外，k近邻算法中k的取值范围是[1] [20]。进而利用5折交叉验证的方法，在训练数据上对每个数据集进行算法性能的评估，从而确定每个数据集的最佳参数。

4.3. 实验结果

Table 2. Experimental results under Average precision evaluation index

表2. 在Average precision评价指标下的实验结果

数据集	BR	ML-LOC	ML-kNN	GLOCAL	ML-GAL
arts	0.594 ± 0.006 (4)	0.623 ± 0.004 (2)	0.524 ± 0.002 (5)	0.607 ± 0.003 (3)	0.631 ± 0.006 (1)
business	0.861 ± 0.007 (5)	0.878 ± 0.002 (3)	0.882 ± 0.001 (2)	0.883 ± 0.001 (1)	0.875 ± 0.001 (4)
cal500	0.343 ± 0.017 (5)	0.473 ± 0.003 (4)	0.493 ± 0.002 (3)	0.507 ± 0.001 (2)	0.625 ± 0.003 (1)
enron	0.575 ± 0.006 (5)	0.599 ± 0.003 (4)	0.629 ± 0.002 (3)	0.669 ± 0.002 (2)	0.683 ± 0.007 (1)
image	0.788 ± 0.008 (3)	0.650 ± 0.005 (5)	0.795 ± 0.003 (2)	0.766 ± 0.004 (4)	0.802 ± 0.003 (1)
llog	0.207 ± 0.024 (5)	0.339 ± 0.005 (2)	0.306 ± 0.004 (4)	0.316 ± 0.003 (3)	0.351 ± 0.002 (1)
medical	0.748 ± 0.039 (5)	0.894 ± 0.003 (1)	0.802 ± 0.005 (4)	0.815 ± 0.007 (2)	0.803 ± 0.003 (3)
yeast	0.747 ± 0.010 (4)	0.757 ± 0.003 (3)	0.762 ± 0.002 (1)	0.609 ± 0.001 (5)	0.759 ± 0.001 (2)
AvgRank	4.500	3.000	3.000	2.750	1.750

Table 3. Experimental results under Ranking loss evaluation index

表3. 在Ranking loss评价指标下的实验结果

数据集	BR	ML-LOC	ML-kNN	GLOCAL	ML-GAL
arts	0.201 ± 0.005 (5)	0.152 ± 0.002 (4)	0.148 ± 0.001 (3)	0.137 ± 0.001 (2)	0.134 ± 0.001 (1)
business	0.072 ± 0.005 (5)	0.052 ± 0.002 (4)	0.038 ± 0.001 (2)	0.040 ± 0.001 (3)	0.035 ± 0.006 (1)
cal500	0.233 ± 0.008 (5)	0.225 ± 0.002 (4)	0.183 ± 0.001 (3)	0.178 ± 0.001 (2)	0.165 ± 0.002 (1)
enron	0.194 ± 0.006 (5)	0.157 ± 0.002 (4)	0.147 ± 0.001 (3)	0.114 ± 0.002 (1)	0.147 ± 0.001 (3)
image	0.205 ± 0.017 (4)	0.311 ± 0.005 (5)	0.172 ± 0.002 (1)	0.199 ± 0.003 (3)	0.185 ± 0.005 (2)
llog	0.328 ± 0.030 (5)	0.273 ± 0.010 (4)	0.165 ± 0.001 (1)	0.182 ± 0.004 (3)	0.179 ± 0.001 (2)
medical	0.089 ± 0.021 (5)	0.023 ± 0.001 (2)	0.044 ± 0.002 (3)	0.058 ± 0.003 (4)	0.017 ± 0.002 (1)
yeast	0.183 ± 0.006 (3)	0.186 ± 0.003 (4)	0.169 ± 0.001 (2)	0.349 ± 0.002 (5)	0.132 ± 0.003 (1)
AvgRank	4.625	3.875	2.250	2.875	1.500

实验结果是针对各个算法在8个数据集上实施了10次5折交叉验证，所得实验结果不仅展示了均值，还涵盖了方差。表2和表3中总结了5种算法在Average precision和Ranking loss两种评价指标下的实验结果。其中粗体标出的是在5种算法中的最优结果。

实验结果表明，本文提出的ML-GAL算法在提升多标签学习性能方面是有效果的。在以上16组(2评价指标 × 8数据集)对比实验结果中，ML-GAL算法共有10次排在第一，3次第二，2次第三以及1次第四。并无排在最后的情况。

Table 4. Friedman statistic F_F and critical value

表4. Friedman统计值F_F及临界值

度量指标	FF	临界值
Hamming loss	5.0594	2.4004
One error	19.2479
Coverage	6.1513

本文采用了Friedman检验对5种不同算法的性能进行了显著性检验，并在表4中列出了各种度量指标的Friedman统计值F_F以及在0.05显著水平下的临界值。经过检验，我们发现在这三个指标上，可以成功推翻对比算法间性能无显著差别的假设。为了更深入地验证本文算法是否显著优于其他四种算法，继续采用了0.05显著水平下的Bonferroni-Dunn检验。在实验中，将ML-GAL作为控制算法，利用临界值域(Critical Difference, CD)来量化ML-GAL算法与其他算法在平均排序上的差异。如果其他算法的评价排序值与ML-GAL差距超过CD值，则表明ML-GAL算法的性能与其他算法存在显著差异。

图4的CD图提供了直观的视觉比较，图中水平轴表示了5种算法的平均排序值，排序值越接近右侧，说明算法排名越靠前。在每个CD图中，如果某个算法与ML-GAL的差距小于一个CD值，我们会用一条加粗黑线来将其相连。否则，则意味着这两种算法在多标签学习的性能上存在显著差异。

(a) Hamming loss (b) One error

(c) Coverage

Figure 4. Results of comparison between ML-GAL and other comparison algorithms under Bonferroni-Dunn test

图4. ML-GAL与其他四个算法在Bonferroni-Dunn检验下的比较结果

通过分析图4可以得到以下结论：

(1) ML-GAL算法在这三种评价指标上的表现均最为出色；

(2) ML-GAL算法在这三种评价指标上的性能都显著优于BR [14]；

(3) ML-GAL在One error评价指标下的数值表现尤为突出。与GLOCAL [25]相比，两者在Hammingloss和Coverage两个指标下的表现相当接近，但在Oneerror评价指标下的表现相差较多。与ML-Knn [12]相比，两者在Oneerror评价指标下相差不多，但在Hammingloss和Coverage两个指标的区别明显。

5. 结论

本文提出了一种新的多标签学习算法，在解决多标签问题过程中同时考虑到了全局和局部目标点相关性。详细流程是先考虑整个训练数据中所包含的全局检测目标点的相关性，并利用神经网络来学习相关性。然后在一个簇中选定查询点，利用欧式距离计算局部目标点的相关性。将两种目标点相关性整合到一起来提升多标签学习模型的性能。最后在多种类型的数据集上和其他算法进行对比实验。实验结果表明了ML-GAL算法在多标签学习上的有效性和合理性。