王一賓，黃志強，程玉勝

（1.安慶師范大學計算機與信息學院，安徽安慶246133 2.安徽省高校智能感知與計算重點實驗室，安徽安慶246133)

近年來，多標簽學習[1-2]得到了廣泛的研究，不同于傳統(tǒng)單標簽學習算法，單個示例僅和單個標簽相關聯(lián)；在多標簽學習中每個示例則與多個標簽相關聯(lián)，這種學習框架也更加符合現(xiàn)實世界對象的多義性。但由于多標簽空間具有很高的復雜度，標簽相關性問題也是目前多標簽學習的一大挑戰(zhàn)。對于多標簽學習中標簽之間存在的相關性問題，根據(jù)標簽之間的關聯(lián)程度，可以將其分為3類[3]：一階算法、二階算法和高階算法。對于一階算法，不考慮其標簽相關性，直接將多標簽問題轉化為多個獨立的二分類問題。代表算法有二元關聯(lián)（BR）算法[4]，該算法為每個標簽單獨訓練一個分類器。對于二階算法，考慮到成對標簽之間的相關關系，代表算法有校準標簽排序（CLR）[5]，該算法將多標簽學習轉化為成對的標簽排序問題。在高階算法中，考慮所有其他標簽對每個標簽的影響，鏈式分類器（CC）[6]將多標簽學習問題轉化為一個二元分類問題鏈，以真實標簽編碼為特征。

考慮所有標簽關聯(lián)的另一種方法是通過學習一個潛在的標簽空間來捕獲高級標簽語義，該方法通常是利用標簽矩陣的低秩分解[7]得到潛在標簽。Jing等[8]使用字典學習來獲得嵌入標簽。Du等[9]引入基于核范數(shù)的誤差模型描述圖像中遮擋和缺損部分，然后將錯誤圖像與訓練樣本結合起來構建字典，從而重建圖像。Yeh等[10]也提出了一種深度學習方法來學習聯(lián)合特征和標簽嵌入。這些方法與典型相關分析（CCA）[11]密切相關，它通過學習潛在子空間，以便使用相應的標簽表示示例。以往的研究大多放在全局標簽相關性上，然而有時標簽關聯(lián)可能只由局部數(shù)據(jù)子集共享。為了解決這個問題，Huang使用局部標簽相關性算法（MLLOC）[12]，通過嵌入代碼來擴展每個示例的特征表示，該代碼將示例標簽對局部標簽相關性的影響進行了編碼。

在目前的多標簽學習中，需要對樣本進行人工標記，人工標記有時會忽略他們不了解或不感興趣的標簽，或者遵循某種算法來降低標記成本，導致訓練集中某些標簽缺失。為解決標簽缺失問題，Cheng等提出NeLC-NLS[13]算法，利用近鄰空間信息與正負標簽間相關性構建出非平衡化標簽補全矩陣，從而提升近鄰標簽空間的質量。Xu[14]提出利用邊信息進行矩陣補全（MAXIDE），該方法基于快速低秩矩陣的完備性，利用了標簽相關性，而同樣依賴于低秩結構的低秩經驗風險最小化的多標簽學習（LEML）[15]算法則沒有明確使用標簽關聯(lián)性。多標簽分類（ML-LRC）[16]通過在標簽關聯(lián)矩陣上采用低秩結構來獲取全局標簽關聯(lián)，并通過引入補充標簽矩陣來解決標簽缺失的問題，它只關注全局標簽相關性，而不考慮局部標簽相關性。顯然，同時學習全局和局部標簽相關性更可取，Zhu等提出具有全局與局部標簽相關性的多標簽算法（GLOCAL）[17]，該方法通過學習潛在標簽和優(yōu)化標簽流行正則項，同時利用全局標簽和局部標簽的相關性，可以補全缺失標簽和處理全標簽問題。

基于以上分析，本文主要對GLOCAL算法改進，在多標簽學習中由于標簽是相關的，標簽矩陣通常被認定是低秩矩陣[7,10]。GLOCAL算法在學習潛在標簽以及原始標簽與潛在標簽的關聯(lián)性時，在選取適當?shù)木S數(shù)后，通過低秩分解獲得的初始化的低秩矩陣是隨機獲取的，導致該算法結果不穩(wěn)定，所以本文在分解標簽矩陣構造兩個小矩陣時，利用K-means聚類算法[18]獲得聚類中心集合，該集合即為其中一個矩陣，在確定其中一個分解矩陣后，可以學習到另一矩陣。

