融合相似度圖和隨機(jī)游走模型的多標(biāo)簽短文本分類算法*

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

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

1 引言

傳統(tǒng)的單標(biāo)簽分類學(xué)習(xí)是指每一個(gè)樣本實(shí)例擁有唯一的一個(gè)類別標(biāo)簽，其中每一個(gè)標(biāo)簽屬于一個(gè)互斥的標(biāo)簽集合L(|L|>1)。但是，在實(shí)際應(yīng)用中，普遍存在一條數(shù)據(jù)可能同時(shí)屬于多個(gè)不同類別的情況，這類數(shù)據(jù)被稱作多標(biāo)簽數(shù)據(jù)[1]，比如，一篇新聞報(bào)道可以同時(shí)屬于“娛樂”類別和“科技”類別，一部影片可以同時(shí)屬于“動(dòng)作片”和“驚悚片”。和傳統(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)前的研究熱點(diǎn)和難點(diǎn)，在文本分類、定向營(yí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ù)分類算法對(duì)轉(zhuǎn)換后的數(shù)據(jù)進(jìn)行分類。BR(Binary Relevance)[3]是一種典型的問題轉(zhuǎn)換算法，它將每個(gè)標(biāo)簽的預(yù)測(cè)看作是一個(gè)獨(dú)立的單分類問題，并為每個(gè)標(biāo)簽訓(xùn)練一個(gè)獨(dú)立的分類器，用所有訓(xùn)練數(shù)據(jù)對(duì)每個(gè)分類器進(jìn)行訓(xùn)練。但是，這種算法忽略了標(biāo)簽之間的相互關(guān)系，往往無法達(dá)到令人滿意的分類效果。文獻(xiàn)[4]提出了一種針對(duì)DBR(Dependent Binary Relevance)的修剪方法，使用Phi系數(shù)函數(shù)來估計(jì)標(biāo)簽之間的相關(guān)度，以去除不相關(guān)的標(biāo)簽。Liu等[5]提出一種基于動(dòng)態(tài)規(guī)劃的分類器鏈CC-DP(Classifier Chain-Dynamic Programing))算法和貪婪的分類器鏈(CC-Greedy)算法搜索全局最優(yōu)的標(biāo)簽，彌補(bǔ)了CC(Classifier Chain)算法[6]對(duì)標(biāo)簽選擇敏感的缺陷。另一種思路是改進(jìn)算法，即改進(jìn)已有單標(biāo)簽學(xué)習(xí)算法以解決多標(biāo)簽學(xué)習(xí)問題。如ML-KNN算法[7]通過統(tǒng)計(jì)得出每個(gè)標(biāo)簽的先驗(yàn)概率，對(duì)標(biāo)簽集合Y中的每個(gè)標(biāo)簽λ，分別計(jì)算樣本x有標(biāo)簽λ和沒有標(biāo)簽λ的概率，進(jìn)而預(yù)測(cè)x是否具有標(biāo)簽λ。Tsoumakas等[8]提出RAkEL (RAndom k labELsets)方法將初始標(biāo)簽集分解為若干個(gè)小的隨機(jī)子集，并利用Label Powerset算法[9]訓(xùn)練分類器。除此之外，其他研究者也利用各種方法進(jìn)行多標(biāo)簽分類的研究[10,11]。

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

2 相關(guān)工作

2.1 多標(biāo)簽分類

從本質(zhì)上講，多標(biāo)簽分類可被看作是一個(gè)標(biāo)簽排序問題[12]。根據(jù)測(cè)試樣本與每個(gè)類別標(biāo)簽之間的相關(guān)度對(duì)其進(jì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)簽集合。因此，對(duì)樣本x的標(biāo)簽預(yù)測(cè)可以表示成如下所示的向量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í)得到一個(gè)多標(biāo)簽分類器h:X→2Y，對(duì)于給定的任意新樣本x，分類器能預(yù)測(cè)該樣本隸屬的標(biāo)簽集合。

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

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

