一種基于圖的層次多標記文本分類方法

摘 要:由于一個類別在層次樹上可能存在多個鏡像，基于層次樹來進行分類可能會導致不一致性。一種自然的解決方法是采用圖結構來描述類別關系，在現實生活中人們實際的描述方式也是如此。鑒于此，提出了一種直接基于圖的層次多標記分類方法，稱為GraphHMLTC。該方法利用有向無圈圖的拓撲排序而非樹的自頂向下的層次關系來確定類別之間的分類順序，并且該拓撲序根據分類情形進行動態維護。實驗表明，采用層次圖分類的GraphHMLTC方法比非層次分類方法的代表之一BoosTexter.MH在較大程度上改善了分類精度。該工作體現了基于層次圖的分類方法的可行性和優越性。

關鍵詞:文本分類; 層次分類; 多標記分類; 有向無圈圖; 拓撲排序

中圖分類號:TP181 文獻標志碼:A

文章編號:1001-3695(2010)03-0909-04

doi:10.3969/j.issn.1001-3695.2010.03.028

Graph-based method for hierarchical multi-lable text classification

LUO Jun

(Center of Computer Network， Guangdong Polytechnic Normal University， Guangzhou 510665， China)

Abstract:Most of existing hierarchical text classification methods is based on a hierarchical category tree. However， such a tree structure maybe leads to some kinds of inconsistency for the reason of multiple images of a category on it. A nature solution for this is to adopt a hierarchical graph structure， which is a practical way to depict category relationships in a real world. So this paper presented a novel method for multi-lable text classification directly based on a hierarchical graph， called GraphHMLTC. Determined the classification order among categories by a topological sorting of vertexes in a graph (in fact， a directed acyclic graph)， not by a hierarchical structure from top to down in a tree. Also， dynamically maintained the topological sorting according to the classification situation. Experiment results show that the method improves the classification accuracy in a great degree， compared to a representative of non-hierarchical multi-lable classification methods， BoosTexter.MH. Therefore， this work reveals that a graph-based classification method is feasible and superior.

Key words:text classification(TC); hierarchical classification; multi-lable classification; directed acyclic graph; topological sorting

近年來，文本分類(TC)的研究熱點主要集中在數據集傾斜(imbalanced data set)、標注瓶頸(label bottleneck)、層次分類、問題的非線性可分性(nonlinear separability)以及Web頁面分類(Web document categorization)等方面[1~3]。其中，層次分類是指多層類別關系下的分類問題，面對的類別間存在類似于樹或有向非循環圖的多層分級類別結構，可以更好地支持瀏覽和查詢，也使得部分規模較大的分類問題通過分治的方法得到更好的解決。更進一步，如果允許一個文檔的類別標記為層次類別結構中的0、1個或者多個類別，則稱為層次多標記文本分類[4~6]。

隨著基于學習的分類技術的進展，分類不一致性(classification inconsistency)問題日益受到人們的關注[7~9]。不一致性的現象多種多樣，其根源主要來自于兩個方面:分類方法本身和領域背景知識。前者如SVM層次分類方法[9]，文檔可能屬于某個兒子類別但不屬于其父親類別;后者主要是體現在用來描述類別關系的層次結構上。到目前為止，幾乎所有的層次文本分類方法[10~13]都采用樹型結構來描述類別關系，即層次樹(hierarchical tree)。層次樹提供了一種簡單且易于實現的描述方式，但是在類別較多且關系復雜的情況下會存在一些隱患。例如，經濟法既屬于經濟范疇又屬于法律范疇，這樣的一個類別在層次樹中既位于以經濟類別為根的子樹，同時也位于以法律為根的子樹。因此，層次樹最大的問題是面對同時屬于多個類別的子類別，勢必需要用不同的節點(即鏡像)來表示它，這可能產生同一類別在不同子樹中不一致的分類結果。

