劉依璐，曹付元，2

1.山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，太原 030006

2.山西大學(xué) 計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室，太原 030006

隨著數(shù)據(jù)量的爆炸式增長，大規(guī)模多標(biāo)簽分類算法比傳統(tǒng)的多標(biāo)簽分類算法更符合實(shí)際的分類要求。大規(guī)模多標(biāo)簽分類的目標(biāo)是訓(xùn)練一個(gè)分類器，該分類器可以從大規(guī)模的標(biāo)簽集合中挑選出與實(shí)例最相關(guān)的標(biāo)簽子集。目前已被廣泛用于圖像及視頻標(biāo)注[1-2]、文本分類[3-4]、基因功能預(yù)測[5]、臨床醫(yī)學(xué)[6]等實(shí)際任務(wù)中。

對于大部分現(xiàn)有的大規(guī)模多標(biāo)簽分類算法[7-10]，都要求訓(xùn)練數(shù)據(jù)中所有的標(biāo)簽信息是完整的。然而在實(shí)際應(yīng)用中，用戶提供的標(biāo)記可能是不完整的。一方面是因?yàn)闃?biāo)簽數(shù)量多，逐個(gè)標(biāo)注的過程費(fèi)時(shí)費(fèi)力，因此大部分人工標(biāo)注者會選擇只標(biāo)注相對重要的標(biāo)簽，而丟棄不太重要的標(biāo)簽。另一方面原因是標(biāo)注者的知識范圍有限。例如，在維基百科的在線收藏中給文章標(biāo)記類別時(shí)，人工標(biāo)注者通常只標(biāo)注他們知道的類別標(biāo)簽。這就導(dǎo)致了多標(biāo)簽數(shù)據(jù)集中標(biāo)簽的缺失情況。在這種情況下，直接在含有缺失標(biāo)簽的數(shù)據(jù)集上訓(xùn)練傳統(tǒng)的分類器會給分類效果帶來較大的誤差。

因此，許多用于解決含缺失標(biāo)簽的大規(guī)模多標(biāo)簽分類算法被提出。例如，Tan 等人[11]提出的歸納式解決方法Smile，該方法借助標(biāo)簽在整個(gè)原始數(shù)據(jù)集中的共現(xiàn)概率來獲取標(biāo)簽之間的相關(guān)性，而后利用它來恢復(fù)原始數(shù)據(jù)集中丟失的信息，然后構(gòu)建一個(gè)線性的分類器，通過一致性和平滑性這兩個(gè)基本的假設(shè)來優(yōu)化最終的目標(biāo)函數(shù)。為了便于處理大規(guī)模數(shù)據(jù)，該算法還引入了共軛梯度加速算法及基于樹的最近鄰查找方法進(jìn)行模型優(yōu)化。王晶晶等人[12]提出MCWD+傳統(tǒng)多標(biāo)簽分類器的方法進(jìn)行缺失標(biāo)簽的恢復(fù)及模型訓(xùn)練，該算法主要通過迭代地更新每個(gè)訓(xùn)練實(shí)例的權(quán)重并且引入一個(gè)標(biāo)簽相關(guān)性矩陣來恢復(fù)訓(xùn)練數(shù)據(jù)中的缺失標(biāo)簽信息，最后采用傳統(tǒng)分類器進(jìn)行模型訓(xùn)練。由于該算法采用傳統(tǒng)分類器進(jìn)行訓(xùn)練，因此在處理大規(guī)模數(shù)據(jù)時(shí)效率并不高。Akbarnejad等人提出的ESMC算法[13]是一種基于嵌入的方法，為充分考慮標(biāo)簽之間的相關(guān)性，采用了非線性嵌入標(biāo)簽向量的方法，并通過學(xué)習(xí)特征空間與潛在空間之間的映射進(jìn)行建模。此外，還借助了偽實(shí)例參數(shù)化稀疏高斯過程的思想，大大減少了模型的訓(xùn)練時(shí)間，使其能夠處理大規(guī)模數(shù)據(jù)。LSML算法[14]提出一種學(xué)習(xí)標(biāo)簽特定特征的新方法，用于帶有缺失標(biāo)簽的多標(biāo)簽分類。通過學(xué)習(xí)高階標(biāo)簽相關(guān)性，從原始標(biāo)簽矩陣中增加一個(gè)新的補(bǔ)充標(biāo)簽矩陣。然后，學(xué)習(xí)每個(gè)類標(biāo)簽的標(biāo)簽特定數(shù)據(jù)表示，并在此基礎(chǔ)上結(jié)合學(xué)習(xí)到的高階標(biāo)簽相關(guān)性來構(gòu)建多標(biāo)簽分類器。MLLCRS-ML 算法[15]提出一種能夠處理含缺失標(biāo)簽的分類器，該分類器考慮了特定于標(biāo)簽的特征，同時(shí)利用成對的標(biāo)簽相關(guān)性來恢復(fù)丟失的標(biāo)簽，并使用加速近端梯度法來有效地解決潛在的優(yōu)化問題。

上述方法可以歸類為全局多標(biāo)簽分類方法，因?yàn)樗鼈兌技僭O(shè)標(biāo)簽之間的關(guān)系可以在整個(gè)實(shí)例集上進(jìn)行建模，然而在實(shí)際任務(wù)中，標(biāo)簽之間的相關(guān)性只能適用于一部分實(shí)例子集，并且很少有相關(guān)性是全局適用的。例如，在給雜志中的圖片標(biāo)注標(biāo)簽時(shí)，“apple”與“fruit”之間的高相關(guān)性就不能同時(shí)被美食類雜志和科技類雜志共享，而只能被美食類雜志使用。

