跨文档事件检测算法

冯戈利

(1.西北工业大学 机电学院，陕西西安 710072)(2.成都飞机工业(集团)有限责任公司，四川成都 610092)

事件检测与描述问题是由自动文本抽取(Automatcic Content Extraction，ACE)会议提出的，主要研究如何描述事件并根据给定语料库实现事件的检测。目前的研究主要集中在单文档事件检测，采用概率模型、分类算法和文本匹配等方法实现事件检测。

事件检测是自然语言处理和数据挖掘的一个交叉研究热点方向。文献［1］提出了基于事件实例驱动的事件抽取方法，然后通过二元分类器对新闻文本中的事件实例与非事件实例进行分类，选取句子的长度、位置、词语的个数、命名实体的个数、时间的个数、数值的个数、停用词的频率等作为二元分类器的参数识别新闻文本中表述事件的句子。文献［2］针对具有关联要素的中文文本事件检测问题，采用关联关系分析、关键词语义扩展和关键词作用域扩展等方法，将目标事件包含的所有文本作为一个整体进行关键词匹配实现事件检测。文献［3］基于时空元素语义搜索引擎，提出基于语义的文本事件信息抽取方法，应用多方面语义知识和统计方法，强调时、空元素对于事件追踪的定位功能，进行信息抽取和归并，最终实现对文本中事件的描述。在文档事件检测基础上，微博的事件检测也是一大研究热点［4－8］。其中张志瑛［4］提出了基于LDA主题模型的事件检测方法，通过挖掘属于事件的主题，然后找到与该主题关联的微博，实现微博事件的检测。赵江江［5］以任意领域事件触发词为核心，并包括与其关联的时间、地点、人物、数量等多种元素构成的结构化数据，提出基于规则的方法和基于CRF模型的方法进行事件检测。杨文漪［6］提出将事件检测重点从文档转换为特征，通过微博数据自身的特点来表示微博特征。除了事件检测外，单建芳［9］还研究了事件的文本表示方法。作为事件检测的一种基础方法，文本相似度计算［10－12］也是目前研究的热点方向。

本文针对单一文档只包含一个事件部分信息，传统算法难以确切判断该文档是否具有该事件的情况，提出了一种跨文档的事件检测算法(Cross－Document Event Detection Algorithm，CDEDA)，该算法能够联合多篇描述同一事件的文档(其中每篇文档只包含部分事件的信息)检测出目标事件。CDEDA以文档中的信息要素为词汇单元，建立共现词网络，事件通过主体、时间、地点和主题的4W(Who，When，Where，What)向量描述，通过深度优先搜索算法在共现词网络中搜索事件4W向量的子向量(由于4W向量的每个分量可能由多个词表示，子向量的每个分量仅由一个词表示，每个事件的4W向量会有多个子向量)，判断文档集中是否包含目标事件，最后根据子向量的分量逆向求解包含这些分量的文档，实现跨文档的事件检测。

1 跨文档事件检测模型

1.1 模型介绍

在跨文档事件检测中，事件信息要素虽然分布于不同的文档，但是他们都是描述同一个事件，存在一些相同的信息要素。本文以文档之间相同的信息要素建立共现词网络(共现词指在两篇文档中共同出现的词语)，实现跨文档事件检测。

首先，提取文档中的信息要素。对于事件的主体、时间、地点的提取方法采用命名实体识别方法［13］。对于事件的主题，本文采用 TF－IDF算法［14］(Term Frequency － Inverse Document Frequency)。首先，计算文档中每个词语的权重值，并选取权重值较高的Top－N词语进行描述。然后，建立共现词网络。网络的节点为第一步中所有共现词候选集合中的信息要素，如果两个信息要素属于共现词，那么在这两个节点间连一条边。第三步，发掘共现词网络中的环。在共现词网络中，一个完整的回路所组成的环表示环中各个节点都相互关联，那么这些节点代表的信息要素共同出现的文档也具有一定的关联性。最后，将表征事件的信息要素与这些环所包含的信息要素进行匹配，如果某个环包含事件中的全部信息要素，那么组成这个环的相关文档就包含该事件，从而达到跨文档检测的目的。

