李曉紅，王閃閃，馬堉銀，馬慧芳

(西北師范大學(xué)計算機科學(xué)與工程學(xué)院，甘肅 蘭州 730070)

1 引言

傳統(tǒng)的單標(biāo)簽分類學(xué)習(xí)是指每一個樣本實例擁有唯一的一個類別標(biāo)簽，其中每一個標(biāo)簽屬于一個互斥的標(biāo)簽集合L(|L|>1)。但是，在實際應(yīng)用中，普遍存在一條數(shù)據(jù)可能同時屬于多個不同類別的情況，這類數(shù)據(jù)被稱作多標(biāo)簽數(shù)據(jù)[1]，比如，一篇新聞報道可以同時屬于“娛樂”類別和“科技”類別，一部影片可以同時屬于“動作片”和“驚悚片”。和傳統(tǒng)的單標(biāo)簽分類問題相比，多標(biāo)簽分類問題存在著顯著的區(qū)別，類別間的相關(guān)性和共現(xiàn)性直接導(dǎo)致傳統(tǒng)的單標(biāo)簽分類方法無法被直接應(yīng)用到多標(biāo)簽分類問題中，多標(biāo)簽分類問題正逐漸成為當(dāng)前的研究熱點和難點，在文本分類、定向營銷、基因功能分類和圖像語義注釋等領(lǐng)域中的應(yīng)用尤為廣泛。

多標(biāo)簽分類問題需要尋找最優(yōu)的分類算法從而提高多標(biāo)簽數(shù)據(jù)的分類精度。目前，多標(biāo)簽分類最常見的思路有2種[2]。一種是問題轉(zhuǎn)換，就是將多標(biāo)簽數(shù)據(jù)集轉(zhuǎn)換成單標(biāo)簽數(shù)據(jù)集，然后用傳統(tǒng)的單標(biāo)簽數(shù)據(jù)分類算法對轉(zhuǎn)換后的數(shù)據(jù)進行分類。BR(Binary Relevance)[3]是一種典型的問題轉(zhuǎn)換算法，它將每個標(biāo)簽的預(yù)測看作是一個獨立的單分類問題，并為每個標(biāo)簽訓(xùn)練一個獨立的分類器，用所有訓(xùn)練數(shù)據(jù)對每個分類器進行訓(xùn)練。但是，這種算法忽略了標(biāo)簽之間的相互關(guān)系，往往無法達到令人滿意的分類效果。文獻[4]提出了一種針對DBR(Dependent Binary Relevance)的修剪方法，使用Phi系數(shù)函數(shù)來估計標(biāo)簽之間的相關(guān)度，以去除不相關(guān)的標(biāo)簽。Liu等[5]提出一種基于動態(tài)規(guī)劃的分類器鏈CC-DP(Classifier Chain-Dynamic Programing))算法和貪婪的分類器鏈(CC-Greedy)算法搜索全局最優(yōu)的標(biāo)簽，彌補了CC(Classifier Chain)算法[6]對標(biāo)簽選擇敏感的缺陷。另一種思路是改進算法，即改進已有單標(biāo)簽學(xué)習(xí)算法以解決多標(biāo)簽學(xué)習(xí)問題。如ML-KNN算法[7]通過統(tǒng)計得出每個標(biāo)簽的先驗概率，對標(biāo)簽集合Y中的每個標(biāo)簽λ，分別計算樣本x有標(biāo)簽λ和沒有標(biāo)簽λ的概率，進而預(yù)測x是否具有標(biāo)簽λ。Tsoumakas等[8]提出RAkEL (RAndom k labELsets)方法將初始標(biāo)簽集分解為若干個小的隨機子集，并利用Label Powerset算法[9]訓(xùn)練分類器。除此之外，其他研究者也利用各種方法進行多標(biāo)簽分類的研究[10,11]。

