面向大规模数据的在线新事件检测

蔡偃武,高大启,阮 彤,蒋锐权

(1.华东理工大学计算机科学与工程系,上海200237;2.上海证券交易所技术开发部,上海200120)

面向大规模数据的在线新事件检测

蔡偃武1,高大启1,阮 彤1,蒋锐权2

(1.华东理工大学计算机科学与工程系,上海200237;2.上海证券交易所技术开发部,上海200120)

通过分析基于新闻要素的在线新事件检测算法的时间消耗,提出一种面向大规模数据环境的在线新事件检测算法。该算法利用基于倒排索引的高效相似报道搜索机制,有效减少单路径聚类算法中的相似度比较次数。通过对报道预处理、报道与事件比较以及索引搜索这3个过程的并行化,提高算法在多机环境下的运行效率和可伸缩性。实验结果表明,该算法在不影响漏检率和误检率的基础上,提高了新事件检测的速度,并且在千万到亿级别的报道规模下,其吞吐量达到150条/s～200条/s。

新事件检测;单路径聚类;大规模数据;并行计算;倒排索引;MapReduce架构

1 概述

随着大数据时代的来临,如何解决互联网上的海量信息的过载问题,成为当前研究的一大热点。解决互联网信息过载的前提在于合理的组织信息,然后以一定的方式把信息提供给用户。解决信息过载的一种方式是使用基于关键词的信息检索,该方法预先将海量信息按关键词进行组织,用户在需要查询信息时,通过对指定关键词进行匹配获得相关信息。然而,基于关键词信息检索技术的局限性也非常明显,在许多情况下,用户难以用关键词精准地表达自己的信息查询意图。因此,这种信息检索方式越来越难以满足人们的需求。

信息获取的另一种方式是将信息以话题为主线来组织,然后通过话题来分类展现信息给用户。话题是指一个种子事件或活动以及与之直接相关的事件或活动[1],以话题为主线组织信息的关键问题在于如何快速高效地从海量信息中发现话题并且跟踪话题的发展。话题检测与追踪(Topic Detection and Tracking,TDT)技术是从新闻数据流中自动发现新话题并追踪已知话题发展动态的信息智能获取技术[2]。新事件检测(New Event Detection,NED)作为话题检测与追踪的一项重要子任务,其目标是从按时序顺序到来的新闻源中识别新闻话题中一个事件的第—篇报道[3]。事件是指发生在特定时间和特定地点的事情[4](如神舟十号飞船发射升空),而不是指一个广泛的概念(如中美关系)。总体而言,一个话题包含多个事件,事件则包含若干报道。NED的研究在现实中有广泛的应用,如信息源(电视、社交网络等)的自动监控、证券市场的分析、行业调研、个性化信息定制等。

通常影响NED性能的主要因素有3个:难以区分相似的事件,容易把属于相同事件的报道误报为不同事件,难以选择报道归并到事件的阈值和使用多维特征事件表示模型时各特征的权重系数。针对上述问题,文献[5]提出一种利用新闻要素构建表示模型的在线新事件检测算法:将新闻的地点、人物和内容3个特征提取形成三维向量表示报道和事件,并利用基于维基百科的简单语义相似度计算方式判别报道与事件的相似性,有效地解决了前2个难点;同时使用基于SVM的分类算法训练学习报道与事件的判别阈值以及各特征的系数,利用机器学习方式有效地解决了阈值和系数的选择问题。文献[6]针对突发事件热点话题识别系统提出一种正文裁剪方法和特征权重计算的改进模型,该模型具有更好的执行效率和适应性更强的文本表示能力。文献[7]通过引入话题种子来改进面向互联网话题识别的单路径聚类算法,在降低漏检率和误检率的同时提高了聚类速度。文献[8]提出集合局部特征和全局特征的单路径聚类算法,在网上论坛的话题识别中获得了较好的性能。文献[9]提出了用词对来表示文本的方法,这种改进的向量空间模型优化了对报道文本的表示模型。文献[10]提出使用时间窗口策略的在线新事件检测方法,该方法提升了新事件检测的速度。然而,现有NED算法在投入到工程应用中使用时,算法的效率问题成为主要瓶颈,主要原因为:与所有的基于单路径的NED算法一样,其整个过程为一串行的过程,先进行报道的预处理,然后每个到来的报道再与现有的事件逐个比较,因此,在最糟糕的(也是大多数)情形下,其时间复杂度为O(n2),其中,n为报道数目。

