基于K-means的GLOCAL改进算法

王一宾，黄志强，程玉胜

（1.安庆师范大学计算机与信息学院，安徽安庆246133 2.安徽省高校智能感知与计算重点实验室，安徽安庆246133)

近年来，多标签学习[1-2]得到了广泛的研究，不同于传统单标签学习算法，单个示例仅和单个标签相关联；在多标签学习中每个示例则与多个标签相关联，这种学习框架也更加符合现实世界对象的多义性。但由于多标签空间具有很高的复杂度，标签相关性问题也是目前多标签学习的一大挑战。对于多标签学习中标签之间存在的相关性问题，根据标签之间的关联程度，可以将其分为3类[3]：一阶算法、二阶算法和高阶算法。对于一阶算法，不考虑其标签相关性，直接将多标签问题转化为多个独立的二分类问题。代表算法有二元关联（BR）算法[4]，该算法为每个标签单独训练一个分类器。对于二阶算法，考虑到成对标签之间的相关关系，代表算法有校准标签排序（CLR）[5]，该算法将多标签学习转化为成对的标签排序问题。在高阶算法中，考虑所有其他标签对每个标签的影响，链式分类器（CC）[6]将多标签学习问题转化为一个二元分类问题链，以真实标签编码为特征。

考虑所有标签关联的另一种方法是通过学习一个潜在的标签空间来捕获高级标签语义，该方法通常是利用标签矩阵的低秩分解[7]得到潜在标签。Jing等[8]使用字典学习来获得嵌入标签。Du等[9]引入基于核范数的误差模型描述图像中遮挡和缺损部分，然后将错误图像与训练样本结合起来构建字典，从而重建图像。Yeh等[10]也提出了一种深度学习方法来学习联合特征和标签嵌入。这些方法与典型相关分析（CCA）[11]密切相关，它通过学习潜在子空间，以便使用相应的标签表示示例。以往的研究大多放在全局标签相关性上，然而有时标签关联可能只由局部数据子集共享。为了解决这个问题，Huang使用局部标签相关性算法（MLLOC）[12]，通过嵌入代码来扩展每个示例的特征表示，该代码将示例标签对局部标签相关性的影响进行了编码。

在目前的多标签学习中，需要对样本进行人工标记，人工标记有时会忽略他们不了解或不感兴趣的标签，或者遵循某种算法来降低标记成本，导致训练集中某些标签缺失。为解决标签缺失问题，Cheng等提出NeLC-NLS[13]算法，利用近邻空间信息与正负标签间相关性构建出非平衡化标签补全矩阵，从而提升近邻标签空间的质量。Xu[14]提出利用边信息进行矩阵补全（MAXIDE），该方法基于快速低秩矩阵的完备性，利用了标签相关性，而同样依赖于低秩结构的低秩经验风险最小化的多标签学习（LEML）[15]算法则没有明确使用标签关联性。多标签分类（ML-LRC）[16]通过在标签关联矩阵上采用低秩结构来获取全局标签关联，并通过引入补充标签矩阵来解决标签缺失的问题，它只关注全局标签相关性，而不考虑局部标签相关性。显然，同时学习全局和局部标签相关性更可取，Zhu等提出具有全局与局部标签相关性的多标签算法（GLOCAL）[17]，该方法通过学习潜在标签和优化标签流行正则项，同时利用全局标签和局部标签的相关性，可以补全缺失标签和处理全标签问题。

基于以上分析，本文主要对GLOCAL算法改进，在多标签学习中由于标签是相关的，标签矩阵通常被认定是低秩矩阵[7,10]。GLOCAL算法在学习潜在标签以及原始标签与潜在标签的关联性时，在选取适当的维数后，通过低秩分解获得的初始化的低秩矩阵是随机获取的，导致该算法结果不稳定，所以本文在分解标签矩阵构造两个小矩阵时，利用K-means聚类算法[18]获得聚类中心集合，该集合即为其中一个矩阵，在确定其中一个分解矩阵后，可以学习到另一矩阵。

