李培，翁偉，林琛,3

(1. 廈門大學(xué) 信息科學(xué)與技術(shù)學(xué)院，福建 廈門361005;2. 廈門理工學(xué)院 計(jì)算機(jī)與信息工程學(xué)院，福建 廈門361024;3. 廈門大學(xué) 深圳研究院，廣東 深圳518057)

中文微博故事線生成方法

李培1，翁偉2，林琛1,3

(1. 廈門大學(xué) 信息科學(xué)與技術(shù)學(xué)院，福建 廈門361005;2. 廈門理工學(xué)院 計(jì)算機(jī)與信息工程學(xué)院，福建 廈門361024;3. 廈門大學(xué) 深圳研究院，廣東 深圳518057)

新浪微博、騰訊微博等微博平臺已經(jīng)成為國內(nèi)重要的網(wǎng)絡(luò)媒體。隨著海量的實(shí)時(shí)信息在微博上分享和傳播，為每個(gè)用戶提供更多方便，展現(xiàn)一目了然的實(shí)事資訊的任務(wù)已經(jīng)迫在眉睫。這就需要在微博中理出重大事件的發(fā)展進(jìn)程。該文中，我們將利用最小權(quán)重支配集和有向斯坦納樹在給定查詢的微博數(shù)據(jù)集上生成故事線。該文的工作由三部分組成：第一部分是在Lucene檢索出來的結(jié)果集上構(gòu)建多視點(diǎn)圖；其次，通過在圖中尋找最小權(quán)重支配集來選出具有代表性的微博；最后，通過求解有向斯坦納樹問題來平滑地連接這些已挑選的微博，形成故事線。在實(shí)際數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證了該文提出系統(tǒng)的高效性和有效性。

微博故事線；最小權(quán)重支配集；有向斯坦納樹

1 引言

微博[1-2]作為時(shí)下最為流行的開放式互聯(lián)網(wǎng)社交服務(wù)，廣泛分布在桌面、瀏覽器、移動終端等多個(gè)平臺上，使得人們可以隨時(shí)隨地地分享資訊，十分受大眾喜愛。據(jù)統(tǒng)計(jì)，2012年6月我國微博用戶已達(dá)到3億之多。人們往往喜歡從微博上獲得第一手消息或是發(fā)布自己的見聞，抑或關(guān)注某個(gè)熱門事件，而非去搜索引擎上獲得這些熱點(diǎn)事件[3]，例如郭美美、躲貓貓等事件都是在微博上曝光及發(fā)酵的。然而，由于微博短時(shí)間內(nèi)更新大量信息的特點(diǎn)在一定程度上造成了信息的碎片化，導(dǎo)致人們難以在較短時(shí)間內(nèi)理清事件的脈絡(luò)。因而，對微博中的相關(guān)事件進(jìn)行查詢并理出事件脈絡(luò)是一種必然的趨勢。

對查詢結(jié)果生成微博故事線，理清事件的脈絡(luò)是極具挑戰(zhàn)性的工作。首先，由于微博數(shù)據(jù)的稀疏性，使得由用戶查詢得到的數(shù)據(jù)集具有大量的冗余及不相關(guān)信息[4]。這就需要在查詢集中過濾掉噪音信息，挑出那些具有代表性的微博。對這些微博進(jìn)行聚類，或結(jié)合檢索相關(guān)的語言模型[5]進(jìn)行處理是一種解決方案。然而傳統(tǒng)文本聚類方法諸如NMF[6]、SNMF[7]等則忽略了微博的實(shí)時(shí)性。在處理中損失了微博的實(shí)時(shí)性，使得生成的故事線難以反映事件的發(fā)展脈絡(luò)及時(shí)間的連續(xù)性。而采用檢索語言模型來處理，又損失了微博的結(jié)構(gòu)性；其次，在得到相關(guān)的代表性微博之后，就需要“平滑”地將這些微博連成故事線。而僅僅按時(shí)間順序來生成故事線[8-9]，難以清晰地反映事件的發(fā)展階段。前期工作[10]在Twitter上進(jìn)行了一些嘗試，主要是在其數(shù)據(jù)集上構(gòu)建多視點(diǎn)圖，并通過最小權(quán)重支配集和有向斯坦納樹來生成故事線。但是其能處理的數(shù)據(jù)量相對較小，并不太適合處理中文的大規(guī)模數(shù)據(jù)。

