一種基于社交事件關聯的故事脈絡生成方法

2018-09-21 03:25:54李瑩瑩蔣浩誼胡春明

計算機研究與發展 2018年9期

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

1(軟件開發環境國家重點實驗室(北京航空航天大學) 北京 100191) 2(北京大數據科學與腦機智能高精尖創新中心(北京航空航天大學) 北京 100191) 3(國家計算機網絡應急技術處理協調中心北京 100029) (liyy@act.buaa.edu.cn)

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

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

然而，故事脈絡生成仍然存在2個問題：1)事件由微博集合表示且有特定主題，如何從微博集合提取與事件對應的強相關的微博集合是一個關鍵問題.目前，針對該問題研究者們已經提出多種解決方式，然而如何選擇最優的方法是一個具有挑戰的問題.2)對有關聯關系的事件如何進行有效組裝，并以故事脈絡的形式展示是另一個關鍵問題.

為此，我們將該問題形式化為3個連續的步驟，即事件檢測、故事組裝以及故事脈絡生成.本文的主要貢獻有3個方面：

1) 從微博檢測事件.依據事件的隱式語義信息關聯事件并組裝故事，為故事生成故事脈絡以可視化故事的發展過程;

2) 提出用包含摘要的有向無環圖描述故事脈絡.該故事脈絡既可以使用戶了解故事，也可使用戶了解故事的發展過程;

3) 利用新浪微博數據集評價我們提出的故事脈絡生成方法.基于用戶體驗的實驗表明我們方法的性能優于現有方法.

1 研究問題和系統框架

在本節中，我們首先介紹術語的定義；然后，我們陳述所研究的問題；最后，我們描述系統框架.

1.1 術語定義

定義1.微博.一個微博m由二元組M,Tm表示，其中，1)M是微博的內容;2)Tm是微博的產生時間.

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

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

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

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

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

1.2 問題陳述

對于微博集({M1,M2,…,Mt})，其中Mt是時間片t的微博集合.我們的目標是:1)從微博集中檢測事件({E1,E2,…,Et})，其中Et是時間片t檢測的事件集合;2)依據事件的隱式語義信息有效的關聯事件并組裝故事(S={s1,s2,…,sNs})，其中si表示一個故事;3)為每個故事生成一個用于可視化故事發展過程的故事脈絡.

1.3 系統框架描述

我們用包含3個組件的框架(如圖2所示)解決故事脈絡生成問題.首先，我們從微博集中檢測事件；然后，我們通過關聯事件組裝故事；最后，我們為每個故事生成描述故事發展過程的故事脈絡.

Fig.2 System framework圖2 系統框架

1.3.1 事件檢測

我們從微博集中檢測事件.首先，從微博集得到由表示事件的核心詞和核心詞間共現關系構成的核心詞圖；然后，發現核心詞圖中緊密連接的子圖并將子圖做為事件的核心詞集合；最后，為事件識別其他的特征Te，Le，Pe，De和Microblog_set.

1.3.2 故事組裝

我們依據主題對事件分組，將事件組裝成故事.首先，我們依據事件的隱式語義信息對事件聚類，將一個簇認為一個故事；然后，我們為每個故事識別其他的特征Ts，Ls，Ps和Cs.

1.3.3 故事脈絡生成

我們為每個故事生成故事脈絡，該故事脈絡由包含摘要的事件有向無環圖表示.首先，我們從故事的事件集基于弱連通分量和最大生成樹構造有向無環圖(skeleton)；然后，我們基于故事的所有事件描述提取短文本作為故事的摘要.

2 系統組件

針對在第1節中形式化的3個步驟，即事件檢測、故事組裝和故事脈絡生成，我們在本節具體介紹所對應的實現方法.

2.1 事件檢測

在事件檢測步驟，我們旨在從微博數據中檢測事件.為幫助用戶理解故事的發展過程，我們認為故事中的事件應該可以使用戶剖析故事的細節，即事件應屬于特定主題且具有細粒度性.

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

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

2.1.1 核心詞發現

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

2.1.2 核心詞社區提取

