（计算机科学与技术专业论文）基于知网和话题更新的话题跟踪算法研究.pdf

摘要 话题跟踪是一项面向新闻报道信息流进行已知话题跟踪的信息处理技术，属 于话题检测与跟踪的一项重要的子任务。话题跟踪算法，即传统的话题跟踪算法， 一般包括话题新闻模型化、相似度计算及阈值比较这三个基本模块。其中，话题 新闻报道的模型表示又分为特征项提取和权重计算这两个主要部分。 知网是以汉语和英语的词语所代表的概念为描述对象，揭示概念与概念之间 以及概念所具有的属性之间的关系的知识库。 本文实现了基于话题更新的话题跟踪算法( 简称t r 算法) ，该算法利用自适 应的话题跟踪思想在话题中不断加入与该话题有关的新内容，对话题模型进行更 新，提高话题模型的适应度。 本文提出并实现了一种基于知网的报道特征规范化的话题跟踪算法( 简称 n c t 算法) 。该算法在传统话题跟踪算法的框架下实现，其中的话题新闻模型化 模块采用了知网知识库求得两个词语之间的相似度，并根据相似度对话题特征进 行规范。 此外，本文还提出并实现了基于知网的报道特征规范化和话题更新的话题跟 踪算法( 简称t r & n c t 算法) 。该算法综合利用了上述两个算法的优点。 在t d t 5 测试语料上的实验分析表明：t r 算法、n c t 算法和t r & n c t 算法 的性能优于传统的话题跟踪算法；t r & n c t 算法的性能在所有算法中效果最好。 关键词：新闻报道；知网；话题更新；话题跟踪；自然语言处理 分类号：1 p 3 9 1 3 t o p i ct r a c k i n g , 弱o n et a s ko ft o p i cd e t e c t i o na n dt o p i ct r a c k i n g ( t d d ，i sa l l i n f o r m a t i o np r o c e s s i n gt e c h n o l o g y , w h i c hi st r a c k i n gk n o w nt o p i cf r o mt h ei n f o r m a t i o n f l o wo fn e w sm e d i a g e n e r a la l g o r i t h mo ft o p i ct r a c k i n gi n c l u d e st h r e eb a s i cm o d u l e s ： t o p i c n e w sr e p r e s e n t a t i o n , s i m i l a r i t yc a l c u l a t i o na n dt h r e s h o l dc o m p a r i s o n a d d i t i o n a l l y , t o p i c n e w sr e p r e s e n t a t i o nh a st w oi m p o r t a n tp a r t s ，w h i c ha r ef e a t u r ee x t r a c t i o na n d w e i g h tc a l c u l a t i o n h o w n e ti sad a t a b a s eo fc o m m o n = s e n s ek n o w l e d g e , w h i c hd e s c r i b e sc o n c e p t si n l e x i c o n so fc h i n e s ea n de n g l i s he q u i v a l e n t s ，a n du n v e i l sr e l a t i o n sb e t w e e nc o n c e p t s a n db e t w e e nc o n c e p ta t t r i b u t e s t h i st h e s i si m p l e m e n t sa na l g o r i t h mo ft o p i ct r a c k i n gb a s e do nt o p i cr e n e w a l ( 1 r ) t r a l g o r i t h mc o n t i n u o u s l ya d d sn e wc o n t e n t sr e l a t e dt ot h et o p i c , b yu s i n gt h et h e o r yo f a d a p t i v et o p i ct r a c k i n g , i no r d e rt ou p d a t et h et o p i cv e c t o ra n d a l h a n c et h ea d a p t a b i l i t y o f r t h i st h e s i sp r o p o s e sa n di m p l e m e n t sa na l g o r i t h mo ft o p i ct r a c k i n gb a s e do nt h e n o r m a l i z a t i o no fc h a r a c t e r i s t i ct e r m so n c t ) b yu s i n gh o w n e t n c ta l g o r i t h mi s i m p l e m e n t e du n d e rt h ef r a m e w o r ko fo r d i n a r yt o p i ct r a c k i n ga l g o r i t h m a n dd u r i n gt h e p r o c e d u r eo ft o p i c n e w sr e p r e s e n t a t i o n , t h ea l g o r i t h mc a l c u l a t e st h es i m i l a r i t yo ft w o w o r d sb yu s i n gh o w n e t f u r t h e r m o r e ，t h i st h e s i sa l s op r o p o s e s a n di m p l e m e n t sa na l g o r i t h mo ft o p i c t r a c k i n gb a s e do nt o p i cr e n e w a la n dt h en o r m a l i z a t i o no fc h a r a c t e r i s t i ct e r m sb yu s i n g h o w n e t ( t r & n c t ) t r & n c ta l g o r i t h mc o m b i n e st h ea d v a n t a g e so ft h e t w o a l g o r i t h m sm e n t i o n e da b o v e t h ee x p e r i m e n t ，w h i c hi s p e r f o r m e d o nt d t 5c o r p u s ，s h o w st h a t ：t h e p e r f o r m a n c e so ft r ，n c ta n dt r & n c ta l g o r i t h ma l eb e t t e rt h a nt h eg e n e r a lt o p i c t r a c k i n ga l g o r i t h m ；i na d d i t i o n , t r & n c ta l g o r i t h mp e r f o r m st h eb e s ta m o n ga l lt h e a l g o r i t h m s k e y w o r d s ：n e w s s t o r i e s ；h o w n e t ；t o p i cr e n e w a l ；t o p i ct r a c k i n g ；n l p c i a s s n o ：t p 3 9 1 3 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅同意学校向国 家有关部门或机构送交论文的复印件和磁盘 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 丝健 签字日期：0 纠罗年6 月彦日 f 导师签名： 签字日期：a 哆年6 月f ，乒日 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：缱彼 签字日期：工卯7 年6 月停日 5 1 致谢 本论文的工作是在我的导师瞿有利副教授的精心指导和悉心关怀下完成的。 瞿老师渊博的学识、严谨的治学态度、孜孜不倦的进取精神、对问题实质的洞察 入微及宽广豁达的长者风范，给了我留下了深刻的印象。攻读硕士期间，无论是 在学习上还是生活上，瞿老师都给予了我很多关心和帮助。在他的影响下，我不 仅学到了很多科研知识，而且还得到了动手实践的机会。从项目中的基本代码编 写到最后的论文完成，瞿老师的耐心指导使我不仅学习到了基本的理论知识，而 且养成了良好的学习习惯。这些都将融入到我未来的奋斗当中，使我受益终身。 感谢田盛丰、王志海、林友芳、于剑、孙永齐、尹传环等老师的谆谆教导和 帮助，他们一丝不苟的治学精神永远是我学习的榜样。 实验室工作及撰写论文期间，李金方、乐可欣、王世强、邵鲁杰、张凯丽、 王玲同学及陈晖师弟等对我论文研究工作给予了热情帮助，在此向他们表达我的 感激之情。他们使我感受到集体的温暖，让我的生活充满了快乐和自信。 最后我要感谢我的父母，是他们将我养育成人，给了我无私的爱。在交大学 习的日子里，他们始终都在给我默默的支持和鼓励，总在我最困难的时候给我最 坚决的支持，父母将永远是我人生最大的精神动力。 1 引言 1 1课题背景 话题跟踪是话题检测与跟踪( t o p i cd e t e c t i o na n dt r a c k i n g ，简称t d t ) 的一 项重要的子任务，它可以描述为：根据给定的与某个话题相关的少量的训练报道， 构造出话题模型，并从新闻报道信息流中识别出和该已知话题相关的后续报道的 过程i l 】。它的主要任务是跟踪与给定话题相关的后续报道，帮助人们把分散的信息 按照话题组织在一起。 新闻报道作为重要的信息源，具有数量大、增长快、时效性强和主题相关等 特性。由于信息量很大，与一个主题相关的新闻信息往往出现在不同的时间内， 并且孤立地分散在各个地方，这样就使人们很难从众多信息中快速地获取自己所 需要的信息。在这种情况下，如何从海量的新闻信息中获得自己感兴趣的新闻信 息成为人们关注的主要问题。话题跟踪( t o p i ct r a c k i n g ) 研究就是在这一背景下 产生的。 话题跟踪的研究目标是实现按话题查找、组织和利用来自各种新闻报道的信 息资源，例如自动监控新闻报道流，跟踪特定话题的新闻报道等。另外，话题跟 踪可以帮助用户找出自己感兴趣的话题的所有相关报道，以及研究话题的发展历 程等等。总体来说，对话题跟踪的研究类似于信息检索和抽取的研究。 话题跟踪的主要特点是：它面向动态的、随时间变化的新闻报道信息流，而 不是静态的文本集合；要求对新闻报道流进行实时跟踪，不允许有延迟；相对于 大量的未标注报道，可用于训练的正例非常少。 1 2话题检测与跟踪技术的发展历史 话题检测和话题跟踪是话题检测与跟踪技术( t d t ，t o p i cd e t e c t i o na n d t r a c k i n g ) 的两个重要任务。该技术研究的最初想法始于1 9 9 6 年，美国国防高级 研究计划署( d a r a p ) 根据自己的要求提出开发一种新技术，能在没有人工干预 的情况下自动确定新闻信息中话题的结构。这些初始研究的主要目的是要确定来 自信息检索领域的基于主题的技术，在大多程度上能够用来解决基于事件的信息 组织问题【1 7 l 。此后，来自d a r a p 和卡内基梅隆大学等的研究者开始定义话题检 测与跟踪研究的内容，并开发用于解决此问题的初步技术。 在一系列评测会议的推动下，) t 研究得到了不断发展。从1 9 9 8 年开始，在 d a r p a 支持下，美国标准技术研究所( n i s t ) 每年举办t d t 国际会议并进行相 应的系统评测，参加者包括m mw a t s o n 研究中心、卡内基梅隆大学、麻省理工 大学等著名大学和研究机构 2 1 。d a r p a 收集了从1 9 9 4 年7 月1 日到1 9 9 5 年6 月 3 0 日路透社新闻专线和c n n 广播稿的1 6 0 0 0 篇新闻报道作为1 r i ) t 预研项目的语 料。该评测会议制定了评判标准，并确定了五项子任务：新闻报道的切分、新事 件识别、报道关系识别、话题识别和话题跟踪 3 , 4 1 。 从1 9 9 6 年开始，对t d t 进行的有关研究都很成功。1 i ) t1 9 9 8 是话题检测与 跟踪技术的第一次公开评测，并设立了三项评测任务：新闻报道的切分、话题跟 踪以及话题检测。从这次评测开始，错误识别代价，这种将漏报率与误报率结合 起来的新指标开始作为主要的t d t 评测指标。n i s t 从1 9 9 9 年开始主持t d t 系列 评测，除了原有的三项评测任务，t d t l 9 9 9 新增了两项任务：首次报道识别和报 道关系识别。一直以来，话题跟踪是1 r i ) t 评测中最重要的评测任务之一。 1 r i ) t 系列评测过程中采用由语言数据联盟( l i n g u i s t i cd a t ac o n s o r t i u m ，简称 l d c ) 提供的语料库【5 】。目前为止，共建立了五个可用于话题检测与跟踪研究的语 料库，分别是t d t l 或t d t - p i l o t ( 预研语料) 、t d t - 2 、t d t - 3 、t d t - 4 和t d t - 5 。 这些语料均选自于大量新闻媒体的多语言新闻报道集合。其中，t d t 5 只包含了文 本形式的新闻报道，其他的语料既包含文本形式的新闻报道，也包含广播形式的 新闻报道。早先的t d t 语料包含英文和中文两种语言形式，从t d t 3 开始，又加 入了阿拉伯文的新闻报道。同时，l d c 根据报道与话题的相关性，对所有语料进 行了标注。在t d t - 2 与t d t - 3 中采取了三类标注形式，使用“y e s 一、“b r i e f 和“n o ”作为报道与话题相关度的标识。而t d t - 4 与t d t - 5 只采用“y e s 和“n o 这两种标识。 在近几年的话题跟踪评测中，其实现方法大致分为两类，一是基于文本分类 的方法，比如卡内基梅隆大学【6 】的k 最近邻( k - n e a r e s tn e i g h b o r ，简称k n n ) 和决策树( d e c i s i o nt r e e ，简称d t r e e ) 方法 5 】，以及麻省理工大学阿默斯特分校 ( u m a s s ) 的b o o s t i n g 算法【8 】等；另一类是基于信息检索的方法，包括向量检索和 概率检索。 从问题的提出到研究，再到一系列的t d t 评测，我们能够看出话题跟踪与信 息抽取研究一样，其提出和发展都是在一系列的评测驱动的方式下进行的。t d t 评测的目标是模拟真实的应用环境，在评测中包含大量话题、多语言文本和多种 来源的质量参差不齐的文本。这种评测研究的方法具有明确的形式化研究任务、 公开的训练与测试数据及公开的评测比较等特点，给话题跟踪的研究提供了良好 的平台。 2 1 3研究任务及主要技术 1 3 1 基本概念 话题检测与跟踪技术主要研究如何从新闻报道中检测出新话题，并跟踪该话 题的后续报道。其中，话题( t o p i c ) 、事件( e v e n t ) 、报道( s t o r y ) 和主题( s u b j e c t ) 是该技术的几个最基本概念【1 1 。 话题是指若干对某事件相关报道的集合，包括一个核心事件或活动以及所有 与之直接相关的事件和活动。 事件由某些原因和条件引起的，发生在特定的时间和地点，涉及某些对象， 并可能伴随某些必然结果。 报道指一个与话题紧密相关的，包含两个或多个独立陈述某个事件的子句的 新闻片段。 主题的概念比话题的含义要广一些，主题可以涵盖多个类似具体的事件或者 根本不涉及任何具体事件。比如，“地震 是一个主题，而“2 0 0 8 年5 月1 2 日四川省汶川县发生里氏8 0 级大地震一则是一个话题。 在最初的研究中，话题与事件的含义是一样的，随着话题检测与跟踪研究的 发展，话题的概念逐步被区分出来。比如“2 0 0 8 年5 月1 2 日四川省汶川县发生里 氏8 0 级大地震 这个话题，对受伤人员展开救助和各界对灾区进行捐助，均是与 此话题有关的事件。 1 3 2 话题检测与跟踪技术的五项任务 t d t 的研究包含了五项基础性的研究任务：面向新闻广播类报道的切分任务； 对未知话题首次相关报道的检测任务；报道间相关性的检测任务；面向未知话题 的检测任务以及面向已知话题的跟踪任务 7 1 。 报道切分( s t o r ys e g m e n t a t i o nt a s k ，简称s s t ) 是将原始数据流切分成具有 完整结构和统一主题的报道。由于获得的文本信息流本身就是以单个报道的形式 出现的，所以s s t 面向的数据流主要是广播、电视等媒体的音频数据流。切分的 方式分为两类：一是直接针对音频信号进行切分；另一类是将音频信号翻录成文 本形式，再进行切分。前者的切分对象是未经过翻录的广播，根据音频信号的分 布规律划分报道边界；而后者是得到文本形式的新闻报道，然后根据主题内容的 差异估计报道边界。 报道切分是其他四项任务的预处理，也就是说，其他任务都是在报道切分的 3 基础上进行的。实际应用中的t d t 系统必须保证新闻报道得到有效切分，才能进 行后续的有关检测或跟踪研究。有关研究表明，它对各种识别任务影响很大，对 跟踪任务影响较小。 首次报道检测( f i r s t - s t o r yd e t e c t i o nt a s k ，简称f s d ) 是指从具有时间顺序的 新闻报道流中自动检测出未知话题出现的第一篇报道。虽然首次报道检测与话题 检测的任务类似，但两者的输出并不相同，前者输出的是一篇报道，而后者输出 的则是一个相关于某一话题的报道集合。在t d t 2 0 0 4 的评测中，将首次报道检测 转换成了新事件检测( n e we v e n td e t e c t i o n ，简称n e d ) 。n e d 与f s d 类似，区 别在于检测对象从话题具体化为事件，这是由于某些话题的跳跃式出现，即话题 在消失一段时间后又重新出现并且起源于一个新的事件。比如“恐怖主义一这个 话题包括2 0 0 1 年的美国9 1 1 事件和2 0 0 2 年的印度尼西亚巴厘岛惨案，其中，这 两个话题在不同的时间由不同的事件引发，从而跳跃式出现。n e d 就是要研究如 何区分不同事件引发的相同话题。 关联检测( l i n kd e t e c t i o nt a s k ，简称u ) t ) ，它的主要任务是对给定的两篇新 闻报道做出判断，即是否讨论同一个话题。因为话题检测与跟踪的本原问题就是 检测话题与报道之间以及报道与报道之间的相关性，所以可以说关联检测是承载 t d t 其他各项任务的基本平台。大部分关联检测研究关注于相关性计算，包括文 本描述及特征项选择。常用的关联检测系统使用余弦相似度计算。 话题检测( t o p i cd e t e c t i o nt a s k ，简称t d ) 的主要任务是检测和组织系统预 先未知的话题。t d 要求在所有话题未知的情况下构造话题模型，并且该模型不能 独立于某一个特例话题。话题检测系统通常分为两个阶段：检测出最新话题：根 据已经检测出的话题，收集后续与其相关的报道。 话题检测意在将输入的新闻报道归入不同的话题簇，并在需要的时候建立新 的话题簇。从本质上看，这项研究等同于无指导的( 系统无法预先知道该有多少 话题簇、什么时候建立这些话题簇) 聚类研究，但只允许有限的向前看。通常的 聚类可看作是基于全局信息的聚类，即在整个数据集合上进行聚类，但话题检测 中用到的聚类是以增量方式进行的。这意味着在做出最终的决策前，不能或只能 向前面看有限数量的文本或报道。话题检测作为一种增量聚类，可以划分为两个 阶段：检测出新事件的出现；将描写先前遇到的话题的报道归入相应的话题簇。 显然，第一个阶段就是对新发生事件的检测。话题检测任务是对新事件检测任务 的一个自然扩展。但是，这两项任务的区别也是很明显的：前者关心的是将谈论 某个话题的所有新闻报道归入一个话题簇，如果仅仅不能正确检测出对某个话题 的首次报道，问题并不严重；后者则正好相反，它只关心系统能否将引出某个话 题的第一篇报道检测出来。 4 话题跟踪任务( t o p i ct r a c k i n g ) 监测新闻信息流，找到与某已知话题有关的 后续报道。其中，已知话题由一则或者多则报道得到，通常是把l 4 篇相关报道 作为训练报道，训练得出话题模型。然后，判断后续数据流中的每一篇新闻报道 与话题的相关性，从而实现跟踪功能。 1 3 3 实现话题跟踪的主要技术 目前，现有的话题跟踪实现方法大致可分为两类：一类是基于文本分类的方 法，比如卡内基梅隆大学【5 ，6 】的k - 最近邻( k - n e a r e s tn e i g h b o r ，简称k n n ) 方法、 决策树( d e c i s i o nt r e e ，简称d - t r e e ) 方法和麻省理工大学阿默斯特分校( u m a s s ) 【8 】的二元分类算法等，这些方法都面临着训练报道过于稀疏的问题；另一类是基于 信息检索的方法，包括向量检索和概率检索，如j a m e sa l l a n 和m i c h a e l t 9 】采用的 r o c c h i o 算法，其核心思想是利用跟踪得到的后续报道不断改进和更新话题模型。 k n n 方法首先根据内容的相关性，选出与当前报道最相近的k 个种子报道作 为最近邻，然后根据最近邻所属的话题类别判断当前报道所论述的话题。d - t r e e 方法根据种子报道构造话题决策树，该树型结构中的每个中间节点均表示着一种 决策属性，即报道相关于话题的条件，节点产生的分支则分别代表一种决策并指 向下一层子节点，决策树的叶节点代表话题类别，输入决策树的待测报道经过逐 层节点的判断，最终划分于特定话题类别。二元分类方法将种子报道划分为相关 与不相关两个类别，根据两类报道与话题相关性的概率分布训练得到一个线性分 类器，使用该分类器将后续报道进行分类。 以上这三种基于文本分类的方法面临的主要问题是训练报道的稀疏性，话题 跟踪任务一般只给定少量相关报道作为训练报道，通常只有l 4 篇。 在基于信息检索的方法中，具有代表性的是r o c c h i o 算法，这是一种相关反馈 算法，它假设相关报道中的特征有助于话题的正确描述，因此这些特征在话题模 型中的权重被加强，而不相关报道中的特征则趋向于错误地引导话题描述，所以 权重被削弱。r o c c h i o 算法的最大优点是系统可以利用跟踪到的后续报道不断改进 和更新话题模型，从而跟踪话题的后续发展。缺陷在于对阈值的依赖程度很高， 如果初始阈值设置过高，则后续相关报道的漏检率加大；如果阈值设置过低，将 引入大量噪声。其中，后者对跟踪系统性能造成的损失最大，因为大量噪声直接 误导话题模型的更新，从而导致跟踪结果的错误率提高。 值得注意的是，这两类方法的研究前提是认为文本中词与词之间是独立的。 但在实际的应用中，文本中出现的近义词和同义词等对文本之间相似度的计算的 影响也比较大。 5 1 4话题检测与跟踪的研究前景 话题检测与跟踪作为一项综合的技术，需要较多的自然语言处理理论和技术 作为支撑，其中涉及计算语言学、机器学习和人工智能学等很多领域的相关技术， 其核心是自然语言处理技术。 目前，基于概率模型以及自然语言处理技术的信息描述与匹配方法在1 r i ) t 研 究中得到了广泛的应用。利用概率模型的方法主要是通过特征的概率分布以及特 征之间的共现率等统计信息来描述文本，包括向量空间模型( v s m ) 【埘、语言模 型( v m ) 1 1 , 1 2 1 和相关性模型( 1 蝴) 1 3 , 1 4 1 。概率模型通过分析特征在文本集中的 概率分布建立话题与报道模型，这种方法的缺陷在于忽略了特征自身带的一些语 言信息，同时也遗漏了短语级、语句级和篇章级的结构与层次。随着话题检测与 跟踪技术的发展，只靠传统的基于统计策略的方法，比如：信息检索、信息过滤 和分类等并不能真实地描述其语义空间。因此，基于n l p 技术及其与统计学原理 相融合的相应研究将逐步成为t d t 领域的重要方向。 将来的发展应主要关注话题本身的特性，如话题的突发性与跳跃性、相关报 道的延续性与继承性及新闻的时序性等。这也决定了仅仅利用现有的信息检索方 法对进一步提升，i i ) t 系统的性能是有限的，要想突破必须要借助更多的自然语言 理解技术。同时应考虑多种方法的综合运用，综合使用多种相对成熟的方法，从 长期看来在实际应用中可能效果最佳，这也是将来的一个研究发展方向。 这些方法在一定程度上提高了t d t 系统的性能，但只能是对传统统计策略的 一种补充与修正，并没有形成独立于话题检测与跟踪领域特有的研究框架与模型。 因此，未来的研究方向将主要集中于以下几个方面： ( 1 ) 新闻报道特有的特征提取与信息挖掘技术； ( 2 ) 建立具备新闻报道特性的描述模型； ( 3 ) 针对新闻报道时序性的检测与跟踪策略； ( 4 ) 机器学习与自然语言处理技术的有效融合； ( 5 ) 检测与跟踪模型的自适应学习与更新策略。 t d t 的发展与实际应用关系密切，在国家信息安全、企业市场调查和个人信 息定制等方面都存在着实际需求。随着现有系统性能的不断提高，t d t 在各个领 域将得到越来越广泛地应用。 6 1 5本文主要工作及组织安排 1 5 1 本文主要工作 本文的研究目的是对话题检测与跟踪中话题跟踪这一子任务进行深入的了解 与研究，掌握国内外话题跟踪研究的新动态。在现有的向量空间描述文档的基础 上，实现了一个基于话题更新的话题跟踪算法，提出了基于知网的报道特征规范 化的跟踪算法以及基于知网的报道特征规范化和话题更新的话题跟踪算法。实验 表明话题更新和同义词近义词的消除有助于提高话题跟踪系统的性能。 本文主要讨论了与话题跟踪技术有关的内容，介绍了实现话题跟踪需要解决 的问题，讨论了结合权重调整、话题更新和基于知网的对报道特征进行规范化的 方法。通过实际分析发现，地点名词、人名及一些专有名词等作为特征项对于新 闻报道具有很好的表征作用，因此在实现话题跟踪算法的过程中对这些词的权重 做了调整。同时，本文针对训练报道稀疏这一问题，利用自适应的话题跟踪思想， 对话题模型进行了更新，达到了提高系统性能的作用。此外，对于特征项之间相 互不独立的现象，本文采用了知网这个知识库，提出了如何利用知网知识系统计 算词语间的相似度并消除近义词语对系统的影响的方法。 1 5 2 全文组织安排 全文共分为六章，分别介绍了话题跟踪的相关技术、话题跟踪算法的设计实 现以及相关的实验结果： 第一章是引言部分，介绍了话题检测与跟踪技术的研究背景和发展历史，并阐 述了话题检测与跟踪的主要技术及发展前景。 第二章介绍了话题跟踪的相关技术，包括话题与报道的模型表示、话题与报 道的相似度计算及阈值的确定等。 第三章对知网进行了介绍，分别介绍了知网的结构、知识系统及知网的应用 这几个方面。 第四章是话题跟踪算法的设计与实现，主要内容包括话题跟踪算法的基本模 块、基于话题更新的话题跟踪算法、基于知网的报道特征规范化算法以及基于知 网的报道特征规范化和话题更新的话题跟踪算法。 第五章主要介绍了影响话题跟踪性能的几个因素，系统性能的评价标准、实 验结果及其分析。 7 2 话题跟踪的关键技术 2 1 新闻报道的模型表示 实现一个话题跟踪算法，判断报道是否与某个话题有关，首先要解决的问题 是用什么模型来表示这些待测的新闻报道【1 5 】。一篇新闻文本的正文虽然是整个文 本内容最好的表达，但是较长的篇幅使文本处理变得很困难。所以，不管是训练 报道还是语料库中的新闻报道，都必须表示成计算机可以识别的形式，来为文本 的后续处理做准备。 目前，常用的报道模型有语言模型( l a n g u a g em o d e l ，l m ) 和向量空间模型 ( v e c t o rs p a c em o d e l ，v s m ) 。 2 1 1 语言模型和向量空间模型 语言模型【1 6 1 是一种基于概率的模型，用来计算某种语言中所有句子或其他语 言单位的概率。一般来说，语言模型的研究任务是：已知文本序列中前面( 卜1 ) 个 词汇，第j 个词汇为单词w 的可能性的大小。在大多数统计语言模型的应用，比 如语音识别和信息检索等研究中，一个句子的概率常常被分解为若干n - g r a m 概率 的乘积，也就是刀元语言模型。 假设报道中出现的词矽各不相关，则某报道d 和话题r 相关的概率是： 咿旧= 警聊玎等 ( 2 1 ) 其中，尸( 乃是新闻报道和话题r 相关的先验概率；只w l 乃表示词w 在某话题t 中的生成概率；只叻是词w 在整个语料库中的分布；尸 ( j r l 西表示报道丁和话题d 相 关的概率。 针对新闻报道的特点，本文采取向量空间模型。它是一种文档表示形式，具 有概念简单，实现灵活的特点。它将文档表示成为一个空间向量，向量的每一维 代表该文本的一个特征( t e r m ) ；并且每一维的取值，即权重，对应于该特征对文 档的代表性。 按照向量空间模型，一篇新闻报道可以表示为d = d ( f ，w i ；t 2 ，w 2 ；t n ， w ) ，其中是从文档d 中选出的特征项，w i 是项矗对应的权重，1 f 肌有了文 档的向量表示，两篇文档d j 和仍的相关度就可以通过向量之间的相似度s i m ， 8 伤) 来度量。 值得注意的是，向量空间模型建立的前提是认为词与词之间是相互独立的。 也就是说，向量的每一维之间均是独立没有关系的。 2 1 2 特征项提取 每篇新闻报道一般都有几百个字符，如果把新闻的所有文本作为特征，不仅 需要昂贵的处理代价，还会因为噪音过多而影响话题跟踪系统的性能。而且每个 特征向量都要代表一篇新闻报道文本。因此，如何提取具有代表性的特征项就成 为了首要问题。作为文本的特征项，应该具有彻底性和专门性【1 7 1 这两个特点。所 谓彻底性，就是指能够涵盖文本主题的程度，而专门性就是指能够反映文本的具 体内容。 在选择特征项时通常有以下几个原则【埔1 ：一是选择包含语义信息较多，对文 本的表示能力较强的语言单位作为特征项；二是文本在这些特征项上的分布有比 较明显的统计规律性；三是比较容易实现，时间和空间的开销都不能太大。 根据对文本分析处理的层次和特征本身具有的信息特点，可以将候选特征划 分为以下几个层次1 1 9 】： 1 ) 次词语级：由词语分解得到的一些特征。字节n - g a r m 是属于这一级别的 常用特征。采用这种特征不需要对文本做深层次的分析处理，适合处理多语言文 本，即将不同语言的文本统一看作连续的字节流。此外，这种文本表示方法还具 有一定的容错能力，能够排除某些拼写错误的影响。 2 ) 词语级：一般认为，词语是构成文本的主体，是最能反映文本语义的基本 单位，选择词作为特征项能充分表示文本的语义。目前，基于词的文本表示方法 在话题跟踪系统的实现中还是非常有效的。 3 ) 句法级：短语和句法信息。利用有效的分析工具，可以得到文本的某些句 法特征，如一些名词短语等。由词性标注过程得到的词类信息也是一种句法级的 特征。 4 ) 语义级：文本的某种语义表示。目前还没有一种可操作的文本语义表示形 式和完全自动的语义抽取方法。不过，多义词在文本中的确定语义即词义排歧的 结果在某种程度上也可看作是一种语义级的文本特征。 5 ) 篇章级：文本的篇章结构，如章、节和小节等结构信息。位置信息也可以 看作是某种篇章级的特征。 6 ) 语用级：与上下文和情景紧密相关的文本意义特征，如某电子邮件包含多 于2 0 个以上的收件人则认为它很有可能是垃圾邮件。 9 一般来说，特征级别越高，对文本信息的描述就越详细。划分候选特征项的 前提是对文本进行分词处理，分词的基本方法有最大匹配法、最大概率法和最短 路径分词法。由于本文采用语料库的新闻报道已经经过分词处理，所以这里不再 一一介绍 本文采用的t d t 5 语料库以词语级作为新闻文本的划分层次，划分后的词均 有相应的词性标注。以计算所的汉语词性标记集为例【2 0 】，它一共有9 9 个标记，2 2 个一类，酯个二类，1 1 个三类。比如“美国n s 和。举行一这两个词语，其中 “n s 一表示该词为地名，属于二类；“v 一表示该词为动词，属于一类。 对一篇经过分词处理的新闻报道选取特征项，首先要按词性标注保留名词、 动词和形容词等具有实际意义的词，去除对文本表征贡献不大的停用词、虚词和 标点等。具体包括区别词b 、助词u 、语气词y 、象声词o 、叹词e 、介词p 、数词 m 、量词q 、连词c 和标点符号w 。然后，将剩下的词按照其词性以及词频等信息， 赋予不同的权重值。最后，选取权重较大的若干个关键词特征项组成向量，来唯 一地表示该篇新闻报道。 2 1 3 权重计算 特征项选取主要用来去掉特征空间中那些被认为无关的或者是相关性不大的 特征。其中，特征的相对重要性由其权重来衡量。定义如下：假设一个系统包含 有m 个文档，一个不同的特征项，则t k 表示一个文档；给其中的项t k ( j 敛勤) 赋 值，记为毗，表示它在文档集中的重要程度，通常称为项玖的权重。它主要包括 3 个指标：词频度、相对这一类文本的集中度和相对这一类文本的分散度。通常认 为权重大小能够反映其在这一类文本中的重要性，为每一类文本选取特征词的方 法就是按照权重大小选取权重最大的刀个词作为这一类的特征词。 由于文本特征维数很高，如果单凭经验人工给每个特征项赋予权重是不现实 的。因此，通常采用统计的方法，即词频( t e r mf r e q u e n c y , 简写成咖和倒排文档 频率( i n v e r s ed o c u m e n tf r e q u e n c y ，简写成i d f ) 来计算每个特征项的权重。近几年， 用得比较多的是由g 。s a l t o n l 2 l 】等提出的著名权重公式： w e i g h t = 矿* i d f ( 2 2 ) 1 ) 词频矿 在利用统计方法计算每个特征项的权重之前，先按照词性为每个词赋予一个 词性权重值贝t e r m ) 。由于新闻报道中更强调事件发生的地点、时间和对象，所以 人名、地名、机构团体名及其他专有名词能够很好的对新闻事件进行表征，在计 算权重时要赋予较高的权重，即根据词性信息加权融合关键词词频： 1 0 = ：= 迅一n n 一； = i ：= 话讲嘲一c 一= ：，= b 0 r g 撕砒n n 一； 一= ：，= 讧呻咿一； 其中，t e r m 表示文本特征项，即关键词，那么s t f c t e r m ) = 巳一。咖棚。f c t e r m ) ( 2 3 ) 人t e r m ) 是指关键词在该篇报道中出现的次数，吠t e r m ) 是加权融合关键词之后得 到的词频数。 2 ) 逆向文档频数渺 逆向文档频数( i d f ) 是一个词语普遍重要性的度量，它是指词在整个文本集 中出现的频数倒数。如果词形出现在许多文档中，由于其区分能力减弱，它的重 要性也降低。渺值随着新闻报道数量的增多而随之改变，计算每篇文档的关键词 向量时，使用的都是当前渺值。通常情况下，计算渺的公式为： 渺：1 0 9 型( 2 4 ) 其中刀表示包含词w 的文本数；n 表示文本集中的文本总数。 本文采用t f i d f 权重计算公式，这种方法有利于滤掉常见的词语，保留重要 的词语。 2 1 4 新闻报道模型表示的流程 新闻报道模型表示的具体流程如下： 1 ) 去掉虚词、停用词、虚词，保留名词、形容词以及动词等有实际意义的命 名实体； 2 ) 计算词形在文档中出现的次数，利用加权融合处理得到词频t 吠t e r m ) ： 3 ) 计算词形的逆文档频数，利用t f i d f 权重计算公式得到词的权重； 4 ) 重复( 1 ) 一( 3 ) 步，得到所有词的权重，并按照权重值由高到低排序，取前万 个词组成特征向量，作为新闻报道的表征。 2 2 相似度计算 新闻报道和话题经过模型表示之后，便可以通过某种方法计算新闻报道与话 题的相关度。在向量空间模型中，相关程度的大小一般是通过计算相似度来得到 的。相似度( s i m i l a r i t y ) 指两个文档之间的相似程度。得到报道与话题的相似度 之后，就可以将该值与预设的阈值进行比较，判断报道是否与话题有关。 基于向量的文档相似度计算有很多种方法，常用的有内积、d i c e 系数和余弦 法则。本文采用余弦法则来计算两篇文档间的相似度【2 2 1 。 设耽d 是特征项t 在文档d 中的权重，将文档d 表示成为特征空间的一个向量 乃， 圪= ( 五，) ，( 互，一) ，亿，形，d ) ，t = l ，2 ，o * e 9 册 其中朋是特征项个数，乃即特征项t ，睨d 的值由t f i d f 公式【2 i 】给出。那么， 计算已知话题西和新闻报道西之间的相似度的余弦公式如下： s i m ( v 一，匕，) = 耄彤一形力= t i i ( 2 5 ) 对于语言模型来说，报道d 与话题r 的相似度用如下公式来计算【2 3 1 ： s i r e ( d , d = 丢荟触id l o g 业等孚幽 ( 2 6 ) 其中p ( i 力是通过最大似然估计算法计算得到的词c o 在给定话题r 中的概率； 尸( ) 是词c o 在语料库中的分布；吠，力是报道d 中特征项的词频：厶是指报道 的长度。 通常用语言模型算出的话题与新闻报道之间的相似度不可比较，因为单个语 言模型都有各自不同的概率特征，这样测试文档和不同话题之间算出的数值差异 很大，不能用单一的阈值进行比较，必须进行归一化。 2 3 阈值大小的确定 计算得到话题与新闻报道的相似度后，要将相似度的值与预设的阈值进行比 较，大于阈值的即与该话题相关，否则与该话题无关。因此，对阈值的设定相当 重要。 1 2 但是，通常情况下阈值的确定十分困难。一般采用先预定初始值，然后通过 测试语料库，使用话题跟踪算法进行实验，再根据跟踪结果的准确度调整预设的 初始值。本文也采用了这种办法来确定阈值。 这样的方法有两个缺点，一方面，初始值很难确定，只能根据经验或简单的 测试来设定；另一方面，对预设值进行调整的时候，调整的幅度不好确定，只有 反复的测试，然后再反复的调整。目前还没有比较简单，并且有效的办法来确定 阈值的大小。 1 3 3 知网 3 1 知网概述 知网( 英文名称为h o w n e t ) 是一个以汉语和英语的词语所代表的概念为描述 对象，以揭示概念与概念之间以及概念所具有的属性之间的关系为基本内容的常 识知识库【2 4 1 。 在知网中，描述词汇语义的概念被分解成各种义原【2 5 】，即最基本的、不易于 再分割的意义的最小单位，通过有限的义原组合来表达无限的概念，每个词可以 具有多个概念( 即一词多义) 。 知网作为一个知识系统，名副其实是一个网而不是树。它所着力要反映的是 概念的共性和个性，例如：对于“医生一和“患者一，“人一是它们的共性。知网 在主要特性文件中描述了“人一所具有的共性，那么搿医生一的个性是他是“医 治 的施事，而。患者 的个性是他是“患病 的经验者。对于“富翁一和“穷 人一，“美女 和“丑八怪一而言，“人一是它们的共性。而它们的个性，即：“贫 、 “富一与“美 、“丑一等不同的属性值，则是它们的个性。 此外，知网还着力反映概念之间和概念的属性之间的各种关系，定义了上下 位、同义、反义及部件一整体等1 6 种关系，从而使知网形成了一个网状的知识系 统。 总体来说，知网描述了下列各种关系【2 4 】： a ) 上下位关系( 由概念的主要特征体现，请参看知网管理工具) b ) 同义关系( 可通过 同义、反义以及对义组的形成获得) c ) 反义关系( 可通过同义、反义以及对义组的形成获得) d ) 对义关系( 可通过同义、反义以及对义组的形成获得) c ) 部件整体关系( 由在整体前标注体现，如“心 、“c p u ”等) 0 属性宿主关系( 由在宿主前标注& 体现，如“颜色 、“速度 等) g ) 材料成品关系( 由在成品前标注? 体现，如“布 、“面粉等) h ) 施事经验者关系主体事件关系( 由在事件前标注 体现，如“医生、“雇 主 等) i )受事内容领属物等事件关系( 由在事件前标注$ 体现，如“患者 、“雇员” 等) j )工具事件关系( 由在事件前标注体现，如“手表、“计算机等) 1 4 k )