本文提出的系統(tǒng)是基于前人的工作[10]進(jìn)行改進(jìn)的，并在新浪微博上的中大規(guī)模數(shù)據(jù)上進(jìn)行了實(shí)驗(yàn)。本文的系統(tǒng)主要在兩個(gè)方面進(jìn)行了優(yōu)化: (1)在原有的支配集算法上加入TopK集進(jìn)行優(yōu)化，減少了其時(shí)間花費(fèi)，有利于處理較大規(guī)模的數(shù)據(jù)；(2)在原有的斯坦納樹上加入了時(shí)間窗口，約束了其搜索上下限，減少了其處理花費(fèi)。

本文的結(jié)構(gòu)如下: 第二部分介紹系統(tǒng)的具體實(shí)現(xiàn)過程；第三部分介紹數(shù)據(jù)的獲取及中文微博的處理；第四部分介紹對比實(shí)驗(yàn)及一些參數(shù)調(diào)節(jié)的結(jié)果；第五部分對全文進(jìn)行總結(jié)。

2 微博故事線生成方法

微博故事線生成主要將解決兩個(gè)問題: 尋找最小權(quán)重支配集問題和求解有向斯坦納樹問題，本文將在接下來的部分作詳細(xì)介紹。前期工作[10]生成微博故事線的主要過程如圖1所示。

圖1 生成微博故事線的主要過程

首先，用戶給出一個(gè)查詢(這里的查詢主要指的是用戶感興趣的熱點(diǎn)事件或話題，例如，查詢可能是“馬航失聯(lián)”等)，我們由Lucene檢索得到一系列微博結(jié)果，然后在此結(jié)果集上構(gòu)建多視點(diǎn)圖，其實(shí)質(zhì)就是將每條微博視為一個(gè)節(jié)點(diǎn)并給其賦予相應(yīng)的權(quán)重，這個(gè)權(quán)重主要由該微博節(jié)點(diǎn)和查詢之間的語義相似度決定。而微博節(jié)點(diǎn)之間由兩種邊定義，一種是無向邊，主要表示微博節(jié)點(diǎn)之間的語義相似程度；另一種是有向邊，主要表示微博節(jié)點(diǎn)之間時(shí)間上的連續(xù)性。之后，通過在多視點(diǎn)圖中的無向圖中找最小權(quán)重支配集來獲得那些具有代表性的微博節(jié)點(diǎn)。由于找最小權(quán)重支配集是個(gè)NP難問題[11]，故本文主要采用近似算法求解，2.2節(jié)將對算法進(jìn)行介紹。最后，將利用支配集在多視點(diǎn)圖的有向圖中，通過求解有向斯坦納樹問題來生成故事線，2.3節(jié)將對這一方法加以介紹。

2.1 構(gòu)建多視點(diǎn)圖

定義1 多視點(diǎn)圖. 一個(gè)多視點(diǎn)圖是一個(gè)四元組(V,W,E,A)，其中V是點(diǎn)集，W是點(diǎn)的權(quán)集，E是無向邊集，代表兩條微博之間的相似度，A是有向邊集，代表兩條微博在時(shí)間上的連續(xù)性。

在由Lucene檢索獲得的微博結(jié)果集上，本文將每條微博視為一個(gè)節(jié)點(diǎn)來構(gòu)建多視點(diǎn)圖。構(gòu)建這個(gè)圖主要由三個(gè)非負(fù)實(shí)參數(shù)來控制:α，τ1,τ2(τ1<τ2)。圖中微博節(jié)點(diǎn)之間的語義相似度是使用余弦來計(jì)算的。由此，可以定義無向邊集E，當(dāng)兩個(gè)微博節(jié)點(diǎn)之間的相似度大于α?xí)r，就將其連接起來。定義有向邊集A，當(dāng)τ1≤tj-ti≤τ2時(shí),就作一條從點(diǎn)i到點(diǎn)j的有向邊，其中ti、tj是其節(jié)點(diǎn)上的時(shí)間戳。我們稱[τ1,τ2]為一個(gè)時(shí)間窗口。定義點(diǎn)的權(quán)集W，對于其中的每個(gè)點(diǎn)vi，其權(quán)重是1-Score(q,vi),其中score∈(0,1)為其在查詢q下該條微博由Lucene中語言模型計(jì)算的相關(guān)性得分。這樣每個(gè)節(jié)點(diǎn)的權(quán)值越低，其與查詢的相關(guān)性也就越高，后面就可直接利用最小權(quán)重支配集算法來選出具有代表性的微博節(jié)點(diǎn)。

