跨文檔事件檢測算法

馮戈利

(1.西北工業(yè)大學 機電學院，陜西西安 710072)(2.成都飛機工業(yè)(集團)有限責任公司，四川成都 610092)

事件檢測與描述問題是由自動文本抽取(Automatcic Content Extraction，ACE)會議提出的，主要研究如何描述事件并根據(jù)給定語料庫實現(xiàn)事件的檢測。目前的研究主要集中在單文檔事件檢測，采用概率模型、分類算法和文本匹配等方法實現(xiàn)事件檢測。

事件檢測是自然語言處理和數(shù)據(jù)挖掘的一個交叉研究熱點方向。文獻［1］提出了基于事件實例驅動的事件抽取方法，然后通過二元分類器對新聞文本中的事件實例與非事件實例進行分類，選取句子的長度、位置、詞語的個數(shù)、命名實體的個數(shù)、時間的個數(shù)、數(shù)值的個數(shù)、停用詞的頻率等作為二元分類器的參數(shù)識別新聞文本中表述事件的句子。文獻［2］針對具有關聯(lián)要素的中文文本事件檢測問題，采用關聯(lián)關系分析、關鍵詞語義擴展和關鍵詞作用域擴展等方法，將目標事件包含的所有文本作為一個整體進行關鍵詞匹配實現(xiàn)事件檢測。文獻［3］基于時空元素語義搜索引擎，提出基于語義的文本事件信息抽取方法，應用多方面語義知識和統(tǒng)計方法，強調時、空元素對于事件追蹤的定位功能，進行信息抽取和歸并，最終實現(xiàn)對文本中事件的描述。在文檔事件檢測基礎上，微博的事件檢測也是一大研究熱點［4－8］。其中張志瑛［4］提出了基于LDA主題模型的事件檢測方法，通過挖掘屬于事件的主題，然后找到與該主題關聯(lián)的微博，實現(xiàn)微博事件的檢測。趙江江［5］以任意領域事件觸發(fā)詞為核心，并包括與其關聯(lián)的時間、地點、人物、數(shù)量等多種元素構成的結構化數(shù)據(jù)，提出基于規(guī)則的方法和基于CRF模型的方法進行事件檢測。楊文漪［6］提出將事件檢測重點從文檔轉換為特征，通過微博數(shù)據(jù)自身的特點來表示微博特征。除了事件檢測外，單建芳［9］還研究了事件的文本表示方法。作為事件檢測的一種基礎方法，文本相似度計算［10－12］也是目前研究的熱點方向。

本文針對單一文檔只包含一個事件部分信息，傳統(tǒng)算法難以確切判斷該文檔是否具有該事件的情況，提出了一種跨文檔的事件檢測算法(Cross－Document Event Detection Algorithm，CDEDA)，該算法能夠聯(lián)合多篇描述同一事件的文檔(其中每篇文檔只包含部分事件的信息)檢測出目標事件。CDEDA以文檔中的信息要素為詞匯單元，建立共現(xiàn)詞網(wǎng)絡，事件通過主體、時間、地點和主題的4W(Who，When，Where，What)向量描述，通過深度優(yōu)先搜索算法在共現(xiàn)詞網(wǎng)絡中搜索事件4W向量的子向量(由于4W向量的每個分量可能由多個詞表示，子向量的每個分量僅由一個詞表示，每個事件的4W向量會有多個子向量)，判斷文檔集中是否包含目標事件，最后根據(jù)子向量的分量逆向求解包含這些分量的文檔，實現(xiàn)跨文檔的事件檢測。

1 跨文檔事件檢測模型

1.1 模型介紹

在跨文檔事件檢測中，事件信息要素雖然分布于不同的文檔，但是他們都是描述同一個事件，存在一些相同的信息要素。本文以文檔之間相同的信息要素建立共現(xiàn)詞網(wǎng)絡(共現(xiàn)詞指在兩篇文檔中共同出現(xiàn)的詞語)，實現(xiàn)跨文檔事件檢測。

首先，提取文檔中的信息要素。對于事件的主體、時間、地點的提取方法采用命名實體識別方法［13］。對于事件的主題，本文采用 TF－IDF算法［14］(Term Frequency － Inverse Document Frequency)。首先，計算文檔中每個詞語的權重值，并選取權重值較高的Top－N詞語進行描述。然后，建立共現(xiàn)詞網(wǎng)絡。網(wǎng)絡的節(jié)點為第一步中所有共現(xiàn)詞候選集合中的信息要素，如果兩個信息要素屬于共現(xiàn)詞，那么在這兩個節(jié)點間連一條邊。第三步，發(fā)掘共現(xiàn)詞網(wǎng)絡中的環(huán)。在共現(xiàn)詞網(wǎng)絡中，一個完整的回路所組成的環(huán)表示環(huán)中各個節(jié)點都相互關聯(lián)，那么這些節(jié)點代表的信息要素共同出現(xiàn)的文檔也具有一定的關聯(lián)性。最后，將表征事件的信息要素與這些環(huán)所包含的信息要素進行匹配，如果某個環(huán)包含事件中的全部信息要素，那么組成這個環(huán)的相關文檔就包含該事件，從而達到跨文檔檢測的目的。

