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

魏明川，朱俊杰，張 瑾，張 凱，程學(xué)旗，任 彥

(1. 中國科學(xué)院計算技術(shù)研究所，北京 100190；2. 中國科學(xué)院研究生院，北京 100190；3. 國家計算機網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心，北京 100190)

1 引言

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

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

2 相關(guān)工作

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

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

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

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

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

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

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

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

3.1 二元關(guān)鍵詞子話題表示模型

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

表1 關(guān)鍵詞子話題模型對比結(jié)果

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

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

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

(2)

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

1) 能保證兩個關(guān)鍵詞作為一個聯(lián)合整體被納入考慮；

2) 能保證兩個關(guān)鍵詞組和對應(yīng)文檔語料有合適的相關(guān)度。

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

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

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

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

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

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

(3)

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

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

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

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

3.3 模型算法及實現(xiàn)過程

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

模型流程如下：

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

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

具體算法實現(xiàn)過程如下：

輸入：n篇t話題下的文檔語料，每篇文檔限定的關(guān)鍵詞數(shù)x，衰減模型中衰減系數(shù)β，最終子話題個數(shù)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 實驗結(jié)果及分析

4.1 實驗數(shù)據(jù)集及實驗指標(biāo)

為了評測子話題發(fā)現(xiàn)模型生成結(jié)果質(zhì)量，本文共設(shè)計3種指標(biāo)進行評測。子話題中聯(lián)合關(guān)鍵詞組的tf值可作為該子話題和對應(yīng)文檔的相關(guān)度。兩個關(guān)鍵詞如果在一篇文獻中同時出現(xiàn)過，表示該子話題和該篇文檔相關(guān)聯(lián)?；诖吮疚脑O(shè)計了子話題覆蓋度cr、子話題獨立度dr兩個關(guān)于子話題及文檔相關(guān)度的評測指標(biāo)。

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

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

wr越高，說明子話題之間關(guān)鍵詞重復(fù)度越低，對應(yīng)子話題獨立性越高，反之亦然。

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

表2 待檢測話題

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

4.2 實驗結(jié)果

4.2.1 對比測試

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

圖1 子話題覆蓋率結(jié)果圖

圖2 子話題多樣性結(jié)果圖

圖3 子話題關(guān)鍵詞獨立度結(jié)果圖

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

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

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

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

4.2.2 人工評價

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

AMCSubtopic模型生成的9組話題top5子話題和對應(yīng)的人工標(biāo)注匹配結(jié)果如表3所示。

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

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

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

5 總結(jié)與下一步工作

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

[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] 王巍. 基于關(guān)鍵詞和時間點的網(wǎng)絡(luò)話題演化分析.[D]. 復(fù)旦大學(xué)中國優(yōu)秀碩士學(xué)位論文. 2009.

[4] 袁繼鵬. 網(wǎng)絡(luò)輿情話題演化及話題重要度分析[D]，中國科學(xué)院計算技術(shù)研究所碩士學(xué)位論文， 2012.

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

[6] 張瑾. 面向Web話題的多文檔文摘關(guān)鍵技術(shù)研究[D]. 中國科學(xué)院計算技術(shù)研究所博士學(xué)位論文，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].中文信息學(xué)報，2007，21(6):72-57.

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

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

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

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

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

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