徐曉丹

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

0 引言

隨著Internet的發(fā)展和普及，跨文本的研究越來(lái)越受到人們的重視．將同個(gè)主題的多個(gè)文本去除冗余信息，按照一定的壓縮比有機(jī)地融合在一起，即為多文檔文摘．隨著網(wǎng)絡(luò)信息量的日益豐富，多文檔文摘技術(shù)已成為新的研究熱點(diǎn)．

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

針對(duì)上述情況，本文將半監(jiān)督聚類的思想融入到子主題劃分中，通過(guò)層次聚類對(duì)可信度高的句子進(jìn)行主題類別標(biāo)記，生成少量已標(biāo)記主題類別的句子集，在此基礎(chǔ)上對(duì)所有句子進(jìn)行constrained-k-means聚類，通過(guò)交叉驗(yàn)證的方法確定子主題的數(shù)目k，然后采用k-means聚類生成k個(gè)子主題．

1 多文檔子主題的表示

多文檔集合D由文檔di組成:D={di|i=1，2，…，f}，每個(gè)文檔 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表示集合中的文本號(hào);l表示句子在文本中的位置．

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

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

2 句子的語(yǔ)義距離計(jì)算

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

式(1)中，a為可調(diào)參數(shù)．

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

式(2)中:m和n分別表示句子A和句子B的有效詞的個(gè)數(shù);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 個(gè)詞 ai，bj之間的語(yǔ)義相似度，計(jì)算公式為

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

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

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

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

3 半監(jiān)督聚類的子主題劃分

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

3．1 半監(jiān)督的k-means聚類

半監(jiān)督學(xué)習(xí)的基本思想是:利用有標(biāo)記數(shù)據(jù)構(gòu)造學(xué)習(xí)機(jī)，并對(duì)部分無(wú)標(biāo)記數(shù)據(jù)進(jìn)行預(yù)測(cè)，再將無(wú)標(biāo)記數(shù)據(jù)和對(duì)應(yīng)的預(yù)測(cè)標(biāo)記加入到訓(xùn)練集中，重新對(duì)學(xué)習(xí)機(jī)進(jìn)行訓(xùn)練，以提高學(xué)習(xí)機(jī)的性能［4］．根據(jù)學(xué)習(xí)任務(wù)的不同可分為半監(jiān)督分類和半監(jiān)督聚類．半監(jiān)督聚類方法利用少量的標(biāo)記數(shù)據(jù)輔助聚類算法的實(shí)現(xiàn)，將提高聚類算法的精度．

現(xiàn)有的半監(jiān)督聚類算法［5］很多是在傳統(tǒng)聚類算法的基礎(chǔ)上引入監(jiān)督信息發(fā)展而來(lái)，代表性算法是基于經(jīng)典k-means算法的各種半監(jiān)督kmeans算法．

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

基于歐氏距離［7］、類內(nèi)誤差平方和準(zhǔn)則，k-means聚類的目標(biāo)函數(shù)定義為

k-means方法中k值和聚類中心的選擇對(duì)算法有較大的影響．本文采用半監(jiān)督的思想確定k值:首先，使用層次聚類獲得初始的類別k，并把類別中可信度高的樣本標(biāo)記為該類別，獲得已標(biāo)記樣本集合;然后，根據(jù)已標(biāo)記樣本集合和未標(biāo)記樣本集合修正初值k，修正的過(guò)程就是一個(gè)半監(jiān)督的學(xué)習(xí)過(guò)程．

假設(shè)已標(biāo)記的少量樣本集合為L(zhǎng)，無(wú)標(biāo)記的樣本集合為U，i和j為已標(biāo)記樣本集的標(biāo)記．取k=2為初始值，在完整的樣本集{L，U}上進(jìn)行constrained-k-means聚類［8］，當(dāng) k 取不同值時(shí)，計(jì)算已標(biāo)記樣本集L中被錯(cuò)誤標(biāo)記的樣本總數(shù)M，使M取得最小值的k值即為k-means算法的最佳初值．其中

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

