魏明川，朱俊杰，張 瑾，張 凱，程學旗，任 彥

(1. 中國科學院計算技術研究所，北京 100190；2. 中國科學院研究生院，北京 100190；3. 國家計算機網絡應急技術處理協調中心，北京 100190)

1 引言

隨著互聯網信息的爆炸性增長，如何在海量信息里更快速、準確地提取有用信息日益成為一大挑戰(zhàn)。由于傳統(tǒng)信息檢索技術在有效獲取有用信息方面作用有限，因而對如何有效地提煉各種文本信息知識提出了難題。話題檢測與跟蹤(Topic Detection and Tracking ,TDT)著力研究如何對網絡文本進行高效組織和檢索。但某些話題對象存在持續(xù)時間長、涵蓋事件多的特點，如果直接用TDT中的定義事件組織專題，會導致事件個數隨著專題規(guī)模擴大而爆炸增長；同時，TDT無法發(fā)現話題中事件的關系，很難檢測話題中事件生成、衍化直至消亡的過程。針對以上問題，很多研究都提出建立子話題層的解決方法，在話題層和新聞事件層生成子話題層，使之成為銜接話題和事件之間的橋梁，從而構建出適合大規(guī)模數據自動分析的完備組織模式。傳統(tǒng)子話題劃分方法一般都是基于詞元的向量空間模型或基于此模型的一些改進方法，所得結果在重要性和多樣性上存在欠缺。

針對上述問題，本文提出一種基于二元關鍵詞組的子話題劃分模型，并且利用吸收馬爾可夫鏈算法對生成的子話題進行有效吸收提取，從而得到兼?zhèn)渲匾院投鄻有缘淖釉掝}結果。本文結構如下： 第2節(jié)介紹相關工作；第3節(jié)介紹本文提出的子話題發(fā)現模型；第4節(jié)描述實驗數據、評測標準、最終實驗結果及其分析；第5節(jié)為總結和下一步工作展望。

2 相關工作

作為話題表示模型的基本單元，關鍵詞是表示話題內容和區(qū)分話題類型的主要元素，因此TDT的一個研究熱點是研究如何從大量文本中提取出能獨立代表一個話題的關鍵詞。

基于關鍵詞的話題研究方面，Makkonen[1]提出根據話題的4個要素，將詞語分成時間類、地點類、實體類、動作類，從而將一個話題表示為一個語義向量{時間、地點、人物、事件}。在此思路下Hua-Jun Zeng[2]提出將詞語在文章的屬性具體表示為包括tf-idf、詞語長度、內部聚合相似度等概念，通過將詞語屬性進行線性組合，計算詞語在文章中的權重，排序生成關鍵詞，但是對以上特征的具體選取并沒有較好的解決方案。王巍[3]只利用tf-idf特征值，將詞語位置分為標題和正文，修正不同位置的關鍵詞tf-idf值并進行線性組合，通過標題長度和正文長度比進行動態(tài)調整，從而降低詞頻噪音。

子話題是話題(或子話題)內一組相關事件或活動的集合。目前子話題的研究大都是基于話題內的子話題劃分，該方面研究并沒有太多新穎有效的模型或解決方案，主要思路還是延續(xù)基于關鍵詞的方案。

基于話題內子話題的發(fā)現研究方面，袁繼鵬[4]提出計算每個關鍵詞的新穎度，并以此作為子話題分界的依據之一，其新穎度用分布密度來表征，從而得到子話題的分界點，并最終以此分界點作為子話題衍化時間點。另外，李軍等人[5]提出基于話題模型的子話題劃分方法，方法用隱含語義空間表示文檔，采用層次聚類進行子話題劃分。

以上方法都是基于1個關鍵詞的一元模式，但實際生活中很多事件很難用一個關鍵詞準確描述，因此以上方案都存在子話題劃分準確度不高，結果不夠理想的情況。本文提出了二元模式的子話題劃分方案，但該方案由于特定關鍵詞的權重唯一性，權重高的關鍵詞相互之間會生成冗余子話題，從而導致生成結果多樣性效果較差。

針對子話題多樣性質量優(yōu)化問題，張瑾等人[6]提出基于圖的子話題劃分的多文檔文摘算法，算法中借助吸收馬爾可夫鏈來更新句子的貢獻度，并借助其收斂性實現文摘算法的穩(wěn)定性。但該算法的衰減過快，不能具體適應本文的子話題模型。

針對此問題，本文提出一種針對子話題的吸收馬爾可夫鏈算法(absorbing Markov chain subtopic, AMCSubtopic)來提升子話題多樣性質量。

3 基于吸收馬爾可夫鏈的子話題發(fā)現方法

3.1 二元關鍵詞子話題表示模型