鑒于此，本文提出一種基于層次圖(hierarchical graph)的多標記文本分類方法。該方法利用有向無圈圖的拓撲排序而非樹的自頂向下的層次關系來確定類別間的分類順序。在層次圖中每個類別只對應一個節點，可以避免層次樹中一個類別對應多個節點可能導致的不一致;此外，層次圖中頂點拓撲序的動態維護也可以防止如SVM方法所導致的不一致性。據筆者所知，目前還沒有任何文本分類技術直接采用圖結構來進行層次分類，因此本文的方法是很有研究前景和應用價值的。

1 層次文本分類簡介

隨著待分類的類別數目增多，類別本身固有的層次結構在分類過程中越發突顯其重要性。層次文本分類的關鍵在于如何正確而有效地利用類別關系來指引分類過程。基本方法分為兩大類，即big-bang方法和top-down方法[10]。

在big-bang方法中，整個分類過程只使用一個分類器，將處于層次樹上的所有葉節點類別看成平等的類，本質上是一種單層分類(flat classification)，不能很好地應用類別間的關系。此外，分類器構造極其不靈活，一旦類別結構發生稍許變化就需要重新訓練。在top-down方法中，層次樹的每個節點都有一個分類器。文檔首先由根節點的分類器進行分類，然后傳遞給下層的一個或多個兒子節點;再由兒子節點的分類器進行分類，直至到達葉子節點或某個不能再分類的中間節點。該方法的最大缺點是容易阻斷問題(block problem)[8]。一旦父節點的分類器分類錯誤，文檔將不能傳遞給兒子節點的分類器。此外，因為要構造很多分類器，所以需要充足的訓練例，否則性能受影響。

在層次分類過程中，如果需要多標記分類則無疑增加分類任務的難度。層次的多標記分類即將實例標記為層次結構上的多個節點。多標記分類方法分為兩大類，即問題轉換方法和修改算法方法[4]。前者把多標記分類問題轉換為一個或多個單標記分類或回歸問題，后者擴展具體的學習算法來直接處理多標記數據。例如，Adaboost.MH輸出標記集合中屬于每個標記的確認度[14];ML-kNN對每個標記使用KNN算法然后輸出標記的排序[5，15];概率模型生成方法[16]對每個標記產生不同的詞;基于模型，多標記文檔可以表示為標記的單詞分布;模型的參數通過訓練例最大化后驗估計來學習，使用EM算法來計算哪些標記具有最大權值等。

2 層次圖

2.1 層次結構分類

Sun等人[10]將可采用的類別層次結構歸納為四種，即虛類別樹(virtual category tree)、類別樹(category tree)、虛有向無圈類別圖(virtual directed acyclic category graph)和有向無圈類別圖(directed acyclic category graph)。其中，在“虛”的層次結構中，文檔只能標記為葉子節點關聯的類別;而在非“虛”的層次結構中，文檔可以標記為中間節點或者葉子節點關聯的類別。

有向無圈類別圖是現實生活中最常用的類別結構，如Yahoo!或Open Directory Project等構建的網絡目錄結構等。但是為了提高效率，目前已有的大多數方法都基于(虛)類別樹，只有Frommholz[7]嘗試采用有向無圈類別圖來進行層次分類，但是是在后處理階段才考慮層次結構。非層次分類器先輸出文檔屬于每個類別的概率，然后根據類別之間的相鄰關系來調整這些概率值。由于分類過程依然是單層分類，降低了整體的分類性能。一些學習類別模型的方法[9]也將擴展到更通用的圖結構上。

2.2 層次樹的不足

當與某一類別相關聯的類別較多時，就容易產生如前所述的在類別層次樹上多個節點表示同一類別的現象，從而帶來分類不一致的隱患。例如，圖1是一棵對網頁進行分類的層次樹，根節點是一個虛節點，表示由所有網頁文檔組成的虛類別。其中的類別A和B既是類別P1的子類，也是類別P2的子類。按照top-down方法，對某篇文檔d自頂向下進行分類，可能會產生如下結果:

a)P1的分類器認為d不屬于P1，產生了阻斷(即d也不屬于A);與此同時，P2的分類器認為d屬于P2，繼而往下傳遞，最后標記為A。不同的子樹對同一類別產生了不同的判斷結果，這是第一種不一致現象。

b)假設分支節點的分類器最終是對葉子節點類別產生一個排序。在P1的子樹中，分類結果是d屬于B的概率高于屬于A的概率;而在P2的子樹中，分類結果是d屬于A的概率高于屬于B的概率。由于在不同子樹中進行分類，很難對兩個類別之間不同的排序結果進行統一處理，這是第二種不一致現象。

當然，還會存在由于樹結構所導致的其他不一致現象。這些不一致現象的根源來自于樹中不同節點可以表示同一類別，因此采用層次圖可以避免這些問題。

2.3 層次圖

層次圖是有向無圈圖，與層次樹一樣用來表示類別的種屬關系。有向無圈圖是不包含圈的有向圖，在貝葉斯分類方法中也經常使用，用來表示特征之間的有限依賴關系[17]。

本文用來表示文本類別的層次圖(圖2)有如下特點: a)每個節點表示一個類別，不同節點對應的類別也不同;b)每條有向邊(即圖2中的箭頭線)表示類別之間的種屬關系，箭尾表示父類，箭頭指向子類;c)只有一個入度為0的節點，即表示由所有文檔組成的總類;d)出度為0的節點表示不能再細分的類別。

不含平行邊和自回路的圖稱為簡單圖。下面介紹后面章節用到的有向簡單圖中的相關概念和性質，來自于有向圖的專著(文獻[18])。

定義1 設D=(V， A)是有向簡單圖，V是頂點集，A是邊集。對于D的一個頂點v，定義集合:N+D(v)={u∈V-v: vu∈A}， N-D(v)={w∈V-v: wv∈A}，分別稱集合N+D(v)和N-D(v)為頂點v的出鄰集(out-neighbourhood)和入鄰集(in-neighbourhood)。其中:|N+D(v)|稱為v的出度deg+(v) (out-degree)，|N-D(v)|稱為v的入度deg-(v) (in-degree)。

例如，在圖2的有向圖中，N+D(b)={c，d，e，f}，N-D(b)={a}，且deg+(b)=4，deg-(b)=1。

定理1 有向無圈圖一定存在著頂點的拓撲序。

拓撲序是圖中頂點的排序，使得圖中每條有向邊的出發頂點在排序中都位于該邊所指向的頂點的前面。Kahn[19]提出了復雜性為O(|V|+|A|)的算法來找有向無圈圖D=(V， A)中的拓撲序。應用該算法在圖2中可找到一條拓撲序為a b c d e f g h。

3 算法

基于圖的層次文本分類方法由兩個過程組成(圖3)，即訓練過程和分類過程。訓練過程使用訓練文檔來生成所需要的分類器，而分類過程利用生成的分類器將新文檔實例標記為合適的類別。由于層次圖中頂點與類別是一一對應的，在不引起混淆的情況下，本文以下內容中將不再嚴格區分頂點與類別。

3.1 訓練過程

由于一個文檔可以屬于多個類別，訓練例是多標記數據(multi-lable data)。令x表示一個文檔，Y表示類別集合，則訓練例的形式為(x，Y+)。其中:Y+表示x所屬的類別集合且Y+Y。因而在訓練過程，首先要將訓練例進行轉換，使得多標記數據變為單標記數據(singlelable data)，即一個訓練例(x，Y+)轉換為|Y+|個訓練例(x，y+)。其中y+Y+。

另一方面，由于文檔的標記過程一般只標記所屬的類別，而不標記不屬于的類別，訓練集的反例如下:在層次圖D中，設頂點u是頂點v的出鄰集N+D(v)的頂點，則類別u的反例集合Y-(u)為(∪w∈(N+D(v)-u) Y+(w))-Y+(u)，即一個類別的反例集等于位于同一出鄰集的其他頂點的正例集合。

