一種基于質心的多標簽文本分類模型研究*

李校林，王 成

(1.重慶郵電大學通信與信息工程學院，重慶 400065；2.重慶郵電大學通信新技術應用研究中心，重慶 400065； 3.重慶信科設計有限公司，重慶 400021)

1 引言

隨著網絡的快速發展，網頁新聞機構或社交網絡隨時都會產生大量的電子文本[1 - 3]。在這種情況下，文本分類TC(Text Classification)成為發現和分類文檔的關鍵技術[4,5]。

TC是一種將未標記的文本文檔自動分配到預定義類別的方法。近年來由于文本檢測、垃圾郵件過濾、作者識別、生物信息和文檔識別等數據處理需求的增長，TC越來越受到關注并被廣泛應用于各個領域[6 - 10]。多標簽分類是1個實例可以同時分為多個類別[11]的一種方法。例如1篇關于基督教會對“達芬奇密碼”電影發行的報紙文章可同時標記為“宗教”和“藝術”2種類別。

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

2類算法都有各自的優缺點。問題轉換算法具有低計算復雜度的優點。然而，當數據非常大并且導致較低的分類準確度時，它將受到類不平衡的影響。自適應算法可以通過考慮每個標簽有效地解決類不平衡問題，但計算復雜度非常高。為了解決這些問題，本文提出了一種基于質心的多標簽文本分類模型ML-GM(Multi-Label Gravitation Model)。

該模型的提出是基于質心分類器并參考GM(Gravitation Model)[19]。由于在該模型中質心覆蓋的區域將在所有方向上均等地擴展或收縮，可以直接緩解類不平衡問題。而基于質心的分類器CBC(Centroid Based Classifier)[19]的計算復雜度在訓練階段是線性的，因此它比其他TC方法更有效，這一優勢對于在線文本分類任務很重要[20 - 23]。 實驗結果表明，ML-GM在平均精確度、AUC、1-錯誤率和漢明損失方面優于現有的多標簽分類算法。

2 相關工作

2.1 相關問題

盡管文本分類方法已被研究了很多年，但是很少有作者在CBC中研究過這個任務[24]。基于CBC分類高效的特點，本文提出了一種多標簽文本分類模型，稱為多標簽引力模型(ML-GM)。其主要思想是通過判斷未定義實例和質心的相對引力是否屬于在訓練階段學習的引力區間內來執行多標簽分類?；谫|心的多標簽分類過程如圖1所示。

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

2.2 質心分類器

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

(1)

其中，tf(ti,dj)是術語ti在文檔dj中出現的頻率，|D|是訓練文檔的總數，|D(ti)|表示包含術語ti的文檔數。術語權重的規范化執行方式如下所示：

(2)

2個文檔之間的相似性可以用余弦公式來測量：

(3)

其中，“·”表示向量的點積，‖d‖2表示d的L2范數。

質心向量cj是通過對Cj類中所有文檔向量進行求和并進行歸一化。質心向量可以用式(4)來表示：

(4)

文檔向量和質心向量之間的相似性可以用余弦公式進行測量：

(5)

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

(6)

3 ML-GM方法

3.1 GM

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

(7)

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

(8)

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

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

(9)

其中，Mj為Cj類的質量因子。

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

質量因子M可以在訓練階段通過式(10)和式(11)來學習得到：

Mi:=Mi+ζ

(10)

Mj:=Mj-ζ

(11)

其中，ζ是一個常數，用來控制迭代強度。

算法1隨機學習質量(M)法

輸出：類的質量因子。

1：forj=1,j≤Pdo

2：Mj←1;

3：endfor

4：Rnew←1;

5：Repeat～Iter++;

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 多標簽引力模型

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

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

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

(12)

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

圖1所示為ML-GM分類流程圖。整個分類過程可分為2個步驟：訓練階段和測試階段。第1步訓練本文分類模型，第2步測試文本分類模型。

第1步：訓練階段。

培訓文件：從語料庫準備的培訓文件。

預處理：初始化并過濾語料庫中的單詞。例如，使用停用詞列表處理文檔中具有高頻但具有含義的詞，并在整個文本中處理低頻率的罕見詞。

特征處理：使用TFIDF方法對文檔進行矢量處理。

訓練模型：基于算法2創建ML-GM模型，該模型可以對多標簽文本進行分類。