與全局標(biāo)簽相關(guān)性不同，局部標(biāo)簽相關(guān)性是由部分樣本計(jì)算得出的，利用這種相關(guān)性進(jìn)行訓(xùn)練更加符合實(shí)際任務(wù)需要。例如：在美食類的雜志中，使用“apple”與“fruit”之間的高相關(guān)性；在科技類的雜志中不使用“apple”與“fruit”之間的高相關(guān)性，而使用“apple”與“phone”之間的高相關(guān)性。為此，本文提出一種基于局部標(biāo)簽相關(guān)性的多標(biāo)簽分類方法LMC（local label correlations-based multi-label classification algorithm），通過使用局部的標(biāo)簽相關(guān)性進(jìn)行缺失標(biāo)簽信息的恢復(fù)及低秩分類器的訓(xùn)練。具體來說，該算法首先對特征空間進(jìn)行聚類分析，將訓(xùn)練集中的所有示例劃分到不同的簇中，然后在標(biāo)簽空間中使用共現(xiàn)次數(shù)來估計(jì)局部標(biāo)簽相關(guān)性。最后，利用得到的標(biāo)簽相關(guān)性進(jìn)行缺失標(biāo)簽的恢復(fù)，并將該過程與低秩模型的訓(xùn)練過程整合至一個(gè)統(tǒng)一的框架中，以提升大規(guī)模數(shù)據(jù)上的模型訓(xùn)練速度。

1 含缺失標(biāo)簽的大規(guī)模多標(biāo)簽分類算法

本章講述提出的LMC算法。第一部分介紹多標(biāo)簽分類算法的問題定義。第二部分詳細(xì)介紹LMC算法主要處理過程：獲取局部標(biāo)簽相關(guān)性、缺失標(biāo)簽的恢復(fù)及模型訓(xùn)練。第三部分介紹算法的優(yōu)化。第四部分介紹算法的測試過程。

1.1 問題定義

在傳統(tǒng)的多標(biāo)簽分類任務(wù)中，X=Rd代表含有d維特征向量的輸入空間，Y={1,-1}q代表含有q個(gè)可能標(biāo)簽的輸出空間，訓(xùn)練集D={(xi,yi)|1 ≤i≤n} ，其中n表示訓(xùn)練樣本的個(gè)數(shù)，xi=(xi1,xi2,…,xid)∈X 表示第i個(gè)實(shí)例的d維特征向量，yi=(yi1,yi2,…,yiq)∈Y 表示第i個(gè)實(shí)例相應(yīng)的q維標(biāo)簽向量，yi中的取值yij=1 時(shí)表示第j個(gè)標(biāo)簽屬于第i個(gè)實(shí)例，否則表示為yij=-1。多標(biāo)簽分類任務(wù)的目標(biāo)是從已知的訓(xùn)練集D中學(xué)習(xí)一個(gè)分類模型h:X→2Y來準(zhǔn)確地預(yù)測新實(shí)例的標(biāo)簽集合。

讓X=(x1;x2;…;xn)∈Rn×d為實(shí)例的特征矩陣，Y=(y1;y2;…;yn)∈{1,-1}n×q為實(shí)例的標(biāo)簽矩陣，對于傳統(tǒng)的多標(biāo)簽分類來說矩陣Y中的數(shù)據(jù)沒有缺失，然而在含有缺失標(biāo)簽的矩陣Y中只有部分相關(guān)標(biāo)簽是已知的，只能得到一個(gè)不完整的標(biāo)簽矩陣C=(c1;c2;…;cn)∈{1,0,-1}n×q，其中ci=(ci1,ci2,…,ciq)，當(dāng)cij=1 時(shí)表示第j個(gè)標(biāo)簽屬于第i個(gè)實(shí)例，cij=-1 時(shí)表示第j個(gè)標(biāo)簽不屬于第i個(gè)實(shí)例，cij=0 則表示第j個(gè)標(biāo)簽缺失。此外，本文中采用的標(biāo)簽矩陣C是高維的，即C中的q值較大。

1.2 LMC算法

在含有缺失數(shù)據(jù)的大規(guī)模多標(biāo)簽分類問題中，主要面臨兩個(gè)問題：一方面是較大的數(shù)據(jù)量[16-20]，另一方面是訓(xùn)練數(shù)據(jù)中存在缺失的標(biāo)簽信息[21-24]。在這種情況下，采用傳統(tǒng)的多標(biāo)簽分類器不僅會降低分類器的分類準(zhǔn)確度，還會產(chǎn)生較大的時(shí)間和存儲代價(jià)。為了解決上述兩個(gè)問題，本文提出一種基于局部標(biāo)簽相關(guān)性的LMC算法，該算法首先對訓(xùn)練樣本的特征域進(jìn)行聚類分析，將原始數(shù)據(jù)集分成k個(gè)數(shù)據(jù)簇，使得同一個(gè)數(shù)據(jù)簇中的樣本具有相似的標(biāo)簽相關(guān)性；然后在每個(gè)數(shù)據(jù)簇中挖掘標(biāo)簽之間的局部相關(guān)性，并利用得到的相關(guān)性進(jìn)行缺失標(biāo)簽信息的恢復(fù)；最后為每個(gè)數(shù)據(jù)簇訓(xùn)練一個(gè)低秩的分類器，并將標(biāo)簽的分類任務(wù)與缺失標(biāo)簽的恢復(fù)任務(wù)進(jìn)行集成，采用迭代優(yōu)化的方式得到最終的分類器。在預(yù)測階段，給出一個(gè)新樣本，利用與樣本距離最近的數(shù)據(jù)簇對應(yīng)的局部模型進(jìn)行標(biāo)簽預(yù)測。圖1 簡明扼要地說明了LMC 算法的框架，在下面的章節(jié)中將對該算法進(jìn)行詳細(xì)闡述。