考慮到目前已有的多標(biāo)簽分類算法在數(shù)據(jù)預(yù)測訓(xùn)練模型過程中，要么忽略類別標(biāo)簽之間的相互依賴關(guān)系，要么忽略初始特征對預(yù)測值的重要影響，甚至把這些標(biāo)簽作為附加特征增加到原始特征集中，使得本來維數(shù)就很高的特征集更加復(fù)雜。即使考慮了類別標(biāo)簽之間的依賴關(guān)系，也往往不能充分利用這種關(guān)系，且多標(biāo)簽分類算法忽略標(biāo)簽集合與訓(xùn)練集合之間的初始預(yù)測值，使得多標(biāo)簽分類不準(zhǔn)確。本文針對這些問題，提出一種融合相似度圖和重啟隨機游走模型的多標(biāo)簽分類SGaRW (multi-label classification algorithm combining Similarity Graph and Random Walk)算法。一方面，利用相似度圖充分計算文本與標(biāo)簽之間的關(guān)系，另一方面利用重啟隨機游走模型挖掘標(biāo)簽與標(biāo)簽之間潛在的語義聯(lián)系，最后再進行合理的融合，使得多標(biāo)簽分類結(jié)果更準(zhǔn)確。

2 相關(guān)工作

2.1 多標(biāo)簽分類

從本質(zhì)上講，多標(biāo)簽分類可被看作是一個標(biāo)簽排序問題[12]。根據(jù)測試樣本與每個類別標(biāo)簽之間的相關(guān)度對其進行打分，然后按照分值的高低來決定樣本所隸屬的標(biāo)簽。

設(shè)X={x1,x2,…,xn}表示樣本集合，Y={y1,y2,…,ym}表示標(biāo)簽集合，訓(xùn)練集合表示為D={(xi,Yi)|1≤i≤n}，其中xi∈X為d維的樣本向量(xi1,xi2,…,xid)，而Yi?Y是樣本xi所屬的標(biāo)簽集合。因此，對樣本x的標(biāo)簽預(yù)測可以表示成如下所示的向量H(x)：

H(x)=(s1(x),…,si(x),…,sm(x))

(1)

其中，si(x)∈[0,1]描述樣本x與標(biāo)簽yi之間的相關(guān)度。多標(biāo)簽分類就是從訓(xùn)練數(shù)據(jù)中學(xué)習(xí)得到一個多標(biāo)簽分類器h:X→2Y，對于給定的任意新樣本x，分類器能預(yù)測該樣本隸屬的標(biāo)簽集合。

因此，多標(biāo)簽分類就是尋找較優(yōu)的分類算法來構(gòu)造高精度的分值向量H(x)，從而達到準(zhǔn)確分類的目的。本文提出了融合相似度圖和重啟隨機游走模型的算法SGaRW實現(xiàn)文本的多標(biāo)簽分類，該算法分2個階段實現(xiàn)：第1階段創(chuàng)建相似度圖，計算文本與標(biāo)簽集合之間的初始預(yù)測值向量H(x)；第2階段構(gòu)建標(biāo)簽依賴關(guān)系圖，在此圖上執(zhí)行重啟隨機游走算法，挖掘標(biāo)簽之間潛在的語義關(guān)系，算法收斂時即可得到文本隸屬各個標(biāo)簽的概率向量。

2.2 基于語義網(wǎng)WordNet的相似度圖

基于Wordnet3.0構(gòu)建的相似度圖[13,14]是一個有向加權(quán)圖G1=〈V1,E1〉，用來計算圖中頂點之間的語義相似度。其中，V1=itemsset∪senseset，itemsset集合由表示詞項的節(jié)點item構(gòu)成，senseset集合由表示含義的節(jié)點sense構(gòu)成。含義節(jié)點之間、含義節(jié)點與詞項節(jié)點之間以及詞項節(jié)點之間連有向邊〈vi,vj〉∈E1，邊上的權(quán)重記為wij。如圖1所示，itemsset={adventure,thriller,action}，senseset={“document with 100 non-noise words ‘a(chǎn)dventure’ appearing 2 times and the ‘Thriller’ appearing 1 time and the word ‘love’ appearing 1 time”,“a wild and exciting undertaking lawful”,“take a risk hope of…”,“something that people do or cause to happen” }。從節(jié)點“adventure”指向第1個含義節(jié)點的權(quán)值表示某人需要單詞“adventure”的信息，那么他對該詞的第1個含義節(jié)點感興趣的概率是0.92。而由含義節(jié)點指向節(jié)點“adventure”的權(quán)值為1，即某人看到含義節(jié)點中的任意一個，一定會想到單詞“adventure”。 所以，相似度圖又可以稱為概率圖，邊〈vi,vj〉反映了一種條件概率，表示看到當(dāng)前節(jié)點vi的條件下聯(lián)想到節(jié)點vj的概率。

Figure 1 Similarity graph based on WordNet

2.3 重啟隨機游走模型