1 GLOCAL算法及其改進算法

1.1 K-means算法

K-means 算法將給定的數(shù)據(jù)集X=[x1,x2,…,xn]劃分成K個類別{C1,C2,…,Ck}，K-means 聚類算法思想：從數(shù)據(jù)集X中隨機選擇K個對象，分別作為K個類別的初始聚類中心Cj(j=1,2,…,k)；分別計算數(shù)據(jù)集中每個元素與所選聚類中心的歐式距離，根據(jù)最近鄰原則，將元素劃分到相應的類別中；計算每個類別中元素的平均值，將其作為新的聚類中心；重復以上步驟，直至新的聚類中心不再變化。

歐式距離是在歐式空間中兩個樣本之間的直線距離。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模型的優(yōu)化問題：

其中R(U,V,W)是正則化參數(shù)，λ，λ2為平衡參數(shù)。

1.2.2 全局和局部相關性

利用標簽相關性是多標簽學習的關鍵。我們利用標簽關聯(lián)來規(guī)范模型。由于全局和局部標簽關聯(lián)可能共存，因此引入標簽流形正則化項，以便將兩者結合起來。全局流形正則化的基本思想是由示例級流形正則化[19]優(yōu)化獲得的。具體來說，兩個標簽的正相關程度越高，對應的分類器輸出結果越接近，反之亦然。也就是說，正相關標簽會促使對應的分類器輸出結果相似，而負相關標簽會將使對應的輸出結果不相似。

對所有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的拉普拉斯矩陣。

由于標簽相關性在不同的局部區(qū)域可能有所不同，因此引入局部流形正則化。假設數(shù)據(jù)集X被劃分為g組{X1,X2,…,Xg}，其中Xm∈ ?d×nm具有nm個示例。設Ym為Y中對應Xm的標簽子矩陣，Sm∈ ?l×l為組m的局部標簽相關矩陣。與全局標簽相關性相似，我們期望分類器輸出為正（負）標簽相似（不相似），最小化其中Lm為Sm的拉普拉斯矩陣，F(xiàn)m=UWTX為組m分類器輸出矩陣，加入全局與局部的標簽流行正則化式后，（2）式優(yōu)化得

其中λ，λ2，λ3，λ4是平衡參數(shù)。

標簽流行正則化可以利用全局和局部的相關性是因為全局標簽相關性用L0編碼，局部標簽相關性用Lm編碼。一個大的局部組標簽相關性比全局標簽相關性的作用更大。當全局標簽相關矩陣是局部標簽相關矩陣的線性組合時，相應的拉普拉斯矩陣也是具有相同組合系數(shù)的線性組合。（4）式可以寫作

1.2.3 標簽相關性

標簽流行正則化的成功取決于一個好的標簽相關性矩陣，在多標簽學習中，通常利用余弦距離計算標簽之間的相關系數(shù)[22]。然而，一些訓練集中的標簽只有少數(shù)正示例，導致估計值會含噪聲。當標簽缺失時，觀察到的標簽分布與真實的分布有很大的不同，這個估計值會引起誤差。在本算法中，直接學習拉普拉斯矩陣，而不用去指定相關度量或標簽相關矩陣。由于拉普拉斯矩陣是對稱正定的，因此，對于m∈{1,2,…,g}，將Lm分解為其中Zm∈ ?l×k。將學習拉普拉斯矩陣轉換為學習Z={Z1,Z2,…,Zg}。為了避免平凡解Zm=0，使每個對角線元素為1，同時獲得了Lm的歸一化拉普拉斯矩陣[23]。

令J=[Jij]為指標矩陣，當(i,j)∈Ω時Jij=1，否則為0?？梢灾貙憺镠adamard 乘積J°(Y-UV)，結合拉普拉斯矩陣的分解和Zm的對角約束，得到最優(yōu)化問題：

1.2.4 交替最小化學習

（6）式的問題能通過迭代的方法調整變量以找到合適的解決方案。在每次迭代中，用梯度下降來更新{Z,U,V,W}中的一個變量，同時固定其他變量，將整個優(yōu)化問題簡化為幾個簡單的子問題。利用MANOPT工具箱在歐幾里得空間上用線性搜索實現(xiàn)梯度下降以更新Z、V、U、W的流行[17]。

1.3 GLOCAL的改進算法

