李瑩瑩 馬 帥 蔣浩誼 劉 喆 胡春明 李 雄

1(軟件開(kāi)發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室(北京航空航天大學(xué)) 北京 100191) 2(北京大數(shù)據(jù)科學(xué)與腦機(jī)智能高精尖創(chuàng)新中心(北京航空航天大學(xué)) 北京 100191) 3(國(guó)家計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心 北京 100029) (liyy@act.buaa.edu.cn)

社交網(wǎng)絡(luò)已被政府、公司甚至總統(tǒng)(如奧巴馬、特朗普等)等廣泛用于發(fā)布新聞和報(bào)道事件.社交網(wǎng)絡(luò)中信息的實(shí)時(shí)性和快速傳播的能力使其成為獲取信息的重要媒介.短文本的表述方式也能夠有效地傳遞關(guān)鍵信息.社交網(wǎng)絡(luò)的這些特性顛覆了傳統(tǒng)媒體在信息傳播上的統(tǒng)治力，這使其為監(jiān)控事件及其演化提供了寶貴數(shù)據(jù).然而，社交網(wǎng)絡(luò)中文本的快速積累、口語(yǔ)化的表達(dá)方式以及文本內(nèi)容中的錯(cuò)別字使得監(jiān)控事件及事件間的演化具有極大挑戰(zhàn).從社交網(wǎng)絡(luò)文本中對(duì)具有同一主題的的事件及其演化進(jìn)行提取能夠極大地幫助我們?cè)谌吧蠈?duì)某一事件進(jìn)行了解.例如：我們期望獲得關(guān)于平昌冬奧會(huì)所有項(xiàng)目(即事件)的信息和這些項(xiàng)目的進(jìn)程(即事件演化).這需要我們首先檢測(cè)事件，而后對(duì)這些事件進(jìn)行聚類(lèi)從而獲得具有同一主題的事件(即故事)，并最終以一種用戶(hù)友好的方式(故事脈絡(luò))呈現(xiàn)出來(lái).

目前針對(duì)該問(wèn)題的方法按照是否需要用戶(hù)提供關(guān)鍵詞，大致可分為2類(lèi)：1)關(guān)鍵詞檢索依賴(lài)型算法，將該問(wèn)題形式化為信息檢索問(wèn)題，依據(jù)用戶(hù)提供的關(guān)鍵詞生成故事脈絡(luò)，如MetroMap[1]首先依據(jù)用戶(hù)提供的關(guān)鍵詞匹配到相關(guān)的文檔，然后用其構(gòu)造用于表示故事脈絡(luò)的多尺度地圖.再如Wang等人[2]首先依據(jù)主題相關(guān)的包含文本描述的圖像集合用圖像的文本和時(shí)間相似度構(gòu)造帶權(quán)重的圖，然后通過(guò)在該圖上解決最小權(quán)重支配集(minimum-weighted connected dominating set)問(wèn)題選擇用于表示故事脈絡(luò)的對(duì)象；再如GESM[3]首先依據(jù)用戶(hù)提供的關(guān)鍵詞得到相關(guān)的微博，然后依據(jù)Wang等人[2]的算法構(gòu)造故事脈絡(luò).然而，這類(lèi)方法嚴(yán)重依賴(lài)于用戶(hù)所提供的關(guān)鍵詞，而對(duì)于用戶(hù)無(wú)法提供關(guān)鍵詞的情況，這類(lèi)算法無(wú)法提供相應(yīng)的結(jié)果，這限制了該類(lèi)方法的應(yīng)用.2)為了解決這一問(wèn)題，關(guān)鍵詞檢索獨(dú)立型算法能夠自動(dòng)生成故事脈絡(luò)，如CAST[4]首先從數(shù)據(jù)流中基于微博的文本相似度和時(shí)間相似度構(gòu)造微博圖，并將微博圖中稠密子圖做為事件，然后依據(jù)事件間的相似度構(gòu)造事件間關(guān)系，依據(jù)事件間關(guān)系追蹤事件的上下文.StoryGraph[5]則將每天的新聞文本分到不同主題集合中，然后通過(guò)新產(chǎn)生的主題與已經(jīng)存在的主題的Pearson相關(guān)系數(shù)決定事件的演化.

然而，故事脈絡(luò)生成仍然存在2個(gè)問(wèn)題：1)事件由微博集合表示且有特定主題，如何從微博集合提取與事件對(duì)應(yīng)的強(qiáng)相關(guān)的微博集合是一個(gè)關(guān)鍵問(wèn)題.目前，針對(duì)該問(wèn)題研究者們已經(jīng)提出多種解決方式，然而如何選擇最優(yōu)的方法是一個(gè)具有挑戰(zhàn)的問(wèn)題.2)對(duì)有關(guān)聯(lián)關(guān)系的事件如何進(jìn)行有效組裝，并以故事脈絡(luò)的形式展示是另一個(gè)關(guān)鍵問(wèn)題.

為此，我們將該問(wèn)題形式化為3個(gè)連續(xù)的步驟，即事件檢測(cè)、故事組裝以及故事脈絡(luò)生成.本文的主要貢獻(xiàn)有3個(gè)方面：

1) 從微博檢測(cè)事件.依據(jù)事件的隱式語(yǔ)義信息關(guān)聯(lián)事件并組裝故事，為故事生成故事脈絡(luò)以可視化故事的發(fā)展過(guò)程;

2) 提出用包含摘要的有向無(wú)環(huán)圖描述故事脈絡(luò).該故事脈絡(luò)既可以使用戶(hù)了解故事，也可使用戶(hù)了解故事的發(fā)展過(guò)程;

3) 利用新浪微博數(shù)據(jù)集評(píng)價(jià)我們提出的故事脈絡(luò)生成方法.基于用戶(hù)體驗(yàn)的實(shí)驗(yàn)表明我們方法的性能優(yōu)于現(xiàn)有方法.

1 研究問(wèn)題和系統(tǒng)框架

在本節(jié)中，我們首先介紹術(shù)語(yǔ)的定義；然后，我們陳述所研究的問(wèn)題；最后，我們描述系統(tǒng)框架.

1.1 術(shù)語(yǔ)定義

定義1.微博.一個(gè)微博m由二元組M,Tm表示，其中，1)M是微博的內(nèi)容;2)Tm是微博的產(chǎn)生時(shí)間.

定義2.事件.一個(gè)事件e是在某時(shí)間和地點(diǎn)發(fā)生的事件[6],例如：“正確的中國(guó)國(guó)旗趕制完成預(yù)計(jì)11日運(yùn)抵里約”是一個(gè)事件.其由六元組(式)Te,Microblog_set,Ce,Le,Pe,De表示.其中，1)Te表示檢測(cè)到事件的時(shí)間;2)Microblog_set表示事件的微博集合;3)Ce表示記錄事件主要信息的核心詞集合;4)Le表示事件的地點(diǎn);5)Pe表示事件的參與者集合;6)De表示事件的描述，該描述由一個(gè)短句子表示.我們基于微博集合Microblog_set識(shí)別Le,Pe和De特征.

