李校林，王 成

(1.重慶郵電大學(xué)通信與信息工程學(xué)院，重慶 400065；2.重慶郵電大學(xué)通信新技術(shù)應(yīng)用研究中心，重慶 400065； 3.重慶信科設(shè)計(jì)有限公司，重慶 400021)

1 引言

隨著網(wǎng)絡(luò)的快速發(fā)展，網(wǎng)頁(yè)新聞機(jī)構(gòu)或社交網(wǎng)絡(luò)隨時(shí)都會(huì)產(chǎn)生大量的電子文本[1 - 3]。在這種情況下，文本分類TC(Text Classification)成為發(fā)現(xiàn)和分類文檔的關(guān)鍵技術(shù)[4,5]。

TC是一種將未標(biāo)記的文本文檔自動(dòng)分配到預(yù)定義類別的方法。近年來(lái)由于文本檢測(cè)、垃圾郵件過(guò)濾、作者識(shí)別、生物信息和文檔識(shí)別等數(shù)據(jù)處理需求的增長(zhǎng)，TC越來(lái)越受到關(guān)注并被廣泛應(yīng)用于各個(gè)領(lǐng)域[6 - 10]。多標(biāo)簽分類是1個(gè)實(shí)例可以同時(shí)分為多個(gè)類別[11]的一種方法。例如1篇關(guān)于基督教會(huì)對(duì)“達(dá)芬奇密碼”電影發(fā)行的報(bào)紙文章可同時(shí)標(biāo)記為“宗教”和“藝術(shù)”2種類別。

在過(guò)去幾年中，學(xué)者們已經(jīng)提出了大量算法來(lái)學(xué)習(xí)多標(biāo)簽數(shù)據(jù)。多標(biāo)簽學(xué)習(xí)算法可分為2類[12]：(1)問(wèn)題轉(zhuǎn)換算法；(2)自適應(yīng)算法。第1類算法將多標(biāo)簽學(xué)習(xí)問(wèn)題轉(zhuǎn)化為其他成熟學(xué)習(xí)場(chǎng)景。代表方法有二元相關(guān)性BR(Binary Relevance)[13]、標(biāo)準(zhǔn)校準(zhǔn)標(biāo)簽排名CLR(Calibrated Label Ranking)[14]和隨機(jī)k-標(biāo)簽集(Random k-labelsets)[15]。第2類算法通過(guò)調(diào)整常用學(xué)習(xí)技術(shù)直接處理多標(biāo)簽數(shù)據(jù)來(lái)解決多標(biāo)簽學(xué)習(xí)問(wèn)題。代表性算法包括多標(biāo)簽k-最近鄰算法ML-KNN(Multi-Label K-Nearest Neighbor)[16]、多標(biāo)簽決策樹(shù)ML-DT(Multi-Label Decision Tree)[17]和排名支持向量機(jī)Rank-SVM(Ranking Support Vector Machine)[18]。

2類算法都有各自的優(yōu)缺點(diǎn)。問(wèn)題轉(zhuǎn)換算法具有低計(jì)算復(fù)雜度的優(yōu)點(diǎn)。然而，當(dāng)數(shù)據(jù)非常大并且導(dǎo)致較低的分類準(zhǔn)確度時(shí)，它將受到類不平衡的影響。自適應(yīng)算法可以通過(guò)考慮每個(gè)標(biāo)簽有效地解決類不平衡問(wèn)題，但計(jì)算復(fù)雜度非常高。為了解決這些問(wèn)題，本文提出了一種基于質(zhì)心的多標(biāo)簽文本分類模型ML-GM(Multi-Label Gravitation Model)。

該模型的提出是基于質(zhì)心分類器并參考GM(Gravitation Model)[19]。由于在該模型中質(zhì)心覆蓋的區(qū)域?qū)⒃谒蟹较蛏暇鹊財(cái)U(kuò)展或收縮，可以直接緩解類不平衡問(wèn)題。而基于質(zhì)心的分類器CBC(Centroid Based Classifier)[19]的計(jì)算復(fù)雜度在訓(xùn)練階段是線性的，因此它比其他TC方法更有效，這一優(yōu)勢(shì)對(duì)于在線文本分類任務(wù)很重要[20 - 23]。 實(shí)驗(yàn)結(jié)果表明，ML-GM在平均精確度、AUC、1-錯(cuò)誤率和漢明損失方面優(yōu)于現(xiàn)有的多標(biāo)簽分類算法。

