维普资讯 http://www.cqvip.com 第25卷第5期 2008年5月 计算机应用研究 Application Research of Computers Vo1.25 No.5 Mav 2008 一种改进的回溯事件检测算法 常诚,樊绮娜,张阔,李涓子 (清华大学计算机科学与技术系,北京100084) 摘要:重点研究事件检测模型中层次聚类算法的改进,提出利用在关键词抽取基础上利用新闻的各种要素信 息计算新闻之间相似度的方式,搭建了一个在线新闻检索系统,在其上利用新华社的新闻语料进行实验。实验 结果表明改进方法的效果明显,性能较之未使用前有显著的提升。 关键词:事件检测;聚类;关键词抽取 中图分类号:TP301 文献标志码:A 文章编号:1001—3695(2008)05—1333—04 Improved retrospective event detection algorithm CHANG Cheng,FAN Qi—na,ZHANG Kuo,LI Juan—zi (Dept.of Computer Science&Technology,Tsinghua University,Beiifng 100084,China) Abstract:This paper proposed an algorithm utilizing several methods to address the problem.It used keyword extraction to re— duce the vector space model of the news and selected the keyword that could represent the news story mostly.It proposed a hierarchical clustering algorithm utilizing news metadata for similarity computing in a unified framework.Furthermore,based on this approach,it built all on—line news search system,which provided functions to organize news data into news event,and furthermore provided personalized service for users.Experimental results on news data from Xinhua News agency show that both the proposed approaches can effectively improve the pedormance of RED task,compare to the baseline method. Key words:event detection;clustering;keyword extraction 近年来随着网络的普及,在网上浏览新闻已成为人们获得 最新信息的最佳媒介之一。目前各大门户网站及主要的搜索 无法满足要求。如果能根据新闻事件将某一主题的新闻文档 进行汇整,对于提高新闻资料的利用价值和帮助新闻工作者改 进效率,应有相当的助益。 基于以上的理由,在分析了新闻内容的特点后,本文采用 向量空间模型来表示新闻文档。在计算新闻之间相似度 引擎公司都提供了在线新闻阅读服务。Google和百度等网站 还支持基本的新闻分类(如国内、国外、政治、体育等)浏览功 能,用户可以通过这些服务浏览当13或者过去所发生的新闻。 但是,由于新闻报道的更新频繁,其庞大的数据量使得用户常 常有信息过量的感觉,很难快速准确地检索到高质量的新闻信 息。除了简单的分类浏览以外,目前仍然没有进一步辅助用户 阅读相对粒度更细的新闻事件的工具。新闻事件由于有多人 同时撰述的特性,并没有一个公正客观的角度来描述特定的事 件。而且,新闻记者采写同一事件的立场差异很大,切入角度 时综合考虑时间、类别和新闻具体内容等信息,并且利用关键 字抽取对新闻文档进行预处理,简化了向量的维度。本文还借 鉴层次聚类的思想实现对新闻事件的检测,使得新闻事件的粒 度划分更加灵活和准确。 1 相关研究 1.1关键词抽取 也有所不同,再加上专业素质等原因,其所撰写的稿件内容可 能与实际情况有所出入。这样,读者想要客观了解某一新闻事 件,就必须多方阅读和比较,花费在新闻浏览与搜寻上的时间 在信息检索中,对于文件内容首先需要借由分词技术来分 析文件,从而筛选出能代表该文件的特征词。本文所探讨的新 十分可观。 新闻事件除必须掌握时效性以外,热点事件更需深入挖掘 以及跟踪报道。此外由于篇幅所限,对同一事件的后续报道经 常需要参考和引述之前的文章。一般来说,读者多根据现存报 道加之回忆勾勒出事件的梗概,再在计算机中检索以获取历史 闻文件是由中文描述。由于中文自身的特点,它不像英文那样 在词与词之间有空格间隔,而且最近的研究表明,由新词导致 的分词错误占到60%” ,加之中文字词的多样性,这些都给中 文分词增加了相当的困难。对于新闻文件来说,新词的作用更 是不可忽视。中文分词的方法可归纳为三种,即基于词典、基 于统计和结合前两种方法的混合分词法 j。 报道。传统的检索方式需要用户对自己的查询需求有相当的 理解。然而,如果用户对查询的需求比较模糊,如新闻编辑想 知道过去一年国内农业领域都有哪些热点事件等,类似上述这 样的需求,用户很难精确定义查询请求,仅仅依靠关键字检索 收稿日期:2007.03.26;修回日期:2007—05-28 经过分词处理后还不足以被选做代表文件的关键词。要 选出这样的字词,还需计算该词在文件中的权重。词权重的设 基金项目:国家自然科学基金资助项目(90604025) 作者简介:常诚(1982-),男,硕士研究生,主要研究方向为文本挖掘、信息检索(ehangc04@mails.tsin-ghHa.edu.cn);樊绮娜(1983.),女,硕士研 究生,主要研究方向为文本挖掘、信息检索;张阔(1981-),男,博士研究生,主要研究方向为文本挖掘、信息抽取、信息检索;李涓子(1968-),女,副 教授,主要研究方向为语义网、中文信息处理、网络环境下的知识发现和知识管理. 维普资讯 http://www.cqvip.com ・1334・ 计算机应用研究 j_脑醛 第25卷 定是借由计算该字词在单一文件的重要性及在整个文件集合 中的重要性而来的。目前最常使用的词权重计算方式为 TFIDF(term ̄equency inverse document ̄equency)。 ’l 攀 燃 勰 :惜・__■■・竹"懈■I直・荚●嘲 .. 1.2新闻事件检测与追踪 2 主妻弛 主曼—I 盎戳 婀壁璺 量 这项研究开始于1998年由美国国防部高等研究计划局 (DARPA)所主导的新闻主题探测与追踪计划(topic detection and tracking,TOT)。该计划的目的主要是希望从新闻广播的 嚣 雀 圳器 _{墓剖 塞毪) 嗽 黼j● ■ 7 5盐斤'j…. 愚 。抖: 撵翘5贽奎 ;{j :强 茹 茹 曩懈 储・Ei昔 _l蕾* l0帕・*I-・橇数据流中找出并追踪新的事件。新闻事件检测与追踪为其中 的一个子任务。 ± 童鲤 弛睦鬟 燕#蓝 点殳 !嘣盐亳亘 阜蝴1 2月2 盹c髓—蝈 固 L扁鼻■瞳讣 辫 ^.划 鼬科哪聱 酾蔓瞳 漪&■茸鼎I赫 五 I嘲t吊蠢 蕾尉I 蠹■鬻1 O 0 'Il蛾I一 错・■敝-埔・柚瞄时幻●I *■■・磊¨鼍: … 一 一 、 _= 事件定义为在一个确定时间、确定地点发生的事情 ;主 题则被定义为一个种子事件以及所有与其直接相关的事件与 活动[4]。在本文的工作中,事件都表现为新闻文档的集合,主 题则表现为查询词。例如,在一个时间段内,报道禽流感在某 地发生的新闻文档构成了一个新闻事件,而这些事件又是属于 查询农业这个主题所得到的结果集合。 回溯事件检测(RED)定义为在历史新闻库中发现未经定 ¥} ¥¥ 义的事件_5]。虽然RED相关的研究已经进行了多年,但它仍 然有很多问题尚待解决。这方面最早的工作是由Yang等人提 出的,他们提出了凝聚聚类算法(GAC)来解决R薰 ED问题。此 后,研究人员更多地关注与RED类似的新事件检测(NED)问 题。最近,LI Zhi.wei等人-6 利用新闻的时间分布和内容信息 定义了一个概率模型来描述新闻事件,并利用此模型估计事件 的个数。本文提出的算法参考了Yang的思想,并在GAC的基 础上提出了若干改进。 2 系统框架 基于新华社的语料设计并实现了基于事件的新闻检索系 统,其目的是为用户提供更加灵活的检索方式,以及将检索结 果按照所描述的新闻事件有效地组织起来,从而增加新闻文档 的利用率。 本文中所述系统讨论的主要数据是新闻语料。在设计算 法时考虑到新闻语料的自身特点,系统的性能会得到改善。新 闻稿件应当包括作者、新闻来源、报道时间等信息。国内外较 大的通讯社其新闻稿件又有自身的特点。下面将详细介绍新 闻稿件的新华社预处理、相似度计算以及事件检测算法,而其 中很重要的一步,即关键词抽取因篇幅关系将另作介绍。系统 流程如图I所示;查询界面如图2所示。 用户界面(Web) 图1新闻检索系统框图 图2新闻检索系统用户界面 2。1 预处理及新闻描述 由于系统要处理的新闻数据是XML文档,其内容片段如 下: (?xml version=”1.0”encoding=”UTF一8”?) (XinhuaML) (Package) (Transmissionld)20050420xjdfw5505(/Transmissionld) (DateTime)20050420T013057Z(/DateTime) (Item) (Component) (Role NormalName=”Main”/> (Lines) (HeadLine)(服务・Ⅱ)国产高端手机集体”跳水”(/ HeadLine) (KeywordLine Eid=”GJ”>经济(/KeywordLine) (/Lines) (ContentItem) (MediaType NormalName=”Text”/> <Format NormalName=”TEXT”/> (Characteristics) Property NormalName=”WordCount”HowPresent= ”字数”Value=”501”/) (/Characteristics) (Content) (![CDATA[新华社北京4月20日专电(记者令伟家) 五一“黄金周”的“前哨站”已拉开了序幕:从本周开始,联想、波导、海 尔、夏新、康佳等国产手机品牌中的“高端产品”——以百万像素拍照 手机、智能商务手机、6.5万色低价彩屏手机为代表的主流手机产品价 格开始全线下挫。 记者在北京苏宁朝阳路店看到,许多国产“高端”手机的售价已跌 破千元:一款原价1288元的6.5万色彩屏、30万像素摄像头的联想手 机的售价为998元;而一款30万像素的波导彩屏手机由原来的1258 元降至1058元;一款东信6 5万色彩屏折叠手机仅售655元…・・ 据业内人士介绍,今年手机市场最主要的特点是产品个性化的细 分,上半年主流产品将以6.5万色双屏3O万摄像头手机为主,下半年 的“领航者”可能是彩屏带摄像头的mp3手机。目前国产手机厂商在 这类产品上的技术难关已攻破,现在关键是让产品尽快与消费者见面。 处于年中的五一“黄金周”,一直是手机销售集中爆发的时段。也 是手机销售上下半年的分水岭,因此成了众多厂商十分看重的黄金商 机。国美、苏宁、大中等许多家电连锁超市都纷纷联手国产手机厂家, 调低多款手机价格,以期能在这次与“洋品牌”的手机大战中收复地 盘。(完)]])(/Content) (/Contentltem) (/Component) (/Item) (/XinhuaML) 数据预处理包含两个过程:利用XML解析器将新闻文档 中元数据提取出来,包括新闻报道的撰写时间、作者、新闻分 类、标题和新闻内容;利用分词技术、去除停用词等字词处理技 术将标题和新闻内容表示成一系列词构成的向量。 维普资讯 http://www.cqvip.com 第5期 常诚,等:一种改进的回溯事件检测算法 ・1335・ 本文对新闻标题和内容采用向量空间模型(VSM)表示。 向量空间模型的基本思想是以向量来表示文本(1.0 ,1.0 ,…, 1.0 )。其中:1.0 为第i个特征项的权重,其计算方法采用TF— IDF公式。目前存在多种TF—IDF公式。笔者在系统中采用了 一代表的类别是医药卫生领域的突发事件,即l4是ll的子类 别。在计算分类的相似度时首先将字串切割为两位数字构成 的序列,c ,c ,…,c ,c 为类别号;然后依次从左至右判断类别 号是否相等,若相等则将其相似度加上1/2的 次方。其中 种比较普遍的TF—IDF公式分别对标题和内容计算得到带有 W(t,d)=(tf(t,d)×log(N/n +0.O1)/ 指的是c。,c ,…,Cs-1都相等时c 也相等,即 sier。 (ac,a1)=1/2+(1/2) +・”+(1/2) ;s≥l 当c 不相等时,类别的相似度为0。 表1知识属性分类法 类别号 类别名 类别号 类别名 词元权重信息的向量空间模型。  ̄/∑ d[tf(t,d)×log(N/n +0.O1)] 其中:1.0(t,d)为词t在文本d中的权重;f(t,d)为词t在文本 d中的词频;Ⅳ为训练文本的总数,此处由于系统使用新华社 01 02 政治、法律 军事 o9 10 市场信息 文化、艺术及娱乐 的新闻预料作测试数据,Ⅳ为测试数据的新闻条数20 000; 为训练文本集中出现t的文本数;分母为归一化因子。 由于新闻报道的篇幅,向量空间的维度并不会很高, 经过统计,一般在200个词左右。算法的复杂度并不会随向量 空间的规模呈现指数级的增长,而且后续工作还要对已经得到 的结果作进一步处理。因此本文并未考虑使用传统的方法来 进行特征选择,而是使用后面将会提到的关键词抽取技术将特 征词的维度进一步降低。这样,经过以上处理,每个新闻可以 描述为由两个向量构成的模型: dIllk={weightf(d,Wf ),…,weightf(d,W )} d 。 nt={weight (d,W 1),…,weight (d,W )} 其中: 为新闻d中的词元数量;weight (d,1.0)和weight (d,1.0) 代表词元1.0在新闻d标题和内容中的权重。 2.2关键词抽取 基于上述工作,使用中国科学院计算所的ICTCLAS 并 利用前面已经得到的结果d 和drive抽取出一串候选的关键 词。候选的关键词是通过评价函数来评价的,分数越高越可能 是关键词。这个评价函数是在TF—IDF的基础上增加若干机制 来设计的,包括有单词的各种特征(长度、位置、词频等)。此 外,本文还应用了新的新词发现机制。由于篇幅所限,这里不 再作详述。 3事件检测算法 3.1新闻相似度计算 这一部分的算法应用在如图1系统中事件检测的部分。 由于预处理后从新闻文档中可以得到时间、新闻分类和内容等 信息,在计算新闻间的相似度时对这三个部分分别进行计算, 然后再通过加权合并得到统一的新闻相似度。此外,相似度也 可以在检索时根据需要灵活地按用户定制的方式计算。 对于新闻内容,在关键词抽取的基础上采用传统的向量夹 角的方式来计算: N厂—矿——] —~ sim一 ( ,a1)一 × )/√( )( 略) 其中: 和 为新闻的特征向量;Ⅳ为特征向量的维数; 为 向量的第 维。 对于新闻分类,按其在分类树中的距离进行计算。需要说 明的是,这里的新闻分类指的是新华社的新闻数据中知识属性 分类法对应的类别。其类别如表l所示。 表l的分类标准对于新闻事件检测来说粒度较粗,但可以 将其用于增强新闻间相似度计算的精度。新闻文档经过预处 理可以得到分类信息是由类别号构成的字串,如“l114”,其所 03 社会 11 医药卫生 o4 天气、环保、灾害 12 体育 05 科学和技术 13 其他 06 教育 14 突发事件 07 宏观经济 15 素材资料 08 行业经济 对于新闻报道时间之间的相似度,考虑采用指数衰减的方 式来计算: siert (aI,a1)=e 一0。 其中:It 一f,I是新闻报道时间所相差的天数;0根据实验结果 设为0,15。 最后,新闻间的相似度可由下面的公式得出: sier(aI,aI)=a sim (aI,a1)+卢sier i 。(al,aI)+ sim ( ,a1) 其中: 、 是由实验得出的参数,这里分别设为6、3和9。 3.2聚类算法 这一部分的算法对应在图2的聚类模块中。算法借鉴了 层次聚类的思想来实现事件的检测。该算法可以动态调整聚 类结果的粒度;缺点是其算法执行性能受到数据集的影响。本 文对此应用了QuadTree 对算法的性能方面作了优化。 输入:查询结果的集合NewsSet,新闻间相似度构成的矩阵d[1.. n][1…n]。 输出:聚类簇的集合。 a)开始时将每一个新闻文档i都定义为一个聚类簇c b)令T=t 一,t 为聚类簇的集合,其中每个聚类簇t 又是一棵 聚类簇构成的树 c)while(当71中非空的元素个数大于1时){ d)在相似度矩阵中找到相似度最大(这里设为m)的一对聚类t. 和0 e)建立一个新的子树tz用于表示聚类簇z,并将聚类簇t 、 ,作为 其孩子节点 f)for allm≠i,J{ g)利用以下方式计算新得到的聚类簇z与其他聚类簇的相似度 h)O[1,m]:(1t l XDt ,m]+l ,I Xo[j,m])/(1t l+l ,1)。其 中t 、0是合并成聚类簇z的孩子节点 i)} j)从集合71中删除聚类簇t。和 k)将tf赋值给t 1)当m小于阈值 时,计算终止,跳出循环 m)} 说明:在操作相似度矩阵时为了避免重复计算,使用了 QuadTree算法进行优化,这里不作更详细的介绍;通过大量的 实验表明,阈值 设为0.11可以有效地将结果控制在l0~l5 类,且对比实验的结果最好。 4实验结果 本文从新华社的新闻库中选取了2005年4月一2006年1 月的27 072篇新闻文档,并利用XNL解析器从中抽取元数据 维普资讯 http://www.cqvip.com ・1336・ 计算机应用研究 第25卷 信息作为实验数据。由于实验数据是中文数据且目前没有相 关成熟的系统作比较,本文所做的工作都是在前面提到的检索 系统中进行测试。 4.1 实验方法及评价标准 0.9 0.8 0.7 0.6 0.5 0.4 0 3 0.2 0.1 0 口改进前圈改进后l ;1 J口改进前豳改进后I 实验的方式是首先选择几个有代表性的查询词,在检索系 统中对查询结果进行聚类,由领域专家按事件进行分类。选择 的查询词为“农业”“住房”,分别对检索结果进行分类;然后, 二\_ 量 匡 二] l -]0一 f0.864 —函霪l 0.2 ■ 查 E翠 查全率 F-mea8ure 查准率 查全率 F-measm 图3在查询词为“农业”的 返回数据上的实验结果 图4在查询词为“住房”的 返回数据上的实验结果 将结果与仅使用内容和标题的特征词向量进行聚类的事件检 测算法和应用关键词抽取后的事件检测算法进行比较。 本文采用应用广泛的F—measure算法来评价事件检测的 从结果中可以看到,使用关键词抽取和层次聚类后对于聚 类效果起到了明显的增强作用。通过分析结果中各聚类簇的 新闻文档,可以将这个增强作用总结成以下几点: 结果。在已知文档分类的前提下,先计算查全率和查准率: recall(i, )=n ̄/ei precision(i,n=n ,n| 其中:n 沩在聚类簇 中包含事件i的文档个数;■为聚类簇 的文档个数;e 为事件i的文档数目。 聚类簇 和事件i的F—measure由下面的公式给出: ,(i, )=2recall(i, )×precision(i, )/(recall( , )+precision(i, )) 最后,总的F—measure值为 F=∑lZi/n max{F(i, )} 4.2实验结果及分析 实验基于不同的查询词返回结果分别进行了标注,并忽略 掉文档数较少的类别。结果中每个记录对应一篇新闻报道。 表2为一组标注过的实验数据,其查询词为“农业”。 表2一组实验数据 事件关键词 文档数 事件关键词 文档数 技术培训 33 禽流感 I7 农业税 33 志愿者 4 科技创新 25 表3为不使用关键词抽取而仅在预处理后的内容和标题 的特征向量基础上应用本文的事件检测算法和采用关键词抽 取后并应用本文中算法对查询结果进行聚类得到的结果对比。 各符号的定义如下:e 为事件i的文档总数;nj为聚类簇 的文 档总数;max(Ft )为事件i达到最大F—measure值时聚类簇 中 包含事件i的文档个数;max(F(i, ))为事件i和不同聚类簇J 的F—measure值中最大的值。 表3一组对比实验结果 从F—measure的结果来看,对于查询农业相关的新闻,应 用了本文所提出的事件检测算法后的结果与未使用它的方法 相比较,F—measure提高了40%。图3、4分别是查询农业和住 房时的详细结果对比图。从F—measure的结果来看,对于查询 住房来说算法提高了16.7%;从查准率和查全率的结果来看, 对于查询农业和查询住房这两种方法分别提高了43.3%与 17.7%,20.9%与42.2%;查准率平均提高了32.1%,查全率 平均提高了30.1%。 a)关键词抽取使得描述新闻的向量空间维度更小,特征 词更具代表性,过滤了许多与新闻关系不密切的词。 b)充分利用了各个新闻要素进行相似度计算,使得结果 更为精确。 C)利用层次聚类方法来控制结果粒度。 5结束语 本文首先从信息检索的角度给出了新闻事件检测的概念 模型,描述了构成系统的各部分所涉及到的相关技术,并重点 阐述了基于关键词抽取和新闻相似度计算的层次聚类算法。 通过实验表明,采用该方法可以增强用户体验和对资源更为高 效的管理。本文所述的事件检测算法中,算法的核心部分是通 过计算新闻相似度和利用层次聚类来完成的。在下一步的工 作中,笔者将考虑事件的要素抽取,包括时间、人物、地点、事件 描述,形成带语义的结构化信息,并使用数据挖掘的方法挖掘 新的知识。同时,将考虑利用机器学习方法挖掘事件之间的联 系,并利用模板生成更为详细的事件路径图。 参考文献: [1]SPROAT R,EMERSON T.The first international Chinese word seg- mentation bakeoff[C]//Proc of the 1 st SIGHAN Workshop Attached with the ACL2003 Sapporo:[s.n],2003:I33—143. [2]张春霞,郝天永.汉语自动分词的研究现状与困难[J].系统仿真 学报,2005,17(1):139—140. [3]YANG Yi—ruing,CARBONELL J G,BROWN R,et a1.Learning印一 proaches for detecting and tracking news events[J].IEEE Intelligent Systems:Special Issue on Applications of Intelligent Informa— tion Retrieval,1999,14(4):32—43. [4]ALIJAN J.Topic detcetion and tracking:event—based information or- ganization[M].Norwell:Kluwer Academic Publishers,2002:17— 31. [5]YANG Yi—uring,PIERCE T,CARBONELL J G.A study on retnr- spective and on—line event detection[C]//Proc ofthe 21 st Annum In— temational ACM SIGIR Conference on Research and Development in Information Retrieva1.New York:ACM Press,1998:28—36. [6]LI Zhi—wei,WANG Bin,LI Ming-jing,et a1.A probabilistie model ofr retrospective news event detection[C]//Pmc of the 28th Annual International ACM SIGIR Conference on Research and Development in Ifnormation Retireva1.New York:ACM Press,2005:106—1 13. 【7]张华平,刘群.ICTCLAS[EB/OL].http://www.nip.org.cn/pro- ject/project.php?proj—id=6. [8]EPPSTEIN D.Fast hierarchical clustering and other applications of dynamic closest paisr[C]//Pmc of the 9th Symposium Discrete Algo- rithms.San Francisco:ACM and SIAM.1998:619.628.