根據(jù)空簇出現(xiàn)的頻率判定k是否已經(jīng)取到最大值．空簇指的是某一簇中不包含任何標(biāo)記數(shù)據(jù)．當(dāng)空簇出現(xiàn)的頻率大于45%(經(jīng)驗(yàn)值)時(shí)，可以認(rèn)為k已經(jīng)取到最大值．在k值的優(yōu)化過(guò)程中，如果某一簇內(nèi)的監(jiān)督信息滿足下式，那么認(rèn)為此次聚類結(jié)果無(wú)效:

式(8)中，r為一個(gè)閾值．閾值r根據(jù)反復(fù)實(shí)驗(yàn)確定，一般認(rèn)為當(dāng)nic與njc數(shù)量接近時(shí)，類標(biāo)記為c的簇即為無(wú)效簇．

3．2 基于半監(jiān)督聚類子主題劃分算法

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

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

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

3)取k=2為初值，在完整的句子集{L，U}上進(jìn)行constrained-k-means聚類，當(dāng)聚類后空簇的頻率大于設(shè)定值時(shí)，結(jié)束聚類．

4)計(jì)算當(dāng)k取不同值時(shí)L中被錯(cuò)誤標(biāo)記的句子總數(shù)M，選擇M的數(shù)目最少的k為子主題的數(shù)目．

5)以上面生成的k值為基礎(chǔ)，對(duì)所有的句子進(jìn)行k-means聚類，最后得到k個(gè)子主題．

4 實(shí)驗(yàn)與評(píng)估

本文采用聚類的正確率來(lái)評(píng)價(jià)聚類的結(jié)果．首先由專家得到文檔集合的主題信息;然后以專家的聚類為標(biāo)準(zhǔn)，比較文檔里的每個(gè)句子是否被分在正確的主題類中，得到聚類的正確率p作為評(píng)價(jià)指標(biāo);最后采用本文提出的方法進(jìn)行實(shí)驗(yàn)．實(shí)驗(yàn)的語(yǔ)料庫(kù)來(lái)自人民網(wǎng)的原始網(wǎng)頁(yè)，包含軍事、國(guó)際、經(jīng)濟(jì)等8個(gè)大類別共5 096個(gè)網(wǎng)頁(yè)．從語(yǔ)料庫(kù)中抽取10個(gè)多文檔集合進(jìn)行實(shí)驗(yàn)，每個(gè)集合包含5～8篇文章．實(shí)驗(yàn)結(jié)果如表1所示．

表1 層次聚類法和半監(jiān)督聚類法的聚類精度

由實(shí)驗(yàn)結(jié)果可以得到以下結(jié)論:

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

2)本文提出的半監(jiān)督學(xué)習(xí)的方法可根據(jù)數(shù)據(jù)本身的特點(diǎn)動(dòng)態(tài)地確定子主題的數(shù)目，因此可以相對(duì)精確地得到子主題的個(gè)數(shù)，從而有效地提高了分類效果．

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

5 結(jié)語(yǔ)

本文論述了一種基于半監(jiān)督學(xué)習(xí)的子主題聚類方法，該方法嘗試運(yùn)用半監(jiān)督的思想處理子主題的類別歸屬問題，半監(jiān)督聚類的方法有效地彌補(bǔ)了層次聚類和k-means聚類的不足，能根據(jù)數(shù)據(jù)本身的特點(diǎn)獲得最佳的k值，實(shí)驗(yàn)結(jié)果表明該方法是有效的．在下一步的工作中將在此基礎(chǔ)上實(shí)現(xiàn)多文檔的自動(dòng)摘要．

［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］秦兵，劉挺，陳尚林，等．多文檔文摘中句子優(yōu)化選擇方法研究［J］．計(jì)算機(jī)研究與發(fā)展，2006，43(6):1129-1134

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

［5］李昆侖，曹錚，曹麗蘋，等．半監(jiān)督聚類的若干新進(jìn)展［J］．模式識(shí)別與人工智能，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．