1 GLOCAL算法及其改进算法

1.1 K-means算法

K-means 算法将给定的数据集X=[x1,x2,…,xn]划分成K个类别{C1,C2,…,Ck}，K-means 聚类算法思想：从数据集X中随机选择K个对象，分别作为K个类别的初始聚类中心Cj(j=1,2,…,k)；分别计算数据集中每个元素与所选聚类中心的欧式距离，根据最近邻原则，将元素划分到相应的类别中；计算每个类别中元素的平均值，将其作为新的聚类中心；重复以上步骤，直至新的聚类中心不再变化。

欧式距离是在欧式空间中两个样本之间的直线距离。Xi与Xj在m维空间中的欧式距离为

1.2 GLOCAL算法

1.2.1 GLOCAL基本模型

由于标签在多标签学习中是相关的，标签矩阵通常被认定为低秩矩阵。令{-1,1}l×n是正确标签矩阵，其中每个是第i个示例的标签向量，将͂分解为两个低秩矩阵

其中Vk×n表示潜在标签，Ul×k表示原始标签与潜在标签怎样相关。矩阵U和V可以通过来获得。令观测到的标签矩阵为Y=[y1,y2,…,yn]∈{-1,0,1}l×n，Ω是标签不为零的元素的位置集合。对观测到的矩阵Y最小化重构误差否则为0。当所有元素都能被观测到时，可以看作特殊情况，则。

通过学习矩阵W∈ℝd×k将示例映射到潜在标签，并且通过最小化平方损耗来获得W，其中X =[x1,x2,…,xn]∈ℝd×n是包含了所有示例的矩阵。将对示例x的预测标签写作其中f(x)=UWT。令其中fj(x)是x的第j个预测标签，将所有x∈X的f(x)连在一起则是

结合低秩矩阵分解的重构误差最小化和从示例到潜在标签的线性映射的平方损失最小化，得到基本GLOCAL模型的优化问题：

其中R(U,V,W)是正则化参数，λ，λ2为平衡参数。

1.2.2 全局和局部相关性

利用标签相关性是多标签学习的关键。我们利用标签关联来规范模型。由于全局和局部标签关联可能共存，因此引入标签流形正则化项，以便将两者结合起来。全局流形正则化的基本思想是由示例级流形正则化[19]优化获得的。具体来说，两个标签的正相关程度越高，对应的分类器输出结果越接近，反之亦然。也就是说，正相关标签会促使对应的分类器输出结果相似，而负相关标签会将使对应的输出结果不相似。

对所有n个示例的预测都存储在l×n矩阵F0中，其第i行fi,:包含对第i个标签的预测。如果第i个标签和第j个标签的正相关程度越高，则fi,:应该与fj,:更相似，反之亦然。与示例级流形正则化项[20]类似，标签流形正则化可以定义为

其中S0为l×l全局标签相关矩阵。如果标签i和j正相关，则[S0]i,j也是正的。若将（3）式最小化，将随之变小。设D0是对角S01的对角矩阵，其中1是元素全为1的向量。（3）式中的流形正则化项可以等价地写成是l×l维S0的拉普拉斯矩阵。

由于标签相关性在不同的局部区域可能有所不同，因此引入局部流形正则化。假设数据集X被划分为g组{X1,X2,…,Xg}，其中Xm∈ ℝd×nm具有nm个示例。设Ym为Y中对应Xm的标签子矩阵，Sm∈ ℝl×l为组m的局部标签相关矩阵。与全局标签相关性相似，我们期望分类器输出为正（负）标签相似（不相似），最小化其中Lm为Sm的拉普拉斯矩阵，Fm=UWTX为组m分类器输出矩阵，加入全局与局部的标签流行正则化式后，（2）式优化得

其中λ，λ2，λ3，λ4是平衡参数。