本文在现有基于新闻要素的NED算法基础上,着重解决算法的速度问题,进而提出有效的解决方案,并实现高速NED算法。

2 基于新闻要素的在线NED算法

2.1 报道和事件的表示模型

报道和事件的表示模型具体如下:

(1)报道预处理

在进行NED之前首先要对报道进行预处理,预处理步骤主要包括去重、分词、词性标注、除去停用词。本文研究中的中文分词和词性标注工具采用的是北京理工大学张华平博士的NLPIR工具包[11]。

(2)新闻报道和事件的表示模型

从事件定义可以得知时间和地点为事件的2个主要特征,其实事件的另外两大要素也同样重要,即事件相关的人物和事件的主要内容。同样,对于一篇新闻报道,也可以使用这四大要素更精确地表示。传统报道表示方法通常采用单一的文本向量表示,这种表示向量的维度一般比较高,使得计算变得过于复杂,又难以准确区分相似事件。因此,本文采用文献[5]提出的一种基于新闻要素的报道与事件表示模型,它选用了报道的时间、人物、地点和普通内容4个部分组成表示模型,其中,前3个部分采用向量空间模型表示;普通内容是指具有实际意义的普通名词和动词。对于新闻报道来讲“时间”是一个孤立的值,而对于事件来讲“时间”是由第一篇报道时间和最近一篇报道时间所组成的时间段。因此,新闻报道和事件可以用以下形式表示:

报道={主体,地点,普通内容,时间戳}

事件={主体,地点,普通内容,时间段}

(3)增量TF-IDF模型

TF-IDF模型是一种计算词权重的经典模型,在该模型中一个词在一个文档中的频率(TF)用从训练语料中生成的逆文档频率衡量。在测试过程中出现新词时,有2种解决方法:简单地忽略该新词或者设置该新词的文档频率为常数1。第1种方法会导致新词的权重为0,第2种方法会导致新词项获得过高的权重。为解决传统TF-IDF模型的不足,本文利用增量式TF-IDF计算词的权重,在增量TF-IDF中文档频率df(w)不是一个固定的常数而是随着时间点变化。在时刻t通过更新频率把一个新的测试文档集合Ct加入到模型中,如式(1)所示:

其中,dfCt表示词w在新加入的文档集合Ct中的文档频率,初始的文档频率df0(w)从一个训练集合生成。

在增量TF-IDF中没有忽略新词并且根据新词在新文档集合中的使用情况为其分配权重,由于新的事件经常引进新词,为新词分配适当的权重可以改善模型效果。

在增量TF-IDF中,词w在时刻t、文档d中的权重如式(2)所示:

其中,tf(d,w)表示词w在文档d中出现的次数;Nt表示在时刻t前采集到的报道总数。因此,一个文档d在时刻t可以利用式(3)表示,n表示文档d中相异的词语总数。

采用基于新闻要素的报道表示模型,则一篇新闻报道S可以表示如下:S→{N,P,C,t},其中,N表示人名和机构名;P表示地名;C表示具有实际意义的普通名词和动词;t表示报道的发布时间;N,P,C利用式(3)表示;事件E可以表示为E→{N,P,C, (te,t1)},tl表示事件E的最近一篇报道的时间,te表示E的第一篇报道的时间。

2.2 报道和事件相似度的计算

本文采用文献[12]的报道和事件相似度计算方法,将报道和事件分成4个互不相关的部分,每个部分采用不同的文本表示模型。要计算报道和事件的相似度首先要分别计算几个不同组成部分的相似度,包括地名部分的相似度、名称部分的相似度以及普通内容部分的相似度。通过这3个部分相似度的加权来表示报道S与事件E在t时刻的相似度,计算方法如式(4)所示:

其中,sim(S,E)表示报道和事件的相似度;sim(SP,EP),sim(SN,EN)和sim(SC,EC)分别表示报道和事件人名部分、地名部分及内容部分的相似度,这些相似度分别由式(5)所示的余弦相似度公式计算得到;w1,w2,w3分别表示各部分的权重。

2.3 新事件检测方法

新事件检测方法主要是判断报道和事件的相关性,而相关性是通过比较报道和事件的相似度与阈值的关系得出的,对于每个在t时刻接收到的报道S,式(6)的值是用于决定S是否是关于一个新事件的报道分数。

其中,t是报道S的发布时间,如果分数score(S)超过一定的阈值,则认为存在一个和报道S相似的事件,S归为一个旧事件;否则意味着没有与报道S相似的事件,S可以认为是新的事件。

目前绝大部分的在线新事件检测算法都是基于单路径聚类算法,本文采用此聚类方法,其算法具体过程如下:

(1)取报道流中一篇报道S,对其文本进行预处理,提取人名、地名和时间以构建S的表示模型。

(2)如果事件类库中尚不存在事件,则S作为第一篇报道,建立一个以S为中心的事件E,返回步骤(1)。

(3)如果事件类库中已有事件,则使用式(4)对所有事件Ei计算Ei与报道S的相似度sim(S,Ei),求最大的相似度MaxSim以及达到最大相似度时的事件E。

(4)比较MaxSim与相似度阈值θ的大小,如果MaxSim未达到阈值,则认为S属于新的事件,建立一个以S为第一报道的新事件类簇;如果MaxSim达到阈值,则认为报道S和事件E是相关,将S归入E中,并更新事件E。

(5)如果报道流中有未处理报道,返回步骤(1)继续处理。

本文采用基于新闻要素的新事件检测算法流程如图1所示。

图1 基于新闻要素的新事件检测算法的流程

3 改进的快速NED算法

3.1 现有算法的时间消耗分析

从图1可知,NED算法主要有3个步骤:预处理及转化成表示模型,报道与事件的相似度计算,阈值判别及归并到事件(报道达到合并到事件的阈值时)或创立事件(报道为一新事件时)。相对于前2个步骤,步骤3速度非常快,因为其操作次数为1次且操作过程非常快。对于步骤1,每篇报道仅需要处理1次,因此其速度主要由所采用的NLP分词、词性标注等工具的处理速度决定。步骤2为算法中时间消耗最多的步骤,主要原因在于对于每篇报道,其计算次数随报道数目成线性增长;而此步骤的总时间则随报道数目的平方增长。因此,当算法运用于大规模数据处理时,其处理吞吐量会迅速下降。本节接下来着重解决提高预处理和报道与事件的相似度计算这2个步骤的速度。

3.2 报道预处理的并行化

在实验环境下,报道通常依据严格的时间顺序放入到NED算法中。在现实应用中,尤其在大规模数据环境下,由于信息采集系统的工作原理决定了收集到的报道不可能完全符合时间的先后顺序。然而,本文基于的NED算法及其他大多数NED算法并不需要时间具备严格的顺序。

报道的预处理过程是独立的,因此,该步骤可以轻易地进行并行化,仅需要启用多个进行预处理的进程即可。而且并行化后的时间与并行进程的数目基本成反比。因此,当预处理步骤并行化后,理想情况下其时间可以忽略不计(只要有足够多的硬盘设施)。

3.3 使用索引机制减少报道比较次数的方法

在现有的NED算法中,任何一条新到来的报道均需要与之前的事件进行比较,导致算法的复杂度为报道数目的平方。在现实应用中,尤其在大规模数据情形下,这些比较绝大多数是无用的,比较得到的相似度很多都接近于0。既然如此,如果有一种机制,能把这些无效的比较预先进行过滤,将大大提高算法的效率。

在信息检索中,倒排索引机制是进行文档快速检索的常用方式。倒排索引[13]是一种可以记录文档或文档集中的单词或关键词在文档中出现位置信息的一种索引数据结构。这种索引方式是文档全文检索系统中最常使用的,它可以用于大规模的搜索引擎中。