在核心詞社區提取階段，我們提取表示事件的核心詞集合.事件的核心詞通常緊密連接.依據上一步輸出的核心詞圖，我們用社區檢測算法[8]檢測緊密連接的核心詞社區，即由詞(點)和詞間共現關系(邊)構成的稠密子圖.核心詞社區對應事件的核心詞集合，其能夠有效地描述一個事件.我們依據圖3(a)展示的核心詞圖檢測出圖3(b)的核心詞社區，該核心詞社區表示“江蘇省政府追授沭陽因公犧牲輔警孫孟濤見義勇為英雄稱號”事件.

Fig.3 A core word community in the core word graph圖3 核心詞圖的一個核心詞社區

2.1.3 事件特征識別

在事件特征識別階段，我們將事件的數據進行結構化以增加事件的描述信息.僅用核心詞集合表示事件存在不足，如碎片化和易讀性差.我們將用核心詞集合表示的事件擴充為事件六元組，過程如下：

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

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

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

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

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

6) 我們將參與者集合Pe賦值為事件的微博集合中出現的人名和機構名.

2.2 故事組裝

在故事組裝步驟，我們旨在通過關聯事件組裝故事.為幫助用戶從全景了解故事，故事應囊括該主題下所有事件，即故事組裝需有效組裝有關聯的事件.

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

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

我們用2個連續的模塊完成故事組裝任務.首先，我們依據事件的隱式語義信息關聯事件，將事件分到不同的故事;然后，我們依據事件的特征，識別故事的特征，生成故事的結構化表示，以便用戶查詢.

2.2.1 故事構造

我們用預聚類和細聚類的方式組裝故事.首先，我們用聚類算法DBSCAN[11]實現預聚類，即依據顯式語義信息對事件分組；然后，我們用預聚類的結果初始化LDA中故事的詞分布，并依據LDA生成的隱式語義信息構造故事.

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

首先，我們為事件集合E中每個事件e構造詞向量we.若第k個詞在事件e中，we,k=1；否則we,k=0.然后，我們依據詞向量用DBSCAN將事件聚到類成員P中,其中P={P1,P2,…,PI}，Pi是包含一個事件集合的預簇.DBSCAN使用的距離函數:

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

(1)

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

最終，我們將事件集合E和基于DBSCAN的聚類結果作為細聚類的輸入.

2) 細聚類.細聚類基于預聚類的結果挖掘事件的隱式語義信息，依據事件的隱式語義信息關聯事件，并將事件賦值到故事.LDA生成的隱式語義信息有利于相關性判斷.用預聚類的結果初始化LDA中故事的詞分布可減少LDA的搜索空間.

首先，我們依據預聚類結果初始化LDA中故事的詞分布，給定預聚類結果P，我們將相同的預簇中事件的詞賦給相同的故事；然后，我們用Gibbs Sampling推斷LDA的參數、事件的故事向量；最后，我們依據選擇標準將事件賦給故事.

選擇標準.我們假設每個事件屬于且僅屬于一個故事.我們將事件賦給概率最高的故事.

算法1.故事構造算法.

輸入:事件集合E={e1,e2,…,en}、初始故事數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

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

⑩ end for

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

2.2.2 故事特征識別

在故事特征識別階段，我們將故事的數據進行結構化以便于用戶查詢故事.事件檢測組件為事件生成結構化表示，用事件的結構化表示生成故事的結構化表示既能充分利用相關微博的信息，也可以提高效率.我們基于事件六元組將用事件集合表示的故事擴充為故事五元組，過程如下：1)故事的時間段Ts的開始時間和結束時間分別被賦值為故事的事件集中事件的最早時間和最晚時間;2)故事內包含事件的特征越多，越能幫助用戶查詢故事，故事的地點集合Ls、參與者集合Ps和核心詞集合Cs分別被設為故事的事件集中相應特征的并集.

算法2.故事特征識別算法.

輸入:故事集合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.

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

2.3 故事脈絡生成

在故事脈絡生成步驟，我們旨在為故事生成包含摘要的有向無環圖以可視化故事的發展過程.為有更好的用戶體驗，故事脈絡應兼顧準確性和理解性.準確性指故事脈絡準確地展示事件的發展過程.理解性指故事脈絡便于用戶快速的了解故事.

