秦宇君,史存會(huì),劉悅,俞曉明,程學(xué)旗

(1.中國(guó)科學(xué)院大學(xué),北京 100049;2.中國(guó)科學(xué)院計(jì)算技術(shù)研究所,北京 100190)

0 引言

隨著互聯(lián)網(wǎng)的不斷發(fā)展,人們?cè)絹?lái)越多地通過(guò)網(wǎng)絡(luò)進(jìn)行信息的發(fā)布和接收,這也導(dǎo)致網(wǎng)絡(luò)輿論對(duì)社會(huì)穩(wěn)定的影響程度與日俱增,如Twitter在北非和西亞的“阿拉伯之春”的社會(huì)運(yùn)動(dòng)中,起到了重要作用;國(guó)內(nèi)社會(huì)生活中的食品安全、自然災(zāi)害、懲治腐敗、房市調(diào)控、法治熱點(diǎn)、春運(yùn)、高考等各種事件在網(wǎng)絡(luò)用戶(hù)間被熱烈的討論和傳播,并最終對(duì)人們的現(xiàn)實(shí)社會(huì)生活產(chǎn)生了實(shí)質(zhì)性的影響?；趪?guó)際社會(huì)對(duì)網(wǎng)絡(luò)輿情的需求,輿情系統(tǒng)應(yīng)運(yùn)而生,這類(lèi)系統(tǒng)的主要功能包括突發(fā)事件發(fā)現(xiàn),熱點(diǎn)話題分析,有害信息識(shí)別等。

在實(shí)際的輿情系統(tǒng)中,社會(huì)事件往往是系統(tǒng)關(guān)注的重點(diǎn)?；ヂ?lián)網(wǎng)當(dāng)前已經(jīng)成為報(bào)道和傳播各種社會(huì)事件的重要信息平臺(tái)。在互聯(lián)網(wǎng)中存在眾多的信息發(fā)布通道,如微博、微信、新聞等。不同的信息發(fā)布通道有各自的特點(diǎn),例如對(duì)于微博、微信等網(wǎng)絡(luò)自媒體通道所發(fā)布的信息具有及時(shí)性、多樣性等特點(diǎn),許多社會(huì)事件的第一報(bào)道地點(diǎn)往往都來(lái)自于這些網(wǎng)絡(luò)自媒體,而對(duì)于同一事件的報(bào)道者越多,觀點(diǎn)越豐富,則能從側(cè)面反映出該事件的輿論熱度和潛在的輿論影響力。相對(duì)于微博發(fā)布信息的短、平、快的特點(diǎn),許多來(lái)自新聞網(wǎng)站等通道的事件發(fā)布則更側(cè)重事件的完整性、事實(shí)性,這些新聞媒體通道對(duì)于事件的描述更加詳細(xì),內(nèi)容更加真實(shí)可靠。

對(duì)于網(wǎng)絡(luò)輿情系統(tǒng)而言,系統(tǒng)所發(fā)現(xiàn)的事件如果能既具備很高的輿論熱度和潛在影響力,也能有詳盡的事件信息與很好的可靠程度,則能為后續(xù)相關(guān)事件的及時(shí)處理提供更好的幫助。鑒于微博等網(wǎng)絡(luò)自媒體通道具有反映事件熱度和影響力的能力,而新聞網(wǎng)站等通道具有規(guī)范化、可信度高等特點(diǎn),如果能將這些不同通道的信息進(jìn)行關(guān)聯(lián)與綜合利用,從而發(fā)現(xiàn)事件,則將會(huì)對(duì)網(wǎng)絡(luò)輿情系統(tǒng)的效果有很大的提高。

目前事件發(fā)現(xiàn)領(lǐng)域[1]的研究大多是針對(duì)同種類(lèi)型文檔進(jìn)行研究,研究方法主要分為以文檔為事件中心和以詞為事件中心。以文檔為中心的事件發(fā)現(xiàn)方法主要采用分類(lèi)和聚類(lèi)的方式,將文檔歸為不同的文檔集合,形成事件;以詞為中心的事件發(fā)現(xiàn)方法則利用信號(hào)處理或主題模型等方式獲取事件代表詞,將包含代表詞的文檔歸為同一集合,形成事件。無(wú)論是以文檔為中心還是以詞為中心的方式,其核心都是將文檔轉(zhuǎn)換成另一種表達(dá)形式,然后再利用新的表達(dá)方式將文檔歸納到不同的集合中從而形成事件。對(duì)于單一通道,數(shù)據(jù)的結(jié)構(gòu)和內(nèi)容形式往往相同,因此在用相同的方法進(jìn)行映射之后,在原空間相似的文檔在新空間仍然相似,事件發(fā)現(xiàn)的效果相對(duì)較好。然而在多源文本中,新聞報(bào)道和微博消息在內(nèi)容形式上具有較大區(qū)別,新聞報(bào)道往往用詞規(guī)范,內(nèi)容相對(duì)充實(shí),微博消息則口語(yǔ)化較嚴(yán)重,內(nèi)容相對(duì)短小精煉,如果采用相同的映射方法,很難保證在原空間相似的文檔在新空間仍然相似。

