（计算机应用技术专业论文）基于向量空间的信息检索算法研究.pdf

摘要 互联网技术的迅速发展，使w e b 已经成为世界范围内信息共享和信息传播的最主 要渠道之，其网上的文本数量也成指数级增长。如何能够快速和精确地在浩瀚的信 息海洋中检索到用户所需的信息已成为当今重要的研究课题。本论文针对影响检索效 率的因素一标题位置特征项，在传统向量空间模型的基础上提出一种改进向量空间模 型及其算法，由此提高查询式与文档的匹配度和检索系统的查准率，并通过实验验证 了该算法具有较高的查全率和查准率，可改善w e b 信息检索系统输出结果的排序能力。 关键词：向量空间模型信息检索查全率查准率 a b s t r a c t t e c h n i c a la n dq u i c kd e v e l o p m e n to fi n t e m e t m a k ew e bh a v ea l r e a d yb e c o m e i n f o r m a t i o ni n s i d et h es c o p eo fw o r l d ss h a r ea n do n eo ft h em o s to u t l e t so ft h ei n f o r m a t i o n d i s s e m i n a t i o n ，i t st e x to nt h en e to r i g i n a u yt h eq u a n t i t ya l s ob e c o m e st h ei n d e xn u m b e r c l a s sg r o w t h h o wc a ni n s p e c tt h ei n f o r m a t i o nt h a tc u s t o m e rn e e dt oh a v eb e c o m ew i t l lb v t h es q u a r ei ne x t e n s i v ei n f o r m a t i o no c e a nq u i c k l yt h ei m p o r t a n tr e s e a r c ht o p i cn o w a d a y s a i ma tt h ep u r p o s eo ft h ef a c t o r - h e a d l i n ep o s i t i o nc h a r a c t e r i s t i ci t e m0 1 1t h et r a d i t i o n a l v e c t o rs p a c em o d e lo ff o u n d a t i o n t h i st h e s i sp u tf o r w a r dak i n do fi m p r o v e m e n tv e c t o r s p a c em o d e l t h em e t h o dc a l lr a i s et h es e a r c ht y p ea n dt l l et e x tf i l e st om a t c ht h ed e g r e e t h e nr a i s i n gt h ep r e c i s i o n i th a sh i g h e rr e c a l la n dp r e c i s i o n ，i n f o r m a t i o nr e t r i e v a ls y s t e m k e yw o r d s ：v e c t o rs p a c em o d e l 长春理工大学硕士学位论文原创性声明 本人郑重声明：所呈交的硕士学位论文，基于向量空间的信息检索算法研究是本人 在指导教师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容 外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律结果由本人承担。 作者签名：至磐三月丝日 长春理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“长春理工大学硕士、博士学位论文版权使用 规定，同意长春理工大学保留并向中国科学信息研究所、中国优秀博硕士学位论文 全文数据库和c n k i 系列数据库及其它国家有关部门或机构送交学位论文的复印件和电 子版，允许论文被查阅和借阅。本人授权长春理工大学可以将本学位论文的全部或部 分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编 学位论文。 作者签名：兰整掣年互月掣日 指导导师签名： 年一月一日 4 1 第一章绪论 1 1 论文研究目的和意义 在人类社会的演变和发展过程中，人类的信息活动从来没有间断过，信息一直在 积极地发挥着人类意识到或没有意识到的重要作用。2 1 世纪以来，随着科学技术的空 前进步，信息、物质和能量已构成现代社会文明的三大支柱。随时随地都在自觉不自 觉地接受、传递、存储和利用各种信息，毫无疑问，人类已经进入信息时代。w e b 的发 展伴随着信息的急剧增长，信息检索技术成为研究的热点，g o o g l e 在短短的几年里在 全世界范围的成功，进一步印证了w e b 搜索是信息检索中的一个重要研究和应用方向。 众所周知，科学技术的发展具有连续性和继承性，闭门造车只会重复别人的劳动 或者走弯路。比如，我国某研究所用了约十年时间研制成功“以镁代银”新工艺，满 怀信心地去申请专利，可是美国某公司早在2 0 世纪2 0 年代末就已经获得了这项工艺 的专利，而该专利的说明书就收藏在当地的科技信息所。科学研究最忌讳重复，因为 这是不必要的浪费。在研究工作中，任何一个课题从选题、试验直到出成果，每一个 环节都离不开信息。研究人员在选题开始就必须进行信息检索，了解别人在该项目上 已经做了哪些工作，哪些工作目前正在做，谁在做，进展情况如何等。这样，用户就 可以在他人研究的基础上进行再创造，从而避免重复研究，少走或不走弯路。 科学技术的迅猛发展加速了信息的增长，加重了信息用户搜集信息的负担。许多 研究人员在承接某个课题之后，也意识到应该查找资料，但是他们以为整天泡在图书 馆“普查 一次信息就是信息检索，结果浪费了许多时间，而有价值的信息没有查到 几篇，查全率非常低。信息检索是研究工作的基础和必要环节，成功的信息检索无疑 会节省研究人员的大量时间，使其能用更多的时间和精力进行科学研究。 在改革开放的今天，传统教育培养的知识型人才己满足不了改革环境下市场经济 的需求，新形势要求培养的是能力型和创造型人才，具备这些能力的人才首先需要具 备自学能力和独立的研究能力。大学生在校期间，已经掌握了一定的基础知识和专业 知识。但是，“授之以鱼”只能让其享用一时。如果掌握了信息检索的方法便可以无师 自通，找到一条吸收和利用大量新知识的捷径，把大家引导到更广阔的知识领域中去， 对未知世界进行探索。是谓“教人以渔”，才能终身受用无穷。 1 2 国内外研究现状 1 2 1 国外研究现状 s a lt o n 提出了一种信息检索算法叫向量空m 模型算法，并成功应用f - s m a r t 系统。 该模型使用t f * i d f 将给定的文本( 文章、查询、或文章的一段等) 转换成一个维数很高 的向量，进行查询向量与文档向量的相似度比较。r o c c h i o & s a l t o n 提出了相关反馈模 型，该模型利用用户和系统之间的交互，有效地提高了检索结果的精度。m i c h a lc u t l e r 结合h t m l 标记的特性，在向量空问模型基础上提出了依据位置信息的检索算法，提高 了检索质量。 从2 0 世纪6 0 年代以来，许多研究者发现，w w w 上超链结构也是一个非常丰富而 重要的资源。基于这种超链分析的思想，许多研究学者也相继提出了链接分析算法， 并成为研究的热点。 k l e i b e r g 提出了h i t s ( h y p e r l i n k i n d u c e dt o p i cs e a r c h ) 超链接主题查找算法， 并引入两类网页：权威网页和集中网页。它的主要思想是利用页面的被引用次数及其 向外链接数目的多少来决定不同网页的价值。 b r i n $ p a g e 提出了p a g e r a n k 方法，其基本思想是：一个页面被多次引用，则这个 页面很可能是重要的；一个页面尽管没有被多次引用，但被一个重要页面引用，则这 个页面也很可能是重要的；一个页面的重要性被均分并被传递到它引用的页面。 r l e m p e l 和s m o r a n 提出了s a l s a 算法，该算法考虑了用户回退浏览网页的情况，保 留了p a g e r a n k 的随机漫游和h i t s 中把网页分为a u t h o r i t y 和h u b 的思想，但取消 a u t h o r i t y 和h u b 之间的相互加强关系。 1 2 2 国内研究现状 在我国，信息检索的研究已有多年的历史，早在上个世纪5 0 年代，当计算机被图 书馆等部门用于存储和管理文档时，信息检索就作为一个研究热点领域而诞生了。到 了8 0 年代，信息检索领域在索引模型，文档内容表示以及匹配策略等方面取得了许多 突破性的研究成果，这些成果也成功应用于w e b 上，产生了搜索引擎。 信息检索技术的发展与数据库技术是密切相关的，目前它已在许多方面取得了实用 性的进展。目前流行较广泛的文本检索软件有c d s i s i s 等。全文检索系统方面有 w a i s 、易宝北信的t r s 、北大方正的m i r s 和海文的q u i c k 等。 基于内容检索即多媒体信息检索，它是直接对图像、视频等多媒体信息进行分析， 抽取特征和语义，利用这些内容特征建立索引，然后进行检索。目前，大量的原型系 统已推出。 w e b 信息检索是利用搜索引擎作为检索手段，它的检索方式有超文本检索、全文 ( 网页级) 检索等几种方式。在全文检索方式中，搜索引擎使用网络信息资源自动采用 机器人( r o b o t ) 程序，也称网络蜘蛛、爬虫( s p i d e r ) 软件等，动态访问各站点，收集信 息，建立索引，并自动生成有关资源的简单描述，存入数据库中供检索。但这种机器 人程序的查准率有待提高1 。 随着i n t e r n e t 的快速发展，w e b 信息检索已向个性化检索、人性化检索、智能 化检索和多样化检索等方面发展。个性化可以使得无论是柃索方式还是检索结果的提 供都可以根据用户的不同定制来提供，高级的定制不仅仅是界面形式的与众不同，更 侧重的是内容提供上，可根据个体差异提供适应性的信息服务。 检索系统的人性化是系统性能得以为用户所充分享受的一个重要基础，人性化检 索一方面体现在网络上各个网站设计的规范化以及导航的明晰化。 信息构建( i n f o r m a t i o na r c h i t e c t u r e ，简称i a ) 是近年来兴起的热点问题，信息 构建的提出是为了更好地在网页上组织和表现信息，一个很重要的目标是使信息被理 解，对信息的组织与表达对于实现性能良好的信息检索和获取是必不可少的。增强信 息的表现力和亲和力，这些也是检索所不容忽视的一面。另一面，人性化检索还体现 在检索系统本身的友好界面，检索可视化技术的应用令检索系统对用户而言显得更形 象直观。 如今的网络已经不仅仅是纯文本信息，图像、视频等多媒体信息已无所不在，因 此传统的信息检索技术也需要满足这些新类型的资源查找问题。未来的w e b 信息检索 将向着更加便于人的使用，以更好检索性能服务于用户的方向发展，促进人们对无序 信息世界的有序化组织，令w w w 信息资源得到更为合理的开发和利用。 1 3 主要研究内容 本文在传统向量空间模型的基础上提出一种新的检索方法，通过将一篇文档从逻 辑上划分为n 个相对独立的文本段，然后按照文本段的内容建立文本特征向量以及文本 权值向量，形成基于n 层向量空间模型的检索方法。并在此模型的基础上，更为精确地 定义了特征值向量和相似度的计算方法。本文研究的主要内容为： 1 向量空间模型( v e c t o rs p a c em o d e l ，简称v s m ) ，它是信息检索技术中广泛使 用的检索模型，向量空间模型将文档和查询式表示成向量形式，从而将信息检索转化 为向量空间的向量匹配问题，将文档内容简化为特征项及其权重的向量表示。 2 通过分析传统的向量空问模型，指出其中的缺陷，并针对其缺陷提出解决的方 法，然后通过理论分析和实验手段验证本文提出的改进向量空间模型在检索性能上的 改善。 3 建立n 层向量空间模型，并提出可改善w e b 信息检索系统输出结果的排序能力 的新算法。该模型不但适应新文档的动态扩充，且在文档查询的查全率、查准率以及 查询速度方面也有明显的改进。 第二章基础理论 2 1 检索模型及算法概述 2 1 1 经典信息检索模型 在信息检索引擎中，信息获取方式的优劣主要取决于信息模型的建立方法。信息 模型建立方法主要可以分为三类：布尔模型、向量模型和概率模型。在布尔模型中， 文档和查询式都表示为特征项的集合，可以通过运用集合运算来进行检索：在向量空间 模型中，文档和查询式则表示为高维空间中的向量，可以通过对于向量的代数运算进 行检索：概率模型中，文档和查询式则是通过概率理论形式化为概率分布，检索模型也 建立在概率运算的基础之上。 1 布尔模型 布尔( b o o l e a n ) 模型是基于集合论和布尔代数的一种简单检索模型。在布尔检索 中，要定义一个二值变量的集合，这些变量都对应文档的某个特征，称为索引项。索 引项一般是词或词组等简单的文本项，文档由这些索引项的组合来表征和索引，如果 该项对文档的内容表示有贡献，则赋值为l ，否则为0 。查询式是索引项和操作符a n d ， o r ，n o t 组成的表达式。匹配函数遵循布尔逻辑的原则，检索时根据用户查询和简单的 布尔逻辑规则将文档划分为匹配集和非匹配集。布尔模型的主要优点在于具有清楚和 简单的形式，而主要缺陷在于完全匹配会导致太多或者太少的结果文档被返回。 2 向量空间模型 向量空间模型是近些年使用较多效果较好的一种信息检索模型幢1 。该模型在 s m a r t i 口1 系统环境中获得较好的检索质量。这一模型主要是将文档看作由相互独立的词 条组( t 。，t 。，t 。) 构成，对于每一词条t 。，都根据其在文档中的重要程度赋以一定权 值w 。，将( t ，t ：，t 。) 看成一个。维坐标系中的坐标轴，( w 。，w ：，w 。) 为对应的坐 标值，从而转化为一个向量空间。文档映射成为空间中的一个点，从而将文档信息的 匹配问题转化为向量空间中矢量匹配问题。词条t 。在文档d ；中的权值w ；。通常由两部分 计算获得：一部分是词条k 在文档d ；中出现的次数，即t f m 另一部分是整个文档集合 中包含词条k 的文档个数，即d f 。直观上看，t f ；。越大，w ；。值越大；同样d f t 越小， w ；。值也越大，说明特征项t 。更能代表文档d ；的内容。 搜索引擎进行查询时，其查询条件也要进行向量化，才能方便计算，一般采用布 尔框架。所谓布尔框架就是：t 的值要么是1 ，要么是o ；如果文档d 中包含t ，则t 的权值为1 ，否则为0 。同样在进行查询匹配时，查询条件q 的向量化过程也是如此， 如查询条件q 包含t ，则t 的权值为l ，否则为0 。 向量空间模型突破了一般的俞尔模型中索引项在文档中的权重及索引项和文档的 相似度都只能是0 或1 的局限，其权重和相似度是某个范围中的一个实数，该模型可 4 以将检出的文档按相似度的大小进行排序，让更相关的文档排在前面。 3 概率模型 在2 0 世纪6 0 年代m a r o n 和k u h n s 提出了概率模型，该模型在i n q u e r y n l 系统环境 中取得了较好的检索效果。富有代表性的模型是二值独立检索模型( b i r ) 。b i r 模型实 现简单且检索效果好，它根据用户的查询q ，可以将所有文档分为两类，一类与查询相 关( 集合r ) ，另一类与查询不相关( c ) ，两者概率分别表示为：p ( r i d ) 和p ( ri d ) 。索 引项的分布基于以下两条假设：( 1 ) 文档d 可以表示为d ( x 。，x 。，x 。) ，其中二元随机 变量x ；表示索引项t ；是否在该文档中出现，如果出现，则x i = l ，否则x i = o 。 ( 2 ) 索引 项与索引项之间相互独立，任意一个索引项的动作不会影响到其它索引项。 文档d 与查询q 的相关度排序函数为： s i m ( d ，q ) ：p ( r id ) ( 2 1 ) p ( rd ) 利用b a y s e 公式并经简化，文档与查询q 的相关函数可转换成一下形式： s i m ( d ，q ) - y x , l o g 端 ( 2 2 ) 其中p i = r 1 ，q i = 堡竺，f 表示训练文档集中文档总数，r 表示训练文档集中与用 t 1 一了 户查询相关的文档数，f ；表示在训练文档集中包含特征项t 的文档数，r 。表示r 个相关 文档中包含特征项t 。的文档数。 概率模型的主要优点是文档按照其相关概率的降序排列，其效率明显优于布尔模 型，但比向量空间模型略差嘲。其主要缺点是需要初始时将文档分为相关和不相关的集 合。 2 1 2 主要文本检索算法 当前w w w 正在深度和广度方面飞速发展，i n t e r n e t 上包含了大量信息资源，它变 成人们交流思想，获取信息的便利手段。但是，i n t e r n e t 所具有的开放性、动态性和 异构性使得w w w 上的资源分布很分散，没有统一的管理和结构，大大降低了人们对信 息资源的利用效率。如何快速、准确地从海量信息资源中寻找所需信息已成为困扰网 络用户的一大难题。w w w 上最多的是文本信息，因此w e b 信息处理的核心就是如何处理 这些w e b 文档。 本章对经典信息检索模型和主要信息检索算法进行了分析和比较，详细地阐述了 基于内容检索方法，基于超链分析的检索方法以及融合的检索方法，并对其进行了总 结。 1 基于内容的检索 基于内容的检索方法主要是考虑用户提交的查询串在文档集中的出现情况，包括 特征项频率、特征项位置信息等等。代表性的方法有：基于特征项频率的检索方法、 基于特征项位置信息检索方法阳1 。 ( 1 ) 特征项频率的检索方法 向量空间模型是根据特征项频率进行检索的典型算法 1 ，最初由s a l t o n 等人提出 并发展起来的。该模型主要是将给定的文本( 文章、查询串、或文章的一段等) 看作由 相互独立的特征项( t 。，t ：，t 。) 构成，将( t 。，t 。，t 。) 看成一个r l 维坐标系中的 坐标轴；对于每一特征项t ；，都根据其在文档中的重要程度赋以一定的权值w 。，( w 。， w ：，w 。) 对应为n 维坐标系中坐标值，于是该文计算档便映射为向量空间中的一个点。 特征项t 。在文档d 。中的权值w 。通常由两部分计算获得：一部分是特征项k 在文档d 。中 出现的次数，即t f i 。，另一部分是整个文档集合中包含特征项k 的文档个数，即d f t 。 具体的方法如下： w 。= t f i k 木i d f k = t f i k 爿c ( 1 0 92 ( n n 。) + 1 ) ( 2 3 ) 其中，n 代表文档集合中的文档数量，n 。代表在文档集合中出现特征项t 。的文档 数目。t f ；。越大，w ；。值越大：同样n 。越小，w ；。值也越大，说明该特征项t 。更能够代表文 档d ；的内容。文档向量与查询向量的相似度通常采用余弦方法： s i m ( d i ，q ) = c o s = 1 兰q 一 讹幸。 ( 丢nw 2 从备n g 。2 ) ( 2 4 ) 向量空间模型算法中，相似度值的大小反映了文档与用户查询要求的相关程度， 值越高则代表文档与用户的查询要求越相关。该算法简单有效，已得到广泛的应用。 但是它也存在着不足： 1 ) 没有考虑各个特征项在文档中出现的位置。比如处在标题或摘要中的特征项应 该j 下文中的特征项对文档的主旨更接近； 2 ) 没有涉及w e b 文档检索中的文档链接信息，链接信息从某个角度上来说包含了 被链接w e b 文档的重要讯息，而利用向量空间模型检索w e b 文档则忽视了这些信息。 ( 2 ) 特征项位置信息检索方法 m i c h a lc u t l e r m l 算法是根据特征项位置信息，利用h t m l 文档结构和链接信息进 行检索的方法。该方法首先将h t m i 标记分为六类：p l a i n tt e x t ( 正文) 、t it l e ( 标题) 、 h 一心、h ：；- h 。、s t r o n g ( 包括强调、粗体、斜体、下划线) 、a n c h o r ( 链接标记文本) ，并 根据重要程度对每类赋以不同的重要度因子c i v 。特征项权值的计算公式为： 6 形= ( 陌y oc i v ) 够 ( 2 5 ) 其中，t f v 代表特征项频率向量，t f v = ( t f v l ，t f v ：，t f v 。，t f v ，t f v 。，t f v 。) ，分别 表示特征项t 在正文、s t r o n g 、h 。一h 6 、h , - h 。、标记以及标题中出现的次数。当 c i v = ( 1 ，1 ，1 ，l ，0 ，1 ) 时，特征项t 的权值计算转变为向量空间模型的权值计算公式： w = ( 阿y oc w ) 事i d f = ( t f v i + t f v , + t f v s + t f v 4 + t f v e ) * i d f = t f * i d f ( 2 6 ) 该方法对于不同类别赋以了不同的重要度因子，因此有效地提高了检索质量。但 同时由于该方法在文档总数改变时，必须重新计算文档集中每一特征项的权值，计算 量大，不适用于文档的动态更新。 文献归3 在m i c h a lc u t l e r 算法基础上提出了改进算法，根据特征项出现在不同部 分将一篇文档从逻辑上划分为n 个相对独立的文本段，有效地改善了检索质量。 2 基于超链分析的检索 基于内容的检索方法是一种传统的检索方法，它的很多理论都是由小型的、静态 的、同构型文档集推导出来。然而i n t e r n e t 所具有的开放性、动态性和异构性给信息 检索领域带来了新的挑战。近几年许多研究学者开始利用w e b 页面的结构特性，提出 了基于超链分析的方法，作为基于内容检索方法的补充。该方法将w e b 看成一个有向 图g ：( v ，e ) ，其中v 是页面集合，e 是页面之间超链接集合。该方法认为链接信息与 被链接的对象之间必然存在着某种可信的映射关系，一个页面被其它站点引用的次数 基本上反映了该页面的受欢迎程度( 重要性) 。目前，有关这方面的研究提出了如下方 法： ( 1 ) p a g e r a n k 方法 p a g e r a n k 算法由s e r g e yb r i n 和l a w r e n c ep a g e 提出阳1 。对于描述同一个主题的 文档，人们总是喜欢先看重要( 权威) 的文档，再看次要( 不权威) 的文档。w w w 上的超文 本文档相互之间的链接可以看成是引用，这种引用关系体现出的文档的重要性能够较 好地符合人们主观意识中的文档的重要性。p a g e r a n k 算法就是基于以上思想提出的： 一个网页的质量和重要性可以通过其它网页对其超文本链接的数量来衡量。页面重要 性的计算公式如下： 月m = c ( r ( v ) n ，) ( 2 8 ) v b 。 其中u 代表一个w e b 页面，f u 是u 引用的页面集合，b u 是引用u 的页面集合。是 小于l 的常系数，用于保证所有网页排名值的总和保持为常量，n u = lf ul ，即u 的出度。 为了克服因页面互相指向而造成迭代陷阱，引入衰退因子e ( u ) ， e ( u ) 对应网页 集的某一向量，对应r a n k 的初始值，算法改进如下： 斤俐：cm 风叫) + c e ( u ) r ( 2 9 ) 、，8 7 p a g e r a n k 算法分析页面之间通过超链接形成的链接关系，对每个页面计算出一个 重要度，以提高信息检索的质量。有研究表明，p a g e r a n k 算法计算效率还可以得到很 大地提高归1 ( 2 ) h i t s 算法 h i t s 算法由j o h nk l e i n b e r gn 们提出。该算法为每个页面引入两个权值：a u t h o r i t y 权值和h u b 权值，最后分别输出一组具有最大a u t h o r i t y 权值的页面而和一组具有最 大h u b 权值的页面。a u t h o r i t y 页是相对某主题来说权威的网页，h u b 页是指向很多相 对某主题来说权威网页的网页。算法的基本思想是：一个好的h u b 页指向很多好的 a u t h o r i t y 网页，同时，一个好的a u t h o r i t y 网页也有很多好的h u b 网页指向它。它们 之间是一种环状的关系，相互增强。 算法的具体步骤：从搜索引擎中获取查询结果集，取排名最高的前t 个网页作为 根集s ，然后根据这些网页的入链和出链进行前后一级扩展，构成一个更大的基集t 。 集合t 中每一成员都分别有两个值：a u t h o r i t y 值和h u b 值。算法首先进行初始化，然 后执行网页权重的迭代传递，即i 操作( h u b 到a u t h o r i t y ) 和o 操作( a u t h o r i t y 到h u b ) ： i 操作：a ( u ) ： 略 。操作：h ( u ) ：删 5 0 ( s i = xx ey n e ) ) ( 2 1 0 ) ( s o = xx v n e ) ( 2 i i ) 每次迭代后对a ( u ) 和h ( u ) 进行规范化处理。式( 2 1 0 ) 反映了若一个网页由很多好 的h u b 页指向，则其权威值会相应增加；式( 2 - 1 1 ) 反映了若一个网页指向许多好的权 威网页，则h u b 值也会相应增加。 与p a g e r a n k 算法不同，h i t s 算法考虑了不同链接的重要性。但在实际应用中，h i t s 算法中由s 生成t 的时问开销很昂贵，计算量比p a g e r a n k 算法大：在集合t 中如果有 少数与查询主题无关的网页，但是两者又紧密链接，算法的检索结果可能就是这些无 关网页，从而发生主题漂移问题( t o p i cd r i f t ) 地1 。 ( 3 ) s a l s a 算法 s a l s a 算法由r l e m p e l 和s m o r a n 提出n3 。，基于马儿可夫理论。算法的原理为计 算出链网页漫游中到达某个出链劂页的概率和入链网页漫游中到达某个入链网页的概 率。再按概率从大到小的次序输出概率大的若干个h u b 网页和a u t h o r i t y 网页。算法 具体实现如下： 1 ) 和h i t s 算法的第一步相似，得到根集s 并且扩展为网页集合t ，除去孤立节点； 2 ) 定义2 条马儿可夫链的变化矩阵，也是随机矩阵，分别为h u b 矩阵h ，a u t h o r i t y 矩阵a ； 8 骶萨触五仫州if ( k ) l i ) i j l i i ( 2 1 2 ) 触j 喇j ) r 、研 一。 陬砌= 胜篆，) 叫ib ( k ) l i i ( 2 1 3 ) 胜凡，m ，) 一7 其中b ( i ) 表示指向页面i 的所有其它页面，f ( i ) 表示从页面i 出发的所有其它页 面。 3 ) 求出矩阵a ，h 的主特征向量； 4 ) a 中值大的对应的网页就是所要找的重要网页。 s a l s a 算法只考虑直接相邻的网页对自身a 1 h 的影响，没有h i t 5 中相互加强的迭 代过程，计算量远小于h i t s 。 3 基于融合的检索 基于内容的检索方法是从文档的具体内容出发，因此检索结果的查准率较高，但 是查全率不太理想。而且检索时需要将网页内容全部或部分下载到本地能进行索引处 理，查询速度受到影响，具有一定的局限性。基于超链分析的检索是利用页面的被引 用次数及其链接数目来决定不同网页的价值，因此可以获得比较好的查全率，但是也 存在查准率不高的缺点。近几年许多的研究学者发现结合多种技术和方法的融合检索 比单一检索方法更能有效地提高检索系统的性能，成为研究的热点n 制。目前融合的检 索方法主要有：基于内容和超链分析的融合，分类和基于内容的融合。下面分别介绍。 ( 1 ) 基于内容和超链分析的混合检索 由于超链分析的算法通常忽略文本内容，许多的研究学者将基于内容匹配的方法 引入到超链接的检索方法中。b h 算法n 5 1 在h i t s 算法基础上除了考虑了每篇文档的出 度值和入度值，还结合了查询主题与页面的相关性。a r c 算法n 刚设定文档的a u t h o r i t y 值( h u b 值) 不仅与该文档的入度( 出度) 值有关，而且与该文档的相似度密切联系，该算 法也是基于h i t s 算法的另一种改进算法。 ( 2 ) 分类和基于内容的混合 目前，信息检索系统主要提供两类服务方式：基于目录结构的检索以及基于查询 串的文档检索。基于目录结构的检索用户根据己分好的类别直接访问网页，它可以较 准确的查找到相关文档，但往往无法满足用户搜索某一特定信息文档的要求m 1 ；采用 基于查询串的检索方法，用户可以提交信息( 通常提供关键词) 来限定检索的内容范围， 这种检索方式的缺点是导致检索结果罩包含很多的无关文档。 因此，将两类检索方式相结合，利用分类来进行内容的检索，能够整合两类检索 方式的优缺点，提高检索系统的整体效率。基于分类的检索主要需要解决两个关键问 题：( 1 ) 针对某一查询请求，如何确定数据集中哪螳类文档与之最相关：( 2 ) 在最相关类 文档掣，查询结果如何排序输出。各类检索算法出于相关性的判断不同，表现出不同。 的检索性能。 本文从以下几个方面作了比较，见表2 一l 不同检索算法的比较。 表2 - 1 不同检索算法的比较 检索算法分类基于内容的检索给予超链接基丁融合的检索 分析的检索 评价指标内容和链接的融合内容和分类的融合 是否考虑文件是 否 是是 是否考虑链接否是是否 查全率 较低 高 高 较低 查准率高低高高 速度慢慢较慢快 从以上的分析和比较可以看出，各类检索算法都有各自的特点和优缺点，基于内 容的检索方法检索速度慢，查全率较低：基于超链分析的检索方法查准率低，检索速 度慢；基于融合的检索方法整体性能上要优于单一方法，但是内容和链接的融合检索 速度慢，内容和分类的融合查全率较低。因此，评价检索算法的优劣不能只采用唯一 的标准，而应针对用户的不同需求以及不同的特殊环境，从不同的角度来衡量检索的 性能。 2 2 向量空间模型 2 2 1 向量空间模型简介 1 文本的向量空问表示 对于计算机来说，中文文本就是由汉字和标点符号等最基本的语言符号组成的字 符串，由词构成短语，进而形成句、段、节、章、篇等语言结构。用尽量简单并且准 确的方法表示文档，是进行文本检索的前提引。 为便于描述问题，我们给出以下有关概念的定义： 定义1 文档：指一般的文献或文献中的片断，通常指一篇文章，记为d 。 定义2 索引项：是指文档中含有且能够代表该文档性质的基本语吉单位，记为t 。 1 0 定义3 索引项权重w i k ：表示索引项t k 对文档d ；的重要程度。w ；。= l ( i ，k ) g ( i ) ，其中l ( i ，k ) 代表索引项t 。在文档中的局部权重，g ( i ) 为索引项t k 的全局权重。其计算方法主要运用t f - i d f 公式，目前存在多种t f i d f 公式，现给出 一个常用的归一化公式。 臌 可l _ 1 0 则| 彤) ( 2 1 4 ) 式中，t f ；。表示索引项t 。在文档d ；中出现的次数( 即索引项频率) n 钔，t f 媳越高， 意味着索引项t 。对于文档d 。越重要；d f k 表示含有索引项t k 的文档数量( 即索引项 的文档频率) ，d f k 越高，意味着索引项t 。在衡量文档之间相似性方面的作用越低；n = id i ，即全部文档的数量，分母为归一化因子：i d f k = l o g ( n d f 。) 为逆向文档频率 ，i d f k 越高，意味着索引项t 。对于文档的区别作用越大。如果一个索引项t k 仅出 现在一个文档中，则i d f 。= l o g ( n ) ：如果一个索引项t 。出现在所有的文档中，则i d f k = l o g l = 0 。 定义4 相似度( s i m i l a r i t y ) ：衡量一篇文档向量与用户查询式向量的相近程度， 即判断某篇文档是否是用户所需要的。当文档被表示为文档空间的向量，就可以利用 向量之间的距离公式来表示文档间的相似度。检索过程就是计算文档向量与查询向量 之间的相似度，可以根据相似度值的不同，对检索结果进行排序。计算相似度的方法 有许多种，通常用两个向量的夹角余弦或j a c c a r d 相似度函数。 s i m ( d l ，d 2 ) = c o s o = 力 。讹。 七= l ( 2 1 4 ) 联诚 也扩瓣唾k = l 一 1 5 ) 相似度测算即检索查询时通过查询向量与文档集向量的比较计算，返回与查询相 关度较高的文档，使文档按相关度排序，并设有可选的阂值，当返回文档数目较多时， 可以通过调整阈值的大小来确定文档的返回量拉“。 定义5 向量空间模型( v e c t o rs p a c em o d e l ，简称v s m ) ：设文档集合中共有n 个 不同的索引项t ，t 2 ”，t 。，根据式( 1 ) 计算文档o 。( i = l ，2 ，m ) 的索引项权重w 如果把文档t ，t “，t 。看成一个n 维坐标系，w ；。为坐标系的值，则d ；= 铲，w 譬，w 譬j 成为n 维空间牟的一个而j 量，即文档d 。的向量表示。 ， ( q )i 叮j i g j 、 ( 9 ) 设用户查询式向量为9 2 t ，w j 2 。，_ j ，肌为索引项t k 在查询式q 中 的权重( 1 k n ) ，并根据布尔模型进行确定，则用户查询式的向量化过程可表示为： ( 们1 1 ，觏q 嗽2 l o , 觏盛q ( 2 1 6 ) 2 特征项选择与赋权 可以看出，对向量空间模型来说，有两个基本问题：即特征项的选择和项权重计算 ( 1 ) 特征项选择 用来表示文档内容的项可以是各种类别，对汉语来说，有字、词、短语，甚至是句 子或句群等更高层次单位。项也可以是相应词或短语的语义概念类。项的选择必须由 处理速度、精度、存储空间等方面的要求来决定乜。特征项选取有几个原则：一是应 当选取包含语言信息较多，对文本的表示能力较强的语言单位作为特征项；二是文本 在这些特征项上的分布应当有较为明显的统计规律性，这样将适用于信息检索、文档 分类等应用系统；三是特征选取过程应该容易实现，其时间和空间复杂度都不太大。 实际应用中常采用字、词或短语作为特征项。 由于中文是表意文字，不像英语容易处理，在操作中先要进行句子的切分、词和短 语的识别，而文档的意义主要由实词承担，所以又要划分实词和虚词，最后遴选特征 词。选取特征项的方法通常有两种：一种是语言分析的方法，采取排除法，对理解文 档内容无用的一些虚词、助词和普通词建立信用词表；另一种是数理统计的方法，根 据语言学的研究成果用实词和虚词的词频差异来区分实词和虚词。研究表明，简单的 关键词选择方法取得的效果几乎和复杂的特征选择方法一样好心引。 ( 2 ) 特征项赋权 词语权重大小反映了该词语的重要程度，词语权重计算的准则是要能最大程度的 区分不同文档。特征项赋权即特征项的权重确定，为了兼顾查全率和查准率，检索系 统在对先生项进行赋权时，应同时包含提高查全率和查准率的赋权因子。特征项赋权 因子由频率因子，文档集因子和规格化因子三部分组成。 在文档中频繁出现的特征项具有较高的权重，因此检索系统常使用频率因子 t f ( t e r mf r e q u e n c y ) 进行特征项赋权，使用高频特征项进行查询可以提高系统的查全。 率。 仅使用频率因子并不能保证系统的查询性能，提高查全率时会影响检索系统的查 准率。因此需要引入一个与文档集合有关的因子，加大文档之间的区分度。如果特征 集合中较少的文档中出现，则相应的文档集因子i d f ( i n v e r s ed o c u m e n tf r e q u e n c y ) 较火。在文档总数为n 的集合中，如果包含某特征项的文档数为n ，则文档集因子是 i d f ：l o g ( n n ) 瞳3 1 。较好的查询表达式通常包含能够将一些特定文档与文档集合中其它 1 2 文档区别开来的特征项，这种特征项不仅要有较高的出现频率，还要在文档集合中较 少的文档中出现。将频率因子和文档集因子相乘就可以实现此目的，这就是文本检索 存在问题模型中最常用的t f - i d f 赋权因子。 特征项的权重计算，是人为赋予的，因此主观性较强，但比较权威的确定权重的 方法是运用t f - i d f 公式，假定w 为特征项的权重，则： 讹= 矾够= 矾硪 ( 2 1 7 ) 其中，t f j 。为特征项t 。在文档d 。中的出现频率，称为项频( t e r mf r e q u e n t c y ) ；d f t 则是文档集d 中出现特征项t 。的文档数，称为文档频率；i d f 。为d f k 的倒数，称为 逆向文档频率( i n v e r t e dd o c u m e n tf r e q u e n c y ) 2 4 o 另外，还应考虑到文档的长度，否 则长文档易被检出，而短文档会被漏检，所以通常还要对上面公式进行标准化处理， 因此也存在着多种常用的处理后的t f - i d f 公式。 2 2 2 向量空间模型工作原理 向量空间模型是目前信息检索最常用的数学模型，在w w w 信息方面，向量空间模 型比布尔模型等传统模型更合适。 基于向量空间模型的信息检索一般的过程如下： ( 1 ) 将各个文档和查询都表示成为向量； ( 2 ) 计算查询与各个文档之问的相似度； ( 3 ) 按照查询与各个文档之间的相关度对相关的文档进行排序； ( 4 ) 将排序后的文档以线性列表的形式返回给用户。 根据以上的相关知识引出如图2 1 所示的向量检索模型，这里需要解决特征项的 生成和加权、相似度的计算( 检索运算) 等一系列问题。由于向量检索中采用向量间的 某种距离度量来反映文档对的满足程度，所以相似度的值最好能与真实情况相符，计 算简便：计算出的值最好能归一化到 o ，1 区间上，且分布尽可以均匀，使门限的选择 容易一些。直接选定相似度门限的办法有时不太好控制，这时可以根据相似度对文档 排序并直接给定输出的文档数目。 1 3 图2 1 向量检索模型 1 4 第三章n 层向量空间模型设计 3 1 向量空间模型分析 向量空间模型算法自推出以来在信息检索方面得到了广泛的应用，但随着信息技 术的发展和用户需求的变化，向量空间模型也逐渐显露出存在的缺陷，许多学者也就 此进行了科学研究并提出了不少改进的算法。本章将对向量空间模型向量维数和索引 项位置等方面进行研究分析，并在向量空间模型算法的基础上进行改进。 3 1 1 向量空间模型特点 利用f j 述基本知识实现的信息检索算法如下： ( 1 ) 构造特征项库。输入文档集合中的特征项，并建立特征项库； ( 2 ) 建立文档信息。将文档内容输入数据库，建立文档信息库； ( 3 ) 构造文档向量信息库。对每个文档信息计算每一个特征项的权值，并构建相应 的文档向量： ( 4 ) 查询文档。用户输入查询条件，利用布尔模型得到查询条件的文档向量，再与 每一个文档向量进行计算得到该查询条件与文档的相似度； ( 5 ) 排序输出结果。按照( 4 ) 所计算出来的相似度大小排序输出查询结果。 基于向量空间模型的信息搜索方法存在以下的缺陷： ( 1 ) 文档向量权值计算过程中使用了反比文献频率i d f 。，因此每增加一个文档都 需要重新计算向量； ( 2 ) w e b 文档信息之间的变迁是通过链接完成的，因此，链接的文本信息从某个角 度上来说代表了被链接的w e b 文档的重要信息，而利用向量空间模型进行w e b 信息查询 的应用忽视了这些信息。以上两个缺点导致传统的向量模型查询速度慢，同时查准率也 不高。 另外，索引项权重w 。的直观含义是一个索引项对于一个文档的重要程度，即一个 索引项在多大程度上可以将该文档与其它文档区分开来。采用t f i d f 方法对索引项 加权1 ，在一定程度上给那些经常出现在较少文档中，而不常出现在绝大部分文档中的 索引项赋予更高的权重。由于w e b 文档的半结构化特征，一些索引项出现在特殊位置上， 比如：标题、小标题、超链接等不同域。这些特殊位置的内容代表了w e b 文档的重要 信息，因此，索引项出现的位置与其权重密切相关。而向量空问模型中采用t f i d f 方 法计算索引项权重时忽略了这些信息的重要性，这是造成w e b 信息检索系统输出结果排 序能力差的主要原因之一。另外，文档向量计算过程中采用了t f i d f 方法，这样导致 每增加一个w e b 文档都需要晕新计算向量，从而增加了信息检索系统的负载，使查询速 度变慢。针对传统向量空间模型在w e b 信息检索中存在的缺陷，本文提出了一种改进的 向量空间模型。 】5 向量空间模型认识到使用二元权值的局限性，构建了部分匹配的框架( 通过给查询 和文