目前各大門戶網站及主要搜索引擎公司都提供熱點關鍵詞新聞服務(百度新聞首頁的熱詞新聞模塊)。將圍繞某一事件或與該事件密切相關的若干事件的新聞報道共同組織在一起全方位，多角度跟蹤報道新聞事件。基于關鍵詞的話題演化分析通過計算話題文檔集合中詞語的權重，選出權重靠前的若干詞語作為話題描述信息，以此將話題文檔進行分類從而形成子話題。對于新聞事件而言，其六要素特性(人物、時間、地點、起因、經過、結果)往往要求描述每個事件至少涵蓋兩個到多個關鍵詞。但關鍵詞具有詞義獨立性，因此過多關鍵詞來描述子話題反而會導致子話題的聚焦性失衡；而且實際系統(tǒng)的運行效率會隨著子話題的關鍵詞規(guī)模的增多而增大。因此模型在詞元個數選擇上存在較大商榷性。

表1 關鍵詞子話題模型對比結果

如表1的初步實驗對比發(fā)現，一元關鍵詞描述信息過于粗略，而多元關鍵詞存在信息冗余。綜合復雜度和有效性兩個方面，本文提出基于二元關鍵詞的子話題模型，該模型不但能夠避免單關鍵詞表征意思失衡，同時也降低了系統(tǒng)時間復雜度。模型核心特征在于二元關鍵詞組合的tf-idf值，計算方式如下：

話題T共有n篇文檔語料D{d1,d2,…,dn}，每篇文檔語料都含有若干關鍵詞，所有的關鍵詞集合為W{w1,w2,…,wm}，每個關鍵詞在語料D中都有其特定的tf-idf值，將tf-idf分開為集合TF{tf1,tf2,…,tfm}和IDF{idf1,idf2,…idfm}，對于任意一個關鍵詞Wi滿足式(1)。

其中tfik表示關鍵詞Wi在文檔Dk中的詞頻值。對于模型而言，其關鍵詞組WiWj的聯合初始聯合TF-IDF計算公式如式(2)所示。

(2)

對每篇語料分別算出每個子話題對應兩個關鍵詞的tf-idf值，并取其最小值，這樣做有兩個目的：

1) 能保證兩個關鍵詞作為一個聯合整體被納入考慮；

2) 能保證兩個關鍵詞組和對應文檔語料有合適的相關度。

通過式(2)計算出來的聯合初始tf-idf值并不能作為真正的評判結果指標進行子話題劃分，否則會引入高頻關鍵詞兩兩生成高頻子話題簇，導致生成結果多樣性質量不好。例如，“食品安全”話題下的一批文檔，按照以上聯合初始tf-idf值計算出來的前7個熱點子話題結果如下：

{1“產品 市場”；2“安全 市場”；3“市場 年中”；4“安全 生產”；5“企業(yè) 市場”；6“企業(yè) 安全”；7“產品 安全”}。

以上結果雖然跟話題有較大關聯性，但結果實際主要由關鍵詞組{“產品”；“市場”；“安全”；“生產”}組合生成。結果的覆蓋冗余性過高， 多樣性不足。為了解決以上問題，我們引入了以下的AMCSubtopic算法。

3.2 基于吸收馬爾可夫鏈算法的子話題檢測模型

張瑾等人[6]提出用吸收馬爾可夫鏈來改進文摘質量， Zhu xiaojin等人[7]提出用吸收馬爾可夫鏈來提升結果多樣性。為了更好地評價二元關鍵詞組模型，本文借鑒以上工作，提出基于子話題先驗的關鍵詞組策略模型SubtopicRank，對指定話題t的多文檔語料而言，令F=[f1,f2,…,fl]T表示關鍵詞組重要性得分向量，面向子話題的先驗分布R=[r1,r2,…,rl]T,則SubtopicRank策略可以表示為式(3)。

f(t+1)=λr+ (1-λ) ·M·f(t)

(3)

其中M是轉移概念矩陣，λ是置信度參數，本文模型λ為0，即不考慮先驗知識。為了同時考慮子話題的重要性、新穎性和多樣性，我們引入吸收馬爾可夫鏈。將已入選的關鍵詞組中兩個關鍵詞對應的狀態(tài)都設定為吸收狀態(tài)?；诖艘胛漳Ｐ?，其模型轉移矩陣見式(4)和式(5)。

其中N為n*n的矩陣，為

β為衰減系數。因此SubtopicRank策略公式即式(3)轉化為式(6)。

對于式(2)而言，算法AMCSubtopic目的是利用其吸收特性，對聯合初始tf-idf值進行重排序。因此根據式(6),我們可以得到如下計算聯合tf-idf值的公式：

3.3 模型算法及實現過程

在引入AMCSubtopic算法后，子話題模型得以很好解決子話題新穎性、重要性和多樣性的問題，而本文具體實現方案即針對二元關鍵詞組聯合tf-idf值進行重排序，并設定閾值，取出排名靠前的K個二元關鍵詞組作為子話題生成結果。