圖1 算法框架Fig.1 Architecture of algorithm

1.2.1 獲取局部標(biāo)簽相關(guān)性

不同的實(shí)例會產(chǎn)生不同的局部標(biāo)簽相關(guān)性。因此，本文提出的算法不再從整個(gè)數(shù)據(jù)集中挖掘標(biāo)簽關(guān)系，而是在相似的樣本中尋找標(biāo)簽之間的相關(guān)性，舍棄掉不相似的樣本，以減少其對標(biāo)簽關(guān)系獲取準(zhǔn)確度的影響。為了準(zhǔn)確地獲取標(biāo)簽之間的相關(guān)性，LMC 算法采用聚類的方式來挖掘數(shù)據(jù)之間的局部標(biāo)簽相關(guān)性信息。由于標(biāo)簽集合中有信息的缺失，直接對其進(jìn)行聚類分析會影響相關(guān)性獲取的準(zhǔn)確度。鑒于標(biāo)簽中包含的信息來源于特征域，而且特征域中沒有信息的缺失，因此LMC算法選擇對特征域進(jìn)行聚類分析。同時(shí)也可以在一定程度上避免因數(shù)據(jù)缺失產(chǎn)生的異常點(diǎn)及類別不均衡情況。

本文在實(shí)驗(yàn)過程中選擇k-means 聚類算法來劃分訓(xùn)練數(shù)據(jù)。對樣例集合進(jìn)行聚類后，訓(xùn)練數(shù)據(jù)被分為k個(gè)組{D1,D2,…,Dk}，使得具有相似標(biāo)簽相關(guān)性的實(shí)例分到同一組中。然后在每個(gè)數(shù)據(jù)簇Di中挖掘局部的標(biāo)簽相關(guān)性。詳細(xì)計(jì)算過程如下：

以標(biāo)簽l1與l2之間的相關(guān)性L(l1,l2)為例：

其中，Xl1表示被標(biāo)簽l1標(biāo)注的實(shí)例集合，|Xl1|表示被標(biāo)簽l1標(biāo)注的實(shí)例數(shù)目，Xl2、|Xl2|與Xl1、|Xl1|同理。|Xl1∩Xl2|表示同時(shí)被標(biāo)簽l1及l(fā)2標(biāo)注的實(shí)例數(shù)目。s是引入的一個(gè)平滑參數(shù)，可以在一定程度上避免由于標(biāo)簽不平衡所產(chǎn)生的極端情況。例如，有100 篇文章，其中10 篇本應(yīng)標(biāo)注為足球和鞠蹴，而其他文章標(biāo)記為足球。但此時(shí)由于文化差異，這10 篇文章中的鞠蹴標(biāo)簽全部丟失，即同時(shí)被標(biāo)注為足球和蹴鞠的樣本個(gè)數(shù)為0，則在不考慮s計(jì)算相關(guān)性時(shí)，足球和鞠蹴之間的相關(guān)性估計(jì)將為0，然而這兩個(gè)標(biāo)簽是存在關(guān)聯(lián)的。因此，通過設(shè)置s＞0，就可以在一定程度上避免這種情況。

用L(· ,l2)=(L(l1,l2),L(l2,l2),…,L(lq,l2)) 表示所有標(biāo)簽與l2標(biāo)簽之間的相互關(guān)系。進(jìn)一步地，將計(jì)算出的L(· ,l2)向量進(jìn)行歸一化處理，使得向量各元素之和為1，此時(shí)得到的所有相關(guān)性值在[0,1]區(qū)間內(nèi)，因此，可以將歸一化之后的L(· ,l2)中的值視為其余標(biāo)簽對某標(biāo)簽的貢獻(xiàn)率。同樣以標(biāo)簽l1與標(biāo)簽l2的相關(guān)性為例，具體的歸一化過程如下：

最終，所有的標(biāo)簽相關(guān)性構(gòu)成相關(guān)性矩陣L。

1.2.2 缺失標(biāo)簽的恢復(fù)

在獲取了局部的標(biāo)簽相關(guān)性之后，就利用它對缺失標(biāo)簽進(jìn)行恢復(fù)?；謴?fù)的基本原則有兩點(diǎn)：

（1）在原始數(shù)據(jù)集中存在的標(biāo)簽在恢復(fù)的數(shù)據(jù)集中仍然存在，因?yàn)檫@部分信息是準(zhǔn)確無誤的，因此需要保留這部分信息。

（2）在進(jìn)行不同樣本標(biāo)注時(shí)，具有強(qiáng)相關(guān)性的標(biāo)簽的取值相近，反之亦然。

因此，LMC中具體的標(biāo)簽恢復(fù)過程如下：