本文則針對(duì)傳統(tǒng)事件發(fā)現(xiàn)方法在處理多源文本時(shí)遇到的困難,提出了結(jié)合實(shí)體的事件發(fā)現(xiàn)方法ESP。首先提出了事件核心實(shí)體的概念,給出了事件核心實(shí)體的獲取方法,并通過(guò)在經(jīng)典的Single Pass方法中引入事件核心實(shí)體信息,豐富了多源文本中的各類(lèi)文本的表達(dá),使得多源文本中來(lái)自不同通道的文檔能夠在新的映射空間中具有更多的信息,從而提高了多源文本事件發(fā)現(xiàn)的效果。

傳統(tǒng)的事件發(fā)現(xiàn)方法大概分為兩類(lèi):以文檔為事件核心和以文檔的代表詞為事件核心。前者是通過(guò)將文檔映射到語(yǔ)義特征空間,通過(guò)分類(lèi)或聚類(lèi)的方法來(lái)發(fā)現(xiàn)事件[2-4]；后者則是先利用詞頻突變,關(guān)鍵詞篩選等方法獲得代表文檔特點(diǎn)的詞語(yǔ),再對(duì)詞進(jìn)行聚類(lèi)或關(guān)聯(lián),從而發(fā)現(xiàn)事件[5]。

從文檔角度出發(fā)的事件發(fā)現(xiàn),傳統(tǒng)的方法有層次聚類(lèi)(Hierarchical Clustering)、K-means聚類(lèi)、Single-Pass[6]聚類(lèi)和局部敏感哈希[7](Locality-Sensitive Hashing,LSH)等,這些方法首先都是將文檔映射到語(yǔ)義特征空間,然后進(jìn)行相似度計(jì)算。

層次聚類(lèi)需要人為指定最終期望的結(jié)果個(gè)數(shù),但是在實(shí)際的事件發(fā)現(xiàn)系統(tǒng)中,事件的個(gè)數(shù)往往不能預(yù)先確定,并且在計(jì)算簇內(nèi)相似度時(shí)要對(duì)簇內(nèi)的所有文檔兩兩計(jì)算相似度,時(shí)間復(fù)雜度和空間復(fù)雜度都較高,不太適宜大量數(shù)據(jù)的場(chǎng)景。與層次聚類(lèi)相似的方法還有K-means聚類(lèi),但它需要提前確定k個(gè)聚類(lèi)中心,實(shí)際應(yīng)用中k的確定十分困難,同時(shí)初始點(diǎn)的選擇也極大地影響事件發(fā)現(xiàn)的結(jié)果。

Single-Pass聚類(lèi)方法則是將每一篇新到來(lái)的文章與之前的事件相比較,如果通過(guò)兩兩比較,當(dāng)前的文章與之前的任何一篇均不相似,則視為新的事件,否則加入現(xiàn)有事件列表中。此方法的優(yōu)點(diǎn)是可以處理流式數(shù)據(jù),增量式發(fā)現(xiàn)事件。但是相似閾值的設(shè)定以及文檔到達(dá)的順序會(huì)直接影響事件發(fā)現(xiàn)的效果。

局部敏感哈希方法則是利用多組哈希函數(shù),將文檔從高維空間向低維空間進(jìn)行投影,再利用投影后的低維向量進(jìn)行數(shù)據(jù)分桶索引,對(duì)于屬于同一個(gè)桶中的數(shù)據(jù)進(jìn)行相似度計(jì)算,從而縮小比較的次數(shù),這種方式對(duì)于大量的數(shù)據(jù)能夠很大程度上降低計(jì)算時(shí)間復(fù)雜度。但是在實(shí)際應(yīng)用中,相似文檔并不能很大程度的映射到相同的數(shù)據(jù)分桶中。