一個簡單的共現(xiàn)詞網(wǎng)絡結構圖如圖1所示。圖中節(jié)點(詞語)為從文檔中提取出來的信息要素，兩個節(jié)點有連接線代表這兩個詞語是共現(xiàn)詞。從圖1中，可以挖掘出一條完整的環(huán)路(西飛—365所—2010.5.3—無人機試驗，在圖中以虛線連接)。如果待檢測事件為:“2010年5月3號，365所在西飛成功進行無人機實驗”，事件的向量為{(主題:無人機試驗)，(主體:西飛，365 所)，(時間:2010.5.3)，(地點:西飛，365所)}。環(huán)路中的信息要素包含了待檢測事件的信息要素，說明組成共現(xiàn)詞網(wǎng)絡中的文檔集合包含了該事件的描述。

圖1 共現(xiàn)詞網(wǎng)絡圖

1.2 問題描述

D={d1，d2，…，dn}表示文檔的集合，di表示第 i個文檔，一共有n個文檔。T={t1，t2，…，tm}表示所有信息要素的集合，tj表示第j個信息要素，一共有m個信息要素。如果文檔di包含信息要素tj，記為 tj→di，否則 tj┐→di。Am×n為 m 行 n 列的信息要素－文檔矩陣，Aij定義如下:

G(T，E)為共現(xiàn)詞網(wǎng)絡圖，信息要素的集合T構成圖中節(jié)點的集合。E為邊的集合，兩個信息要素出現(xiàn)在同一個文檔，則在兩個信息要素節(jié)點上連一條邊。

I=(wa，wb，wc，wf)為事件 4W 向量，其中 wa，wb，wc，wf分別是事件的主體向量、時間向量、地點向量、主題向量。事件4W向量的任一分量由若干信息要素組成，其中 wa=(ta1，ta2，…，tap)，wb=

從 wa，wb，wc，wf中分別抽取一個信息要素組成事件 I 的子向量，如子向量tfl)，一個事件通常包含多個子向量。

如果存在一個事件 I 的子向量 Ii，j，k，l，其分量tai，tbj，tck，tfl都是環(huán) h 中的節(jié)點，則稱環(huán) h 包含事件I。

本文研究的問題定義如下。

輸入:文檔的集合D，事件的描述I。

輸出:通過 D 生成 T，Am×n，G(T，E)，然后判斷圖G中是否存在包含事件I的環(huán)h，最后輸出組成環(huán)h的文檔集合Dh。

2 跨文檔事件檢測算法

2.1 信息要素獲取

信息要素包括事件的主體、時間、地點和主題，其中主體包括人名和機構名稱。本文通過命名實體識別方法從文檔中提取主體、時間、地點。對于主題的獲取，則采用TF－IDF算法提取權重值較高的N個詞語作為文檔的主體。TF－IDF算法如公式(2)、(3)、(4)描述:

式中:w(ti，dj)為信息要素ti在文檔dj中的權重;N(ti，dj)為在文檔dj中信息要素ti出現(xiàn)的次數(shù);max(N(tk，dj))為文檔dj中出現(xiàn)次數(shù)最多的信息要素的次數(shù);n為文檔總數(shù);ni為包含信息要素ti的文檔數(shù)。

2.2 共現(xiàn)詞網(wǎng)絡圖生成

最初的輸入是文檔的集合D，通過2.1節(jié)信息要素的獲取方法，可以得到信息要素集合T。結合D，T，通過式(1)，可以得到信息要素－文檔矩陣Am×n。共現(xiàn)詞網(wǎng)絡圖G(T，E)采用鄰接矩陣表示，其中頂點數(shù)組 V={t1，t2，…，tm}，鄰接矩陣為Bm×m，

鄰接矩陣生成過程如下:

2.3 事件檢測算法

直接從圖G中搜索環(huán)，然后判斷是否存在包含事件I的環(huán)，雖然可以達到檢測目的，但要遍歷整個圖G，在遍歷過程中還需要存儲很多與事件I不相關的環(huán)，計算量和存儲量開銷很大，效率很低。

本文采用逆向的思路，首先從事件I中抽取出子向量，然后將子向量中的信息要素和其他若干信息要素組成環(huán)，最后判斷這個環(huán)是否有可能存在于圖G中。

本文采用深度優(yōu)先搜索，具體描述如下:

輸入:事件 I=(wa，wb，wc，wf)，文檔集合 D={d1，d2，…，dn}，共現(xiàn)詞網(wǎng)絡圖 G(T，E)及其鄰接矩陣表示(頂點數(shù)組 V={t1，t2，…，tm}，鄰接矩陣為Bm×m)，包含事件環(huán)h的長度x(x≥5)。

輸出:包含事件I的環(huán)h。