2.2 由最小權(quán)重支配集來分析相關(guān)微博

定義2 支配集. 給定無向圖G=〈V,E〉,存在邊集的子集s，使得對于圖中任意點(diǎn)要么在s中，要么和s中的點(diǎn)鄰接。

定義3 最小權(quán)重支配集. 給定無向有權(quán)圖G=,在其存在的所有支配集中花費(fèi)最小的支配集。

由此，尋找具有代表性的微博的問題就可以轉(zhuǎn)化為在多視點(diǎn)圖中尋找一個(gè)最小權(quán)重支配集的問題。然而，找最小權(quán)重支配集的問題是個(gè)NP難問題，其最小權(quán)重支配集的精確解是難以求出的。為此，前人已經(jīng)提出了一個(gè)較好的近似算法[11,20]來求解最小權(quán)重支配集。其主要思想是: 在每次迭代中，每個(gè)點(diǎn)的權(quán)重都平攤給該點(diǎn)的鄰居，取那些平攤之后權(quán)重最小的點(diǎn)，將這些點(diǎn)添加到最小權(quán)重支配集中，并在無向圖中去掉其相應(yīng)的邊。這樣進(jìn)行多次迭代，直到找到支配集或達(dá)到給定的支配集點(diǎn)數(shù)大小。算法的近似度為1+log(Δ||OPT||)[11,20],其中Δ為無向圖G的最大度，OPT為最小權(quán)重支配集的點(diǎn)數(shù)。

針對最小權(quán)重支配集算法[11,20]，本文進(jìn)行了一定的改進(jìn)，有效利用了微博數(shù)據(jù)的稀疏性，減少了其時(shí)間花費(fèi)，使其更適應(yīng)較大規(guī)模的數(shù)據(jù)處理。由于在近似算法[12]中，每次迭代后得到的無向圖結(jié)構(gòu)發(fā)生了變化，節(jié)點(diǎn)平攤后的權(quán)重需要重新計(jì)算，成為了計(jì)算瓶頸。本文的支配集算法的主要思想是在迭代前對節(jié)點(diǎn)按照權(quán)重排序，每次迭代時(shí)按其權(quán)重排序取權(quán)重最小的前K個(gè)節(jié)點(diǎn)，比較它們的平攤權(quán)重，從而減少了計(jì)算量。這樣在處理較大規(guī)模的數(shù)據(jù)時(shí)，就可以得到一個(gè)比較好的近似解，而時(shí)間花費(fèi)也較少。其主要原因在于由微博數(shù)據(jù)構(gòu)建的圖都較為稀疏，點(diǎn)之間的邊很少，因而，在采用貪心算法計(jì)算其最小權(quán)重支配集時(shí)，點(diǎn)的權(quán)重的影響遠(yuǎn)大于其鄰接邊數(shù)，使得TopK集能較為近似地反映圖中支配集節(jié)點(diǎn)的情況。

本文改進(jìn)的最小權(quán)重支配集的偽代碼如下:

算法1 MWDS

由于將全圖的搜索范圍縮小到TopK集內(nèi)，故由此類貪心算法的近似因子[13-14]可得其近似度1+log(ΔTopK||OPT||),其中ΔTopK為TopK集內(nèi)的最大度，OPT為最小權(quán)重支配集的點(diǎn)數(shù)。

2.3 通過求解斯坦納樹問題來生成故事線

通過以上貪心算法我們獲得了具有代表性的微博節(jié)點(diǎn)，現(xiàn)在我們需要將這些微博節(jié)點(diǎn)‘平滑’地串起來以反映事件的發(fā)展階段。為了解決這個(gè)問題，我們引入了有向斯坦納樹，通過將其轉(zhuǎn)化為有向斯坦納樹問題予以解決。

定義4 有向斯坦納樹問題. 給定一個(gè)有向權(quán)圖G=(V,W,A)，一個(gè)終點(diǎn)集S,一個(gè)根r∈S(S中的每一點(diǎn)到r都是可達(dá)的)，一個(gè)覆蓋點(diǎn)數(shù)約束k。問題主要是在有向圖G中找一棵覆蓋S中的k個(gè)點(diǎn)且擁有最小花費(fèi)的子樹。