除了以上這些將文檔進(jìn)行特征映射后進(jìn)行聚類(lèi)的方法,分類(lèi)方法也被應(yīng)用在事件發(fā)現(xiàn)領(lǐng)域。當(dāng)系統(tǒng)的主要任務(wù)是發(fā)現(xiàn)特定類(lèi)別的事件時(shí),通過(guò)合理的特征設(shè)置,可以利用分類(lèi)方法定向的發(fā)現(xiàn)事件[8]。但是這種方法只能用于某些指定類(lèi)別的事件,很難擴(kuò)展應(yīng)用到大范圍事件發(fā)現(xiàn)系統(tǒng)中。

從詞的角度出發(fā)的事件發(fā)現(xiàn),主要是從詞在時(shí)域和頻域的變化進(jìn)行事件代表詞的篩選,將最終得到的一些詞的集合作為事件的代表。

Kleinberg[9]提出消息的到達(dá)是有時(shí)序關(guān)系的,他提出二元狀態(tài)自動(dòng)機(jī)和無(wú)限狀態(tài)自動(dòng)機(jī)兩種建模方法,通過(guò)模型可以得到某個(gè)詞的狀態(tài)變化序列,從而獲得爆發(fā)詞和相關(guān)文檔。

Fung[10]等人則針對(duì)現(xiàn)有聚類(lèi)方式的問(wèn)題,提出了通過(guò)構(gòu)造詞的分布,判斷某一詞是否屬于爆發(fā)詞。獲取到爆發(fā)詞后,根據(jù)文檔包含爆發(fā)詞的情況,形成爆發(fā)事件。最終還可以通過(guò)跟蹤爆發(fā)詞的變化,獲得事件爆發(fā)的周期。

Ge等[11]則提出了一種利用詞頻的突變以及詞與詞之間的共現(xiàn)關(guān)系,構(gòu)造消息爆發(fā)網(wǎng)絡(luò),網(wǎng)絡(luò)中的節(jié)點(diǎn)是符合突變性質(zhì)的詞,網(wǎng)絡(luò)中的邊則是代表詞的共現(xiàn)關(guān)系,并且邊上的權(quán)重隨著共現(xiàn)次數(shù)的增多而增大。網(wǎng)絡(luò)構(gòu)造完成后再利用TextRank的方式發(fā)現(xiàn)網(wǎng)絡(luò)中的關(guān)鍵詞,作為最終事件的代表性詞匯。

綜上可知,無(wú)論是以文檔為核心還是以詞為核心的事件發(fā)現(xiàn)方法,都是獲取文檔在特征空間的一種表達(dá),然后再利用特征空間的相似性將相似文檔聚到一起形成事件。這種方法雖然可以在很大程度上將相似文檔聚到一起,但是在針對(duì)“事件”這一特殊領(lǐng)域,還有可以提升的空間。

1 結(jié)合實(shí)體的多源文本事件發(fā)現(xiàn)算法ESP

Fig.1 Flow chart of ESP圖1 事件發(fā)現(xiàn)算法流程示意圖

ESP算法是基于Single-Pass流式聚類(lèi)算法進(jìn)行的改進(jìn)。前人[12]的研究認(rèn)為事件是指在某個(gè)特定的時(shí)間和環(huán)境下發(fā)生的,由若干角色參與,表現(xiàn)出若干動(dòng)作特征的一件事情。形式上可以表示為由時(shí)間、地點(diǎn)、人物、機(jī)構(gòu)等實(shí)體構(gòu)成的多元組形式。由于實(shí)體對(duì)事件有很強(qiáng)的表達(dá)能力,如果能準(zhǔn)確地識(shí)別文檔中的核心實(shí)體,并將其作為文檔在事件域的表達(dá),則能更好地進(jìn)行事件發(fā)現(xiàn)。因此,ESP算法首先要對(duì)每篇文檔進(jìn)行核心實(shí)體識(shí)別。在獲得每篇文檔的核心實(shí)體集合后,進(jìn)行文檔間核心實(shí)體集合間相似度計(jì)算。最終將文檔間核心實(shí)體相似度引入現(xiàn)有的事件發(fā)現(xiàn)算法Single-Pass中,進(jìn)行事件發(fā)現(xiàn)。算法流程見(jiàn)圖1。

1.1 事件核心實(shí)體識(shí)別方法