定義3.故事.一個(gè)故事s定義為屬于相同主題的事件集合，例如“2016里約奧運(yùn)會(huì)”是一個(gè)故事，其由五元組(式)Event_set,Ts,Cs,Ls,Ps表示.其中，1)Event_set表示故事的事件集合;2)Ts表示故事的時(shí)間段;3)Cs表示故事的核心詞集合;4)Ls表示故事的地點(diǎn)集合;5)Ps表示故事的參與者集合.我們基于故事的事件集合Event_set識(shí)別Ts,Cs,Ls和Ps特征.

Fig.1 The storyline in a story (“2016 Rio Olympic Games”)圖1 “2016巴西奧運(yùn)”故事的故事脈絡(luò)

定義4.故事脈絡(luò)(storyline).用于可視化故事的發(fā)展過(guò)程，其由二元組skeleton,summary表示，其中,1)skeleton是展示故事內(nèi)事件間演化的有向無(wú)環(huán)圖;2)summary是描述故事大意的短句子.

例1.圖1中故事“2016巴西奧運(yùn)”的故事脈絡(luò)(部分)用于可視化該故事的發(fā)展過(guò)程.圓結(jié)點(diǎn)代表事件，事件的描述和檢測(cè)時(shí)間(UTC+8)在該結(jié)點(diǎn)的右側(cè).事件結(jié)點(diǎn)的索引號(hào)表示該事件在時(shí)間軸上的順序，索引號(hào)越大表示事件的時(shí)間越靠后.從事件結(jié)點(diǎn)ei到事件結(jié)點(diǎn)ej的有向邊表示他們之間的時(shí)序演化關(guān)系.該故事脈絡(luò)有3個(gè)分支：分支A、分支B和分支C.分支A與“巴西里約奧運(yùn)俄羅斯部分運(yùn)動(dòng)員被禁賽”相關(guān)；分支B與“巴西里約奧運(yùn)中國(guó)國(guó)旗有誤”相關(guān)；分支C與“巴西里約奧運(yùn)美國(guó)女子4×100接力掉棒”相關(guān).故事脈絡(luò)中的多個(gè)分支展示了故事“2016巴西奧運(yùn)”的發(fā)展過(guò)程.故事摘要(summary)展示在上方的矩形框里.該摘要由各分支摘要合并而成，可幫助用戶(hù)了解故事概述.

1.2 問(wèn)題陳述

對(duì)于微博集({M1,M2,…,Mt})，其中Mt是時(shí)間片t的微博集合.我們的目標(biāo)是:1)從微博集中檢測(cè)事件({E1,E2,…,Et})，其中Et是時(shí)間片t檢測(cè)的事件集合;2)依據(jù)事件的隱式語(yǔ)義信息有效的關(guān)聯(lián)事件并組裝故事(S={s1,s2,…,sNs})，其中si表示一個(gè)故事;3)為每個(gè)故事生成一個(gè)用于可視化故事發(fā)展過(guò)程的故事脈絡(luò).

1.3 系統(tǒng)框架描述

我們用包含3個(gè)組件的框架(如圖2所示)解決故事脈絡(luò)生成問(wèn)題.首先，我們從微博集中檢測(cè)事件；然后，我們通過(guò)關(guān)聯(lián)事件組裝故事；最后，我們?yōu)槊總€(gè)故事生成描述故事發(fā)展過(guò)程的故事脈絡(luò).

Fig.2 System framework圖2 系統(tǒng)框架

1.3.1 事件檢測(cè)

我們從微博集中檢測(cè)事件.首先，從微博集得到由表示事件的核心詞和核心詞間共現(xiàn)關(guān)系構(gòu)成的核心詞圖；然后，發(fā)現(xiàn)核心詞圖中緊密連接的子圖并將子圖做為事件的核心詞集合；最后，為事件識(shí)別其他的特征Te，Le，Pe，De和Microblog_set.

1.3.2 故事組裝

我們依據(jù)主題對(duì)事件分組，將事件組裝成故事.首先，我們依據(jù)事件的隱式語(yǔ)義信息對(duì)事件聚類(lèi)，將一個(gè)簇認(rèn)為一個(gè)故事；然后，我們?yōu)槊總€(gè)故事識(shí)別其他的特征Ts，Ls，Ps和Cs.

1.3.3 故事脈絡(luò)生成

我們?yōu)槊總€(gè)故事生成故事脈絡(luò)，該故事脈絡(luò)由包含摘要的事件有向無(wú)環(huán)圖表示.首先，我們從故事的事件集基于弱連通分量和最大生成樹(shù)構(gòu)造有向無(wú)環(huán)圖(skeleton)；然后，我們基于故事的所有事件描述提取短文本作為故事的摘要.

2 系統(tǒng)組件

針對(duì)在第1節(jié)中形式化的3個(gè)步驟，即事件檢測(cè)、故事組裝和故事脈絡(luò)生成，我們?cè)诒竟?jié)具體介紹所對(duì)應(yīng)的實(shí)現(xiàn)方法.

2.1 事件檢測(cè)

在事件檢測(cè)步驟，我們旨在從微博數(shù)據(jù)中檢測(cè)事件.為幫助用戶(hù)理解故事的發(fā)展過(guò)程，我們認(rèn)為故事中的事件應(yīng)該可以使用戶(hù)剖析故事的細(xì)節(jié)，即事件應(yīng)屬于特定主題且具有細(xì)粒度性.

表示事件的詞、核心詞，在使用頻率和與其他詞的共現(xiàn)模式上較于該詞的歷史時(shí)刻有異常的變化[7].單個(gè)核心詞表示的事件粒度較粗，不足以表達(dá)事件的全部信息.例如單個(gè)核心詞、輔警，只能表示該事件與輔警有關(guān).緊密連接的核心詞集合可以詳細(xì)地表達(dá)事件信息，增加事件內(nèi)容覆蓋率.例如，緊密連接的核心詞集合，江蘇省、沐陽(yáng)、追授、犧牲和輔警，可詳細(xì)表述“江蘇省政府追授沭陽(yáng)因公犧牲輔警孫孟濤見(jiàn)義勇為英雄稱(chēng)號(hào)”事件.用核心詞集合表示的事件不利于用戶(hù)理解講述的內(nèi)容，我們用事件的結(jié)構(gòu)化表示幫助用戶(hù)理解事件.

我們用3個(gè)連續(xù)的模塊完成事件檢測(cè)任務(wù).首先，用熱點(diǎn)發(fā)現(xiàn)算法[7]發(fā)現(xiàn)表示事件的具有異常出現(xiàn)頻率的詞(核心詞)；然后，用重疊的社區(qū)檢測(cè)算法[8]提取緊密連接的核心詞集合對(duì)事件進(jìn)行詳細(xì)描述；最后，從微博識(shí)別事件其余特征，方便用戶(hù)理解事件.下面描述的3個(gè)連續(xù)的模塊完成事件檢測(cè)任務(wù)，我們采用Ring[9]實(shí)現(xiàn)的事件檢測(cè)算法.

