资源描述
多维文档表示模型下的新闻事件发现与追踪-2009年工作进展报告邸楠北京大学 网络与分布报告编号 PKU_CS_NCIS_TR2009012提交时间 2009-12-27北京大学 信息科学技术学院网络与信息系统研究所，100871式系统实验室， 100871 北京大学信息科学技术学院 网络与信息系统研究所： PKU_CS_NCIS_TR2009012多维文档表示模型下的新闻事件发现与追踪邸楠（北京大学 信息科学与技术学院， 100871） 摘要：事件发现是将来自一个或多个信息源的新闻文档划分到已知的事件类别中，或者标注发现新的事件的过程。随着近年来网络新闻媒体的兴起，新闻网页的数量激增，如何有效的发现、分析这些网页内容中描述的新闻事件已经成为近年来网络信息挖掘研究领域的一个热点。经过对前人工作的调研分析，我们认为仅仅利用新闻文本内容，以及使用单一的“bag of words”模型不能充分展示事件内容的要点。以此为出发点，本文提出了一种新的文档表示模型，它有三个要素：文档的时间、文档中包含的实体，以及文档中包含实体的文本片段。在此基础上本文还采用了基于SVM的方法来帮助整合多个维度的特征以计算不同文档间的相似度。实验结果表明本文提出的方法较之传统单一使用文档向量的方法有提高。最后本文对现有的事件发现工作做了总结，并对今后工作做出了计划。1. 本文讨论中的重要概念和相关定义事件是一个可观察、非平凡的现象，它具有的要素包括时间、地点、发生的事情等，引起人们关注的事件可以是社会性的，也可以是自然性的等。而这些事件会引起大众媒体的关注，随着Web的爆炸式发展，网络媒体对新闻事件的报道已成为新闻报道的重要部分：这可以是网络新闻门户、个人blog等。针对这些网络媒体发表的与新闻事件相关文档进行的事件发现（event detection）或事件追踪（event tracking）已经成为近年来网络挖掘方向（web mining）中热门的研究点。这里我们首先给出几个与事件相关的重要概念：首先是事件（event）：我们定义事件是发生在一个特定时间、地点的事情，而且网络媒体中存在新闻文档对该事件进行报道。在后面的研究中我们将把事件表示成一组描述该事件的新闻文档的集合。第二是新闻文档（news story）：一篇新闻文档是事件发现工作中的基本单元，其中包括事件的若干信息，这可以是对一个新事件的报道，也可以是对现有事件进展的描述等。每篇新闻文档除了文本内容外，还至少包含一个时间标签以表明该文档的发表时间。这里我们假设每篇新闻文档属于且只属于一个事件。最后是事件发现：根据前面的两个定义和假设，事件发现就是将新闻文档集合划分成若干不相交的子集，使得每个子集中的文档都是描述同一事件的。另一类我们要讨论的重要概念是命名实体。首先，我们定义命名实体是用来标识一个客观存在的事物的词或短语，比如人名、地名、机构名等。其次，我们认识到新闻文档对特定事件进行报道大都是围绕特定命名实体为核心展开的，具体来说：命名实体是事件报道的重要元素，而事件报道的方式一般为描述这些命名实体的特征、属性；或描述这些命名实体的行为动作；或几个参与到该事件的命名实体之间的关系。因此本文后面对事件发现的工作很重要的一部分是以新闻文档中出现的命名实体为主要研究对象展开的。2. 事件发现研究工作现状与问题事件发现最开始是NIST主持的TDT（Topic Detection and Tracking）评测工作，这包括新事件发现（new event detection），主题发现（topic detection）和回顾式事件发现（retrospective event detection）等几个子任务7, 10, 11。其主要任务目标是分析来自不同信息源的新闻文档，将描述同一事件（主题）的文档合并在一起，下文中我们的工作和“新事件发现”任务更为相关。在早期的相关工作中，较有影响力的是7，其中所处理的数据为TDT-2，其中新闻文档的来源是传统的报纸媒体。该工作分别提出了两种不同的事件发现方法：一种是是用增量TFIDF模型来刻画新闻文档，事件发现则转化为一个增量聚类的问题10, 11, 12，即每篇文档按照其发表时间顺序形成一个文档流，并依照这个顺序以cosine为框架来计算每个新闻文档与现有的事件集合相似度，并以此来判断每个文档所属的事件类别；第二种方法则是采用基于GAC（Group Average Clustering）的层次聚类方法，在整个的新闻文档集合上构建一棵层次聚类树，最终通过时序分析来得到每个具体事件所对应的新闻文档集合。随着研究的进展，近年来事件发现的研究已不仅仅局限于对TDT测试集这样的小规模文本集的处理，越来越多的工作是面向来自Web中新闻网站的海量新闻网页的分析与挖掘。这其中很多工作是以7为基本框架进行了改进与增强：1中对来自不同新闻源的文档分别计算所涉及词语的TF和DF，并以此证实不同新闻源具有不同的语言特征，而利用这些特征能够提高事件发现的效果。13中首次提出为每个新闻文档只建立一个term vector对事件发现任务可能存在缺陷，它所引用的原因是不同新闻文档对同一事件的描述可能是不同的：它们可以从不同方面来描述同一事件；它们可以描述同一事件在不同阶段的进展等。这些都会使在采用单一term vector的模型下描述同一事件的新闻文档间相似度降低，因此13采用了定长滑动窗口对新闻文档进行分段（segmentation），并用各子段的term vector集合来表示一个新闻文档，并以此来解决新闻文档叙述方式、内容不同引起的事件发现效率的降低。类似的工作还有6, 14, 15, 16等。命名实体（named entity）-例如人名，地名，机构名等-在新闻文档中的作用与其在事件发现中的重要性也受到很多研究者的关注，6将新闻文档中出现的term分为命名实体与非命名实体两部分，其实验结果表明命名实体term所包含的信息量要明显高于非命名实体term。而3, 13对表示新闻文档的term vector中，命名实体对应的term weight根据命名实体的类别与其所在新闻文档的类别进行调整也比原始模型下对事件发现的精度有明显的提升。通过对以往事件发现工作的分析，我们认为该问题可以分为三个主要任务，它们分别是（1）文档的表示（representation），（2）新事件发现（detection）或已有事件的追踪（tracking）（也就是文档的分类，不过新事件发现不好算作分类），（3）新闻事件之间以及描述同一事件的不同文档的关系的分析（threading）。以形式化的表示来讲，第一个问题是将一组新闻文档的原始形式转换成为可以计算的文档集合；第二部分将D划分为若干子集，（类别事先给定还是不定？）其中为描述同一个所有新闻文档的集合；第三部分是分析集合中各元素间的关系，即构建一个文档关系树，关系树T中的顶点为所有描述同一事件的各新闻文档，T中的边为文档间的依存关系（什么是“依存关系”？）。其中一篇文档的表示可以分为三个子部分：这包括文档的文本内容，文档的时间信息和文档其它信息（例如：新闻源信息，作者信息，文本中命名实体信息等）。现有工作中一般只用到了前面两个部分，例如1, 2, 3, 5, 6, 7中利用单文档向量来表示文本，只是在相似度比较中会引入一个时间衰减因子。第三部分中包含的信息大都是新闻网页中特有的、且具有强烈区分度的内容，而这些内容在已有的事件发现工作中利用的并不多，例如3中特别添加文档中出现的实体列表作为文档表示的一部分。但这些工作利用的实体信息是独立的，没有和之前的文本内容、时间信息有任何关联。第二部分现有工作主要是利用传统的分类或聚类方法，其中具体方法中会采用添加时间衰减因子、随时间更新模型等方法使现有方法能考虑文档间的时间差异性1, 2, 3, 7；近年来也有采用文档生成模型来解决此问题的4。第三部分的工作一般是利用文档时间和文档内容两个特征来刻画文档间的依存关系，例如5, 6等。3. Web新闻文档文本的表示3.1. 已有文档表示模型比较在以往的事件发现工作中，新闻文档的表示形式可以分为下面几个类型：首先是使用单一的词空间向量模型（Vector Space Model）加文档时间的形式3, 6, 7, 10, 11, 12，这里我们介绍下7的文档表示模型和其在此模型下的文档档相似度计算方法。首先每篇文档中的正文被构建成单一的词汇向量（term vector），而文档时间方面，由于7处理的数据为TDT2来自新闻报纸，则以文档所在的报纸发行日期做为新闻文档的时间。在词汇向量的构造中，每一维度的大小即每个词对于该文档的权重基本采用传统IR领域中最常用的TFIDF模型。与原始TFIDF模型不同的是，由于文档有时间标签，因此原始公式中的DF（词汇的文档频率）会随时间不同而发生改变，DF的具体更新方法为：这里为词汇w截至到时刻t的DF，而表示包含词汇t且时间标签为t的文档个数。则词汇w在时间标签为t新闻文档p中的权重则表示为：近期一些工作中，对单一词空间向量模型中词汇权重的计算方法进行了改进3, 6。其主要思想是突出文档中对所描述事件关联度更大的词汇例如命名实体在词汇向量中的权重。这里对于命名实体e，其在文档p的词汇向量中的权重随着实体类型和文档主题的不同而被修改：这里是命名实体e对于文档p所属新闻主题的chi-square统计量，以表示该实体对于主题的相关度。在单一词汇向量模型下，计算一篇文档与一个新闻事件之间的相似度，即它们报道的事件是否相同是利用有时间衰减因子的文档向量的相似度来衡量的。其基本公式如下：例如7中使用词向量的cosine做文档相似度，而使用使用线性衰减函数来刻画事件相似度随时间的变化。其它工作也有使用Hellinger距离来衡量文档相似度，时间衰减函数也有使用log衰减函数的。第二大类文档表示模型为多词空间向量模型1, 5, 13, 14, 16，在此类工作中，新闻文档的表示不再使用单一的词汇空间，5中对不同的新闻来源分别建立词汇空间，并根据新闻文档的来源分别建立不同的词汇向量。1, 13, 14中则利用新闻文档中内容的不同将文档切分为若干文本子段（segmentation），将文档表示为多个文本子段的词汇向量集合。其中1利用定长的滑动窗口将文档划分为若干相互重叠的文本子段如下图：而两个新闻文档之间的相似度则取文档中文本子段相似度中最大值：事件发现工作中使用的第三类文档表示模型是概率模型4，在概率模型下新闻文档和新闻事件都被看成了一组词汇的概率分布，而文档间相似度、文档与事件的相似度利用这些概率分布之间的差异来衡量。4中利用了四类概率分布：人名，地名，关键字和时间。其中前三个分布是多项式分布而事件时间分布符合正态分布。各分布中的具体参数则通过EM算法在一组已标注的数据上训练的到。但是使用概率模型事件发现工作至今比较少，这其中有两个原因，其一是该方法只适合离线情况下（所有文档一开始就可全部获得）的事件发现，而现今主要工作都是针对在线形式（文档随着其时间标签而顺序到来）的事件发现；另一个重要原因是该方法需要在训练各概率分别的系数以前确定数据集中所有新闻事件的个数，而高效而准确的估计事件个数在很多场景下是不可能的。3.2. 多维特征的新闻文档表示模型事件发现工作首先需要对其处理的原始数据，即新闻文档转换成为某种可以计算的特定形式，不同的文档表示模型不仅影响整个系统的时间、空间效率，也对系统的精度等有明显的影响。最自然的是采用IR、IE研究中最常用也一般是很有效的词空间向量模型。上文中引用的很多相关工作都是基于该模型或其变种来进行的。但是我们认为将模型应用事件发现任务中有两点缺陷，而在前人的相关研究中并没有明确提出、分析与解决：第一， 词空间向量模型下，只考虑了新闻文档中正文文本的信息，现有的工作中文档其他部分的信息或者完全没有被利用到，或者没有显示的加入到文档表示模型中。第二， 现有使用词空间向量模型构造的文档向量，仍然采用IR研究领域中的TFIDF模式来计算向量各维度的权重。而1, 3, 5, 13中的研究显示：在文本挖掘，特别是事件发现相关工作中仅仅利用词汇的TFIDF来代表其在文本中出现的重要程度是不合适的，有些特殊的词汇（例如命名实体）应该在事件发现任务中得到更高的重视。相应的我们通过对Web中新闻文档的构成部分和新闻文本的叙述方式的分析，我们有两点基本认识：第一， Web新闻文档中，与其所报道事件内容相关的不止是新闻报道的正文。其他文档特征（网页特征），例如：文档标题（title），文档发布时间，文档中用户评论，网页URL，网页间链接关系等，都是与报道事件紧密相关的，如果文档表示模型中能有效的整合这些信息应该能提高事件发现任务的效果。第二， 即使对新闻文档中的正文文本，我们认为其中对所报道事件的信息密度也是不同的。正如我们前面分析的，新闻报道一般是围绕与事件相关的实体展开的，因此文本中出现的命名实体应比其它term更加重要；更进一步在这些命名实体周围的描述实体信息的上下文也比其它文本更重要。一个有效的文档表示模型应该能体现出这种信息表述的不平衡性而我们经过对网络中的新闻文档分析和阅读最近一些相关文献认为有下列几点应该加入到文档的：首先新闻文档描述事件的发生时间应该作为事件发现过程中的一个重要特征；第二新闻文档中某些特定的词汇命名实体，例如人名、地名、机构名等应该被特别关注；第三大部分新闻文档在内容上可以分为几个段落，而不同段落的内容可能具有很大差异，例如文档前部段落是描述新闻事件的背景，而后部段落则是描述事件的最新进展。综合考虑上面讨论，我们认为下面几个基本特征应该包含在文档表示模型中：第一， 新闻文档中报道的事件发生时间第二， 新闻文档中的命名实体，例如人名、地名、机构名等第三， 新闻文档中描述实体属性、行为、关系等的实体上下文。 第四， 新闻文档中其余与其所报道事件相关的信息。3.3. 时间特征这就引入了如下几个问题，以及我们的解决方案：如何有效来提取新闻文档描述事件的发生时间。这个问题在早期的事件发现工作7, 10, 14中并没有被重视，主要是因为当时使用的数据集例如TDT2-TDT5都是采用新闻报纸等数据源，其文档时间可以很容易的获得。而我们处理的数据来自互联网，即新闻网页。首先我们来讨论一下对新闻文档我们能够获取哪些与其有关的时间特征：第一是新闻文档的抓取时间，即该网页第一次被我们发现的时间；第二是新闻文档的最后修改时间，该时间可以通过网页文件属性或者http header来提取；第三是新闻网页的发布时间，该时间是新闻发布源发射出该文档的事件，最后就是文档中事件发生的时间。虽然我们是可以分析文档内容来提取事件发生时间，但这样做有两个问题：一是一篇新闻文档中可能包含多个时间关键字，它们可能是之前事件内容发生时间，也可能是未来可能发生内容的时间，；第二在文本内容中的时间一般是使用相对时间词，例如“昨天”，“本月17号”等。考虑到事件提取的精度与效率，我们转而采取使用新闻文档的“发表时间”（即前述T3）来代替新闻事件的发生时间，由于新闻内容的时效性需求这个发表时间与事件发生时间是吻合的，而另一方面新闻文档中有若干特征使我们能够快速、准确的提取文档发表时间。具体提取文档发表时间的做法是：首先我们分析文档所在网页的URL，因为URL中通常包含文档发表日期的年、月、日，例如一个常见的新闻网页URL：“1. 时间段开始为200*2. 其后的一个字节以内包含数字字符3. 各段数字字符的范围为01-12、01-31另外新闻文档一般会在文档标题下列出该新闻的一些重要信息：新闻发布时间、新闻来源、新闻点击率等，例如上面例子网页中该信息内容为：“ 2008年08月25日16:19 新华网”，而这样的文本块与周围文本在位置、字体、字号等有明显不同，我们使用一种基于VIPS的方法对网页文本分块以发现这个新闻标题下的新闻信息块，同样利用类似从URL中提取时间的规则匹配方法来提取信息块中的新闻发布时间。如果以上两种方法提取的时间有差别，我们使用其中较晚的时间作为最终的新闻发布时间。这种方法提取的时间虽然是新闻网页的“发表时间”，但是由于互联网中新闻事件报道的时效性，文档“发表时间”与文档报道的事件“发生时间”的差距应该会很小，在后面实验中使用的“北京2008奥运”数据中，平均的文档“发表时间”与文档报道的事件“发生时间”仅差0.31天，而其中报道的事件平均持续时间为1.26天。因此我们认为利用文档的“发表时间”作为新闻文档的时间标签是可以接受的。3.4. 命名实体特征如何在新闻文档中发现我们感兴趣类型的命名实体。对于中文数据集这个问题我使用了姚从磊的工作8，其基本方法是使用DIPRE方法，通过少量的“实体、属性”对来迭代的获取包含实体的文本模板，并通过这些模板来识别文档集中的实体。在后面的实验中我主要关注人物名、机构名、地点名、体育竞赛名称等几类实体。而对于英文文档，我们使用了Stanford大学开发的NLP包中的命名实体识别器32，它使用CRF模型来识别命名实体。3.5. 文本特征6, 14, 15, 16，3, 13, 14分别提出了对新闻文档中文本的表示应该采用分段的方法，已经突出文本中命名实体的作用。而我们在前面对新闻文档中文本叙述的假设是：新闻报道是围绕着参与到事件的命名实体来展开叙述的。因此我们对新闻文档正文的表示的基本想法是，以命名实体为核心，将文档正文切分为若干描述命名实体信息的文本子段，以这些文本子段来表示文档正文。因此我们将面临着以实体为核心的文档分段和文档子段表示的两个基本问题。3.5.1. 文档分段首先我们来分析如何对新闻文档进行分段表示。以往的工作中有些使用新闻内容的自然段3，有些使用定长的滑动窗口1来指导对文档的分段。我们在实际中觉得这两种方法都有些问题：按自然段的划分方法粒度过大，按定长文本窗口的方法则缺乏了内容相容度的考虑，可能将不同内容的文本分到同一段落中。另外我们在之前基于文本中共现的实体关系发现工作中9注意到在文档中命名实体、命名实体对周围的文本包含的信息量更高，通常其内容描述了新闻事件的重要信息。因此我们使用命名实体来帮助指导文档的分段，提取文档中的命名实体周围的文本组成的文本片段集合来代表该文档。我们提出的第一种文档分段方式是以句子为单位的滑动窗口方法，其具体处理流程如下：1.提取所有包含我们关注类型命名实体的句子，构成集合，中为一个包含至少一个特定类型的命名实体。2. 对上述集合S中每一个，从其中第一个出现的命名实体向前扩展至多个字节，从其中最后一个出现的命名实体向后扩展至多个字节，并且保证扩展后的文本片段中不超过t个句子。我们通过实验得到，时候效果最好。扩展后的文本片段构成集合。上面的分段方法并没有考虑子段间，段内文字与段外文字的相似度。而我们之前的假设要求我们分段后，各子段为描述子段内出现的命名实体的信息，这样分段后应该会造成子段内的文本相似度大于子段间的文本相似度。因此我们采用在文档摘要中提出的TextTilling算法来帮助确定子段划分位置，其核心思想是通过句子间相关度的下降坡度识别子话题的边界首先，TextTilling将报道划分为有序排列的句子集，每个句子采用向量空间模型进行描述。然后在每两个句子之间设置子话题的候选边界，假设某一候选边界bi位于句子si和si+1之间，则两句相关度的下降坡度计算如下： (1)其中为候选处的下降坡度；表示句子间的相关度，如果下降坡度高于阈值，则被确定为一文本子段的边界。在此基础上，新闻文档的正文被划分为若干不同文本子段阈值的计算如式（），n为报道内候选边界的总数；S为所有候选边界下降坡度的均值。 (2)3.5.2. 子段表示模型在传统的分类算法中，一般使用TFIDF方式来计算待分类文档向量中各维度的权重，而在我们的分段文档模型下，文档被表示成一组文本子段的集合，每个文本子段的长度都很短，因此造成子段文本向量的稀疏度很大，这也影响了文本段比较的精确性。因此在词向量的词频估算上，我们使用PLSI（Probabilistic Latent Semantic Indexing）这样一个概率模型。PLSI模型认为文档中是由若干隐含的子主题模型生成的，这点与我们分析得到新闻文档中包含了若干相对独立的子主题是相一致的。下面的描述中我们使用d来代表文档，w表示词汇，而用z来表示一个隐含主题。在PLSI模型下文档d中出现词汇w可以分为独立的三个步骤，首先是以概率P(d)选择一个文档d；其次是以概率P(z|d)任选一个隐含主题z；最后是以概率P(w|z)来选取词汇w，那么以数学形式表达出来就是： （3）由于引入了隐含主题z来联系文档d与文档中出现的词汇w，因此在PLSI模型中d与w是相对于隐含主题z是条件独立的： （4）PLSI模型中文档向量词频的估算是利用在文档d出现的条件下词汇w出现的条件概率 ，而通过（1）式引入隐含主题z，则词频估计为 （5）因此我们需要确定隐含主题z的个数和 、 这两个参数，其中隐含主题z的个数我们通过使用实验选择效果最好的一个，而另两个参数的获取我们通过EM方法从一个数据集中训练得到 和 。具体的过程是，首先对 和 给定一个初始值，我们这里的初始值分别设为1/|W|和1/|Z|，即保证各概率相同而且全概率为1。E步骤为： （6）这一步可以通过（1）和贝叶斯公式获得。而M步骤中，通过在训练集中统计得到的文档d中词汇w的出现频率f(w,d)，我们对 和 的估计为： （7） （8）这其中我们可以把 看成通过训练集对 的一个估计，通过全概率公式和条件概率的定义可以得到上面二式。但是以上的方法只能以离线的方式来处理一批新闻文档，而我们之前的方法是以在线模式来进行的。也就是说每隔一段时间会有一批新的文档到来，相应的文档集合、词汇集合都会有新的元素加入。因此我们需要在新文档到来后重新计算上面提到的模型的两个参数。这样一种简单的方法是对新的文档集合、词汇集合利用上面提到的EM过程重新计算，这样的方法会造成每次都要重复一次耗时的训练过程，而实际每次加入的新文档和新的词汇并不是很多，因此原有以计算好的参数的变化应该很小，应不需要有改变；而由于加入了一些新的词汇所以需要重新计算。因此我们只需要计算和，初始值的设置中都被设为1/|Z|， 被设为1/|W|，而的设置保持与前次的训练值比例相同，并且使得全概率为1。在E步骤中： （9） （10）而在M步骤中： （11） （12） 最终得到 （13）3.5.3. 子段排序对于报道每个事件的新闻文档的文本，我们将其划分为若干子文本段。在文本特征的比较中，我们将新来文档也划分文子文本段，比较这些子文本段的相似度并取相似度最大的k个作为新来文档与已知事件（文档）的文本特征相似度。进一步的对子文本段的观察、分析，我们发现有些子段或其相似内容在描述不同的事件的文档中都会出现例如在“北京2008奥运”主题数据集中有些子段描述的是奥运背景信息，如果与这样的子段相似我们认为并不重要；而另一方面，如果一个子段及其相似内容只在描述一个事件的文档中出现，那么与这样的子段相似则指示着新来文档很有可能是描述该事件的。基于这样的思路，我们为每个子段定义两个指标N（新颖性指标）和C（一般性指标）。对这两个指标的计算，我们对每个子段的两个指标都初始设为1，之后我们利用下面的递归式进行迭代计算： （14） （15）其中和分别代表在第t次迭代中，第i个事件中第j个子段的“新颖性指标”和“一般性指标”，而和分别是间的相似度，但是为了保证迭代过程收敛，这里要求： （16） （17）在得到每个子段的新颖性指标N和一般性指标C后，我们使用一个二元score函数为每个子段计算出一个评分，在文本特征的比较中，我们取新来文档子段与评分前k的子段比较的相似度作为文本相似度特征。现有我们考虑使用做初步的实验来验证该方法的效果。最终我们的方法为每篇新闻文档D提取的特征有：文档的发表时间T、文档中各类关键类型命名实体列表和命名实体周围的文本子段向量的有序列表和每个文本子段的排序分数集合。这里Ei是在文档D中出现的第i种类型命名实体列表，是一个文本子段i的词向量，是文本子段i的排序得分。4. 新闻文档的分类与新事件的发现为了计算新来文档与已分类文档的相似度，我们需要一种方法能够综合的考虑前文文档表示部分中提到的文档的各项特征，这包括文档时间、文档中实体集合，文档中文本片段集合等。因此我们提出一种基于SVM的方法来整合新闻文档不同维度的信息来衡量新旧文档间的相似度。然后将文档相似度与一个固定阈值比较，如果其小于该阈值则新来文档代表一个新的事件，否则将该文档分到与其相似度最大的文档所属的事件类别中。设待分类文档Doc1，而一篇已分类的文档为Doc2，下面介绍文档各特征差差异度的计算方法：1文档时间相似度：首先我们定义概念“事件时间跨度”：事件，不妨设其所有新闻文档的发布时间满足，则事件Event的时间跨度即为，。那么设Doc1的发布时间为T1，Doc2的发布时间为T2，另外Doc2所在的事件的时间跨度为，则Doc1，Doc2的时间相似度是。2文档中命名实体集合相似度：设Doc1中出现的命名实体集合为EL1，Doc2中命名实体列表为EL2，它们的差异度可以利用下面四个方法来计算：Dice coefficient： (18)Jaccard coefficient： (19)overlap coefficient： (20)Cosine： (21)则整体的实体计划相似度为这四个维度组成的向量。 (22)3文档片段相似度：设Doc1的文本片段向量集合，Doc2的文本片段向量集合，我们取文本片段间内积最大的前k个，这里面k经过实验取7。其具体公式为： (23) 基于前面三类特征，我们为构造了其相似度向量，利用半人工标注的训练集，我们利用同一个事件内的文档对作为正例，而利用不同事件之间的文本对作为反例来训练一个SVM分类器。之后我们利用一个sigmoid函数17来将转换为Doc1与Doc2相似度值。最后将Doc1与所有已分类文档计算该相似度。将与新事件阈值比较，如果其大于阈值则Doc1属于所在的事件，如果其小于阈值则Doc1为一个新的事件类别。5. 评测和实验结果5.1. 实验数据实验数据分两个部分，第一部分为中文数据来自我们去年7月-8月抓取的一批以北京奥运会为主题的新闻网页，其时间跨度为35天，抓取网页的来源有43个，其可以分为三大类：第一是国内几个主要新闻门户网站：新浪、搜狐、新华网、等。第二类是国内各省级行政区划的官方新闻门户：千龙网（北京）、（湖南）、（云南）等。第三是北京奥运会专门网站的新闻发布板块：、等。在这批数据上，我们抽取出其中8月1日-8月7日这7天的数据，利用聚类+人工判断的方式提取了561篇新闻文档，并将其标注到37个事件类别中。我们取其中前3天的397篇新闻文档作为训练集，以后4天的164篇新闻文档作为测试集。第二部分实验数据为英文部分，我们通过Google News Archive收集了2008年有关HP公司的新闻数据。具体收集方法是以“Hewlett-Packard”作为搜索词，投入到Google News Archive的搜索引擎18中，并设置时间区间为2008年1月1日-2008年12月31日。其返回的结果格式为一个新闻事件列表，每个表项包括新闻的title，第一篇报道的时间，新闻摘要，和一个包含相关报道的新闻文档URL的列表。我们抽取了其中至少包含15篇报道的事件，并抓取了报道这些事件的新闻文档，这样整个数据集包括2031篇新闻文档，其中共有67个不同的事件。5.2. 验证性试验本文中的一个基本假设是，新闻报道是围绕着参与到该新闻的命名实体进行叙述的，因此新闻文档中出现的命名实体、以及其周围描述这些实体信息的实体上下文要比新闻文档其它部分更与其所报道的事件相关（在这个意义上，其他部分可以文档“发表时间”与文档报道的事件“发生时间”看成是关于事件描述的“噪音”）。为了验证这个假设，我们做了如下两个实验：第一个实验中，我们分别对“北京2008奥运”数据中处于相同事件内和处于不同事件之间的的新闻文档对计算其文本相似度，这里我们利用全文相似度与实体上下文相似度两种方法计算。图1和图2中横轴为文档对的全文文本相似度而纵轴是其中实体上下文的文本相似度，实验结果显示在报道同一事件的文档对之间，实体上下文的相似度要大于全文文本5图表1 相同事件内文档两种相似度比较全文文本相似度 v.s. 实体上下文相似度图表2 不同事件内文档两种相似度比较全文文本相似度 v.s. 实体上下文相似度第二个实验中，我们将两类文本视为待分类数据的两种特征，进一步使用chi-square统计量来衡量两类文本对事件类别的相关度。我们以数据一中的事件为分类类别，以所有新闻文档作为分类问题中已标注数据集，计算了全文文本和实体上下文文本计算其平均的chi-square统计量来衡量两类文本特征对事件类别的相关度，对任意一个事件类别E其contingence table为：ABCD其chi-square统计量为 (24)其中, C=1-A, D=1-BN是属于事件类别E中新闻文档的个数，M是不属于事件类别E的文档个数。分别对应于在全文文本下两文档的相似度和实体上下文文本下两文档的相似度。chi-square统计量全文文本2.41实体上下文1.06图表3 全文文本与实体上下文对事件类别的相关度比较5.3. 对比系统介绍在下面的实验中我们比较了前文中提出的多特征文档表示方式与基于SVM的文档相似比较方法，下文中我们记其为Multi-Feature。实验对比的方法有下面几种：1 Incremental IDF：该方法7中文档被表示成单一的词向量与发布时间的二元组，词向量中term weighting采用BM25，但是不同的是其中IDF的计算考虑到时间局部性。2 Fix-Window Segmentation：新闻文档以定长的滑动窗口划分为若干子段的词向量集合来表示1。3 Entity Reweighing：文档表示的词向量表示中，命名实体根据其类型和所在文档描述的事件类型而重新计算权值3。5.4. 评测标准在早期的TDT2到TDT5评测集中，事件发现的评测一般使用曲线31作为评测标准，而在我们的工作中并没有使用，主要原因是考虑其中的惩罚系数在非TDT数据的数据集上难以准确估计3, 4, 5, 16, 26。我们使用传统分类评测中precision, recall和F-measure30。我们假设其具体计算公式如下： (25) (26) (27) (28) (29) (30) 这里为事件i中属于类别j的文档个数，为属于事件i的文档个数，而为属于类别j的文档个数。为了方便在整个数据集上比较不同事件发现方法的效果，我们继续引入平均的precision, recall和F-measure的定义： (31) (32) (33)5.5. 实验数据及分析图表4 中文新闻数据上不同事件发现方法效果比较图表5 英文新闻数据上不同事件发现方法效果比较实验结果表明使用全部实体列表、发表时间特征的方法要明显好于另外三种方法。其中我们的Multi-Feature方法在中、英文数据集上分别生成了29个和58个事件类别。Fix-Windows生成了15个中文事件类别和38个英文事件类别，这在四种方法中是生成事件类别最少的，因此Fix-Windows在我们的实验中倾向于将较小的事件类别合并到大的事件类别中。这主要是因为这两个数据集都是围绕一个特定的主题（北京奥运与HP公司），因此大部分文档中都包含文本子段描述一些这些主题的背景信息，而Fix-Windows方法使用子段间最大相似度造成了该方法倾向于生成比较大的事件类别。相应的我们提出的方法中，文档子段之间除了相似度之外还有子段排名，而上述的背景子段因为在大量报道不同事件的文档中出现则其排名较低，因此不会出现Fix-Windows方法中出现的错误。I-IDF方法的效果明显差于其它三种方法，我们认为这主要是因为I-IDF方法对时间特征的使用，它通过词汇DF随时间的变化来显示事件的变迁，而中文数据集中一共只跨越了7天，而平均每个事件延续时间为1.53天，英文数据集虽然跨越了1年，但是其中事件的延续时间也只有7.29天。而这样短的时间跨度使得DF变化很小，因此I-IDF的效果最差。而我们的方法中，时间作为SVM相似度计算中的一个特征，随着训练集的不同，我们的方法能够动态的适应不同时间跨度的事件类别。而且实验结果也显示文档中的命名实体的重要性和对不同事件的区分度。在两个数据集上，四种方法的效果也不尽相同。其中I-IDF方法在中文和英文数据集上的效果都是最差的，这种情况已经在前面的验证实验中有所体现。而在Fix-Windows在英文数据集上要好于其在中文数据集的效果，其原因是英文数据集的事件跨度较长，其中事件的时间跨度较大以及其事件进展造成即使报道相同事件的新闻文档之间的文本相似度也较低，同时该方法也因此得到了最好的精度。而使用分段比较文本的方法则能得到更好的效果。另一方面，Entity-Reweighting的方法则在中文数据集上的效果更好，通过分析其原因是中文数据集中每篇新闻文档中包含的命名实体个数要多于英文数据集，而英文数据集中报道不同事件的文档也倾向于包含相同的实体，其中覆盖率超过50%的实体即有7个。总体而言综合使用分段和实体上下文的方法取得了最好的效果。下面是两个参数选择的使用结果。图表6 文档分段参数p、t的选择图表7 中文数据集上文档特征比较的参数k的选择图表8 英文数据集上文档特征比较的参数k的选择在下面的实验中测试了我们利用的多种特征对事件发现效率的不同贡献，我们的实验中特征被分为实体特征与文档特征和时间特征三类，我们分别下面三种特征类别组合：“实体+时间”特征，“文档+时间”特征和“实体+文档+时间”特征。下面的图表为三类特征组合对事件发现的影响。图表10. 中文数据集上不同特征组合对事件发现的影响图表11. 英文数据集上不同特征组合对事件发现的影响实验结果比较有趣，只利用“实体+时间”特征的方法甚至在recall上要高于使用所有特征的方法。这里面的原因应该是在两个数据集中的较大的事件（相关文档较多的事件）大都包含一些有很强指向性的命名实体（实体与事件的相关度很高），因此“实体+时间”方法能对这类事件的识别效果更好而使最终结果得到更高的recall。而另一点需要注意的是，只使用“文档+时间”特征的方法在两个数据集上都要比使用所有特征的方法要差20%以上，这样再次证明的了命名实体在事件识别中所起的重要性和必要性。接下来我们比较下不同词向量构造方法，这里有四类方法：TF-IDF，Offline-PLSI，Online-PLSI-1和Online-PLSI-2。这里面TF-IDF使用bm25公式来计算各词汇维度的权重，而后面三种方法使用3.5.2节中提到的PLSI来评估词汇对于文档的权重。而Offline-PLSI使用全部文档训练PLSI来为新来的文档计算词权重，Online-PLSI-1只使用某时刻新来的文档来训练PLSI模型，而Online-PLSI-2使用3.5.2节中的方法来增量的训练PLSI。实验结果显示使用PLSI模型的词权重计算要明显好于使用TFIDF的方法，这样的结果是因为文档子段的长度比一般文档要短得多，利用PLSI来平滑词权重是很有必要的。而在时间开销上3.5.2节中使用的在线方法更新PLSI基本与离线方法相同。图表12. 中文数据集上不同词权重计算方法的效果图表13 英文数据集上不同词权重计算方法的效果图表14 不同词权重方法的时间开销最后我们来测试下不同文本分段方法带来的结果。这里我们比较三种不同的分段方法，首先是直接使用新闻文档的自然段来切分，第二种使用1的定长滑动窗口来切分包含命名实体的文本，而第三种使用Texttilling算法来确定文本子段的分割点。这三种方法分别被记做Paragraph、Fix-Window和Texttilling。从表格1和表格2中列出了不同分段方法产生的子段基本信息，这里使用自然段的方法生成的子段平均长度最大，而产生的子段个数最少；定长滑动窗口的方法则产生最多的文本子段。图表16和图表17显示了三种方法对事件发现的影响：其中使用了Texttilling分段算法的效果在精度和召回率上都好于另两种方法。而后两种方法由于都是围绕命名实体进行分段，因此其精度要好于直接使用自然段的方法。另外直接使用自然段的分段方法在事件的召回率上比较高，其原因应该是这两个测试数据集中的内容基本是围绕同一个主题（中文数据集是有关08奥运的新闻文档，英文数据集是有关HP公司08年的新闻文档），因此在这些新闻文档的开始或结束段落中都包含比较相似的文本内容（例如奥运会的基本信息等），而直接利用自然段的方法划分的文本子段明显少于后两种方法，因此该方法倾向于得到较大的事件类别，这样反而提高了该方法的召回率。文本子段长度文本子段个数Paragraph212.76.5FIX-Window5021.5Texttilling79.115.2表格1 中文数据中文本分段信息文本子段长度文本子段个数Paragraph154.59.2FIX-Window5018.3Texttilling92.312.7表格2 英文数据中文本分段信息图表16 中文数据集上不同分段方法对事件发现的影响图表17 英文数据集上不同分段方法对事件发现的影响6. 总结和未来工作以上的工作基本完成了由一组新闻文档聚合成为事件的流程，这其中的主要贡献是提出了一种新的新闻文档表示模型，该模型考虑了文档的时间、文档中的实体和文本片段等多种与事件内容相关的特征；另一方面因为文档表示的改变，我们使用了SVM来综合多个维度进行文档间相似度计算。通过实验看到该方法的效果是高于传统的单文档向量的方法和只使用文本片段的方法。但应该注意在和另一种使用部分文档特征的方法 - 只使用实体列表 - 比较中，我们的方法提高并不很明显。这也提示我们的文档表示模型在文本片段特征上还有缺陷。另外文档表示模型的另两个特征类别：文档描述事件的时间和文档中的实体列表也有可以细化的空间，文档时间现在是利用新闻文档的一些特点通过提取URL和新闻文档内容信息块中的文档发布时间来进行的，而这些特点并不是所有新闻文档都适用，而且这种做法也不适于其它例如blog、论坛等信息源的文档；文档中的实体方面，我们现有做法并不区分实体的类型，而在测试集构造以及实验过程中我们发现在不同事件中不同类型实体的重要性是不同的，如果能够自动学习获取这方面的知识并在文档相似度计算考虑这方面的因素也应能提高系统整体精度。未来的工作首先是修改文档表示模型中文本片段的提取与表示，一方面在新闻文档特征中，我们认为与新闻事件紧密相关的还有文档标题，相关链接，用户评价等。在实验中，文档标题特征显示对文档来源有比较强的依赖性，因此不能直接作为独立的特征加入现有工作框架；而后两种特征的提取、筛选难度比较大，进一步的工作还在考虑中第二对于文档分类后的进一步分析，我们观察到描述同一事件的文档间有两种不同的关系：转载和事件进展。前者表示两文档的内容相似度很高，甚至全文完全雷同，这主要反映了网络新闻媒体间的转载行为；而事件发展关系则是表示两篇文档描述同一个事件的不同侧面内容、不同观点的评论或者是事件的发展过程记录。显然后者的重要性要高于前一种关系。因此我们希望能够发现、区分这样的关系，并根据不同类型的关系构造同一事件内的文档间的关系结构，以此来揭示事件在网络媒体中的报道轨迹。第三我们提出的多特征文档表示模型与在此之上的基于SVM的文档相似度综合方法，作为一个信息抽取的框架并不一定局限于事件发现这一类挖掘工作。而对于其他信息挖掘任务，如何能有效的发现、评估文档特征的有用性、有效性是一个需要明确解决的问题。另外还有几个工作是我们现在还没有仔细考虑的。其一是新闻事件的表示，如何能够提取有效的关键字、或使用其他方法来表示一个特定的新闻事件。在此问题上HP Lab做过有关研究，希望能够与他们进行有效的交流讨论。另外在事件层次上我们希望能够监控或筛选与一个特定机构相关的新闻事件，这需要获得能够描述、代表特定机构的一些特征，例如机构名称、类别、相关人员、地点等重要实体列表、机构相关的事件训练集等。7. 参考文献1 T. Brants, F. Chen, and A. Farahat. A system for new event detection. In Proceedings of ACM SIGIR. 2003.2 J. P. Callan, W. B. Croft, and S. M. Harding. The INQUERY Retrieval System. In Proceedings of DEXA-92, 3rd International Conference on Database and Expert Systems Applications, 1992, 78-83. 3 K. Zhang, J. Li, and G. Wu. New Event Detection Based on Indexing-tree and Named Entity. In Proceedings of the 30th Annual International ACM SIGIR. 2007.4 Z. Li, B. Wang, M. Li, and W.-Y. Ma. A probabilistic model for retrospective news event detection. In Proceedings of the 28th Annual International ACM SIGIR. 2005.5 R. Nallapati, A. Feng, F. Peng, and J. Allan. Event threading within news topics. In Proceedings of the Thirteenth ACM CIKM. 2004.6 K. Giridhar and J. Allan. Text Classification and Named Entities for New Event Detection. In Proceedings of the 27th Annual International ACM SIGIR Conference, 2004.7 Yang, Y., Pierce, T., and Carbonell, J. A Study on Retrospective and On-Line Event Detection, in Proceedings of the 21st Annual International ACM SIGIR. 1998. 8 Conglei Yao. Research on the extraction of Web entities and entity activities. PhD thesis. 20089 Nan DI. web content-based entity relation analysis. PhD general examination report. 2007.10 J. Allan, J. Carbonell, G. Doddington, J. Yamron, and Y. Yang. Topic detection and tracking pilot study: Final report. In Proc. DARPA Broadcast News Transcription and Understanding Workshop, 1998.11 J. Allan, R. Papka, and V. Lavrenko. On-line new event detection and tracking. In Proc. of SIGIR98, pages 3745, Melbourne, Australia, 1998. ACM.12 Y. Yang, J. Carbonell, R. Brown, T. Pierce, B.T. Archibald, and X. Liu. Learning Approaches for Detecting and Tracking News Events. In IEEE Intelligent Systems Special Issue on Applications of Intelligent Information Retrieval, volume 14 (4), 1999, 3243.13 G. Kumaran and J. Allan. Te
展开阅读全文