由于在無向圖中此問題是NP難問題，顯然在有向圖中其同樣為NP難問題。對于此問題，前人已經(jīng)做了一些好的近似算法。而本文主要采用Charikar和Chekuri于1999年提出的近似算法[15]并對其進(jìn)行了一定優(yōu)化。算法的主要思路是尋找從根節(jié)點(diǎn)到每個(gè)終結(jié)點(diǎn)的最短路徑并將它們合并起來。算法輸入是一個(gè)層參數(shù)i(i≥1)，一個(gè)終結(jié)點(diǎn)集X，一個(gè)根節(jié)點(diǎn)r，一個(gè)覆蓋點(diǎn)數(shù)約束k(要求生成的子樹要覆蓋終結(jié)點(diǎn)集X中的k個(gè)點(diǎn))，當(dāng)i=1時(shí)，算法返回到當(dāng)前根節(jié)點(diǎn)最近的X中的k個(gè)點(diǎn)的最短路徑的集合。定義有向權(quán)圖G中邊的權(quán)為該邊始點(diǎn)的權(quán)，例如，邊(u，v)的權(quán)就是u的點(diǎn)權(quán)。

本文的改進(jìn)主要是結(jié)合微博數(shù)據(jù)的實(shí)時(shí)性，在其中引入時(shí)間窗口，時(shí)間窗口的下限為支配集中最早的時(shí)間點(diǎn)，時(shí)間窗口的上限為支配集中最晚的時(shí)間點(diǎn)，這樣有效地限制了其在搜索時(shí)的深度，同時(shí)不影響故事線的生成，使其更適應(yīng)較大規(guī)模數(shù)據(jù)條件下的處理。

本文改進(jìn)的有向斯坦納樹的偽代碼如下:

算法2 DST

3 數(shù)據(jù)獲取及中文微博處理

本文所采用的數(shù)據(jù)主要是從新浪微博上爬取的。我們設(shè)計(jì)的爬取方案主要是在獲得其相關(guān)授權(quán)后，利用新浪微博的API，從指定的節(jié)點(diǎn)開始爬取數(shù)據(jù)，并將其存入數(shù)據(jù)庫。其架構(gòu)如圖2所示。

圖2 爬蟲架構(gòu)圖

本文所采用的爬蟲和傳統(tǒng)的爬蟲思路相同，即先取得一個(gè)入口點(diǎn)，例如，授權(quán)用戶，然后將入口點(diǎn)的關(guān)注列表和跟隨者列表加入隊(duì)列，同時(shí)讀取每個(gè)人最近的微博，再獲取它們的關(guān)注列表和跟隨者列表，擴(kuò)散式地往下搜索。

本文主要是利用Lucene結(jié)合IK Analyzer來對中文微博進(jìn)行處理，即: 從數(shù)據(jù)庫中逐條抽取出微博，利用Lucene將微博的用戶、時(shí)間、內(nèi)容等索引起來，在構(gòu)建索引時(shí)，利用IK Analyzer來進(jìn)行中文分詞。

4 實(shí)驗(yàn)結(jié)果和分析

本文將通過實(shí)驗(yàn)全面地論證我們系統(tǒng)的可行性和優(yōu)越性。首先，將生成故事線的方法及其子部分和其他方法作比較，驗(yàn)證使用最小權(quán)重支配集和斯坦納樹生成故事線的優(yōu)勢，這部分將在4.1中介紹；其次，本文將比較系統(tǒng)的一些參數(shù)的調(diào)節(jié)情況，這部分將在4.2中介紹；最后，將做一些用戶測評，來主觀比較我們系統(tǒng)和其他系統(tǒng)生成故事線的好壞，這部分將在4.3中介紹。

本文的數(shù)據(jù)集是通過爬蟲從新浪微博上爬取下來的微博，這些微博經(jīng)過隨機(jī)采樣，其時(shí)間點(diǎn)分布是分散的，涉及到的話題也是千差萬別的。其基本統(tǒng)計(jì)信息見表1。

表1 微博數(shù)據(jù)集的統(tǒng)計(jì)信息