2.1.1 核心詞發(fā)現(xiàn)

在核心詞發(fā)現(xiàn)階段，我們發(fā)現(xiàn)表示事件的核心詞.表示事件的詞在使用頻率和與其他詞的共現(xiàn)模式上較于該詞的歷史時(shí)刻有異常變化[7].我們用HOTSPOT[7]檢測(cè)能描述事件的詞.該算法首先依據(jù)微博數(shù)據(jù)構(gòu)造詞共現(xiàn)圖；然后檢測(cè)有異常變化的詞，即核心詞，并輸出核心詞及核心詞間共現(xiàn)關(guān)系構(gòu)成的圖(核心詞圖).

2.1.2 核心詞社區(qū)提取

在核心詞社區(qū)提取階段，我們提取表示事件的核心詞集合.事件的核心詞通常緊密連接.依據(jù)上一步輸出的核心詞圖，我們用社區(qū)檢測(cè)算法[8]檢測(cè)緊密連接的核心詞社區(qū)，即由詞(點(diǎn))和詞間共現(xiàn)關(guān)系(邊)構(gòu)成的稠密子圖.核心詞社區(qū)對(duì)應(yīng)事件的核心詞集合，其能夠有效地描述一個(gè)事件.我們依據(jù)圖3(a)展示的核心詞圖檢測(cè)出圖3(b)的核心詞社區(qū)，該核心詞社區(qū)表示“江蘇省政府追授沭陽(yáng)因公犧牲輔警孫孟濤見(jiàn)義勇為英雄稱(chēng)號(hào)”事件.

Fig.3 A core word community in the core word graph圖3 核心詞圖的一個(gè)核心詞社區(qū)

2.1.3 事件特征識(shí)別

在事件特征識(shí)別階段，我們將事件的數(shù)據(jù)進(jìn)行結(jié)構(gòu)化以增加事件的描述信息.僅用核心詞集合表示事件存在不足，如碎片化和易讀性差.我們將用核心詞集合表示的事件擴(kuò)充為事件六元組，過(guò)程如下：

1) 我們將時(shí)間Te賦值為事件被檢測(cè)的時(shí)間(每10 min);

2) 我們依據(jù)核心詞集合尋找包含事件所有核心詞的微博集合Microblog_set;

3) 我們將描述De賦值為事件的微博集合中包含核心詞集合中的詞最多的句子;

4) 我們從事件的微博集合中識(shí)別所有的命名實(shí)體(named entity)，包括地名、人名和機(jī)構(gòu)名等;

5) 我們將地點(diǎn)Le賦值為事件的微博集合中最頻繁出現(xiàn)的地名;

6) 我們將參與者集合Pe賦值為事件的微博集合中出現(xiàn)的人名和機(jī)構(gòu)名.

2.2 故事組裝

在故事組裝步驟，我們旨在通過(guò)關(guān)聯(lián)事件組裝故事.為幫助用戶(hù)從全景了解故事，故事應(yīng)囊括該主題下所有事件，即故事組裝需有效組裝有關(guān)聯(lián)的事件.

依據(jù)事件詞的相似度，即事件的顯式語(yǔ)義信息，將有關(guān)聯(lián)關(guān)系的事件聚成簇是簡(jiǎn)單直觀的方式.但基于顯式語(yǔ)義信息聚類(lèi)得到的簇粒度較細(xì)，即只能將詞相似度較高的事件聚到相同的簇.考慮到相同故事的事件可能包含較少的共有詞，如表1所示，事件e10和事件e11僅包含“Rio”和“Olympic”兩個(gè)共有詞，基于顯式語(yǔ)義信息的聚類(lèi)不能有效組裝有關(guān)聯(lián)關(guān)系的事件.Latent Dirichelet Allocation(LDA)為數(shù)據(jù)集中的數(shù)據(jù)，例事件集合中的事件，生成有利于相似性和相關(guān)性判斷的主題分布[10].我們通過(guò)用LDA生成事件的主題分布發(fā)現(xiàn)事件e10和事件e11的主題分布很相似.為方便說(shuō)明，以下稱(chēng)事件的主題分布為隱式語(yǔ)義信息.我們基于LDA挖掘的隱式語(yǔ)義信息將相同主題的事件聚成簇.

Table 1 Two Eevents From the Story (“2016 Rio Olympic Games”)表1 故事“2016巴西奧運(yùn)”中2個(gè)事件

我們用2個(gè)連續(xù)的模塊完成故事組裝任務(wù).首先，我們依據(jù)事件的隱式語(yǔ)義信息關(guān)聯(lián)事件，將事件分到不同的故事;然后，我們依據(jù)事件的特征，識(shí)別故事的特征，生成故事的結(jié)構(gòu)化表示，以便用戶(hù)查詢(xún).

2.2.1 故事構(gòu)造

我們用預(yù)聚類(lèi)和細(xì)聚類(lèi)的方式組裝故事.首先，我們用聚類(lèi)算法DBSCAN[11]實(shí)現(xiàn)預(yù)聚類(lèi)，即依據(jù)顯式語(yǔ)義信息對(duì)事件分組；然后，我們用預(yù)聚類(lèi)的結(jié)果初始化LDA中故事的詞分布，并依據(jù)LDA生成的隱式語(yǔ)義信息構(gòu)造故事.

1) 預(yù)聚類(lèi).預(yù)聚類(lèi)依據(jù)事件的顯式語(yǔ)義信息對(duì)事件分組.目前有很多成熟且應(yīng)用廣泛的聚類(lèi)算法.我們從成熟聚類(lèi)算法中選擇適合我們?nèi)蝿?wù)的算法.基于密度的聚類(lèi)算法DBSCAN有3個(gè)優(yōu)勢(shì)：①能處理帶噪音的數(shù)據(jù);②不需要指定類(lèi)別;③容易適應(yīng)單遍(single-pass)聚類(lèi)，即只需遍歷一遍數(shù)據(jù)集即可完成聚類(lèi).我們采用DBSCAN進(jìn)行預(yù)聚類(lèi).

首先，我們?yōu)槭录螮中每個(gè)事件e構(gòu)造詞向量we.若第k個(gè)詞在事件e中，we,k=1；否則we,k=0.然后，我們依據(jù)詞向量用DBSCAN將事件聚到類(lèi)成員P中,其中P={P1,P2,…,PI}，Pi是包含一個(gè)事件集合的預(yù)簇.DBSCAN使用的距離函數(shù):

dis(ei,ej)=1-cos(wei,wej)，

(1)

其中，wei和wej分別是事件ei和事件ej的詞向量.

最終，我們將事件集合E和基于DBSCAN的聚類(lèi)結(jié)果作為細(xì)聚類(lèi)的輸入.

2) 細(xì)聚類(lèi).細(xì)聚類(lèi)基于預(yù)聚類(lèi)的結(jié)果挖掘事件的隱式語(yǔ)義信息，依據(jù)事件的隱式語(yǔ)義信息關(guān)聯(lián)事件，并將事件賦值到故事.LDA生成的隱式語(yǔ)義信息有利于相關(guān)性判斷.用預(yù)聚類(lèi)的結(jié)果初始化LDA中故事的詞分布可減少LDA的搜索空間.