重啟隨機游走模型RWR(Random Walk with Restart)[15]是遍歷圖的一個隨機過程，其基本思想是：從一個或一系列頂點開始遍歷一個圖，在任意一個頂點，遍歷者將以概率1-α隨機選擇與該頂點相鄰的頂點，或以概率α隨機跳躍到圖中的任何一個頂點，每次游走后得到的概率分布刻畫了圖中每個頂點被訪問到的可能性，反復(fù)迭代這一過程直到收斂于一個穩(wěn)定的概率分布。其數(shù)學(xué)表示為：

Pt+1=(1-α)·C·Pt+α·Q

(2)

其中，Pt表示第t步時達到的概率分布向量；C是概率轉(zhuǎn)移矩陣；α是重啟因子，即直接回到出發(fā)頂點的概率；Q是重啟向量，本文對應(yīng)為初始預(yù)測向量。

3 多標(biāo)簽文本分類算法設(shè)計

本文提出的多標(biāo)簽分類算法SGaRW分為2個階段。第1階段根據(jù)文本內(nèi)容創(chuàng)建相似度圖，計算文本與標(biāo)簽集合之間的初始預(yù)測值H(x)；第2階段構(gòu)建標(biāo)簽依賴圖，并在此圖上進行隨機游走，挖掘標(biāo)簽集合間的潛在關(guān)系。當(dāng)游走概率趨于穩(wěn)定時，即可得到文本的預(yù)測標(biāo)簽集合。

3.1 樣本與標(biāo)簽集合之間的初始預(yù)測值

本文將一篇短文本看作一個含義節(jié)點，訓(xùn)練文本的各個標(biāo)簽映射為詞項節(jié)點，創(chuàng)建相似度圖，則任意短文本與標(biāo)簽之間的相似性可用式(3)和式(4)計算：

cor(vdoc,vlabel)=∑Apt(vdoc|vlabel)

(3)

Apt(vdoc|vlabel)=∏P(vi|vj)

(4)

其中，節(jié)點序列pt=〈vdoc,…,vi,vj,…,vlabel〉表示從vdoc到vlabel的一條有向簡單路徑,ppt(vi|vj)是相似度圖上vi和vj之間邊上的權(quán)重，用于計算2節(jié)點之間的親密程度。Apt(vdoc|vlabel)表示vdoc到vlabel在簡單路徑pt上的親密程度。根據(jù)馬爾可夫模型，Apt(vdoc|vlabel)是該有向路徑上所有相鄰邊上權(quán)值的乘積。所以，圖中vdoc和vlabel的單向相關(guān)性就是從節(jié)點vdoc到節(jié)點vlabel的所有路徑上Apt(vdoc|vlabel)之和。隨著路徑長度增加，條件概率的值將減小，路徑越長，2個節(jié)點親密的程度越小。

接下來，本文使用均值度量2個節(jié)點之間的相似性：

correlation(vdoc,vlabel)=

(5)

經(jīng)過以上步驟，即可得到樣本x與某標(biāo)簽yi之間的初始預(yù)測值，記為hi(x)，即：

hi(x)=correlation(x,yi)

(6)

考慮所有的標(biāo)簽，即可得到樣本x與標(biāo)簽集合Y的相關(guān)分?jǐn)?shù)，如式(7)所示：

H(x)=[h1(x),h2(x),…,hm(x)]T

(7)

3.2 在標(biāo)簽依賴圖上隨機游走

3.2.1 標(biāo)簽與標(biāo)簽之間的依賴關(guān)系

本文使用圖2所示的無向圖來編碼標(biāo)簽之間的依賴關(guān)系，記為G2=(V2,E2)，其中，V2是數(shù)據(jù)集上所有標(biāo)簽構(gòu)成的節(jié)點集合，E2是邊集，若標(biāo)簽yi和yj同時標(biāo)記文本x，則在yi和yj之間增加一條邊。邊上的權(quán)值記為wij，定義為同時擁有標(biāo)簽yi和yj的文本個數(shù)，如式(8)所示：

(8)

Figure 2 Label graph

無向圖G2的鄰接矩陣S是q×q的對稱矩陣，如圖3所示，q是標(biāo)簽依賴圖中的頂點數(shù)。本文用式(9)對其進行非對稱處理：

(9)

其中，sij是鄰接矩陣S中的元素，sj是S中第j列所有元素之和。得到非對稱化的鄰接矩陣如圖4所示。