其中，是對第i個(gè)實(shí)例的第j個(gè)標(biāo)簽恢復(fù)后的值，ci表示含缺失標(biāo)簽數(shù)據(jù)集中第i個(gè)實(shí)例的標(biāo)簽向量，L(·,lj) 表示其余標(biāo)簽與第j個(gè)標(biāo)簽之間的相關(guān)性向量。采用式（3）可以很好地保證兩點(diǎn)基本準(zhǔn)則。

最后選擇閾值0.5 來確定最終的值，如果的值大于0.5 時(shí)，在C中cij的值變?yōu)?；否則在C中cij的值變?yōu)?1。并將恢復(fù)好的標(biāo)簽矩陣記為Y~ ∈{-1,1}n×q，同時(shí)將其作為新的標(biāo)簽集。

1.2.3 模型訓(xùn)練

在處理在現(xiàn)有的解決方案中，許多算法都將分類任務(wù)與缺失標(biāo)簽的恢復(fù)任務(wù)分離開來，但是在處理大規(guī)模數(shù)據(jù)時(shí)會增加模型的訓(xùn)練時(shí)間。因此，LMC算法將這兩個(gè)任務(wù)進(jìn)行結(jié)合，在恢復(fù)數(shù)據(jù)的同時(shí)進(jìn)行多標(biāo)簽分類。

在使用傳統(tǒng)的線性分類器f(x;Z)=xZ(Z∈Rd×q)時(shí)，模型的訓(xùn)練誤差通常表示為：

但直接在大規(guī)模數(shù)據(jù)集中使用傳統(tǒng)線性分類器的訓(xùn)練時(shí)間會很長。基于以下觀察：盡管多標(biāo)簽分類問題中的標(biāo)簽數(shù)量可能很大，但通常存在顯著的標(biāo)簽相關(guān)性，這意味著輸出空間是低秩的，LMC算法選擇將建模所需的有效參數(shù)數(shù)量減少到遠(yuǎn)小于d×q，即通過對矩陣Z的低秩分解限制Z僅學(xué)習(xí)少量潛在因素來捕捉標(biāo)簽與特征之間的關(guān)系。這樣不僅能有效控制過擬合，而且還能提高在大規(guī)模數(shù)據(jù)上的計(jì)算速度。具體做法如下：

在每個(gè)數(shù)據(jù)簇Di中，先利用標(biāo)簽之間的相關(guān)性進(jìn)行缺失數(shù)據(jù)的恢復(fù)，后將恢復(fù)后的標(biāo)簽矩陣投入分類模型中進(jìn)行訓(xùn)練，再將模型訓(xùn)練的結(jié)果作為新的輸入重新進(jìn)行標(biāo)簽恢復(fù)和訓(xùn)練。在分類模型中，采用低秩分解技術(shù)將矩陣Z分解為兩個(gè)秩為r(r?q) 的低秩矩陣W∈Rd×r和H∈Rq×r，使得Z=WHT。因此，模型的目標(biāo)函數(shù)更新如下：

其中，表示第i個(gè)實(shí)例對應(yīng)的恢復(fù)后的標(biāo)簽向量；α及β為調(diào)節(jié)因子，α用來進(jìn)行低秩控制，防止模型的過擬合，β用來約束數(shù)據(jù)恢復(fù)的準(zhǔn)確度。

在式（5）中，第一項(xiàng)用來計(jì)算模型的訓(xùn)練誤差；第二項(xiàng)實(shí)現(xiàn)對參數(shù)的低秩控制；第三項(xiàng)為標(biāo)簽恢復(fù)的誤差項(xiàng)，旨在使用標(biāo)簽之間的局部相關(guān)性進(jìn)行缺失數(shù)據(jù)的恢復(fù)，若某標(biāo)簽缺失，且該標(biāo)簽與已存在標(biāo)簽之間的相關(guān)性越大，則該標(biāo)簽被恢復(fù)為1的概率就越大，反之亦然。

1.3 優(yōu)化

針對式（5），LMC算法采用迭代最小化的方式進(jìn)行優(yōu)化。為了便于運(yùn)算，首先將式（5）簡化為矩陣形式。

步驟1固定W、Y~ ，求H，則目標(biāo)函數(shù)可以轉(zhuǎn)化為：

接下來對上式進(jìn)行求導(dǎo)，可得：

其中，I為單位矩陣。

步驟2固定H、，求W，則目標(biāo)函數(shù)可以轉(zhuǎn)化為：

與步驟1方法類似，令該式的導(dǎo)數(shù)為0，得到：

但是在計(jì)算W時(shí)，涉及大量的大規(guī)模矩陣相乘，計(jì)算速率會大大降低。因此，LMC 算法選擇采用其他的方法進(jìn)行優(yōu)化。共軛梯度法是非常重要的一種優(yōu)化算法，該方法所需存儲量小，穩(wěn)定性高，收斂速度快，是求解大型線性及非線性方程組最有用的方法之一。結(jié)合上述分析，LMC 算法采用共軛梯度算法對式（10）進(jìn)一步進(jìn)行優(yōu)化。

首先需要對式（10）求解出一階導(dǎo)數(shù)和二階導(dǎo)數(shù)：

其中，w=vec(W)，s=vec(S)，vec(*)代表矩陣的向量化操作，S是一個(gè)d×q維的任意矩陣。

接下來就可以直接使用共軛梯度法進(jìn)行問題的求解。具體的執(zhí)行過程可參考相關(guān)文獻(xiàn)[13]。