第2步：測試階段。

測試文檔：在語料庫中準備的測試文檔。

預處理：文本的處理方式與訓練階段的預處理步驟相同。

特征處理：使用TFIDF方法對文本進行矢量處理。

相似性估計：在此步驟中，將文檔向量與每個類中的引力區間進行比較以進行分類。

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

算法2ML-GM的訓練階段

輸入:q個類別和p個樣本的數據。

輸出:引力區間。

1：forj=1,…,q

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

3：endfor

4：forj=1,…,q

5：fori=1,…,p

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

7：endfor

8：endfor

9：ReturnFjINT=[Fjmin,Fjmax]

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

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

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

4 實驗

本節進行了一些實驗來檢驗本文提出的多標簽分類模型的性能。應用任務主要是網頁分類。采用ML-KNN[16]、BR[6]和CLR[14]與ML-GM進行比較。

4.1 評估指標和實驗數據

本文使用平均精確度(Average Accuracy)、漢明損失(Hamming Loss)、1-錯誤率(One-error)和AUC[13]來評估多標簽分類模型的性能。平均精確度評估特定標簽上方列出的標簽的平均分數。漢明損失評估錯誤分類的實例-標簽對的分數。1-錯誤率評估頂級標簽不在相關標簽集中的示例的分數。AUC被稱為ROC曲線下的區域，并且與每個實例的標簽排名性能相關。平均精確度和AUC的值越大，而漢明損失和1-錯誤率的值越小，性能越好。在這個實驗中，使用雅虎的網絡數據集來確認本文提出的模型的有效性。

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

Table 1 Description of datasets表1 數據集基本信息

圖3和圖4用柱形圖的形式展示了表1中的數據信息。從圖3中可以看出，這些標簽的數量沒有差異,標簽最少的類別是“Entertainment”。從圖4中可以看出，大約40%的實驗數據被用作構建分類模型的訓練集，60%被用作測試集來測試分類方法的性能。

Figure 3 Label numbers of each dataset圖3 每個數據集的標簽數

Figure 4 Instance numbers of each dataset圖4 每個數據集中的實例數

4.2 實驗結果和分析

表2～表5分別給出了在Yahoo數據集上的平均精確度、AUC、漢明損失和1-錯誤率的實驗結果，其中最好的結果用黑體標出。

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-錯誤率比較

與ML-KNN相比較：在所有11個數據集上ML-GM平均精確度、AUC、1-錯誤率優于ML-KNN的。對于漢明損失，ML-GM在9個數據集上是最好的，在數據集Education和Social上稍微低于ML-KNN的。與BR相比較：ML-GM在所有數據集上的評估數據都優于BR的。與CLR相比較，在9個數據集上，ML-GM平均精確度表現最優，而CLR在數據集Education和Society上表現最優。對于AUC，ML-GM在所有數據集上都表現最優。對于漢明損失，ML-GM在10個數據集上表現最優，而CLR僅在數據集Science上表現最優，但是ML-GM與CLR在此數據集上相差很小，大約為0.000 9。對于1-錯誤率，ML-GM在8個數據集上表現最優，而在數據集Art,Reference,Science上ML-GM要稍微差于CLR。但總的來說，所提模型的性能大致優于其他多標簽分類模型。

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

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

總的來說，ML-GM和BR的計算速度比CLR和BR快得多。從圖5a中可以看出，當樣本數為500時，所有模型的計算時間非常接近。然而，ML-KNN和CLR的計算時間大于ML-KNN和BR的。BR和ML-GM之間的計算時間差異不是太大，時間增長曲線非常相似。圖5c中，當樣本數超過2 500時，ML-KNN計算時間迅速增加。研究發現，本文提出的多標簽分類模型在計算效率方面優于ML-KNN和CLR的，類似于BR的。

5 結束語

本文提出了一種新的多標簽文本分類模型ML-GM。利用質心分類器的線性技術復雜性來提高計算效率，并利用引力模型的均勻分布來解決類不平衡導致的分類精確度低的問題。從實驗中可以得出結論，本文提出的模型與其他分類模型比較，可以提高文本分類的準確度，減少分類錯誤。

但是，在ML-GM分類模型分類過程中，未考慮某一測試文本不屬于任何一個類時怎么處理。今后，我們將針對該問題進行研究。