訓練過程為層次圖中的每個頂點u(除了入度為0的總類別節點)生成一個二元分類器Hu:X×Y→R。其中:X是文檔集合，□是類別集合，R是實數集合。對于x∈X且y∈Y，Hu(x，y)>0表示文檔x屬于類別y，反之不屬于。絕對值|Hu(x，y)|則是對此判斷的確認度。

3.2 分類過程

基于圖的層次多標記文本分類過程見算法GraphHMLTC。

Algorithm: Graph-based hierarchical multi-label text classification (GraphHMLTC)

輸入:新文檔x，層次圖HG=〈V，E〉，固定閾值θ，類別集合L。

輸出:x所屬的每個類別l及其確認度Hl(x)。

a)找出圖HG中的一條拓撲序T。

b)對HG中每個頂點u計算其入度deg-(u)。

c)按照拓撲序T依次處理圖HG中的頂點u。

d)調用頂點u(對應類別l)的分類器Hl對x進行分類，返回結果Hl(x)。

e)如果Hl(x)<θ，則從拓撲序T中去除u，并且所有屬于u的出鄰集中頂點v的deg-(v)減1;如果deg-(v)等于0，則從拓撲序T中去除v，且屬于v的出鄰集中的所有頂點入度減1。依此類推，直到去除一個頂點后，在T中排在該頂點后面的所有頂點的入度均不為0為止。

f)輸出T中保留的頂點所對應的類別l及其確認度Hl(x)。

關于該算法的相關解釋如下:

a)在層次圖頂點的拓撲序中，父類所對應的頂點一定排在子類所對應的頂點前面。根據拓撲序來對文本進行分類(步驟c))，可以保證先對父類進行分類再對子類進行分類。

b)在二元分類中，對文檔屬于某個類別的判別往往采用固定閾值或動態閾值的方法[20]。固定閾值是預先指定的最小確認度，而動態閾值是當前判別的類別集合的確認度平均值。固定閾值方法缺乏靈活性，但是穩定并且可以較好地表達對分類結果的期望;動態閾值方法靈活，但是在確認度都較小甚至為負值的情況下也要被迫選擇文檔歸屬的類別。基于上述分析，本文采用固定閾值方法(步驟e))。

c)當一個分類器的返回結果沒有達到固定閾值(返回結果為負值，表示文檔不屬于該類別;返回結果為正值，但是小于固定閾值，表示文檔屬于該類別的確認度不高)，即表示文檔不屬于該類別。按照層次分類的思想，如果文檔不屬于某一父類，則也不屬于其子類，因而不需要調用子類的分類器進行分類。故算法的步驟e)根據分類情形對拓撲序進行動態調整，剪除已經明確不屬于某父類對其子類的傳遞路徑(即入度減1)。如果某類別頂點的入度減為0，則表示待分類文檔不屬于其所有父類，因此需從拓撲序中去除該頂點，即無須調用該類別的分類器。

d)拓撲序中沒有被去除的頂點對應的類別即待分類文檔所屬的類別(步驟f))。

由于找拓撲序的時間為O(|V|+|E|)，算法GraphHMLTC的時間復雜性為max{O(|V|+|E|)，O(|V|T(Hl))}。其中T(Hl)為二元分類器Hl所花的時間。

關于拓撲序的動態調整舉例如下:圖2中頂點的原有拓撲序為a b c d e f g h，設θ=0.5，如果對于文檔x，有Hb(x)=0.3<θ，則deg-(d)=deg-(e)=0，deg-(f)=1，因此拓撲序變為a c f g h。

4 實驗

為了研究本文方法的可行性，選取了Open Directory Project上的一個子集computers來進行實驗。該子集的部分類別層次圖如圖4所示。實驗過程共使用了該子集下的381個類別和6 953個網頁文檔。Computers類別分為6個子類，各子類所選擇的文檔數目如表1所示。

表1 computers的6個子類的文檔數

類別文檔數類別文檔數

computer science187security275

hardware568software2906

Internet2 713system304

