劉依璐，曹付元，2

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

2.山西大學(xué) 計算智能與中文信息處理教育部重點實驗室，太原 030006

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

對于大部分現(xiàn)有的大規(guī)模多標(biāo)簽分類算法[7-10]，都要求訓(xùn)練數(shù)據(jù)中所有的標(biāo)簽信息是完整的。然而在實際應(yīng)用中，用戶提供的標(biāo)記可能是不完整的。一方面是因為標(biāo)簽數(shù)量多，逐個標(biāo)注的過程費時費力，因此大部分人工標(biāo)注者會選擇只標(biāo)注相對重要的標(biāo)簽，而丟棄不太重要的標(biāo)簽。另一方面原因是標(biāo)注者的知識范圍有限。例如，在維基百科的在線收藏中給文章標(biāo)記類別時，人工標(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)簽在整個原始數(shù)據(jù)集中的共現(xiàn)概率來獲取標(biāo)簽之間的相關(guān)性，而后利用它來恢復(fù)原始數(shù)據(jù)集中丟失的信息，然后構(gòu)建一個線性的分類器，通過一致性和平滑性這兩個基本的假設(shè)來優(yōu)化最終的目標(biāo)函數(shù)。為了便于處理大規(guī)模數(shù)據(jù)，該算法還引入了共軛梯度加速算法及基于樹的最近鄰查找方法進行模型優(yōu)化。王晶晶等人[12]提出MCWD+傳統(tǒng)多標(biāo)簽分類器的方法進行缺失標(biāo)簽的恢復(fù)及模型訓(xùn)練，該算法主要通過迭代地更新每個訓(xùn)練實例的權(quán)重并且引入一個標(biāo)簽相關(guān)性矩陣來恢復(fù)訓(xùn)練數(shù)據(jù)中的缺失標(biāo)簽信息，最后采用傳統(tǒng)分類器進行模型訓(xùn)練。由于該算法采用傳統(tǒng)分類器進行訓(xùn)練，因此在處理大規(guī)模數(shù)據(jù)時效率并不高。Akbarnejad等人提出的ESMC算法[13]是一種基于嵌入的方法，為充分考慮標(biāo)簽之間的相關(guān)性，采用了非線性嵌入標(biāo)簽向量的方法，并通過學(xué)習(xí)特征空間與潛在空間之間的映射進行建模。此外，還借助了偽實例參數(shù)化稀疏高斯過程的思想，大大減少了模型的訓(xùn)練時間，使其能夠處理大規(guī)模數(shù)據(jù)。LSML算法[14]提出一種學(xué)習(xí)標(biāo)簽特定特征的新方法，用于帶有缺失標(biāo)簽的多標(biāo)簽分類。通過學(xué)習(xí)高階標(biāo)簽相關(guān)性，從原始標(biāo)簽矩陣中增加一個新的補充標(biāo)簽矩陣。然后，學(xué)習(xí)每個類標(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)簽的特征，同時利用成對的標(biāo)簽相關(guān)性來恢復(fù)丟失的標(biāo)簽，并使用加速近端梯度法來有效地解決潛在的優(yōu)化問題。

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

與全局標(biāo)簽相關(guān)性不同，局部標(biāo)簽相關(guān)性是由部分樣本計算得出的，利用這種相關(guān)性進行訓(xùn)練更加符合實際任務(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)性進行缺失標(biāo)簽信息的恢復(fù)及低秩分類器的訓(xùn)練。具體來說，該算法首先對特征空間進行聚類分析，將訓(xùn)練集中的所有示例劃分到不同的簇中，然后在標(biāo)簽空間中使用共現(xiàn)次數(shù)來估計局部標(biāo)簽相關(guān)性。最后，利用得到的標(biāo)簽相關(guān)性進行缺失標(biāo)簽的恢復(fù)，并將該過程與低秩模型的訓(xùn)練過程整合至一個統(tǒng)一的框架中，以提升大規(guī)模數(shù)據(jù)上的模型訓(xùn)練速度。

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