根據(jù)包含事件I的環(huán)h逆向獲取組成環(huán)h的文檔集合Dh的算法如下:

3 實驗與分析

3.1 數(shù)據(jù)集說明

為了驗證算法的有效性，通過網(wǎng)絡爬蟲工具搜集新華網(wǎng)、新浪新聞、騰訊新聞、網(wǎng)易新聞、搜狐新聞、360新聞上2014年11月份共6 000條新聞文檔。選取了10個待檢測事件，人工分辨新聞文檔是否描述了待檢測的事件作為實驗判斷依據(jù)。

3.2 評估指標

實驗評估指標為正確率、召回率和F1－measure，所有檢測結果可以分為表1中的4種情況。

準確率 (P)、召回率(R)、F1－measure值(F1)計算公式如下:

表1 檢測結果分類

3.3 基準算法

文檔集合:

事件:

算法1:k詞項事件檢測算法(k－Term Event Detection Algorithm，k－TEDA)。

如果di包含事件I中k個信息要素，則判斷di包含事件I。

算法2:k文檔事件檢測算法(k－Document E-vent Detection Algorithm，k－DEDA)。

如果k個文檔的集合包含事件I中所有信息要素，減少任意一個文檔后的文檔集合，不包含I中所有信息要素，則判斷這k個文檔都在描述事件I。

3.4 實驗結果與分析

在3.1節(jié)中描述的數(shù)據(jù)集上分別計算CDEDA、k－TEDA、k－DEDA 3種算法的準確率、召回率、F1－measure值，對于k－TEDA、k－DEDA兩種算法，k值分別取1，2，3做實驗。

圖2 TEDA的準確率

對于k－TEDA，實驗結果如圖2和圖3所示，其準確率隨k的增大而提高，召回率隨k的增大而降低。對于k－DEDA，實驗結果如圖4和圖5所示，其準確率隨k的增大而降低，召回率隨k的增大而提高。3種算法的準確率、召回率、F1－measure值分別如圖6、圖7和圖8所示，1－DEDA正確率最高，但其召回率很低;1－TEDA召回率很好，但正確率比較低;本文提出的CDEDA算法在正確率和召回率上都比較好，從圖8中的F1－measure可以看出，CDEDA是最高的，其他兩種算法很難在正確率和召回率兩者上都取得很好的效果。

圖3 TEDA的召回率

圖4 DEDA的準確率

圖5 DEDA的召回率

圖6 3種算法的準確率

4 結束語

圖7 3種算法的召回率

圖8 3種算法的F1－measure

本文采用4W向量描述待檢測事件，從文檔集中提取信息要素，并建立共現(xiàn)詞網(wǎng)絡，提出了跨文檔的事件檢測算法CDEDA，它能夠聯(lián)合多篇描述同一事件的文檔進行事件檢測。實驗證明，本文提出的算法在準確率、召回率、F1－measure值上都優(yōu)于其他一些算法。

［1］ 許旭陽，李弼程，張先飛，等.基于事件實例驅動的新聞文本事件抽?。跩］.計算機科學，2011(8):232－235.

［2］ 褚衍杰，魏強，李云照.基于關鍵詞語義與作用域擴展的事件檢測［J］.計算機工程，2014(8):273－276，281.

［3］ 李婷玉.基于語義的文本事件信息抽取方法的研究與實現(xiàn)［D］.上海:上海交通大學，2012.

［4］ 張志瑛.基于主題模型和社區(qū)發(fā)現(xiàn)的微博熱點事件檢測研究［D］.重慶:西南大學，2014.

［5］ 趙江江.開放域事件抽取與微博事件檢測跟蹤［D］.哈爾濱:哈爾濱工業(yè)大學，2013.

［6］ 楊文漪.面向微博的事件檢測算法研究［D］.北京:北京郵電大學，2013.

［7］ Sakaki T，Okazaki M，Matsuo Y.Earthquake shakes Twitter users:real－ time event detection by social sensors［C］//Proceedings of the 19th international conference on World wide web，New York.NY，USA:ACM，2010:851－860.

［8］ Weng J，Lee B S.Event detection in twitter［J］.ICWSM，2011(11):401－408.

［9］ 單建芳.面向事件的文本表示研究［D］.上海:上海大學，2012.

［10］趙玉茗.文本間語義相關性計算及其應用研究［D］.哈爾濱:哈爾濱工業(yè)大學，2009.

［11］趙玉茗，徐志明，王曉龍，等.基于詞匯集聚的文檔相關性計算［J］.電子與信息學報，2008(10):2512－2515.

［12］黃承慧，印鑒，侯昉.一種結合詞項語義信息和TF－IDF方法的文本相似度量方法［J］.計算機學報，2011(5):856－864.

［13］江會星.漢語命名實體識別研究［D］.北京:北京郵電大學，2012.

［14］Yang Y，Pierce T，Carbonell J.A study on retrospective and on －line event detection［C］//Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.Melbourne，Australia:ACM，1998:28 －36.