（计算机软件与理论专业论文）基于用户兴趣的个性化搜索引擎的分析与研究.pdf

摘要 摘要 基于用户兴趣的个性化搜索引擎是为了满足不同用户的需求，利用用户的兴 趣主题内容，提出的以用户个体为中心的搜索引擎。其目的是更好地为不同兴趣 的用户提供个性化服务。随着网络信息的快速增长，个性化搜索引擎为不同兴趣、 不同知识背景的用户提供更为方便的检索系统，并能够得到更好的检索效果。 本文围绕着基于用户兴趣的个性化搜索引擎的研究逐步展开，针对个性化搜 索引擎的关键技术用户兴趣存储模型的定义和算法进行了深入的剖析，并在 传统的用户兴趣树结构基础上改善了原有的存储结构，并设计相应的创建、更新 用户兴趣树等算法。 其次，本文提出了用户更新速率( 硼r ) 的概念。用户更新速率，是用来判 断用户兴趣变化的快慢，依照用户更新时，兴趣特征词的权值变化和新词的增加 数量，量化用户兴趣变化的快慢。这样可以使系统自动的设定下次用户兴趣树的 更新时间，从而可以根据用户不同的浏览行为，更好的拟合用户兴趣，以获得更 好的查全率和查准率。 另外，本文深入介绍了有关个性化搜索引擎的相关技术，着重介绍了兴趣相 关度的定义以及获取兴趣相关度的方法。 最后，为了考察用户兴趣模型和用户更新速率( 硎r ) 的作用效果，设计了 相应的实验。实验一获取了在用户兴趣模型下，检索系统的查全率和查准率；实 验二模拟两个用户的不同浏览行为，获取了u u r 参与下的更新速度。实验最后， 系统对在u u r 参与下和没有u u r 参与下的用户兴趣模型进行了检索效果方面的 比较。结论是，在用户更新速率( 硼r ) 参与下的用户兴趣模型更能够快速模拟 用户兴趣变化，从而在检索系统中能够达到更好的查全率和查准率。 关键词用户兴趣树；兴趣相关度；用户更新速率；个性化搜索引擎 a b s t r a c t a b s t r a c t p e r s o n a l i z e ds e a r c he n g i n eb a s e do nu s e ri n t e r e s t ，i no r d e rt om e e tt h en e e d so f d i f f e r e n tu s e r s ，u s i n gt h eu s e r si n t e r e s tc o n t e n t ，i ss u b m i t t e db yt h ei n d i v i d u a l u s e r - c e n t r i cs e a r c he n g i n e t h ea i mi st op r o v i d eu s e r sw i t hd i f f e r e n ti n t e r e s t s p e r s o n a l i z e d s e r v i c eb e t t e r w i t ht h e r a p i dg r o w t ho fn e t w o r ki n f o r m a t i o n , p e r s o n a l i z e ds e a r c he n g i n ei sm o r ec o n v e n i e n tt ot h es e a r c he n g i n eu s g r sw h oh a v e d i f f e r e n ti n t e r e s t s ，d i f f e r e n tb a c k g r o u n d s ，a n di sa b l et og e tb e t t e rs e a r c hr e s u l t s i nt h i sd i s s e r t a t i o n ，p e r s o n a l i z e ds e a r c he n g i n eb a s e do nu s e ri n t e r e s ti sc a r r i e d o u ts t e pb ys t e p i ti sf o c u s i n go na n da n a l y z i n gt h ek e yt e c h n o l o g y - t h ed e f i n i t i o no f u s e r s i n t e r e s ts t o r a g em o d e la n da l g o r i t h mi n d e p t h s o m ei m p r o v e m e n to fs t o r a g e s t r u c t u r eh a sb e e nm a d eb a s e do i lt h e 仃a d i t i o n a lt r e es t r u c t u r eo fu s e ri n t e r e s ta n da l s o s o m ea l g o r i t h m sh a v eb e e nm a d ei no r d e rt oc r e a t ea n du p d a t et h em o d e l s e c o n d l y , t h i sd i s s e r t a t i o np r e s e n t st h ec o n c 印to fu s e ru p d a t er a t e ( u u r ) w h i c h i su s e dt od e t e r m i n et h er a t eo fu s e ri n t e r e s t sc h a n g e i tq u a n t i f i e st h ec h a n g e si nu s e r i n t e r e s t a c c o r d i n gt ot h ew e i g h tc h a n g ea n dt h ei n c r e a s eo fn e ww o r d s ，n l i sw i l l a u t o m a t i c a l l ys e tt h es y s t e mt i m ef o rt h en e x tu p d a t e ，w h i c hi sb e t t e rt of i tt h eu s e r s i n t e r e s tb a s e do nd i f f e r e n tu s e r sb e h a v i o r , i no r d e rt og e tb e t t e rr e c a l lr a t ea n d p r e c i s i o nr a t e i na d d i t i o n ，t h i sd i s s e r t a t i o nd e s c r i b e st h et e c h n o l o g i c sw h i c hr e l a t e dt os e a r c h e n g i n e ，f o c u s e so nt h ed e f i n i t i o no ft h er e l e v a n td e g r e eo fi n t e r e s ta n d t h em e t h o dt o o b t a i nt h er e l e v a n td e g r e eo fi n t e r e s t f i n a l l y , i no r d e rt oi n s p e c tt h ee f f e c t so fu s e rm o d e la n du s e ri n t e r e s t ( u u r ) ，t l l i s p a p e rd e s i g nt w or e l a t e de x p e r i m e n t s ，n l ef i r s te x p e r i m e n ti st oo b t a i nt h er e c a l la n d p r e c i s i o nr a t e so ft h er e t r i e v a ls y s t e r nu s i n gu s e ri n t e r e s tm o d e l ；t h es e c o n d e x p e r i m e n ts i m u l a t e st w od i f f e r e n tu s a sw h o h a v ed i f f e r e n tb e h a v i o rw h e n b r o w s i n g i n t e m e ta n do b t a i nt h eu p d a t et i m eu s i n g 嗽t h es y s t e r nm a k e sac o m p a r i s o no f e f f e c t sb e t w e e nt h es y s t e mu s i n g 愀o rn o t t h ec o n c l u s i o ni st h a tt h es y s t e mu s i n g u s e ru p d a t er a t e ( u u r ) i sb e t t e rt os i m u l a t eu s e r si n t e r e s tc h a n g e s ，i no r d e rt ob e t t e r a c h i e v er e c a l lr a t ea n dp r e c i s i o nr a t ei nt h es e a r c h i n gs y s t e m k e y w o r d s u s e r si n t e r e s tt r e e ；i n t e r e s tc o r r e l a t i o n ；u s e r su p d a t er a t e ；p e r s o n a l i z e d s e a r c he n g i n e i i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其 它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示了谢意。 签名： 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校 有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的 全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签二沣导品签赶 第1 章绪论 第1 章绪论 2 l 世纪是i n t e m e t 开始膨胀的时期，它的发展速度是异常惊人的。但是面对 如此浩瀚的网络世界和庞大的电子数字信息，网络用户如何能准确的找到符合自 己需求的电子信息，这已经成为了基于i n t e m e t 研究的重大课题。为了帮助用户 搜索到所需的信息，有关专家开发出了用于i n t e m e t 上的信息检索工具搜索 引擎( s e a r c he n g i n e ) 。这章主要介绍了本课题的研究背景、现实意义和个性化 信息服务系统的发展现状。 1 1 研究背景和意义 i n t e m e t 是世界上规模最大的计算机互连网络，为人们提供了信息共享和交 流的平台。它的应用又从最早的军事、商业已经渗透到了人们的日常工作和生活 当中，成为许多人生活中不可缺少的一部分。与此同时，i n t e m e t 的扩张表现在 信息量的急剧增加上，各种以电子文本形式存在的网络信息正以惊人的速度增 长。目前，因特网上的信息量相当于人类过去1 0 0 年产生的信息总量。但是由于 因特网上的信息纷繁复杂、良莠不齐，因此信息的价值则相对有所削减。 搜索引擎的出现暂时缓解了这一矛盾。据中国互联网络信息中心( c n n i c ) 2 0 0 9 年1 月1 3 日发布的第2 3 次中国互联网络发展状况统计报告中，搜索 引擎是网民在互联网中获取所需信息的基础应用，目前搜索引擎的使用率为 6 8 0 ，在各互联网应用中位列第四，而对于使用互联网的重要性方面，最多网 民认同搜索引擎的重要性，占六成多【i 】。可见搜索引擎已经在网络信息检索方面 的重要性。 但是，仅仅依靠传统搜索引擎已经无法满足人们的需求。调查表明，用户对 现有的搜索引擎的检索结果不够满意1 2 】。目前的搜索引擎还是存在局限性的，主 要是信息丢失、返回过多无用信息，以及信息无关等几方面。归咎其原因，在于 ( 1 ) 搜索引擎不能随着用户的兴趣、专业、地域等不同而个性化描述用户需要 检索的词汇，从而造成因为兴趣、专业、地域等不同而造成的检索歧义；( 2 ) 搜 索引擎并没有能够帮助用户准确描述其需求的功能，使得检索内容过于模糊和概 括，从而造成搜索到无关的信息。因此，人们迫切地需要一些个性化系统来学习 和了解用户的背景和兴趣爱好，从而能够帮助用户在使用搜索引擎过程中，更加 准确、减少歧义地检索到用户自己所需要的信息。那么如何获取和表示用户的背 景和兴趣爱好，如何高效率、高质量地建立用户兴趣的模型，以及如何利用用户 的模型提供更好的信息检索服务，都成为今后研究的热点。 北京工业大学工学硕士学位论文 1 2 国内研究状况 1 2 1 理论研究 随着信息技术的进步和网络的不断扩张，信息资源在全球范围得到了最大程 度的共享。同时，由于用户的个体特殊性以及兴趣偏好多变等特点。因此，i n t e m e t 上的个性化服务系统必须具备三个能力，即用户兴趣模型能很好地反映用户的兴 趣偏好；为适应用户偏好的变化，用户兴趣模型能作适应性的改变；自动寻找相 关领域信息源，主动向用户提供推荐的个性化服务【3 1 。 在个性化服务研究的早期，建模技术并没有得到应有的重视。大量的研究集 中在实现个性化服务的具体技术上，如推荐技术、信息检索技术、用户聚类技术 等，用户建模技术往往只是这些研究中几笔带过的陪衬。然而随着个性化服务的 发展和研究的深入，研究者逐渐意识到，个性化服务的质量不仅仅取决于具体的 推荐技术、检索技术等，还取决于用户兴趣和偏好等特点的可计算描述，而后者 尤其重要。所以，近年来，有关用户建模技术的研究开始从具体的个性化服务形 式中脱离出来，作为个性化服务中的基础技术来研究。 国外学者对于个性化信息检索的用户模型研究的主要成果有： l i e b e r m a nh ，l e t i z i a 6 】提出了信息代理l e t i z i a ，可准确地监控用户浏览行为， 自动形成一个用户模型。系统不要求用户进行显示的评价，主要是通过分析用户 的浏览行为确定用户的兴趣爱好。 c h a n 提出w e b m a t e 4 1 1 ，它是帮助用户有效浏览和搜索w e b 的代理，w e b m a t e 通过多维加权变量记录用户在不同领域的兴趣。 p a z z a n im 【4 2 】和b i l l s u sd t 4 2 1 主张用户以一个专门的主题对页面进行排序，系 统基于网页内容和页面级别学习用户模型，通过模型预测用户是否对页面感兴 趣。 b a l a b a n o v i cn 4 3 】提出的f a b 要求让用户亲自来排序页面，基于页面等级和内 容来发现用户模型。 近几年来，国内对个性化信息检索用户模型也进行了研究，具体集中在用户 模型的表示方法、用户建模方法、用户建模技术、用户模型优化等问题的研究。 如田萱等简述了搜索引擎个性化模型的定义】，论述了用户个性化模式表示形 式，即向量表示法与概念层次表示法，并且提出以h u f f m a n 树的形式组织用户兴 趣词条来描述用户的个性化需求模式。应晓敏中提出了一种面向个性化服务的客 户端细粒度用户建模方法【4 5 1 ，并且将用户兴趣不再简单地区分为用户感兴趣的类 ( i n t e r e s t i n gc a t e g o r y ，简称i c ) 和用户不感兴趣的类( n o n - i n t e r e s t i n gc a t e g o r y ， 简称n i c ) ，而是按照人们通常对兴趣的理解划分为不同的兴趣类。徐科进行了 基于搜索历史的用户兴趣模型的研究【4 6 1 ，全面描述了用户兴趣模型的建立及通过 自动隐式学习算法不断更新、优化模型的处理过程，并给出了对模型的评价标准。 2 第1 章绪论 李宝林1 4 7 】等为高效确立用户的信息需求模型，提出采用动态遗传算法进行启发式 特征术语的选择方法，它可以有效地与其它用户分享信息选择经验，借以优化用 户模型。 1 2 2 原型系统的用户模型研究 据调查，在国外原型系统中分别采用了各种不同的表示用户模型的方式，首 先国外的主要有以下几种【4 】。 m y y a h o o 是一种利用用户手工定制兴趣爱好的建模方法，从而建立用户兴趣 模型，由于y a h o o 站点包含的信息众多，而每个用户真正感兴趣的信息相当有限， 为了提高用户的访问效率、使用户能够直接浏览感兴趣的信息，y a h o o 站点1 9 9 6 年推出个性化服务m y y a h o o 。 m e t a c r a w l e r 系统是w a s h i n g t o n 大学开发的基于i n t e m e t 中八个搜索引擎的元 搜索引擎系统。它提供了统一的接口，用户将查询请求提交给m e t a c r a w l e r ，它 在通过成员调度策略转给其他各个搜索引擎，最后把结果以统一的形式返回给用 户。通过在实际的信息和用户之间生成统一的用户过滤处理层，提高了系统的灵 活性。 凡帽o n a lw e b w a t c h e r 5 】系统是一个用于w e b 浏览的个人软件助理，它伴随用 户从一个页面到另一个页面，并且对系统认为用户感兴趣的超链接加深亮度。但 不足之处在于系统地建议被限制在一个页面存在的链接上。 三e 比妇【6 】是一个帮助用户浏览w w w 的界面a g e n t ，它直接从用户的浏览行为 中推测用户兴趣，当用户在阅读一个w e b 页面时，l e t i z i a 从当前文档开始执行 深度优先搜索，在搜索中提供潜在的感兴趣的超链接，并会在一个单独的w e b 窗口中提供建议。虽然减轻了用户的负担，但是建模的质量并不高。 g r o u p l e n s e t7 】系统是一个用于u s e n e t 新闻的合作过滤系统，此系统存储了 两部分数据：用户提供消息的比率及给予他们比率的用户组织间的关系。 g r o u p l e n s e 系统将新闻消息规划成为兴趣聚类，以提高本地频率的密度。 c i t e s e e r 采用了一个文件的集合方法描述用户模型；i f w e b 采用了加权语义网 来表达关键词及其与上下文之间的关系；s i t e s e e r 采用了书签和目录结构等信息 表示用户模型等。 其次，国内主要代表性的研究有： 南京大学研究的d o l t r i - a g e n t 引。系统的主体技术被应用于网络信息搜索， 主要特征是具有学习功能，并能够获取用户的信息，如用户的兴趣、爱好和思维 方式等。同时，系统可以主动、定期为用户查找信息，并根据用户搜索信息的变 化，相应地调整“知识库”中的通用字和关键字，使之能够有效地适应专业领域 的信息搜索。系统的本地信息库还可以对搜索到的信息进行分类存储和管理，并 具有与其它系统的协作功能。 复旦大学吴立德教授和黄萱菁博士等人参加的t r e c - 9 会议信息过滤 北京工业大学工学硕士学位论文 f i l t e r i n g 子项目，取得了较好的效果【4 8 1 。 东北大学的姚天顺教授和林鸿飞博士等人在他们提出的过滤模型中，用户需 求采用基于实例文本的主题词表示【4 9 】。 中国科学院软件研究所的阮彤、冯东雷等博士在其信息过滤研究中，提出了 基于贝叶斯网络的信息过滤模型b m i f ，描述了信息过滤系统的基本结构【5 们。 研究发现，虽然国外在信息过滤领域的研究比较领先，但是系统的服务质量 不高，并且目前尚不能处理中文文献。国内该领域的研究虽然也有很大进展，但 是信息过滤的技术难度大，特别是中文信息处理的特殊性，更增加了关键技术研 究的难度。 1 3 本文研究内容以及文章结构 1 3 1 本文研究内容 1 本文介绍了搜索引擎和个性化搜索引擎的系统结构和操作步骤，并且着重讨 论了搜索引擎和个性化搜索引擎之间的异同点，详细介绍了个性化搜索引擎中应 用到的相关技术； 2 讨论了与用户兴趣模型有关的技术和概念，用户兴趣树存储模型、兴趣相关 度、中文分词和文本表示； 3 本文提出了用户更新速率的概念，用来判断用户兴趣变化的快慢，依照用户 更新时，兴趣特征词权值的变化和新词的增加数量，量化用户兴趣变化快慢，从 而自动地设定下次更新时间； 4 对用户兴趣模型进行了检索性能的测试，主要测试了用户兴趣模型判断未知 文本是否属于用户兴趣的能力，获取用户兴趣模型的查全率和查准率； 5 模拟两种用户的浏览行为，测试由用户更新速率决定的用户兴趣模型的检索 效果，以及固定更新时间的用户兴趣模型的检索效果，并且进行了比较，由用户 更新速率u u r 参与的用户兴趣模型其更加能快速模拟用户的兴趣变化，从而提 高检索效果。 1 3 2 论文结构安排 第l 章绪论，本章主要介绍了基于用户兴趣的个性化搜索引擎的产生背景、 意义以及相关技术的国内外相关研究成果，并明确了主要研究内容； 第2 章个性化搜索引擎的理论模型及主要技术研究，本章介绍了搜索引擎 模型和个性化搜索引擎的理论模型的构架和各部分功能，以及有关个性化搜索引 擎的主要技术； 第3 章用户兴趣模型及相关技术，本章着重讨论了有关用户兴趣模型描述、 4 第1 章绪论 创建、维护等方面的功能和方法和相关的技术，其中包括兴趣相关度、中文分词、 文本表示方法和用户兴趣树存储模型的定义和算法； 第4 章个性化用户兴趣模型的设计与实现，本章详细说明了个性化用户兴 趣模型的系统架构和执行步骤，并分模块详细说明了各模块的作用、设计和相关 技术； 第5 章实验数据分析，本章对用户兴趣模型检索性能和用户更新速率进行 了实验，并分析了所得到的实验数据； 最后是结论，总结了本文所做的工作以及下一步工作的设想。 5 第2 章个性化搜索引擎的理论模型及主要技术研究 第2 章个性化搜索引擎的理论模型及主要技术研究 随着互联网的迅猛发展，各种信息正以几何级数的方式增长，信息量的膨胀 使得用户很难获得自己所需要的准确信息。为了从i n t e r n e t 上获得准确信息，人 们开始使用搜索引擎作为检索网络信息的工具，但是仍然难以完全满足用户的需 求。为了满足不同用户的需求，提出了以用户个体为中心的搜索引擎，即个性化 搜索引擎。 2 - 1 个性化搜索引擎的理论模型 2 1 1 搜索引擎的模型 现有的搜索引擎系统一般包含5 个基本部分：网络蜘蛛( s p i d e r ) 、分析器 ( a n a l y z e r ) 、索引器( i n d e x e r ) 、检索器( s e a r c h e r ) 和用户接口( u s e ri n t e r f a c e ) 。 j 鬈移ji j 图2 1 搜索引擎模型 f i g u r e2 1s e a r c he n g i n em o d e l 图2 1 中，网络蜘蛛，负责对网络进行遍历、下载文档和记录u r l 地址： 分析器，负责对网络蜘蛛下载的文档进行分析，以便用于索引记录：索引器，负 责将文档表示为便于检索的方式并存储在索引数据库中；检索器，负责从索引中 找出与用户查询请求相关的文档；用户接口，负责为用户提供界面，可视化的进 行用户的输入输出。 这种传统的搜索引擎模型，没有对用户有任何区分，也就是说任何用户当输 入相同关键字时，返回的搜索结果就会完全相同。而实际上，由于用户的专业背 景、兴趣爱好等的不同，所需要的信息往往是不同的。由于i n t e m e t 上信息巨大， 这种不加区分的检索过程，势必不会完全满足用户的个性要求，会降低检索的正 7 北京工业大学工学硕士学位论文 确性。 2 ，1 1 1 网络蜘蛛 网络蜘蛛，又称搜索器、爬虫( c r a w l e r ) 或者“机器人 ( r o b o t s ) 。如果把 i n t e r n e t 比喻成一个蜘蛛网，那么s p i d e r 就是在互联网上爬来爬去的蜘蛛。网络 蜘蛛是通过网页的链接地址u r l 来寻找网页，从网站的某一个页面( 通常是首页) 开始，读取网页的内容，找到在网页中的其它链接地址，然后通过这些链接地址 寻找下一个网页，这样一直循环下去，直到把这个网站所有的网页都抓取完为止。 因此，网络蜘蛛的运行可以抽象为一个有向图的遍历过程【9 】。如果把整个互联网 当成一个网站，那么网络蜘蛛就可以用这个原理把互联网上所有的网页都抓取下 来。网络蜘蛛对网站的网页获取一般是周期性的，大概为每月一次或者每月数次， 访问次数以网页的更新频率而定，网络蜘蛛的性能很大程度上影响了搜索引擎站 点的规模。 2 1 1 2 分析器 分析器根据网上数据的特点，按照一定的算法，对已经搜集获得的网页和超 链接信息进行分析。从中获取有关网页的客观信息，如作者名、u r l 、更新时间、 编码长度、链接频次度等；同时，可以通过自动化程序分析网页的抽象数据或者 网页内容信息，如关键词、关键字权重、短语、单字等。分析器的功能多数是与 索引器相结合实现的。 2 1 1 3 索引器 索引器的主要功能是收集的信息，建立索引库以供查询。通过由分析器计算 得来的信息，索引器从网页的抽象数据中抽出索引项，建立索引。索引项又分为 客观索引项和内容索引项：( 1 ) 客观索引项，与网页文档的语义内容无关，包括 如作者名、u r l 、更新时间、编码长度、链接频次度等；内容索引项，表述文档 内容，如关键词、关键字权重、短语、单字等。 在索引器中需要面临到的问题，是如何提取诸如关键字等的信息。对于英文 内容的网页，由于词语的独立性，所以通过词语和词语直接的空格就可进行分解 计算。但是对于中文内容的网页，更多的词语意义是要通过字和字之间的结合表 现的，所以需要中文分词技术进行支持。 分析器分析所得的网页描述信息，都是页面到页面描述数据的正排表。索引 器的核心工作就是重新整理这些网页描述信息，对必要的数据项建立倒排表：包 括关键词到网页的倒排表、站点到网页的倒排表等，为用户的检索做准备。索引 器是搜索引擎的核心技术之一，它的策略很大程度上影响了搜索引擎的效率与准 确性。目前，比较常用的方法是对网页的标题( t i t l e ) 和内容( c o n t e n t ) 进行索 弓l t l o j 。 第2 章个性化搜索引擎的理论模型及主要技术研究 2 1 1 4 检索器 检索器，其功能是根据用户的查询关键字在索引库中快速检索文档，进行相 关度评价，对将要输出的结果排序，并能按用户的查询需求合理反馈信息。检索 器常用的模型有：布尔逻辑模型、模糊逻辑模型、向量空间模型和概率模型。大 多数检索系统是把以上各种模型混合在一起，以达到最佳检索效果。而人们对搜 索引擎的检索器功能强弱的判定【1 l 】主要是看检索界面是否友好、检索手段是否灵 活多样、是否有多种途径保证检索结果的精确度、是否提供优化检索结果的各种 帮助手段等几个方面。 2 1 1 5 用户接口 用户接口，是用户与搜索引擎的互动界面，主要功能是用户输入查询关键字、 显示检索器得到的检索结果，或者有用户对检索结果进行的反馈界面，用来方便 用户进行检索、高效获取有用信息等。以百度和g o o g l e 这两大搜索引擎为例， 在其主页中存在搜索界面，用户输入待检索词以及各种简单或者高级的检索条； 在结果输出界面中，搜索引擎将检索结果展现为一个线性的文档列表，其中包括 文档标题、摘要、链接信息等，并按照相似度从大n d , 的顺序排列。用户接口， 一般理解为搜索引擎对用户的直接服务，其界面友好与否，搜索结果是否符合用 户要求将成为用户对搜索引擎评判的标准。 2 1 2 搜索引擎的评价标准 一般来说，搜索引擎的评价标准主要有收录范围、检索功能、检索结果排序、 检索效率、使用接口几个方面【l2 1 。 1 检索效率 在检索效率中，主要用检索时间、查全率、查准率以及月等指标对搜索引 擎进行评价，这也是搜索引擎评价标准中比较硬性的评价指标。 检索时间，是用户从输入查询关键字开始检索开始，到搜索引擎返回给用户 的搜索结果所经历的时间，一般认为检索时间越少，搜索引擎反应越快，当然在 用户检索应用中是比较实际的指标。 查全率，是系统在进行某一检索时，检出的相关文献所占系统文献库中的相 关文献的比重，即：查蟀= 翥慕淼 组。， 查准率，是系统在进行某一检索时，检索出的相关文献占所有检索出的文献 的比重，即： 查准率= 麓器 ( 2 2 ) 查全率和查准率是衡量检索系统效率的两个重要指标，两者结合使用就能够 9 北京工业大学工学硕士学位论文 反映一个搜索引擎的基本检索效果。 几测试值，是查全率和查准率的综合测试值，可以从两者结合角度测试检 索系统效果，即： 砌。试值= 锚鬻 ( 2 3 ) 2 收录范围 搜索引擎根据其检索范围可分为主题型搜索引擎和综合型搜索引擎，对于主 题型搜索引擎来说，搜索范围势必比综合型搜索引擎范围小。而且搜索引擎的收 录范围还由于搜索引擎本身的规模来决定。一般来说，大型搜索引擎收录的范围 比较大，内容比较全。 3 检索功能 在搜索引擎系统中，一般都是对用户输入的关键词进行搜索，其扩展功能包 括布尔逻辑检索、词组查询、用户关键词纠正、限制字段等等。检索功能的增加 一般来说是根据大多数用户的检索行为和特点进行增加的。 4 检索结果排序 一般来说，查找用户检索的关键字可以获得众多检索的网页结果，但是其中 有包括重复的和重要性稍差的网页，因此搜索引擎在这个阶段需要为用户提供可 靠地检索结果排序，可以为用户减少浏览时间，增加用户的检索效率。每个搜索 引擎对其检索排序的方法都有所不同，例如g o o g l e 和百度两大搜索引擎搜索同 一个关键字的搜索结果，其对搜索结果的排序也未必完全相同。所以，检索结果 排序的评价，很大程度上依赖于不同用户的理解和浏览行为。 5 用户接口 主要功能是，用户输入查询关键字并显示检索器的查询结果。使用者接口的 设计也是评价搜索引擎一个相当重要的因素，因为设计不良，即使查询功能再多、 再好，也可能无法吸引大众使用。界面要简单大方，并提供辅助说明或者系统特 性介绍。 2 1 3 个性化搜索引擎的模型 个性化搜索引擎的模型是指根据用户的兴趣和浏览行为等参数，进行个性化 信息的记录和维护，并进行个性化信息检索，从而返回与用户需求相关的检索结 果。 1 0 第2 章个性化搜索引擎的理论模型及主要技术研究 ，一o ， 图2 2 个性化搜索引擎模型 f i g u r e2 - 2p e r s o n a l i z e ds e a r c he n g i n em o d e l 与传统的搜索引擎模型相比较，个性化搜索引擎增加了优化查询模块、优化 结果模块、用户兴趣库以及用户兴趣管理模块四个模块。由于在搜索过程中考虑 到了用户的个体和兴趣的差异，个性化搜索引擎实际上可以提高用户的搜索准确 率和搜索质量。 2 2 个性化搜索引擎的主要技术 2 2 1 查询扩展 在优化查询模块中，查询扩展是主要的技术方法。查询扩展，是指通过使用 已经建立好的用户兴趣库或知识库来对搜索词条进行扩充，从而获取更能满足用 户兴趣和已有知识库的搜索结果，并能够针对不同用户提高搜索引擎的查全率和 查准率( 见公式2 1 和2 2 ) 。 在建立用户兴趣库或知识库后，当用户开始进行检索信息时，获取到用户的 查询关键字，并将具有相关概念或者相似类别的属性加入到用户的查询关键字 中，以起到查询词的扩展效果。例如，某用户的用户兴趣库或知识库包含类别为 “计算机的兴趣词条，当用户查询“程序”时，系统自动确定用户需要检索的 相似类别为“计算机，并将属于“计算机”类别的属性词“计算机”加入到查 询关键字中，即检索词由“程序”变成“程序计算机 ，从而精确了用户的查询 内容，缩小查询范围，减少用户不必要的无用信息浏览。 2 2 2 结果排序 在优化结果模块中，结果排序是很重要的结束。当搜索引擎收到用户的查询 北京工业大学工学硕士学位论文 关键字指令后，首先根据查询的关键字搜索到相关的网页信息，然后对相关网页 排序，使得对用户作用更大或者用户更为感兴趣的网页排到前面。基于这种思想， 势必需要一些对网页评分规则和算法来计算网页排名。本节中主要研究了基于链 接分析的算法以及基于网页内容的算法。 2 2 2 1 基于链接分析的算法 本节主要用p a g e r a n k 算法和h i t s 算法来对基于链接分析( l i n ka n a l y s i s ) 的排序算法进行说明。 1 p a g e r a n k l l 3 i 1 1 4 11 1 5 1 p a g e r a n k 算法是在搜索引擎g o o g l e 中提出的【m 】。算法提出了一个评判网 页重要与否的标志与衡量准则，网页的重要性，是由其他网页引用或链接的次数 决定的。例如，网页彳的链接在网页口中被提及，如果网页c 、d 、e 等都链接 了a ，就说明彳重要性很强，因此网页a 的p a g e r a n k 值也就很高。p a g e r a n k 值公式如下： p a g e r a n 尼( 彳) ：( 1 一d ) + d p a g e r 。a ，n k 。( t f ) ( 2 4 ) 信j o 、1 f ， 其中，p a g e r a n k ( a ) 是页面彳的网页级别；d 是阻尼系数，取值在0 到1 之 间，一般设置为0 8 5 ；p a g e r a n k ( 正) 是页面正的网页级别，页面互链向页面彳； c ( 正) 是页面正链接出去的链接数量。从以上公式可以看出： ( 1 ) 指向页面a 的网页越多，么的p a g e r a n k 值越高，说明页面a 的重要程度 越高； ( 2 ) 指向页面a 的网页正中，页面互的p a g e r a n k 值越高，表示页面彳的p a g e r a n k 值越高，即网页级别越高的页面z 指向页面a ，那么页面a 的重要程度越高； ( 3 ) 指向页面彳的网页z 中，链出的链接个数越少，证明网页彳的重要程度越 高。 p a g e r a n k 算法有效的解决了评价网页的重要性问题，即用网页自身之间的 链接关系评价他们本身的重要程度，是一种比较客观和可靠的方式。在信息飞速 发展的今天，应用该方法到搜索引擎中，有效地提高了检索信息的效果与准确程 度。p a g e r a n k 也作为g o o g l e 特有的方法，沿用至今，得到了亿万用户的肯定与 支持。 2 h i t s 算法 19 9 9 年k l e i n b e r g l l 7 1 提出了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 ) 算法来评 价网页内容的重要性。该算法中，网页的重要性是由用户提出的检索主题来决定 的。根据网页的超链接结构，而将网页分为h u b 页面和a u t h o r i t y 页面，其中 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 i t s 算法描述如下： 1 2 第2 章个性化搜索引擎的理论模型及主要技术研究 1 由用户在检索系统中搜索检索词口，获得一个初始的结果集，构成算法的 根集( r o o ts e t ) ，例如根基的成员个数n = 2 0 0 ； 2 将根集( r o o t s e t ) 扩展为基本集( b a s e s e t ) ，它包含了所有由根集中的成 员页面所指向的页，以及所有指向根集成员页面的页。可以设定扩展上限，如页 面个数为1 0 0 0 5 0 0 0 个； 3 按照公式2 5 和公式2 6 递归计算基本集中每个页面的a u t h o r i t y 权值a 。和 h u b 权值日。，其中彳。、日。初始值为同一个常数k 。根据线性代数理论，可以证 明么。和日。的结果与它们的初始值无关。 a ，= h 。 ( 2 5 ) q ：q - - - p h ，= a q ( 2 6 ) q ：p - - q 其中，gjp 表示网页g 链接到p ，p 专q 表示网页p 链接到g 。对于 任意网页p ，其a u t h o r i t y 值彳，可以通过计算所有链向p 的网页口的日，之和来取 得，其h u b 值日，可以通过计算所有由p 链接的网页口的彳，之和来取得。一个好 的h u b 页面链向很多好的a u t h o r i t y 页面；相对的，一个好的a u t h o r i t y 页面，也 被很多好的h u b 页面所链接【1 8 】。 2 。2 。2 2 基于网页内容的算法 与基于链接分析的算法不同，基于网页内容的算法纯粹是通过分析计算网页 标题、网页内容等信息获取网页的重要程度。针对网页内容的判断准则，可以根 据网页内容是否与用户兴趣库或知识库的内容相同或者相关作为评判准则或者 评分原则。例如，当用户使用检索关键字“苹果 进行检索获得了一个搜索结果 集时，系统凭借已经建立的用户兴趣库得知该用户对“计算机 、“笔记本”等类 别有兴趣时，会自动得为检索结果集成员进行评分，与用户兴趣相关的网页诸如 内容是“苹果笔记本 、“苹果计算机系统 等的网页评分就会比较高，即对用户 的重要程度高，排序的位置比较靠前。 2 2 3 用户兴趣模块的算法 有关用户兴趣库和用户兴趣管理中出现的算法，将在“第3 章用户兴趣模 型的描述及相关技术 中做详细说明。 2 3 本章小结 本章主要介绍了个性化搜索引擎的模型和主要研究技术。首先介绍了传统的 搜索引擎的理论模型，并说明了搜索模型的评价标准。随后引入了个性化搜索引 擎模型，对个性化搜索引擎模型与传统搜索引擎的不同点进行了说明。随后介绍 了有关个性化搜索引擎的主要研究技术，其中有关用户兴趣库和用户兴趣管理中 北京工业大学工学硕士学位论文 出现的算法，将在下一章进行阐述。 1 4 第3 章用户兴趣模型的描述及相关技术 第3 章用户兴趣模型的描述及相关技术 伴随着i n t e m e t 应用的发展和不断壮大，人们越来越需要基于i n t e r n e t 的个性 化服务，从而满足不同用户的个性化需求。而所谓个性化服务1 9 】，就是只对不同 用户采取不同的服务策略，提供不同的服务内容。系统提供用户的不同服务的前 提，是要了解用户的个性特征，而对于用户个性特征最适合的描述方式就是用户 兴趣知识，它是实现个性化的关键。 3 1 用户兴趣模型的描述 3 1 1 用户兴趣模型的定义 用户兴趣模型是针对用户的个性兴趣而建立的模型，也称为“个性化模型” 和“用户模型”。用户兴趣模型【2 0 1 【2 1 1 2 2 1 用于捕捉并记录用户的需求兴趣点，存 储和管理用户的历史行为和用户的背景信息，通过建立模型来记录、管理用户的 兴趣，描述用户可能的潜在兴趣需求。模型中记录下了用户的历史行为以及对系 统的评价，以此优化查询行为，优选查询结果。 用户兴趣模型有多种分类方式：( 1 ) 按照建模的对象划分，可以分为组用户 模型和单个用户模型；( 2 ) 按照信息源划分，可以分为显式模型和隐式模型；( 3 ) 按照时间尺度划分，可以分为长期模型和短期模型；( 4 ) 按照更新方式划分，可 以分为静态模型和动态模型；( 5 ) 按照表现形式划分，可以分为基于属性的模型 和基于知识的模型等。 作为描述用户个性化兴趣特征的用户兴趣模型，它不仅仅是针对用户的兴趣 信息描述，而是一种具有特定数据结构、面向算法的形式化的用户兴趣描述，从 而保证用户兴趣模型可以( 1 ) 被系统自动创建、存储和维护；( 2 ) 伴随用户兴 趣的变化而自动做出相应调整；( 3 ) 利用相应算法获取用户兴趣信息。 3 1 2 用户兴趣模型的功能作用 用户兴趣模块的功能作用主要有以下几点： 1 管理用户基本信息：对用户的背景信息的管理，如教育背景、年龄层次、 专业领域等信息。当搜索一些信息时，可以针对用户的背景信息进行结合式查询， 避免因不同领域和背景所带来的信息歧义。并有助于更好地提供用户真正关心的 信息【2 3 】。 2 获取用户兴趣：用户兴趣模型中非常关键的技术就是如何获取用户兴趣， 按照信息源划分，可以分为显式模型和隐式模型。显示模式，即系统初始化时， 用户对系统进行的人工手动输入兴趣的模型；隐式模型，即系统从用户浏览历史、 用户浏览行为中自动获取用户兴趣的模型。 3 记录、维护、管理用户兴趣：此功能是利用特有的数据结构记录用户兴 1 5 北京工业大学工学硕士学位论文 趣：基于用户日常浏览行为和浏览内容，并使用有效地算法维护和更新用户的兴 趣信息；从用户兴趣模型中推算出用户的最大兴趣词语，并在查询扩展和结果排 序中得到应用。 3 2 用户兴趣模型的创建 在建立用户兴趣模型的过程中，根据用户的参与程度，通常可以把用户建模 技术分为用户手工定制建模、示例用户建模和自动用户建模等等【2 4 1 。 ( 1 ) 用户手工定制建模 用户手工定制建模，是指用户兴趣模型是由用户自己手工输入或选择自己兴 趣的用户建模方法，是个性化服务发展早期的主要建模方法。用户手工定制建模 方法要求用户从成百上千的众多信息中手工选择自己感兴趣的信息。系统要求用 户输入感兴趣的关键词，然后系统将用户的关键词作为兴趣模型，进行个性化推 荐。 缺点则是( 1 ) 完全依赖于