2 相關(guān)工作

2.1 相關(guān)問(wèn)題

盡管文本分類方法已被研究了很多年，但是很少有作者在CBC中研究過(guò)這個(gè)任務(wù)[24]?；贑BC分類高效的特點(diǎn)，本文提出了一種多標(biāo)簽文本分類模型，稱為多標(biāo)簽引力模型(ML-GM)。其主要思想是通過(guò)判斷未定義實(shí)例和質(zhì)心的相對(duì)引力是否屬于在訓(xùn)練階段學(xué)習(xí)的引力區(qū)間內(nèi)來(lái)執(zhí)行多標(biāo)簽分類?；谫|(zhì)心的多標(biāo)簽分類過(guò)程如圖1所示。

Figure 1 Flow chart of ML-GM classification圖1 ML-GM分類流程圖

2.2 質(zhì)心分類器

文檔由基于質(zhì)心的文本分類中的向量空間模型VSM(Vector Space Model)[25]表示。比如文本dj=(ω1j,…,ωkj)，k是術(shù)語(yǔ)(特征)集的大小，ωij代表文檔dj中第i個(gè)術(shù)語(yǔ)ti的權(quán)重，不同術(shù)語(yǔ)在一個(gè)文本中具有不同的重要性。術(shù)語(yǔ)加權(quán)是通過(guò)為術(shù)語(yǔ)指定適當(dāng)?shù)臋?quán)重來(lái)提高TC的有效性的重要步驟。在術(shù)語(yǔ)加權(quán)方法中，術(shù)語(yǔ)頻率和反文檔頻率TFIDF(Term Frequency and Inverse Document Frequency)是最著名和最常用的方法，如式(1)所示[19]：

(1)

其中，tf(ti,dj)是術(shù)語(yǔ)ti在文檔dj中出現(xiàn)的頻率，|D|是訓(xùn)練文檔的總數(shù)，|D(ti)|表示包含術(shù)語(yǔ)ti的文檔數(shù)。術(shù)語(yǔ)權(quán)重的規(guī)范化執(zhí)行方式如下所示：

(2)

2個(gè)文檔之間的相似性可以用余弦公式來(lái)測(cè)量：

(3)

其中，“·”表示向量的點(diǎn)積，‖d‖2表示d的L2范數(shù)。

質(zhì)心向量cj是通過(guò)對(duì)Cj類中所有文檔向量進(jìn)行求和并進(jìn)行歸一化。質(zhì)心向量可以用式(4)來(lái)表示：

(4)

文檔向量和質(zhì)心向量之間的相似性可以用余弦公式進(jìn)行測(cè)量：

(5)

最后，未定義文檔將被分配到最相似的類別：

(6)

3 ML-GM方法

3.1 GM

GM[19]是受牛頓的萬(wàn)有引力定律啟發(fā)而提出的。在GM中，類CA和類CB可以看作對(duì)象A和對(duì)象B，未定義文檔d可以看作對(duì)象S。rA和rB分別代表S到A和B之間的距離。對(duì)類CA和類CB具有相同吸引力的分類超平面定義如式(7)所示：

(7)

MA*Sim(d,cA)=MB*Sim(d,cB)

(8)

在測(cè)試階段，未定義文檔和Cj類質(zhì)心之間的力可以通過(guò)式(9)描述：

F(d,cj)=Mj*Sim(d,cj)

(9)

其中，Mj為Cj類的質(zhì)量因子。

然后，分類器將未定義的文檔分配給其質(zhì)心向量與文檔最相似的類別。

質(zhì)量因子M可以在訓(xùn)練階段通過(guò)式(10)和式(11)來(lái)學(xué)習(xí)得到：

Mi:=Mi+ζ

(10)

Mj:=Mj-ζ

(11)

其中，ζ是一個(gè)常數(shù)，用來(lái)控制迭代強(qiáng)度。

算法1隨機(jī)學(xué)習(xí)質(zhì)量(M)法