在實(shí)驗(yàn)中，本文主要使用ROUGE[16](版本1.5.5)來進(jìn)行評價(jià)。ROUGE是一個(gè)廣泛用于文本摘要的評價(jià)工具，它通過與人工摘要比較計(jì)算其重疊部分的內(nèi)容來評估該摘要的質(zhì)量。其評價(jià)指標(biāo)有三個(gè): 精度、召回率和F-measure。本文選用F-measure作為評價(jià)指標(biāo)。其評估方法也有多種，主要是ROUGE-N、ROUGE-L、ROUGE-W和ROUGE-SU，本文都予以選用，以全面評估系統(tǒng)的好壞。

4.1 故事線生成質(zhì)量比較

由于故事線生成的方法很少，因而我們在檢索出相關(guān)微博的基礎(chǔ)上，通過使用不同的文本摘要方法從其中抽取出關(guān)鍵的微博形成故事線來進(jìn)行比較。

我們從2009年8月至2012年5月之間選取了比較熱門的十個(gè)事件作為查詢，同時(shí)，對于每個(gè)查詢，我們在Lucene檢索的結(jié)果集上按照時(shí)間的連續(xù)性和事件的相關(guān)性挑出微博來組成故事線，人工做了四條故事線作為評測標(biāo)準(zhǔn)。

這里將用我們的方法和近年來較有影響力的文本摘要[19]方法進(jìn)行比較。

1) Random: 隨機(jī)選取句子作為摘要

2) PRF[5]: 利用偽反饋的語言模型來選取最相關(guān)的句子作為摘要；

3) LexPageRank[17]: 根據(jù)句子的語義相似度構(gòu)建圖，利用與PageRank相似的算法來尋找其中的核心節(jié)點(diǎn)作為摘要；

4) NMF[6]: 通過構(gòu)建句子-詞矩陣并將其分解來獲得每個(gè)句子的權(quán)重并排序構(gòu)成摘要；

5) SNMF[7]: 通過構(gòu)建句子語義相似度矩陣，并進(jìn)行對稱非負(fù)矩陣分解，對得到的結(jié)果進(jìn)行聚類和計(jì)算其句子的權(quán)重并排序來獲得摘要；

6) LSA[18]: 構(gòu)建句子-詞矩陣并對其進(jìn)行SVD分解，在其右奇異向量上找到索引值最大的句子作為摘要。

本文的方法和以上方法的比較結(jié)果見表2，從中可以看出，我們方法的效果要明顯好于其他方法。

表2 我們生成故事線的方法和傳統(tǒng)方法比較

本文方法能取得良好的效果主要是基于以下兩方面: (1)使用最小權(quán)重支配集算法選取核心微博，使從查詢集中抽取出的微博高度相關(guān)，為生成故事線奠定了基礎(chǔ)； (2)使用有向斯坦納樹來將那些核心微博節(jié)點(diǎn)“平滑”的串起來以生成故事線，使得生成的故事線內(nèi)容連貫，時(shí)間連續(xù)，邏輯清楚。接下來的實(shí)驗(yàn)將對這兩方面進(jìn)行驗(yàn)證。

首先，本文將評估最小權(quán)重支配集算法選取具有代表性的微博的質(zhì)量，驗(yàn)證最小權(quán)重支配集算法較其他方法更適于選取具有代表性的微博。本文主要用傳統(tǒng)的文本聚類方法NMF和SNMF以及檢索語言模型PRF和其比較。實(shí)驗(yàn)主要通過將這些方法運(yùn)用在Lucene檢索的查詢集上，抽取出核心微博組成摘要和人工生成的摘要進(jìn)行比較。

實(shí)驗(yàn)結(jié)果見圖3。從比較結(jié)果來看，最小權(quán)重支配集算法的效果明顯好于其他方法?？梢?，最小權(quán)重支配集算法較傳統(tǒng)的文本聚類算法以及一些檢索語言模型更適于在微博上選取具有代表性的節(jié)點(diǎn)。

圖3 最小權(quán)重支配集算法和其他方法比較