通过分析报道与事件比较的计算方式,不难发现,比较的过程实质上就是一次查找最佳相似文档的过程。因此,可以很自然地把索引方式引入到NED算法中。在时刻t0,现有的事件作为已有的索引文档集合,而新到来的报道则作为搜索的目标,通过搜索即可找到与当前报道相似度最大的事件。倒排索引的效率是很高的,因此可大大提高算法的效率。在把倒排索引引入到NED算法中时,需要注意以下4点:

(1)本文使用多要素表示事件和报道,这些要素相当于倒排索引中的字段;

(2)并非所有的事件(报道)要素均可使用倒排索引:地点计算需要使用基于地理树的语义相似度计算,时间戳也有其特定的算法,因此使用倒排索引的仅为主体要素和普通内容要素;

(3)通过倒排索引得到的相似度值并不作为最终的相似度,因此,各要素的权重可依据经验值进行选取;

(4)通过倒排索引得到的值仅作为过滤NED算法中无效比较的参考值:对于某报道,最终选取的与其最相似的事件在倒排索引查找时必定也会得到较高的相似度。

引入倒排索引机制以过滤无效报道后,对于某报道,通常会选取相似度最大的特定数量(通过多次实验,本文选取值为20)的事件进行准确地计算,从中选取真正与当前报道最相似的事件,判断是否达到指定的阈值。

3.4 倒排索引设计与查找过程并行化

在NED中,事件和报道都是具备时效性的,报道与事件的相似度受它们之间的时间差距的影响非常大;因此,不能把所有的事件放入到一个倒排索引库中。使用多索引的另一原因是效率问题,在大规模数据下,多个索引对速度的优化也非常明显。本文采用的基本时间单位是天,因此,对于一篇报道,它与过去某一天内的所有报道的时间相似度因素是等同的。因此,本文采用以日期对索引库进行分布的办法,即同一日期的事件放到一个索引中。

在分开索引后,对于一篇报道,需要从有效时间范围内的所有索引库中进行查找;显然,此过程是可以并行进行的。多个索引查找完毕后,将结果合并排序,然后从中选取相似度值最大的一定数量的事件。

3.5 报道与事件比较过程的并行化

虽然整个NED过程是串行工作的,但对于一篇报道,它与现有报道的相似度计算是独立的,也就是说可以并行计算的。因此,对于经过倒排索引查找得到的特定数量的候选事件,并行化计算其真实相似度后,从结果中选取相似度值最大的事件与相应的阈值进行对比。这个过程可使用MapReduce框架实现,MapReduce框架的操作对象仅限于键值对＜key,value＞,其处理过程如式(7)所示:

在Map阶段,输入的键是新闻报道的URL,值是经过预处理后的新闻报道,Map函数在不同处理节点上对每个新闻报道在分布式索引库中进行搜索,Map输出结果的键不改变,但是值是作为索引结果的候选事件。通过Combine阶段将不同节点查找到的候选事件归到一起,由Reduce阶段的函数统一处理。在Reduce阶段,计算每个报道的全部候选事件与报道的相似度,找出具有最大相似度的事件并输出,输出键值对的键是报道的URL,值是事件及最大相似度。

4 实验结果与分析

4.1 评测语料

本文研究中的主要工作是对NED算法在速度上的改进,因此,本文需要使用大数据规模的语料。本文使用网页采集爬虫从互联网采集了从2013年6月份的中文新闻报道,总数目为20 474 078。由于在大规模数据下,难以由人工验证算法的结果,因此为了评估算法的其他性能,本文还采用了文献[5]中的语料作为评估语料。

4.2 评测标准

在对新事件检测算法测试结果分析时,通常采用由NIST为TDT建立的评测体系,该评测体系是在评测算法的误检率和漏检率基础上确立的。评测指标CDet由式(8)定义:

其中,CDet是性能损耗代价,综合了漏检率和误检率;CMiss是漏检率的代价系数;PMiss是漏检率的条件概率;Ptarget和Pnon-target是先验目标概率;CFA表示误检率代价系数;PFA表示误检率的条件概率。评价TDT系统性能时常采用(CDet)Norm,它是CDet的规范化表示,由式(9)定义:

虽然本文主要工作侧重于算法速度的改进而对于算法的漏检率及误报率方面并未在文献[5]的基础上作相应改进,但是在改进算法速度时,对其中的算法过程进行了调整,可能会影响算法的误报率和漏检率。因此,本文将以文献[5]中NED算法的结果作为对比评测标准,并同时使用其中的评测语料。

对于算法在速度性能上的改进,本文采用的是4.1节中所述的大规模数据,同样将与文献[5]中的算法进行对比。

4.3 结果分析

本文对新的NED算法的漏检率和误报率进行了评估,得到的漏检率-误报率曲线[3]如图2所示。由于SVM阈值法对算法参数进行了确定,因此得到并非曲线而是一个点。评测时,2种算法均使用手工阈值选取及使用SVM自动确定阈值的方式,而手工阈值均选用文献[5]中确定的最佳值。可以得到结论,不论是采用何种阈值的确定方式,本文算法的改进对于算法的漏检率和误报率的影响小,基本可以忽略。

图2 本文算法与文献[5]算法的漏检率-误报率对比

然后,评估算法速度方面的性能,分别使用本文算法及文献[5]算法在所选取的大规模数据集上运行。同时,为了评估算法时间与报道数目之间的关系,分别使用报道数目为10 000,100 000,1 000 000, 10 000 000以及所有的20 474 078,得到的时间消耗如表1所示(当算法消耗的时间大于100 h后,由于时间关系不能等待算法运行完毕)。由表1中可以得到以下结论:(1)本文算法的速度性能得到极大提高,尤其在大数据量时;(2)文献[5]算法的时间复杂度基本为报道数目的平方,而本文算法的时间复杂度与报道数目成线性关系;(3)使用并行化处理使算法速度进一步提升,在C0和C1 2种情况下,算法速度都比文献[5]快,A1同时使用了并行化预处理和并行化相似度比较,速度比C0和C1快。

表1为大规模数据集下各算法消耗的时间,其中,A0表示文献[5]中使用手工阈值的算法;A1表示本文算法使用手工阈值;B0表示文献[5]中使用SVM确定阈值的算法;B1表示本文算法使用SVM确定阈值;C0表示本文算法使用手工阈值但不用并行化预处理;C1表示本文算法手工阈值但不用并行化相似度比较。

本文对算法在处理大规模报道数据集的条件下进行可扩展性测试,实验选择报道库中的5 000 000篇报道,测试计算节点数分别为3,4,6,8, 12,16情况下算法的消耗时间,结果如图3所示。

图3 系统消耗时间与节点数量的关系

从结果中可以发现随着计算节点数的增加,会比较明显地降低处理相同数据量时所需的时间,因此本文算法具有较好的可扩展性,在实际应用中可以根据用户数据规模需求来配置计算节点数目,满足不同的用户需求。

5 结束语

在线新事件检测是从新闻报道流中识别出未知的事件。目前已有的自动在线新事件检测方法能够有效地检测新事件,但几乎均不适用于大规模数据环境下的在线新事件检测。大规模数据下的在线新事件检测需要算法具备极高的效率。为此,本文提出一种适用于大规模数据环境的在线新事件检测算法,该算法在基于新闻要素的新事件检测算法的基础上进行了3个方面的改进:(1)使用并行的方式进行新闻报道的预处理;(2)利用高速索引机制,减少单路径聚类算法中的比较次数;(3)使用MapReduce架构使聚类算法并行化。实验结果表明,该算法提高了新事件检测过程的速度,下一步将研究大规模数据下的热点话题发现技术。

[1] Allan J,CarbonellJ,Doddington G,etal.Topic Detection and Tracking Pilot Study:Final Report[C]// Proceedings of DARPA Broadcast News Transcription and Understanding Workshop.[S.l.]:Lansdowne Press,1998.