本章講述提出的LMC算法。第一部分介紹多標(biāo)簽分類算法的問題定義。第二部分詳細介紹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個可能標(biāo)簽的輸出空間，訓(xùn)練集D={(xi,yi)|1 ≤i≤n} ，其中n表示訓(xùn)練樣本的個數(shù)，xi=(xi1,xi2,…,xid)∈X 表示第i個實例的d維特征向量，yi=(yi1,yi2,…,yiq)∈Y 表示第i個實例相應(yīng)的q維標(biāo)簽向量，yi中的取值yij=1 時表示第j個標(biāo)簽屬于第i個實例，否則表示為yij=-1。多標(biāo)簽分類任務(wù)的目標(biāo)是從已知的訓(xùn)練集D中學(xué)習(xí)一個分類模型h:X→2Y來準(zhǔn)確地預(yù)測新實例的標(biāo)簽集合。

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

1.2 LMC算法

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

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

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

不同的實例會產(chǎn)生不同的局部標(biāo)簽相關(guān)性。因此，本文提出的算法不再從整個數(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)簽集合中有信息的缺失，直接對其進行聚類分析會影響相關(guān)性獲取的準(zhǔn)確度。鑒于標(biāo)簽中包含的信息來源于特征域，而且特征域中沒有信息的缺失，因此LMC算法選擇對特征域進行聚類分析。同時也可以在一定程度上避免因數(shù)據(jù)缺失產(chǎn)生的異常點及類別不均衡情況。

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

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

其中，Xl1表示被標(biāo)簽l1標(biāo)注的實例集合，|Xl1|表示被標(biāo)簽l1標(biāo)注的實例數(shù)目，Xl2、|Xl2|與Xl1、|Xl1|同理。|Xl1∩Xl2|表示同時被標(biāo)簽l1及l(fā)2標(biāo)注的實例數(shù)目。s是引入的一個平滑參數(shù)，可以在一定程度上避免由于標(biāo)簽不平衡所產(chǎn)生的極端情況。例如，有100 篇文章，其中10 篇本應(yīng)標(biāo)注為足球和鞠蹴，而其他文章標(biāo)記為足球。但此時由于文化差異，這10 篇文章中的鞠蹴標(biāo)簽全部丟失，即同時被標(biāo)注為足球和蹴鞠的樣本個數(shù)為0，則在不考慮s計算相關(guān)性時，足球和鞠蹴之間的相關(guān)性估計將為0，然而這兩個標(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)系。進一步地，將計算出的L(· ,l2)向量進行歸一化處理，使得向量各元素之和為1，此時得到的所有相關(guān)性值在[0,1]區(qū)間內(nèi)，因此，可以將歸一化之后的L(· ,l2)中的值視為其余標(biāo)簽對某標(biāo)簽的貢獻率。同樣以標(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)簽進行恢復(fù)?；謴?fù)的基本原則有兩點：

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

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

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

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

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

1.2.3 模型訓(xùn)練

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

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

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

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

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

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

1.3 優(yōu)化

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

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

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

其中，I為單位矩陣。

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

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

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

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

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

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

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

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

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

1.4 模型預(yù)測

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

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

算法1LMC算法

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

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

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

2.fori=1 tokdo

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

4.初始化Y~ =C，隨機初始化矩陣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.計算各聚類簇中心與xtest的距離

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

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

2 實驗

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

2.1 實驗設(shè)置

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

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

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

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

2.1.2 評價指標(biāo)

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

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

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

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

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

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

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

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

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

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

2.2 參數(shù)影響

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

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

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

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

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

2.2.2 平衡因子α 的影響

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

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

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

2.2.3 平衡因子β 的影響

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

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

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

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

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

圖5 展示了算法隨著低秩的維度約束r變化時的性能變化情況，橫坐標(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的實驗分析，本文推薦r參數(shù)取值在標(biāo)簽個數(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ù)時目標(biāo)函數(shù)的收斂情況，在其他數(shù)據(jù)集上的實驗結(jié)果也是類似的。

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

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

2.3 實驗結(jié)果

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

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

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

2.4 分類結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

通過上述大量實驗的比較分析，充分體現(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ù)集分解為多個數(shù)據(jù)簇，后利用隱藏在數(shù)據(jù)簇內(nèi)部的局部標(biāo)簽相關(guān)性來進行缺失標(biāo)簽的恢復(fù)及局部模型的訓(xùn)練。本文在7 個來自不同領(lǐng)域的基準(zhǔn)數(shù)據(jù)集上進行了大量實驗，結(jié)果表明本文提出算法在處理大規(guī)模數(shù)據(jù)及缺失數(shù)據(jù)上具有一定的優(yōu)越性。對于未來的工作，將尋求一種更合適的方法將具有相似標(biāo)簽相關(guān)性的多標(biāo)簽實例進行聚類。