最小權(quán)重支配集算法能夠取得好的效果主要有以下三個(gè)原因: (1)在構(gòu)建多視點(diǎn)圖時(shí)，通過給其每個(gè)節(jié)點(diǎn)賦予相應(yīng)的權(quán)重(該節(jié)點(diǎn)和查詢之間的相關(guān)度)，把節(jié)點(diǎn)和查詢有機(jī)地聯(lián)系起來； (2)在計(jì)算支配集時(shí)，不僅考慮了節(jié)點(diǎn)之間的關(guān)聯(lián)度，也考慮了節(jié)點(diǎn)與查詢之間的相關(guān)度； (3)通過使支配集花費(fèi)最小，選取了最優(yōu)化的節(jié)點(diǎn)。

其次，本文將評估有向斯坦納樹生成故事線的質(zhì)量，以驗(yàn)證有向斯坦納樹生成的故事線的效果。本文將在最小權(quán)重支配集的基礎(chǔ)上，通過比較timeline(按時(shí)間順序輸出)和斯坦納樹生成故事線的質(zhì)量。

實(shí)驗(yàn)結(jié)果見圖4。從比較結(jié)果來看，有向斯坦納樹生成的故事線的質(zhì)量要好于Timeline，由此可知，斯坦納樹更能“平滑”地將微博串起來以生成故事線，其生成的故事線也更能反映事件的發(fā)展階段，邏輯更加清楚。

綜上，本文通過最小權(quán)重支配集算法和有向斯坦納樹算法來生成故事線是可行的，也較其他方法更有優(yōu)勢。

4.2 參數(shù)調(diào)節(jié)

在以上客觀地論證了我們提出方法的優(yōu)勢后，這部分將詳細(xì)介紹系統(tǒng)中的一些重要參數(shù)的調(diào)節(jié)情況。

首先，對于構(gòu)建多視點(diǎn)圖中無向邊的相似度閾值的調(diào)節(jié)，實(shí)驗(yàn)中我們將閾值從0.2開始調(diào)節(jié)，到0.7為止，步長為0.05。其實(shí)驗(yàn)結(jié)果見圖5。通過不同閾值的比較可知，相似度的閾值對支配集的生成有一定影響，閾值并不是越高越好，過高的閾值會增加圖中的孤立點(diǎn)數(shù)，影響支配集的生成。

圖4 有向斯坦納樹算法和timeline比較

圖5 無向邊的相似度閾值調(diào)節(jié)情況

接下來，本文將介紹構(gòu)建多視點(diǎn)圖中影響有向邊生成的時(shí)間窗口的閾值(τ1、τ2)的調(diào)節(jié)情況。直觀上看，時(shí)間窗口不能太大，過大的時(shí)間窗口不能反映事件在時(shí)間上的連續(xù)性，同時(shí)也不能太小，過小的時(shí)間窗口則使圖太稀疏。按照常規(guī)的事件發(fā)展來看，時(shí)間窗口應(yīng)以1-7天為宜。故此，實(shí)驗(yàn)中，我們首先將τ1設(shè)為1天，變化τ2至7天為止，研究τ2的影響。接下來，我們τ2設(shè)為5天，將τ1從1天開始調(diào)節(jié)，研究τ1的影響。

實(shí)驗(yàn)結(jié)果見圖6(a)、(b)，從中可知，當(dāng)τ1=1、τ2變化時(shí)，其結(jié)果較為平穩(wěn)；而當(dāng)τ1=3時(shí)，實(shí)驗(yàn)結(jié)果最好；而當(dāng)τ2=5，τ1變化時(shí)，其變化則較為劇烈，且隨著τ1的增大，實(shí)驗(yàn)效果變差。

圖6 (a)時(shí)間窗口閾值τ1=1，τ2變化情況; (b)時(shí)間窗口閾值τ2=5，τ1變化情況

最后，本文將介紹有向斯坦納樹中根的選取情況。從算法角度上看，根的選取將很大程度上影響最后生成故事線的質(zhì)量。而一個(gè)好的根應(yīng)該具備以下兩個(gè)條件: (1)其時(shí)間點(diǎn)在數(shù)據(jù)集中應(yīng)盡可能早；(2)其在語義上應(yīng)盡可能相似于查詢。因而，我們通過設(shè)定相似度閾值，在支配集中找一個(gè)時(shí)間點(diǎn)最早且達(dá)到閾值的節(jié)點(diǎn)作為根，通過比較閾值的設(shè)定來分析該相似度的影響。