标签流行正则化可以利用全局和局部的相关性是因为全局标签相关性用L0编码，局部标签相关性用Lm编码。一个大的局部组标签相关性比全局标签相关性的作用更大。当全局标签相关矩阵是局部标签相关矩阵的线性组合时，相应的拉普拉斯矩阵也是具有相同组合系数的线性组合。（4）式可以写作

1.2.3 标签相关性

标签流行正则化的成功取决于一个好的标签相关性矩阵，在多标签学习中，通常利用余弦距离计算标签之间的相关系数[22]。然而，一些训练集中的标签只有少数正示例，导致估计值会含噪声。当标签缺失时，观察到的标签分布与真实的分布有很大的不同，这个估计值会引起误差。在本算法中，直接学习拉普拉斯矩阵，而不用去指定相关度量或标签相关矩阵。由于拉普拉斯矩阵是对称正定的，因此，对于m∈{1,2,…,g}，将Lm分解为其中Zm∈ ℝl×k。将学习拉普拉斯矩阵转换为学习Z={Z1,Z2,…,Zg}。为了避免平凡解Zm=0，使每个对角线元素为1，同时获得了Lm的归一化拉普拉斯矩阵[23]。

令J=[Jij]为指标矩阵，当(i,j)∈Ω时Jij=1，否则为0。可以重写为Hadamard 乘积J∘(Y-UV)，结合拉普拉斯矩阵的分解和Zm的对角约束，得到最优化问题：

1.2.4 交替最小化学习

（6）式的问题能通过迭代的方法调整变量以找到合适的解决方案。在每次迭代中，用梯度下降来更新{Z,U,V,W}中的一个变量，同时固定其他变量，将整个优化问题简化为几个简单的子问题。利用MANOPT工具箱在欧几里得空间上用线性搜索实现梯度下降以更新Z、V、U、W的流行[17]。

1.3 GLOCAL的改进算法

GLOCAL算法可以有效处理多标签学习，但该算法在分解标签矩阵时随机获取两个低秩矩阵。因此本文利用在标签矩阵聚类后获得的聚类中心矩阵代替GLOCAL算法中的一个初始化低秩矩阵，K值则为另一低秩矩阵的维数来改进GLOCAL算法，得到K-GLOCAL算法，算法描述如下。

（1）在标签空间Yl×n上使用K-means聚类，将Y分为K份，每一份的聚类中心用Cj(j=1,2,…,k)来表示；（2）将聚类中心Cj(j=1,2,…,k)放置在同一矩阵Cl×k中；（3）初始化U、V、W、Z，令U=C；（4）重复；（5）或者m=1,2,…,g/*学习标签相关性*/；（6）固定V、U、W，通过（7）式[17]更新Zm，End for/*学习潜在标签*/；（7）固定U、W、Z，通过（8）式[17]更新V；（8）固定V、W、Z，通过（9）式[17]更新U；（9）固定U、V、Z，通过（10）式[17]更新W；直到收敛。

2 实验设计