GLOCAL算法可以有效處理多標簽學習，但該算法在分解標簽矩陣時隨機獲取兩個低秩矩陣。因此本文利用在標簽矩陣聚類后獲得的聚類中心矩陣代替GLOCAL算法中的一個初始化低秩矩陣，K值則為另一低秩矩陣的維數(shù)來改進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 實驗設計

為了說明本文算法的優(yōu)勢，選取來自Yahoo Web Pages(http：//www.kecl.ntt.co.jp/as/members/ueda/yahoo.tar)和Mulan(http：//mulan.sourceforge.net/datasets-mlc.html)的13個多標簽數(shù)據(jù)集。數(shù)據(jù)集包含文本、圖片等信息，具體描述如表1所示。由于原始數(shù)據(jù)標簽不含損失，本文采取隨機缺損的方式獲得數(shù)據(jù)集。在后續(xù)實驗結果中，每個數(shù)據(jù)集使用前3個字母表示。

表1 多標簽數(shù)據(jù)集的詳細描述

實驗代碼均在Matlab2016a中運行。硬件環(huán)境為Intel?Core?i5-4200M 2.50 GHz CPU，8 G內存；操作系統(tǒng)為Windows7。本文選取了4 種評價準則[2]，即平均精度(AP)、接受者操作特性曲線下平均面積(AUC)、覆蓋率(CV)、和排序損失(RL)來綜合評價多標簽學習算法的性能。為方便，AP↑、AUC↑、CV↓和RL↓中↑表示指標數(shù)值越高越好，↓表示指標數(shù)值越低越好。

3 實驗結果與分析

在實驗過程中，對原始標簽聚類，判斷聚類個數(shù)K時，本文通過算法迭代，對比實驗結果來獲取K值，本文K值為22。ρ表示已知標簽數(shù)占全標簽數(shù)的百分比，ρ=100表示全標簽。為了驗證算法的有效性，采用測試集實驗。表2至表5給出了本文算法和其他4種算法在13個數(shù)據(jù)集上的實驗結果，數(shù)字加粗則表明在對比的算法中結果最好。其中算法一至算法四依次代表MAXIDE、LEML、ML-LRC、GLOCAL，算法五則是本文算法K-GLOCAL。

表2 對測試集缺損標簽數(shù)據(jù)恢復結果上的平均精度測試AP(↑)

表3 對測試集缺損標簽數(shù)據(jù)恢復結果上的接受者操作特性曲線下平均面積測試AUC(↑)

表4 對測試集缺損標簽數(shù)據(jù)恢復結果上的覆蓋率測試CV(↓)

表5 對測試集缺損標簽數(shù)據(jù)恢復結果上的排序損失測試RL(↓)

實驗結果說明：從表2至表5中可以看出，K-GLOCAL算法在在排序損失、平均精度以及覆蓋率指標下有較小優(yōu)勢；在接受者操作特性曲線下平均面積指標下，多數(shù)數(shù)據(jù)集上的實驗結果占優(yōu)；當ρ=30時，本文算法總體占優(yōu)。下面通過統(tǒng)計假設檢驗說明本文算法的合理性。

統(tǒng)計假設檢驗：為了對比K-GLOCAL算法與其他算法，采用5%的Nemenyi[24]檢驗，計算每個算法兩兩之間的平均序值的差值，如果差值大于臨界差值CD（Critical Difference）則說明兩個算法有顯著差異，如果小于CD則說明兩個算法的性能沒有顯著差別。本文則分別對表2至表5中已知30%標簽的數(shù)據(jù)集和已知70%標簽的數(shù)據(jù)集實驗結果進行檢驗。

圖1 為已知30%標簽的數(shù)據(jù)集實驗結果，若兩個算法之間沒有顯著差別則用實線連接，反之則不連。如圖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%標簽的數(shù)據(jù)集實驗結果，如圖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算法改進。針對其初始化潛在標簽與原始標簽的關聯(lián)陣問題，利用聚類中心矩陣代替初始化低秩矩陣，更能表示潛在標簽與原始標簽的關聯(lián)性，聚類個數(shù)K則代替在標簽矩陣維數(shù)k，有利于提高算法的精度。實驗結果表明本文的算法具有一定的優(yōu)勢。但本文算法仍存在問題，即只考慮在標簽空間做出改進，沒有著重考慮特征與標簽之間的關聯(lián)性。因此，如何利用特征與標簽之間的關聯(lián)性對標簽進行補全是接下來的研究內容。