基于半監督學習的中文多文檔子主題劃分*

徐曉丹

(浙江師范大學數理與信息工程學院，浙江金華 321004)

0 引言

隨著Internet的發展和普及，跨文本的研究越來越受到人們的重視．將同個主題的多個文本去除冗余信息，按照一定的壓縮比有機地融合在一起，即為多文檔文摘．隨著網絡信息量的日益豐富，多文檔文摘技術已成為新的研究熱點．

目前，對多文檔研究較多的是通過聚類的方法生成多文檔文摘［1-3］，將多文檔集合中相同意義的文本單元(句子)聚成一類，每一類便可以理解為一個子主題或是邏輯主題，然后從子主題中抽取句子生成文摘．從子主題的角度生成文摘可以使文摘的覆蓋性強而冗余信息少，是一種有效的方法．在該方法中，子主題的確定是其中關鍵的一個環節，現有的方法主要有基于層次聚類的方法和k-means方法(即k均值聚類算法)．基于層次的聚類方法需要預先設定一個終止的閾值，而閾值的確定需要大量的先驗知識;基于k-means的聚類方法需要預先給定目標類別數量，而文檔中的子主題的數目是未知的．2種方法的效果都不是很理想．

針對上述情況，本文將半監督聚類的思想融入到子主題劃分中，通過層次聚類對可信度高的句子進行主題類別標記，生成少量已標記主題類別的句子集，在此基礎上對所有句子進行constrained-k-means聚類，通過交叉驗證的方法確定子主題的數目k，然后采用k-means聚類生成k個子主題．

1 多文檔子主題的表示

多文檔集合D由文檔di組成:D={di|i=1，2，…，f}，每個文檔 di可以表示為句子 si，l的集合，di={si，l|l=1，2，…，g}，由此多文檔集合 D 就可以看成是句子的集合:D={si，l|si，l∈di，i=1，2，…，f，l=1，2，…，g}．其中:i表示集合中的文本號;l表示句子在文本中的位置．

多文檔集合的子主題是指多文檔集合中意義相同或相似的句子組合，這些子主題代表多文檔集合中的各個局部信息，局部信息的綜合在一定程度上能代表文檔集合的總體信息．因此，多文檔集合可以描述成由多個子主題構成:D={Ti|i=1，2，…，h}，每個 Ti是一個句子集合．

將多文檔集合描述為若干邏輯子主題的集合，是從理解的角度描述多文檔集合，在此基礎上可以提高多文檔文摘的質量和信息的覆蓋率．在邏輯子主題的劃分過程中，句子之間的語義距離是一個重要的衡量因素，2個句子的語義距離越小，它們被劃為同一個主題的可能性就越大．

2 句子的語義距離計算

本文通過計算句子的相似度獲取句子之間的語義距離．2個句子的相似度越大，語義距離就越?。谏鲜黾僭O，設2個句子A和B之間的相似度為 S(A，B)，則句子 A和 B的語義距離d(A，B)為

式(1)中，a為可調參數．

句子的相似度通過計算句子所包含詞匯之間的相似度獲得．設句子A包含的有效詞為a1，a2，…，am，B 包含的有效詞為 b1，b2，…，bn，則句子 A和B之間的語義相似度S(A，B)的計算公式為

式(2)中:m和n分別表示句子A和句子B的有效詞的個數;S(ai，B)表示詞ai和句子B的相似度;S(bj，A)表示詞 bj和句子 A的相似度;S(ai，B)=max(S(ai，b1)，S(ai，b2)，…，S(ai，bn));S(bj，A)=max(S(bj，a1)，S(bi，a2)，…，S(bi，am));S(ai，bj)表示 2 個詞 ai，bj之間的語義相似度，計算公式為

式(3)中，d(ai，bj)表示詞 ai，bj之間的語義距離．