一个简单的共现词网络结构图如图1所示。图中节点(词语)为从文档中提取出来的信息要素，两个节点有连接线代表这两个词语是共现词。从图1中，可以挖掘出一条完整的环路(西飞—365所—2010.5.3—无人机试验，在图中以虚线连接)。如果待检测事件为:“2010年5月3号，365所在西飞成功进行无人机实验”，事件的向量为{(主题:无人机试验)，(主体:西飞，365 所)，(时间:2010.5.3)，(地点:西飞，365所)}。环路中的信息要素包含了待检测事件的信息要素，说明组成共现词网络中的文档集合包含了该事件的描述。

图1 共现词网络图

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)为共现词网络图，信息要素的集合T构成图中节点的集合。E为边的集合，两个信息要素出现在同一个文档，则在两个信息要素节点上连一条边。

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都是环 h 中的节点，则称环 h 包含事件I。

本文研究的问题定义如下。

输入:文档的集合D，事件的描述I。

输出:通过 D 生成 T，Am×n，G(T，E)，然后判断图G中是否存在包含事件I的环h，最后输出组成环h的文档集合Dh。

2 跨文档事件检测算法

2.1 信息要素获取

信息要素包括事件的主体、时间、地点和主题，其中主体包括人名和机构名称。本文通过命名实体识别方法从文档中提取主体、时间、地点。对于主题的获取，则采用TF－IDF算法提取权重值较高的N个词语作为文档的主体。TF－IDF算法如公式(2)、(3)、(4)描述:

式中:w(ti，dj)为信息要素ti在文档dj中的权重;N(ti，dj)为在文档dj中信息要素ti出现的次数;max(N(tk，dj))为文档dj中出现次数最多的信息要素的次数;n为文档总数;ni为包含信息要素ti的文档数。

2.2 共现词网络图生成

最初的输入是文档的集合D，通过2.1节信息要素的获取方法，可以得到信息要素集合T。结合D，T，通过式(1)，可以得到信息要素－文档矩阵Am×n。共现词网络图G(T，E)采用邻接矩阵表示，其中顶点数组 V={t1，t2，…，tm}，邻接矩阵为Bm×m，

邻接矩阵生成过程如下:

2.3 事件检测算法

直接从图G中搜索环，然后判断是否存在包含事件I的环，虽然可以达到检测目的，但要遍历整个图G，在遍历过程中还需要存储很多与事件I不相关的环，计算量和存储量开销很大，效率很低。

本文采用逆向的思路，首先从事件I中抽取出子向量，然后将子向量中的信息要素和其他若干信息要素组成环，最后判断这个环是否有可能存在于图G中。

本文采用深度优先搜索，具体描述如下:

输入:事件 I=(wa，wb，wc，wf)，文档集合 D={d1，d2，…，dn}，共现词网络图 G(T，E)及其邻接矩阵表示(顶点数组 V={t1，t2，…，tm}，邻接矩阵为Bm×m)，包含事件环h的长度x(x≥5)。

输出:包含事件I的环h。

根据包含事件I的环h逆向获取组成环h的文档集合Dh的算法如下:

3 实验与分析

3.1 数据集说明

为了验证算法的有效性，通过网络爬虫工具搜集新华网、新浪新闻、腾讯新闻、网易新闻、搜狐新闻、360新闻上2014年11月份共6 000条新闻文档。选取了10个待检测事件，人工分辨新闻文档是否描述了待检测的事件作为实验判断依据。

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节中描述的数据集上分别计算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向量描述待检测事件，从文档集中提取信息要素，并建立共现词网络，提出了跨文档的事件检测算法CDEDA，它能够联合多篇描述同一事件的文档进行事件检测。实验证明，本文提出的算法在准确率、召回率、F1－measure值上都优于其他一些算法。

［1］ 许旭阳，李弼程，张先飞，等.基于事件实例驱动的新闻文本事件抽取［J］.计算机科学，2011(8):232－235.

［2］ 褚衍杰，魏强，李云照.基于关键词语义与作用域扩展的事件检测［J］.计算机工程，2014(8):273－276，281.

［3］ 李婷玉.基于语义的文本事件信息抽取方法的研究与实现［D］.上海:上海交通大学，2012.

［4］ 张志瑛.基于主题模型和社区发现的微博热点事件检测研究［D］.重庆:西南大学，2014.

［5］ 赵江江.开放域事件抽取与微博事件检测跟踪［D］.哈尔滨:哈尔滨工业大学，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］.哈尔滨:哈尔滨工业大学，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.