首先，我們依據(jù)預(yù)聚類(lèi)結(jié)果初始化LDA中故事的詞分布，給定預(yù)聚類(lèi)結(jié)果P，我們將相同的預(yù)簇中事件的詞賦給相同的故事；然后，我們用Gibbs Sampling推斷LDA的參數(shù)、事件的故事向量；最后，我們依據(jù)選擇標(biāo)準(zhǔn)將事件賦給故事.

選擇標(biāo)準(zhǔn).我們假設(shè)每個(gè)事件屬于且僅屬于一個(gè)故事.我們將事件賦給概率最高的故事.

算法1.故事構(gòu)造算法.

輸入:事件集合E={e1,e2,…,en}、初始故事數(shù)Ns；

輸出:故事集合S={s1,s2,…,sm}(m≤Ns).

Construct.Story (E,Ns)；

①S←{s1,s2,…,sNs}；

② {P1,P2,…,PI}←DBSCAN(E)；

③ fori=1 toIdo

④ ifi≤Nsthen

⑤k←i；

⑥ else

⑦k←random(1,Ns)；

⑧ end if

⑨ 將預(yù)簇Pi中所有事件的所有詞賦給故事sk的詞列表；

⑩ end for

故事構(gòu)造的偽代碼如算法1所示，給定事件集E，故事構(gòu)造算法構(gòu)造并返回故事集S.首先，我們用聚類(lèi)算法DBSCAN預(yù)聚類(lèi)(行②);然后，我們用DBSCAN的預(yù)聚類(lèi)結(jié)果初始化LDA(行③～⑩);隨之，我們用Gibbs Sampling推斷LDA的參數(shù)，包括推斷事件的故事向量(行～);而后，我們依據(jù)選擇標(biāo)準(zhǔn)將事件分到故事中并去掉不包含事件的故事(行～);最后，我們返回非空的故事集S(行).

2.2.2 故事特征識(shí)別

在故事特征識(shí)別階段，我們將故事的數(shù)據(jù)進(jìn)行結(jié)構(gòu)化以便于用戶(hù)查詢(xún)故事.事件檢測(cè)組件為事件生成結(jié)構(gòu)化表示，用事件的結(jié)構(gòu)化表示生成故事的結(jié)構(gòu)化表示既能充分利用相關(guān)微博的信息，也可以提高效率.我們基于事件六元組將用事件集合表示的故事擴(kuò)充為故事五元組，過(guò)程如下：1)故事的時(shí)間段Ts的開(kāi)始時(shí)間和結(jié)束時(shí)間分別被賦值為故事的事件集中事件的最早時(shí)間和最晚時(shí)間;2)故事內(nèi)包含事件的特征越多，越能幫助用戶(hù)查詢(xún)故事，故事的地點(diǎn)集合Ls、參與者集合Ps和核心詞集合Cs分別被設(shè)為故事的事件集中相應(yīng)特征的并集.

算法2.故事特征識(shí)別算法.

輸入:故事集合S={s1,s2,…,sm}；

輸出:故事集合S={s1,s2,…,sm}.

Identify.Story.Feature (S)；

① for each storys∈Sdo

②Ts.start←min({Te|e∈Event_sets})；

③Ts.stop←max({Te|e∈Event_sets})；

⑦ end for

⑧ returnS.

故事特征識(shí)別的偽代碼如算法2所示.給定故事集S，故事特征識(shí)別算法為故事集S中每個(gè)故事識(shí)別特征并返回故事集S.首先，故事的開(kāi)始時(shí)間被設(shè)為事件集中的事件的最早時(shí)間(行②)，故事的結(jié)束時(shí)間被設(shè)為事件集中事件的最晚時(shí)間(行③)；然后，故事的地點(diǎn)集合、參與者集合和核心詞集合分別被設(shè)為事件集中地點(diǎn)、參與者集合和核心詞集合的并集(行④～⑥)；最后，故事集S被返回(行⑧).

2.3 故事脈絡(luò)生成

在故事脈絡(luò)生成步驟，我們旨在為故事生成包含摘要的有向無(wú)環(huán)圖以可視化故事的發(fā)展過(guò)程.為有更好的用戶(hù)體驗(yàn)，故事脈絡(luò)應(yīng)兼顧準(zhǔn)確性和理解性.準(zhǔn)確性指故事脈絡(luò)準(zhǔn)確地展示事件的發(fā)展過(guò)程.理解性指故事脈絡(luò)便于用戶(hù)快速的了解故事.

故事可能包含多個(gè)相對(duì)獨(dú)立的部分.例“2016巴西奧運(yùn)”故事包含“巴西里約奧運(yùn)俄羅斯部分運(yùn)動(dòng)員被禁賽”和“巴西里約奧運(yùn)美國(guó)女子4×100接力掉棒”等多個(gè)相對(duì)獨(dú)立的部分.我們用弱連通分量提取故事中多個(gè)相對(duì)獨(dú)立的部分.為方便描述，下面稱(chēng)相對(duì)獨(dú)立的部分為分支.

分支內(nèi)的事件有較強(qiáng)的關(guān)聯(lián)關(guān)系.復(fù)雜的圖結(jié)構(gòu)表示的分支不便于用戶(hù)快速的理解[15].如圖4(a)中圖結(jié)構(gòu)表示的分支，雖然其充分地表達(dá)了事件間的關(guān)聯(lián)關(guān)系，但其也引入一些不必要連接，如事件e3到事件e7.為折中準(zhǔn)確性和理解性，我們用最大生成樹(shù)生成分支的樹(shù)結(jié)構(gòu)，如圖4(b)所示.

Fig.4 A branch represented by a graph or tree structure圖4 由圖或樹(shù)結(jié)構(gòu)表示的分支

我們用2個(gè)連續(xù)的模塊完成故事脈絡(luò)生成任務(wù).首先，我們從故事的事件集中基于弱連通分量和最大生成樹(shù)構(gòu)造故事骨架;然后，我們用基于圖的方法提取短文本做為故事的摘要.

2.3.1 故事骨架構(gòu)造

在故事骨架構(gòu)造階段，我們依據(jù)故事的事件集構(gòu)造用于描述故事發(fā)展過(guò)程的有向無(wú)環(huán)圖.首先，我們計(jì)算任意2事件間的權(quán)重，依此生成有向邊，構(gòu)造一個(gè)事件圖；然后，我們依據(jù)事件圖識(shí)別故事中的分支，即識(shí)別該圖中所有的弱連通分量，并形成弱連通分量集合；最后，我們?yōu)槿踹B通分量集合中每個(gè)弱連通分量構(gòu)造一個(gè)最大生成樹(shù),即用樹(shù)結(jié)構(gòu)表示的分支.這些用樹(shù)結(jié)構(gòu)表示的分支構(gòu)成故事的骨架:

w(ei,ej)=I(Tei,Tej)siml(ei,ej)×
(cpsimp(ei,ej)+ccsimc(ei,ej)),

(2)

其中，ei和ej表示2個(gè)事件,I(Tei,Tej)表示事件間的時(shí)間關(guān)系；siml，simp和simc表示2事件地點(diǎn)、參與者集合和核心詞集合的相似度；cp和cc是權(quán)重系數(shù)，該權(quán)重系數(shù)在滿(mǎn)足cp+cc=1的條件下可以被調(diào)整.

演化關(guān)系包含著事件的時(shí)間關(guān)系.有向邊只能從先發(fā)生的事件指向后發(fā)生的事件.若Tei

相同地點(diǎn)發(fā)生的事件更可能屬于相同的分支.siml用于度量2事件地點(diǎn)間的相似度.siml(ei,ej)=1，若事件ei和事件ej的地點(diǎn)相同；siml(ei,ej)=0.5，若事件ei的地點(diǎn)地理位置上屬于事件ej的地點(diǎn)，例如地點(diǎn)“中國(guó)北京”在地理位置上屬于地點(diǎn)“中國(guó)”；siml(ei,ej)=0，在其他情況下.

事件間的參與者和核心詞的相似度同樣能反映事件間的演化關(guān)系.simp(ei,ej)度量2事件的參與者集合的Jaccard系數(shù)，simc(ei,ej)度量2事件的核心詞集合的Jaccard系數(shù).

事件的微博集合由包含事件所有核心詞的微博構(gòu)成.事件的地點(diǎn)和參與者由微博集合中的命名實(shí)體構(gòu)成.因此事件的核心詞、地點(diǎn)和參與者包含了微博集合的主要信息.

我們?cè)?個(gè)組裝的故事上調(diào)節(jié)權(quán)重系數(shù)cp和cc.首先，我們使用多組權(quán)重系數(shù)構(gòu)造故事骨架.然后，我們依據(jù)骨架是否反應(yīng)故事的發(fā)展過(guò)程對(duì)多個(gè)故事骨架排序，并依據(jù)排序結(jié)果設(shè)定cp=0.3和cc=0.7.

算法3.故事骨架構(gòu)造算法.

輸入:故事s的事件集Event_set={e1,e2,…,e|Event_set|}；

輸出:故事的骨架skeleton.

Construct.Story.Skeleton(Event_set)；

① 基于Event_set創(chuàng)建一個(gè)按時(shí)間升序排列的事件列表event.list；

②skeleton←null；

③event2branch←null；*事件到分支映射*

④ fori=0 toevent.list.size-1 do

⑤event.parent←null；*父事件結(jié)點(diǎn)*

⑥edge.weight←0；*與父事件結(jié)點(diǎn)邊的權(quán)重*

⑦ forj=0 toi-1 do

⑧j2i.weight←compute.weight(event.list,j,i)；*依據(jù)式(2)計(jì)算事件j到i的有向邊權(quán)重 *

⑨ ifj2i.weight>edge.weightthen

⑩event.parent←event.list.get(j)；

branch);

branch);

故事骨架構(gòu)造的偽代碼如算法3所示.給定故事s的事件集Event_set，算法3為故事s構(gòu)造并返回故事骨架skeleton.算法計(jì)算弱連通分量的同時(shí)構(gòu)造弱連通分量的最大生成樹(shù).首先，我們依據(jù)事件的時(shí)間升序排列事件(行①).然后，我們遍歷事件(行④～).我們計(jì)算事件event與任意時(shí)間在event之前的事件間的有向邊權(quán)重，并尋找最大的權(quán)重和對(duì)應(yīng)的父事件event.parent(行⑤～).若存在父事件，則事件event屬于事件event.parent所在的分支，并在分支中添加從事件event.parent到事件event的邊(行～)，否則，構(gòu)造新的只包含事件event的分支branch(行～).最后，我們返回故事骨架skeleton(行).

時(shí)間復(fù)雜度分析.升序排列事件花費(fèi)的時(shí)間為O(|Event_set|lb(|Event_set|)).構(gòu)造弱連通分量集和最大生成樹(shù)需計(jì)算任意2事件間有向邊權(quán)重，花費(fèi)的時(shí)間為O(|Event_set|2).總花費(fèi)時(shí)間為O(|Event_set|2).

2.3.2 故事摘要提取

在故事摘要階段，我們依據(jù)故事的事件集為故事提取便于用戶(hù)了解故事概述的摘要.為使用戶(hù)從摘要了解各分支內(nèi)容，故事摘要應(yīng)包含各分支內(nèi)容.事件描述便于用戶(hù)理解事件，因此，我們基于故事的事件集提取幾個(gè)事件描述作為故事摘要.首先，我們用TextRank[12]為各分支提取摘要；然后，我們將各分支的摘要合并為故事摘要.

算法4.故事摘要提取算法.

輸入:故事骨架skeleton；

輸出:故事摘要story_summary.

Extract.Story.Summary (skeleton)；

①story_summary←null；

② for eachbranch∈skeletondo

③branch_description←merge.description(branch)；*將分支內(nèi)所有的事件描述合為分支描述*

④branch_summary←TextRank(branch_description)；

⑤story_summary.add(branch_summary)；

⑥ end for

⑦ returnstory_summary.

故事摘要提取的偽代碼如算法4所示.給定故事s的故事骨架skeleton，故事摘要提取算法為故事s提取并返回故事摘要story_summary.我們生成各分支摘要，并將各分支摘要合并成故事摘要(行②～⑥).首先，我們將分支branch中所有的事件描述合并為分支描述branch_description(行③)，并用TextRank從文章branch_description中提取分支摘要branch_summary(行④)；然后，我們將分支摘要branch_summary合并到故事的摘要story_summary中(行⑤)，并將其返回(行⑦).

3 實(shí)驗(yàn)與結(jié)果

針對(duì)第2節(jié)中提出的方法，我們?cè)诒竟?jié)進(jìn)行實(shí)驗(yàn)驗(yàn)證.首先，我們介紹實(shí)驗(yàn)設(shè)置；然后，我們?cè)u(píng)價(jià)事件檢測(cè)、故事組裝和故事脈絡(luò)生成3個(gè)組件的性能，并展示我們提出的方法較于已有方法的優(yōu)勢(shì).

3.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)運(yùn)行在2個(gè)Intel Xeon E5-2650 v3 CPUs,64 GB內(nèi)存的機(jī)器(64 b Windows7旗艦版系統(tǒng))上.新浪微博數(shù)據(jù)集包含從2016-06-01—2016-08-31的共2.16億條微博.我們將時(shí)間片設(shè)為10 min，即每10 min檢測(cè)一次事件.在該微博集我們共檢測(cè)19.8萬(wàn)個(gè)事件.

3.2 事件檢測(cè)實(shí)驗(yàn)結(jié)果及分析

本節(jié)主要評(píng)價(jià)事件檢測(cè)的性能.首先，我們構(gòu)造測(cè)試集；然后，我們?cè)u(píng)價(jià)2個(gè)事件檢測(cè)算法Ring[9]和MetroMap[1]的性能.