由于目前對(duì)于事件核心實(shí)體尚未有統(tǒng)一的定義,因此本文首先對(duì)事件核心實(shí)體進(jìn)行定義。

定義:事件核心實(shí)體是指對(duì)于描述、刻畫(huà)一個(gè)事件起到重要作用的人名、地名、機(jī)構(gòu)名等實(shí)體。

根據(jù)以上定義,本文提出的事件核心實(shí)體識(shí)別方法,流程分為以下兩步:(1)對(duì)事件文本進(jìn)行命名實(shí)體識(shí)別,獲得事件的候選實(shí)體集合,候選實(shí)體集合中的每個(gè)實(shí)體都包含了實(shí)體的類(lèi)型信息和位置信息。(2)利用本文提出的EntityRank算法對(duì)實(shí)體集合中的實(shí)體進(jìn)行重要度排序,將重要度最高的實(shí)體作為核心實(shí)體。針對(duì)第一步中的命名實(shí)體識(shí)別,可直接利用現(xiàn)有命名實(shí)體識(shí)別方法獲得,在此不再贅述。

EntityRank算法是在TextRank的基礎(chǔ)上針對(duì)實(shí)體進(jìn)行的改進(jìn)算法。與TextRank類(lèi)似,EntityRank首先要對(duì)文檔中出現(xiàn)的實(shí)體進(jìn)行構(gòu)圖,構(gòu)圖方法如下。

(1)按照段落作為實(shí)體共現(xiàn)的窗口,處于同一段落中的實(shí)體相互連邊。原始的算法中兩點(diǎn)之間有連邊即表示兩點(diǎn)之間有一定的相關(guān)關(guān)系。在一篇報(bào)道中,一個(gè)段落往往對(duì)應(yīng)著一個(gè)相關(guān)主題,處于一個(gè)段落中的實(shí)體則通常具有相關(guān)關(guān)系,利用段落作為實(shí)體共現(xiàn)的窗口既能避免人為設(shè)定k值導(dǎo)致的偏差,又能使相關(guān)實(shí)體能夠建立起聯(lián)系。

(2)處于同一窗口內(nèi)的實(shí)體按照距離遠(yuǎn)近關(guān)系計(jì)算,如式(1)所示。由于實(shí)體往往具有稀疏性,處于同一窗口內(nèi)的實(shí)體并不會(huì)像普通詞匯一樣密集,此時(shí)如果再利用共現(xiàn)詞頻等作為連邊權(quán)重往往不能起到相應(yīng)的作用。但是根據(jù)語(yǔ)言學(xué)的規(guī)律,相關(guān)的實(shí)體往往會(huì)距離比較近,因此利用實(shí)體在段落中的距離來(lái)衡量實(shí)體之間的相關(guān)關(guān)系比較符合連邊權(quán)重的意義。

(1)

其中Wij表示連邊權(quán)重,dis(i,j)表示實(shí)體i和實(shí)體j之間的距離,max_distance為整篇文章的所有段落中最長(zhǎng)段落的長(zhǎng)度。

得到了連邊權(quán)重Wij后,便可以按照公式(2)進(jìn)行迭代運(yùn)算,最終獲得每個(gè)實(shí)體的重要度。

(2)

其中d是抑制因子,d∈(0,1),In(Vi)為與Vi有連邊的所有節(jié)點(diǎn),Out(Vj)為與Vj有連邊的所有節(jié)點(diǎn),WS(Vi)為節(jié)點(diǎn)Vi的重要度。

EntityRank算法的主要步驟總結(jié)如下。

算法:EntityRank輸入:帶有位置信息的實(shí)體集合S=[(entity1,loc1),(entity2,loc2),…,(entityn,locn)]輸出:實(shí)體對(duì)應(yīng)權(quán)重信息Res=[(entity1,weight1),(entity2,weight2),…,(entityn,weightn)] step1step2step3step4將實(shí)體集合按照段落進(jìn)行切分,分成若干子集。S1, S2,…, Sn,Si∈S.針對(duì)每個(gè)子集Si,進(jìn)行構(gòu)圖。構(gòu)圖規(guī)則為:(1)子集中的實(shí)體為圖中的節(jié)點(diǎn)。(2)屬于同一子集中的實(shí)體相互建立連邊。(3)連邊權(quán)重由公式(1)得到。針對(duì)步驟2得到的圖,按照公式(2)進(jìn)行節(jié)點(diǎn)權(quán)重迭代計(jì)算。返回結(jié)果Res。