Figure 3 Adjacency matrix

Figure 4 Asymmetric adjacency matrix

3.2.2 標(biāo)簽依賴圖上的隨機游走

由于每一個標(biāo)簽的預(yù)測在一定程度上能傳播到其他標(biāo)簽上，因此，與樣本有關(guān)的標(biāo)簽預(yù)測不僅由樣本自身的特征決定，也會通過其他標(biāo)簽的預(yù)測被加強，標(biāo)簽的預(yù)測會經(jīng)過多次更新而不是被預(yù)測模型直接決定。本文利用在PageRank中的簡單策略重寫式(2)得到式(10)：

(10)

為了直觀地說明本文算法分類的過程，以圖1所示相似度圖的一部分為例進行說明。

首先根據(jù)式(3)和式(7)可以計算預(yù)測樣本doc與各個標(biāo)簽之間的單向相似性及標(biāo)簽的初始預(yù)測值：

cor(vdoc,vadventure)=0.11，cor(vadventure，vdoc)=0.04，hadventure(vdoc)=0.075。

同樣可以得到：hthriller(vdoc)=0.07，haction(vdoc)=0.075，hraomance(vdoc)=0.06。

因此,樣本doc與標(biāo)簽集合的相關(guān)分?jǐn)?shù)H(doc)=(0.075,0.07,0.075,0.06)T。

然后再根據(jù)標(biāo)簽依賴圖計算狀態(tài)轉(zhuǎn)移矩陣S(如圖4所示)。若α= 0.15，P= (0.25,0.25,0.25,0.25)T。

按照式(10)迭代直至滿足收斂條件，得到：

P(Y)doc=(0.68752828,0.3993173,0.1124934, 0.80029032)T

由此可知，樣本doc最可能的標(biāo)簽是adventure和thriller。

4 實驗結(jié)果與分析

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

為了驗證本文算法的分類性能，使用2個多標(biāo)簽分類文本數(shù)據(jù)Movies 和 AAPD(Arxiv Academic Paper Dataset)進行實驗，其中標(biāo)簽密度[1]表示每個樣本的平均標(biāo)簽數(shù)。

Movies來自IMDB實驗室人工采集的2 011條英文電影簡介和對應(yīng)的36個主題標(biāo)簽，標(biāo)簽密度為2.97。

AAPD數(shù)據(jù)集收集了計算機科學(xué)領(lǐng)域的55 840篇論文摘要和對應(yīng)的54個主題標(biāo)簽，標(biāo)簽密度為2.41。

4.2 評價標(biāo)準(zhǔn)

傳統(tǒng)的單分類算法性能評價指標(biāo)，如查全率、查準(zhǔn)率無法直接用于評價多標(biāo)簽算法的分類性能。因此，本文將采用以下3種指標(biāo)來衡量所提算法的性能。

(1)漢明損失(Hamming Loss)。

漢明損失[16]是評估誤分類的實例-標(biāo)簽對多少的一種評價指標(biāo)，即屬于該樣本的標(biāo)簽未出現(xiàn)在該類標(biāo)簽集合中而不屬于的標(biāo)簽卻出現(xiàn)。該指標(biāo)的值越小，表示分類性能越優(yōu)，其值為零時性能最優(yōu)(公式和實驗部分簡記為H_loss)。

(11)

(2) 杰卡德相似系數(shù)(Jaccard Index)。

杰卡德相似系數(shù)[17]用來度量2個集合之間的相似性，它被定義為2個集合A和B交集的元素個數(shù)除以并集的元素個數(shù)。該指標(biāo)取值越大，分類性能越優(yōu)，當(dāng)其取值為1時性能最優(yōu)。

(12)

(3) 精確度(Accuracy)。

(13)

4.3 實驗結(jié)果

為了評測本文算法在多標(biāo)簽文本分類方面的性能，精心設(shè)計了以下3個實驗：(1)選擇不同的隨機游走收斂閾值α進行實驗，驗證不同的α得到不同的實驗結(jié)果，并確定最優(yōu)的α值；(2) 使用不同大小的訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)進行實驗，驗證數(shù)據(jù)規(guī)模對實驗結(jié)果的影響；(3)將本文算法與其他不同的多標(biāo)簽分類算法進行對比。

實驗1不同的α對實驗的影響。