算法MetroMap依據(jù)微博構(gòu)造詞共現(xiàn)圖，基于詞共現(xiàn)圖用社區(qū)檢測(cè)算法檢測(cè)緊密連接的詞社區(qū)，用詞社區(qū)表示事件.

我們提出的框架(事件檢測(cè)、故事組裝和故事脈絡(luò)生成)需要關(guān)聯(lián)事件.框架是否合理依賴(lài)檢測(cè)的事件間是否存在關(guān)聯(lián).事件核心詞集合的重合度可以反映事件間的關(guān)聯(lián)性.我們使用冗余度指數(shù)redundancy-ratio計(jì)算事件集E含有關(guān)聯(lián)事件的事件所占的百分比：

(3)

其中，E表示事件集；δ是0到1間的實(shí)數(shù)，表示閾值；ei表示事件；I(ei,E,δ)是示性函數(shù)，表示事件集E是否存在與事件ei相關(guān)聯(lián)的事件.若事件集E存在事件ej(ei≠ej)，且cos(corewordei,corewordej)>δ，則I(ei,E,δ)=1；否則I(ei,E,δ)=0.

事件檢測(cè)使用的數(shù)據(jù)集包含2016-08-11—2016-08-13共3 d 780萬(wàn)條微博.我們用該數(shù)據(jù)集構(gòu)造3個(gè)測(cè)試集.其中，測(cè)試集A由2016年8月13日的微博構(gòu)成，測(cè)試集B由2016-08-11—2016-08-12的微博構(gòu)成，測(cè)試集C由2016-08-11—2016-08-13的微博構(gòu)成.

Ring和MetroMap的冗余度指數(shù)如圖5所示.在測(cè)試集C上，當(dāng)閾值δ=0.1 時(shí)，Ring的冗余度指數(shù)大于82%，MetroMap的冗余度指數(shù)是100%.Ring和MetroMap檢測(cè)的大部分事件至少有一個(gè)關(guān)聯(lián)事件.這說(shuō)明我們提出的自底向上的框架(事件檢測(cè)、故事組裝和故事脈絡(luò)生成)的合理性.

在圖5(b)中，MetroMap的冗余度指數(shù)隨著閾值的增加輕微地減小，這說(shuō)明MetroMap檢測(cè)的事件存在大量重復(fù)事件.在圖5(a)中，Ring的冗余度指數(shù)對(duì)閾值很敏感，這說(shuō)明較于MetroMap，Ring檢測(cè)到事件的多樣性更好.同時(shí)，事件可能與另一天的事件相關(guān)聯(lián).因此，當(dāng)數(shù)據(jù)集變大時(shí)，冗余度指數(shù)也變大.

Fig.5 redundancy-ratio at different datasets and thresholds圖5 不同數(shù)據(jù)集和閾值上的冗余度指數(shù)

3.3 故事組裝實(shí)驗(yàn)結(jié)果及分析

本節(jié)主要評(píng)價(jià)故事組裝的性能.首先，我們構(gòu)造用于評(píng)價(jià)的故事集，即金標(biāo)準(zhǔn);然后，我們利用金標(biāo)準(zhǔn)評(píng)價(jià)我們的故事組裝算法、LDA[10]、BTM[13]、GSDMM[14]、DBSCAN[11]和Story Forest[15]的性能.

1) LDA.首先，該方法用主題模型LDA生成事件的主題分布；然后，該方法依據(jù)選擇標(biāo)準(zhǔn)將事件賦給主題，一個(gè)主題對(duì)應(yīng)一個(gè)故事.

2) BTM.首先，該方法用主題模型BTM生成事件的主題分布；然后，該方法依據(jù)選擇標(biāo)準(zhǔn)將事件賦給主題，一個(gè)主題對(duì)應(yīng)一個(gè)故事.

3) GSDMM.首先，該方法用主題模型GSDMM生成事件的主題分布；然后，該方法依據(jù)選擇標(biāo)準(zhǔn)將事件賦給主題，一個(gè)主題對(duì)應(yīng)一個(gè)故事.

4) DBSCAN.該方法用DBSCAN聚類(lèi)，一個(gè)簇對(duì)應(yīng)一個(gè)故事.事件間的距離用1減去事件間詞的cosine值表示.

5) Story Forest.該方法依據(jù)事件核心詞與故事核心詞的Jaccard系數(shù)判定事件是否屬于某故事.

構(gòu)造金標(biāo)準(zhǔn).我們請(qǐng)2個(gè)志愿者將事件檢測(cè)算法檢測(cè)的19.8萬(wàn)個(gè)事件分組，一個(gè)組對(duì)應(yīng)一個(gè)故事.首先，一個(gè)志愿者對(duì)2016-06-01—2016-07-15的事件分組，另一個(gè)志愿者對(duì)2016-07-16—2016-08-31的事件分組.然后，一個(gè)志愿者查看另一個(gè)志愿者的分組結(jié)果，被2個(gè)志愿者認(rèn)可的分組結(jié)果才會(huì)被保留.最后，為分析有演化過(guò)程的故事，我們移除包含4個(gè)及以下事件的故事.最終我們構(gòu)造了共包含1 011個(gè)事件的41個(gè)故事.

我們使用已有的評(píng)價(jià)方法[16-17]評(píng)價(jià)故事組裝的性能.我們將人工標(biāo)注的故事稱(chēng)為金標(biāo)準(zhǔn)故事，將故事組裝算法組裝的故事稱(chēng)為組裝故事.對(duì)任意一個(gè)金標(biāo)準(zhǔn)故事g，我們計(jì)算該金標(biāo)準(zhǔn)故事與任意組裝故事a的相似度，并將有最高相似度的組裝故事ag映射到金標(biāo)準(zhǔn)故事g:

(4)

其中，sim(g,a)是金標(biāo)準(zhǔn)故事g和組裝故事a的相似度;Event_setg是金標(biāo)準(zhǔn)故事g的事件集;Event_seta是組裝故事a的事件集;|·|代表集合中元素的個(gè)數(shù);∩代表集合的交集.

然后，我們計(jì)算F1值:

(5)

(6)

(7)

其中，g是金標(biāo)準(zhǔn)故事，Event_setg是金標(biāo)準(zhǔn)故事g的事件集.ag是映射到金標(biāo)準(zhǔn)故事g的組裝故事,Event_setag是組裝故事ag的事件集,G是金標(biāo)準(zhǔn).

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

我們調(diào)節(jié)6種方法:我們的故事組裝算法、LDA、BTM、GSDMM、DBSCAN和Story Forest，調(diào)整參數(shù)的方式為：