步驟3固定H、W，更新Y~ ，則目標(biāo)函數(shù)可以轉(zhuǎn)化為：

與步驟1方法類似，令該式的導(dǎo)數(shù)為0，得到：

然后，對中原本為1和-1的數(shù)據(jù)進(jìn)行恢復(fù)，以保證原始數(shù)據(jù)集中的信息不發(fā)生丟失。

1.4 模型預(yù)測

在優(yōu)化完成之后就可以得到最優(yōu)的W和H，記為W*，H*。對于待預(yù)測的樣本特征向量xtest，首先計(jì)算距離其最近的聚類簇，然后利用該聚類簇的局部分類器進(jìn)行預(yù)測，公式如下：

上述利用局部標(biāo)記相關(guān)性的LMC算法的詳細(xì)步驟如算法1所示。

算法1LMC算法

輸入：訓(xùn)練集D=[X,C]，測試樣本xtest，聚類個(gè)數(shù)k，平衡因子α、β，最大迭代次數(shù)max_iter。

輸出：測試樣本的預(yù)測標(biāo)簽向量ytest。

1.對訓(xùn)練樣本的特征域進(jìn)行k-means 聚類分析，得到k個(gè)小聚類簇{D1,D2,…,Dk}

2.fori=1 tokdo

3.將聚類簇Di作為訓(xùn)練樣本

4.初始化Y~ =C，隨機(jī)初始化矩陣W、H，max_iter=100

5.forj=1 tomax_iterdo

6.根據(jù)式（9）更新H

7.將式（12）、（13）作為共軛梯度算法的輸入更新W

8.根據(jù)式（14）更新Y~

9.end for

10.end for

11.計(jì)算各聚類簇中心與xtest的距離

12.挑選距離最近的聚類簇對應(yīng)的分類器，得到W*，H*

13.根據(jù)式（16）得到預(yù)測的標(biāo)簽向量ytest，并返回

2 實(shí)驗(yàn)

這部分主要評估LMC 算法的有效性。將LMC 算法在7 個(gè)多標(biāo)簽數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，并和現(xiàn)有的5 種相關(guān)算法進(jìn)行比較和分析，從而來驗(yàn)證LMC 算法的可行性和有效性。

2.1 實(shí)驗(yàn)設(shè)置

2.1.1 數(shù)據(jù)集

本文將LMC 算法在7 個(gè)來自不同領(lǐng)域的數(shù)據(jù)集上與其他算法進(jìn)行對比實(shí)驗(yàn)。實(shí)驗(yàn)中用到的數(shù)據(jù)集的詳細(xì)信息如表1所示。

表1 數(shù)據(jù)集描述（按標(biāo)簽數(shù)目升序排列）Table 1 Description of data sets（sorted in ascending order of number of labels）

在實(shí)驗(yàn)過程中，對于每一個(gè)數(shù)據(jù)集，將其隨機(jī)劃分為訓(xùn)練集（占70%）和測試集（占30%），此過程反復(fù)進(jìn)行5次，最后將這5次實(shí)驗(yàn)結(jié)果的均值作為最終的結(jié)果。

2.1.2 評價(jià)指標(biāo)

現(xiàn)有評價(jià)多標(biāo)簽分類性能的指標(biāo)主要分為基于實(shí)例的評價(jià)標(biāo)準(zhǔn)、基于標(biāo)簽的評價(jià)標(biāo)準(zhǔn)和基于排序的評價(jià)標(biāo)準(zhǔn)，詳細(xì)描述可參考相關(guān)文獻(xiàn)[25]。本文從中選擇其中5 個(gè)常用的評價(jià)指標(biāo)來對比各算法的性能，分別為P@1、P@3、P@5、average-AUC 和coverage。前三種標(biāo)準(zhǔn)是基于實(shí)例的評價(jià)標(biāo)準(zhǔn)，用來評估在測試集中預(yù)測值較高的幾個(gè)標(biāo)簽的分類性能，coverage則用來評估整體的分類性能，average-AUC 屬于基于排序的評價(jià)標(biāo)準(zhǔn)，從標(biāo)簽排序的角度來衡量分類性能。對于前4 種評價(jià)指標(biāo)來說，指標(biāo)的取值越大，則表明算法的性能越好；對最后一個(gè)評價(jià)指標(biāo)而言，取值越小則算法的性能越好。

2.1.3 參數(shù)設(shè)置

本文將提出的LMC 算法與現(xiàn)有的5 種多標(biāo)簽分類算法進(jìn)行比較，這些算法都可以用來解決含有缺失標(biāo)簽的大規(guī)模多標(biāo)簽分類問題。每個(gè)算法都根據(jù)原論文建議配置了相應(yīng)的參數(shù)。

（1）Smile[11]：該算法利用標(biāo)簽之間的相關(guān)性進(jìn)行缺失標(biāo)簽的估計(jì)，并建立線性的分類器進(jìn)行模型的訓(xùn)練和對未知樣本的標(biāo)簽預(yù)測。各個(gè)參數(shù)的具體設(shè)置詳見文獻(xiàn)[11]。