为了说明本文算法的优势，选取来自Yahoo Web Pages(http：//www.kecl.ntt.co.jp/as/members/ueda/yahoo.tar)和Mulan(http：//mulan.sourceforge.net/datasets-mlc.html)的13个多标签数据集。数据集包含文本、图片等信息，具体描述如表1所示。由于原始数据标签不含损失，本文采取随机缺损的方式获得数据集。在后续实验结果中，每个数据集使用前3个字母表示。

表1 多标签数据集的详细描述

实验代码均在Matlab2016a中运行。硬件环境为Intel®Core™i5-4200M 2.50 GHz CPU，8 G内存；操作系统为Windows7。本文选取了4 种评价准则[2]，即平均精度(AP)、接受者操作特性曲线下平均面积(AUC)、覆盖率(CV)、和排序损失(RL)来综合评价多标签学习算法的性能。为方便，AP↑、AUC↑、CV↓和RL↓中↑表示指标数值越高越好，↓表示指标数值越低越好。

3 实验结果与分析

在实验过程中，对原始标签聚类，判断聚类个数K时，本文通过算法迭代，对比实验结果来获取K值，本文K值为22。ρ表示已知标签数占全标签数的百分比，ρ=100表示全标签。为了验证算法的有效性，采用测试集实验。表2至表5给出了本文算法和其他4种算法在13个数据集上的实验结果，数字加粗则表明在对比的算法中结果最好。其中算法一至算法四依次代表MAXIDE、LEML、ML-LRC、GLOCAL，算法五则是本文算法K-GLOCAL。

表2 对测试集缺损标签数据恢复结果上的平均精度测试AP(↑)

表3 对测试集缺损标签数据恢复结果上的接受者操作特性曲线下平均面积测试AUC(↑)

表4 对测试集缺损标签数据恢复结果上的覆盖率测试CV(↓)

表5 对测试集缺损标签数据恢复结果上的排序损失测试RL(↓)

实验结果说明：从表2至表5中可以看出，K-GLOCAL算法在在排序损失、平均精度以及覆盖率指标下有较小优势；在接受者操作特性曲线下平均面积指标下，多数数据集上的实验结果占优；当ρ=30时，本文算法总体占优。下面通过统计假设检验说明本文算法的合理性。

统计假设检验：为了对比K-GLOCAL算法与其他算法，采用5%的Nemenyi[24]检验，计算每个算法两两之间的平均序值的差值，如果差值大于临界差值CD（Critical Difference）则说明两个算法有显著差异，如果小于CD则说明两个算法的性能没有显著差别。本文则分别对表2至表5中已知30%标签的数据集和已知70%标签的数据集实验结果进行检验。

图1 为已知30%标签的数据集实验结果，若两个算法之间没有显著差别则用实线连接，反之则不连。如图1(a)所示，K-GLOCAL 与ML-LRC 无显著差别，ML-LRC 与LEML、GLOCAL，LEML 与GLOCAL、MLLOC无显著差别。如图1(b)所示，K-GLOCAL与ML-LRC无显著差别，ML-LRC与GLOCAL、LEML 无显著差别，GLOCAL 与LEML、MMLOC 无显著差别。如图1(c)所示，K-GLOCAL 与 MMLOC无显著差别，MMLOC 与 ML-LRC、LEML、GLOCAL 无显著差别。如图1(d)所示，K-GLOCAL 与 MLLRC无显著差别，ML-LRC与LEML、GLOCAL、MLLOC无显著差别。

图1 算法综合性能比较

图2为已知70%标签的数据集实验结果，如图2（a）所示，ML-LRC与GLOCAL、K-GLOCAL无显著差别，K-GLOCAL与LEML无显著差别，LEML与MMLOC无显著差别。如图2（b）所示，ML-LRC与KGLOCAL、GLOCAL 无显著差别，K-GLOCAL 与 GLOCAL、LEML 无显著差别，LEML 与 MMLOC 无显著差别。如图2（c）所示，K-GLOCAL与GLOCAL、ML-LRC无显著差别，GLOCAL与ML-LRC、LEML、MMLOC无显著差别。如图2（d）所示，K-GLOCAL与ML-LRC、GLOCAL无显著差别，ML-LRC与GLOCAL、LEML无显著差别，LEML与MMLOC无显著差别。

图2 算法综合性能比较

4 总 结

本文结合K-means聚类算法，对GLOCAL算法改进。针对其初始化潜在标签与原始标签的关联阵问题，利用聚类中心矩阵代替初始化低秩矩阵，更能表示潜在标签与原始标签的关联性，聚类个数K则代替在标签矩阵维数k，有利于提高算法的精度。实验结果表明本文的算法具有一定的优势。但本文算法仍存在问题，即只考虑在标签空间做出改进，没有着重考虑特征与标签之间的关联性。因此，如何利用特征与标签之间的关联性对标签进行补全是接下来的研究内容。