1) LDA，BTM和GSDMM.我們?cè)跇?biāo)注故事集上調(diào)節(jié)3個(gè)方法的參數(shù)，alpha，beta和初始故事數(shù)Ns.首先，我們固定beta和Ns，從0.1～1之間，以0.1為步長(zhǎng)調(diào)節(jié)alpha，并取得最優(yōu)值；然后，我們選擇取得最優(yōu)值的alpha并固定Ns，從0.01～0.1之間，以0.01為步長(zhǎng)調(diào)節(jié)beta，并取得最優(yōu)值；最后，我們選擇取得最優(yōu)值的alpha和beta，從50～500之間，以50為步長(zhǎng)調(diào)節(jié)Ns，并選擇取得最優(yōu)值的Ns.當(dāng)2個(gè)參數(shù)設(shè)置取得相似結(jié)果時(shí)，我們參考文獻(xiàn)報(bào)道的BTM和GSDMM中所使用的參數(shù)設(shè)置.

2) 本文方法.我們使用最優(yōu)的LDA配置(alpha=0.1,beta=0.03)，并用網(wǎng)格搜索調(diào)節(jié)初始故事數(shù)Ns、最小點(diǎn)數(shù)minpts和半徑radius參數(shù).其中Ns∈{50,100,150,200,250,300,350,400,450,500},minpts∈{2,3,4},radius∈{0.6,0.65,0.7,0.75,0.8}.

3) DBSCAN.我們用網(wǎng)絡(luò)搜索調(diào)節(jié)最小點(diǎn)數(shù)minpts和半徑radius參數(shù).其中minpts∈{2,3,4},radius∈{0.6,0.65,0.7,0.75,0.8}.

4) Story Forest.我們從0.01～0.1以0.01為步長(zhǎng)調(diào)節(jié)閾值.當(dāng)閾值增加時(shí)，性能下降.因些，我們沒(méi)有測(cè)試閾值大于0.1的性能.

3.3.2 性能評(píng)價(jià)

6種方法在不同初始故事數(shù)的性能(F1)如圖6所示.因?yàn)榭臻g限制，我們只展示在5個(gè)不同的故事數(shù)({50,150,250,350,450})的結(jié)果.使用顯式語(yǔ)義信息組裝故事的Story Forest和DBSCAN有較差的性能，這說(shuō)明顯式信息不能有效地組裝故事.DBSCAN最優(yōu)的結(jié)果準(zhǔn)確率為0.706，召回率為0.459，這證明DBSCAN聚類(lèi)得到的簇粒度較細(xì)，即只能將詞相似度較高的事件聚到相同的簇.當(dāng)初始故事數(shù)在[50,450]時(shí)，我們的方法和LDA的性能優(yōu)于 BTM和GSDMM.我們的方法使用DBSCAN降低LDA初始化時(shí)的隨機(jī)性，有比LDA更好的性能.

Fig.6 Performances at different story number Ns圖6 各算法在不同初始故事數(shù)Ns的性能

我們對(duì)比我們的方法和LDA在不同的參數(shù)(初始故事數(shù)Ns、最小點(diǎn)數(shù)minpts和半徑radius)的性能.當(dāng)minpts在[2,4]、radius在(0.65,0.75)和Ns在[100,500]時(shí)，我們的方法取得了比LDA更大的F1值，實(shí)驗(yàn)結(jié)果見(jiàn)附錄A.

(8)

不同的Gibbs Sampling迭代次數(shù)Ni ter的性能如圖7所示.當(dāng)Ni ter=1 000時(shí)，4個(gè)方法都達(dá)到最優(yōu)性能；當(dāng)Ni ter=200時(shí)，LDA沒(méi)達(dá)到最優(yōu)性能，而我們的方法達(dá)到最優(yōu)性能.我們依據(jù)式(8)計(jì)算LDA和我們的方法在Gibbs Sampling迭代過(guò)程的收斂值，并展示在不同的收斂閾值下LDA和我們的方法需要的運(yùn)行時(shí)間.我們的方法用DBSCAN降低LDA初始化時(shí)的隨機(jī)性，比LDA收斂更快，實(shí)驗(yàn)結(jié)果見(jiàn)附錄B.

Fig.7 Performances at different iteration number Ni ter圖7 各算法在不同迭代次數(shù)Ni ter的性能

Fig.8 Running time of different story assembly methods圖8 不同故事組裝方法的運(yùn)行時(shí)間

在相同的迭代次數(shù)(1 000)，我們?cè)诟淖償?shù)據(jù)集(事件數(shù))和參數(shù)(初始故事數(shù))的情況下對(duì)比運(yùn)行時(shí)間.效果最好的3個(gè)方法，即本文方法、LDA和GSDMM的運(yùn)行時(shí)間如圖8所示.GSDMM所需的

時(shí)間最多.我們的方法用DBSCAN的聚類(lèi)結(jié)果初始化LDA，在相同的迭代次數(shù)下本文方法比LDA的運(yùn)行時(shí)間略高.本文方法比LDA收斂快，在實(shí)際運(yùn)行中可通過(guò)減小迭代次數(shù)縮短運(yùn)行時(shí)間.

綜上所述，本文方法有最優(yōu)的F1值；本文方法較LDA收斂快，即實(shí)際運(yùn)行過(guò)程中本文方法比LDA需要的運(yùn)行時(shí)間少.

3.4 故事脈絡(luò)生成實(shí)驗(yàn)結(jié)果及分析

本節(jié)主要評(píng)價(jià)故事脈絡(luò)生成的性能.我們基于3個(gè)組裝故事(Case 1,Case 2,Case 3)對(duì)比我們的方法、Timeline[18]和 Story Forest[15]的性能.

1) Timeline.該方法基于事件的時(shí)間先后關(guān)系線性的關(guān)聯(lián)事件.

2) Story Forest.該方法首先判斷新事件與已發(fā)生事件是否重復(fù)，若重復(fù)則將2事件合并.該方法然后為非重復(fù)的新事件選擇父節(jié)點(diǎn).該方法計(jì)算新事件與已有事件的連接強(qiáng)度(作者自定義的函數(shù)).如果最大的連接強(qiáng)度小于閾值，則新事件的父親為故事的根結(jié)點(diǎn)，否則新事件的父親為連接強(qiáng)度最大的事件.

Case 1.中國(guó)維和部隊(duì)遇襲.北京時(shí)間2016年6月，聯(lián)合國(guó)在巴里加奧的多層面綜合穩(wěn)定特派團(tuán)營(yíng)地被汽車(chē)炸彈襲擊.中國(guó)維和部隊(duì)中1人犧牲、多人受傷.同年7月，中國(guó)維和部隊(duì)在南蘇丹執(zhí)行任務(wù)時(shí)被炮彈擊中，有2人犧牲、多人受傷.

Case 2.萬(wàn)科股權(quán)之爭(zhēng).中國(guó)A股市場(chǎng)上規(guī)模最大的并購(gòu)與反并購(gòu)攻防戰(zhàn).2015年12月17日，萬(wàn)科股權(quán)之爭(zhēng)正式進(jìn)入正面肉搏階段.

Case 3.2016里約奧運(yùn)會(huì).2016年里約熱內(nèi)盧奧運(yùn)會(huì)于2016-08-05—2016-08-21在巴西里約執(zhí)內(nèi)盧舉行.