輸出：類的質(zhì)量因子。

1：forj=1,j≤Pdo

2：Mj←1;

3：endfor

4：Rnew←1;

5：Repeat～I(xiàn)ter++;

6：error←0;

7：Rold←Rnew;

8：forn=1,n≤Ndo

11：Mj←Mj+ζ;

13：error++;

14：endif

15：endfor

16：Rnew←error/N;

17：Untilε>(Rold-Rnew)/RoldorIter>Max

18：returnMj～(1≤j≤P);

3.2 多標(biāo)簽引力模型

本文對(duì)GM進(jìn)行改進(jìn)提出了基于質(zhì)心的多標(biāo)簽引力模型(ML-GM)，在ML-GM中，Cj類質(zhì)心和此類中文本之間的相似性可以用引力來(lái)表示，可以在此類中得出一個(gè)引力區(qū)間FjINT=[Fjmin,Fjmax]。Fjmin和Fjmax是Cj類質(zhì)心與類中文本的最大和最小引力。在測(cè)試階段，計(jì)算未標(biāo)記文檔與每個(gè)類質(zhì)心之間的相似性。

未定義文檔與每個(gè)類質(zhì)心之間的吸引力可以用F(d,cj)來(lái)表示，如式(12)所示：

F(d,cj)=Mj*Sim(d,cj)

(12)

其中，Mj表示Cj類的質(zhì)量因子，可以由式(10)和式(11)計(jì)算得出。Sim(d,cj)是衡量文檔d和類質(zhì)心之間相似性的指標(biāo)，其代表1/r2。當(dāng)F(d,cj)∈FjINT時(shí)，則未定義文檔d被分配到Cj類中，實(shí)現(xiàn)多標(biāo)簽文本分類。

圖1所示為ML-GM分類流程圖。整個(gè)分類過(guò)程可分為2個(gè)步驟：訓(xùn)練階段和測(cè)試階段。第1步訓(xùn)練本文分類模型，第2步測(cè)試文本分類模型。

第1步：訓(xùn)練階段。

培訓(xùn)文件：從語(yǔ)料庫(kù)準(zhǔn)備的培訓(xùn)文件。

預(yù)處理：初始化并過(guò)濾語(yǔ)料庫(kù)中的單詞。例如，使用停用詞列表處理文檔中具有高頻但具有含義的詞，并在整個(gè)文本中處理低頻率的罕見(jiàn)詞。

特征處理：使用TFIDF方法對(duì)文檔進(jìn)行矢量處理。

訓(xùn)練模型：基于算法2創(chuàng)建ML-GM模型，該模型可以對(duì)多標(biāo)簽文本進(jìn)行分類。

第2步：測(cè)試階段。

測(cè)試文檔：在語(yǔ)料庫(kù)中準(zhǔn)備的測(cè)試文檔。

預(yù)處理：文本的處理方式與訓(xùn)練階段的預(yù)處理步驟相同。

特征處理：使用TFIDF方法對(duì)文本進(jìn)行矢量處理。

相似性估計(jì)：在此步驟中，將文檔向量與每個(gè)類中的引力區(qū)間進(jìn)行比較以進(jìn)行分類。

算法2總結(jié)了ML-GM訓(xùn)練階段的代碼。在該模型訓(xùn)練階段中，q和p分別表示訓(xùn)練數(shù)據(jù)集中的類別數(shù)和類中的實(shí)例數(shù)。如算法2所示，基于多標(biāo)簽訓(xùn)練示例，第1～3行使用式(4)計(jì)算每個(gè)實(shí)例的質(zhì)心。第4～8行通過(guò)式(9)計(jì)算每個(gè)類質(zhì)心與該類文檔中的相似性引力值。最后，將每個(gè)類別中的引力值相互比較并返回1個(gè)引力區(qū)間。

算法2ML-GM的訓(xùn)練階段

輸入:q個(gè)類別和p個(gè)樣本的數(shù)據(jù)。

輸出:引力區(qū)間。

1：forj=1,…,q

2： 用式(4)計(jì)算質(zhì)心cj；

3：endfor

4：forj=1,…,q

5：fori=1,…,p

