（计算机应用技术专业论文）web信息检索与主题提取的关键技术研究.pdf

复旦大学硕士学位论文摘要 摘要 随着i n t e m e t 及大容量存贮技术的迅速发展，w e b 上的信息日益丰富。从海量、异构的 w e b 信息源中获取用户所需要的知识是一项很难的事情，同时也是一项亟需解决的问题。 g o o g l e ，a l t a v i s t a 及百度等搜索引擎的出现，为用户在互连网查找信息提供了便利，但是目 前搜索引擎返回的文档质量参差不齐，难于满足用户对高质量检索结果的需求。针对目前w e b 检索结果质量不高的现状，“寻找与用户查询相匹配的高质量文档”也就是“主题提取”成了 w 曲信息检索的研究热点。 本文对目前信息检索的各种关键技术进行了概述：介绍了传统的文档检索模型以及三种 经典的链接分析算法，并对评测文档检索性能的各项指标进行了简要介绍。 在现有基于内容匹配的布尔扩展模型最短片断模型的基础上，提出了一种使用链接 语义分析的主题提取算法。通过引入概念层次树及使用概念距离来计算网页间的相似度，改 进了h i t s 算法中扩展集的质量，从源头有效地抑制了链接分析算法的主题漂移现象；通过 链接分权以及结合文档的内容语义，消除了垃圾链接并进一步排除了与查询主题无关的页面。 最后，通过对文档的页面内容，结构信息，锚文本信息以及链接信息等特征的综合评分，得 到最终的返回结果列表。实验表明，这种方法行之有效，能够较大程度地改善主题提取的质 量。 最后设计并实现了基于以上算法的w e b 信息检索系统，并对其中的主要数据结构及索引 创建过程进行了介绍。在t r e c2 0 0 3 的主题提取任务上的实验表明，性能得到了较大的改善。 论文最后对实验结果进行了比较分析。 关键词：w e b 信息检索，主题提取，关键资源，链接分析，锚文本 中图分类号：t p 3 9 1 复日+ 大学硕士学位论文 摘要 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e m e ta n dm a s ss t o r a g et e c h n o l o g y , t h ei n f o r m a t i o ni nt h e w e bi n c r e a s i n g l ya c c u m u l a t e s t or e t r i e v et h eu s e f u lk n o w l e d g ef r o mt h eh e t e r o g e n e o u sa n dh u g e w e bi n f o r m a t i o ns o u r c e si sn o to n l yad i f f i c u l tt h i n gb u ta l s oad e s i d e r a t ep r o b l e mt ob es o l v e t h e a d v e n to fs e a r c he n g i n es u c ha sg o o g l e ，a l t a v i s t aa n db a i d u ，e t c h a sf a c i l i t a t e dt h eu s e r si nt h e s e a r c h i n gf o rm a t e r i a l s b u tt h eq u a l i t yo fd o c u m e n t sr e t u r n e db yt h es e a r c he n g i n ei sn o ts og o o d a n dc a nn o ts a r i s 句t h eu s e s r e q u i r e m e n t sf o rh i g hq u a l i t yd o c u m e n t s “t h ep r o c e s so ff i n d i n gq u a l i t y d o c u m e n t sr e l a t e dt oau s e rq u e r y ”，i e ， t o p i cd i s t i l l a t i o n b e c o m e st h er e s e a r c hh o t s p o ti nt h ew e bi n f o r m a t i o n r e t r i e v a lf i e l d i nt h et h e s i st h ea u t h o ri n t r o d u c et h ek e yt e c h n o l o g i e si nt h ew e bi n f o r m a t i o nr e t r i e v a l ：i n c l u d i n gt r a d i t i o n a l d o c u m e n tr e t r i e v a lm o d e l sa n dt h r e ek i n d so fc l a s s i c a ll i n k a g ea n a l y s i sa l g o r i t h m s t h ep r i m a r y i n d i c e so fe v a l u a t i n gt h er e t r i e v a lp e r f o r m a n c ea r ea l s oi n t r o d u c e dc o n c i s e l y a t o p i cd i s t i l l a t i o na l g o r i t h mb a s e do nt h ee x t e n d e db o o l e a ns e a r c hm o d e l _ s h o r ts u b s t r i n g s e a r c hm o d e lh a sb e e np r o p o s e d t h ea l g o r i t h mu s e st h el i n k a g es e m a n t i ca n a l y s i st oi m p r o v et h e h i t sa l g o r i t h m ：t h eu s eo fh i e r a r c h yc o n c e p tt r e ea n dc o n c e p td i s t a n c eh a si m p r o v e dt h eb a s es e t sq u a l i t yi n h i t sa l g o r i t h m ，a ss u c c e s s f u l l ys o l v e st h et o p i cd r i f tp h e n o m e n o ni nt h el i n k a g ea n a l y s i sa l g o r i t h m ；t h ef r a c t i o n a l w e i g h t so fl i n k a g ea n dc o m b i n a t i o no fc o n t e n ta n a l y s i sh e l pt oe l i m i n a t et h en o i s el i n k a g e sa n df u r t h e rw i p eo u t t h en o n - r e l e v a n tp a g e s i nt h ee n d ，w eg e tt h er e s u l tl i s to nt h eb a s i so fs c o r eo fd o c u m e n tc o n t e n t ，s t r u c t u r e i n f o r m a t i o no fd o c u m e n t ，l i n k a g ei n f o r m a t i o n ，a n c h o rt e x t ，u r la n ds oo n t h ee x p e r i m e n t ss h o wt h a t t h em e t h o di se f f e c t i v et oi m p r o v et h eq u a l i t yo f t o p i cd i s t i l l a t i o na n de n h a n c et h eu s e r s r e t r i e v a le f f i c i e n c y i nt h ee n dt h ew b bi n f o r m a t i o nr e t r i e v a ls y s t e mb a s e do nt h ea b o v ea l g o r i t h mi sd e s i g n e da n d i m p l e m e n t e d i nt h et h e s i sw ed e s c r i b et h es y s t e m sa r c h i t e c t u r ea n di m p l e m e n t a t i o nm e t h o d si n d e t a i ls u c ha sm a j o rd a t as t r u c t u r ea n dt h ep r o c e s so fc r e a t i n gi n d e x e t c 1 1 1 ee x p e r i m e n t so nt h e t r e c2 0 0 3t o p i cd i s t i l l a t i o nt a s ks h o wt h a tt h er e t r i e v a lp e r f o r m a n c ei si m p r o v e dg r e a t l y t h e e x p e r i m e n t s r e s u l t sa r ea l s ol i s t e da n da n a l y z e db yc o m p a r i s o n k e y w o r d s ：w e bi n f o r m a t i o nr e t r i e v a l ，t o p i cd i s t i l l a t i o n ，k e yr e s o u r c e s ，l i n k a g ea n a l y s i s ，a n c h o rt e x t i i 复旦大学硕士学位论文第一章绪论 1 1 研究背景与意义 第一章绪论 随着计算机技术与网络技术的发展，i n t e m e t 上的可得资源日益丰富，信息 发布及更新的速度远远大于整理、利用信息的速度。据【1 】统计，在2 0 0 3 年， i n t e r n e t 上能够公开访问到的不同网站超过了5 0 0 0 万个，网页总容量约为1 6 7 t b ； 另一方面，信息增长态势更为惊人，据【2 】的调查显示：2 0 0 4 年网页总数同期相 比增长1 0 8 6 ，呈现出逐年翻番的几何增长的势头。 极大丰富的w e b 资源导致了信息过载乃至信息爆炸现象。要从海量的w e b 信息源中检索到自己所需的资料，若不借助于合适的工具，单靠人工浏览网页来 查找，则无异于大海捞针，事倍功半，甚至于徒劳无功。 在这种背景下，搜索引擎应运而生，并且获得了极大的成功。现今最为有名 的搜索引擎g o o g l e ，a l t a v i s t a ，i n f o s e e k ，l y c o s 及百度等的存在为用户在互连网 上查找信息提供了便利，成了人们获取信息的得力工具。但是由于w e b 上的信 息是如此巨大，导致搜索引擎返回的文档质量良莠不齐，主题漂移等现象屡见不 鲜，因而它们很难满足用户对高质量检索结果的需求。如何在现有各种文本检索 技术的基础上，通过充分利用文档的各种特征，自动快捷地获取与用户查询相匹 配的高质量资源的需求日渐凸显。这种为获得与用户查询相匹配的高质量文档的 信息检索过程也被称为主题提取 3 ，是当今w e b 信息检索领域的一个研究热点 【4 】【7 】。 另一方面，这类从海量文本信息中迅速有效地找到所需要的信息的技术又是 计算技术领域最有可能首先取得突破并获得实际应用的方向。著名期刊b y t e 曾有文章预测：这类信息检索与数据挖掘软件将成为继文字处理软件、表处理软 件之后未来最重要的五种软件之一：其有着十分广阔的应用领域和市场价值 8 】。 本文主要研究w e b 信息检索与主题提取中的各种关键技术，并探求如何在 现有各种文本检索技术的基础上，通过充分利用文档的各种特征如页面文档内 容，文档结构信息，链接信息，锚文本信息以及u r l 等来改善主题提取的质量， 提高用户信息检索的效率，从而使用户更有效地利用w e b 上的信息来创造价值。 1 2 信息检索的历史 从大量的纷繁复杂的信息源中查找信息的历史由来已久：从最早的模式匹配 到图书馆中的书目查询，科技文献检索，数据库系统中的数据查询以及数据挖掘 1 复旦大学硕士学位论文 第一章绪论 等等，发展到小规模的，研究性语料库中的文本检索，以及对海量、异构的w e b 数据源的搜索，乃至今天的对返回文档的质量要求很高的主题提取。可以说信息 检索沿着从简单到复杂，数据量从4 , n 大，对检索的质量要求从低到高的趋势不 断向前发展。 目前w e b 检索具有十分巨大的应用需求，然而其性能远远未能达到用户的期 望。w e b 检索主要的难点还在于在于文本检索。对于无结构的文本检索，存在着 传统的基于语言学和人工智能的方法( 即理性主义) 以及基于语料库和统计语言 模型的新方法( 即经验主义) 这两大阵营【9 。 最早得到发展的是基于语言学和人工智能的方法，这种方法通过制定一些规 则并进行语法分析来理解自然语言文本 1 0 1 1 1 ，在小规模的，实验性的研究测 试中具有较好的效果。其中具有代表性的是采用移位规约算法的l r 语法分析方 法 1 0 】和采用图结构进行语法分析的图算分析方法 1 2 】。然而当处理对象从小规 模受限语言处理走向大规模真实文本处理时，该方法显示出局限性：其所需的大 量的知识和推理规则十分匮乏( 收集整理全部所需的知识和推理规则是一个长期 的，系统的过程，少数人难以在短时间内完成) ，并且还需要极大的计算量；这 些瓶颈导致了该方法在分析大规模的真实文本时效率的低下和精度的急剧下降 1 3 。 当前信息检索的重心由基于语言学的方法转向了基于统计学的方法，常见的 三种文本表示模型向量空间模型( v e c t o rs p a c em o d e l ，v s m ) 1 4 ，概率模型 1 5 】 和语言模型 1 6 】中都用文档和查询中的词频( t e r mf r e q u e n c y ，t f ) 和倒排文档频率 ( i n v e r t e dd o c u m e n tf r e q u e n c y ，i d f ) 来表示文档和查询的内容，其本质是一种统 计方法 1 7 】。 向量空间模型 1 4 】是由s a l t o n 等人于6 0 年代末提出，并成功地应用于著名的 s m a r t 系统，通过假定文档的特征间的相互独立，该模型对文档的表示进行了 简化，两个文档问内容相似度通过用于表示文档的向量之间的相似性来度量，最 常用的是余弦距离。 s p a r kj o n e s 和s r o b e r t s o n 提出的概率模型综合考虑了词频、文档频率和文 档长度等因素，把文档和查询按照一定的概率关系融合，形成了o k a p i 系统中著 名的b m 2 5 公式 1 8 】 1 9 ，在信息检索领域获得了很大的成功。 此外，许多研究人员也在尝试采用规则和统计相结合的研究思路，这也是将 来很可能出成果的方向。这方面的较有代表性的研究有：概率化的图分析器 2 0 ， 概率l r 分析算法研究 2 1 ，采用e b m t 技术的排歧策略 2 2 ，利用语法规则和 经验模式进行句法功能标注 2 3 等。 2 复旦大学硕士学位论文第一章绪论 1 3w e b 信息检索的新趋势 与通常的文本检索相比，w e b 信息检索有着以下一些的特点： 1 w e b 上的文档分布于异构的各个网站中，其网页数量极大； 2 网页是一种半结构化文档，页面具有一定的描述层次，存在着一定的结 构； 3 网页之间还具有很强的互连性。研究数据表明f 2 4 ，平均每个网页拥有 2 3 个内部链接和5 6 个外部链接。网页的这些特性使得i n t e r n e t 与其他的信息源 有着巨大的区别，对传统信息检索技术提出了新的挑战； 3 ，网页质量参差不齐，搜索引擎垃圾( s p a m m i n g ) 现象屡见不鲜； 4 由于网页链接的存在，网页问存在着错综复杂的联系；互联网的超链接 拓扑结构同时孕育着传统数据环境所没有的另一种丰富信息。越来越多的学者已 经开始致力于这方面的研究。新一代的搜索引擎普遍利用链接信息提高了w e b 检索的准确率和召回率 5 用户进行w e b 查询时，偏向于用一两个简短的查询词来表示查询，致使 查询主题的意思表示很不充分，并常常带有二义性和多义性。 针对w e b 文档的上述特点，不少学者致力于如何充分利用一个系统框架来 统一地利用它们，但要将这些特征特别是将链接信息纳入到一个综合的语义相关 度计算的框架里，却是一个非常难解决的问题。 对于半结构化的w e b 网页文档而言，链接结构是一个很重要的特征，有效 地利用它能够显著地提高w e b 检索的性能；这点在商用的搜索引擎上得到了证 实。但是，针对某个固定的语料集，一系列的实验都没有体现出链接信息的使用 对于查询质量改善的作用。链接方法中存在的基本假设：如果网页a 有链接指 向网页b ，则认为b 和a 相关。但是，假设中的这种相关并不一定指是内容上 的相关，更不一定是语义的相关。因此，将单纯的链接相关的网页作为文档相关 度的依据，对链接信息使用有断章取义的意味，效果往往与愿望背道而驰。 为了更好地利用链接信息，必须将其与文档内容的语义结合起来。我们知道， 自然语言文本中的词汇( 术语) 具有一词多义( p o l y s e m y ) 和一义多词( s y n o n y m y ) 的 特点：由于一词多义，基于精确匹配的检索算法会报告许多用户不要的东西； 由于一义多词，基于精确匹配的检索算法又会遗漏许多用户想要的东西。 如何有效地解决上述问题，不少学者提出了不同的解决方案。 s u s a nt d u m a i s 提出的潜在语义索引( l a t e n ts e m a n t i ci n d e x i n g ，简称l s i ) 2 5 1 成功地用解决了自然语言理解的难题。该方法用以术语( t e r m s ) 作为行，文件 ( d o c u m e n t s ) 作为列构建一个大矩阵。设矩阵一共有t 行d 列，矩阵名为x ，矩阵 的元素为术语在文件中的出现频度。数学上可以证明：x 可以分解为三个矩阵 一3 一 复旦大学硕士学位论文 第一章绪论 t o ，s o ，d o ( d o 的转置1 的积，其中t 0 和d o 的列向量都是正交归一化的，s o 是对角矩阵t o 是t + m 矩阵，s o 是m * m 矩阵，d o 是d * m 矩阵，m 是x 的秩。 这种分解叫做单值分解( s i n g l a rv a l u ed e c o m p o s i t i o n ，s v d ) ，如公式( 1 1 ) 所示。 x = t 0 * s 0 * d 0 ( 1 1 ) 给定了矩阵x ，基于x 可以解决以下三类问题： 第一类问题是术语的类比和聚类问题； 第二类问题是文件的类比和聚类问题； 第三类问题是术语和文件的关联问题。 l s i 绕过自然语言理解，使用统计的方法反映术语之间内在的相关性，同时 又具有较高的效率。 也有学者利用网页的其他一些特征信息来调整链接算法中的链接权重计算， 以此来降低垃圾链接的干扰，提高了检索的准确率。微软亚洲研究院提出了一种 w e b 链接分析的统一框架 2 6 ，把h i t s 算法扩充到两个集合上：网页集和用户 集。利用用户之间的关系及用户和网页之间的关系，调整网页之间的链接权重， 准确地检索到用户需要的网页。 g l e nj e h 等人 2 7 提出衡量个性化w e b 检索的策略，根据用户喜欢浏览的网 页集，确定其个性化的p a g e r a n k 向量( p e r s o n a l i z e dp a g e r a n kv e c t o r ，p p r v ) ， 以此来提高检索结果的质量。 对于s p a m m i n g ，著名的搜索引擎g o o g l e 通过对p a g e r a n k 进行了相应的调 整来提高其对各类作弊方式的监测灵敏度，如对桥页、i pc l o a k i n g 、泛滥链接 ( l i n k f a r m ) 、f f a 链接等进行惩罚；d m o z ，y a h o o ! 等分类目录使用“权威的 非关联外部链接”作为决定排名的重要因素的作法也值得借鉴。 此外，w e b 页面的u r l 可能会反映页面的类型，也可能反映页面之间的目 录结构关系，有效地使用它也有助于改善检索的返回结果集的质量。 综上，链接信息需要和其他信息配合起来，特别是与文档内容及锚文本的语 义以及文档结构，u r l ，m e t a 标签等一些网页特征结合起来，才能真正提高检 索性能。 1 4t r e c 综述 文本检索会议( t e x tr e t r i e v a lc o n f e r e n c e ，简称t r e c ) 2 8 是当前文本检索 领域最权威的国际会议之一，代表了当今世界文本检索领域的最高水平。它是由 美国国家技术标准局和国防部高级研究计划局组织召开的一年一度的国际测评 会议；旨在通过提供规范的大规模语料( g b 级) 和对文本检索系统性能客观、公 正的评测来促进技术的交流和发展；促进政府部门、学术界及工业界间的交流与 4 复旦大学硕士学位论文第一章绪论 合作；加速技术的产业化，发展对文本检索系统的评测技术。从1 9 9 2 年第一届 会议开始，迄今已举办了1 3 届。由于该会议的重大影响力，吸引了众多公司， 高校及研究组织的参加。表1 ，表2 及表3 列出了历届t r e c 参加单位数，相关 任务及部分参加单位列表【2 9 】。 表1 ：历届t r e c 的设立的任务和参加的单位数 任务t r e c lt r e c 2t r e c 3t r e c 4t r e c 5t r e e 6 a dn o c1 82 42 62 32 83 l r o u t i n g 1 62 52 51 51 62 l i n t e r a c t i v e31 129 s p a n i s h 41 07 c o n f u s i o n45 d bm e r g i n g33 f i l t e r i n g 471 0 c h i n e s e91 2 n l p 42 s p e e c h 1 3 c r o s s l a n g u a g e 1 3 h i g hp r e c i s i o n 5 v l c q u e r y q a w e b v i d e o n o v e l t y g e n o m e h a i l d r o b u s t 参赛单位 2 23 l3 33 63 85 1 表2 ：历届t r e c 的设立的任务和参加的单位数( 续) 任务 t r e c 7t r e c 8t r e c 9t r e c l 0t r e c l lt r e c l 2 a dh o c4 24 1 r o u t i n g i n t e r a c t i v e87666 s p a n i s h c o n f u s i o n d bm e r g i n g f i l t e r i n g 1 21 41 51 02 1 c h i n e s e n l p s p e e c h 1 01 03 c r o s s l a n g u a g e 91 31 61 09 5 复日大学硕士学位论文 第一章绪论 v l c76 q u e r y 2 5 6 q a 2 0 2 8 3 63 43 3 w e b 1 7 2 33 02 3 2 7 v i d e o1 21 9 n o v e l t y 1 31 4 g e n o m e 2 9 i a i m1 4 r o b u s t 1 6 参赛单位5 6 6 6 6 9 8 79 3 9 3 表3 ：参加过t r e c 的部分单位 公司大学亚洲参加单位 瓯dm r r s i n g a p o r eu ( k r d l ) b n n c m u k o r e au m i c r o s o f t c a m b r i d g eu a j o uu s u nc o r n e l iu p o h a n gu a p p l e n a l a n du y o n s e iu f u j i t s u m a s s a c h u s e t t su t s i n g h u au ( l a i w a n ) n e cn e wm e x i c os t a t eu t a i w a nu x e r o xc a l i f o r n i ab e r k e l e yu h o n g k o n gc h i n e s eu i b mm o n t r e a iu m i c r o 航r e s e a r c ha s i a c l r r r e c h3 0 h n sh o p k i n su f u d a nu n r r r u t g e r su c a s o r a c l ew a t e r l o ou t s i n g h u au r i c o h p e n n s y l v a n i au s h a n g h a ij i a o t o n gu - l e x i c i o n ed u b l i nc i t yu t o k y ou 从表中我们可以看到参赛单位数量逐年增多，参赛项目常常推陈出新。但几 乎历届会议均包含文本检索( a dh o c 及其替代任务w e b ) 和文本过滤( r o u t i n g 及 其替代任务f i l t e r i n g ) 这两个项目。它们可谓是奥运场上的“田径”和“游泳”， 历年都吸引了众多的参加单位。这种现象不是偶然的，因为这两个目前技术应用 最广泛的信息检索项目，对应了信息检索的两个基本模式：信息的“推和拉”。 特别值得一提的是，复旦大学，微软亚洲研究院，清华大学和中科院计算所 等是第一批来自中国大陆的参加单位。在吴立德老师、黄萱菁老师、牛军钰老师 的指导下，作者参加了第十三届t r e c 会议( t i 也c2 0 0 4 ) 的w e b t r a c k 项目。 6 复旦大学硕士学位论文第一章绪论 1 5w e b 项目与t o p i cd i s t i l l a t i o n 子任务 w e b 检索项目始于1 9 9 9 年的第八届文本检索会议，其目的是针对w e b 建立 一个框架，使得研究者能够可靠地检验新的w e b 检索技术 3 0 1 。它是对a dh o e 即传统检索项目的延伸。w e bt r a c k 开始使用的是有1 6 m 个网页的w t l o g 文档 集，它有两个任务：t o p i cr e l e v a n c e 任务和h o m e p a g ef i n d i n g 任务。 w e b 项目中先后设立了从t r e c2 0 0 2 开始，w e bt r a c k 用的文档集是g o v 文档集。这个文档集是通过对美国政府网站抓页获取的。它包括大约1 m 个网页 和大约2 5 0 k 个非h t m l 文档( d o c ，p d f , p s 等) 。它的字节数达到了1 8 1 9 i g a b y t e 。 t o p i cd i s t i l l a t i o n ( t p ) 是w e b 项目中的一个子任务，始于2 0 0 2 年的t r e c 1 1 ，目的是找到与给定主题相关的关键资源，t o p i cd i s t i l l a t i o n 任务目标是 查找关键资源 3 1 3 2 。与搜索引擎所返回的相关文档相比，关键资源数量更少。 比如我们要查找与“复旦大学”相关的网页，则网站h t t p ：w w w f u d a n e d u c n 下的各子站点网页都是相关的，而对于t o p i cd i s t i l l a t i o n 而言，只有h t t p ： w 啊f u d a n e d u c n 这个网址所对应的复旦大学的主页才是关键资源。界定关 键资源有助于减少返回的检索结果数量。 关键资源的内容与它的链接、目的相比，可能更不重要。很多网站的主页并 没有提供很多详细的内容信息，但是却包含了大量指向能提供详细信息的网址。 例如：对于查询“复旦大学”而言，h t t p ：w w w f u d a n e d u c n 是一个关键资 源。 关键资源与分类目录也是有区别的，关键资源提供的是关于某个主题( 用户 查询) 的k e yr e s o u r c e s ，而分类目录是不考虑主题的。关键资源还可以是以下 几种网页： 1 ) 和某个主题高度相关的网站的主页或子网站的主页； 2 ) h u b 页( 即包含有很多指向相关网页链接的网页) ； 3 ) 一个对用户非常有用的服务。比如h t t p ：w w w n a sa g o v s e a r c h 提供 了n a s a 网站的检索服务，如果用户想了解n a s a 的信息，则这个检索服务将非常 重要； 4 ) 同一个网站包含的关键资源一般不会超过2 个； 5 ) 一个网站里存在确定级别的目录和主题相关，如 w w w w h i t e h o u s e g o v h i s t o r y 对应查询主题“w h i t eh o u s eh i s t o r y ”。 根据关键资源的含义，我们可以看出，在w e b 项目的主题提取任务中，单纯 利用文档正文内容的统计信息是不够的，必须充分使用w e b 文档文件的链接结构 信息，锚文本信息，u r l 信息等特征来调整，优化，才有可能得到较好的结果。 在国内，清华大学、中科院计算所、微软亚洲研究院、复旦大学等机构也在 7 复旦大学硕士学位论文 第一章绪论 进行包括中英文在内的多语种的w e b 信息检索研究，并且参加了t r e c 、m u c 等国 际会议，取得了可喜的进展 3 3 ，3 4 。 1 6 本文的组织结构 本文共五章，各章节的内容具体安排如下： 第一章是绪论，介绍了文本的研究背景与意义，信息检索的历史与现状，然 后对与本文密切相关的t r e c 会议进行了综述，简要地介绍了w e b 项目的主题提 取任务，并详细地阐述了关键资源的含义。 第二章介绍了信息检索的一些基本理论：包括信息检索的相关术语；信息检 索一般体系结构：三种传统的信息检索模型；常用的权重评价方案以及三种经典 的链接分析算法。最后还介绍了评测检索性能的各项评价指标。 第三章介绍了一种基于最短片断检索模型和链接语义分析的主题提取算法， 通过引入概念层次树及使用概念距离来计算网页间的相似度，改进了h i t s 算法 中扩展集的质量，从源头有效地抑制了链接分析算法的主题漂移现象；通过链接 分权以及结合文档的内容语义，消除了垃圾链接并进一步排除了与查询主题无关 的页面。最后，通过对文档的页面内容，结构信息，锚文本信息以及链接信息等 特征的综合评分，得到最终的返回结果列表 第四章实现了基于以上算法的信息检索系统，并在t r e cw e b 项目上进行了 实验，最后对实验结果进行了分析。 第五章对本文的内容进行总结，并对未来的研究前景作了展望。 8 复旦大学硕士学位论文 第二章信息检索的理论基础 第二章信息检索基础理论 2 1 相关术语与定义 信息检索( i n f o r m a t i o nr e t r i e v a l ) ，泛指用户从各种信息集合中查找所需要 知识的过程；一般情况下指文本信息检索( 故常常也被称为文本检索) 。它包括信 息的存储、组织、表现、查询、存取等各个方面，其核心在于为文本信息编制索 引并进行检索。从历史上看，信息检索经历了手工检索、计算机检索、网络化检 索以及智能化检索等多个发展阶段。 在信息检索领域，将待检索的记录称为文档，而将被检索的文档集称为语料 集。语料集通常是静态的，具有固定的内容。与数据库中有固定语义的结构化记 录不同，用于信息检索的文档通常由无结构或半结构化的自然语言文档组成。然 而，无结构的文档却常常具有结构化的标题部分。例如：一本书，杂志或一篇论 文通常含有作者，题目，出版日期，主题及摘要等，这些元数据信息构成了文档 的标题部分，而书的具体内容则由风格不定，形式千变万化的自然语言构成。而 有些文档，常常具有一定的结构与语义，比如对于某个介绍国家信息的文档集而 言，每个文档含有对不同国家的介绍：第一段常常是地名，位置以及人口状况等 信息；第二段则可能是该国的主要工业状况的介绍，等等。这种文档集常常被称 为半结构化的文档集 3 5 1 。 文本检索侧重于对无结构化的文档进行查找，但是被提交的一个检索请求 ( 通常称为查询主题) 常常既可能针对文档的有格式部分( 如作者) ，又可能针对文 档的无结构化的内容部分( 如关于某一个特定主题) 。 此外，文本检索和文本过滤有很大的相似之处。文本过滤本质上来说是判断 文本是否符合用户需求，因此可以把文本过滤看成一个两类( 是否) 的分类问 题；而它和给定检索需求，从文本库中搜索相关文本的文本检索非常相似；所不 同的是文本检索有相对固定的文本库和千变万化的检索需求，而文本过滤则有着 相对固定的用户需求和动态变化的文本流。可以说，文本过滤和文本检索是同一 硬币的正反两面 3 6 1 。 2 2 检索模型与体系结构 传统的信息检索系统及算法通常都是为特定语料集设计的。这些语料集相对 i n t e r n e t 上的信息来说，具有规模较小、内容较为一致等特点，如新闻报道库或 ( 真实) 图书馆的目录等【3 7 】。当前，互联网的发展推动了信息检索技术的发展 9 复旦大学硕士学位论文 第二章信息检索的理论基础 和应用，一大批商业搜索引擎应运而生，为用户进行快速信息获取和信息导航提 供了便利。当前，信息检索已经发展到网络化和智能化的阶段。信息检索的对象 从相对封闭、稳定一致、由独立数据库集中管理的信息内容扩展到开放、动态、 更新快、分布广泛、管理松散的w e b 内容。 i n t e m e t 上的检索系统，也就是通常说的搜索引擎，是在传统的信息检索系 统上的改造与扩充。w e b 搜索引擎和传统信息检索系统主要有不同两个方面：一 是数据量大小不同，传统信息检索系统一般索引库的规模多在g b 级，而w e b 信息检索则要处理几千力甚至上亿的网页；二是检索要求不同，w e b 信息检索的 信息极多，查准和排序就显得特别重要，而查全率显得相对次要。 现有的w e b 搜索引擎虽然能够便捷地帮助用户找到所需要的文档，但是返 回给用户的是一批原始的相关文档列表，常常还需要用户在长长的列表中再次通 过逐项浏览来寻找满足自己需求的相关文档，通常的状况是：用户需要的文档往 往淹没在“垃圾文档”中。因此，商用的搜索引擎还是不能高效、准确地反馈给 用户最需要的信息；w e b 信息检索还有很大的优化余地。必须通过对原始的相关 文档做进一步的优化处理，以便得到更加符合用户需求的信息。 这里我们把信息检索的任务看作“是在给定用户的信息需求后，从文档集中 识别出最为匹配的文档”。其过程及组成部分如图2 1 所示 3 8 。 图2 1 信息检索的一般模型 图中的模型主要包括： 文档模型：即文档的索引，也就是文档的识别和表示，包括语义内容和 1 0 复旦大学硕士学位论文第二章信息检索的理论基础 上下文属性( 如作者，编辑者及文档的索引等) 。 查询模型：即用户需求信息的获取与表示。 匹配函数：即在文档表示和查询表示的基础上，定义查询和文档的相关 程度函数。 性能评价：一般采用精度( p r e c i s i o n ) 和查全率( 也称为召回率，r e c a l l ) 对 检出的文本进行评价，处理速度有时也用于评价系统的效率。 相关反馈：根据检索出的结果对查询表示( 少数情况下也对文档表示) 进行扩充与参数化，以提高系统性能。 任何一个检索模型都有其理论基础和相关假设，上述检索模型存在的普遍性 假设有： 夺被检索对象主要为文档对象。 夺对象的检索与其他对象是否被检出无关，具有独立性( 按类别检索时显 然是不合适的) 。 夺检索是根据文档内容的表示及所需信息的表示进行的。 夺文档内容和所需信息的表示都是非精确的。 和传统的信息检索系统相类似，w e b 搜索引擎的目标同样是向用户提供一系 列满足用户查询的文档。但此时用户希望系统能够找到在i n t e m e t 上满足他需求 的网页文档。对于w e b 检索，用户提交的查询主题词一般都较短：2 5 个单词， 然而用户却希望在返回的文档列表能够在尽可能靠前的文档中包含相关文档。由 于i n t e m e t 环境的异构，分布和数据海量的特点，w e b 搜索引擎的体系结构也比 传统的检索系统要复杂一些，通常的系统结构如图2 2 所示 3 9 1 ： 图中的模块主要包括： 用户查询界面：根据用户给出的查询，利用已有的索引信息来返回与用户查 询相关的网页文档列表。 抓取器：完成对i n t e r n e t 上网页信息的抓取，将得到的页面存放在页面存储 库d p ( p a g er e p o s i t o r y ) 。这些抓取器由抓取器控制模块进行控制。 页面存储库：用来存放由抓取器获得的原始页面文档。同时为索引模块和分 析模块提供相关接口来处理页面。 索引模块：对存放在页面存储中的原始网页文档制作索引。通常包括文本索 引( 内容索引) 和( 链接索引) ， 分析模块：生成其他一些索引信息，如网站的点击率、更新频率、访问量及 页面的重要度等。 排序模块：将查询引擎的输出结果进行重排序以进一步提高检索的精度。 复旦人学硕士学位论文第二章信息检索的理论基础 页面存储库 图2 2w e b 搜索引擎的一般体系结构 2 3 传统的信息检索模型 我们知道，目前信息检索主要有两大类的方法，基于语言学和人工智能的方 法( 即理性主义) 以及基于语料库和统计语言模型的新方法( 即经验主义) 。目 前得到广泛应用的是基于语料库和统计语言模型的方法，而基于语言学和人工智 能的“理性主义”方法一般被结合到“经验主义”方法之中。 6 0 年代中期以来，人们提出了大量检索模型。自最初的为一些较小的和较 为结构化的文档所设计的特殊模型( 如文献记录，包括题目、作者和主题码等) ， 发展到现在具有较强理论基础和能处理多种文档格式的模型。当前的模型能够处 理具有复杂内部结构的文档，并且一般都具有学习和利用相关反馈进行查询优化 等功能，使得系统性能大大提高。 传统的信息检索模型主要有三种 3 8 ： 严格匹配模型。它是许多商业信息检索系统的理论基础。 概率模型。把检索看作是文档表示和查询之间匹配程度的概率估计问题。 向量空间模型。把文档和查询看作是多维向量空间中的向量，用距离作为 相似度的度量。 传统的信息检索模型用称为索引项的关键词来表示一篇文档。索引项可以是 1 2 复旦大学硕士学位论文第二章信息检索的理论基础 字、词或词组。将一篇文档表示成了一批索引项的集合后，我们就会发现不同的 索引项对描述这篇文档所起的作用是不一样的。通常我们认为如果一个词在每篇 文档都出现，那么它对描述文档起不到任何作用；如果一个词只在很少的文档中 出现，那么这个词就能显著缩小我们需要检索的空间，即它对描述这篇文档能起 到很大作用。这就引出了权重的概念。 令k ，表示一个索引项，d 。表示一个文档，w 。0 表示索引项k ；在文档d ，中 的权重。权重w 。量化了项k 。对描述文档d j 所起到的作用。 定义：令t 表示文档集里所有不同索引项的数目，k 。表示一个索引项。k = k ， k 。，k 。 表示索引项构成的集合。 对于文档d ，中有的索引项k 。，权重w 。 o 。对于文档d 。中没有的索引项k 。， 权重w 。= o 。这样我们就可以将文档d ，表示成一个向量西= ( w 。，w ：。，w 。) 。 向量d 。的第i 维就对应于项k 。在文档d 。中的权重。 2 3 1 严格匹配模型 严格匹配模型( e x a c tm a t c hm o d e l ) 是给定一个查询，利用匹配函数，将文 档集分为两个集合：匹配集和非匹配集。在匹配的文档子集中文档一般不在匹配 程度上进行排序。但可以根据文档日期、字母顺序或其他属性来排序。严格匹配 模型中最简单而又具有代表性的便是布尔模型 4 0 。 2 3 1 1 布尔模型 布尔检索模型是基于集合理论和布尔