维普资讯 http://www.cqvip.com 第２５卷第５期 ２００８年５月 计算机应用研究 Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ Ｖｏ１．２５ Ｎｏ．５ Ｍａｖ ２００８ 一种改进的回溯事件检测算法 常诚，樊绮娜，张阔，李涓子 （清华大学计算机科学与技术系，北京１０００８４） 摘要：重点研究事件检测模型中层次聚类算法的改进，提出利用在关键词抽取基础上利用新闻的各种要素信 息计算新闻之间相似度的方式，搭建了一个在线新闻检索系统，在其上利用新华社的新闻语料进行实验。实验 结果表明改进方法的效果明显，性能较之未使用前有显著的提升。 关键词：事件检测；聚类；关键词抽取 中图分类号：ＴＰ３０１ 文献标志码：Ａ 文章编号：１００１—３６９５（２００８）０５—１３３３—０４ Ｉｍｐｒｏｖｅｄ ｒｅｔｒｏｓｐｅｃｔｉｖｅ ｅｖｅｎｔ ｄｅｔｅｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ＣＨＡＮＧ Ｃｈｅｎｇ，ＦＡＮ Ｑｉ—ｎａ，ＺＨＡＮＧ Ｋｕｏ，ＬＩ Ｊｕａｎ—ｚｉ （Ｄｅｐｔ．ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ，Ｔｓｉｎｇｈｕａ Ｕｎｉｖｅｒｓｉｔｙ，Ｂｅｉｉｆｎｇ １０００８４，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｄ ａｎ ａｌｇｏｒｉｔｈｍ ｕｔｉｌｉｚｉｎｇ ｓｅｖｅｒａｌ ｍｅｔｈｏｄｓ ｔｏ ａｄｄｒｅｓｓ ｔｈｅ ｐｒｏｂｌｅｍ．Ｉｔ ｕｓｅｄ ｋｅｙｗｏｒｄ ｅｘｔｒａｃｔｉｏｎ ｔｏ ｒｅ— ｄｕｃｅ ｔｈｅ ｖｅｃｔｏｒ ｓｐａｃｅ ｍｏｄｅｌ ｏｆ ｔｈｅ ｎｅｗｓ ａｎｄ ｓｅｌｅｃｔｅｄ ｔｈｅ ｋｅｙｗｏｒｄ ｔｈａｔ ｃｏｕｌｄ ｒｅｐｒｅｓｅｎｔ ｔｈｅ ｎｅｗｓ ｓｔｏｒｙ ｍｏｓｔｌｙ．Ｉｔ ｐｒｏｐｏｓｅｄ ａ ｈｉｅｒａｒｃｈｉｃａｌ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｕｔｉｌｉｚｉｎｇ ｎｅｗｓ ｍｅｔａｄａｔａ ｆｏｒ ｓｉｍｉｌａｒｉｔｙ ｃｏｍｐｕｔｉｎｇ ｉｎ ａ ｕｎｉｆｉｅｄ ｆｒａｍｅｗｏｒｋ．Ｆｕｒｔｈｅｒｍｏｒｅ，ｂａｓｅｄ ｏｎ ｔｈｉｓ ａｐｐｒｏａｃｈ，ｉｔ ｂｕｉｌｔ ａｌｌ ｏｎ—ｌｉｎｅ ｎｅｗｓ ｓｅａｒｃｈ ｓｙｓｔｅｍ，ｗｈｉｃｈ ｐｒｏｖｉｄｅｄ ｆｕｎｃｔｉｏｎｓ ｔｏ ｏｒｇａｎｉｚｅ ｎｅｗｓ ｄａｔａ ｉｎｔｏ ｎｅｗｓ ｅｖｅｎｔ，ａｎｄ ｆｕｒｔｈｅｒｍｏｒｅ ｐｒｏｖｉｄｅｄ ｐｅｒｓｏｎａｌｉｚｅｄ ｓｅｒｖｉｃｅ ｆｏｒ ｕｓｅｒｓ．Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｏｎ ｎｅｗｓ ｄａｔａ ｆｒｏｍ Ｘｉｎｈｕａ Ｎｅｗｓ ａｇｅｎｃｙ ｓｈｏｗ ｔｈａｔ ｂｏｔｈ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｐｐｒｏａｃｈｅｓ ｃａｎ ｅｆｆｅｃｔｉｖｅｌｙ ｉｍｐｒｏｖｅ ｔｈｅ ｐｅｄｏｒｍａｎｃｅ ｏｆ ＲＥＤ ｔａｓｋ，ｃｏｍｐａｒｅ ｔｏ ｔｈｅ ｂａｓｅｌｉｎｅ ｍｅｔｈｏｄ． Ｋｅｙ ｗｏｒｄｓ：ｅｖｅｎｔ ｄｅｔｅｃｔｉｏｎ；ｃｌｕｓｔｅｒｉｎｇ；ｋｅｙｗｏｒｄ ｅｘｔｒａｃｔｉｏｎ 近年来随着网络的普及，在网上浏览新闻已成为人们获得 最新信息的最佳媒介之一。目前各大门户网站及主要的搜索 无法满足要求。如果能根据新闻事件将某一主题的新闻文档 进行汇整，对于提高新闻资料的利用价值和帮助新闻工作者改 进效率，应有相当的助益。 基于以上的理由，在分析了新闻内容的特点后，本文采用 向量空间模型来表示新闻文档。在计算新闻之间相似度 引擎公司都提供了在线新闻阅读服务。Ｇｏｏｇｌｅ和百度等网站 还支持基本的新闻分类（如国内、国外、政治、体育等）浏览功 能，用户可以通过这些服务浏览当１３或者过去所发生的新闻。 但是，由于新闻报道的更新频繁，其庞大的数据量使得用户常 常有信息过量的感觉，很难快速准确地检索到高质量的新闻信 息。除了简单的分类浏览以外，目前仍然没有进一步辅助用户 阅读相对粒度更细的新闻事件的工具。新闻事件由于有多人 同时撰述的特性，并没有一个公正客观的角度来描述特定的事 件。而且，新闻记者采写同一事件的立场差异很大，切入角度 时综合考虑时间、类别和新闻具体内容等信息，并且利用关键 字抽取对新闻文档进行预处理，简化了向量的维度。本文还借 鉴层次聚类的思想实现对新闻事件的检测，使得新闻事件的粒 度划分更加灵活和准确。 １ 相关研究 １．１关键词抽取 也有所不同，再加上专业素质等原因，其所撰写的稿件内容可 能与实际情况有所出入。这样，读者想要客观了解某一新闻事 件，就必须多方阅读和比较，花费在新闻浏览与搜寻上的时间 在信息检索中，对于文件内容首先需要借由分词技术来分 析文件，从而筛选出能代表该文件的特征词。本文所探讨的新 十分可观。 新闻事件除必须掌握时效性以外，热点事件更需深入挖掘 以及跟踪报道。此外由于篇幅所限，对同一事件的后续报道经 常需要参考和引述之前的文章。一般来说，读者多根据现存报 道加之回忆勾勒出事件的梗概，再在计算机中检索以获取历史 闻文件是由中文描述。由于中文自身的特点，它不像英文那样 在词与词之间有空格间隔，而且最近的研究表明，由新词导致 的分词错误占到６０％” ，加之中文字词的多样性，这些都给中 文分词增加了相当的困难。对于新闻文件来说，新词的作用更 是不可忽视。中文分词的方法可归纳为三种，即基于词典、基 于统计和结合前两种方法的混合分词法 ｊ。 报道。传统的检索方式需要用户对自己的查询需求有相当的 理解。然而，如果用户对查询的需求比较模糊，如新闻编辑想 知道过去一年国内农业领域都有哪些热点事件等，类似上述这 样的需求，用户很难精确定义查询请求，仅仅依靠关键字检索 收稿日期：２００７．０３．２６；修回日期：２００７—０５－２８ 经过分词处理后还不足以被选做代表文件的关键词。要 选出这样的字词，还需计算该词在文件中的权重。词权重的设 基金项目：国家自然科学基金资助项目（９０６０４０２５） 作者简介：常诚（１９８２－），男，硕士研究生，主要研究方向为文本挖掘、信息检索（ｅｈａｎｇｃ０４＠ｍａｉｌｓ．ｔｓｉｎ－ｇｈＨａ．ｅｄｕ．ｃｎ）；樊绮娜（１９８３．），女，硕士研 究生，主要研究方向为文本挖掘、信息检索；张阔（１９８１－），男，博士研究生，主要研究方向为文本挖掘、信息抽取、信息检索；李涓子（１９６８－），女，副 教授，主要研究方向为语义网、中文信息处理、网络环境下的知识发现和知识管理． 维普资讯 http://www.cqvip.com ・１３３４・ 计算机应用研究 ｊ＿脑醛 第２５卷 定是借由计算该字词在单一文件的重要性及在整个文件集合 中的重要性而来的。目前最常使用的词权重计算方式为 ＴＦＩＤＦ（ｔｅｒｍ￣ｅｑｕｅｎｃｙ ｉｎｖｅｒｓｅ ｄｏｃｕｍｅｎｔ￣ｅｑｕｅｎｃｙ）。 ’ｌ 攀 燃 勰 ：惜・＿＿■■・竹＂懈■Ｉ直・荚●嘲 ．． １．２新闻事件检测与追踪 ２ 主妻弛 主曼—Ｉ 盎戳 婀壁璺 量 这项研究开始于１９９８年由美国国防部高等研究计划局 （ＤＡＲＰＡ）所主导的新闻主题探测与追踪计划（ｔｏｐｉｃ ｄｅｔｅｃｔｉｏｎ ａｎｄ ｔｒａｃｋｉｎｇ，ＴＯＴ）。该计划的目的主要是希望从新闻广播的 嚣 雀 圳器 ＿｛墓剖 塞毪） 嗽 黼ｊ● ■ ７ ５盐斤＇ｊ…． 愚 。抖： 撵翘５贽奎 ；｛ｊ ：强 茹 茹 曩懈 储・Ｅｉ昔 ＿ｌ蕾＊ ｌ０帕・＊Ｉ－・橇数据流中找出并追踪新的事件。新闻事件检测与追踪为其中 的一个子任务。 ± 童鲤 弛睦鬟 燕＃蓝 点殳 ！嘣盐亳亘 阜蝴１ ２月２ 盹ｃ髓—蝈 固 Ｌ扁鼻■瞳讣 辫 ＾．划 鼬科哪聱 酾蔓瞳 漪＆■茸鼎Ｉ赫 五 Ｉ嘲ｔ吊蠢 蕾尉Ｉ 蠹■鬻１ Ｏ ０ ＇Ｉｌ蛾Ｉ一 错・■敝－埔・柚瞄时幻●Ｉ ＊■■・磊¨鼍： … 一 一 、 ＿＝ 事件定义为在一个确定时间、确定地点发生的事情 ；主 题则被定义为一个种子事件以及所有与其直接相关的事件与 活动［４］。在本文的工作中，事件都表现为新闻文档的集合，主 题则表现为查询词。例如，在一个时间段内，报道禽流感在某 地发生的新闻文档构成了一个新闻事件，而这些事件又是属于 查询农业这个主题所得到的结果集合。 回溯事件检测（ＲＥＤ）定义为在历史新闻库中发现未经定 ￥｝ ￥￥ 义的事件＿５］。虽然ＲＥＤ相关的研究已经进行了多年，但它仍 然有很多问题尚待解决。这方面最早的工作是由Ｙａｎｇ等人提 出的，他们提出了凝聚聚类算法（ＧＡＣ）来解决Ｒ薰 ＥＤ问题。此 后，研究人员更多地关注与ＲＥＤ类似的新事件检测（ＮＥＤ）问 题。最近，ＬＩ Ｚｈｉ．ｗｅｉ等人－６ 利用新闻的时间分布和内容信息 定义了一个概率模型来描述新闻事件，并利用此模型估计事件 的个数。本文提出的算法参考了Ｙａｎｇ的思想，并在ＧＡＣ的基 础上提出了若干改进。 ２ 系统框架 基于新华社的语料设计并实现了基于事件的新闻检索系 统，其目的是为用户提供更加灵活的检索方式，以及将检索结 果按照所描述的新闻事件有效地组织起来，从而增加新闻文档 的利用率。 本文中所述系统讨论的主要数据是新闻语料。在设计算 法时考虑到新闻语料的自身特点，系统的性能会得到改善。新 闻稿件应当包括作者、新闻来源、报道时间等信息。国内外较 大的通讯社其新闻稿件又有自身的特点。下面将详细介绍新 闻稿件的新华社预处理、相似度计算以及事件检测算法，而其 中很重要的一步，即关键词抽取因篇幅关系将另作介绍。系统 流程如图Ｉ所示；查询界面如图２所示。 用户界面（Ｗｅｂ） 图１新闻检索系统框图 图２新闻检索系统用户界面 ２。１ 预处理及新闻描述 由于系统要处理的新闻数据是ＸＭＬ文档，其内容片段如 下： （？ｘｍｌ ｖｅｒｓｉｏｎ＝”１．０”ｅｎｃｏｄｉｎｇ＝”ＵＴＦ一８”？） （ＸｉｎｈｕａＭＬ） （Ｐａｃｋａｇｅ） （Ｔｒａｎｓｍｉｓｓｉｏｎｌｄ）２００５０４２０ｘｊｄｆｗ５５０５（／Ｔｒａｎｓｍｉｓｓｉｏｎｌｄ） （ＤａｔｅＴｉｍｅ）２００５０４２０Ｔ０１３０５７Ｚ（／ＤａｔｅＴｉｍｅ） （Ｉｔｅｍ） （Ｃｏｍｐｏｎｅｎｔ） （Ｒｏｌｅ ＮｏｒｍａｌＮａｍｅ＝”Ｍａｉｎ”／＞ （Ｌｉｎｅｓ） （ＨｅａｄＬｉｎｅ）（服务・Ⅱ）国产高端手机集体”跳水”（／ ＨｅａｄＬｉｎｅ） （ＫｅｙｗｏｒｄＬｉｎｅ Ｅｉｄ＝”ＧＪ”＞经济（／ＫｅｙｗｏｒｄＬｉｎｅ） （／Ｌｉｎｅｓ） （ＣｏｎｔｅｎｔＩｔｅｍ） （ＭｅｄｉａＴｙｐｅ ＮｏｒｍａｌＮａｍｅ＝”Ｔｅｘｔ”／＞ ＜Ｆｏｒｍａｔ ＮｏｒｍａｌＮａｍｅ＝”ＴＥＸＴ”／＞ （Ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ） Ｐｒｏｐｅｒｔｙ ＮｏｒｍａｌＮａｍｅ＝”ＷｏｒｄＣｏｕｎｔ”ＨｏｗＰｒｅｓｅｎｔ＝ ”字数”Ｖａｌｕｅ＝”５０１”／） （／Ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ） （Ｃｏｎｔｅｎｔ） （！［ＣＤＡＴＡ［新华社北京４月２０日专电（记者令伟家） 五一“黄金周”的“前哨站”已拉开了序幕：从本周开始，联想、波导、海 尔、夏新、康佳等国产手机品牌中的“高端产品”——以百万像素拍照 手机、智能商务手机、６．５万色低价彩屏手机为代表的主流手机产品价 格开始全线下挫。 记者在北京苏宁朝阳路店看到，许多国产“高端”手机的售价已跌 破千元：一款原价１２８８元的６．５万色彩屏、３０万像素摄像头的联想手 机的售价为９９８元；而一款３０万像素的波导彩屏手机由原来的１２５８ 元降至１０５８元；一款东信６ ５万色彩屏折叠手机仅售６５５元…・・ 据业内人士介绍，今年手机市场最主要的特点是产品个性化的细 分，上半年主流产品将以６．５万色双屏３Ｏ万摄像头手机为主，下半年 的“领航者”可能是彩屏带摄像头的ｍｐ３手机。目前国产手机厂商在 这类产品上的技术难关已攻破，现在关键是让产品尽快与消费者见面。 处于年中的五一“黄金周”，一直是手机销售集中爆发的时段。也 是手机销售上下半年的分水岭，因此成了众多厂商十分看重的黄金商 机。国美、苏宁、大中等许多家电连锁超市都纷纷联手国产手机厂家， 调低多款手机价格，以期能在这次与“洋品牌”的手机大战中收复地 盘。（完）］］）（／Ｃｏｎｔｅｎｔ） （／Ｃｏｎｔｅｎｔｌｔｅｍ） （／Ｃｏｍｐｏｎｅｎｔ） （／Ｉｔｅｍ） （／ＸｉｎｈｕａＭＬ） 数据预处理包含两个过程：利用ＸＭＬ解析器将新闻文档 中元数据提取出来，包括新闻报道的撰写时间、作者、新闻分 类、标题和新闻内容；利用分词技术、去除停用词等字词处理技 术将标题和新闻内容表示成一系列词构成的向量。 维普资讯 http://www.cqvip.com 第５期 常诚，等：一种改进的回溯事件检测算法 ・１３３５・ 本文对新闻标题和内容采用向量空间模型（ＶＳＭ）表示。 向量空间模型的基本思想是以向量来表示文本（１．０ ，１．０ ，…， １．０ ）。其中：１．０ 为第ｉ个特征项的权重，其计算方法采用ＴＦ— ＩＤＦ公式。目前存在多种ＴＦ—ＩＤＦ公式。笔者在系统中采用了 一代表的类别是医药卫生领域的突发事件，即ｌ４是ｌｌ的子类 别。在计算分类的相似度时首先将字串切割为两位数字构成 的序列，ｃ ，ｃ ，…，ｃ ，ｃ 为类别号；然后依次从左至右判断类别 号是否相等，若相等则将其相似度加上１／２的 次方。其中 种比较普遍的ＴＦ—ＩＤＦ公式分别对标题和内容计算得到带有 Ｗ（ｔ，ｄ）＝（ｔｆ（ｔ，ｄ）×ｌｏｇ（Ｎ／ｎ ＋０．Ｏ１）／ 指的是ｃ。，ｃ ，…，Ｃｓ－１都相等时ｃ 也相等，即 ｓｉｅｒ。 （ａｃ，ａ１）＝１／２＋（１／２） ＋・”＋（１／２） ；ｓ≥ｌ 当ｃ 不相等时，类别的相似度为０。 表１知识属性分类法 类别号 类别名 类别号 类别名 词元权重信息的向量空间模型。 ￣／∑ ｄ［ｔｆ（ｔ，ｄ）×ｌｏｇ（Ｎ／ｎ ＋０．Ｏ１）］ 其中：１．０（ｔ，ｄ）为词ｔ在文本ｄ中的权重；ｆ（ｔ，ｄ）为词ｔ在文本 ｄ中的词频；Ⅳ为训练文本的总数，此处由于系统使用新华社 ０１ ０２ 政治、法律 军事 ｏ９ １０ 市场信息 文化、艺术及娱乐 的新闻预料作测试数据，Ⅳ为测试数据的新闻条数２０ ０００； 为训练文本集中出现ｔ的文本数；分母为归一化因子。 由于新闻报道的篇幅，向量空间的维度并不会很高， 经过统计，一般在２００个词左右。算法的复杂度并不会随向量 空间的规模呈现指数级的增长，而且后续工作还要对已经得到 的结果作进一步处理。因此本文并未考虑使用传统的方法来 进行特征选择，而是使用后面将会提到的关键词抽取技术将特 征词的维度进一步降低。这样，经过以上处理，每个新闻可以 描述为由两个向量构成的模型： ｄＩｌｌｋ＝｛ｗｅｉｇｈｔｆ（ｄ，Ｗｆ ），…，ｗｅｉｇｈｔｆ（ｄ，Ｗ ）｝ ｄ 。 ｎｔ＝｛ｗｅｉｇｈｔ （ｄ，Ｗ １），…，ｗｅｉｇｈｔ （ｄ，Ｗ ）｝ 其中： 为新闻ｄ中的词元数量；ｗｅｉｇｈｔ （ｄ，１．０）和ｗｅｉｇｈｔ （ｄ，１．０） 代表词元１．０在新闻ｄ标题和内容中的权重。 ２．２关键词抽取 基于上述工作，使用中国科学院计算所的ＩＣＴＣＬＡＳ 并 利用前面已经得到的结果ｄ 和ｄｒｉｖｅ抽取出一串候选的关键 词。候选的关键词是通过评价函数来评价的，分数越高越可能 是关键词。这个评价函数是在ＴＦ—ＩＤＦ的基础上增加若干机制 来设计的，包括有单词的各种特征（长度、位置、词频等）。此 外，本文还应用了新的新词发现机制。由于篇幅所限，这里不 再作详述。 ３事件检测算法 ３．１新闻相似度计算 这一部分的算法应用在如图１系统中事件检测的部分。 由于预处理后从新闻文档中可以得到时间、新闻分类和内容等 信息，在计算新闻间的相似度时对这三个部分分别进行计算， 然后再通过加权合并得到统一的新闻相似度。此外，相似度也 可以在检索时根据需要灵活地按用户定制的方式计算。 对于新闻内容，在关键词抽取的基础上采用传统的向量夹 角的方式来计算： Ｎ厂—矿——］ —～ ｓｉｍ一 （ ，ａ１）一 × ）／√（ ）（ 略） 其中： 和 为新闻的特征向量；Ⅳ为特征向量的维数； 为 向量的第 维。 对于新闻分类，按其在分类树中的距离进行计算。需要说 明的是，这里的新闻分类指的是新华社的新闻数据中知识属性 分类法对应的类别。其类别如表ｌ所示。 表ｌ的分类标准对于新闻事件检测来说粒度较粗，但可以 将其用于增强新闻间相似度计算的精度。新闻文档经过预处 理可以得到分类信息是由类别号构成的字串，如“ｌ１１４”，其所 ０３ 社会 １１ 医药卫生 ｏ４ 天气、环保、灾害 １２ 体育 ０５ 科学和技术 １３ 其他 ０６ 教育 １４ 突发事件 ０７ 宏观经济 １５ 素材资料 ０８ 行业经济 对于新闻报道时间之间的相似度，考虑采用指数衰减的方 式来计算： ｓｉｅｒｔ （ａＩ，ａ１）＝ｅ 一０。 其中：Ｉｔ 一ｆ，Ｉ是新闻报道时间所相差的天数；０根据实验结果 设为０，１５。 最后，新闻间的相似度可由下面的公式得出： ｓｉｅｒ（ａＩ，ａＩ）＝ａ ｓｉｍ （ａＩ，ａ１）＋卢ｓｉｅｒ ｉ 。（ａｌ，ａＩ）＋ ｓｉｍ （ ，ａ１） 其中： 、 是由实验得出的参数，这里分别设为６、３和９。 ３．２聚类算法 这一部分的算法对应在图２的聚类模块中。算法借鉴了 层次聚类的思想来实现事件的检测。该算法可以动态调整聚 类结果的粒度；缺点是其算法执行性能受到数据集的影响。本 文对此应用了ＱｕａｄＴｒｅｅ 对算法的性能方面作了优化。 输入：查询结果的集合ＮｅｗｓＳｅｔ，新闻间相似度构成的矩阵ｄ［１．． ｎ］［１…ｎ］。 输出：聚类簇的集合。 ａ）开始时将每一个新闻文档ｉ都定义为一个聚类簇ｃ ｂ）令Ｔ＝ｔ 一，ｔ 为聚类簇的集合，其中每个聚类簇ｔ 又是一棵 聚类簇构成的树 ｃ）ｗｈｉｌｅ（当７１中非空的元素个数大于１时）｛ ｄ）在相似度矩阵中找到相似度最大（这里设为ｍ）的一对聚类ｔ． 和０ ｅ）建立一个新的子树ｔｚ用于表示聚类簇ｚ，并将聚类簇ｔ 、 ，作为 其孩子节点 ｆ）ｆｏｒ ａｌｌｍ≠ｉ，Ｊ｛ ｇ）利用以下方式计算新得到的聚类簇ｚ与其他聚类簇的相似度 ｈ）Ｏ［１，ｍ］：（１ｔ ｌ ＸＤｔ ，ｍ］＋ｌ ，Ｉ Ｘｏ［ｊ，ｍ］）／（１ｔ ｌ＋ｌ ，１）。其 中ｔ 、０是合并成聚类簇ｚ的孩子节点 ｉ）｝ ｊ）从集合７１中删除聚类簇ｔ。和 ｋ）将ｔｆ赋值给ｔ １）当ｍ小于阈值 时，计算终止，跳出循环 ｍ）｝ 说明：在操作相似度矩阵时为了避免重复计算，使用了 ＱｕａｄＴｒｅｅ算法进行优化，这里不作更详细的介绍；通过大量的 实验表明，阈值 设为０．１１可以有效地将结果控制在ｌ０～ｌ５ 类，且对比实验的结果最好。 ４实验结果 本文从新华社的新闻库中选取了２００５年４月一２００６年１ 月的２７ ０７２篇新闻文档，并利用ＸＮＬ解析器从中抽取元数据 维普资讯 http://www.cqvip.com ・１３３６・ 计算机应用研究 第２５卷 信息作为实验数据。由于实验数据是中文数据且目前没有相 关成熟的系统作比较，本文所做的工作都是在前面提到的检索 系统中进行测试。 ４．１ 实验方法及评价标准 ０．９ ０．８ ０．７ ０．６ ０．５ ０．４ ０ ３ ０．２ ０．１ ０ 口改进前圈改进后ｌ ；１ Ｊ口改进前豳改进后Ｉ 实验的方式是首先选择几个有代表性的查询词，在检索系 统中对查询结果进行聚类，由领域专家按事件进行分类。选择 的查询词为“农业”“住房”，分别对检索结果进行分类；然后， 二＼＿ 量 匡 二］ ｌ －］０一 ｆ０．８６４ —函霪ｌ ０．２ ■ 查 Ｅ翠 查全率 Ｆ－ｍｅａ８ｕｒｅ 查准率 查全率 Ｆ－ｍｅａｓｍ 图３在查询词为“农业”的 返回数据上的实验结果 图４在查询词为“住房”的 返回数据上的实验结果 将结果与仅使用内容和标题的特征词向量进行聚类的事件检 测算法和应用关键词抽取后的事件检测算法进行比较。 本文采用应用广泛的Ｆ—ｍｅａｓｕｒｅ算法来评价事件检测的 从结果中可以看到，使用关键词抽取和层次聚类后对于聚 类效果起到了明显的增强作用。通过分析结果中各聚类簇的 新闻文档，可以将这个增强作用总结成以下几点： 结果。在已知文档分类的前提下，先计算查全率和查准率： ｒｅｃａｌｌ（ｉ， ）＝ｎ￣／ｅｉ ｐｒｅｃｉｓｉｏｎ（ｉ，ｎ＝ｎ ，ｎ｜ 其中：ｎ 沩在聚类簇 中包含事件ｉ的文档个数；■为聚类簇 的文档个数；ｅ 为事件ｉ的文档数目。 聚类簇 和事件ｉ的Ｆ—ｍｅａｓｕｒｅ由下面的公式给出： ，（ｉ， ）＝２ｒｅｃａｌｌ（ｉ， ）×ｐｒｅｃｉｓｉｏｎ（ｉ， ）／（ｒｅｃａｌｌ（ ， ）＋ｐｒｅｃｉｓｉｏｎ（ｉ， ）） 最后，总的Ｆ—ｍｅａｓｕｒｅ值为 Ｆ＝∑ｌＺｉ／ｎ ｍａｘ｛Ｆ（ｉ， ）｝ ４．２实验结果及分析 实验基于不同的查询词返回结果分别进行了标注，并忽略 掉文档数较少的类别。结果中每个记录对应一篇新闻报道。 表２为一组标注过的实验数据，其查询词为“农业”。 表２一组实验数据 事件关键词 文档数 事件关键词 文档数 技术培训 ３３ 禽流感 Ｉ７ 农业税 ３３ 志愿者 ４ 科技创新 ２５ 表３为不使用关键词抽取而仅在预处理后的内容和标题 的特征向量基础上应用本文的事件检测算法和采用关键词抽 取后并应用本文中算法对查询结果进行聚类得到的结果对比。 各符号的定义如下：ｅ 为事件ｉ的文档总数；ｎｊ为聚类簇 的文 档总数；ｍａｘ（Ｆｔ ）为事件ｉ达到最大Ｆ—ｍｅａｓｕｒｅ值时聚类簇 中 包含事件ｉ的文档个数；ｍａｘ（Ｆ（ｉ， ））为事件ｉ和不同聚类簇Ｊ 的Ｆ—ｍｅａｓｕｒｅ值中最大的值。 表３一组对比实验结果 从Ｆ—ｍｅａｓｕｒｅ的结果来看，对于查询农业相关的新闻，应 用了本文所提出的事件检测算法后的结果与未使用它的方法 相比较，Ｆ—ｍｅａｓｕｒｅ提高了４０％。图３、４分别是查询农业和住 房时的详细结果对比图。从Ｆ—ｍｅａｓｕｒｅ的结果来看，对于查询 住房来说算法提高了１６．７％；从查准率和查全率的结果来看， 对于查询农业和查询住房这两种方法分别提高了４３．３％与 １７．７％，２０．９％与４２．２％；查准率平均提高了３２．１％，查全率 平均提高了３０．１％。 ａ）关键词抽取使得描述新闻的向量空间维度更小，特征 词更具代表性，过滤了许多与新闻关系不密切的词。 ｂ）充分利用了各个新闻要素进行相似度计算，使得结果 更为精确。 Ｃ）利用层次聚类方法来控制结果粒度。 ５结束语 本文首先从信息检索的角度给出了新闻事件检测的概念 模型，描述了构成系统的各部分所涉及到的相关技术，并重点 阐述了基于关键词抽取和新闻相似度计算的层次聚类算法。 通过实验表明，采用该方法可以增强用户体验和对资源更为高 效的管理。本文所述的事件检测算法中，算法的核心部分是通 过计算新闻相似度和利用层次聚类来完成的。在下一步的工 作中，笔者将考虑事件的要素抽取，包括时间、人物、地点、事件 描述，形成带语义的结构化信息，并使用数据挖掘的方法挖掘 新的知识。同时，将考虑利用机器学习方法挖掘事件之间的联 系，并利用模板生成更为详细的事件路径图。 参考文献： ［１］ＳＰＲＯＡＴ Ｒ，ＥＭＥＲＳＯＮ Ｔ．Ｔｈｅ ｆｉｒｓｔ ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｈｉｎｅｓｅ ｗｏｒｄ ｓｅｇ－ ｍｅｎｔａｔｉｏｎ ｂａｋｅｏｆｆ［Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ １ ｓｔ ＳＩＧＨＡＮ Ｗｏｒｋｓｈｏｐ Ａｔｔａｃｈｅｄ ｗｉｔｈ ｔｈｅ ＡＣＬ２００３ Ｓａｐｐｏｒｏ：［ｓ．ｎ］，２００３：Ｉ３３—１４３． ［２］张春霞，郝天永．汉语自动分词的研究现状与困难［Ｊ］．系统仿真 学报，２００５，１７（１）：１３９—１４０． ［３］ＹＡＮＧ Ｙｉ—ｒｕｉｎｇ，ＣＡＲＢＯＮＥＬＬ Ｊ Ｇ，ＢＲＯＷＮ Ｒ，ｅｔ ａ１．Ｌｅａｒｎｉｎｇ印一 ｐｒｏａｃｈｅｓ ｆｏｒ ｄｅｔｅｃｔｉｎｇ ａｎｄ ｔｒａｃｋｉｎｇ ｎｅｗｓ ｅｖｅｎｔｓ［Ｊ］．ＩＥＥＥ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ：Ｓｐｅｃｉａｌ Ｉｓｓｕｅ ｏｎ Ａｐｐｌｉｃａｔｉｏｎｓ ｏｆ Ｉｎｔｅｌｌｉｇｅｎｔ Ｉｎｆｏｒｍａ— ｔｉｏｎ Ｒｅｔｒｉｅｖａｌ，１９９９，１４（４）：３２—４３． ［４］ＡＬＩＪＡＮ Ｊ．Ｔｏｐｉｃ ｄｅｔｃｅｔｉｏｎ ａｎｄ ｔｒａｃｋｉｎｇ：ｅｖｅｎｔ—ｂａｓｅｄ ｉｎｆｏｒｍａｔｉｏｎ ｏｒ－ ｇａｎｉｚａｔｉｏｎ［Ｍ］．Ｎｏｒｗｅｌｌ：Ｋｌｕｗｅｒ Ａｃａｄｅｍｉｃ Ｐｕｂｌｉｓｈｅｒｓ，２００２：１７— ３１． ［５］ＹＡＮＧ Ｙｉ—ｕｒｉｎｇ，ＰＩＥＲＣＥ Ｔ，ＣＡＲＢＯＮＥＬＬ Ｊ Ｇ．Ａ ｓｔｕｄｙ ｏｎ ｒｅｔｎｒ－ ｓｐｅｃｔｉｖｅ ａｎｄ ｏｎ—ｌｉｎｅ ｅｖｅｎｔ ｄｅｔｅｃｔｉｏｎ［Ｃ］／／Ｐｒｏｃ ｏｆｔｈｅ ２１ ｓｔ Ａｎｎｕｍ Ｉｎ— ｔｅｍａｔｉｏｎａｌ ＡＣＭ ＳＩＧＩＲ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｒｅｓｅａｒｃｈ ａｎｄ Ｄｅｖｅｌｏｐｍｅｎｔ ｉｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｒｅｔｒｉｅｖａ１．Ｎｅｗ Ｙｏｒｋ：ＡＣＭ Ｐｒｅｓｓ，１９９８：２８—３６． ［６］ＬＩ Ｚｈｉ—ｗｅｉ，ＷＡＮＧ Ｂｉｎ，ＬＩ Ｍｉｎｇ－ｊｉｎｇ，ｅｔ ａ１．Ａ ｐｒｏｂａｂｉｌｉｓｔｉｅ ｍｏｄｅｌ ｏｆｒ ｒｅｔｒｏｓｐｅｃｔｉｖｅ ｎｅｗｓ ｅｖｅｎｔ ｄｅｔｅｃｔｉｏｎ［Ｃ］／／Ｐｍｃ ｏｆ ｔｈｅ ２８ｔｈ Ａｎｎｕａｌ Ｉｎｔｅｒｎａｔｉｏｎａｌ ＡＣＭ ＳＩＧＩＲ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｒｅｓｅａｒｃｈ ａｎｄ Ｄｅｖｅｌｏｐｍｅｎｔ ｉｎ Ｉｆｎｏｒｍａｔｉｏｎ Ｒｅｔｉｒｅｖａ１．Ｎｅｗ Ｙｏｒｋ：ＡＣＭ Ｐｒｅｓｓ，２００５：１０６—１ １３． 【７］张华平，刘群．ＩＣＴＣＬＡＳ［ＥＢ／ＯＬ］．ｈｔｔｐ：／／ｗｗｗ．ｎｉｐ．ｏｒｇ．ｃｎ／ｐｒｏ－ ｊｅｃｔ／ｐｒｏｊｅｃｔ．ｐｈｐ？ｐｒｏｊ—ｉｄ＝６． ［８］ＥＰＰＳＴＥＩＮ Ｄ．Ｆａｓｔ ｈｉｅｒａｒｃｈｉｃａｌ ｃｌｕｓｔｅｒｉｎｇ ａｎｄ ｏｔｈｅｒ ａｐｐｌｉｃａｔｉｏｎｓ ｏｆ ｄｙｎａｍｉｃ ｃｌｏｓｅｓｔ ｐａｉｓｒ［Ｃ］／／Ｐｍｃ ｏｆ ｔｈｅ ９ｔｈ Ｓｙｍｐｏｓｉｕｍ Ｄｉｓｃｒｅｔｅ Ａｌｇｏ－ ｒｉｔｈｍｓ．Ｓａｎ Ｆｒａｎｃｉｓｃｏ：ＡＣＭ ａｎｄ ＳＩＡＭ．１９９８：６１９．６２８．