本文所選用的評價文本分類性能的指標包括查全率(recall)、查準率(precision)、宏觀F1值(macro-F1)、微觀F1值(micro-F1)。設NCRi是正確分類到Ci類的文檔數，NCi是實際屬于Ci類的文檔數，NPi是分類器預測為Ci類的文檔數，N是文檔總數，m是類別總數。各指標的具體定義如下:

查準率:Pi=NCRi/Npi

查全率:Ri=NCRi/NCi

宏觀查準率:PM=(1/m)∑mi=1Pi

宏觀查全率:RM=(1/m)∑mi=1Ri

F1值:F1i=2RiPi/(Ri+Pi)

宏觀F1值:FM1=(1/m)∑mi=1F1i

微觀F1值:Fμ1=(2×∑mi=1Pi×∑mi=1Ri)/((∑mi=1Pi+∑mi=1Ri)×m)

本文選擇非層次分類方法的代表——BoosTexter.MH[14]與本文方法作比較。 BoosTexter.MH是一個單層的多標記文本分類器，使用Boosting技術來改善分類精度。為了方便實現，本文算法GraphHMLTC的層次圖上每個節點的二元分類器均使用BoosTexter.MH(即單層單標記分類)，利用節點“本地的”訓練例來判別是否屬于對應的類別。而在BoosTexter.MH的實驗中，所有類別的文檔作為一個完整的訓練集來進行。

實驗環境為Pentium Processor(2.66 GB)+RAM(1 GB)+Fedora 9.0。實驗過程采用3交叉驗證法，即訓練集分為三個子集，兩個用來訓練，一個用來驗證。實驗結果如表2所示。其中GraphHMLTC的閾值設為θ=0.5。表2的第一行表示實驗中所采用的Boosting技術的迭代次數T，分別為5、10、20、50、100、200次。每欄中的四個數字從上到下依次為PM、RM、FM1、Fμ1的值。例如，當迭代次數T=5時，在訓練集上GraphHMLTC的宏觀查準率PM=0.54，宏觀查全率RM=0.56，宏觀F1值FM1=0.55，微觀F1值Fμ1=0.50。

表2 本文方法與BoosTexter.MH的分類性能比較

分類方法5102050100200

BoosTexter.MH0.430.510.470.420.450.480.460.430.500.560.530.500.580.570.570.56

0.630.680.650.610.660.680.700.65

GraphHMLTC0.540.560.550.500.590.560.570.510.650.670.660.600.740.700.710.68

0.820.800.810.770.840.790.810.79

從表2可以看到，GraphHMLTC的性能是令人滿意的。隨著迭代次數的增多，兩種方法的宏觀查準率PM和宏觀查全率RM都有所提高，但是GraphHMLTC增長的幅度要比BoosTexter.MH大得多。特別地，在迭代次數為200時，GraphHMLTC的PM已經達到84%，而BoosTexter.MH僅有66%，這說明采用圖形層次結構在較大程度上提高了分類精度。另外，GraphHMLTC的FM1和Fμ1也呈穩定增長的趨勢，這說明由查準率和查全率所構成的綜合性能指標也改善了。

5 結束語

本文提出了一種基于圖結構的層次多標記分類方法，稱為GraphHMLTC。與基于樹結構的層次分類方法不同，該方法利用有向無圈圖的拓撲排序來確定類別之間的分類順序。層次圖中的每個類別只對應一個節點，在其之上的拓撲排序保障了先父類后子類的合理分類順序。而使用圖結構就自然克服了樹結構中由于多個節點表示同一類別所帶來的分類不一致性。實驗表明，采用層次圖分類的GraphHMLTC方法比非層次分類方法BoosTexter.MH在較大程度上改善了分類的精度。

本文的未來工作如下:a)進一步完善實驗工作。由于大部分基于樹結構的層次分類器不能直接獲得，但可以嘗試實現其近似版本，來與本文方法進行分類性能和代價等方面的比較。b)增強方法的應用性。將基于圖的層次分類思想應用到更多的多標記分類領域以提高準確度，如音樂分類、語義情景分類、醫學診斷等領域。