模型流程如下：

2) 得到二元關鍵詞組初始權重： 按式(2)計算得到每個關鍵詞組的初始權重值、排序；

3) 得到最終子話題： 將關鍵詞組按序放入待吸收隊列中，每次取出隊列中最大權重條目作為吸收子話題，然后根據AMCSubtopic算法更新隊列中剩余條目權重值，重新排序，重復以上過程直至隊列為空。

具體算法實現過程如下：

輸入：n篇t話題下的文檔語料，每篇文檔限定的關鍵詞數x，衰減模型中衰減系數β，最終子話題個數s。

輸出：s個子話題

fori←0ton

do

Wi=DivideDocIntoWord(Di)

MergeWord(&G,Wi)

done

SortWordByTf(&G)

fori←0tog-1

forj←0tog-1

do

Make2Keywords(&F,gj,gj+1)

done

done

SortWordByTf(&F)

len=0

whilelen!=s

do

Slen=PopFromBegin(&F)

UpdateByMarkov(&F,β)

len++

done

4 實驗結果及分析

4.1 實驗數據集及實驗指標

為了評測子話題發(fā)現模型生成結果質量，本文共設計3種指標進行評測。子話題中聯合關鍵詞組的tf值可作為該子話題和對應文檔的相關度。兩個關鍵詞如果在一篇文獻中同時出現過，表示該子話題和該篇文檔相關聯。基于此本文設計了子話題覆蓋度cr、子話題獨立度dr兩個關于子話題及文檔相關度的評測指標。

子話題覆蓋度(cr)為所有子話題關聯文檔的并集和原始文檔集的相似度，cr越大，說明子話題關聯文檔并集和原始文檔集余越接近。cr為1表示子話題關聯文檔并集和原始文檔集重合;而dr表示任一子話題和其他所有子話題關聯文檔集的差異情況，dr越大，說明子話題之間關聯的文檔交集越小，說明子話題之間多樣性越強，如果dr為1，表示子話題之間完全獨立。

為更形象體現子話題之間獨立性，我們設計了第三個評價指標： 關鍵詞的獨立度wr。已知每個子話題stk有兩個關鍵詞sTWk={stwk1,stwk2}，對于獨立性不高子話題集而言，各個子話題之間重復關鍵詞較多，因此wr是一個描述子話題集關鍵詞之間的重復情況的指標。公式如下：

wr越高，說明子話題之間關鍵詞重復度越低，對應子話題獨立性越高，反之亦然。

本文使用某在線系統(tǒng)，人工配置9個新聞話題進行數據采集，得到文檔數量和相應話題名稱如表2所示。

表2 待檢測話題

系統(tǒng)采集源都是來自中國境內的各個新聞網站，因此數據源可靠且準確。為了更好評價相似話題的子話題結果，我們選用了話題4和話題5、話題2和話題7兩組相似度較高的話題集用于評測。

4.2 實驗結果

4.2.1 對比測試

根據以上9個話題數據集，本文使用測試模型1為原始二元關鍵詞子話題模型，模型2為引入AMCSubtopic的子話題模型，測試中分別取每個話題集的前20個子話題結果進行測試。實驗基于子話題覆蓋率，多樣性和獨立度生成的實驗結果分別如圖1、圖2和圖3所示。

圖1 子話題覆蓋率結果圖

圖2 子話題多樣性結果圖

圖3 子話題關鍵詞獨立度結果圖

圖1中顯示模型2在9組話題測試結果中其子話題的覆蓋率都高于模型1，說明模型2中子話題結果并集對原始語料的覆蓋度有所提升， 從而更好全面體現出話題內容概要。

圖2中模型2在子話題多樣性上性能較模型1有了大幅度提升，多樣性平均提升了約10%，從而說明了AMCSubtopic對子話題冗余信息處理非常優(yōu)秀。

結合圖1、圖2結果可以看出，基于AMCSubtopic的子話題發(fā)現模型不僅提升了子話題結果并集的覆蓋度，還減少了子話題之間彼此的信息冗余，尤其在信息冗余處理上，效果非常明顯。

圖3是驗證子話題多樣性更直觀的結果圖。而圖3中模型2的子話題關鍵詞組基本沒有重復，而模型1的子話題組關鍵詞重復情況比較嚴重，從而說明模型2的多樣性的確優(yōu)于模型1，也印證了本文引入AMCSubtopic的想法初衷。

4.2.2 人工評價

為了更好的評測結果，我們從AMCSubtopic模型生成的子話題結果截取前10個進行人工標注測試。我們邀請了20個不同工作領域的用戶進行測試，用戶按重要度遞減標注出每個話題前5個子話題作為熱點Top5結果。對比人工標注的Top5和模型自動生成的Top5結果，根據排名給出權重值得出標注結果和自動結果的匹配度，從而評價模型性能。