6： 用式(9)計(jì)算得出F(d,cj)；

7：endfor

8：endfor

9：ReturnFjINT=[Fjmin,Fjmax]

為了更好地解釋本文所提出的模型，給出分類模型示例圖，如圖2所示，并詳細(xì)地闡述如何進(jìn)行多標(biāo)簽分類。

Figure 2 Diagram of classfication圖2 分類模型圖

示例：在訓(xùn)練階段，通過(guò)式(4)計(jì)算每個(gè)類別的質(zhì)心(例如cA,cB,cD,cE)。接下來(lái)，計(jì)算預(yù)處理文本(例如dA1,dA2;dS1,dS2;dD1,dD2;dE1,dE2)和類質(zhì)心之間的相似性，用引力來(lái)表示(例如dA1和cA之間的相似性為引力值FA1)。最后，在每個(gè)類中得出1個(gè)文本與類質(zhì)心的相似性引力區(qū)間FjINT=[Fimin,Fimax]。其中，F(xiàn)jmin和Fimax是Cj類中文本向量與類質(zhì)心之間的最小和最大相似性引力值。在測(cè)試階段，預(yù)處理的未定義文檔d和質(zhì)心之間的相似性引力值F(d,cj)將由式(12)計(jì)算得出。最后，將此引力值與Cj類中的相似性引力區(qū)間進(jìn)行比較，從而進(jìn)行文本分類。當(dāng)F(d,cj)=FjINT時(shí)，未定義文檔d被分配到Cj類中，實(shí)現(xiàn)多標(biāo)簽文本分類。

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

本節(jié)進(jìn)行了一些實(shí)驗(yàn)來(lái)檢驗(yàn)本文提出的多標(biāo)簽分類模型的性能。應(yīng)用任務(wù)主要是網(wǎng)頁(yè)分類。采用ML-KNN[16]、BR[6]和CLR[14]與ML-GM進(jìn)行比較。

4.1 評(píng)估指標(biāo)和實(shí)驗(yàn)數(shù)據(jù)

本文使用平均精確度(Average Accuracy)、漢明損失(Hamming Loss)、1-錯(cuò)誤率(One-error)和AUC[13]來(lái)評(píng)估多標(biāo)簽分類模型的性能。平均精確度評(píng)估特定標(biāo)簽上方列出的標(biāo)簽的平均分?jǐn)?shù)。漢明損失評(píng)估錯(cuò)誤分類的實(shí)例-標(biāo)簽對(duì)的分?jǐn)?shù)。1-錯(cuò)誤率評(píng)估頂級(jí)標(biāo)簽不在相關(guān)標(biāo)簽集中的示例的分?jǐn)?shù)。AUC被稱為ROC曲線下的區(qū)域，并且與每個(gè)實(shí)例的標(biāo)簽排名性能相關(guān)。平均精確度和AUC的值越大，而漢明損失和1-錯(cuò)誤率的值越小，性能越好。在這個(gè)實(shí)驗(yàn)中，使用雅虎的網(wǎng)絡(luò)數(shù)據(jù)集來(lái)確認(rèn)本文提出的模型的有效性。

表1所示為數(shù)據(jù)集的基本信息。數(shù)據(jù)集由11個(gè)頂級(jí)類別(例如“Business”和“Science”)組成。根據(jù)類別的不同隨機(jī)選取了不同數(shù)量的樣本作為訓(xùn)練文本。

Table 1 Description of datasets表1 數(shù)據(jù)集基本信息

圖3和圖4用柱形圖的形式展示了表1中的數(shù)據(jù)信息。從圖3中可以看出，這些標(biāo)簽的數(shù)量沒(méi)有差異,標(biāo)簽最少的類別是“Entertainment”。從圖4中可以看出，大約40%的實(shí)驗(yàn)數(shù)據(jù)被用作構(gòu)建分類模型的訓(xùn)練集，60%被用作測(cè)試集來(lái)測(cè)試分類方法的性能。

Figure 3 Label numbers of each dataset圖3 每個(gè)數(shù)據(jù)集的標(biāo)簽數(shù)

Figure 4 Instance numbers of each dataset圖4 每個(gè)數(shù)據(jù)集中的實(shí)例數(shù)