故事可能包含多個相對獨立的部分.例“2016巴西奧運”故事包含“巴西里約奧運俄羅斯部分運動員被禁賽”和“巴西里約奧運美國女子4×100接力掉棒”等多個相對獨立的部分.我們用弱連通分量提取故事中多個相對獨立的部分.為方便描述，下面稱相對獨立的部分為分支.

分支內的事件有較強的關聯關系.復雜的圖結構表示的分支不便于用戶快速的理解[15].如圖4(a)中圖結構表示的分支，雖然其充分地表達了事件間的關聯關系，但其也引入一些不必要連接，如事件e3到事件e7.為折中準確性和理解性，我們用最大生成樹生成分支的樹結構，如圖4(b)所示.

Fig.4 A branch represented by a graph or tree structure圖4 由圖或樹結構表示的分支

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

2.3.1 故事骨架構造

在故事骨架構造階段，我們依據故事的事件集構造用于描述故事發展過程的有向無環圖.首先，我們計算任意2事件間的權重，依此生成有向邊，構造一個事件圖；然后，我們依據事件圖識別故事中的分支，即識別該圖中所有的弱連通分量，并形成弱連通分量集合；最后，我們為弱連通分量集合中每個弱連通分量構造一個最大生成樹,即用樹結構表示的分支.這些用樹結構表示的分支構成故事的骨架:

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

(2)

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

演化關系包含著事件的時間關系.有向邊只能從先發生的事件指向后發生的事件.若Tei

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

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

事件的微博集合由包含事件所有核心詞的微博構成.事件的地點和參與者由微博集合中的命名實體構成.因此事件的核心詞、地點和參與者包含了微博集合的主要信息.

我們在3個組裝的故事上調節權重系數cp和cc.首先，我們使用多組權重系數構造故事骨架.然后，我們依據骨架是否反應故事的發展過程對多個故事骨架排序，并依據排序結果設定cp=0.3和cc=0.7.

算法3.故事骨架構造算法.

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

輸出:故事的骨架skeleton.

Construct.Story.Skeleton(Event_set)；

① 基于Event_set創建一個按時間升序排列的事件列表event.list；

②skeleton←null；

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

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

⑤event.parent←null；*父事件結點*

⑥edge.weight←0；*與父事件結點邊的權重*

⑦ forj=0 toi-1 do

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

⑨ ifj2i.weight>edge.weightthen

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

branch);

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

2.3.2 故事摘要提取

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

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

輸入:故事骨架skeleton；

輸出:故事摘要story_summary.

Extract.Story.Summary (skeleton)；

①story_summary←null；

② for eachbranch∈skeletondo

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

④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 實驗與結果

針對第2節中提出的方法，我們在本節進行實驗驗證.首先，我們介紹實驗設置；然后，我們評價事件檢測、故事組裝和故事脈絡生成3個組件的性能，并展示我們提出的方法較于已有方法的優勢.

3.1 實驗設置

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

3.2 事件檢測實驗結果及分析

本節主要評價事件檢測的性能.首先，我們構造測試集；然后，我們評價2個事件檢測算法Ring[9]和MetroMap[1]的性能.

算法MetroMap依據微博構造詞共現圖，基于詞共現圖用社區檢測算法檢測緊密連接的詞社區，用詞社區表示事件.

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

(3)

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

事件檢測使用的數據集包含2016-08-11—2016-08-13共3 d 780萬條微博.我們用該數據集構造3個測試集.其中，測試集A由2016年8月13日的微博構成，測試集B由2016-08-11—2016-08-12的微博構成，測試集C由2016-08-11—2016-08-13的微博構成.

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

在圖5(b)中，MetroMap的冗余度指數隨著閾值的增加輕微地減小，這說明MetroMap檢測的事件存在大量重復事件.在圖5(a)中，Ring的冗余度指數對閾值很敏感，這說明較于MetroMap，Ring檢測到事件的多樣性更好.同時，事件可能與另一天的事件相關聯.因此，當數據集變大時，冗余度指數也變大.

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