（2）MCWD+MLKNN[12]：該算法將標(biāo)簽恢復(fù)方法MCWD與傳統(tǒng)多標(biāo)簽分類算法MLKNN進(jìn)行結(jié)合用來進(jìn)行缺失數(shù)據(jù)的恢復(fù)，且可以擴(kuò)展至大規(guī)模數(shù)據(jù)集上。其中MLKNN算法中近鄰個(gè)數(shù)的取值設(shè)置為10，平滑系數(shù)取值設(shè)置為1，其余各參數(shù)的具體設(shè)置詳見文獻(xiàn)[12]。

（3）ESMC[13]：該算法使用隨機(jī)方法非線性嵌入標(biāo)簽向量，以解決基于嵌入式的學(xué)習(xí)方法中尾標(biāo)簽預(yù)測不準(zhǔn)確的問題。該方法在處理丟失標(biāo)簽及大規(guī)模數(shù)據(jù)集方面具有良好的表現(xiàn)。各個(gè)參數(shù)的具體設(shè)置詳見文獻(xiàn)[13]。

（4）LSML[14]：該算法提出一種學(xué)習(xí)標(biāo)簽特定特征的新方法，用于帶有缺失標(biāo)簽的多標(biāo)簽分類。通過學(xué)習(xí)高階標(biāo)簽相關(guān)性，從原始標(biāo)簽矩陣中增加一個(gè)新的補(bǔ)充標(biāo)簽矩陣。然后，學(xué)習(xí)每個(gè)類標(biāo)簽的標(biāo)簽特定數(shù)據(jù)表示，并在此基礎(chǔ)上結(jié)合學(xué)習(xí)到的高階標(biāo)簽相關(guān)性來構(gòu)建多標(biāo)簽分類器。各個(gè)參數(shù)的具體設(shè)置詳見文獻(xiàn)[14]。

（5）MLLCRS-ML[15]：該算法提出一種能夠處理含缺失標(biāo)簽的分類器，該分類器考慮了特定于標(biāo)簽的特征，同時(shí)利用成對的標(biāo)簽相關(guān)性來恢復(fù)丟失的標(biāo)簽，并使用加速近端梯度法來有效地解決潛在的優(yōu)化問題。各個(gè)參數(shù)的具體設(shè)置詳見文獻(xiàn)[15]。

（6）LMC：對于本文提出的算法，k-means中聚類個(gè)數(shù)的取值在[50，150]內(nèi)進(jìn)行選擇，平衡因子α的取值在[0.5，1.5]范圍內(nèi)進(jìn)行選擇，β取值在[0.5，1.0]之間，低秩參數(shù)r的取值在[30，300]內(nèi)進(jìn)行選擇，迭代參數(shù)max_iter的取值設(shè)為50。

以上參數(shù)均采用五折交叉驗(yàn)證方法選擇適用于各數(shù)據(jù)集的最優(yōu)值。

2.2 參數(shù)影響

本節(jié)對LMC 算法中的五個(gè)重要參數(shù)：k-means 聚類中的類簇個(gè)數(shù)k，平衡因子α，平衡因子β，低秩約束參數(shù)r及最佳迭代次數(shù)max_iter展開研究。每次僅改變一個(gè)參數(shù)的取值，其余參數(shù)保持不變。

2.2.1 聚類個(gè)數(shù)k 的影響

在LMC 算法中，聚類個(gè)數(shù)k用來確定k-means 聚類的個(gè)數(shù)，進(jìn)一步影響標(biāo)簽相關(guān)性的獲取細(xì)致度。本文將k的取值從1 取到250，步長為50，并在LMC 算法上運(yùn)行了10 次，然后取平均值作為最終結(jié)果。在各個(gè)數(shù)據(jù)集上隨聚類個(gè)數(shù)變化時(shí)的Precision@1取值變化如圖2所示。

圖2 聚類個(gè)數(shù)的影響Fig.2 Influence of number of clusters

從圖2中可以看出當(dāng)聚類簇個(gè)數(shù)為1時(shí)，Precision@1取值較低，說明此時(shí)算法的分類性能并不是最優(yōu)，因?yàn)榇藭r(shí)僅僅利用了全局的標(biāo)簽相關(guān)性。隨著聚類個(gè)數(shù)的增加，算法的性能有所提升。但是當(dāng)?shù)竭_(dá)某個(gè)最優(yōu)聚類個(gè)數(shù)之后算法的性能有所下降，這是因?yàn)楫?dāng)聚類個(gè)數(shù)過多時(shí)，每個(gè)聚類簇中的樣本個(gè)數(shù)過少，無法準(zhǔn)確捕捉標(biāo)簽之間的相關(guān)性。而且當(dāng)聚類個(gè)數(shù)較多時(shí)，LMC 算法訓(xùn)練的分類器個(gè)數(shù)也較多，訓(xùn)練時(shí)間也會明顯增加。鑒于圖2顯示的結(jié)果，本文建議聚類個(gè)數(shù)的設(shè)置為50/100/150。在下列實(shí)驗(yàn)中，LMC算法在各數(shù)據(jù)集中的聚類個(gè)數(shù)取值均以該圖為指導(dǎo)進(jìn)行設(shè)置。

2.2.2 平衡因子α 的影響

平衡因子α用來控制模型的低秩性，以避免模型出現(xiàn)過擬合及降低模型的復(fù)雜度。本文設(shè)置α的取值從0至2.0，步長為0.5，并將10 次實(shí)驗(yàn)結(jié)果的平均值作為最終結(jié)果。圖3展示了LMC算法在各個(gè)數(shù)據(jù)集上隨平衡因子α變化時(shí)的Precision@1取值。