1.2 實(shí)體集合間相似度計(jì)算方法

(1)字形字序法

字形字序法的主要作用是計(jì)算兩個(gè)實(shí)體在字面上的相似度,主要借鑒現(xiàn)有的詞形詞序法[13]。設(shè)sameCC(A,B)為實(shí)體A和B中相同字的個(gè)數(shù),當(dāng)同一個(gè)字在A和B中出現(xiàn)的次數(shù)不同時(shí),以出現(xiàn)次數(shù)少的計(jì)數(shù),則實(shí)體A和B的字形相似度為:

(3)

可知,0≤WordSim(A,B)≤1.

設(shè)OnceCS(A,B)表示A和B中都出現(xiàn)且只出現(xiàn)一次的字的集合。Pfirst(A,B)表示OnceCS(A,B)中的每個(gè)字在A中的位置序號(hào)構(gòu)成的數(shù)字排列，Psecond(A,B)表示Pfirst(A,B)中的分量按對(duì)應(yīng)字在B中的字序排列生成的數(shù)字排列，RevOrd(A,B)表示Psecond(A,B)各相鄰分量的逆序數(shù)。則A和B的字序相似度為

(4)

可知0≤OrdSim(A,B)≤1.綜合字形相似度和字序相似度,詞語(yǔ)A和B的相似度為:

Simword(A,B)=α1×WordSim(A,B)+α2×WordSim(A,B) ，

(5)

其中α1和α2均為常數(shù)并且滿(mǎn)足α1+α2=1,因此0≤Simword(A,B)≤1.由于詞形相似度相對(duì)詞序相似度更能代表詞的相似程度,所以一般有α1>α2.

(2)語(yǔ)義相關(guān)法

語(yǔ)義相關(guān)法的主要作用是計(jì)算兩個(gè)實(shí)體在語(yǔ)義上的相似度,主要利用Word2Vec[14-16]的方式對(duì)實(shí)體進(jìn)行向量化表示,然后利用余弦相似度對(duì)兩個(gè)實(shí)體的向量表示進(jìn)行計(jì)算。

Simsem(A,B)=cos(Ai,Bi) ，

(6)

其中A和B為兩個(gè)實(shí)體,Ai和Bi則為A和B對(duì)應(yīng)的向量,Simsem(A,B)為實(shí)體A和B的語(yǔ)義相似度。

(3)實(shí)體集合相似度計(jì)算

兩篇文本包含的實(shí)體之間的相關(guān)性是這兩篇文本之間相關(guān)性的重要反映。最大實(shí)體關(guān)聯(lián)法是計(jì)算兩個(gè)實(shí)體集合之間相似度的方法,是在最大詞語(yǔ)關(guān)聯(lián)法[17]的基礎(chǔ)上針對(duì)實(shí)體進(jìn)行的改善。對(duì)于兩個(gè)實(shí)體集合A和B,針對(duì)集合中的實(shí)體獲得詞向量A′={a1,a2,…,am}和B′={b1,b2,…,bn},不失一般性,可令n≥m.構(gòu)建兩個(gè)文檔的實(shí)體特征相關(guān)矩陣為:

(7)

其中Sij表示實(shí)體Ai和Bj之間的綜合相關(guān)度值,由字形字序法和語(yǔ)義相關(guān)度共同決定:

Sij=α3×Simword(Ai,Bj)+α4×Simsem(Ai,Bj) ，

(8)

其中Simsem(Ai,Bj)為實(shí)體Ai和實(shí)體Bj對(duì)應(yīng)詞向量的余弦相似度的值,α3和α4均為常數(shù)并且滿(mǎn)足α3+α4=1,因此0≤sij≤1.可知矩陣S第i行中的最大值是實(shí)體集合A中實(shí)體Ai與實(shí)體集合B中實(shí)體相關(guān)度最大的實(shí)體的相關(guān)度值。取S中每一行具有最大值的元素,構(gòu)成文檔A和B的最大實(shí)體關(guān)聯(lián)序列:

maxL={S1,x1,S2,x2,…,Sm,xm} ，

(9)

然后,由式(10)計(jì)算A和B之間的實(shí)體相關(guān)度:

(10)

其中,wi和wxi分別是Ai和Bxi在實(shí)體集合A和B中的權(quán)重,其定義如下：

(11)

(12)

其中size(A)表示實(shí)體集合中包含實(shí)體的數(shù)量,t為當(dāng)前實(shí)體在實(shí)體列表中的位置,L代表衰減周期,k則為衰減系數(shù)。