實(shí)驗(yàn)結(jié)果見圖7，從中可知，相似度一定程度上影響根選取的效果，且隨著相似度閾值的提高，實(shí)驗(yàn)結(jié)果的總體趨勢是下降的。過高的相似度閾值使得根選取的時(shí)間點(diǎn)過于晚，從而影響了其生成故事線的質(zhì)量。

圖7 根的相似度閾值選取情況

4.3 用戶測評

由于評估故事線的質(zhì)量是比較主觀的，很難評價(jià)其結(jié)構(gòu)性和相關(guān)性?；诖宋覀冞M(jìn)行了一次用戶調(diào)查，隨機(jī)選了15位學(xué)生參加。在調(diào)查中，本文所用的查詢是相同的，數(shù)據(jù)與上文實(shí)驗(yàn)部分所采用的相同。每個(gè)參與者將會比較不同系統(tǒng)在同一個(gè)話題下生成的故事線，用1～5分來衡量對系統(tǒng)的滿意度。我們實(shí)現(xiàn)的系統(tǒng)是:

1) LPR: 主要使用LexPageRank的方法來生成故事線；

2) NMF: 主要使用NMF文本聚類方法來生成故事線；

3) SNMF: 主要使用SNMF文本聚類方法來生成故事線；

4) LSA: 主要使用LSA語義分析的方法來生成故事線；

5) PRF: 主要使用偽反饋的語言模型來生成故事線；

6) ours: 本文提出的系統(tǒng)。

圖8是本文提出的系統(tǒng)對一個(gè)例子(其查詢是“北約空襲利比亞”)生成故事線的效果圖，從中可以看出其內(nèi)容比較相關(guān)，結(jié)構(gòu)比較清晰，事件發(fā)展階段清楚。表3顯示的是用戶對每個(gè)系統(tǒng)的平均滿意度。從中可知: (1)用戶對我們系統(tǒng)生成的故事線滿意度明顯高于其他系統(tǒng)； (2)用戶更喜歡結(jié)構(gòu)清晰的故事線而非單一的文本摘要，因?yàn)楣适戮€更易于用戶理解。

圖8 本文提出系統(tǒng)的效果圖

系統(tǒng)PRFLPRLSANMFSNMFOurs滿意度3．133．733．403．603．134．13

5 結(jié)論

本文基于前人提出的系統(tǒng)[10]，解決了中文微博故事線生成的問題，并在兩個(gè)方面進(jìn)行了優(yōu)化: 對于最小權(quán)重支配集算法，通過在其中引入TopK集，縮小了貪心算法的計(jì)算空間，減少了其時(shí)間花費(fèi)；而對于有向斯坦納樹算法，通過在其中加入時(shí)間窗口，約束了其搜索的下限，減少了處理花費(fèi)。通過這些優(yōu)化，使本文提出的系統(tǒng)更適合于較大規(guī)模的中文微博的故事線生成，而通過在新浪微博數(shù)據(jù)上的實(shí)驗(yàn)和用戶調(diào)查也驗(yàn)證了該結(jié)論。

在未來的工作中，我們將會在以下兩方面進(jìn)一步優(yōu)化我們的系統(tǒng): (1)對多視點(diǎn)圖進(jìn)行改進(jìn)，使其能反映更多的信息； (2)在最小權(quán)重支配集算法中引入可信度，進(jìn)一步提高查找具有代表性微博的精度。

[1] 張劍峰,夏云慶,姚建民. 微博文本處理研究綜述[J]. 中文信息學(xué)報(bào).2012,26(4): 21-27.

[2] 文坤梅,徐帥,李瑞軒,等. 微博及中文微博信息處理研究綜述[J]. 中文信息學(xué)報(bào).2012，26(6)： 27-37.

[3] Teevan J,Ramage D,Morris M R. #Twitter Search: a comparison of microblog search and web search[C]//Proceedings of the 4th International Coference on Web Search & Web Data Mining. 2015: 35-44.

[4] 莫溢,劉盛華,劉悅,程學(xué)旗. 一種相關(guān)話題微博信息的篩選規(guī)則學(xué)習(xí)算法[J]. 中文信息學(xué)報(bào).2012，26(5): 27-37

[5] Cao G,Nie J Y,Gao J,et al. Selecting good expansion terms for pseudo-relevance feedback SIGIR[C]//Proceedings of the SIGIR 2008: 243-250.