3.3 故事組裝實驗結果及分析

本節主要評價故事組裝的性能.首先，我們構造用于評價的故事集，即金標準;然后，我們利用金標準評價我們的故事組裝算法、LDA[10]、BTM[13]、GSDMM[14]、DBSCAN[11]和Story Forest[15]的性能.

1) LDA.首先，該方法用主題模型LDA生成事件的主題分布；然后，該方法依據選擇標準將事件賦給主題，一個主題對應一個故事.

2) BTM.首先，該方法用主題模型BTM生成事件的主題分布；然后，該方法依據選擇標準將事件賦給主題，一個主題對應一個故事.

3) GSDMM.首先，該方法用主題模型GSDMM生成事件的主題分布；然后，該方法依據選擇標準將事件賦給主題，一個主題對應一個故事.

4) DBSCAN.該方法用DBSCAN聚類，一個簇對應一個故事.事件間的距離用1減去事件間詞的cosine值表示.

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

構造金標準.我們請2個志愿者將事件檢測算法檢測的19.8萬個事件分組，一個組對應一個故事.首先，一個志愿者對2016-06-01—2016-07-15的事件分組，另一個志愿者對2016-07-16—2016-08-31的事件分組.然后，一個志愿者查看另一個志愿者的分組結果，被2個志愿者認可的分組結果才會被保留.最后，為分析有演化過程的故事，我們移除包含4個及以下事件的故事.最終我們構造了共包含1 011個事件的41個故事.

我們使用已有的評價方法[16-17]評價故事組裝的性能.我們將人工標注的故事稱為金標準故事，將故事組裝算法組裝的故事稱為組裝故事.對任意一個金標準故事g，我們計算該金標準故事與任意組裝故事a的相似度，并將有最高相似度的組裝故事ag映射到金標準故事g:

(4)

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

然后，我們計算F1值:

(5)

(6)

(7)

其中，g是金標準故事，Event_setg是金標準故事g的事件集.ag是映射到金標準故事g的組裝故事,Event_setag是組裝故事ag的事件集,G是金標準.

3.3.1 參數調節

我們調節6種方法:我們的故事組裝算法、LDA、BTM、GSDMM、DBSCAN和Story Forest，調整參數的方式為：

1) LDA，BTM和GSDMM.我們在標注故事集上調節3個方法的參數，alpha，beta和初始故事數Ns.首先，我們固定beta和Ns，從0.1～1之間，以0.1為步長調節alpha，并取得最優值；然后，我們選擇取得最優值的alpha并固定Ns，從0.01～0.1之間，以0.01為步長調節beta，并取得最優值；最后，我們選擇取得最優值的alpha和beta，從50～500之間，以50為步長調節Ns，并選擇取得最優值的Ns.當2個參數設置取得相似結果時，我們參考文獻報道的BTM和GSDMM中所使用的參數設置.

2) 本文方法.我們使用最優的LDA配置(alpha=0.1,beta=0.03)，并用網格搜索調節初始故事數Ns、最小點數minpts和半徑radius參數.其中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.我們用網絡搜索調節最小點數minpts和半徑radius參數.其中minpts∈{2,3,4},radius∈{0.6,0.65,0.7,0.75,0.8}.

4) Story Forest.我們從0.01～0.1以0.01為步長調節閾值.當閾值增加時，性能下降.因些，我們沒有測試閾值大于0.1的性能.

3.3.2 性能評價

6種方法在不同初始故事數的性能(F1)如圖6所示.因為空間限制，我們只展示在5個不同的故事數({50,150,250,350,450})的結果.使用顯式語義信息組裝故事的Story Forest和DBSCAN有較差的性能，這說明顯式信息不能有效地組裝故事.DBSCAN最優的結果準確率為0.706，召回率為0.459，這證明DBSCAN聚類得到的簇粒度較細，即只能將詞相似度較高的事件聚到相同的簇.當初始故事數在[50,450]時，我們的方法和LDA的性能優于 BTM和GSDMM.我們的方法使用DBSCAN降低LDA初始化時的隨機性，有比LDA更好的性能.

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