由于在多源文本中,來(lái)自不同通道的數(shù)據(jù)具有的事件實(shí)體數(shù)量多少不一、種類(lèi)不同，不同類(lèi)型的事件實(shí)體之間顯然不能進(jìn)行相似度計(jì)算,而在同種類(lèi)型事件實(shí)體計(jì)算相似度時(shí)則既要考慮到字面的相似性,又要結(jié)合語(yǔ)義相似度。除此之外,例如某些微博數(shù)據(jù)中只會(huì)包含少量類(lèi)型的事件實(shí)體,而新聞報(bào)道中包含的事件實(shí)體類(lèi)型相對(duì)較多,這種情況下,如果兩種文本共同含有的實(shí)體相似度很高,則兩篇文章的整體相似度可能依舊很高,因此在文檔間實(shí)體集合相似度計(jì)算方法設(shè)計(jì)的過(guò)程中不能簡(jiǎn)單地將不同類(lèi)型的實(shí)體相似度進(jìn)行疊加?；谝陨系目紤],本文設(shè)計(jì)的文檔間實(shí)體集合相似度計(jì)算方法主要有以下幾個(gè)步驟。

1)共同出現(xiàn)的同類(lèi)型實(shí)體之間計(jì)算相似度。

2)相似度計(jì)算方法選用最大實(shí)體關(guān)聯(lián)法。

3)對(duì)于不同實(shí)體類(lèi)型的相似度計(jì)算結(jié)果取平均。

根據(jù)以上幾點(diǎn),本文提出的文檔間實(shí)體集合相似度計(jì)算方法可以用下式表示：

(13)

其中A,B表示兩篇文檔,Ae和Be表示兩篇文檔中屬于類(lèi)型e的實(shí)體集合,EntitySim表示文檔間實(shí)體集合相似度,entitys為兩篇文檔中共同出現(xiàn)的實(shí)體類(lèi)型,entitys-num為兩篇文檔中共同出現(xiàn)的實(shí)體類(lèi)型的數(shù)量,Siment即上文中的最大實(shí)體關(guān)聯(lián)法。

1.3 結(jié)合實(shí)體的多源文本事件發(fā)現(xiàn)算法ESP

ESP算法的核心在于利用兩篇文檔在事件實(shí)體間的相似度,輔助進(jìn)行事件發(fā)現(xiàn)。事件核心實(shí)體的具體使用方式可以分多種情況:(1)當(dāng)事件核心實(shí)體間相似度大于某個(gè)閾值時(shí),直接判定為相似,歸為一類(lèi),否則通過(guò)文本相似度進(jìn)行判斷。(2)當(dāng)事件核心實(shí)體間相似度小于某個(gè)閾值時(shí),直接判斷為不相似,否則通過(guò)文本相似度進(jìn)行判斷。(3)將事件核心實(shí)體相似度與文本相似度進(jìn)行結(jié)合之后再和閾值進(jìn)行比較等。

在利用以上幾種方式進(jìn)行輔助事件發(fā)現(xiàn)的過(guò)程中,事件核心實(shí)體間相似度是指當(dāng)前文檔與現(xiàn)有事件中所有文檔的事件核心實(shí)體相似度的平均值。如果當(dāng)前文檔能夠加入現(xiàn)有事件,則用當(dāng)前文檔的向量更新事件代表向量，即

(14)

其中n為當(dāng)前事件所包含的文檔數(shù),V為當(dāng)前文檔向量,VEold為當(dāng)前事件代表向量,VEnew為更新后的事件代表向量。

Entity Single-Pass算法的核心偽代碼如下。

算法:Entity Single-Pass 輸入:documents,SIM-THRESH,ENTITY-THRESH 輸出:eventSet 123456789 101112131415161718192021222324252627FOREACH doc in documents max-sim=0.0 matchEvent=NUL matchFlag=False doc-entity=getEntitys(doc) doc-vec=getDocVec(doc) FOREACH event in eventSet event-entitys=getEntitys(event) event-vec=getEventVec(event) entity-sim=GetEntitySimilarity(doc-entity,event-entitys) IF entity-sim> ENTITY-THRESH THEN UpdateEvent(event,doc,doc-entity,eventSet) matchFlag=True BREAK END IF vec-sim=getCosinSim(doc-vec,event-vec) IF vec-sim> max-sim THEN max-sim=vec-sim matchEvent=event END IF END FOR IF not matchFlag and max-sim> SIM-THRESH THEN UpdateEvent(event,doc,doc-entity,eventSet) ELSE CreateEvent(doc,doc-entity,eventSet) END IFEND FORReturn eventSet