為了計算2個詞之間的語義距離，以哈爾濱工業大學信息檢索研究中心提供的《同義詞詞林擴展版》為基礎，根據它提供的詞的語義編碼計算詞的語義距離．《同義詞詞林擴展版》采用層級體系，按照樹狀的層次結構把所有收錄的詞條組織到一起．在該詞典中，每個詞都有一個語義編碼，這個語義編碼采用5層結構，分別為大類、中類、小類、詞群和原子詞群．2個詞之間的語義關系通過編碼來體現，例如“農民”的語義編碼為Ae07A01，“牧民”的語義編碼為“Ae07B01”．若 2個詞的語義編碼的第1層、第2層和第3層都是相同的，從第4層開始不同，則說明這2個詞的意義比較接近．d(ai，bj)具體計算公式為

式(4)中:t(2≤t≤6)為它們之間的語義代碼從第t層開始不同;當t=6時，表示前面的5層全部相同，語義距離為0，說明2個詞為同義詞，它們間的相似度就為1．

若2個詞的語義代碼從第1層就開始不同，但同屬于 A，B，C，D 大類或者同屬于 F，G，H，I，J大類，則考慮到《同義詞詞林》大類之間的相關性(如第1至第4大類多為名詞，第6至第10大類多為動詞等等)，將這類詞語之間的語義距離設為d(ai，bj)=12，否則就將其設為+∞．

3 半監督聚類的子主題劃分

計算出句子的語義距離后，就可以進行子主題的劃分．其基本的思想是:將語義距離小即相似性高的句子聚成一類，生成若干個子主題．傳統的基于層次聚類的方法中閾值的確定需要大量的先驗知識，同時聚類結果不能修正;k-means聚類方法通過多次迭代修正可以取得好的聚類效果，但該方法需要預先知道聚類的個數．本文采用半監督的聚類方法，可以有效地克服上述缺陷，取得較好的效果．

3．1 半監督的k-means聚類

半監督學習的基本思想是:利用有標記數據構造學習機，并對部分無標記數據進行預測，再將無標記數據和對應的預測標記加入到訓練集中，重新對學習機進行訓練，以提高學習機的性能［4］．根據學習任務的不同可分為半監督分類和半監督聚類．半監督聚類方法利用少量的標記數據輔助聚類算法的實現，將提高聚類算法的精度．

現有的半監督聚類算法［5］很多是在傳統聚類算法的基礎上引入監督信息發展而來，代表性算法是基于經典k-means算法的各種半監督kmeans算法．

k-means算法為:假設有一個無標記的數據集X={x1，x2，…，xn}，xi∈Rn，將其分成 k 類 C1，C2，…，Ck，即 Cq={xj}Nqj=1?X，每類的均值為 m1，m2，…，mk．其中，Nq為第 q 類的樣本數目［6］．則第 q類的均值mq的計算公式為

基于歐氏距離［7］、類內誤差平方和準則，k-means聚類的目標函數定義為

k-means方法中k值和聚類中心的選擇對算法有較大的影響．本文采用半監督的思想確定k值:首先，使用層次聚類獲得初始的類別k，并把類別中可信度高的樣本標記為該類別，獲得已標記樣本集合;然后，根據已標記樣本集合和未標記樣本集合修正初值k，修正的過程就是一個半監督的學習過程．

假設已標記的少量樣本集合為L，無標記的樣本集合為U，i和j為已標記樣本集的標記．取k=2為初始值，在完整的樣本集{L，U}上進行constrained-k-means聚類［8］，當 k 取不同值時，計算已標記樣本集L中被錯誤標記的樣本總數M，使M取得最小值的k值即為k-means算法的最佳初值．其中

式(7)中:c表示聚類后各簇的標號;nic，njc表示在第c簇中標記為i，j的數據的數量．

根據空簇出現的頻率判定k是否已經取到最大值．空簇指的是某一簇中不包含任何標記數據．當空簇出現的頻率大于45%(經驗值)時，可以認為k已經取到最大值．在k值的優化過程中，如果某一簇內的監督信息滿足下式，那么認為此次聚類結果無效:

式(8)中，r為一個閾值．閾值r根據反復實驗確定，一般認為當nic與njc數量接近時，類標記為c的簇即為無效簇．

3．2 基于半監督聚類子主題劃分算法

基于半監督聚類子主題劃分算法的步驟如下:

1)預先給定一個初始子主題的數目h(一般取值為3)，使用層次聚類方法獲得初始聚類T={Ti}(1≤i≤h)，其中 Ti是句子的集合，Ti={si，l|l=1，2，…，g'}．

2)對于每個Ti，找出離聚類中心最近的w個句子(w取初始類別的平均句子數目的5%)，將其標記為該類別，并將這些句子加入到已標記數據集合L中，形成初始的少量帶標記的句子集合L和無標記句子集合U．

3)取k=2為初值，在完整的句子集{L，U}上進行constrained-k-means聚類，當聚類后空簇的頻率大于設定值時，結束聚類．

4)計算當k取不同值時L中被錯誤標記的句子總數M，選擇M的數目最少的k為子主題的數目．

5)以上面生成的k值為基礎，對所有的句子進行k-means聚類，最后得到k個子主題．

4 實驗與評估

本文采用聚類的正確率來評價聚類的結果．首先由專家得到文檔集合的主題信息;然后以專家的聚類為標準，比較文檔里的每個句子是否被分在正確的主題類中，得到聚類的正確率p作為評價指標;最后采用本文提出的方法進行實驗．實驗的語料庫來自人民網的原始網頁，包含軍事、國際、經濟等8個大類別共5 096個網頁．從語料庫中抽取10個多文檔集合進行實驗，每個集合包含5～8篇文章．實驗結果如表1所示．

表1 層次聚類法和半監督聚類法的聚類精度

由實驗結果可以得到以下結論:

1)使用層次劃分的方法對多文檔子主題進行識別時，對部分文檔不能起到很好的效果．基于層次劃分的方法是不可回溯的，一旦某個句子被劃分到某個類別后，就不能再發生改變，并且層次聚類的結果需要確定閾值，這個閾值對聚類的結果有很大的影響，這就需要用戶對劃分對象有一定的了解．

2)本文提出的半監督學習的方法可根據數據本身的特點動態地確定子主題的數目，因此可以相對精確地得到子主題的個數，從而有效地提高了分類效果．

3)聚類的結果受句子相似度的影響較大．

5 結語

本文論述了一種基于半監督學習的子主題聚類方法，該方法嘗試運用半監督的思想處理子主題的類別歸屬問題，半監督聚類的方法有效地彌補了層次聚類和k-means聚類的不足，能根據數據本身的特點獲得最佳的k值，實驗結果表明該方法是有效的．在下一步的工作中將在此基礎上實現多文檔的自動摘要．

［1］Endre B，Paul B K，David J N．A clustering based approach to creating multi-document summaries［C］//The 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval．New Orleans:ACM SIGIR，2001:34-42．

［2］Radev R，Jing Hongyan，Malgorzata B．Centroid-based summarizaiton of multiple documents:Sentence extraction，utility-based evaluation，and user studies［C］//ANLP/NAACL 2000 Workshop on Summarization．Seattle:Association for Computational Linguist，2000:21-29．

［3］秦兵，劉挺，陳尚林，等．多文檔文摘中句子優化選擇方法研究［J］．計算機研究與發展，2006，43(6):1129-1134

［4］Zhu Xiaojin．Semi-supervised learning literature survey［R］．Madison:University of Wisconsin，2008．

［5］李昆侖，曹錚，曹麗蘋，等．半監督聚類的若干新進展［J］．模式識別與人工智能，2009，22(5):735-741

［6］Mac Q J．Some methods for classification and analysis of multivariate observations［C］∥Proc of the 5th Berkeley Symp on Mathematical Statistics and Prohability．Berkeley:University of Califfornia Press，1967:281-297．

［7］Klein D，Kamvar S D，Manning C．From instance-level constraints to space-level constraints:Making the most of prior knowledge in data clustering［C］//Proc of the 19th International Conference on Machine Learning．Sydney:International Machine Learning Society，2002:307-314．

［8］Basu S，Baneoee A，Moonev R J．Semi-supervised clustering by seeding［C］∥Proc of the 19th International Conference on Machine Learning．Sydney:International Machine Learning Society，2002:19-26．