參考文獻:

[1]蘇金樹，張博鋒，徐昕. 基于機器學習的文本分類技術研究進展[J]. 軟件學報，2006，17(9):1848-1859.

[2]郝秀蘭，陶曉鵬，徐和祥，等. KNN文本分類器類偏斜問題的一種處理對策[J].計算機研究與發展，2009，46(1):52-61.

[3]周炎濤，唐劍波，吳正國.基于向量空間模型的多主題Web文本分類方法[J].計算機應用研究， 2008，25(1):142-144.

[4]TSOUMAKAS G， KATAKIS I. Multi-label classification:an overview[J]. International Journal of Data Warehousing and Mining， 2007，3(3):1-13.

[5]TSOUMAKAS G， VLAHAVAS I. Random k-labelsets: an ensemble method for multilabel classification[C]//Proc of the 18th European Conference on Machine Learning: Springer， 2007:406-417.

[6]TSOUMAKAS G， KATAKIS I， VLAHAVAS I. Mining multi-label data[K]//Data Mining and Knowledge Discovery Handbook. 2nd ed. New York :Springer， 2009: 1383.

[7]FROMMHOLZ I. Categorizing Web documents in hierarchical catalogues[C]//Proc of the 23rd European Colloquium on Information Retrieval Research. Darmstadt， Delaware: Springer， 2001.

[8]SUN A， LIM E P， NG W K， et al. Blocking reduction strategies in hierarchical text classification[J]. IEEE Trans on Knowledge and Data Engineering， 2004，16(10):1305-1308.

[9]ROUSU J， SAUNDERS C， SZEDMK S，et al. Learning hierarchical multi-category text classification models[C]//Proc of the 22nd International Conference on Machine Learning. New York:ACM Press， 2005:744-751.

[10]SUN Ai-xin， LIM E P. Hierarchical text classification and evaluation[C]//Proc ofIEEE International Conference on Data Mining. Wa-shington DC: IEEE Computer Society， 2001: 521-528.

[11]SUN Ai-xin， LIM E P. Web unit based mining of homepage relationships[J]. Journal of the American Society for Information Science and Technology， 2006，57(3):394-407.

[12]HUANG C C， CHUANG S L， CHIEN L F. Liveclassifier: creating hierarchical text classifiers through Web corpora[C]//Proc of the 13th International ACM World Wide Web Conference. New York: ACM Press， 2004:184-192.

[13]ESULI A， FAGNI T， SEBASTIANI F. TreeBoost.MH: a boosting algorithm for multi-label hierarchical text categorization[C]//Proc of the 13th International Symposium on String Processing and Information Retrieval. Berlin: Springer， 2006:13-24.

[14]SCHAPIRE R E， SINGER Y. BoosTexter: a boosting-based system for text categorization[J]. Machine Learning， 2000，39(2/3):135-168.

[15]ZHANG Ming-lin， ZHOU Zhi-hua. A k-nearest neighbor based algorithm for multi-label classification[C]//Proc of the 1st IEEE International Conference on Granular Computing. 2005:718-721.

[16]McCALLUM A. Multi-label text classification with a mixture model trained by EM[C]//Proc of the AAAI Workshop on Text Learning. Orlando， Florida: AAAI， 1999.

[17]KOLLER D， SAHAMI M. Hierarchically classifying documents using very few words[C]//Proc of the 14th International Conference on Machine Learning. San Francisco: Morgan Kaufmann， 1997:170-178.

[18]BANG-JENSEN J， GUTIN G D. Theory， algorithms and applications[M]//2nd ed. London: Springer， 2008.

[19]KAHN A B. Topological sorting of large networks[J]. Communications of the ACM， 1962，5(11):558-562.

[20]吳春穎，王士同.一種改進的KNN Web文本分類方法[J].計算機應用研究， 2008，25(11):3275-3277.