本實驗在Movies數(shù)據(jù)集上采用留一法進行，驗證不同的α?xí)玫讲煌姆诸愋阅?。具體地，隨機抽取1個樣本作為測試集，剩余的2 010條數(shù)據(jù)全部作為訓(xùn)練集，總共抽取了600次測試數(shù)據(jù)，最后將得到的600組實驗的平均值作為最后的結(jié)果進行分析。在每組實驗中，參數(shù)α分別取0.000 1,0.000 07,0.000 04,0.000 01進行實驗，結(jié)果如表1所示。

Table 1 Experimental results with different α

由表1可以看出，α=0.00007時H_loss和Jaccard這2個指標(biāo)都達到了最大值，Accuracy略微低一點。總體來看，綜合性能指標(biāo)最優(yōu)，因此在后面的2個實驗中，α的值均設(shè)定為0.000 07。

由表2可以看出，當(dāng)測試集的大小為500，訓(xùn)練集v的大小為1 500時，其H_loss和Jaccard均達到最好的情況，Accuracy略低。另外，為了表現(xiàn)其他指標(biāo)的正比例增長趨勢所反映的含義，在圖5中繪制了1-H_loss的值來體現(xiàn)算法性能。 AAPD數(shù)據(jù)集上的實驗結(jié)果如圖5所示，隨著訓(xùn)練集規(guī)模不斷增大，1-H_loss的值不斷減小，但是降低程度不明顯。而杰卡德相似性系數(shù)和準(zhǔn)確率不斷增加。當(dāng)訓(xùn)練集規(guī)模為40 000時，上升趨勢趨于平穩(wěn)?？傮w來看，測試集規(guī)模為1 000時得到的實驗結(jié)果比測試集規(guī)模為3 000 時的實驗結(jié)果好。

Table 2 Experimental results on Movies

實驗2數(shù)據(jù)集的規(guī)模對實驗結(jié)果的影響。

因漢明損失是用于量化基于單個標(biāo)簽的分類誤差，該指標(biāo)的值越小，表示分類性能越優(yōu)。

Figure 5 Experimental results on AAPD

實驗3不同算法的性能對比。

本文選擇與BR、ML-KNN、CC、CLLIFT[19]和LSFLC[20]等算法進行對比。其中，ML-KNN 中k=20，CLLIFT中比率參數(shù)δ設(shè)置為0.1，其他均采用算法的默認(rèn)參數(shù)。各算法在AAPD數(shù)據(jù)集上的結(jié)果如圖6所示。

Figure 6 Performance comparison of each algorithm on AAPD

從圖6可以看出，不論是Accuracy值，還是漢明損失值和杰卡德相似度值，SGaRW算法實現(xiàn)多標(biāo)簽分類的效果是最好的。CLLIFT盡管也考慮了標(biāo)簽信息，但僅僅作為輔助信息，而SGaRW則是通過在標(biāo)簽依賴圖上進行隨機游走，考慮了標(biāo)簽與標(biāo)簽之間潛在的語義聯(lián)系。并且，SGaRW算法使不屬于該文本的標(biāo)簽盡量少地出現(xiàn)在標(biāo)簽集合中，從而降低錯誤率。只是在AAPD數(shù)據(jù)集上，由于數(shù)據(jù)稠密的特性，SGaRW算法與BR、ML-KNN、CLLIFT等算法在Accuracy指標(biāo)上的差異度略小。

5 結(jié)束語

本文提出了一種融合相似度圖和隨機游走模型的多標(biāo)簽分類算法SGaRW，能夠有效解決短文本多標(biāo)簽分類問題。算法利用外部知識庫WordNet提供的先驗信息構(gòu)建相似度圖，在其上計算標(biāo)簽與文本之間的初始匹配值；然后基于數(shù)據(jù)的已有標(biāo)簽建立標(biāo)簽依賴圖，并在圖上執(zhí)行重啟隨機游走，最終確定預(yù)測文本的類別標(biāo)簽。由于SGaRW算法中相似度圖的構(gòu)建只考慮了名詞、動詞和形容詞這幾種主要實例，造成部分輔助信息的丟失，學(xué)習(xí)過程加長，可能會降低最終的分類精度。下一步研究的重點將考慮增加數(shù)據(jù)集規(guī)模，引入短文本語義理解、句法分析等技術(shù)來提升短文本多標(biāo)簽分類性能，也會考慮進一步優(yōu)化算法。