基于Wordnet3.0構(gòu)建的相似度圖[13,14]是一個(gè)有向加權(quán)圖G1=〈V1,E1〉，用來計(jì)算圖中頂點(diǎn)之間的語義相似度。其中，V1=itemsset∪senseset，itemsset集合由表示詞項(xiàng)的節(jié)點(diǎn)item構(gòu)成，senseset集合由表示含義的節(jié)點(diǎn)sense構(gòu)成。含義節(jié)點(diǎn)之間、含義節(jié)點(diǎn)與詞項(xiàng)節(jié)點(diǎn)之間以及詞項(xiàng)節(jié)點(diǎn)之間連有向邊〈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é)點(diǎn)“adventure”指向第1個(gè)含義節(jié)點(diǎn)的權(quán)值表示某人需要單詞“adventure”的信息，那么他對(duì)該詞的第1個(gè)含義節(jié)點(diǎn)感興趣的概率是0.92。而由含義節(jié)點(diǎn)指向節(jié)點(diǎn)“adventure”的權(quán)值為1，即某人看到含義節(jié)點(diǎn)中的任意一個(gè)，一定會(huì)想到單詞“adventure”。 所以，相似度圖又可以稱為概率圖，邊〈vi,vj〉反映了一種條件概率，表示看到當(dāng)前節(jié)點(diǎn)vi的條件下聯(lián)想到節(jié)點(diǎn)vj的概率。

Figure 1 Similarity graph based on WordNet

2.3 重啟隨機(jī)游走模型

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

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

(2)

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

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

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

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

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

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

(3)

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

(4)

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

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

correlation(vdoc,vlabel)=

(5)

經(jīng)過以上步驟，即可得到樣本x與某標(biāo)簽yi之間的初始預(yù)測(cè)值，記為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)簽依賴圖上隨機(jī)游走

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é)點(diǎn)集合，E2是邊集，若標(biāo)簽yi和yj同時(shí)標(biāo)記文本x，則在yi和yj之間增加一條邊。邊上的權(quán)值記為wij，定義為同時(shí)擁有標(biāo)簽yi和yj的文本個(gè)數(shù)，如式(8)所示：

(8)

Figure 2 Label graph

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

(9)

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

Figure 3 Adjacency matrix

Figure 4 Asymmetric adjacency matrix

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

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

(10)

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

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

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)簽依賴圖計(jì)算狀態(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 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

4.2 評(píng)價(jià)標(biāo)準(zhǔn)

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

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

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

(11)

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

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

(12)

(3) 精確度(Accuracy)。

(13)

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

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

實(shí)驗(yàn)1不同的α對(duì)實(shí)驗(yàn)的影響。

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

Table 1 Experimental results with different α

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

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

Table 2 Experimental results on Movies

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

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

Figure 5 Experimental results on AAPD

實(shí)驗(yàn)3不同算法的性能對(duì)比。

本文選擇與BR、ML-KNN、CC、CLLIFT[19]和LSFLC[20]等算法進(jìn)行對(duì)比。其中，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算法實(shí)現(xiàn)多標(biāo)簽分類的效果是最好的。CLLIFT盡管也考慮了標(biāo)簽信息，但僅僅作為輔助信息，而SGaRW則是通過在標(biāo)簽依賴圖上進(jìn)行隨機(jī)游走，考慮了標(biāo)簽與標(biāo)簽之間潛在的語義聯(lián)系。并且，SGaRW算法使不屬于該文本的標(biāo)簽盡量少地出現(xiàn)在標(biāo)簽集合中，從而降低錯(cuò)誤率。只是在AAPD數(shù)據(jù)集上，由于數(shù)據(jù)稠密的特性，SGaRW算法與BR、ML-KNN、CLLIFT等算法在Accuracy指標(biāo)上的差異度略小。

5 結(jié)束語

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