（计算机软件与理论专业论文）基于lucene的个性化搜索引擎的研究与实现.pdf

内蒙古大学硕士学位论文 基于l u c e n e 的个性化搜索引擎的研究与实现 摘要 随着i n t e r n e t 技术的迅速发展，网络提供给人们的信息量越来越大。搜索引擎作为人们 在网上查找、获取信息的重要手段之一，在各个领域都已得到了广泛的应用。为了给用户提 供个性化的查询服务，个性化搜索引擎应运而生。经过众多研究者的不懈努力，个性化搜索 引擎技术已取得了一些进展。本文针对目前搜索引擎存在的不足以及当前用户个性化查询的 要求，在深入研究搜索引擎兴趣学习方法及相关技术的基础上，提出了一个基于用户兴趣收 集和反馈技术用户兴趣模型。研究工作具有一定的理论意义和较强的实用价值。本论文所作 的主要工作如下： 介绍了个性化搜索引擎的工作原理，提出了建立在个性化搜索引擎体系结构上用户信息 的收集方法、收集的内容和存储方式，基于上述内容，描述了基于用户描述文件的用户建模 方法。 通过隐式收集用户信息，提出了一种基于该技术的用户模型的更新方法，并在此基础上， 结合用户模型的基本特点，描述了一种个性化查询扩展方法和一种个性化排序方法。 本文最后实现了一个基于l u c e n e 的个性化搜索引擎系统，证明了上述架构的可行性，此 外，通过收集用户的查询信息，证明了用户模型的建立，在某种程度上，提高了搜索引擎的 查准率，证明了基于用户模型的个性化方法具有一定的优越性。 关键字：搜索引擎，个性化，查询扩展，l u c e n e 基于l u c e n e 的个性化搜索引擎的研究与实现 t h er e s e a r c ha n di m p l e m e n t a t i o no fp e r s o n a l i z e ds e a r c he n g i n b a s eo nl u c e n e 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 tt e c h n o l o g yt h en e t w o r kc a r lp r o v i d ep e o p l em o r ea n d m o r ei n f o r m a t i o n s e a r c he n g i n eh a sb e e nw i d e l yu s e di nm a n yf i e l d s ，w h i c hi st r e a t e da sat o o lt h a t p e o p l ec a ng e ti n f o r m a t i o no nw o r l dw i d ew e b i no r d e rt op r o v i d ep e r s o n a l i z e ds e a r c hs e r v i c ef o r u s e r s ，p e r s o n a l i z e ds e a r c he n g i n ec o m e sf b r t h b e c a u s eo fm a n yr e s e a r c h e r sc o n t r i b u t i o n ，p e o p l e h a v em a d eg r e a tp r o g r e s si np e r s o n a l i z e ds e a r c he n g i n e t h i st h e s i sp o i n t so u tt h es h o r t a g eo f c u r r e n ts e a r c he n g i n ea n du s e r sr e q u i r e m e n t so fp e r s o n a l i z e ds e a r c h ，d o e ss o m er e s e a r c ho n i n t e r e s tl e a r n i n gm e t h o d sa n di t st e c h n o l o g y , an e wu s e ri n t e r e s tm o d e li sp r o p o s e d i tm a i n l yt a k e s c h a r g eo fi n f o r m a t i o nc o l l e c t i o no fu s e ri n t e r e s ta n du s e rf e e d b a c kt e c h n o l o g y t h er e s e a r c hi so f v a l u ei nb o t ht h e o r ya n da p p l i c a t i o n t h em a i nw o r ki nt h et h e s i si ss h o w e da sf o l l o w ： t h er e s e a r c ht e l l sb a s i ct h e o r yo fp e r s o n a l i z e ds e a r c he n g i n e ，a n dt h em e t h o d ，c o n t e n t sa n d s t o r a g eo fc o l l e c t i o no fu s e ri n f o r m a t i o nb a s e do nm a k i n gu s e rm o d e l a c c o r d i n gt ot h et h e o r y a b o v e ，i tp r e s e n t st h ew a y so fm a k i n gu s e rm o d e lb a s e do nu s c = i p r o f i l e t h r o u g hc o l l e c t i n gu s e ri n f o r m a t i o n ，t h et h e s i sp r e s e n t sak i n do fm e t h o da b o u tr e n e w i n gu s e r m o d e lb a s e do nt h i st e c h n o l o g y f u r t h e r , t og e tu n i t e dt ot h ec h a r a c t e r so fu s e rm o d e l ，a p e r s o n a l i z e dq u e r ye x p a n s i o nm e t h o da n dan e w s o r to fp e r s o n a l i z e dp a g e r a n k i n ga r ep r o p o s e d a ne x p e r i m e n t a ls y s t e mb a s eo nl u c e n ei se s t a b l i s h e da n dp r o v e st h ef e a s i b i l i t yo fa r c h i t e c t u r e a b o u tp e r s o n a l i z e ds e a r c he n g i n e b e s i d e s ，t h r o u g hc o l l e c t i n gu s e ri n f o r m a t i o n ，an e wu s e rm o d e li s s e tu p ，i ns o m ep e r c e n t s ，a n di ti m p r o v e sq u e r yp r e c i s i o no fs e a r c he n g i n e k e y w o r d ：s e a r c he n g i n e ，p e r s o n a l i t y , q u e r ye x p a n s i o n ，l u c e n e j l 内蒙古大学硕士学位论文 图表目录 图表2 1 信息检索过程一6 图表4 1l u c e n e 主要功能2 7 图表4 2 系统结构与源码组织图2 9 图表4 3 用户模型流程图3 2 图表4 4 用户模型实现3 3 图表4 5 查询扩展流程图3 4 图表4 6 查询扩展实现3 5 图表4 7 个性化查询扩展流程图3 6 图表4 8 个性化查询扩展实现。3 7 图表4 - 9 个性化排序流程图3 8 图表4 1 0 个性化排序实现。3 9 图表4 1 ln t c i r 测试集文档例子4 0 图表4 12n t c i r 测试集t o p i c 4 0 图表4 1 3 测评实验结果4 3 图表4 1 4 个性化测评结果。4 4 表格4 1 影响评分的因素3 1 表格4 2 测评实验数据4 2 表格4 3 用户建模t o p i c 选择4 3 v 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人 己经发表或撰写过的研究成果，也不包含为获得内蒙古大学或其他教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在 论文中作了明确的说明并表示了谢意。 学位论文作者签名：丑兹幺隆指导教师签名：量! 垂垦l 日 期：芈日期：掣 在学期间研究成果使用说明书 学位论文作者完全了解内蒙古大学有关保留和使用学位论文的规定，即：内 蒙古大学研究生在校攻读学位期间论文工作的知识产权单位属内蒙古大学。学校 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查 阅和借阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印 或其它复制手段保存、汇编学位论文。作者今后使用涉及在学期间主要研究内容 或研究成果，须征得内蒙古大学就读期间导师的同意；若用于发表论文，版权单 位必须署名为内蒙古大学方可投稿或公开发表。 学位论文作者签名： 日 期： 指导教师签名： 日期： 鞋 内蒙古大学硕士学位论文 1 1 研究背景与意义 第一章绪论 伴随着计算机、通信、网络等技术的成熟和广泛应用，互联网自1 9 8 9 年诞生以来得到了 迅猛发展，在十多年时间里，发展成为现今人类社会信息资源的一个重要组成部分，在全球 范围内越来越多的信息实体开始选择互联网为其主要载体。但是，它们却没有建立起一条有 效的信息提供途径。绝大多数的网站都是仅仅通过浏览的方式提供内容，即使是经过精心编 排、组织合理的网站，也会有7 0 到8 0 的网页内容不能被有效查阅。网民对信息的需求越 来越大，同时也越来越没有耐心。 搜索引擎的出现改变了人们获取信息的方式，利用搜索引擎可以快速地找到需要的信息。 目前，搜索引擎是仅次于门户的互联网第二大核心技术，伴随互联网的普及和网上信息的爆 炸式增长，它越来越引起人们的重视。人们上网的主要目的是查询信息。搜索引擎作为一项 网络应用，已经成为人们查询信息的主要工具。它可以从大量纷杂的信息中，找到与主题相 关的信息，为人们查询信息提供了方便。但是，目前的搜索引擎存在着很多的问题，它只解 决了信息查询的问题，而从信息资源覆盖面、检索精度、检索接口的易用性、可维护性等许 多方面来看，其效果并不能令人满意，而人们迫切地希望能够从上快速、有效地找到所需信 息。如何帮助用户快速找到需要的信息，成为互联网研究中一项重要的课题。 根据中国互联网络信息中心c n n i c 于2 0 0 9 年1 发布的第2 3 次中国互联网络发展状 况统计报告显示 1 ，2 0 0 8 年底，我国的网民人数达到2 9 8 亿，全国网页数量和网页字节 数分别为1 6 0 亿个和4 6 0 ，2 1 7 g b 。目前使用搜索引擎的比例7 2 4 ，电子邮件的应用率是 5 6 5 ，即时通信使用率已经达到8 1 4 。这说明人们越来越多的通过互联网络来获取信息， 而搜索引擎也就成为了查找信息的主要方式。根据上述分析可以看出，搜索引擎在i n t e r n e t 和w e b 发展过程中，其作用越来越显著，故不论从理论角度还是实际应用角度，都必须对其 进行深入的研究与探索。 目前，尽管搜索引擎较早期的点击网页链接有了很大的进步，用户在互联网上获取信息 的途径有了很大的改善，但是用户在互联网上要找寻自己真正需要的信息还并不是一件容易 的事情，这无疑对搜索引擎提出了更高的要求。针对上述情况，如何能够更有效、更准确地 找到自己感兴趣的信息，过滤与自己的求无关的信息，成为搜索引擎的热点研究问题之一。 因此，个性化搜索引擎以及个性化技术就是在这一背景下被提出来的。个性化的目的就是让 基于二l u c e n e 的个性化搜索引擎的研究与实现 搜索引擎更加深入、更加细致地参与到每个用户的整个检索过程中。从关键词的选择、检索 范围的确定到检索结果的精炼，帮助用户在浩如烟海的信息中找到和需求真正相关的页面从 与用户相关的大量文档中找用广最相关、最需要、最感兴趣的页面，并将这些页面尽早地显 示到用户面前。因此，个性化搜索引擎的研究有很大的实用性价值。 1 2 现状与发展 搜索引擎个性化是搜索引擎研究的一个热点方向，搜索引擎的个性化利用资源和用户兴 趣的相似性来获取信息，从而为用户提供个性化的信息，此外，个性化搜索引擎主要通过用 户建模技术为用户提供个性化的信息。因此，用户建模技术无疑是个性化搜索引擎的研究热 点问题。 用户模型或用户描述文件是实现个性化搜索引擎的关键，它们是对用户兴趣的表示，系 统只有建立能够准确反映用户兴趣的用户模型或用户描述文件，才能够实现个性化服务。根 据收集用户信息方式的不同，常用的用户建模方法有用户主动提供、基于显式反馈的方法、 基于隐式反馈的方法等。 尽管个性化搜索引擎的研究取得了一定的进展，搜索引擎能够提供自己的个性化服务， 但目前的搜索引擎在个性化方面还存在很多的局限性，主要体现在以下三个方面： ( 1 ) 对不同的用户缺乏不同兴趣度的变化 很多搜索引擎不考虑用户信息偏好和用户的不同，对所有用户提供一样的界面和同样的 成千上万的结果，使用户在寻找有用信息时如同大海捞针，不能根据不同的用户给出相应的 建议。同时，用户要获取最新的信息，只能重复同样的查询命令，浪费了用户大量的时间。 ( 2 ) 不具备良好的交互性 现有搜索引擎的检索模式是用户输入搜索关键词，搜索引擎返回相关页面结果集，用户 浏览返回的页面。用户往往通过输入不同且相关的关键词来获得满足其信息需求的结果，即 通过对查询关键词的修改，如泛化、特化等，从而获得满意的结果，但现有搜索引擎不能理 解这些不同的关键词实质上用户是想获得同样的结果。在返回的页面集中，用户选择感兴趣 的页面进行浏览，不同用户的浏览顺序和页面不尽相同，现有搜索引擎不能跟踪用户的浏览 行为，也就不能针对不同用户的不同行为提供个性化的页面重排序，从而实现个性化的服务， 更好地满足用户的信息需求。 ( 3 ) 用户查询均是独立的 2 内蒙古大学硕士学位论文 现有搜索引擎将用户的每一次查询都看作是一次独立的行为，不能识别用户为了获得某 一信息而使用不同关键词进行的相邻查询之间的联系，不能更好地满足用户的信息需求。同 一个用户在不同时期不同环境下输入同一关键词，得到的结果都是一样的，没有考虑用户兴 趣随时间和环境的变化。 因此，在个性化搜索引擎中，首先必须挖掘用户的兴趣信息，建立合理的模型来描述、 管理用户的兴趣，并通过不断更新与维护，逐渐优化模型，以精确反映用户的兴趣需求，为 后续的个性化搜索提供基础。这对于个性化搜索引擎的开发与实践也具有十分重要的理论价 值和应用前景。 1 3 本文的主要研究内容 本文针对现有搜索引擎交互性的不足，提出了一种基于用户兴趣和查询扩展技术的搜索 引擎框架。其主要包括如何将用户浏览过程中定义用户兴趣模型的方法，并在此基础上实现 个性化查询扩展和个性化排序。本文还研究了流行的搜索引擎框架l u c e n e ，并将其扩展实现 了一个基于l u c e n e 的个性化搜索引擎系统，通过实验证明了该模型及其方法的可行性和有效 性。 本文的主要研究内容包括用户建模的方法，查询扩展方法以及搜索结果集排序等内容， 具体研究内容如下： ( 1 ) 建立用户模型的方法研究； ( 2 ) 基于用户模型的查询扩展方法研究； ( 3 ) 基于用户模型的排序算法的研究。 ( 4 ) 开源搜索引擎框架l u c e n e 的扩展 1 4 本文的组织结构 本文的组织结构如下： 第一章是绪论，主要阐述本文的研究背景及意义、研究内容和组织结构； 第二章是搜索引擎的综合研究，主要内容包括：信息检索基础理论，查询扩展技术及相 关度计算排序技术； 第三章建立了个性化搜索引擎的理论模型，并研究了个性化搜索引擎的关键 技术：提出用户兴趣模型，并在此基础上提出个性化查询扩展及排序算法； 3 基了二l u c e n e 的个性化搜索引擎的研究与实现 第四章介绍了流行搜索引擎框架l u c e n e ，并对于之前提出的用户兴趣模型，个性化查询 扩展等各模块给出了基于l u c e n e 的实现；最后设计了个性化测评实验，并给出了实验结果及 分析。 第五章对全文的工作进行了总结，并提出了本文进一步的研究方向。 4 内蒙古大学硕士学位论文 第二章搜索引擎相关理论与技术 2 1 信息检索技术和理论基础 2 1 1 信息检索的概念 信息检索( i n f o r m a t i o nr e t r i e v a l ，i r ) 泛指用户从包含各种信息的文档中集中查找所需 要的信息或知识的过程。随着当今社会各领域的迅猛发展，信息以爆炸的方式不断增长，而 且种类相当繁杂，除了文本、数字以外，还常常包括图形、位图像、声音、动态图像等多媒 体文档。 信息检索主要研究对整个文档信息的表示、存储、组织和访问。一个好的信息检索系统 不仅要求将输出信息进行相关性排名，还能根据用户的意图、兴趣和特点自适应和智能化的 调查匹配机制，获得用户满意的检索输出。 一般的检索过程如下图所示，为了描述这个检索过程，我们使用一个简单的、一般的软 件体系结构，首先在检索过程开始之前，有必要定义文本数据库。这通常是由数据库管理器 来完成的，数据库管理器详细说明如下：( a ) 将要使用的文献；( b ) 将要在该文本上执行的 操作；( c ) 文本模型( 即文本结构和可以检索的那些因素) 。文本操作转换了原始文献，生成 文献的逻辑视图。 一旦定义好了文献的逻辑视图，数据库管理器就为文本建立索引。索引是一个关键的数 据结构，因为它支持在大量数据中快速查找。考虑到文献数据库经过标引后，才能发生检索 过程。用户首先详细说明用户需求，随后运用与文本操作相同的方法对用户需求进行分析和 转换。然后，真正的查询开始之前，先执行查询操作，为用户需求提供一个系统表达式。接 着通过处理查询获得检出文献。在把文献发给用户之前，将根据相关度对检出文献进行排序。 随后用户检查经过排序的文献集合，查找有用的信息，形成一个子集并开始用户反馈循环。 基于l u c e n e 的个性化搜索引擎的研究与实现 捧序文献 一。_ _ - - j 一一 一 用户反馈 用户需求 逻辑视图逻辑视图 一文本一一 文本 亩自固 查询 宙 检出文献 图表2 - 1 信息检索过程 f i g u r e2 1p r o c e s so fi n f o r m a t i o nr e t ri e v a i 2 1 2 信息检索的评测 在信息检索研究中常常在两个方面受到批评。首先，研究人员认为它缺乏正式固定的框 架作为基础，其次认为它缺乏健壮、稳定的实验平台和基准测试。由于给定文献的相关性判 断确实存在着主观性，因此第一项批评很难完全克服。但是对于第二种批评意见，则是完全 可以消除的。近三十年来，信息检索实验主要以小型测试集为基础，这些小型测试集并不能 反映出大型文献环境种所存在的主要问题，此外，由于不同团体的研究角度不同即使使用同 样的测试集，因此使得检索系统很难具有可比性，也就不存在普遍认可的基准测试了。 直到上世纪9 0 年代，才出现了一些大规模的测试集，如：t r e c 、c l e f 、n t c i r 等，其中 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 ) 是第一个大规模的信息检索系统评估学术会议，在国际上 有很大的声望，得到检索评估领域的广泛重视，起到了示范作用。欧洲以及亚洲各国的研究 者也尝试筹办不同的语言的评估会议，构建大规模的测试集，如欧洲各国联合筹办的c l e f 信 息检索评估会议，日本国立情报学研究所举办的n t c i r 评估会议等 3 。 最常用的信息检索性能评价尺度是查全率和查准率 2 。信息检索的查准率为检索结果中 有用的相关文档数与检索到的查询结果总数之比，而信息检索的查全率为满足用户查询要求 或相关于查询要求的信息与被检索出的结果集信息比率。其中查准率和查全率的定义如下： 对于信息检索要求i ，如果用r 表示相关文档的集合，a 表示检索结果组成的文档集合，并用 r a 表示r 和a 的交集，即检索到的相关文档集合，l x i 表示集合x 的元素个数，则： 6 内蒙古大学硕士学位论文 m c i s m = 酱肚蒯= 酱 a lr 其中p r e c i s i o n 被称作为检索精度，表示检索到的相关文档占检索结果文档的比例： r e c a l l 被称作为召回率，表示检索到的相关文档占实际相关文档的比例。 最常用的评价指标包括前n 选的精度，l l 点平均精度，f 度量值。 ( 1 ) 前n 选精度 在检索返回的结果中，用户往往对排在前面的结果最感兴趣，而一般不会浏览后面的结 果。因此，排在前面的结果的质量也直接影响用户对检索的满意程度，于是前n 选精度也是 在信息检索中一个有用且常用的指标。这里n 通常取为5 ，1 0 ，2 0 或者1 0 0 。 ( 2 ) l l 点平均精度 假设用户可以一次检查检索结果集合a 里的所有文档，那么用上面定义的p r e c i s i o n 和 r e c a l l 就足够了。但是实际情况却是a 中的文档首先根据相似程度被排序，然后用户从前向 后依次查看文档。在这种情况下，p r e c i s i o n 和r e c a l l 会随着用户查看的进度而变化。于是 就有了用p r e c i s i o n 和r e c a l l 的曲线图来评价检索系统性能的方法一点平均精度。 把分为o 、1 0 、2 0 、1 0 0 这个1 1 个等级，分别计算它们对应的p r e c i s i o n ，无法 直接计算的点则可以用插值法等方法来确定。这样绘制出来的曲线可以直观的反映对一个查 询的检索效果。当我们需要衡量检索算法在检索多个不同的查询时的总体检索性能时，则可 以对所有查询，在同一个r e c a l l 等级上对各个p r e c i s i o n 值取平均。而l l 点平均精度就是 对1 1 个r e c a l1 等级上对应的p r e c i s i o n 值取平均。这也是目前最常用的标准评价方法之一。 ( 3 ) f - m e a s u r e 检索精度和召回率是两个相互关联的评价标准。通常一个系统的检索精度提高了，其召 回率往往会下降，因此只用任何一个进行评价都可能失之偏颇。除了1 1 点平均精度以外， f - m e a s u r e 也是应该对检索精度和召回率综合考察的指标。它的定义为： ，( j ) = 1 r ( j ) 二+ i p 一( j ) 其中j 是指在有序的结果列中的前j 个文档，p ( j ) 和r ( j ) 中分别为前j 篇文档的精度和 召回率。 2 1 3 信息检索的数学模型 信息检索模型是指如何对查询和文档进行表示，然后对它们进行相似度计算的框架和方 基于l u c e n e 的个性化搜索引擎的研究与实现 法。信息检索的三个经典模型分别是布尔模型、向量空间模型和概率模型 2 】。布尔模型是许 多商业信息检索系统的理论基础。在布尔模型中，文档和查询都被表示为索引项的集合，因 此该模型是集合论模型。在向量空间模型中，把文档和查询表示成一个n 维空间中的向量， 距离作为相似度的度量，该模型是代数模型。在概率模型中，把检索看作是文档和查询之间 匹配成功的概率估计问题，用于构建文档和查询的机制是基于概率论的，该模型是概率模型。 近几年，基于统计理论的信息检索模型逐渐流行起来。比较有代表性的是基于语言模型的信 息检索。语言模型是以概率论和统计理论为基础发展起来的模型，最早在语音识别中取得成 功，随后在自然语言处理中也得到广泛的应用。 2 1 3 1 布尔模型 布尔模型 2 是基于集合理论和布尔代数的一种简单的检索模型，文档和查询都是用集合 描述，它们之间的关系由集合的运算确定。这个模型的观点是，在文档d 中，索引项要么出 现，要么不出现。索引项砖在文档d ，中的权值w ，为二值函数，即w ， o ，1 ) ；而查询q 本质 上都是由索引项用连接词n o t 、a n d 、o r 连接起来组成的布尔表达式，可以表示成析取范式 d n f ( d is j u n c ti v en o r m a lf o r m ) 。 布尔模型在2 0 世纪六、七十年代得到了很大发展，在早期的许多商业系统中得到了广泛 应用，比如著名的d i a l o g ，s t a i r s ，m e d l a r s 等系统。布尔模型的优点是：( 1 ) 简单，速度快； ( 2 ) 易于表达一定程度的结构化信息。其缺点也很明显：( 1 ) 因为所有索引项的权重不是1 就 是0 ，所以无法反映出索引项对文档表示的重要程度；( 2 ) 布尔表达式过于严格，很难给出只 有部分满足用户需求的结果。 2 1 3 2 向量空间模型 向量空间模型( v e c t o rs p a c em o d e l ，v s m ) 2 5 由s a l t o n 等人于2 0 世纪6 0 年代末提 出，并成功应用于著名的s m a r t 4 系统。在此后的几十年中，该模型及其相关的技术，如 索引项的选择、加权策略，以及采用相关反馈进行查询优化等技术，在文本分类，自动索引， 信息检索等多个领域取得了广泛的应用。v s m 目前已经成为了最流行也最重要的信息检索模 型之一。 经典向量模型，以线性代数为基础。它认为每一篇文档和查询都被表示为一个t 维空间 内的向量，其中t 为系统中索引项的总数。用w ，表示索引项在文档d ，中的权重，那么文档 内蒙古大学硕士学位论文 的向量为d ，= ( w l w 2 ，w ，) 。同样地，查询的向量为g = ( 4 2 1 q 矿，w ，) 。将文档和查询 都表示成t 维空间的向量之后，可以定义它们在t 维空间中的距离，常用的方法之一用夹角 的余弦量化文档和向量之间的相似度： 跏( d y , q ，= 尚= f w 心。 扛l 目前最常用的权重估计公式是著名的t f i d f 公式： w ，= 皈，f 职 其中皈，( t e r mf r e q u e n c y ) 表示索引词气在文档d j 中出现的频率；而溉( i n v e r s e d o c u m e n t f r e q u e n c y ) 表示索引词的反比文档频率。 向量模型尽管结构简单，但对于一般集合而言仍然是一个适应性强的相关度排序策略。 在向量模型的框架中，通过查询扩展和相关反馈，可以改善其产生的排序结果集合。与大量 其他的相关度排序方法相比，即使向量模型不是最优，效果也是相当不错。向量空间模型的 简单、便捷和不错的性能，使它成为当今流行的检索模型之一。 2 1 3 3 概率模型 概率模型是由r o b e r t s o n 和s p a r kj o n e s 于1 9 7 6 年提出的，也就是后来有名的二值独立 检索模型( b i n a r yi n d e p e n d e n tr e t r i e v a l ，b i r ) 。该模型试图在概率论的框架下解决信息检 索问题。给定查询q ，该模型会估计文档集合中的文档d j 与q 相关的概率。对于给定查询q ， 存在一个文档集合r ，称为理想结果集，该集合只包含完全相关的文档而不包含其他不相关 的文档，这些不相关的文档组成集合r 。这样检索的过程就看成是详细描述理想结果集属性 的过程。然而，我们并不能确切知道理想结果集的属性是什么。在查询初始阶段，我们只有 查询提供的一些信息，用于指示理想结果集可能是什么样的。但是如果经过一个不断重复的 反馈过程，即用户在返回的文档集中指定哪些是真正相关的文档，模型就可以逐渐学习到更 多的信息，从而能较为准确地估计理想结果集的属性，完成对文档的排序过程。 对于一个查询q ，模型定义它与文档d ；的相似度为： 9 基于l u c e n e 的个性化搜索引擎的研究与实现 州咖) = 黜 式中，p ( 尺l 嘭) 代表文档是相关文档的概率，而尸( j r l 嘭) 代表不相关文档的概率 2 。由于 一开始，我们并不知道集合r ，通过查询及反馈过程不断地调整r ，以期r 接近理想的相关集 合。 概率模型的优点在于它能够按照相关概率递减的顺序将结果返回给用户，而其不足之处 在于：( 1 ) 需要预先将文档分成相关和不相关的集合，在查询信息不足的时候，分类的精度不 高，可能造成检索性能下降；( 2 ) 查询和文档中每个索弓i 词的权重都是二值的，没有考虑它们 出现的频率信息：( 3 ) 同其他模型一样，索引词的独立性假设没有反应自然语言文本的真实情 况。 2 1 3 。4 语言模型 一直以来，语言模型被应用于语音识别、汉语输入法等研究，但是从1 9 9 8 年以来，具有 语言模型的信息检索模型的研究开始兴起，并在最近几年的时间内取得了很大的进展。在信 息检索中的统计语言模型是一个用来生成自然语言的概率模型。在简单和基本的语言模型就 是人们常用的一元模型，在该模型中用一个词在文档中出现的相关频率来表示。更复杂一些 的模型则同时还考虑词出现的顺序、短语、以及在时间和文档集合变化时语言的统计信息变 化。 如果用变量w 代表一个文本中顺序排列的n 个词，即w = w 1 ，则统 计语言模型的任务是给出任意词序列w 在文本中出现的概率p ( w ) 。利用概率的 乘积公式，p ( w ) 可展开为 p ( 形) = p ( w 1 ) 尸( w 21w 1 ) 尸( w 31w , w 2 ) p ( i w 2 k 1 ) 不难看出，为了预测词睨的出现概率，必须己知它前面所有词的出现概率。从计算上来看， 这太复杂了。如果任意一个词的出现概率只同它前面的n 一1 个词有关，问题就可以得到很大 的简化。这时的语言模型叫做n 元模型( n - g r a m ) ，即 尸( 形) = p ( w 1 ) p ( w 21w 1 ) p ( w 31w lw 2 ) p ( 1w l w 2 一，) n 乩冉p ( 1w 一h 睢一) 符号兀乩埘p ( ) 表示概率的连乘。当n = l 、n = 2 或n = 3 时候分别称为一元 1 0 内蒙古大学硕士学位论文 模型( u n i g r a m ) 、二元模型( b i g r a m ) 或三元模型( t r i g r a m ) 。以三元模型为例，近 似认为任意词w 的出现概率只同它紧前面的两个词有关，即 、p ( w ) - - 兀瑚。尸( ww 一：嵋一。) 由于语言模型的训练语料不可能无限大，许多合理的词之间的搭配关系在语 料库中没有出现，必然出现数据稀疏现象巨。称之为零概率问题。数据平滑技术用于解决该 问题。数据平滑技术用来对采用最大似然规则的概率估计进行调整。首先它可以保证模型中 任何概率均不为零。其次，数据平滑使模型参数概率分布趋向更加均匀。低概率包括零概率 被调高，高概率被调低。 2 2 查询扩展技术 2 2 1 基于全局分析的查询扩展 全局分析是最早被提出来的查询扩展优化方法。其基本思想是：对整个文献集的语词进行 相关分析( 如语词共现分析) ，得到每对语词的关联程度( 如共现率) ，构造叙词表，再从叙词表 中选取与原查询关联程度较高的词作为扩展词进行查询扩展。这里叙词表是指一种数据结构， 类似于同义词词典，用来表示词与词之间的关系。全局分析的查询扩展技术经历了语词全局聚 类技术 5 - 11 、相似性叙词表 1 2 ，1 3 、潜在语义索引 1 5 ，1 6 等发展阶段。 2 2 1 1 基于语词全局聚类的查询扩展技术 其基本思想是：对整个文献集的全部文档聚类生成不同的簇，由这些簇组成全局叙词表或 者对每个簇构造相应的局部叙词表。 v o o r h e e s 在1 9 8 6 年 8 ，c r o u c h 和y a n g 在1 9 9 2 年 9 ，h u n a g 在2 0 0 3 年 1 0 和j i a h o n g d a i 在2 0 0 4 年 1 1 的研究成果表明，这种扩展方法确实能提高检索性能。其主要缺陷是不能处 理查询词的歧义性问题。即如果一个查询词有多个意义，词的聚类算法会把词分配到不同的簇 中，从而使查询结果更含糊，查询性能可能会下降。 2 2 1 2 基于相似性叙词表的查询扩展技术 为了解决上述中的缺陷，q u i 与f r e i 在1 9 9 3 年提出了基于概念的查询扩展技术 1 2 。j i n g 与c r o f t 在1 9 9 4 年则提出t p h r a s e f i n d e r 技术 1 3 。这些技术在一定程度上解决了查询词歧义 基于l u c e n e 的个性化搜索引擎的研究与实现 性问题。它们的共同点是：所选的扩展词要与全部原查询词同现。 q u i 与f r e i 构建的相似性叙词表在查询扩展中用于计算检索词和整个查询的相似性。主要 思想是：首先对全部文档进行分析，建立一个检索词与文档间的关联矩阵t ，然后构造检索词之 间的关联矩阵s = t t t ( t t 为t 的转置矩阵) ，文档集出现的检索词与整个查询的相似性是 用前者和后者中每个检索词相似性的权重值的和来表示，将此权值按降序排列，前列检索词作 为扩展词。但这种方法的计算开销非常大。 2 2 1 3 基于潜在语义索引的查询扩展技术 一些学者利用l s i 方法来解决上文节中的问题并取得了一定的成果。l s i 试图通过使用检 索词的共现信息进行奇异值分解( s v d ：s i n g u l a rv a l u ed e c o m p o s i t i o n ) 来发现检索词之间 的重要关联关系，以减少向量空间的维数。l s l 分析每一个检索词出现的上下文的相似性，创建 一个低维的特征向量空间。在此空间中，出现在相似上下文中的检索词聚集在一起，如给定一 个阈值，与特定检索词相似的检索词就很容易得到，将这些词加入到原查询就可以实现查询扩 展。 它的缺点依然是计算开销很大 1 5 ，1 6 。虽然l s i 提高了系统的查全率，但这是以损失查准 率为代价的。另外，l s i 虽然对同义词解决较好，但对一词多义问题只能部分解决。 2 2 2 基于局部分析的查询扩展 局部分析的扩展技术较好地解决全局分析的缺陷。它主要是利用初检出的与原查询最相 关的n 篇文档作为扩展词的来源。局部分析扩展技术主要有局部聚类技术、用户相关反馈技术 和局部上下文分析技术等。 2 2 2 1 基于局部聚类的查询扩展技术 基于局部聚类的扩展最早是由a t t e r 和f r a e n k e l 在1 9 7 7 年提出来。它依据全局聚类算法， 首先对初检出的文档聚类，得到局部簇，然后从簇中选取与原查询相关的语词进行查询扩展。 由于其分析的文档较少，从而提高了检索速度。主要缺点是：若初检出的文档与原查询相关程 度低下，则扩展后检索性能反而下降：另外，其扩展效果对前n 篇初检出的文档篇数n 较敏感，检 索性能不稳定。 1 2 内蒙古大学硕士学位论文 2 2 2 2 基于局部上下文分析的查询扩展技术 x u 和c r o f t 在1 9 9 0 年提出l c a 方法成功地解决了全局分析方法中计算量大和上文中对n 敏 感的问题 1 8 。l c a 方法在整体上是局部分析，但其利用全局分析中的p h r a s e f i n d e r 技术，并仅 仅考察初检出的最相关的前n 篇文档的共现率，从而减少了计算量。l c a 以概念为查询单位来进 行扩展。其基本思想是：从初检出的文档中选出与原查询词共现的概念，计算每一个概念与整 个查询的相似度并排序，排在前面的概念作为扩展词。 l c a 方法被用于检索系统i n q u e r y 1 4 中，并在t r e c 标准测试集上取得良好的效果。实验结 果表明，l c a 方法对n 的选择敏感度比局部聚类的方法要小得多 1 8 。对于l c a 方法，n 可取3 0 至3 0 0 之间，其检索效果都有很大的提高，而局部聚类方法对n 的选择仅局限1 0 以内。主要原因 是它们的扩展策略不同所致，即l c a 针对的是前n 个初检文档的段落而局部聚类法选择的是前n 篇初检文档：另外，l c a 选择的是与原查询词共现的概念而局部聚类法选择的是前列文档中高 频出现的检索词。 2 3 相关性计算及排序技术 2 3 1 传统的相关性排序技术 随着i n t e r n e t 的出现和迅速发展，用户在网上搜索信息时都会用到搜索引擎，搜索引 擎的结果排序就是搜索程序在搜索到一定数量的结果后就按照一定的方式返回给用户，用户 最关心的是得到的结果是不是自己最想要的，而这些最想要的结果出现在越前面越好。这就 涉及到搜索引擎是按什么标准来判断用户查询与搜索结果间的相似程度，就涉及到搜索引擎 结果排序的问题。 在传统的搜索引擎中评价查询和文档的相关度的方法中最经典、最有影响的是g e r a l d s a l t o n 等在3 0 多年前提出的“向量空间模型 ( v e c t o rs p a c em o d e l ，v s m ) 1 9 。该模型 的基本思想是：把查询q 和文档d 看成由相互独立的词条组构成，这样，文档d 和查询q 都可以被简化为词汇的集合。不失一般性， 令= f 。，t ：，t ， 为一个词典，t i 为词项，n 为它的规模，则 d = ( f p ，t 2 m 2 ，t n ”，) ，g = ( f 1 ，t 2 “，f ) 式中m i ，n i ( i = 1 ，2 ，n ) 表示相应词项出现的个数，即词频t f ，在通常情况下，人们去掉 基丁l u c e n e 的个性化搜索引擎的研究与实现 t i 而直接用m i ，n i 来表示d 和q ，而且在实际中用规格化表示。这样d = ( ，w n ) ， 其中，w = ，z ，z m ，同样的q 也有这样的形式。但是另一方面，若一个词项t i 在许多文 档中都出现，尽管它可能在文档内部出现的频度也很高，但是它对于不同文档的区分能力就 不会很强，因此引入文档频率d f ( t i ) ：砖m ，其中表示词项在文档集合d 中涉及的个数，m 表示集合d 的大小。但是这里需要的是一个与d f 成反比的量i d f ，因此定义肼净i g m k ， 这样包含这个词的文档个数越少，i d f 的值就越大，如果文档集中的每一个文档都包含这个词， 那么i d f 的值为0 。也就是说，如果一个词出现在文档集的每一个文档中，那么这个词在从 文档集中区分出该文档时几乎不起任何作用。把词项的权重w ，重新定义为：w ；= t f i * i d f ；， 因此在求文档与查询的相关性就变成了求d 和q 向量的某种距离，最常用的是余弦距离： 嵋g ， 驯以g ) 堋s ( 以曲2 氚 2 3 2 基于超链接结构的排序技术 根据情报学中的引文分析法，一般来说，某期刊或论文被引用的次数越多，越能证明该 期刊或论文的质量。同样，把这个思想移植到互联网上。如果指向这个网页的链接来自大量 具有同类内容的网页，那么这个网页就可以看作是权威网页( a u t h o r i t y ) 或中枢网页( h u b ) 。 此时搜索结果的相关性排序并不完主依赖于词频统计，而是更多地依赖超链分析。在考虑一 个网页被另一个网页的引用时候，不是单纯的将被引用网页的h i tn u m b e r 加1 ，而是将引用 网页的连接数作为权，同时将该引用网页的重要性考虑进来，就可以得到扩展后的网页评分。 g o o g l e 最早提出网页评分的p a g e r a n k 算法。它提出了一个“随机冲浪”模型来描述网络 用户对网页的访问行为。模型假设如下： ( 1 ) 用户随机选择一个网页作为上网的起始网页； ( 2 ) 看完这个网页后，从该网页内所含的超链接随机的选择一个页面继续进行浏览；