從圖3 中可以看出當(dāng)α取值為0 時(shí)，Precision@1 取值較低，因?yàn)榇藭r(shí)并沒有對分類器施加低秩約束，而且模型的復(fù)雜度非常高。當(dāng)α取值增加時(shí)，算法的性能有所提升，這是因?yàn)槟Ｐ偷膹?fù)雜度得以降低，過擬合的可能性也得到了減少，最終使得模型的處理效率得到了提升。鑒于圖3結(jié)果，本文建議α參數(shù)取值大于0.5。

圖3 平衡因子α 的影響Fig.3 Influence of balance factor α

2.2.3 平衡因子β 的影響

平衡因子β用來約束缺失標(biāo)簽恢復(fù)的準(zhǔn)確度。該參數(shù)選擇與參數(shù)α同樣的取值范圍進(jìn)行實(shí)驗(yàn)。給定平衡因子β不同的取值，LMC 算法在各數(shù)據(jù)集上Precision@1的變化如圖4所示。

圖4 平衡因子β 的影響Fig.4 Influence of balance factor β

從圖4可以看出，當(dāng)β取值為0時(shí)，算法并沒有進(jìn)行缺失標(biāo)簽恢復(fù)的情況下，而是直接使用含缺失的標(biāo)簽進(jìn)行訓(xùn)練，因此算法的性能并沒有達(dá)到最優(yōu)。隨著取值的增大，該算法會更加注重缺失標(biāo)簽的恢復(fù)，性能逐步提升。但是β取值過大時(shí)，算法會約束恢復(fù)后的標(biāo)簽過分接近含缺失標(biāo)簽取值，此時(shí)，算法的性能會逐步下降，設(shè)置退化為β取值為0的性能。因此，本文建議β參數(shù)的取值在[0.5，1.0]之內(nèi)。

2.2.4 低秩參數(shù)r 的影響

參數(shù)r用來表示低秩矩陣的維度。該參數(shù)的取值范圍從標(biāo)簽個(gè)數(shù)q的1/10 提升至標(biāo)簽個(gè)數(shù)的取值。同樣將10次實(shí)驗(yàn)結(jié)果的平均值作為最終結(jié)果。

圖5 展示了算法隨著低秩的維度約束r變化時(shí)的性能變化情況，橫坐標(biāo)表示低秩約束的維度。在不同的數(shù)據(jù)集中，數(shù)據(jù)的冗余度及標(biāo)簽相關(guān)的程度不同，因此算法在該變量上的最優(yōu)取值涉及范圍較廣。同樣，r的取值不能過大也不能過小，過大會破壞標(biāo)簽的低秩約束，而且也會增加模型訓(xùn)練負(fù)擔(dān)，過小則不能準(zhǔn)確捕捉到標(biāo)簽之間的相關(guān)性?；趫D5的實(shí)驗(yàn)分析，本文推薦r參數(shù)取值在標(biāo)簽個(gè)數(shù)較少的數(shù)據(jù)集上在總標(biāo)簽數(shù)的1/2～1/4 之間選擇，在大規(guī)模數(shù)據(jù)集上則在總標(biāo)簽數(shù)的1/8～1/10之間選擇。

圖5 低秩參數(shù)r 的影響Fig.5 Influence of low-rank parameter r

2.2.5 迭代次數(shù)max_iter 的影響

參數(shù)max_iter為模型的訓(xùn)練截止條件。該參數(shù)的取值范圍從1 逐次增至150。圖6 展示了算法增加迭代次數(shù)時(shí)目標(biāo)函數(shù)的收斂情況，在其他數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果也是類似的。

從圖6 可以看出，在迭代次數(shù)為50 之前，算法在以上四個(gè)數(shù)據(jù)集均達(dá)到收斂，具有較快的收斂速度?；趫D6，推薦max_iter取值設(shè)為50。

圖6 迭代次數(shù)max_iter 的影響Fig.6 Influence of number of iterations max_iter

2.3 實(shí)驗(yàn)結(jié)果

本文僅展示缺失率為10%（缺失的標(biāo)簽個(gè)數(shù)占總標(biāo)簽個(gè)數(shù)的10%）時(shí)各對比算法在不同數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，如表2～6 所示。其中最優(yōu)的實(shí)驗(yàn)結(jié)果已用粗體標(biāo)識出來，“—”表示因?qū)嶒?yàn)花費(fèi)時(shí)間過長暫未取得實(shí)驗(yàn)結(jié)果，括號中的數(shù)字表示各算法在同一數(shù)據(jù)集上的結(jié)果排名。

從表2～6 中可以看出，在35 組（5 個(gè)評價(jià)指標(biāo)×7 個(gè)數(shù)據(jù)集）對比實(shí)驗(yàn)結(jié)果中，LMC算法共有27次排名第一（含并列），7 次排名第二（含并列），排在第三的共有1次。這說明提出算法在缺失率為10%時(shí)分類的準(zhǔn)確度上要優(yōu)于其余五種算法，其他缺失率設(shè)置下的分類性能也類似。

表2 在P@1下的實(shí)驗(yàn)結(jié)果“均值（排名）”（取值越大越好）Table 2 Experimental result on P@1“mean（ranking）”（the larger the value，the better）

2.4 分類結(jié)果分析