我們基于用戶(hù)體驗(yàn)的方式評(píng)價(jià)性能.首先，我們將12個(gè)志愿者隨機(jī)平均分成6組.然后，我們將3個(gè)組裝故事在3個(gè)不同方法下的結(jié)果*https://github.com/liyingrenjie/storyline2(共9個(gè)故事脈絡(luò))隨機(jī)呈現(xiàn)給6組志愿者，并請(qǐng)志愿者在準(zhǔn)確性(該脈絡(luò)是否描述故事的發(fā)展過(guò)程)和理解性(該脈絡(luò)是否有助于用戶(hù)理解故事)2方面對(duì)3個(gè)方法排序，即針對(duì)一個(gè)結(jié)果志愿者對(duì)其進(jìn)行排序，即最好為1，次好為2，最差為3.最后，我們將排序的算數(shù)平均值做為評(píng)價(jià)故事脈絡(luò)生成性能的指標(biāo).準(zhǔn)確性從微觀上評(píng)價(jià)故事脈絡(luò)，即故事脈絡(luò)中事件間的連接是否合理.理解性從宏觀上評(píng)價(jià)故事脈絡(luò)，即故事脈絡(luò)是否從大體上易于用戶(hù)理解故事的主要內(nèi)容.

基于試點(diǎn)用戶(hù)體驗(yàn)的故事脈絡(luò)生成的性能評(píng)價(jià)如表2和表3所示.相同算法在不同案例下的評(píng)分不一樣，這說(shuō)明故事脈絡(luò)的評(píng)價(jià)存在主觀性.我們的方法在3個(gè)案例下的準(zhǔn)確性和理解性都有最靠前的排名.這說(shuō)明，較于Timeline和Story Forest，用戶(hù)傾向我們方法生成的故事脈絡(luò).

Table 2 Accuracy by a Pilot User Experience Study表2 基于試點(diǎn)用戶(hù)體驗(yàn)的故事脈絡(luò)生成的準(zhǔn)確性

Table 3 Comprehension by a Pilot User Experience Study表3 基于試點(diǎn)用戶(hù)體驗(yàn)的故事脈絡(luò)生成的理解性

附錄C列出2位志愿者對(duì)不同方法的評(píng)價(jià).從故事脈絡(luò)和志愿者評(píng)論可看出，我們的方法兼顧了準(zhǔn)確性和理解性.我們的方法既可區(qū)分故事中相對(duì)獨(dú)立的分支以便于用戶(hù)理解故事，又在分支內(nèi)能較好體現(xiàn)事件的關(guān)聯(lián)關(guān)系.

4 相關(guān)工作

故事脈絡(luò)生成問(wèn)題在社交網(wǎng)絡(luò)[18]和傳統(tǒng)媒體[19-21]都有相關(guān)研究.傳統(tǒng)媒體的內(nèi)容嚴(yán)謹(jǐn)而完整，一篇新聞可完整地描述事件.社會(huì)網(wǎng)絡(luò)的文本短小精悍，具有碎片化和語(yǔ)法不標(biāo)準(zhǔn)等特性.一條微博可能只包含事件的碎片化信息.基于文章可描述事件的方法[19,21]直接用于社交網(wǎng)絡(luò)可能得不到理想的效果.

解決故事脈絡(luò)生成問(wèn)題的方法大致分為2類(lèi)：分步法和整合法.分步法將問(wèn)題形式化為多個(gè)組件，即事件檢測(cè)、故事組裝和故事脈絡(luò)生成；整合方法則嘗試構(gòu)造一個(gè)統(tǒng)一模型來(lái)解決該問(wèn)題.

1) 分步法.這里我們分別對(duì)事件檢測(cè)、故事組裝和故事脈絡(luò)的相關(guān)工作進(jìn)行回顧.①事件檢測(cè).Lee等人[22]將社交網(wǎng)絡(luò)流建模為動(dòng)態(tài)微博網(wǎng)絡(luò)，并將網(wǎng)絡(luò)中緊密連接的微博集合做為事件.Story Forest[15]對(duì)新聞文本流聚類(lèi)，并將簇做為事件.②故事組裝.Story Forest[15]依據(jù)事件與已有故事的語(yǔ)義距離將事件分配到特定故事.③故事脈絡(luò)生成.Lee等人[22]用事件間的Jaccard系數(shù)追蹤事件間的演化關(guān)系.Story Forest[15]在故事內(nèi)依據(jù)自定義的函數(shù)生成故事脈絡(luò).Lee等人[22]用關(guān)鍵詞集合表示事件，不利于用戶(hù)理解事件.Lee等人[22]依據(jù)事件的微博相似度是否大于閾值判定事件的演化關(guān)系;這種方法存在2個(gè)問(wèn)題：①只能連接相似度較高的事件；②會(huì)引入一些不必要的連接.

2) 整合法.CHARCOAL[23]用提出的概率圖模型對(duì)新聞文章間的聯(lián)系(link)建模，對(duì)故事的進(jìn)展(progress)，并通過(guò)新聞文章間的聯(lián)系生成故事脈絡(luò).單個(gè)微博可能不包含事件的所有關(guān)鍵信息(例如地點(diǎn)和參與者)，因此CHARCOAL不能直接用于社交網(wǎng)絡(luò).DSEM[24]和DSDM[25]用非參數(shù)化的生成模型同時(shí)提取事件的結(jié)構(gòu)化表示和事件在連續(xù)時(shí)間片的演化模式.MEP[26]用基于非負(fù)矩陣分解的主題模型同時(shí)檢測(cè)事件和連續(xù)時(shí)間片的事件的演化.然而，這些模型只能追蹤連續(xù)變化的模式，難以對(duì)時(shí)間跨度大、不連續(xù)的故事內(nèi)事件間的演化進(jìn)行追蹤.

5 總結(jié)與展望

在社交網(wǎng)絡(luò)通過(guò)故事脈絡(luò)對(duì)事件及事件間的演化建模具有重要意義且極具挑戰(zhàn).我們將故事脈絡(luò)生成問(wèn)題形式化為事件檢測(cè)、故事組裝和故事脈絡(luò)生成3個(gè)連續(xù)的組件，并提出了解決框架.我們提出用包含摘要的有向無(wú)環(huán)圖可視化故事的發(fā)展過(guò)程.新浪微博數(shù)據(jù)集上進(jìn)行的實(shí)驗(yàn)表明我們的方法能有效展示故事的發(fā)展過(guò)程.社交網(wǎng)絡(luò)存在大量的用戶(hù)關(guān)系、用戶(hù)行為和用戶(hù)畫(huà)像等信息，且用戶(hù)是社交網(wǎng)絡(luò)的主要參與者，這些信息對(duì)于故事脈絡(luò)生成有重要參考價(jià)值.社交網(wǎng)絡(luò)每天產(chǎn)生大量的數(shù)據(jù)，online的故事脈絡(luò)生成方法便于大規(guī)模部署.如何將方法修改為online的模式并融合用戶(hù)信息是下一步的研究工作.