基于K-means的GLOCAL改進(jìn)算法

王一賓，黃志強(qiáng)，程玉勝

（1.安慶師范大學(xué)計(jì)算機(jī)與信息學(xué)院，安徽安慶246133 2.安徽省高校智能感知與計(jì)算重點(diǎn)實(shí)驗(yàn)室，安徽安慶246133)

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

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

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

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

1 GLOCAL算法及其改進(jìn)算法

1.1 K-means算法

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

歐式距離是在歐式空間中兩個(gè)樣本之間的直線距離。Xi與Xj在m維空間中的歐式距離為

1.2 GLOCAL算法

1.2.1 GLOCAL基本模型

由于標(biāo)簽在多標(biāo)簽學(xué)習(xí)中是相關(guān)的，標(biāo)簽矩陣通常被認(rèn)定為低秩矩陣。令{-1,1}l×n是正確標(biāo)簽矩陣，其中每個(gè)是第i個(gè)示例的標(biāo)簽向量，將?分解為兩個(gè)低秩矩陣

其中Vk×n表示潛在標(biāo)簽，Ul×k表示原始標(biāo)簽與潛在標(biāo)簽怎樣相關(guān)。矩陣U和V可以通過來獲得。令觀測(cè)到的標(biāo)簽矩陣為Y=[y1,y2,…,yn]∈{-1,0,1}l×n，Ω是標(biāo)簽不為零的元素的位置集合。對(duì)觀測(cè)到的矩陣Y最小化重構(gòu)誤差否則為0。當(dāng)所有元素都能被觀測(cè)到時(shí)，可以看作特殊情況，則。

通過學(xué)習(xí)矩陣W∈?d×k將示例映射到潛在標(biāo)簽，并且通過最小化平方損耗來獲得W，其中X =[x1,x2,…,xn]∈?d×n是包含了所有示例的矩陣。將對(duì)示例x的預(yù)測(cè)標(biāo)簽寫作其中f(x)=UWT。令其中fj(x)是x的第j個(gè)預(yù)測(cè)標(biāo)簽，將所有x∈X的f(x)連在一起則是

結(jié)合低秩矩陣分解的重構(gòu)誤差最小化和從示例到潛在標(biāo)簽的線性映射的平方損失最小化，得到基本GLOCAL模型的優(yōu)化問題：

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

1.2.2 全局和局部相關(guān)性

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

對(duì)所有n個(gè)示例的預(yù)測(cè)都存儲(chǔ)在l×n矩陣F0中，其第i行fi,:包含對(duì)第i個(gè)標(biāo)簽的預(yù)測(cè)。如果第i個(gè)標(biāo)簽和第j個(gè)標(biāo)簽的正相關(guān)程度越高，則fi,:應(yīng)該與fj,:更相似，反之亦然。與示例級(jí)流形正則化項(xiàng)[20]類似，標(biāo)簽流形正則化可以定義為

其中S0為l×l全局標(biāo)簽相關(guān)矩陣。如果標(biāo)簽i和j正相關(guān)，則[S0]i,j也是正的。若將（3）式最小化，將隨之變小。設(shè)D0是對(duì)角S01的對(duì)角矩陣，其中1是元素全為1的向量。（3）式中的流形正則化項(xiàng)可以等價(jià)地寫成是l×l維S0的拉普拉斯矩陣。

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

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

標(biāo)簽流行正則化可以利用全局和局部的相關(guān)性是因?yàn)槿謽?biāo)簽相關(guān)性用L0編碼，局部標(biāo)簽相關(guān)性用Lm編碼。一個(gè)大的局部組標(biāo)簽相關(guān)性比全局標(biāo)簽相關(guān)性的作用更大。當(dāng)全局標(biāo)簽相關(guān)矩陣是局部標(biāo)簽相關(guān)矩陣的線性組合時(shí)，相應(yīng)的拉普拉斯矩陣也是具有相同組合系數(shù)的線性組合。（4）式可以寫作

1.2.3 標(biāo)簽相關(guān)性

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

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

1.2.4 交替最小化學(xué)習(xí)

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

1.3 GLOCAL的改進(jìn)算法

GLOCAL算法可以有效處理多標(biāo)簽學(xué)習(xí)，但該算法在分解標(biāo)簽矩陣時(shí)隨機(jī)獲取兩個(gè)低秩矩陣。因此本文利用在標(biāo)簽矩陣聚類后獲得的聚類中心矩陣代替GLOCAL算法中的一個(gè)初始化低秩矩陣，K值則為另一低秩矩陣的維數(shù)來改進(jìn)GLOCAL算法，得到K-GLOCAL算法，算法描述如下。

（1）在標(biāo)簽空間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）重復(fù)；（5）或者m=1,2,…,g/*學(xué)習(xí)標(biāo)簽相關(guān)性*/；（6）固定V、U、W，通過（7）式[17]更新Zm，End for/*學(xué)習(xí)潛在標(biāo)簽*/；（7）固定U、W、Z，通過（8）式[17]更新V；（8）固定V、W、Z，通過（9）式[17]更新U；（9）固定U、V、Z，通過（10）式[17]更新W；直到收斂。

2 實(shí)驗(yàn)設(shè)計(jì)

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

表1 多標(biāo)簽數(shù)據(jù)集的詳細(xì)描述

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

3 實(shí)驗(yàn)結(jié)果與分析

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

表2 對(duì)測(cè)試集缺損標(biāo)簽數(shù)據(jù)恢復(fù)結(jié)果上的平均精度測(cè)試AP(↑)

表3 對(duì)測(cè)試集缺損標(biāo)簽數(shù)據(jù)恢復(fù)結(jié)果上的接受者操作特性曲線下平均面積測(cè)試AUC(↑)

表4 對(duì)測(cè)試集缺損標(biāo)簽數(shù)據(jù)恢復(fù)結(jié)果上的覆蓋率測(cè)試CV(↓)

表5 對(duì)測(cè)試集缺損標(biāo)簽數(shù)據(jù)恢復(fù)結(jié)果上的排序損失測(cè)試RL(↓)

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

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

圖1 為已知30%標(biāo)簽的數(shù)據(jù)集實(shí)驗(yàn)結(jié)果，若兩個(gè)算法之間沒有顯著差別則用實(shí)線連接，反之則不連。如圖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%標(biāo)簽的數(shù)據(jù)集實(shí)驗(yàn)結(jié)果，如圖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 總 結(jié)

本文結(jié)合K-means聚類算法，對(duì)GLOCAL算法改進(jìn)。針對(duì)其初始化潛在標(biāo)簽與原始標(biāo)簽的關(guān)聯(lián)陣問題，利用聚類中心矩陣代替初始化低秩矩陣，更能表示潛在標(biāo)簽與原始標(biāo)簽的關(guān)聯(lián)性，聚類個(gè)數(shù)K則代替在標(biāo)簽矩陣維數(shù)k，有利于提高算法的精度。實(shí)驗(yàn)結(jié)果表明本文的算法具有一定的優(yōu)勢(shì)。但本文算法仍存在問題，即只考慮在標(biāo)簽空間做出改進(jìn)，沒有著重考慮特征與標(biāo)簽之間的關(guān)聯(lián)性。因此，如何利用特征與標(biāo)簽之間的關(guān)聯(lián)性對(duì)標(biāo)簽進(jìn)行補(bǔ)全是接下來的研究?jī)?nèi)容。