為了分析不同算法在不同數(shù)據(jù)集中的性能，使用Friedman 檢驗(yàn)進(jìn)行性能分析。在實(shí)驗(yàn)中，總共有6 種方法和7個(gè)數(shù)據(jù)集并分別將其記為k=6，N=7，Rj表示第j個(gè)算法在所有數(shù)據(jù)集上的平均排名，則Friedman統(tǒng)計(jì)值服從自由度為6-1=5 的χ2分布。表7 顯示了在顯著性水平α=0.05 上每個(gè)評估標(biāo)準(zhǔn)的FF取值。如表7 所示，所有的評估值都超過了臨界值，因此這些方法的性能是不同的。

表3 在P@3下的實(shí)驗(yàn)結(jié)果“均值（排名）”（取值越大越好）Table 3 Experimental result on P@3“mean（ranking）”（the larger the value，the better）

表7 在每個(gè)評價(jià)標(biāo)準(zhǔn)下的Friedman統(tǒng)計(jì)值Table 7 Friedman statistics FF on each evaluation criteria

表4 在P@5下的實(shí)驗(yàn)結(jié)果“均值（排名）”（取值越大越好）Table 4 Experimental result on P@5“mean（ranking）”（the larger the value，the better）

表5 在average-AUC下的實(shí)驗(yàn)結(jié)果“均值（排名）”（取值越大越好）Table 5 Experimental result on average-AUC“mean（ranking）”（the larger the value，the better）

表6 在coverage下的實(shí)驗(yàn)結(jié)果“均值（排名）”（取值越小越好）Table 6 Experimental result on coverage“mean（ranking）”（the smaller the value，the better）

之后，使用Nemenyi 檢驗(yàn)進(jìn)一步分析所有比較方法之間的相對性能，它可以顯示提出的LMC 算法是否能比比較算法實(shí)現(xiàn)更好的性能。臨界值域（CD）由計(jì)算。通過查表，可以得到qα=2.850。然后，可以計(jì)算出CD=2.850。如果LMC的平均排名與另一種方法在所有數(shù)據(jù)集上至少有一個(gè)CD 差異，則這種方法的性能明顯不同于LMC。圖7總結(jié)了每個(gè)評估標(biāo)準(zhǔn)的CD圖。在圖7中，可以看到LMC的水平段在所有評估標(biāo)準(zhǔn)中與除ESMC 之外的其他算法沒有重疊，因此這意味著LMC 與其他算法之間存在顯著差異。ESMC與LMC差別不大的原因是兩個(gè)算法都是用標(biāo)簽之間的相關(guān)性進(jìn)行缺失標(biāo)簽恢復(fù)，并且都存在對長尾標(biāo)簽的處理。此外，通過圖7 可以得出結(jié)論，LMC 在所有評估指標(biāo)上都優(yōu)于其他算法。

圖7 在每個(gè)評價(jià)標(biāo)準(zhǔn)上的CD圖Fig.7 CD diagrams on each evaluation metric

2.5 算法時(shí)間復(fù)雜度

LMC算法主要包括聚類和迭代兩個(gè)部分。k-means聚類的時(shí)間復(fù)雜度為O(n)，在迭代中，主要時(shí)間成本是計(jì)算變量W，時(shí)間復(fù)雜度為O(r(nq+nr+rq))。因此，總的時(shí)間復(fù)雜度為O(nrq+nr2+qr2+n) 。為了分析LMC算法的訓(xùn)練速度優(yōu)勢，表8總結(jié)了所提出方法和比較方法的時(shí)間成本，一般來說，n?d＞q＞r。為了便于比較，此處取每個(gè)算法復(fù)雜度的最高項(xiàng)進(jìn)行對比，由于MCWD+MLKNN算法涉及n3，因此該算法的時(shí)間復(fù)雜度最高。Smile涉及n2，LSML中涉及d3，MLLCRS-ML中q2dn值大于ESMC 中的nq3，ESMC 中的r為三次方，而在LMC 中為二次方。因此，所提出的LMC 方法的復(fù)雜性優(yōu)于其他方法。

表8 各算法的時(shí)間開銷Table 8 Time costs of different methods

通過上述大量實(shí)驗(yàn)的比較分析，充分體現(xiàn)了LMC算法在恢復(fù)缺失數(shù)據(jù)和大規(guī)模多標(biāo)簽數(shù)據(jù)分類方面的優(yōu)勢。

3 結(jié)束語

本文提出了一種基于局部標(biāo)簽相關(guān)性的多標(biāo)簽分類算法，用于解決在大規(guī)模數(shù)據(jù)集上含有缺失標(biāo)簽的分類問題。該方法首先通過在特征空間上應(yīng)用聚類分析，將原始數(shù)據(jù)集分解為多個(gè)數(shù)據(jù)簇，后利用隱藏在數(shù)據(jù)簇內(nèi)部的局部標(biāo)簽相關(guān)性來進(jìn)行缺失標(biāo)簽的恢復(fù)及局部模型的訓(xùn)練。本文在7 個(gè)來自不同領(lǐng)域的基準(zhǔn)數(shù)據(jù)集上進(jìn)行了大量實(shí)驗(yàn)，結(jié)果表明本文提出算法在處理大規(guī)模數(shù)據(jù)及缺失數(shù)據(jù)上具有一定的優(yōu)越性。對于未來的工作，將尋求一種更合適的方法將具有相似標(biāo)簽相關(guān)性的多標(biāo)簽實(shí)例進(jìn)行聚類。