4.2 實(shí)驗(yàn)結(jié)果和分析

表2～表5分別給出了在Yahoo數(shù)據(jù)集上的平均精確度、AUC、漢明損失和1-錯(cuò)誤率的實(shí)驗(yàn)結(jié)果，其中最好的結(jié)果用黑體標(biāo)出。

Table 2 Average accuracy comparison of different classifiers表2 平均精確度比較

Table 3 AUC comparison of different classifiers 表3 AUC比較

Table 4 Hamming loss comparison of different classifiers 表4 漢明損失比較

Table 5 One-error comparison of different classifiers 表5 1-錯(cuò)誤率比較

與ML-KNN相比較：在所有11個(gè)數(shù)據(jù)集上ML-GM平均精確度、AUC、1-錯(cuò)誤率優(yōu)于ML-KNN的。對(duì)于漢明損失，ML-GM在9個(gè)數(shù)據(jù)集上是最好的，在數(shù)據(jù)集Education和Social上稍微低于ML-KNN的。與BR相比較：ML-GM在所有數(shù)據(jù)集上的評(píng)估數(shù)據(jù)都優(yōu)于BR的。與CLR相比較，在9個(gè)數(shù)據(jù)集上，ML-GM平均精確度表現(xiàn)最優(yōu)，而CLR在數(shù)據(jù)集Education和Society上表現(xiàn)最優(yōu)。對(duì)于AUC，ML-GM在所有數(shù)據(jù)集上都表現(xiàn)最優(yōu)。對(duì)于漢明損失，ML-GM在10個(gè)數(shù)據(jù)集上表現(xiàn)最優(yōu)，而CLR僅在數(shù)據(jù)集Science上表現(xiàn)最優(yōu)，但是ML-GM與CLR在此數(shù)據(jù)集上相差很小，大約為0.000 9。對(duì)于1-錯(cuò)誤率，ML-GM在8個(gè)數(shù)據(jù)集上表現(xiàn)最優(yōu)，而在數(shù)據(jù)集Art,Reference,Science上ML-GM要稍微差于CLR。但總的來(lái)說(shuō)，所提模型的性能大致優(yōu)于其他多標(biāo)簽分類模型。

另外，我們還比較了計(jì)算時(shí)間，如圖5所示為計(jì)算時(shí)間隨數(shù)據(jù)樣本數(shù)量增加的變化情況，初始樣本數(shù)量固定在n=500。

Figure 5 Computation time comparison of each model on different datasets圖5 各模型在不同數(shù)據(jù)集上的計(jì)算時(shí)間比較

總的來(lái)說(shuō)，ML-GM和BR的計(jì)算速度比CLR和BR快得多。從圖5a中可以看出，當(dāng)樣本數(shù)為500時(shí)，所有模型的計(jì)算時(shí)間非常接近。然而，ML-KNN和CLR的計(jì)算時(shí)間大于ML-KNN和BR的。BR和ML-GM之間的計(jì)算時(shí)間差異不是太大，時(shí)間增長(zhǎng)曲線非常相似。圖5c中，當(dāng)樣本數(shù)超過(guò)2 500時(shí)，ML-KNN計(jì)算時(shí)間迅速增加。研究發(fā)現(xiàn)，本文提出的多標(biāo)簽分類模型在計(jì)算效率方面優(yōu)于ML-KNN和CLR的，類似于BR的。

5 結(jié)束語(yǔ)

本文提出了一種新的多標(biāo)簽文本分類模型ML-GM。利用質(zhì)心分類器的線性技術(shù)復(fù)雜性來(lái)提高計(jì)算效率，并利用引力模型的均勻分布來(lái)解決類不平衡導(dǎo)致的分類精確度低的問(wèn)題。從實(shí)驗(yàn)中可以得出結(jié)論，本文提出的模型與其他分類模型比較，可以提高文本分類的準(zhǔn)確度，減少分類錯(cuò)誤。

但是，在ML-GM分類模型分類過(guò)程中，未考慮某一測(cè)試文本不屬于任何一個(gè)類時(shí)怎么處理。今后，我們將針對(duì)該問(wèn)題進(jìn)行研究。