（信号与信息处理专业论文）web新闻话题检测与追踪技术研究.pdf

信息工程大学硕士学位论文 摘要 话题检测与追踪是一种检测新出现的话题并追踪话题发展动态的信息智能获取技术。 该技术能把分散的信息有效地汇集并组织起来，从整体上了解一个话题的全部细节以及该 话题中事件之间的相关性，在军事和民用方面都具有极其重要的理论和实用意义。本文主 要研究新闻话题检测与追踪技术，重点研究网页采集、网页噪声净化、新闻话题检测以及 热门话题追踪，取得了如下4 个方面的研究成果。 首先，根据后续处理对网页采集的要求，设计并实现了w 曲采集器。该采集器在采集 过程中进行了r o b o t s 协议分析、网页类型判断、新闻网页时间提取，对传统w 曲采集器 的功能进行了扩展。实验证明，该采集器能够对网页信息进行自动采集，并对后续的应用 提供充分的支持，具有良好的通用性。 其次，从网页文本内容的表示方式以及对网页内部噪声的分析两方面入手，提出一种 基于向量空间模型的网页噪声净化方法。该算法按照标签将网页内容划分为不同的内容 块，从中挑选出网页的主题内容块，根据向量空间模型的内容相似性比较技术对其余内容 块进行判断。实验结果表明，无论从噪声净化的准确性还是完整性方面，新方法均优于传 统净化方法。 再次，针对话题检测中事件动态发展可能会导致后继故事判断错误的现象，提出一种 基于话题重心自适应的话题检测方法。新方法用命名实体作为特征项来表示话题重心，通 过组合初始的话题重心以及每一次动态修正后的话题重心，构建用于检测后继故事的总话 题检测器。实验结果表明，该方法有效地降低了漏报率与错报率，提高了话题检测的性能。 最后，针对训练正例稀疏的问题，提出了一种改进的k n n 话题追踪方法。新方法对传 统k n n 分类方法进行改进并应用于话题追踪，降低了训练反例密集带来的影响；还在话 题追踪过程中加入时间窗策略，降低了计算的复杂度。实验结果表明，该方法能有效地克 服训练集稀疏的问题，提高了话题追踪的效率，保证话题追踪的稳健性。 关键词：话题检测与追踪，w 曲信息采集，向量空间模型，命名实体，话题重心向量，k 近邻 第页 信息工程大学硕士学位论文 a b s t r a c t t o p i cd e t e c t i 觚d 胁c i 【i n g ( t d ti ns h o n ) i s 姐e v t - b a di n f o m a t i o no 玛觚i z i n gt a s k f o rd e t c c t i n gt l l e 印p e a 舢c eo fn e wt o p i c sa n dt r a c k m gt 1 1 e i rr e 印p e a 删1 c e 锄de v o l u t i o n i t s p u r p o s ei st 0o 曙觚i z ei i l f b 肌a t i o ne 伍c i e n t l y 锄dh e l pp e o p l ef i n d i n gw h a tt l l e y m te 够i l y i n r e c e n t ”a r s ，i ti sm e o 坨t i c a l l y 锄dp r a c t i c a l l yv a l u a b l ei i lm i l i t a | 了a n do m e rf i e l d s 1 1 l i s d i s s e r t a t i o ns t u d i e st l l em o d e l s ，a l g o r i t i l l i l sa r l da p p l i c a t i o l l so fs e v e r a lk e yr e 跎a r c ht o p i c so f 矾i n c l l l d i n gw c bc r a w l e r w e b i c l e 粕i n g ，n e w st o p i cd e t e c t i o na n d 眦h n g n l em 旬o r c o 嘶b u t i o no f “sd i s s e r t a t i o ni sa sf o l l o w s ： f i r s t l y ，t l l i sd i s s e r t a t i o nd e s i g r i s 锄dr e a l i 瑟sag e r a lw c bc m w l e rt o 舢f i l im ed e m 孤do f n l ef o l l o w i n gt d t ，w h e r et t 圯p r o t o c o lo fr o b o t si s 锄a i y z e d 锄dw e bs t y l ei sc l 嬲s m e da n dt l l e m w st i m ei sp a r d t h ee x p e r i m e ms h o w sm a tt h e 、v e bc r a w l e rh a v en i c eg e n 删i t y 觚dc 觚 a u t o m a t i c a l l yd o w i l l o a dw e bp a g e s 姐dp r o v i d es 谢五c i e ms 哪r tf b rf o l l o w i n gi l l 】白肌a t i o n 印p l i c a t i o n s s e c o n d l y ，c o m b i n i n gt 1 1 cl ( i l o w l e d g eo f i s yi n f o m m t i o ne m b c d d e d i l lw 曲p a g e s 埘t h 吐圮 w a yo f 佗p 陀s e n t i n gw e bc o n t e m s ，an e wa l g o r i m mb 船c d0 nv s m f o rw e b i s ec l e 姐i n gi s p 咒s e m e d t h e 印p r o a c hd i v i d e st l l e 、c bc o n t e m si n t od i 虢佗n tb l o c l 【sa c c o r d i n gt oh t m l t o k e i l s ，p i c k so u tt h et o p i cc o m e n t 锄di d e n t i f i e sw e b i s eb y 郴i n gt l l es i m i l a r i t yc o n t r a s t t c c l l i l o l o g yb c 柳e e nt h et 叩i cc o m e n ta i l dm e 他s to fc o n t e n 协e x p e r i m e n t ss h o wt l l a tt h i s a l g o r i t i l l i le x c e i so t h e r 地l d i t i o n a lm e t l l o d si ni n t c g r a l i t y 锄d 踮c u r a c yo f t l l ew e bc l c 觚i n g t h i r d l y ，am e t h o do ft o p i cd e t e c t i o nb 硒e do na d a p t i v ec e n t r o i dv e c t o ri sp r o p o dt oa v o i d t l l es h o r t c o m i n go fc u 仃e ma d a 【p t i v em e t l l o d s t h em wm e m o di 眦r o d u c e sn 锄ee n t i t i e st o r 印f e s e n tt o p i c 觚dc o m b i n e sp r e l i m i n a r yt o p i cc e n t r o i dv e c t o r 、i t l le v e r ym o d i f l e dc e n t m i d v e c t o rf o rt o p i cd e t c c t i o n e x p e r i m e n t ss h o wt h a tt l l en e wa l g o r i m ml o w e r st h ep r o b a b i l i t yo f 1 1 1 i s s 锄df 砒a l a m le r r o r s ，锄di m p r o v e st h ep e r f b n n 孤c eo f t o p i cd c t e c t i o ns y s t e m f i n a l l y ；c o n s i d e r i n gt h es p a r s e n e s so fp o s i t i v ee x a m p l e s ，an l e n l o do fm o d i f i e d1 0 呵n b a s e d t o p i ct r a c k i n gi s i n n _ o d u c e d t h em wm e t h o dm o d m e st m d i t i o n a lk n nc l 勰s m c rf o rt o p i c 仃a c k i n g 锄dc o u l dl e s s c nt t l es i d e - e 丘b c to fd e 邶e l yp o p u l a t e dn e g a t i v ee x a m p l e s f l i r 【h e m l o r e ，a t i m e - w i n d o wi si m p o s e dt 0d c c r e 私et h ec o m p l i c a t i o no ft o p i ct r ；k i n 舀e x p e f i m e ms h o w st l l a t t h ci m p r o v e da l g o r i m mo v e r c o m e st l l es p a 塔e n e s so ft r a i n i n gs c t 觚de i l l 坷e ss t a b i l i t yo ft o p i c 蛔c “n g k e yw o r d s ：t o p i cd e t e c t i o na n dt m c k i n g ；w 曲c r a w l e r ；v e c t o rs p a c em 0 d e l ；n 锄ee m i t i e s ； t o p i cc e n 仃o i dv e c t o r ；k _ n e a r e s tn e i 曲b o r 第v i i 页 信息工程大学硕士学位论文 表目录 表l中英文时间信息对照表1 3 表2 两种方法处理数据集前后文件大小变化2 6 表3 两种方法数据集内容提取评估结果2 6 表4 两种方法对数据集的处理速度对比2 6 表5 实验数据的事件集合3 4 表6 话题检测的评测3 4 表7 话题检测实验结果3 6 表8 各类文本数量表示4 3 表9 当 仁2 时话题追踪实验结果4 6 表1 0 当产= 4 时话题追踪实验结果4 6 第1 v 页 信息工程大学硕士学位论文 图目录 图1w 曲新闻话题检测与追踪系统框图。3 图2 话题检测技术示意图。5 图3 话题追踪技术示意图。6 图4w 曲信息采集系统框图。9 图5w 曲信息采集流程图1 5 图6w 曲文档采集结果1 6 图7 向量空间模型1 9 图8 页面的信息示意2 1 图9 文档树结构示意图2 3 图l oh t m lt o 戗t1 1 0 处理结果。2 5 图1 l 新方法处理结果2 5 图1 2 类重心向量示意图3 0 图1 3 新闻话题检测示意图3 1 图1 4 两种方法对话题检测系统开销的比较3 6 图1 5 话题追踪的详细分析过程3 9 图1 6 基于文本分类的话题追踪原理框图4 1 图1 7 斐济发生政变话题新闻报道演化4 5 第v 页 原创性声明 本人声明所提交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表和撰写 过的研究成果，也不包含为获得信息工程大学或其他教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文题目：受堂堑闺适题捡测量迫跬技盔班究 学位论文作者签名： 作者指导教师签名： 日期：多7 年 日期：2 口矽年 学位论文版权使用授权书 s 羁pb 占月，o 日 本人完全了解信息工程大学有关保留、使用学位论文的规定。本人授权信息工程大学 可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允许论文被查阅和借 阅；可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：墼堡垒堑阊话题捡测生追蕴拉苤班究 学位论文作者签名： 作者指导教师签名： 日期：2 ，。7 年 日期：知司年 6 月，口日 多月，6 日 信息工程大学硕士学位论文 第一章引言 1 1 课题的来源和意义 随着信息传播手段的进步，尤其是互联网的出现，信息急剧膨胀。网络上的新闻报道 是其中最主要的信息类型之一，也是人们最为关注的信息类型之一。这些新闻报道具有数 量大、增长快、主题相关、时效性强、动态演化等特性，已成为信息获取的主要来源之一。 当前我们采集的大量网页数据中，新闻网页占有很大的比例。在这种情况下，如何快捷、 准确地从海量的新闻网页中获取感兴趣的信息成为关注的焦点。 目前在信息获取过程中，针对这种数据的处理是通过传统的关键词检索技术【l 】来完成 的。由于网络信息量太大，与一个话题相关的信息往往孤立地分散在不同的时间段和地方， 这种方法返回的信息冗余度过高，很多不相关的信息仅仅因为含有指定的关键词就被作为 结果返回了。并且，其中的相关信息并没有进行有效的组织，只是简单罗列，人们对某些 新闻事件难以做到全面地把握，在人员和处理设备有限的情况下势必造成大量数据不能被 完全处理。这样不仅浪费己采集的资源，而且一旦丢掉的数据中包含有重要价值的信息， 就会造成无法弥补的损失。话题检测与追踪( t o p i cd e t e c t i o n 锄dt r 粥k i n g ，t d t ) 1 2 3 】正是 在这种应用背景下产生的，它是一种检测新出现的话题并追踪话题发展动态的信息智能获 取技术。该技术能把分散的信息有效地汇集并组织起来，从整体上了解一个话题的全部细 节以及该话题中事件之间的相关性。 本课题来源于军队某部科研项目，主要研究项目中新闻话题检测与追踪技术，重点研 究w 曲文档的自动采集、网页噪声的净化以及新闻话题检测与热门话题追踪技术。 1 2 基本概念 1 2 1 话题 t d t 中，话题( t o p i c ) 被定义为与真实世界中不断增长的事件相关的新闻故事的集合。 在最初的研究阶段，话题和事件含义相同。一个话题是指由某些原因、条件引起，发生在 特定时间、地点、有一定的参与者或涉及者，并可能伴随某些必然结果的一个事件，比如 “2 0 0 6 年8 月2 6 日俄罗斯当局查出1 5 4 号客机失事原因”。目前使用的话题概念要相对宽 泛一些，它包括一个核心事件或活动以及所有与之直接相关的事件和活动【4 1 。如果一篇报 道讨论了与某个话题的核心事件直接相关的事件或活动，那么也认为该报道与此话题相 关。比如，搜索飞机失事的幸存者，安葬死难者都被看作与某次飞机失事这个话题相关。 1 2 2 事件 事件( e v e n t ) 是通常在特定时间、地点发生的事情。可以简单地认为话题就是若干对 某事件相关报道的集合。比如“2 0 0 6 年8 月2 4 日俄罗斯1 5 4 客机失事”是一个事件而不 第l 页 信息工程大学硕士学位论文 是话题，俄罗斯1 5 4 客机失事是话题而不是事件。一般地，事件是话题的实例，与一定的 活动相关。 1 2 3 故事 故事( s t o r y ) 是对某个事件的相关报道。在话题检测与追踪领域，它是指一个与话题 紧密相关的、包含两个或多个独立陈述某个事件的子旬的新闻片断州。 1 3 话题检测与追踪的发展与现状 t d t 技术研究的最初想法起子1 9 9 6 年，当时美国国防高级研究计划署( d a r p ：a ) 根 据自己的要求，提出要开发一种新技术，能在没有人工干预的情况下自动判断和识别新闻 数据流的话题。t d t 的研究工作不同于传统的信息检索、信息抽取、文档分类、信息管理 和数据挖掘等文档管理技术，主要原因在于1 1 ) t 技术更多地关注如何识别新的话题和获取 特定话题相关的数据。t d t 研究中对话题的定义描述不同于传统的话题定义描述。t d t 的 t o p i c 描述倾向于某一特定事件及其相关活动等描述，从而t d t 主要将事件作为分析与处 理的对象。 t d t 项目开始于1 9 9 7 年，开始阶段主要发表了包括卡耐基梅隆大学、马萨诸塞大学、 滨州大学等系统的研究报告，对这项技术进行初步研究，并做了一些基础工作【5 1 。t d t 的 研究人员力求设计一种功能强大、通用、自动的学习算法，能够识别和获取人类语言数据 的话题结构，独立于数据的来源、媒介、语种、领域和具体应用。总体来说，t d t 的研究 内容可以分为五个技术任务：将新闻故事数据流分割成为多个故事( s t o r ys e g m e n 诅t i o n ) ； 寻找属于特定话题的所有故事( t 0 p i ct r a c k i n g ) ；发现新话题，并将属于同一个话题 的所有故事进行聚类( t o p i cd e t e c t i o n ) ；发现与新话题相关的第一个出现的故事( f i r s t s t o r yd e t c c t i ) ；确定两个故事涉及的内容是否属于同一个话题( s t o r yl i r i kd e t e c t i o n ) 。 其中第四个技术f i r s ts 自d r yd e t e c t i o n 是第三个技术t o p i cd e t e c t i o n 的基础关键技术，第五 个技术s t o r yl i r i kd e t e c t i o n 相当于为第二、第三和第四个技术任务提供一个基础关键技术。 并且上述几个技术可以进行组合，完成一些功能更加强大的应用任务，本文主要研究的是 第二个和第三个技术。 从1 9 9 8 年开始，在d a r p a 发起和支持下，美国国家标准技术研究所( n i s t ) 每年 都举办t d t 评测。每次先在评测计划中公布当年的评测标准，然后经过一段时期的研究， 再进行评测，最后工作组讨论评测结果和研究进展。到目前为止，总共进行了七次t d t 评测。1 d t 评测采用的语料是由语言数据联盟( l d c ) 提供的t d t 系列语料，目前己公 布的训练和测试语料包括t d tp i l o tc o r p u s 、t d t 2 、t d t 3 、和t d t 4 1 4 】，这些语料都人工 标注了若干事件话题作为标准答案。1 9 9 8 年，t d t 技术第一次公开评测，有九个研究机构 参加，主要有三项评测任务：故事分割、话题追踪和话题检测。评测的目的是评定由自动 语音识别产生的错误和训练样本数目对t d t 性能的影响【5 1 。1 9 9 9 年秋季进行第二次t d t 评测，这次评测将1 9 9 8 年的三个任务扩展到汉语语料中，另外增加两项新任务：话题的 第2 页 信息工程大学硕士学位论文 新故事检测和相关检测，这两个新任务只针对英语语料。评测的主要任务是提高包括新闻 故事的分割、检测和追踪所需要的信息的描述技术，这次评测加入了中文的语料。2 0 0 0 年 进行第三次评测，重点是多语言的话题检测与追踪。第四次评测在2 0 0 1 年举办，主要任 务是提高在多语言新闻数据流中同时进行的t d t 技术。在2 0 0 2 年举办第五次t d t 评测， 阿拉伯语的语料填入到测试集，提倡并鼓励对文本过滤、机器翻译、语音识别、文本分割 等技术的研究。2 0 0 3 年进行第六次t d t 评测，主要有下面几个任务：首故事检测、相关 检测、话题检测、话题追踪。2 0 0 4 年的t d t 评测于以往的评测有较大的变化：故事分割 任务不再进行评测；保留话题追踪任务、话题检测和相关检测任务；增加了有监督的自适 应话题追踪任务和层次话题检测任务。t d t 评测越来越受到人们的重视，已成为一个新兴 的研究热点，国内外的很多著名的大学、公司和研究机构都参加了该评测。国外的机构主 要有：i b mw 西t s o n 研究中心、b b n 公司、卡耐基梅隆大学、马萨诸塞大学、宾州大学、 爱荷华州大学、马里兰大学等等。国内这方面的研究开展的明显晚些，1 9 9 9 年国立台湾大 学参加了话题检测任务的评测，2 0 0 0 年香港中文大学参加了1 d t 某些子任务的评测。目 前，北京大学计算语言学研究所、中科院计算所、哈工大、东北大学、复旦大学、微软亚 洲研究院、清华大学等一些国内有名的研究机构的研究人员也开始进行t d t 相关关键技术 的研究，但他们主要侧重于追踪国外最新理论和跟踪性研究，相关研究成果报道不多【3 j 。 作为一个直接面向应用的研究方向，到目前为止，话题检测与追踪领域的大部分研究 都是借用信息检索的某些方法，只是通过调整某些参数来使这些方法更适合于处理话题。 但是，话题检测与追踪研究的某些特殊性，如面向话题、基于时间等，也决定了仅仅利用 现有信息检索方法对进一步提升t d t 系统的性能是有限的，要想有所突破，必须更多地借 助于自然语言理解技术1 6 7 j 。 1 4w e b 新闻话题检测与追踪系统框架 图lw 曲新闻话题检测与追踪系统框图 第3 页 信息工程大学硕士学位论文 话题检测与追踪是一项综合技术，需要比较多的文本挖掘技术作为支撑，涉及到w 曲 信息采集、w 曲信息抽取、模式识别、人工智能、机器学习、中文自然语言处理、数据挖 掘等很多领域的相关技术，是伴随着互联网的高速发展而发展起来的一项综合性技术。 从图l 的w 曲新闻话题检测与追踪原理框图可以看出，w 曲新闻话题检测与追踪主要 由w 曲信息采集、w 曲信息抽取、新闻话题检测以及话题追踪四部分组成。 1 4 1w 曲信息采集 w 曲信息采集1 8 ，9 1 是通过w 曲文档中的链接地址来寻找w 曲文档，通常从网站某一个 页面开始，读取w 曲文档的内容，找到在w 曲文档中的下一级链接地址，然后通过这些 链接地址寻找更下一层的w 曲文档，这样一直循环下去，直到将此网站所有的w 曲文档 资源都搜寻完毕为止( 也可以按预设条件终止) 【1 0 1 。w 曲信息采集可为w 曲信息处理提 供信息资源，是后续工作的基础。 目前，把w 曲信息采集的发展方向分为以下几种【i l l ： ( 1 ) 全w 曲的信息采集( s c a l a b l ew 曲c r a w l i n g ) 这种信息采集是一种较传统的采集思想，主要是指从一些种子u i 也扩充到整个w 曲 的信息采集。 ( 2 ) 增量式w 曲信息采集( i n c r e m e n t a lw 曲c r a w l i n g ) 对旧的页面采用增量式更新，也就是说，采集器只需要采集新产生的或者己经发生变 化的页面，而对于没有变化的页面不进行采集。 ( 3 ) 基于主题的w 曲信息采集( f o c u s e dw 曲c m w l i n g ) 这种信息采集器是指有选择地搜寻那些与预先定义好的主题相关的页面，对它的研究 现在比较热门。 ( 4 ) 基于用户个性化的w 曲信息采集( c u s t o m i z e dw 曲c r a w l i n g ) 通过用户兴趣制定或与用户交互等灵活手段来采集信息。系统根据实际需要可以直接 把采集结果提供给用户，也可以先存储起来等到以后再提供。 ( 5 ) 迁移的信息采集( 黜1 0 c a t a b l ew 曲c r a w l i n g ) 将采集器上载到所要采集的服务器中，在当地进行采集，并将采集结果压缩后，回传 到本地。 1 4 2w 曲信息抽取 w 曲信息抽取是指通过计算机自动地从大量的w 曲数据中抽取感兴趣的信息，主要目 标是将文档集合转变为易于分析和处理的形式【1 2 1 。它常用自然语言处理作为分析的手段。 信息抽取的任务是从文档中抽取相关的事实【1 3 】，它的处理结果可能是结构化的数据库或 者是最初文档的压缩摘要。所以一种很自然的观点是，信息抽取是w 曲挖掘的预处理阶段， 即w 曲挖掘是建立在有结构的信息抽取结果的基础上。当然，从某种意义上讲，采用机器 学习和数据挖掘技术从w 曲文档中自动抽取模式和规则也属于信息抽取【”】。主要有两种形 第4 页 笪星三堡查兰堡主兰垡丝苎 式的信息抽取1 6 j ：一种是传统的结构化的信息抽取，主要使用了句法、语义分析【1 7 t1 3 1 ；另 一种是从半结构化信息中进行的结构化抽取，主要采用机器学习或数据挖掘技术，同时利 用了h t m l 标记、简单的语法及其定界符【9 2 0 1 。 w 曲信息是半结构化的数据，本课题主要将w 曲中结构化的数据抽取出来，例如：标 题、来源、文本大小、文件发布时间等信息抽取出来：也可进一步进行深层次信息挖掘， 例如：对于新闻文档，可以挖掘新闻涉及的人物、地点、时间、等新闻要素。同时，w 曲 噪声的净化也属于该部分内容。 1 4 3 话题检测技术 话题检测是将输入的新闻报道归入不同的话题，并在需要的时候建立新的话题。从本 质上看，这项研究等同于无指导的聚类研究，但只允许有限地向前看。通常的聚类可看作 是基于全局信息的聚类，即在整个数据集合上进行聚类，但话题检测中用到的聚类是以增 量方式进行的。这意味着，在做出最终的决策前，只能向前看有限数量的文本或报道。 话题检测作为一种增量聚类，可以划分为两个阶段：检测出新话题的出现：将描 写先前发现的话题的相关报道归入相应的话题。显然，第一个阶段就是对新发生事件的检 测，即检测出以前没有讨论过的新闻话题的出现。这个阶段也被看作是对一个话题检测系 统的透明测试，因为判断每个报道是否讨论了一个新话题，是一个话题检测系统的基础。 图2 给出了话题检测任务的一个直观图示。 已知话题一 话题二的首次报道 话题一的后续报道 话题二的后续报道 话题三的首次报道 图2 话题检测技术不惫图 话题检测可以看作是一种按事件的聚类，研究者常采用的算法有：a g g l o m e r a t i v e 聚类 【2 “、增量k m e 锄s 聚类嘲、增量聚类等。i b m 公司开发的一个相对比较成功的话题检测系 统采用了一种两层聚类策略，使用对称的o k a p i 公式来比较两篇报道的相似性。该系统首 先将报道暂时归入不同的小话题( m i c r oc i u s t 盯) ，然后在有限的延迟时间后再将其归入最 终的话题。 1 4 4 话题追踪技术 话题追踪的目的是追踪用户指定的感兴趣的话题的后继发展，判断出与之相关的事 第5 页 信息工程大学硕士学位论文 件。这项研究类似于信息检索领域中基于例子的查询以及信息过滤研究。在话题追踪中， 已知的训练正例非常少，通常事先给出一个或几个已知的、关于该话题的新闻报道；另外， 与某个话题相关的报道常常集中出现在特定的时间段内。图3 给出了话题追踪任务的一个 直观图示，其中有四个新闻报道作为正例用于训练。 关注话题 训练数据 未知数摈 ，制 _ ( k v1 rvv 、rv 测试数据 图3 话题追踪技术示意图 话题追踪系统的性能受到以下一些因素的影响：用于训练的新闻报道的数量，训练及 测试语料使用的语言。有多种不同方法在这项研究中被尝试使用，如r d c c h i o 分类方法田】、 决策树方法、基于h m m 的语言模型m2 5 1 等等，其中比较成功的是k - 近邻方法或多种方法 的组合【2 6 j 目前，话题追踪系统的性能已经达到相当高的程度，已经可以在某些特定领域用于实 用。话题检测与追踪领域的研究者为自己设立了一个更高的目标，即经过未来几年的研究 争取将话题追踪的错误率再降低一半。 1 5 论文的主要贡献和结构安捧 本文研究了w 曲新闻话题检测与追踪关键技术，主要从以下四点进行详细研究：w 曲 信息采集、网页噪声净化、新闻话题检测以及热门话题追踪。本文研究的主要贡献在于： 分析了w 曲信息采集的基本原理，并结合后续处理对采集数据的要求，设计并实现 了w 曲信息采集器； 提出一种基于向量空间模型的网页噪声净化方法，能够完整准确地去除网页噪声； 详细分析了新闻的特点，提出一种基于话题重心自适应的话题检测方法，与传统的 方法相比，该方法有效降低了话题检测的错报率和漏报率： 针对话题追踪训练正例稀疏的问题，提出一种改进的l ( 】、i n 话题追踪方法，有效地 提高了话题追踪的性能。 本文的结构安排如下： 第一章，引言。本章首先介绍本文的研究背景和课题来源，然后介绍了话题检测与追 踪的发展与研究现状，给出w 曲新闻话题检测与追踪的体系结构，并重点给出本文的主要 研究内容及采用的方法。 第6 页 信息工程大学硕士学位论文 第二章，w e b 信息采集。详细介绍了w 曲信息采集的基本原理以及各个模块的功能， 并针对实际需求，在采集过程中进行r o b o t s 分析、网页类型判断、新闻网页时间的提取。 在此基础上，设计并实现了w 曲信息采集器。实验证明，该采集器能够对网页信息进行自 动采集，并对后续的应用提供充分的支持，具有良好的通用性。 第三章，基于向量空间模型的网页噪声净化。本章首先介绍了向量空间模型的概念， 然后对网页的标记语言及结构进行了详细地分析，在此基础上结合对网页噪声的分析与数 据结构相关知识，提出一种基于向量空间模型的网页噪声净化办法。通过对比实验分析得 出结论：无论是在噪声消除的完整性还是在准确性方面，新方法均优于传统噪声净化方法。 第四章，基于话题重心自适应的话题检测。本章首先介绍了话题检测技术的概念及应 用，根据新闻信息数量大、增长快、主题相关、时效性强、动态演化等特性，结合命名实 体与向量空间模型来表示新闻文档，用类重心表示每个新闻话题。针对事件发展导致后继 故事可能判断错误的现象，提出一种基于话题重心自适应的话题检测方法。最后对2 5 个 新闻话题进行测试，结果表明，与传统的方法相比，该方法的错报率与漏报率都有所降低。 第五章，一种改进的k n n 话题追踪方法。详细介绍了话题追踪技术的概念及当前常 用的方法，针对话题追踪中训练正例稀疏的问题，对k n n 文本分类方法进行了有效地改 进并用于话题追踪，此外，还在话题追踪过程中加入时间窗策略，有效降低了计算的复杂 度。最后的实验结果也验证了这种方法优于传统的方法。 第7 页 信息工程大学硕士学位论文 第二章w e b 信息采集 在网络环境下，网络信息资源对信息获取的作用越来越大，提高网络数据的收集处理 能力，增强网络数据的利用率，实现信息处理的自动化成为信息获取研究的主要目的。本 章介绍了主流w 曲信息采集的基本原理，详细分析了w 曲信息采集器的基本结构以及各 个模块的功能。在此基础上，设计并实现w 曲信息采集系统。在实现的网页采集器中，通 过加入采集层数限制、多线程采集等规则来提高w 曲采集的效率和网页质量；还进行了 r 0 b o t s 协议分析、网页类型判断、以及新闻网页时间的提取，对传统w 曲采集器的功能进 行了扩展。实验证明，该采集器能够对网页信息进行自动采集，并对后续的应用提供充分 的支持，具有良好的通用性。 2 1w 曲信息采集概述 随着i n t c m e t 的迅速发展，网络正深刻地改变着人们的生活。而在网上发展最为迅猛 的w w w ( w 矾d w i d ew 曲) 技术，以其直观、方便的使用方式和丰富的表达能力，已逐 渐成为i n t e m e t 上最重要的信息发布和传输方式。然而，w 曲信息的急速膨胀，在给人们 提供丰富信息的同时，又使人们在对它们的有效使用方面面临一个巨大的挑战。一方面网 上的信息多种多样、丰富多彩，而另一方面用户却找不到他们所需要的信息。因而基于 w w w 的w 曲信息采集和相关的信息处理日益成为人们关注的焦点。 w e b 信息采集( w 曲c r a w l c r ) 嘲，也常称作w 曲s p i d e r 、w 曲r o b o t 和w 曲w j n n ， 是指依赖w 曲页面之间的链接关系，从w 曲上自动地获取页面信息，并且随着链接不断 向所需要的w 曲页面进行扩展的过程。粗略地说，它主要是指这样一个w 曲应用程序。 从一个初始的u r l 集合出发，将这些u r l 全部放到一个有序的待提取u r l 队列里。而 w 曲信息提取器从这个队列里按顺序取出u r l ，通过w 曲上的协议，获取u r l 所指向的 页面，然后再从这些己获取的页面中分析提取出新u r l ，并将它们继续放入到待提取u r l 队列里，然后重复上述过程，直到w 曲信息提取器根据自己的搜索策略停止采集为止i l 。 w 曲信息采集主要应用在搜索引擎和网页信息存档中，对搜集数据建立索引，提供检 索服务。其他应用包括：确认网页的有效性，站点结构分析，更新通知、镜像、个人w 曲 助理等。根据不同的应用需要，w 曲信息采集可以采用不同的策略和方法。大到为处理海 量数据而设计的具有可扩展性的w e b 信息采集系统，小到为发现专业信息而设计的专题型 w 曲信息采集系统。 2 2w e b 信息采集的结构 如图4 所示，w 曲网页采集器基本上可以划分为六个部分：u r l 处理器、网页采集器、 网页去重检测器、u r l 提取器、网页标签信息获取器和数据库。它们协调起来从w 曲上 获取信息。图中的箭头表示数据走向。 第8 页 信息工程大学硕士学位论文 图4w e b 信息采集系统框图 2 2 1u r l 处理器 这个部件主要将待采集的u i 也进行排序，并根据一定的策略向w 曲信息采集器分配 u r l 。按照采集系统规模的不同，u r l 可以是多个采集队列，也可以是一个u r l 服务器。 例如，在( b o g l e 搜索引擎的采集系统中就使用了u r l 服务器来缓存u r l ，以达到更快的 处理速度。u r l 处理器主要有三个数据来源：初始的种子u r l 集合：从u r l 采集器 传递过来的新发现的u r l 集合。它们是从己获取页面中分析得来的；页面的m e t a 信息、 主题以及摘要等信息，来自标签信息获取器，它们主要用来显示从u r l 采集器中传递过 来的u r l 的重要性，为在队列中进行排序提供依据。另外，为了加快页面采集速度，u r l 处理器通常自带了d n s 解析功能。 2 2 2 网页采集器 这个部件处于系统的底层，主要通过各种w 曲协议来完成数据的采集。一般来说，协 议包括h t t p 、f t p 、g o p h e r 以及b b s ，也有些采集系统根据应用的需要，采集w 曲c h a t 、 i c q 等特殊信息。本文主要关注的是h t t p 协议。下面简要说一下对h t t p 协议页面采集 的基本步骤： ( 1 ) 分析页面u r l ，抽出目标站点地址和端口号；若无端口号，则设为h t l 甲默认 端口8 0 。判断该站点的连接方式设置，若设为直接连接，则与该地址和端口建立网络连接： 若设为穿越p r o x y 连接，则与指定的p r o x y 地址和端口建立网络连接。 ( 2 ) 若建立网络连接失败，说明该站点不可达，中止抓耿该页面并将其抛弃；否则 继续下一步获取指定页面。 ( 3 ) 由页面u r l 组装h r r p 请求头，若该站点需要用户标识和口令，则将其填入请 求头中，发送请求到目标站点。若超过一定时间未收到应答消息，则中止抓取该页面并将 其抛弃：否则继续下一步骤分析应答消息。 ( 4 ) 分析应答头，判断返回的状态码：若状态码为2 x x ，返回正确页面，进入步骤( 5 ) ； 若状态码为3 0 1 或3 0 2 ，表示页面被重定向，从应答头中提取出新的目标u i 也，转入步骤 第9 页 信息工程大学硕士学位论文 ( 3 ) ；若返回其它状态码，说明页面连接失败，中止抓取该页面并将其抛弃。 ( 5 ) 从应答头中提取出日期、长度、页面类型等页面信息。若设置了页面抓取限制， 进行必要的判断和过滤，抛弃不符合要求的页面。 ( 6 ) 读取页面的内容。对于长度较大的页面，采用分块读取再拼接的方法保证页面 内容的完整。至此该页面的抓取完成。 2 2 3 网页去重检测器 w 曲上存在着大量的镜像页面和重复的页面内容。最近的研究表明，有大约3 0 的页 面是重复的，如不进行网页重复内容的检测过滤，将极大地浪费了网络带宽和系统的运行 效率。因此，重复内容检测是w 曲信息采集器中重要的组成部分，特别是在大型的搜索引 擎中尤为重要。在进行重复内容检测时，一般可以采用简单的段落匹配方法或者相对复杂 的相似度匹配方法。 2 2 4u r l 提取器 对于采集到的页面，通过网页去重检测后，需要分析其中的链接，并对链接进行必要 的转换以获取真实的u r l ，这些任务就是由u r l 提取器来完成的。 对一个页面中的u r l 提取工作流程如下： ( 1 ) 从页面文件队列中取出一个页面文件，如果应答头中未说明文件类型，根据u r l 中的文件扩展名补充完整。如果页面文件队列为空，跳转到步骤( 7 ) 。 ( 2 ) 判断页面是否为t c x t 、h t i l l l 、h t m 、s h t l i l l 文件。如果不是，抛弃此文件，转入步 骤( 1 ) ，否则转入步骤( 3 ) 。 ( 3 ) 从文件头按顺序读取文件，遇到如下标记 、 、 、 、 、 、 等， 记录其中的u r l 连接。如果遇到文件结束符，则跳转到步骤( 7 ) 。 ( 4 ) 将提取出来的u r l 链接按照预先定义的统一的格式补充完整。一般页面链接中 给出的u r l 可以是多种格式的，可能是完整的、包括协议、站点和路径的，也可能是省 略了部分内容的，或者是一个相对路径。因此，根据初始的u r l 将这些链接补充为完整 格式。 ( 5 ) 记录下 、 、 、 、m g s r c = 、 、锄p l c tc o d e - 等后面对此链接的说明信息a 在网页噪 声去除工作中会用到这个信息。 ( 6 ) 存储此u r l 及其扩展元数据，跳转到步骤( 2 ) 。 ( 7 ) 页面u r l 提取完毕。 2 2 5 标签信息提取器 该部件所要获取的信息包括己提取页面的m e t a 信息、作者信息、页面的标题、页面 第1 0 页 焦：垦三堡盔兰婴主兰垡丝奎 的摘要等。主要目的是在没有对页面内容进行语义信息理解的前提下，尽可能多的挖掘出 h 聊l 标签、结构等信息，对从页面中提取出来的u r l 质量的好坏给出一个度量，然后 再传输到u r l 处理器，对待提取u r l 队列进行排序。 其中，页面中标题的提取分为3 步： ( 1 ) 判断正文开始的位置，从文章开头开始，逐段扫描，直到某一段长度不小于设 定的正文最小长度，就假定这段为正文中的一段。 ( 2 ) 由正文位置向前搜索可能是标题的一段，根据字体大小、是否居中、颜色变化 等特征找出最符合的一段文字作为标题。 ( 3 ) 由所给参数调整标题所在的段，使标题提取更准确。句法、语义、统计分析标 题段的前后几段，以准确确定标题段的真实位置。 2 2 6 数据库 通过网页去重检测后的页面数据、提取出来的m e t a 信息、作者信息、主题和摘要等 均需存入数据库中，以备使用。例如，进行分析建立索引等。由于w 曲页面规模的庞大， 提取的相关数据在存入数据库之前，一般要进行压缩处理。 2 3w 曲信息采集的扩展 本章的w 曲信息采集器是为后续工作提供所需的新闻网页数据，我们通过分析w 曲 实际采集过程中的难点，并结合后续工作对网页质量的要求，对w 曲信息采集器作了四项 扩展：r o b o t s 协议分析、网页类型判断、新闻时间提取、网页噪声净化。其中，网页噪声 净化在下一章中详细讲解。 2 3 1r 0 b o t s 协议 为了让网站自身被搜索者查看，吸引更多的访问者，也为了规范搜索引擎的行为，1 9 9 4 年i b