算法:GetEntitySimilarity 輸入:doc-entity,event-entitys 輸出:similarity 1INIT: sim-sum=0 2 FOREACH event-ent in event-entitys 3 sim-sum=sim-sum+siment(doc-entity,event-entity) 4 END FOR 5Return sim-sum/size(event-entitys)

2 實(shí)驗(yàn)結(jié)果及分析

本節(jié)利用真實(shí)的微博事件語(yǔ)料和新聞事件語(yǔ)料對(duì)所提算法進(jìn)行驗(yàn)證。

2.1 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)數(shù)據(jù)來(lái)自于新聞報(bào)道和微博數(shù)據(jù),其中包含臺(tái)灣花蓮地震、云南九寨溝地震、四川涼山山洪、遼寧災(zāi)害天氣、青海地震、美國(guó)槍擊案等30個(gè)事件共2 000條數(shù)據(jù),其中新聞數(shù)據(jù)和微博數(shù)據(jù)各1 000條。

實(shí)驗(yàn)中核心實(shí)體的獲取方式根據(jù)文章所屬通道的類(lèi)型不同而有所區(qū)別。對(duì)于新聞報(bào)道等數(shù)據(jù),利用事件核心實(shí)體識(shí)別方法進(jìn)行核心實(shí)體識(shí)別。對(duì)于微博等數(shù)據(jù),首先根據(jù)微博數(shù)據(jù)格式的特點(diǎn),對(duì)于微博間格符“##”之間的內(nèi)部實(shí)體進(jìn)行識(shí)別和提取,將其直接作為事件核心實(shí)體。如果并未存在特殊結(jié)構(gòu),則同樣利用事件核心實(shí)體識(shí)別方法進(jìn)行識(shí)別。

2.2 評(píng)價(jià)標(biāo)準(zhǔn)

實(shí)驗(yàn)的評(píng)價(jià)指標(biāo)采用聚類(lèi)算法常用的標(biāo)準(zhǔn)化互信息(Normalized Mutual Information,NMI)和蘭德指數(shù)(Rand Index,RI)，其定義分別為：

(15)

其中I為互信息,H代表熵:

(16)

(17)

其中p(xi)表示文檔屬于簇xi的概率,p(x,y)表示文檔屬于簇x∩y的概率。

(18)

2.3 實(shí)驗(yàn)設(shè)計(jì)

K-means和Single-Pass是經(jīng)典的事件發(fā)現(xiàn)算法,因此本文選擇K-means和Single-Pass作為baseline。由于事件核心實(shí)體與傳統(tǒng)的Single-Pass方法有多種結(jié)合方式,本文分別針對(duì)以下情況作了實(shí)驗(yàn)。

(1) 當(dāng)事件核心實(shí)體間相似度大于某個(gè)閾值時(shí),直接判定為相似,歸為一類(lèi),否則通過(guò)文本相似度進(jìn)行判斷。

(2) 當(dāng)事件核心實(shí)體間相似度小于某個(gè)閾值時(shí),直接判斷為不相似,否則通過(guò)文本相似度進(jìn)行判斷。

(3) 將事件核心實(shí)體相似度與文本相似度進(jìn)行結(jié)合之后再和閾值進(jìn)行比較,如果相似度大于閾值,則歸為一類(lèi),否則不能歸為一類(lèi)。

同時(shí),為避免閾值設(shè)置導(dǎo)致的結(jié)果偏差,本文在實(shí)驗(yàn)過(guò)程中,針對(duì)實(shí)驗(yàn)(1)和實(shí)驗(yàn)(2)分別按照事件核心實(shí)體相似度閾值以0.1為間隔,從0.1到1共10組閾值,文本相似度閾值以0.1為間隔,從0.1到1共10組閾值,排列組合共100種閾值組合中選取最優(yōu)組合作為最終的實(shí)驗(yàn)結(jié)果。針對(duì)實(shí)驗(yàn)(3),按照閾值以0.1為間隔,從0.1到2共20種結(jié)果中選取最優(yōu)組合作為最終的實(shí)驗(yàn)結(jié)果。K-means方法中聚類(lèi)中心K分別取20,25,30,35,40,選取最優(yōu)結(jié)果作為最終的實(shí)驗(yàn)結(jié)果。

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