AMCSubtopic模型生成的9組話題top5子話題和對應的人工標注匹配結果如表3所示。

從表3可以看出，AMCSubtopic模型自動生成的子話題結果基本和用戶信息需求基本完全吻合，9組結果中有5組結果能夠完全吻合，最低的也能達到80.00%，說明本文實現的子話題切分模型已經能夠有效的生成符合用戶需求的子話題結果，從而達到子話題檢測目的。

但人工標注的匹配結果還不能完全達到100%，說明子話題結果質量還有優(yōu)化空間。分析結果時發(fā)現，以實體作為一個關鍵詞的子話題結果往往更能夠符合用戶要求，因此本文下一步工作方向將結合實體，實現更高質量的子話題發(fā)現模型。另外，通過表3可以看出，話題4、5和話題2、7之間生成的top5子話題結果比較接近，而該兩組話題本身之間存在較大相似性，從而說明通過子話題之間關系可以反推出對應話題間關系。因此，本文的另一個工作方向就是基于子話題關系分析話題間關系。

表3 Top5子話題統(tǒng)計結果表

5 總結與下一步工作

由于傳統(tǒng)話題檢測方法對于選擇事件粒度比較困難，因此對于一些小粒度事件的發(fā)現及追蹤有較大難度，本文提出的基于二元關鍵詞子話題劃分模型能夠有效解決該方面的問題，并且在模型中引入了吸收馬爾可夫鏈算法，從而能夠有效實現子話題的代表性和多樣性。通過人工標注測試，生成了和用戶標注較為吻合的子話題結果，從而驗證了模型的可實用性。但文本僅僅引入關鍵詞組的tf-idf屬性，在分析具體系統(tǒng)運行結果中我們發(fā)現某些實體關鍵詞對子話題的劃分也起到一定正相關的影響。因此本文下一步的研究點將納入考慮實體關鍵詞對子話題劃分的影響。另外，我們將繼續(xù)拓展子話題關系模型的研究，研究子話題之間衍化和話題之間基于子話題的關聯分析等。

[1] Makkonen J,Ahonen-MykaHand SalmenkiviM Applying semantic classes in event detection and tracking[C]//Proceedings of International Conference on Natural Language Processing(ICON) Mumbai, India,2002： 175-183.

[2] Hua-Jun Zeng,Qi-Cai He, Zheng chen, et al. Learning to Cluster Web Search Results[C]//Proceedings of SIGIR’04, July， Sheffield, South Yorkshire, UK,2004：25-29.

[3] 王巍. 基于關鍵詞和時間點的網絡話題演化分析.[D]. 復旦大學中國優(yōu)秀碩士學位論文. 2009.

[4] 袁繼鵬. 網絡輿情話題演化及話題重要度分析[D]，中國科學院計算技術研究所碩士學位論文， 2012.

[5] 李軍，李娟子. 新聞專題內子話題劃分. 清華大學計算機科學與技術系[C]//Proceedings of the Fourth National Conference of Information Retrieval and Content Security,2008,Vol.1.

[6] 張瑾. 面向Web話題的多文檔文摘關鍵技術研究[D]. 中國科學院計算技術研究所博士學位論文，2009.

[7] Zhu Xiaojin,Goldberg A B,Van Gael J,et al. Improving diversity in ranking using absorbing random walks[C]//Proceedings of Human Language Technologies:the Annual Conference of the North American Chapter of the Association for Computational Linguistics.Rochester:NAACL,2007:97-104.

[8] 洪宇，張宇，劉挺，等.話題檢測與跟蹤的評測及研究綜述[J].中文信息學報，2007，21(6):72-57.

[9] 駱衛(wèi)華，于滿泉，許洪波，等.基于多策略優(yōu)化的分治多層聚類算法的話題發(fā)現研究[J]. 中文信息學報，2006，20(1):29-36.

[10] 張瑾，許洪波. 基于動態(tài)內容的文摘方法研究[C]. 第三屆全國信息檢索與內容安全學術會議論文集(NCIRCS 2007)，蘇州, 2007.

[11] 張瑾，王小磊，許洪波. 自動文摘評價方法綜述[J]. 中文信息學報, 2008，22(3):81-88.

[12] 王燦輝.Web環(huán)境下的新聞專題構建和話題挖掘研究[D]，清華大學博士學位論文， 2008.

[13] 文利娟.Web社區(qū)中話題的發(fā)現與排序[D]，武漢理工大學碩士學位論文， 2009.

[14] 賈自艷，何清，張?？?，等. 一種基于動態(tài)進化模型的時間檢測和追蹤算法[J]，計算機研究與發(fā)展, 2004，41(7):1273-1280.