[2] Allan J,Papka R,Lavrenko V.On-line New Event Detection and Tracking[C]//Proceedings of the 21st AnnualInternationalACM SIGIR Conference on Research and Development in Information Retrieval. Amherst,USA:University of Massachusetts,1998:37-45.

[3] 洪 宇,张 宇,刘 挺.话题检测与跟踪的评测及研究综述[J].中文信息学报,2007,21(6):7l-85.

[4] Seo Y W,Sycara K.Text Clustering for Topic Detection [D].Pittsburgh,USA:Carnegie Mellon University,2004.

[5] 李营那.基于新闻要素的在线新事件检测[D].上海:华东理工大学,2013.

[6] 陈莉萍,杜军平.突发事件热点话题识别系统及关键问题研究[J].计算机工程与应用,2011,47(32):19-22.

[7] Yi Xiaolin,Zhao Xiao,Ke Nan,et al.An Improved Single-pass Clustering Algorithm Internet-oriented Network Topic Detection[C]//Proceedings of the 4th International Conference on IntelligentControland Information Processing.Beijing,China:[s.n.],2013: 560-564.

[8] Chen Feng,Du Juan,Qian Weining,etal.Topic Detection over Online Forum[C]//Proceedings of the 9th Web Information Systems and Applications Conference.Haikou,China:[s.n.],2012:235-240.

[9] 樊旭琴,张永奎.基于词对向量空间模型的新事件检测方法[J].计算机工程与应用,2010,46(12):123-125.

[10] Xu Ruifeng,Peng Weihua,Xu Jun,et al.On-line New Event Detection Using Time Window Strategy[C]// Proceedings of 2011 International Conference on MachineLearning and Cybernetics.Guilin,China: [s.n.],2011:1932-1937.

[11] Zhang Huaping.NLPIR[EB/OL].(2013-06-01).http:// www.nlpir.org/.

[12] Allan J,Lavrenko V,Swan R.Explorations within Topic Tracking and Detection[M].[S.l.]:Kluwer Academic, 2002:197-224.

[13] Inverted Index[EB/OL].(2013-06-30).http://zh. wikipedia.org/w/index.php?title=Inverted Index&old id=19175626.

编辑 陆燕菲

Online New Event Detection for Large-scale Data

CAI Yan-wu1,GAO Da-qi1,RUAN Tong1,JIANG Rui-quan2
(1.Department of Computer Science and Technology,East China University of Science and Technology, Shanghai 200237,China;2.Technology Development Department,Shanghai Stock Exchange,Shanghai 200120,China)

Through analyzing the time consumption of the existing online New Event Detection(NED)algorithm based on news elements,this paper improves an online NED algorithm for large-scale data environment.The algorithm uses efficient reported similar search mechanism based on inverted index to reduce the similarity comparison of single path clustering algorithms.Through parallelization of report pretreatment,report and event comparison,index search,it improves the efficiency and scalability of the algorithm in multimachine.Experimental result shows that the algorithm can greatly improve new event detection speed without affecting the miss probability and false-alarm probability,and its throughput reaches 150～200 reports/s at the scale of 10～100 million reports.

New Event Detection(NED);single-pass clustering;large-scale data;parallel computing;inverted index; MapReduce architecture

1000-3428(2014)10-0037-06

A

TP391

10.3969/j.issn.1000-3428.2014.10.008

国家科技支撑计划基金资助项目“证券业云平台研发与运营”(2012BAH13F02)。

蔡偃武(1989-),男,硕士研究生,主研方向:话题检测,模式识别,神经网络;高大启,教授、博士;阮 彤,副教授、博士;蒋锐权,博士。

2013-10-18

2013-11-19E-mail:caiyanwu9988@163.com

中文引用格式:蔡偃武,高大启,阮 彤,等.面向大规模数据的在线新事件检测[J].计算机工程,2014,40(10):37-42.

英文引用格式:Cai Yanwu,Gao Daqi,Ruan Tong,et al.Online New Event Detection for Large-scale Data[J]. Computer Engineering,2014,40(10):37-42.