實(shí)驗(yàn)對(duì)比結(jié)果如圖2。

Fig.2 Result of text clustering圖2 事件聚類(lèi)結(jié)果圖

5種方法取得最好結(jié)果時(shí)的參數(shù)設(shè)置如表1所示。其中Textsim為文本相似度閾值，Entitysim為實(shí)體集合相似度閾值。

表1 五種方法最優(yōu)閾值表

可以看出,與K-means和原始Single-Pass方法相比,在結(jié)合了事件核心實(shí)體間相似度之后,各次實(shí)驗(yàn)的結(jié)果均好于原始Single-Pass方法。其中方法1和方法3相比原始Single-Pass結(jié)果在NMI和RI評(píng)價(jià)指標(biāo)下均有較明顯提高。方法2的最優(yōu)結(jié)果則與原方法有一定的提升。

針對(duì)方法1的效果提升,可以看出當(dāng)事件核心實(shí)體相似度大于某閾值時(shí),即使不計(jì)算文本相似度,直接歸為一類(lèi),也能達(dá)到準(zhǔn)確發(fā)現(xiàn)事件的效果,并且相對(duì)于只利用文本相似度,消除了一些文本中的噪音,提高了事件發(fā)現(xiàn)的準(zhǔn)確性。

針對(duì)方法2的效果提升,可以看出在原始Single-Pass方法中,存在某些文本相似度上較高,但屬于不同事件的文檔被判斷為同一事件。而通過(guò)利用實(shí)體相似度進(jìn)行過(guò)濾,將這些錯(cuò)誤聚類(lèi)到一起的文檔更好的分開(kāi)。

針對(duì)方法3的效果提升,可以看出事件核心實(shí)體相似度可以彌補(bǔ)文本相似度的不足,兩種相似度結(jié)合后,同一事件下的文檔能更好地結(jié)合在一起。但是同樣,由于某些不屬于同一事件的文檔其文本相似程度偏高,使得結(jié)合實(shí)體相似度后,仍舊使得總體相似度高于閾值,導(dǎo)致聚類(lèi)錯(cuò)誤。

此外,方法1的效果相對(duì)于方法3有更好的表現(xiàn),說(shuō)明了在新聞報(bào)道和微博消息在一起進(jìn)行聚類(lèi)時(shí),文章長(zhǎng)度的不同使得文本在表達(dá)后進(jìn)行相似度計(jì)算的效果并不理想,同時(shí)也說(shuō)明了事件實(shí)體能夠更好地對(duì)事件進(jìn)行表達(dá),從而使得多源數(shù)據(jù)一起聚類(lèi)時(shí)效果更好。

在Single-Pass算法的改進(jìn)過(guò)程中,事件核心實(shí)體間的相似度作為閾值起到了過(guò)濾作用。根據(jù)實(shí)驗(yàn)結(jié)果來(lái)看,以上改進(jìn)的方法相對(duì)于原始Single-Pass的事件發(fā)現(xiàn)方法的效果有所提升,因此可以說(shuō)明結(jié)合事件實(shí)體的改進(jìn)事件發(fā)現(xiàn)算法是有效的,同時(shí)文檔間實(shí)體集合相似度計(jì)算方法也是可行的。

3 結(jié)論

本文提出了一種適用于多源文本場(chǎng)景下的結(jié)合實(shí)體的事件發(fā)現(xiàn)算法ESP,算法針對(duì)傳統(tǒng)事件發(fā)現(xiàn)方法在處理多源文本事件發(fā)現(xiàn)問(wèn)題中的缺陷,提出并設(shè)計(jì)了事件核心實(shí)體識(shí)別方法,同時(shí)設(shè)計(jì)了實(shí)體集合間相似度計(jì)算方法,并給出了將實(shí)體集合相似度與Single-Pass結(jié)合的多種方式。算法通過(guò)引入事件核心實(shí)體的信息,豐富了多源文本中原始文檔的表達(dá)信息,從而提高了事件發(fā)現(xiàn)算法的效果。在微博、微信和新聞等多源數(shù)據(jù)上對(duì)算法的有效性做了驗(yàn)證。通過(guò)與K-means和Single-Pass方法的比較，我們的方法在NMI和RI兩項(xiàng)評(píng)價(jià)指標(biāo)上分別提高了0.2和0.3，證明了ESP算法的有效性。