我們對比我們的方法和LDA在不同的參數(初始故事數Ns、最小點數minpts和半徑radius)的性能.當minpts在[2,4]、radius在(0.65,0.75)和Ns在[100,500]時，我們的方法取得了比LDA更大的F1值，實驗結果見附錄A.

(8)

不同的Gibbs Sampling迭代次數Ni ter的性能如圖7所示.當Ni ter=1 000時，4個方法都達到最優性能；當Ni ter=200時，LDA沒達到最優性能，而我們的方法達到最優性能.我們依據式(8)計算LDA和我們的方法在Gibbs Sampling迭代過程的收斂值，并展示在不同的收斂閾值下LDA和我們的方法需要的運行時間.我們的方法用DBSCAN降低LDA初始化時的隨機性，比LDA收斂更快，實驗結果見附錄B.

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

Fig.8 Running time of different story assembly methods圖8 不同故事組裝方法的運行時間

在相同的迭代次數(1 000)，我們在改變數據集(事件數)和參數(初始故事數)的情況下對比運行時間.效果最好的3個方法，即本文方法、LDA和GSDMM的運行時間如圖8所示.GSDMM所需的

時間最多.我們的方法用DBSCAN的聚類結果初始化LDA，在相同的迭代次數下本文方法比LDA的運行時間略高.本文方法比LDA收斂快，在實際運行中可通過減小迭代次數縮短運行時間.

綜上所述，本文方法有最優的F1值；本文方法較LDA收斂快，即實際運行過程中本文方法比LDA需要的運行時間少.

3.4 故事脈絡生成實驗結果及分析

本節主要評價故事脈絡生成的性能.我們基于3個組裝故事(Case 1,Case 2,Case 3)對比我們的方法、Timeline[18]和 Story Forest[15]的性能.

1) Timeline.該方法基于事件的時間先后關系線性的關聯事件.

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

Case 1.中國維和部隊遇襲.北京時間2016年6月，聯合國在巴里加奧的多層面綜合穩定特派團營地被汽車炸彈襲擊.中國維和部隊中1人犧牲、多人受傷.同年7月，中國維和部隊在南蘇丹執行任務時被炮彈擊中，有2人犧牲、多人受傷.

Case 2.萬科股權之爭.中國A股市場上規模最大的并購與反并購攻防戰.2015年12月17日，萬科股權之爭正式進入正面肉搏階段.

Case 3.2016里約奧運會.2016年里約熱內盧奧運會于2016-08-05—2016-08-21在巴西里約執內盧舉行.

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

基于試點用戶體驗的故事脈絡生成的性能評價如表2和表3所示.相同算法在不同案例下的評分不一樣，這說明故事脈絡的評價存在主觀性.我們的方法在3個案例下的準確性和理解性都有最靠前的排名.這說明，較于Timeline和Story Forest，用戶傾向我們方法生成的故事脈絡.

Table 2 Accuracy by a Pilot User Experience Study表2 基于試點用戶體驗的故事脈絡生成的準確性

Table 3 Comprehension by a Pilot User Experience Study表3 基于試點用戶體驗的故事脈絡生成的理解性

附錄C列出2位志愿者對不同方法的評價.從故事脈絡和志愿者評論可看出，我們的方法兼顧了準確性和理解性.我們的方法既可區分故事中相對獨立的分支以便于用戶理解故事，又在分支內能較好體現事件的關聯關系.

4 相關工作

故事脈絡生成問題在社交網絡[18]和傳統媒體[19-21]都有相關研究.傳統媒體的內容嚴謹而完整，一篇新聞可完整地描述事件.社會網絡的文本短小精悍，具有碎片化和語法不標準等特性.一條微博可能只包含事件的碎片化信息.基于文章可描述事件的方法[19,21]直接用于社交網絡可能得不到理想的效果.

解決故事脈絡生成問題的方法大致分為2類：分步法和整合法.分步法將問題形式化為多個組件，即事件檢測、故事組裝和故事脈絡生成；整合方法則嘗試構造一個統一模型來解決該問題.

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

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

5 總結與展望

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