[6] Park S,Lee J H,Kim D H,et al. Multi-document summarization based on cluster using non-negative matrix factorization[J]. SOFSEM 2007: Theory and Practice of Computer Science,2007: 761-770.

[7] Wang D,Li T,Zhu S,et al. Multi-document summarization via sentence-level semantic analysis and symmetric matrix factorization[C]//Proceedings of the SIGIR,2008: 307-314.

[8] Mei Q,Zhai C X. Discovering evolutionary theme patterns from text: an exploration of temporal text mining[C]//Proceedings of the SIGKDD,2005: 198-207.

[9] Yan R,Wan X,Otterbacher J,et al. Evolutionary timeline summarization: a balanced optimization framework via iterative substitution[C] //Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval. 2011: 745-754.

[10] Lin C,Lin C,Li J,et al. Generating Event Storylines from Microblogs[C]//Proceedings of the ACM,2012: 175-184.

[11] Shen C,Li T. Multi-document summarization via the minimum dominating set[C].ACL,2010: 984-992.

[12] Raz R,Safra S. A sub-constant error-probability low-degree test,and a sub-constant error-probability PCP characterization of NPSTOC[C]//Proceedings of the 29th Acm Symposium on the Theory of Couputingl.1997: 475-484.

[13] Johnson D S. Approximation algorithms for combinatorial problems[J]. Journal of computer and system sciences,1974,9(3): 256-278.

[14] Chvatal V. A greedy heuristic for the set-covering problem[J]. Mathematics of operations research,1979,4(3): 233-235.

[15] Charikar M,Chekuri C,Cheung T,et al. Approximation algorithms for directed Steiner problems SODA,1998: 192-200.

[16] Lin C Y,Hovy E. Automatic evaluation of summaries using n-gram co-occurrence statisticsACL-HLT2003: 71-78.

[17] Erkan G,Radev D R. Lexpage rank: Prestige in multi-document text summarization[C]//Proceedings of the EMNLP.2004,4.

[18] Dumais S T. Latent semantic analysis[J].Annual Review of Information Science and Technology,2005,38(1): 188-230.

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

[20] Wang D,Li T,Ogihara M. Generating Pictorial Storylines via Minimum-Weight Connected Dominating Set Approximation in Multi-View Graphs AAAI 2012[J],PM&R,2012,6(8): 595.

Method for Generating Microblogs Storylines

LI Pei1,WENG Wei2,LIN Chen1,3

(1. School of Information Science and Technology,Xiamen University,Xiamen,Fujian 361005 China;2. School of Computer and Information Engineering,Xiamen University of Technology,Xiamen,Fujian 361024 China;3. Shenzhen Research Institute of Xiamen University,Shenzhen,Guangdong 518057 China)

As microblog becomes an major web medium for individuals sharing and spreading instant information,mining the event evolution on microblogs arises to be a practical task. In this paper,we exploit Minimum-Weight Connected Dominating Set and Directed Steiner Tree to generate storyline from microblog for user input queries. Our framework consists of three stages: 1)Construction of a multi-view graph on the relevant Microblogs obtained by Lucene for user's queries； 2) Selection of the representative microblogs by finding the Minimum-Weight Connected Dominating Set; and 3) Connection of the microblogs as search for the Directed Steiner Tree. Experiments on real datasets demonstrate the efficiency and effectiveness of the proposed framework.

microblog storyline;minimum-weight connected dominating set; directed steiner tree

李培(1990—)，碩士，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘。E?mail：peili@stu．xmu．edu．cn翁偉(1979—)碩士，講師，主要研究領(lǐng)域?yàn)閿?shù)據(jù)庫與數(shù)據(jù)挖掘。E?mail：林琛(1982—)，博士，助理教授，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘。E?mail：chenlin@xmu．edu．cn

2014-02-24 定稿日期： 2014-06-09

上海市智能信息處理重點(diǎn)實(shí)驗(yàn)室開放課題(IIPL-2011-004)；國家自然科學(xué)基金(61102136，61370010,81101115)；福建省自然科學(xué)基金(2011J05158,2011J01371)；CCF-騰訊犀牛鳥科研基金(CCF-Tencent20130101)；深圳市基礎(chǔ)研究計(jì)劃(JCYJ20120618155655087)

1003-0077(2016)03-0143-09

TP391

A