（计算机应用技术专业论文）基于相关度模型的个性化元搜索引擎设计与实现.pdf

东北大学硕士学位论文摘要 基于相关度模型的个性化元搜索引擎设计与实现 摘要 面对着w e b 上面的海量信息，w e b 用户往往只对其中的很小一部分感兴趣。不同的 用户，由于他们各自的需求不同，因此他们需要用不同的“角度”、不同的方式去“看 待”w e b 上面的海量数据，他们所关注的那一小部分信息往往有很大不同。在这种前提 下，普通的w e b 搜索引擎，由于其使用的页面评估技术并不考虑各个不同用户的使用 习惯和偏好，因此它们不可能满足所有人的需求。 对这个问题的一种解决办法就是建立个性化的w e b 搜索引擎。所谓的“个性化”， 也就是搜索引擎会根据单个用户的习惯自动调整自己的设置，以使检索结果尽量满足该 用户的需求。从某种意义上说，个性化搜索引擎就好像为每一个用户单独量身定做了一 个搜索引擎。 本文介绍了一个个性化的元搜索引擎的设计与实现。本文中提出使用词汇之间的 “相关度”来存储单个用户的个性化信息。并提出了能够在用户进行检索的过程中自动 建立针对该用户的“词汇相关度”信息的算法，以及3 种不同的利用词汇相关度对底层 搜索引擎所返回的结果进行重新评估并进行个性化排序的算法。 本文首先介绍了构建该个性化元搜索引擎所涉及到的相关技术、相关理论和假设。 相关技术主要包含与元搜索引擎相关的技术和与个性化服务相关的w e b 挖掘技术、文 本建模技术。理论和假设主要涉及到关于语义与词汇之间的联系与区别的论述。 然后，本文介绍了这个个性化元搜索引擎的总体设计和实现细节。包括文本模型、 各个算法的实现，系统地静态模型和动态模型。 接着文本介绍了在该原型系统上进行的实验以及实验结果。我们得出如下结论：相 关度模型是一种有效的个性化技术，它可以大大提高搜索结果的质量。 最后，我们对本文的内容进行了总结，并提出了进一步的工作方向。 关键词：信息检索；个性化；元搜索引擎；词汇相关度 i i 东北大学硕士学位论文 a b s t r a c t t h e d e s i g na n di m p l e m e n t a t i o no f ap e r s o n a l i z e d m e t a s e a r c he n g i n eb a s e do n c o r r e l a t i v i t ym o d e l a b s t r a c t f a c i n gv e r yl a r g eq u a n t i t yo fi n f o r m a t i o no nt h ew e b ，u s e r sa r eg e n e r a l l yc o n c e m e dw i t h as m a l lp a r to ft h ew h o l ei n f o r m a t i o n b e c a u s eo ft h ed i f f e r e n c e si nu s e r s n e e d s d i f f e r e n t u s e r sm a yn e e dt ov i e wt h ev e r yl a r g ea m o u n to fi n f o r m a t i o ni nd i f f e r e n tw a y s t h es m a l l p o r t i o no fi n f o r m a t i o nt h e yc o n c e m e dm a yb ea l s od i f f e r e n tw i t he a c ho t h e re x t r a o r d i n a r i l y u n d e rt h i sc i r c u m s t a n c e ，n o r m a lw e bs e a r c he n g i n e sc o u l dn o ts a t i s f yt h en e e d s o fa l lp e o p l e a sar e s u l to f i g n o r a n c eo f t h eu s e r s h a b i ti nt h ec o u r s eo f p a g e r a n k i n g as o l u t i o nt ot h i sp r o b l e mi sp e r s o n a l i z i n gt h en o r m a lw e bs e a r c he n g i n e s t h i sm e a n s t h a ts u c has e a r c he n g i n ec a na d j u s ts e t t i n g so fi t s e l fa c c o r d i n gt ou s e r s b e h a v i o rt om a k et h e q u e r yr e s u l t sb e t t e r i nt h i st h e s i sii n t r o d u c et h ed e s i g na n di m p l e m e n t a t i o no f m yp e r s o n a l i z e dm e t a s e a r c h e n g i n e is u g g e s tt h a tw ec a r lu s ei r e l a t i o n s h i pt a b l e ”t os t o r eu s e r s p e r s o n a l i z e d i n f o r m a t i o n ia l s od e f i n ea na l g o r i t h mw h i c hc a nc o n s t r u c t r e l a t i o n s h i pt a b l e d u r i n gt h e p r o c e s so fq u e r y a n did e v e l o p3m e t h o d st ou s et h e “w o r d c o r r e l a t i v i t y t or e o r d e r i n g q u e r yr e s u l t sf r o mu n d e r l y i n gs e a r c he n g i n e s a tt h eb e g i n n i n go ft h i st h e s i s ，ii n t r o d u c et h e t e c h n i q u e s ，t h e o r i e sa n da s s u m p t i o n s w h i c ha r er e l a t i o n a lw i t h p e r s o n a l i z e dm e t a - s e a r c he n g i n e t h et e c h n i q u e si n c l u d et h e m e t a - s e a r c he n g i n e t e c h n i q u e a n dt h ew e bm i n i n g t e c h n i q u ew h i c h i sr e l e v a n tt o p e r s o n a l i z e ds e r v i c e t h e o r i e sa n da s s u m p t i o n si n c l u d ed i s c u s s i o n sa b o u tl e x e m ea n dw o r d s t h e n ，is h o wt h ed e t a i l i nt h eo v e r a l ld e s i g na n di m p l e m e n t a t i o no fm yp e r s o n a l i z e d m e t a - s e a r c he n g i n e ，i n c l u d i n gt e x tm o d e l i n g ，i m p l e m e n t a t i o no fa l la l g o r i t h m s ，a n dt h es t a t i c a n dd y n a m i cm o d e lo f t l f i sp e r s o n a l i z e dm e t a - s e a r c h e n g i n e a n d t h e n ，ip r e s e n tt h er e s u l t so fe x p e r i m e n t sw h i c hh a v eb e e nd o n eo nt h i sp r o t o t y p e s y s t e m a n dw eg e tt h ef o l l o w i n gc o n c l u s i o n ：t h ec o r r e l a t i v i t ym o d e li sa ne f f e c t i v e t e c h n i q u ew h i c hc a nd r a m a t i c a l l yi m p r o v et h eq u a l i t yo fs e a r c hr e s u l t f i n a l l y , w em a k eas u m m a r yo nt h i st h e s i s a n dip r e s e n tt h ef u t u r ew o r ka b o u tm y i i t 东北大学硕士学位论文 a b s t r a c t p r o t o t y p e k e yw o r d s ： i n f o r m a t i o nr e t r i e v a l ；p e r s o n a l i z e d ；m e t a - s e a r c he n g i n e ；w o r d c o r r e l a t i v i t y i v 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的 研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的 研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 意。 学位论文作者签名：于插秀 日期：加汐脾f 同q 卑 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文 的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权东北大学可以将学位论文的全部或 部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名；否则视为不同意。) 学位论文作者签名：导师签名： 签字日期：签字日期： 东北大学硕士学位论文第一章绪论 第一章绪论 1 1 研究背景 信息时代，随着网络信息总量的迅速增长，网络逐渐深入到人们生活的方方面面。 网络上数百亿w e b 页面所包含的大量的知识使很多网络用户受益。然而，网络信息数 量的不断增多，也给网络用户带来了新的问题如何才能从这数百亿w e b 页面中快 速找到自己所感兴趣的内容。 由于网络上的信息是非结构化的、动态的、并且又包含很多种不同的语言文字，这 使得w e b 信息检索这个问题成为一个挑战。尽管像g o o g l e ( h t t p ：w w w g o o g l e t o m ) 、 a l t a v i s t a ( h t t p ：w w w a l t a v i s t a c o m ) 以及l y c o s ( h t t p ：w w w 1 y c o s t o m ) 这些商业化的通 用w 曲搜索引擎已经在某种程度上解决了w e b 信息检索这个问题，然而由于w e b 用户 数量庞大，这种通用的搜索引擎不可能同时满足所有用户的需求。因此，w e b 用户在面 对搜索引擎所返回的动辄数百万条的查询结果时，常常会感到困惑和无奈。 不仅如此，w e b 搜索引擎的另一个重要缺陷是单个搜索引擎所能够检索的页面数非 常有限。不仅如此，每个商业化的w e b 搜索引擎都有一套自己的算法来进行页面搜索 和对页面进行评价，甚至不同的搜索引擎，书写检索词的语法格式也不尽相同。用户不 太可能了解所有搜索引擎的特性和语法格式。在用户不了解搜索引擎的使用方法的情况 下，显然，信息查找必定是低效的。从用户的角度来看，“应付”太多的各不相同的搜 索引擎是很麻烦的。元搜索引擎的发展，在一定程度上解决了以上的问题，但是，如何 将来自不同的底层搜索引擎的查询结果组合起来、如何能够将更加“有用”的结果更“早” 的显示给用户仍然值得研究。 另外，由于网络页面的日点击量很大，绝大多数搜索引擎没有足够的处理能力来对 w 曲页面以及用户在浏览w 曲页面的过程中体现出来的行为特征进行分析。因此，绝 大多数搜索引擎仅仅将w e b 页面按照某种算法进行评估，然后按照评估值的高低对页 面进行排序。用户在真正打开一个页面之前，不能对页面的大体内容有一个大概的了解。 针对以上问题提出的在w e b 信息检索领域中存在的一些问题，目前主要存在两种 解决方案。 一种是构建个性化的搜索技术。这是一种可以让用户自己进行定制的搜索代理，它 1 东北大学硕士学位论文第一章绪论 可以在收集w e b 页面信息的同时，根据用户的定制需求，对w e b 页面进行实时分析。 由于这种代理程序一般运行在用户自己的电脑上，具有比较充裕的计算能力，这使得用 户可以在这种搜索代理上运行比较复杂的分析算法。 第二种方案是领域搜索引擎( 也称作专业化搜索引擎) 。这种搜索引擎仅收集与特 定领域相关的w e b 页面，并且对这些页面建立索引以供用户查找。例如b u i l d i n g o n l i n e ( h t t p ：w w w b u i l d i n g o n l i n e c o m ) 和l a w c r a w l e r ( h t t p ：w w w 1 a w c r a w l e r c o m ) 就属于这 一类搜索引擎。b u i l d i n g o n l i n e 专注于搜索建筑业的w e b 信息，而l a w c r a w l e r 专注于搜 索互联网上的与法律相关的信息 1 】。 1 2 研究意义 尽管，理想情况下，以上所述的两种方案能很好的解决国际互联网上的海量数据与 用户需求之间的矛盾，然而实现起来，仍然存在很多尚不能很好解决的问题。 第一种方案，个性化的搜索技术，需要解决如何高效率地搜索针对某一用户的个性 偏好的w e b 信息，这需要复杂的个性化分析算法。 第二种方案，领域搜索引擎的内容构造过程比较困难。在领域搜索引擎的内容构造 过程中，系统必须确定哪一个超链接指向高质量的w e b 页面。系统还需要能够在相关 页面和不相关页面之间进行区分。 在本文中，我们将主要讨论实现个性化搜索的一种可行方案个性化元搜索引 擎。 作为一种个性化搜索技术，本文所描述的系统解决了如下主要问题。 ( 1 ) 自动收集用户的各种信息。这其中包括一种动态的、交互的、启发式的自动 收集用户行为特征的算法。 ( 2 ) 分析用户数据，创建符合用户特征的访问模式。这既包括对收集到的用户特 征信息进行挖掘，也包括对信息挖掘的结果进行存储的策略。 ( 3 ) 结合用户的行为特征、访问模式，向用户提供个性化的搜索服务。 我们的原型系统使用一种我们自己提出的文本建模技术词汇相关度模型 来构建个性化元搜索引擎。由于本文所提出的词汇相关度模型是专门针对个性户信息检 索而设计的，因此该模型能够很方便的解决上述在实现个性化搜索的过程中遇到的主要 技术问题。 2 东北大学硕士学位论文第一章绪论 1 3 论文安排 本文详细的讨论了在构建基于相关度模型的个性化元搜索引擎中需要解决的关键 性问题，并提出了一种新的个性化特征模型“词汇相关度”模型。由于我们的系统 是建立在词汇相关度模型的基础之上，因此本文在内容结构上，会在介绍系统总体结构 之前，先来详细介绍本文所提出的词汇相关度模型。而后，再依次介绍个性化元搜索引 擎的总体设计方案与详细设计方案。本文各章的内容按如下方式组织。 第一章，绪论，简要介绍本文的课题背景、研究的目的和意义，以及论文内容的结 构安排。 第二章，个性化检索技术的研究背景和现状，简述个性化检索技术产生的背景以及 该领域的研究现状。并对当前个性化w e b 信息检索技术中通常使用到的文本建模技术 进行了简要综述，分析了其各自的优点和缺点。 第三章，个性化元搜索引擎总体设计，在这章，我们提出一个新的用户个性化特征 模型“词汇相关度”。并且详细讨论了与“词汇相关度”技术有关的一些概念。另 外还介绍了使用“词汇相关度”技术实现的个性化元搜索引擎的整体结构，以及设计过 程中的各种设计问题，这些问题包括用户个性信息的自动提取、网页结果的评价等等。 第四章，个性化的元搜索引擎原型系统实现，介绍原型系统的设计与实现细节，并 且简单介绍了实现过程中使用到的相关技术。 第五章，实验与结果分析。在我们的原型系统之上，针对系统的性能，进行了多项 实验，在这一章中，我们给出的各项实验的结果，以及对结果数据的分析。 第七章，结束语，对本文的工作进行了总结并提出了进一步的工作。 3 东北大学硕士学位论文第二章个| 生化检索技术的研究背景和现状 第二章个性化检索技术的研究背景和现状 2 1w e b 信息个性化搜索技术产生的背景 w e b 信息的个性化检索技术是在很多背景原因的共同作用下产生的：这些因素主要 包括： ( 1 ) i n t e r n e t 的兴起和迅猛发展。这使得互联网上面的数据量以惊人的速度增长。 由于互联网数据量的增大，数据的更新量也与网络数据量同步增长。另一方面，i n t e m e t 的用户数量也呈示数增长； ( 2 ) i n t e m e t 上面的资源的特征和状况。互联网上面的资源种类繁多，又具有很多 不利于检索的特征。 ( 3 ) 近些年来计算机领域，尤其是在机器学习、人工智能、数据挖掘、自然语言 处理等领域内的研究有了很大进步。这使得将这些技术应用于信息检索领域成为可能。 在这些背景条件下，将传统的信息检索技术直接应用到i n t e m e t 环境中，不能满足 用户的需要。在i n t e r n e t 环境下，传统的信息检索技术暴露出很多缺陷。为了弥补传统 信息检索在i n t e m e t 环境下所暴露出来的种种缺陷，人们针对各个问题。利用计算机学 科中的最新技术分别提出了很多解决方案，而个性化信息检索技术就是这么多解决方案 中的一个。 2 2 传统的搜索引擎在i n t e m e t 信息检索中存在的问题 i n t e m e t h 的信息资源数量庞大、内容不稳定、i n t e r n e t 的用户众多，使得人们在 i n t e m e t 上查找信息时离不开搜索引擎( s e a r c h e n g i n e ) 。目前，搜索引擎己经成为i n t e m e t 信息检索方式的主流。据c n n i c 于2 0 0 5 年1 月发布的中国互联网络发展状况统计报 告显示高达6 5 o 的网络用户经常使用搜索引擎，搜索引擎成为中国当前第二大互 联网服务，仅次于收发电子邮件闭。 搜索引擎的功能是帮助用户迅速找到用户所感兴趣的资源，在i n t e r n e t 环境下，传 统的典型的实现是基于关键词匹配的信息检索服务。传统的i n t e m e t 搜索引擎不拥有或 仅拥有极少量的知识，并且其设计的目的是面向全体搜索引擎用户。传统的搜索引擎不 划分知识领域、不对特定用户建立任何描述信息、使用关键词匹配，这些设计都限制了 划分知识领域、不对特定用户建立任何描述信息、使用关键词匹配，这些设计都限制了 5 东北大学硕士学位论文第二章个性化检索技术的研究背景和现状 第二章个性化检索技术的研究背景和现状 2 1w e b 信息个性化搜索技术产生的背景 w e b 信息的个性化检索技术是在很多背景原因的共同作用下产生的：这些因素主要 包括： ( 1 ) i n t e m e t 的兴起和迅猛发展。这使得互联网上面的数据量以惊人的速度增长。 由于互联网数据量的增大，数据的更新量也与网络数据量同步增长。另一方面，i n t e m e t 的用户数量也呈示数增长。 ( 2 ) i n t e m e t 上面的资源的特征和状况。互联网上面的资源种类繁多，又具有很多 不利于检索的特征。 ( 3 ) 近些年来计算机领域，尤其是在机器学习、人工智能、数据挖掘、自然语言 处理等领域内的研究有了很大进步。这使得将这些技术应用于信息检索领域成为可能。 在这些背景条件下，将传统的信息检索技术直接应用到i n t e r n e t 环境中，不能满足 用户的需要。在i n t e m e t 环境下，传统的信息检索技术暴露出很多缺陷。为了弥补传统 信息检索在i n t e r n e t 环境下所暴露出来的种种缺陷，人们针对各个问题，利用计算机学 科中的最新技术分别提出了很多解决方案，而个性化信息检索技术就是这么多解决方案 中的一个。 2 2 传统的搜索引擎在i n t e m e t 信息检索中存在的问题 i n t e m e t 上的信息资源数量庞大、内容不稳定、i n t e r n e t 的用户众多，使得人们在 i n t e m e t 上查找信息时离不开搜索引擎( s e a r c he n g i n e ) 。目前，搜索引擎己经成为i n t e m e t 信息检索方式的主流。据c n n i c 于2 0 0 5 年1 月发布的中国互联网络发展状况统计报 告显示，高达6 5 o 的网络用户经常使用搜索引擎，搜索引擎成为中国当前第二大互 联网服务，仅次于收发电子邮件【2 】。 搜索引擎的功能是帮助用户迅速找到用户所感兴趣的资源，在i n t e r n e t 环境下，传 统的典型的实现是基于关键词匹配的信息检索服务。传统的i n t e m e t 搜索引擎不拥有或 仅拥有极少量的知识，并且其设计的目的是面向全体搜索引擎用户。传统的搜索引擎不 划分知识领域、不对特定用户建立任何描述信息、使用关键词匹配，这些设计都限制了 5 东北大学硕士学位论文第二章个性化检索技术的研究背景和现状 搜索引擎的使用效率。由于传统搜索引擎的运行原理、检索机制等方面的技术还不完善， 使得它虽然可以在一定程度上缓解人们查询信息的难题，但还存在一些缺点和不足，具 体如下： ( 1 ) 仅进行简单的关键词匹配，不能深入挖掘关键词背后的语义。因此，搜索引 擎返回的搜索结果经常是答非所问的。 ( 2 ) 忽视不同用户之间的差异。搜索引擎的用户数量是庞大的。不同的用户有不 同的身份地位，自然也有不同的兴趣爱好和检索目的。而传统的搜索引擎对所有用户都 一视同仁，不能体现用户的信息需求个性，这导致某些用户检索得到的结果并非是该用 户所期望的。 搜索引擎的上述缺点使得它在信息检索过程中存在以下问题嘲： ( 1 ) 准确率不高。基于传统搜索引擎进行搜索，不同的用户输入相同的关键字得 到的搜索结果往往是一样的，而由于用户背景、偏好的不同，所关心的内容又是有很大 差别的，虽然搜索引擎返回大量的查询信息，但对于每个用户面言，可用信息又很少， 相对于具体用户而言，搜索引擎返回的查询结果就包含了大量的无用信息。而且返回结 果并不是按用户需求相关度来排序。从大量的返回信息中寻找对自己相关的信息，又会 浪费用户很多时闽和精力。 ( 2 ) 查全率不高。而由于现有的搜索引擎对i n t e m e t 的覆盖率又是有限的( 目前查 全率最高的搜索引擎对i n t e m e t 的覆盖率也只有2 0 左右) ，所以又会漏掉许多具体用户 感兴趣的信息。 因此，搜索引擎在经历了从人工搜索引擎到自动搜索引擎的过程后，逐步开始向智 能化、个性化搜索引擎方向发展。 2 3 个性化信息检索方法简介 用户的背景不同，其所关心的信息领域也各不相同。如何将这种差异和偏好体现在 信息检索中，减少无关信息，提高查询的准确率，进而为用户提供一种一对一的、针对 不同用户量身定做的信息检索服务服务，这种信息服务就称为个性化信息检索服务。实 际上，这就是一种以用户需求为中心的信息检索方法。数据挖掘领域将其理解为二次挖 掘。 6 一 东北大学硕士学位论文第二章个性化检索技术的研究背景和现状 图2 1 个性化信息检索服务一般模型 f 逗2 1 g e n e r a lm o d e lo f p e r s o n a l i z e di n f o r m a t i o nr e t r i e v a ls e r v i c e 如图2 1 所示，首先，不同用户通过各种途径访问w 曲资源，如图2 1 a 所示。其次， 在用户访问w e b 资源的过程中，系统不断“学习”用户的特征，并创建用户访问模型， 如图2 1 b 所示。最后，系统根据得到的用户模型调整服务，以适应不同用户的个性化需 求，如图2 1 c 所示。 只有实现信息服务的个性化，使用用户的个性信息去收集信息、排列信息、整理信 息，才能做到提高搜索精度，提高用户获得所需信息的效率。 为了实现个性化的信息检索服务，就必须对用户的澍览习惯、个人爱好、知识领域、 学术领域及工作领域进行分析、研究和存储。由于个人在日常的工作生活中接触到越来 越多的信息，也需要用越来越多的信息来为他的工作及决策服务，因而怎样应用信息技 术为个人进行信息服务越来越引起信息工作者的重视。个性化信息查询是在相同或是相 近的信息资源当中，对两个不同用户的相似要求，通过软件对用户个性化的学习，把获 得的个性化知识应用于个人的信息搜索过程中。这样软件在信息资源查询后返回的信息 结果是不同的。另外系统还能根据用户的查询请求和用户个性化的知识对查询结果自动 地排序、分类和聚类，然后把查询结果按一定的格式提交给用户。 2 4 个性化w 曲信息检索领域的相关工作和研究现状 随着网络的发展，网络信息的现状和人们的需求之间的矛盾越来越突出，这促使人 们对w e b 信息检索技术进行深入研究。作为w e b 信息检索技术的一个分支，个性化的 w e b 信息检索技术也迅速发展。 为了更好的体现个性化服务与传统服务相比的优势，个性化w 曲信息检索服务必 须充分利用用户的个性化信息。用户的个性特征信息应综合作用于如下三个方面1 4 】： 7 一 东北大学硕士学位论文 第二章个性化检索技术的研究背景和现状 ( 1 ) 使用用户的个性信息来规范，修正用户的查询请求。 ( 2 ) 通过处理查询请求和用户个性信息用来指导信息的获取。 ( 3 ) 使用用户个性的信息来处理查询结果，如过滤和排序。 目前国内外对个性化信息检索的研究取得一定的成就，实现了一些具有个性化信息 服务功能的检索系统或提出了个性化的信息服务的概念。 国外关于个性化信息检索主要是从人工智能的角度出发的，另外元搜索引擎在个性 化信息检索中也取得一定效果。 下面，本文将简要介绍个性化w e b 信息检索领域的相关工作和研究现状。 2 4 1w e b 挖掘技术 w e b 挖掘技术是实现个性化w e b 信息检索的主要技术之一。w e b 挖掘是从数挖掘的 角度发展而来。数据挖掘指的是从大型数据库或数据仓库中提取隐含的、潜在有用的、 易被理解的知识的过程【5 】。将数据挖掘与w w w 相结合，即得到了w 曲挖掘的概念网。 w e b 挖掘就是从w w w 资源上抽取有趣的、潜在有用的模式及隐含信息的数据挖掘过程。 一般的讲，w 曲挖掘可以分为三类( 如图2 _ 2 ) ，分别是：w e b 内容挖掘( w e bc o n t e n t m i n i n g ) 、 w e b 结构挖掘( w e bs t r u c t u r em i n i n g ) 和w e b 使用挖掘( w e bu s a g em i n i n g ) 川。 图2 2w e b 挖掘分类 f i g 2 2 c l a s s i f i c a t i o no f w e b m i n i n g w e b 挖掘的一般过程可以分成三个阶段： 一8 东北大学硕士学位论文 第二章个性化检索技术的研究背景和现状 ( 1 ) 预处理：w e b 挖掘需要对收集的数据进行必要的预处理，例如清除“脏”数据。 ( 2 ) 模式发现：使用不同的w e b 挖掘算法发现用户的访问模式。 ( 3 ) 模式分析：从发现的模式集合中选择有意义的模式。 w e b 内容挖掘是从w e b 资源中发现信息或知识的过程。在创建个性化信息检索系 统时，人们通常应用w e b 内容挖掘对页面内容进行分析。根据实现的方法的不同，w e b 内容挖掘可以分成基于代理的方法和基于数据库的方法。w e b 内容挖掘由于直接处理数 据对象的内容，因此得到的结果一般比较精确。 w e b 使用挖掘技术通常可以应用到两个领域：当用来分析w e b 服务器的访问日志 时，可以利用挖掘得到的服务模型来设计适应性w e b 站点；当应用到单个用户时，通 过分析用户的访问历史来发现有用的用户访问模式。w e b 使用挖掘由于处理数据对象通 常为用户的访问历史或服务器的访问日志，无法得知数据对象代表的内容，因此得到的 结果一般比较粗糙，但是由于该方法比较成熟而且实现起来也较内容挖掘简单，在个性 化信息检索系统中也得到了较为广泛的应用。w e b 使用挖掘的基本方法包括：聚类、关 联规则、序列模式、分类、依赖性建模、统计分析等等。 w e b 结构挖掘包括对页面内部的结构以及页面之间的结构的挖掘。挖掘w e b 结构 信息对于引导用户浏览行为、改进站点设计、评价页面的重要性等都非常重要。p a g e r a n k 算法和h i t s 算法利用w e b 页面间的超链接信息计算页面的权值。w e b 结构挖掘通常需 要整个w e b 的全局数据，因此在个性化搜索引擎和主题搜索引擎研究领域得到了广泛 的应用。 2 4 2w e b 挖掘技术在个性化w e b 信息检索领域中的应用 w e b 挖掘和w e b 信息检索是两种不同的技术，两者既有所区别又紧密相判8 。虽然 w e b 挖掘与w e b 信息检索是两种不同的技术，但w e b 挖掘技术常常应用于w e b 信息检 索领域，以提高信息检索的精度和效率，改善检索结果的组织。下面是w e b 挖掘在w 曲 信息检索系统中的几点应用 9 j ： ( 1 ) w e b 文本挖掘中的文档分类、聚类技术常用于对w e b 文档进行分析处理，并 形成摘要，以改善w e b 文档索引的组织结构。 ( 2 ) w e b 日志挖掘常用于从搜索引擎用户日志服务器端挖掘出用户的检索兴趣， 获得用户的反馈信息，不仅用于提高搜索引擎系统的查准率，还可以方便形成个性化信 息检索。 9 一 东北大学硕士学位论文 第二章个性化检索技术的研究背景和现状 ( 3 ) w e b 结构挖掘常通过分析w e b 页面问的链接关系发现重要的w e b 页面，以改 进搜索引擎的推荐结果。 2 4 3 文本建模技术简介 在各种文本检索技术中，一种很重要的技术就是文本的建模技术。在文本聚类、文 本过滤、个性化文本检索等领域，文本建模技术都扮演着很墓要的角色。到目前为止， 在众多文本建模技术中，最为成功、应用最为广泛的应该算是向量空间模型。当然，不 同的文本建模技术都存在各自的特点、各有所长。因此，本文在详细讨论我们所提出的 “词汇相关度”文本模型之前，将会先来讨论一下传统的各种文本建模技术。 2 4 3 + 文本建模技术的发展 文本模型，本质上讲它就是文本的一种逻辑表示。因为文本的内容都是人类的自然 语言，其非结构化的特性决定了计算机很难自动处理文本信息。因此，为了方便计算机 的自动化文本处理，就需要将非结构化的文本通过某种建模技术转化成一种结构化的逻 辑表示，而后，计算机的各种文本处理算法可以方便的运行在文本模型之上。一般来讲， 文本模型除了要能够以结构化的形式表示文本之外，还应该有利于计算机对文本语义的 自动处理。 早在7 0 年代，文本检索领域出现了很多经典的技术，这其中包括向量空间模型 ( v e c t o rs p a c em o d e l s ) 、基于贝叶斯统计( b a y e s i a ns t a t i s t i c s ) 的布尔方法( b o o l e a n r e t r i e v a l m e t h o d ) 以及简单概率获取模型 10 1 ( s i m p l e p r o b a b i l i s t i cr e t r i e v a l m o d e l s ) 。虽然 到现在已经经过了3 0 年的历史，这些技术至今仍然构成了当今文本检索领域的技术基 础。随着时间的推移，针对不同的具体问题，出现了各种文本建模技术的改良版本。对 传统文本建模技术的改良，使得文本模型的应用十分广泛。由于篇幅所限，本文不能详 细介绍各种文本建模技术的改良版本。本文仅对主要的应用最为广泛的几种文本建模技 术作简要介绍。 2 4 4 文本建模技术研究现状 目前的众多文本模型一般可以分为向量空间模型、布尔逻辑模型和概率推理模型1 1 】。 2 4 4 1 向量空间模型( v e c t o rs p a c em o d e l s ) 目前人们普遍认为向量空间模型是一种非常有效的文本模型( 检索模型) 。它具有 一】o 东j b 大学硕士学位论文第二章个性化检索技术的研究背景和现状 自然语言界面、易于使用【1 2 1 。 在向量空间模型中，使用一个多维的向量来表示一个文档，这个向量的每一个维度 对应于文档中的一个关键词，而向量在这个维度上的值，代表了该关键词在该文档中的 重要程度。例如，对于一个文档d ，如果文档中包含m 个字项，我们就可以使用一个m 维的向量来表示这个文档d 。只要通过某种策略计算出每一个字项的权值( 在文档中的 重要程度) ，就可以将文档d 表示成一个向量。这里假设每一个字项的权值分别用w l 、 w 2 、w 3 w 。表示，则文档d 的向量表示为： d = ( w l ，w 2 ，w 3 ，w m ) ( 2 1 ) 将文本构建成向量，可以按照如下步骤实现。 ( 1 ) 找出文本中所有关键词 ( 2 ) 从所有关键词中去掉终止词( 终止词是指那些在文本中出现频率很高而又没 有什么实际意义的词，例如：“的”、“吗”等等) 。 ( 3 ) 计算剩下的关键词各自的权重 计算字项的权重通常使用的方法是字项频度因子( t e r mf r e q u e n c y 简称t f ) 乘以反 响文档频度因子( i n v e r s ed o c u m e n tf r e q u e n c y 简称i d f ) 1 3 1 。字项频度因子与字项在文 档中出现的频度成正比。反向文档频度因子是用来表示字项在文档中的重要程度。有些 字项在文档中出现的频度很低，可是它们的i d f 却可能很大；而有的字项在文档中出现 的频度很高，其i d f 却可能很小。在向量空间模型的检索系统中，用户的查询是以自 然语言来表示的，采用表示文档向量的方法来表示用户查询的向量。故一个用户查询p 可表示为： p = ( u l ，u 2 ，u 。) ( 2 - 2 ) 其中u j 表示第i 个字项的权重。 按照上述方法构造出向量p 之后，将向量p 与表示文档的向量d 进行比较。一般 来说可以通过计算两个向量之间夹角的余弦来得到两个向量之间的相似度。而后，根据 相似度来判定文档是否满足检索词。 计算两个多维向量夹角的余弦，使用公式( 2 3 ) ： 5 妇( d ，p ) = c 。s ( 。，即2 网d o p = x u j j - 1 ( 2 3 ) 东北大学硕士学位论文第二章个性化检索技术的研究背景和现状 需要注意，使用检索词构造的向量p 与使用文本构造的向量d ，其维度数应该相等， 并且各维度所对应的字项也应该相同。 2 4 4 2 布尔逻辑模型( b o o l e a nl o g i c a lm o d e l s ) 布尔逻辑模型相对于其他文本模型来说更简单一些。在检索过程中，这种模型记录 文档中是否出现某关键词。例如，最简单的关键词表可以只包含三部分信息：关键词、 包含该关键词的文本、关键词在文本中出现的次数。检索时，系统在关键词表中查找检 索词，从而找到包含检索词的文本【1 4 1 。 布尔逻辑模型的最大优点是实现简单、执行效率高、算法易于理解。然而这种传统 的文本建模技术也存在一些不足之处： ( 1 ) 检索结果质量不高。对于一个给定的查询很难控制它的输出结果。有时会得 出很多结果，可与用户个性兴趣相一致的却很少。相反，有时却得不到任何信息。 ( 2 ) 未考虑文档内容与查询的相符程度。对于关键词来说，没有标识其对文档或 查询的重要程度的重要因子或权重。即：所有文档中或查询中的关键词都处于同样重要 的地位，没有主次之分。 ( 3 ) 布尔查询公式可能会产生有背于人们的直觉思维模式的结果。比如一个查询 “aa n dba n dca n dda n de ”，只有包含此查询中所有的项的文档才被得出，包含其中 任意一项与一个项也不包含同样不被作为结果得出。 2 4 4 3 概率推理模型( p r o b a b i l i s t l ci n f e r e n t i a lm o d e l s ) 概率推理模型通过计算文档和用户提交的检索词之间的相似系数来判断用户请求 的页面是否满足用户的需求。这种方法通过应用概率方法减低了相应的文本排列问题的 困难。它的特点是：首先应用模型去计算相关性，其次，应用需求中不同词的权值为线 索判断相关性。 2 4 5 相关研究 矢量空间模型和概率模型，在文献圩峙一，作者比较了这两种常用的表示文档和用户 个性化的模型。矢量空间模型直接用关键词组成的矢量来表示文档和用户兴趣；概率模型 先对文档进行领域分类，再计算文档和用户兴趣与各领域的相关度。并使用这两种模型 对检索结果进行了过滤。矢量空间模型是现在大多数搜索引擎实际使用的文档表示模 型，概率模型对它进行了一定程度的改善，但这两种方法都仅对关键词进行了机械地处 1 2 东北大学硕士学位论文第二章个性化检索技术的研究背景和现状 理，完全不考虑关键词代表的意义，不可能从根本上解决关键词机械匹配方法对查全率、 查准率的影晌。 还有一种方法是使用本体论的方法【1 6 1 。在文献 1 中，作者提出了使用本体论提高文 献检索查准率的方法。这种方法可分为两个步骤： ( 1 ) 首先使用本体库对网页进行领域分类，具体做法是，经过领域分析，得到领 域术语集，用文献的关键词在术语集中进行匹配，得到所有可能与文献匹配的领域。 ( 2 ) 在检索时对用户查询关键词进行处理，由用户指定关键词所属领域，以此提 高查准率。 这种方法的核心是使用领域分类提高查准率，这种方法无疑降低了查全率，同时与 目录式搜索引擎类似，用户与检索系统对领域的分类往往不能完全一致，在实际使用中 查准率也会受到一定的影响。当然由于信息检索领域数据量小，用户对检索系统的使用 水平较高，这种方法有一定的应用价值，而对于搜索引擎，这种方法就不太适用了。 与文献【17 的方法类似，文献【博1 提出了使用通用本体对网络信息及用户关键词进行处 理，介绍了当前的英文通用本体w j r d n e t ，和中文通用本体知网( h o w n e t ) a 在文献【1 明中，作者提出由领域专家与语言专家共同构造本体库，同时建立本体代理 搜集新词，提交后由人工不断丰富本体库。由本体库处理词的同义、多义及相关关系， 以提高搜索引擎的查全率与查准率。这是一种使用本体论彻底解决搜索引擎关键词机械 匹配对查全率、查准率影响问题的方法，但由于互联网的多学科性和动态性，这种方法 对领域专家的要求很高。 在文献旺q 中，提出了一种基于智能代理( i n t e l l i g e n t a g e n t ) 技术的智能化信息检索 体系结构。文献口1 1 中所描述的b r o w s e r b u d d y 系统就是基于智能代理的信息检索系统的 一个实例。另外文献阻1 中所提到的a u t o n o m y 智能代理系统使用神经元网络来识别信息 模式。 另外，文献1 中提出了一种专用的智能代理_ n e w s f i n d e r 系统，这个系统可以按 照用户描述，自动搜索在线新闻。文献】咩- 介绍的b o o k m a r k 系统属于类似的系统。 由以上论述可见，目前对个性化信息检索技术的研究虽然很广泛，但是，尚未出现 一种最优的技术来实现个性化信息检索。各种技术都存在各自的特点。 目前，实现个性化的搜索引擎的主要途径有3 种。 ( 1 ) 基于网页分类的方法。这种实现一般是使用某些聚类算法，将网页自动分类， 然后在用户使用个性化搜索引擎之前，要去用户选择自己感兴趣的领域。然后，系统会 1 3 东北大学硕士学位论文第二章个性化检索技术的研究背景和现状 根据用户所选择的领域来个性化结果排序。 ( 2 ) 基于查询自动扩展的个性化元搜索引擎。这种方法只适用于元搜索引擎。由 于绝大多数搜索引擎的用户并不了解搜索引擎的特性，因此很多用户不能够准确的描述 自己的检索意图。这种方法就是先搜集用户感兴趣的领域，一般来说是给出一个领域列 表，让用户自己选择。然后根据各个领域，对用户的查询进行扩展。例如，如果一个用 户选择感兴趣的领域时选择了“娱乐”，两系统中娱乐这一领域包含了一些扩展用的检 索词，例如，“音乐”、“电影”、“游戏”等等。那么，以后该用户在检索时，他所输入 的查询，就会被系统自动扩展。例如：该用户输入“哈里波特”，系统就会自动将这