（信号与信息处理专业论文）搜索引擎中搜索结果组织的研究.pdf

摘要 摘要 搜索引擎是信息网络时代人们不可缺少的获取信息的重要工具，人们通过 输入查询来获取搜索结果，从而从网络上的离散海量数据中获取想要的信息。 然面当前搜索引擎返回的结果数量庞大，人们要获取想要的信息仍然比较困难。 用户的需求是以最快的速度获得与查询最相关并且最权威的网页信息。围绕这 两个需求高效的组织查询结果是搜索引擎亟需解决的问题。本文就是在这样的 技术背景下展开研究，研究对象是两种主要的搜索结果组织技术：网页排序和 搜索结果聚类。 首先，以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 使用信息设计个性化的排序算法。 在p a g e r a n k 框架下，综合使用网页内容和链接结构信息，修改经典的随机 访问模型，提出扩展的p a g e r a n k 算法来解决用户对搜索结果的相关性和权威性 两方面需求。修改后的随机访问模型，增强了网页权威性和内容相关性在权值 分配中的重要性。最终开发了网页排序算法实验平台，验证了算法的有效性， 相同条件下可以获得比p a g e r a n k 更好的排序结果。 中文网页信息处理时中文分词是必不可少的重要步骤之一，针对基于字典 的中文分词算法对歧义词和未登录词分词效率低的问题，提出基于字典和后缀 数组的分词算法，实验表明本算法可以有效提取高频未登录和歧义的词和短语。 对传统的聚类算法和文本聚类算法进行了综述性研究，指出用于搜索结果 聚类算法的特别要求，实时性，即高效性，和能够准确的提取聚类描述。 最后，提出基于关联规则挖掘的搜索结果聚类算法，将网页集看作事务集， 将网页中的每个词看作事务项进行关联规则挖掘。最后将此聚类算法用于设计 开发的元搜索引擎系统，实验结果表明此算法可以有效地进行网页聚类，可以 较容易地提取较准确的聚类描述，并且容易实现层次聚类。 关键词：网页排序，搜索结果聚类，中文分词，元搜索引擎 i i a b s t r a c t i ni n f o r m a t i o na g e , s e a r c he n g i n ei so n eo ft h em o s ti m p o r t a n tt o o l s ，w h i c hi s i n d i s p e n s a b l ef o rt h ep e o p l er e t r i e v i n gi n f o r m a t i o n u s e r sr e t r i e v ei n f o r m a t i o nf r o m d i s c r e e ta n dh u g ed a t ai nn e t w o r kb ys u b m i r i n gq u e r i e st os e a r c he n g i n e b u tt h e n u m b e ro fs e a r c hr e s u l t si st o ol a r g et ob r o w s e r u s e r sm u s ts p e n dal o to ft i m ei n o r d e rt of i n do u tt h ev e r yi n f o r m a t i o n h o wt oo r g a n i z et h es e a r c hr e s u l t se f f e c t i v e l y s ot h a t1 l s e r sc a ng e tm o s tr e l e v a n ta n dm o s ta u t h o r i t yi n f o r m a t i o nt h e yw a n ti nt h e l e a s tt i m ei st h ep r o b l e mt h a tm u s tb er e s o l v e du r g e n t l y i ns u c hb a c k g r o u n d , t h e s e a r c hr e s u l t s o r g a n i z a t i o nt e c h n o l o g yi sr e s e a r c h e d ，f o c u s i n go np a g er a n k a l g o r i t h ma n d s e a r c hr e s u l t sc l u s t e r i n ga l g o r i t h m ， f i r s t l y , t r a d i t i o n a lp a g er a n ka l g o r i t h ms u c h 船p a g e r a n k , h i t sa n dt h e i r v a r i a t i o na l g o r i t h m sa r es u r v e y e di nd e t a i li np e r s p e c t i v eo fw e bm i i l i n g ，s u c h 舔 w e bc o n t e n tm i n i n g ，w e bs t r u c t u r em i n i n ga n dw e bu s a g em i n i n g t h e nt h e d e v e l o p m e n tt r e n d so fp a g er a n ka l g o r i t h ma r ep r e s e n t ，t h a ti su s i n gm u l 虹p l ea s p e c t i n f o r m a t i o no f w e bp a g e s ，a n dd e v e l o p i n gp e r s o n a l i z e dp a g er a n k a l g o r i t h m u n d e rt h ef r a m e w o r ko fp a g e r a n ka l g o r i t h m , a l le x t e n d e da l g o r i t h mi s p r o p o s e d ，b ya n a l y z i n gi n f o r m a t i o n o fw e bp a g ec o n t e n ta n dl i n ks t r u c t u r e s y n t h e t i c a l l ya n dm o d i f y i n gt h ec l a s s i c a lr a n d o ms u r fm o d e l ，i no r d e rt om e e tt h e u s e r 。sd e n m n do fr e l e v a n c ea n da u t h o r i t y i nm o d i f i e dr a n d o ms u r fm o d e l , t h e i m p o r t a n c eo f a n t h o r i t ya n dr e l e v a n c eo f w e bp a g e si nw e i g h ta l l o c a t i o ni se n h a n c e d t h ev a l i d i t yo ft h ee x t e n d e dp a g e r a n ka l g o r i t h mw a sv a l i d a t e do np a g er a n k a l g o r i t h me x p e r i m e n tp l a t f o r m ，a n db e t t e rs e a r c hr e s u l t ss e t sw e r eg o ti nc o n t r a s tt o p a g e r a n k c h i n e s ew o r ds e g m e n t a t i o ni sav e r yi m p o r t a n ts t e pi nc h i n e s ew e bp a g e p r o c e s s i n g i no r d e rt oi m p r o v et h ee x t r a c t i o np r e c i s i o no ft h ea m b i g u o u sa n d b n l o g g e dw o r d so fc h i n e s ew o r ds e g m e n t a t i o nw i t hd i c t i o n a r y , an e wm e t h o dw a s p r e s e n t e db ya p p l ) 7 i n gs u f f i xa r r a ya l g o r i t h mt oe x t r a c t i n gk e yp h r a s e sf r o mt h e s e g m e n t a t i o nr e s u l t s u s i n gs u c hm e t h o di nc o n t r a s tt ot h es i m p l es e g m e n t a t i o n i a l g o r i t h mw i t hd i c t i o n a r y , h i g h e rw o r ds e g m e n t a t i o np r e c i s i o nw a s g o t a no v e r v i e wo ft r a d i t i o n a l c l u s t e r i n ga l g o r i t h mw a st a k e n a n dr e q u i s i t e p r o p e r t i e so fc l u s t e r i n ga l g o r i t h mf o rs e a r c hr e s u l t sw a sp r o p o s e d ，t h a ti sr e a lt i m e ， h i g he f f i c i e n c ya n de a s yt oe x t r a c tc l u s t e rd e s c r i p t i o n a na l g o r i t h mf o rc l u s t e r i n gs e a r c hr e s u l t sb a s e do na s s o c i a t i o nr u l em i n i n gw a s i n t r o d u c e dt oi m p r o v et h eb r o w s a b i l i t yo fs e a r c hr e s u l t s i na s s o c i a t i o nr u l em i n i n g i nt h i sa l g o r i t h m ，s e a r c hr e s u l t sw e r et r e a t e da st r a n s a c t i o ns e ta n dt h ew o r d so fw e b p a g ec o n t e n ta st r a n s a c t i o ni t e m s t h ea l g o r i t h mw a sa p p l i e dt ot h em e t a - s e a r c h e n g i n es y s t e m t h ee x p e r i m e n tp r o v e dt h a tt h ec l u s t e r i n ga l g o r i t h mg o tm u c hb e r e r p e r f o r m a n c et h a nt r a d i t i o n a lk - m e a n sa l g o r i t h m ；i ta l s oc o u l de x t r a c tc l u s t e r d e s c r i p t i o na n di m p l e m e n th i e r a r c h i c a lc l u s t e r i n ge a s i l y k e y w o r d s ：p a g e r a n k ，s e a r c hr e s u h sc l u s t e r i n g ，c h i n e s ew o r ds e g m e n t a t i o n , m e t a - s e a r c he n g i n e 中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究 工作所取得的成果。除已特别加以标注和致谢的地方外，论文中 不包含任何他人已经发表或撰写过的研究成果。与我一同工作的 同志对本研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权， 即：学校有权按有关规定向国家有关部门或机构送交论文的复印 件和电子版，允许论文被查阅或借阅，可以将学位论文编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：压：边鱼 网年e 旯b 第一章导论 第一章导论 随着网络技术的迅猛发展，网络蕴含的信息量急剧膨胀，其中w e b 更甚。 如何从如此庞大并且离散的信息中获取用户需要的信息就成了一个非常棘手的 问题。当今搜索引擎是人们搜索、获取w e b 信息的主要工具之一。搜索引擎从 最初的第一代以人工标注网页为主，到现今大规模使用机器自动获取网页的第 二代搜索引擎，搜索引擎技术得到了长足的发展和进步。本文将重点关注第二 代搜索引擎中搜索结果的组织技术下文中的搜索引擎都是指第二代搜索引擎。 它主要包括网络蜘蛛、w e b 信息预处理、索引、检索、组织和排序几个部分。 网络蜘蛛也称网络爬虫，是一个功能很强的程序，它会定期根据预先设定的地 址( u r l ) 去查看对应的网页，如果网页发生变化则重新获取网页，否则根据该网 页中的链接继续访问下去，网络蜘蛛访问页面的过程是对互联网上信息遍历的 过程。为了保证遍历信息的广度，一般事先设定一些重要的链接，然后对这些 链接进行遍历，遍历过程中不断记录网页中的链接，不断遍历下去，直至访问 完整个互联网。网络蜘蛛将下载的网页保存到临时数据库中，为了提高检索效 率，需要建立索引，索引一般按照倒排文件的格式存放。检索是根据用户的查 询请求找出所有内容与查询请求相关的所有网页。检索出的结果网页必须经过 组织和排序，目的是方便用户浏览并将最相关最权威的网页最先呈现给用户。 本文将重点讨论搜索结果的排序和聚类两个方面，文章第二章将从w e b 挖 掘的三个方面w e b 内容、链接和使用挖掘三个方面综述搜索引擎中的网页排序 技术；第三章提出基于网页内容和链接分析的网页排序算法；第四到第六章专 注于搜索结果的聚类并以元搜索引擎为平台进行实验研究，其中第四章对网页 聚类进行简单综述，第五章提出用于元搜索引擎中搜索结果聚类的特征提取算 法，此特征提取算法结合了基于字典的中文分词和后缀数组算法。第六章提出 基于关联规则的搜索结果聚类算法并将此算法用于元搜索引肇中。第七章总结 全文。 第二章两页排序综述 第二章网页排序综述 随着网络的不断普及和发展，网页的数量正在以惊人的速度增长，截止2 0 0 4 年底全球网页数量已经突破1 0 0 亿张。基于关键词的传统搜索引擎对于特定的 查询返回的页面通常有成千上万之多。据调查，有8 5 的用户只会浏览搜索引 擎返回的第一页结果 1 】，那么如何从这成千上万个页面中将最相关、权威的页 面放在最前列，就成了搜索引擎急需解决的难题。传统的搜索引擎通过网页内 容与查询的相关程度进行排序来解决相关性需求，当今流行的网页排序算法 g o o - g l e 的p a g e r a n k 和i b m 的c l e v e r 系统采用的h i t s 算法从链接分析的角 度来解决权威性需求。单独的按相关度的排序在海量网页数据搜索中，仍然会 得到大量的结果并无法判定结果的质量，即结果网页的权威性的得不到保障： 单纯的链接分析又存在主题漂移等问题，即相关性得不到保证。两种网页排序 技术无法满足用户对查询结果的相关性和权威性的综合需求。下面将结合网页 内容、链接分析和用户行为三个方面从w e b 挖掘的角度详细分析网页排序技术 的发展，并展望今后的发展方向。 2 1w e b 挖掘 w e b 挖掘 2 】是数据挖掘的一种，是从和w e b 相关的数据中获取有用模式和 隐藏信息的过程。可以将w e b 数据分为以下几种：0 ) n 页的实际内容，包括文 本和多媒体数据；( 2 ) 网页的内部结构，包括它的h t m l 或者x m l 代码；( 3 ) 网页间的链接结构；( 4 ) 描述网页如何被访问的使用数据：( 5 ) 用户的个人注册信 息，包括c o o k i e s 中的信息。从挖掘的数据对象的不同可以将w e b 挖掘按图2 1 进行分类。w e b 内容挖掘的对象是网页的实际内容和w e b 搜索的结果。w e b 内 容挖掘又分为网页内容挖掘和搜索结果挖掘，其中网页内容挖掘即是传统的基 于内容的搜索引擎所完成的工作，搜索结果挖掘就是在网页内容挖掘的结果基 础上进一步搜索。w e b 结构挖掘的对象为网页问的链接结构，从网页问的链接 结构中获有用信息，如现在流行的网页排序筇法，就着重考虑网页问的链接结 构，由此获得网页的评价值进行劂页排序。w e b 使用挖掘的对象为w e b 被访问 第二章同页排序综述 的日志和用户的个人信息，它进一步分为一般访问模式跟踪和定制访问模式跟 踪，其中前者是根据网页访问日志信息获得一般的用户访问模式，后者是根据 定制的模式对用户进行分类。w e b 挖掘技术有很多重要的应用，本文主要研究 它在网页排序中的应用。 图2 1w e b 挖掘体系结构图 2 2 基于w e b 内容挖掘的网页搜索和排序 w e b 内容挖掘是基本的搜索引擎工作的延伸，网页内容挖掘和文本挖掘相 似，它的功能从简单到复杂依次为基于关键词的搜索、索引关联、相似性度量 和搜索、分类和聚合以及自然语言处理 2 】。搜索结果挖掘对搜索引擎的结果进 一步处理，得到更精确和有用的信息，其中网页排序就是其中的重要工作，下 面从各种信息获取模型来分析基于w e b 内容的网页排序技术。 布尔模型【3 】是最早的信息获取模型，在布尔系统中，文档用关键词的集合 来表示，查询由通过逻辑操作符号( 如a n d 、o r 和n o t ) 连接的关键词组成， 在查询与文档的匹配过程中，主要看该文档中的关键词是否满足查询条件。尽 管会有系统将结果按照时间等特征进行排序，但布尔系统基本上不涉及文档的 相关度排序。 目前大多数搜索引擎系统使用的是向量模型【4 】，在向量模型中，假设系统 一共涉及，1 个关键词，则文档和查询都是由圩维的向量表示，其中文档向量中 的元素由关键词在文档中的权重表示，权重越大，关键字在文档中越重要。查 询向量中的元素表示关键词相对于用户的重要性。查询与文档的匹配实际上就 是查询向量与文档向量相似度的计算，常用向量内积来计算相似度，对于包含脚 个关键词的查询q 和文档向量d ，则相似度i 十算如下式， 第二章网页排序综述 跏f 胁f 尥。) 5 网q d = 屹 f # i ( 2 1 ) 其中，屹表示关键词在查询和文档中的权重。关键词在文档中的权重一般基 于关键词在文档中的出现频率，经典的计算关键词权重的方法有t f i d f 、o k a p i 和i n q u e r y 等 5 】，假设关键词字i 在文档- ，中的权值为，按t f i d f 方法定义 则= 吮l g ( 彤) ，其中吮是关键词，在文档，中出现的次数，够表示包含 关键词i 的文档数量，表示文档总数。因此关键词在单个文档中出现的频度 越高，则它越能描述文档的内容，另外当它出现在大量的文档中，说明它的区 分能力较差。在基于内容的网页排序中，这些权值计算函数称为排序函数 ( r a n k i n gf u n c t i o n ) ，因为通过这些函数可以计算某个查询关键词与文档的相关程 度。由于网页特有的半结构化特性，关键词在不同的位置具有不同的重要性， 如出现在 、 、 以及 等 标签中的关键词具有较高的重要性，因此在构造网页排序函数时还要考虑网页 的结构信息。f a n 等【6 】运用遗传规划( g e n e t i cp r o g r a m m i n g ) 利用网页结构信息提 出一种构造排序函数的方法，算法将训练集中网页不同部分关键词的出现频度， 出现此关键词的文档数等作为种子，通过遗传操作迭代获得最佳的排序函数。 b u r g e s 等人【7 】提出排序函数训练中的基于概率的代价函数，并运用神经网络训 练排序函数。这些基于学习构造的排序函数取得了优于传统排序函数效果，但 它们的计算过于复杂且需要很长的训练时俺j 。在向量模型中，文档按照与查询 的楣关程度进行排序，相关度的计算依赖于排序函数的正确构造。 另外还有概率论模型【4 】、神经网络模型 8 】、基于命题逻辑的模型【8 】以及语 言模型 9 】，它们分别从不同的角度描述文档和查询，然后计算文档与查询的相 似度。最终文档的排序部是基于与杳洵的相关程度，排序结果的优劣取决于模 型对文档与查询的正确描述。 随着网页数量呈指数级数的增长，海量的网页数据、良莠不齐的网页质量、 查询关键词本身要比查询主题要广泛的多以及高级的信息获取模型高的计算复 杂度，使得基于文档内容与查询相关度的排序不能满足用户在最短的时间内获 第二章同页排序综述 取最相关、权威的文档的需求。因此有必要利用w e b 的其它信息进行网页排序 的研究。 2 3 基于w e b 结构挖掘的网页排序 网页间的链接拓扑结构为w e b 挖掘提供了丰富的信息，链接一方面引导用 户进行网页浏览，另一方面反映了网页作者的一种判断，表示作者对被引用网 页的一种认可，说明它与当前网页内容相关或具有一定的价值。因此充分挖掘 w e b 的链接拓扑结构，可以获得非常重要的信息。本节主要研究w e b 结构挖掘 中链接分析在网页排序中的重要应用以下首先分析p a g e r a n k 和h i t s 两种基 于链接分析的网页排序算法，然后针对各自的缺点讨论改进算法，最后简要分 析超链接拓扑结构图的性质和建模。 2 3 1p a g e r a n k 算法和w e b 访问模型 p a g e r a n k 1 0 1 1 ) 黾首先被g o o g l e 成功运用的算法，它大大提高了搜索引擎 的搜索精度。它的基本思想是从高质量网页链接过来的网页同样也是高质量的 网页，基于这种回归关系定义p a g e r a n k 的具体算法。 构造有向w e b 图g = ( 矿，e ) ，其中顶点v 为所有的网页集合，边e 为网页间 的链接，网页a 中有指向网页b 的链接表示顶点a 、b 间存在一条有向边。假 设网页u ，e 为被网页“链接的网页集合，鼠为链接网页“的网页集合并且 令( “) = k l ，则网页“的权值值e a ( u ) 的计算方法为： p r ( 班薹等 上式的计算规则可以用网页的随机访问模型( r a n d o ms u r f m o d e l ) 进行描述。用户 根据当前网页的链接等概率的访问其它网页，当到达其它网页时同样跟随链接 浏览下去，网页的权值反映的就是被访问的概率，因此被大量链接的网页( 入度 大) 或被权值较大的网页链接的网页具有较大的权值。 对于随机访问模型，存在另外两种情况，一种是存在这样一类网页，它们 不存在链向其它网页的链接：另一种是存在一类出度为零的网页。当用户访问 第二章网页排序综述 到这两类网页时，按照上述模型访问将终止或仅在某一类网页上徘徊。这两类 网页在迭代过程不断累计权值，直至所用的权值沉积到它们上面，这种现象称 为权值沉积( r a n ks i n k i n g ) 。对于这种情况，假设用户会以一定的概率跳转到其 它网页中，继续浏览。假设跳转以相同的概率发生在每一个网页上，得到下面 新的p a g e r a n k 算法修正形式， p r ( 咖d d ( 咖”们荟等 ( 2 3 ) 其中d 为跳转概率，一般取d = o 1 5 。上式表明访问者以概率l d 跟随链 接进行浏览，以概率d 不再跟随链接浏览而是重新以分布d ) 随机选择一个网 页浏览，一般取d ( u ) 为平均分布，即d ( u ) = l n 。 2 3 2h i t s 算法 h i t s ( h y p e r t e x ti n d u c e dt o p i cs e l e c t i o n ) 1 2 算法是k l e i n b e r g 提出的一种依赖 于查询的网页重要性度量算法。它的研究对象是经过传统文本搜索引擎搜索某 个主题获得的相关网页集。h i t s 算法将网页分为权威( a u t h o r i t y ) 网页和中, g ( h u b ) 网页两类。权威网页是某个查询主题下比较重要、权威的网页，从链接结构来 看就是被很多其它网页引用的、入度较大的网页：中心网页是引用了相当数量 权威网页的网页，出度较大的网页。h i t s 算法的思想是两类网页之间的互相增 强关系，即高质量的权威网页被很多高质量的中心网页引用，而高质量的中心 网页引用很多高质量的权威网页。 h i t s 算法是依赖于特定查询的，因此首先给定一个查询仃，从传统文本搜 索引擎获得与查询相关的网页集& 作为处理对象。由于受计算能力限制和实时 性要求，& 要具有三个特点：( 1 ) s o 楣对较小；( 2 ) s o 中有丰富的和查询相关的 网页；( 3 ) & 中包含了大多数高质量的权威网页。假设网页p 的权威权值为a 。， 中心权值为h ，且满足 ，) 2 = l 和( ，) 2 = l ，h i t s 算法步骤如下： 肚s o p e s o 1 ) 选取传统文本搜索引擎关于查询盯返回结果的前f ( 一般f 取2 0 0 ) 个网页 作为根网页集r ，( r o o ts e t ) 。r 。满足( 1 ) 、( 2 ) 两个特点，但远达不到特点( 3 ) 。 第二章网页排序综述 2 ) 对r ，进行扩充，将被r o 中网页引用的其它网页和引用如的网页包括进 来，形成基本集墨( b a s es e t ) 。 3 ) 进行迭代直到收敛， a p = h q ，= a q( 2 4 ) q ：( 叮，p ) e哼( p 坷) e e 其中e 为& 集合中网页形成的w e b 图的边，( g ，p ) 是指网页q 有到网页p 的链 接，即形成一条边。可以证明经过有限次迭代上式是收敛的，实验中迭代2 0 次 左右就可以收敛。 2 3 3p a g e r a n k 和h i t s 算法的综合分析 p a g e r a n k 侧重于权值的分配和随机访问模型，是独立于查询的离线算法。 而h i t s 强调权威网页和中心网页的相互增强关系，是针对特定查询的在线算 法。p a g e r a n k 中重要性的传递是直接从一个网页到另一个网页的，而h i t s 中 权威网页重要性是通过中心网页间接传递的。本节从线性代数的角度分析两种 算法，并将两者统一起来。 令w 为w e b 图的邻接矩阵，当网页i 有到网页，的链接时= 1 ，否则 = o 。向量a = “，a 2 , - - , ) 7 表示节点的权重，对应于h i t s 的权威网页的 权重和p a g e r a n k 的权值。向量日= ( h i ，) 7 表示节点的中心网页权重。 每个节点的入度岛= 。睨，出度q = 。，则入度和出度向量为 如= ( 6 l ，6 ：，吒) 7 和丸= “，0 2 c o 。) 7 ，并定义对角矩阵d 。= d i a g ( d , ) 和 = 击昭( d 。) 。根据h i t s 算法中式( 4 ) 相互增强关系，定义两种操作，9 和 d ”，其中”( ) = w 7 ，o o p ( o ) = w ， a = ，”( ) = l o p ( d 9 ( 4 ) ) = w 7 w a ，h = o o p ( 爿) = o p ( i o p ( h ) ) = w w 7 日( 2 5 ) 当迭代收敛最终解a ，h 分别为矩阵7 矽和w w 7 的主特征向量。 对于p a g e r a n k 算法根据式( 2 2 ) 有 7 第二章刚页排序综述 a = ，”( 彳) ，其中，”( ) = w 7 9 ：= p 7( 2 6 ) 考虑到用户的随机跳转并根据式( 2 3 ) 有， p r ：芝卵7 + ( 1 一d ) w 7 比( 2 7 ) 以 其中e = ( 1 ，l ，1 ) 7 ，最终的收敛值也为矩阵尸7 的主特征向量。 c h r i s 等人 1 3 】从网页链接中的两种现象( c o c i t a t i o n 和c o r e f e r e n c e ) 开始分 析，将两种算法统一到同一框架下，提供了广阔的算法派生空问。网页f ，_ ，被某 个网页同时引用为c o c i t a t i o n ，网页f ，引用同一个网页为c o - r e f e r e n c e ，如图2 2 所示。网页的这两种链接形式表征的是网页f _ ，之间具有一定程度的相似性。 葛瘩k c ) ： ：球0 k 圈2 2 网页中的c o - c i t a t i o n ( 左) 和c o - r e f e r e n c e ( 右) 现象 从图2 2 可以看出，出度大的网页对网页j ，的引用没有出度小的网页对f ，的 引用重要，这也就是p a g e r a n k 算法中按出度对权值进行归一化的基本原理。同 理，网页对入度小的网页的引用没有对入度大的网页的引用要，因此有必要对 权值按入度进行归一化。基于此为p a g e r a n k 算法定义中心网页权值操作 0 ”( ) = 釉：= q 7 ，考虑用户随机跳转，则 q7 = 堡p p 7 + ( 1 一d ) 阡7 d ：l( 2 8 ) 以 结合上述分析，重新定义操作，”( ) 和o 一( ) 如下， ，”( ) = o ”w 7 d - q , ，0 ”( ) = l o p ( ) 7( 2 9 ) 这样p a g e r a n k 和h i t s 被统一到同一框架中，它们是式( 2 9 ) 的两个特殊情 况。式( 2 9 ) 为构造其它算法提供了的广阔空间，并为统一分析两种算法的特性 提供了依据。 第二章网页排序综述 2 3 4p a g e r a n k 算法的改进 p a g e r a n k 算法计算的是整个搜索引擎涵盖的网页的相对重要性，这样一些 知名网站往往获得较高的权值，对于用户的某个查询，这些网站即使与查询不 相关或微弱相关也会排在返回结果的前列。如使用g o c i g l e 查询“c h i n a ”关键 字，排列在最前的不是h t t p ：w w w c h i n a c o m ，而是h t t p ：c n y a h o o e o m 一等。这种 现象称为主题漂移( t o p i cd r i 。另外c h a k r a b a r t i 等【1 4 】和p e n n o c k 等 1 5 】证明了 w e b 图的属性和主题是非常相关的，并且网页通常倾向于引用和自己内容相关 的网页，用户在按链接进行访问时，会根据链接周围的文字等对链接内容的相 关性进行评估，然后进行访问，并不是对每个链接都有平均的访问概率。比如 说有些链接是有注释性的，有些是用于网站导航，有些是广告等，这些链接被 访问的概率肯定是不相同的。 2 3 4 1 主题敏感的p a g e r a n k 算法 为解决上述问题h a v e l i w a l a 1 6 提出一种主题敏感( t o p i cs e n s i t i v e ) 的算法， 将网页按主题分成不同的类，然后离线计算每一类主题中网页的权值矢量，对 于特定的用户查询，首先评估当前查询与各个主题的相关程度，然后根据相关 程度对权值矢量进行加权组合，并以此作为排序依据。网页主题的确定方法一 种是进行网页聚类，另一种是手动的分类，如根据o d p ( o p e nd i r e c t o r yp r o j e 斌) 1 7 工程将网页分成1 6 大类。 t a o 等【1 8 】发展了这种思想，提出依赖于查询的自适应排序算法，强调了 全局和特定主题两种范畴下网页权值的重要性，并结合两者进行排序。搜索引 擎的c r a w l e r 在获取网页后会提取出最能描述网页内容的几个关键字，这种算 法首先为每个关键字找到最相关的前拧个网页，按相关程度对这r 个网页中进 行排序并量化赋值，排序过程考虑到相互间的链接，关键字的位置等等。最后 组合排序的量化权值与全局范围下的p a g e r a n k 权值进行最终排序，两种权值的 不同组合形式对应不同的排序策略。 h a v e l i w a l a 提出的算法存在主题粒度不易确定的缺点，预先主题分类不可能 满足用户查询主题的多样性，并且主题增多带来的是复杂度的增加。t a o 等人 9 第二章州负排序综述 的算法按网页内容的关键字作为主题划分，有效的解决了主题粒度问题，算法 还结合全局范围下的p a g e r a n k 值，充分体现了网页排序的相关性和权威性要 求。 2 3 4 2 加权p a g e r a n k 算法( 用户访问模型改进) p a g e r a n k 算法的随机访问模型按网页出度平均分配权值，并不能真实反映 权值传递和用户访问过程。x i n g 1 9 提出加权p a g e r a n k ( w e i g h t e dp a g e r a n k ) 算 法，他认为重要的网页在权值分配中应该获得较高比例的权重，其中网页的重 要性和网页的入度和出度成正比。假设网页, ，只为网页甜引用的网页集合， 网页v e e ，入度、出度分别为l 和q ，则基于入度和出度的权重因子为 ，2 南，噶，2 南 亿t 加权p a g e r a n k 算法迭代公式如下 p r ( “) - d ，+ ( 1 一d ) p r ( v ) 嚷j k ： ( 2 1 1 ) 月二不 一一 i n g o n g n g a m 等人【2 0 】提出了以主题为中一5 , ( t o p i cc e n 晒c ) 的p a g e r a n k 算法， 思想是网页权值的分配应和网页内容的相似度成正比，被引用的网页内容与当 前网页的内容越相似分配到的权值比重就越大。r i c h a r d s o n 等人【2 l 】提出结合链 接和链接内容信息的访问模型，考虑到用户按网页链接进行访问时偏向于访问 内容相关的网页。访问模型如下式 乞 ) = ( h ) + ( 1 一d ) 弓( v ) 0 ( v “) ( 2 1 2 ) 其中p j u ) 是在查询q 下分配给网页的访问概率即本算法计算的权值， p 寸“) 是在查询口下从网页v 通过链接访问“的概率，名似) 为在查询q 下从 网页v 不按链接跳转到其它网页的概率。假设r ，( “) 为网页“与查询q 相关程度 的度量，则 和，2 器州一咖器 亿 1 0 第二章网页排序综述 从上式可以看出，基于式( 2 1 3 ) 的访问模型倾向于访问与查询相关的外出链接。 查询口与网页“的相关性度量r 。( “) 可以使用传统信息检索的方法，如文章第三 部分所述。 加权p a g e r a n k 从链接的角度，按网页的重要性进行加权来修正随机访问模 型，改进了标准的p a g e r a n k ，但依然存在严重的主题漂移现象；以主题为中心 的p a g e r a n k 从内容的角度，按网页内容的相关性进行加权来改进随机访问模 型，实验结果与p a g e r a n k 相仿；而r i c h a r d s o n 等人的算法结合了这两种方法 提出了智能的随机访问模型( i n t e l l i g e n ts u r fm o d e l ) ，实验取得了优于p a g e r a n k 算法的结果，并且算法的伸缩性和计算复杂度都能满足大规模网页数据的计算 处理。 2 3 5h i t s 算法的改进 h i t s 算法同样存在主题漂移问题，在对很多广义的主题查询时，h i t s 会 错误地将许多与查询无关的网页赋予较高的权值。由于h i t s 算法计算转移概 率矩阵的主特征向量，仅能发现主社i 又( w e bc o m m u n i t y ) ，如果基本网页集中有 少数与查询无关的网页，但它们是紧密链接的，结果往往会收敛到这些网页， 这种现象称为t k c ( t i 曲t l y k n i tc o m m u n i t y ) 现象【1 2 】。 2 3 5 1 结合w e b 文本挖掘解决主题漂移 i b ma l m a d e n 实验室开发的a r c 2 2 系统，通过考虑链接周围的文本，来 克服这一问题。基本思想是为w e b 图中每条边分配一个链接权值w ( i - - - 9 ，) ，如 果从网页i 到网页，的链接周围与查询相关的文本越多则权值越大。w e b 图的邻 接矩阵的构造不同于h i t s ，当网页f ，之间有链接时彬，= w ( i 哼，) ，否则 形= o 。链接权值w ( i 一，) = l + 盯( f ) ，其中打( ，) 为链接周围b 字节内与查询相关 的文本出现的次数，实验中通常取b = 5 0 。a r c 算法采用h i t s 同样的迭代， a = w 7 h ，h = w a ，其中4 ，h 为初始值为l 的向量。h i t s 在扩展根网页集时 第二章 网贞排序综述 只扩展网页链接长度为l 的网页( 直接相邻的) ，而a r c 扩展的链接长度为2 。 a r c 算法目标是找到前1 5 个最重要的网页，所以只要向量a ，h 中前1 5 个值稳 定即可终止迭代，实验表明迭代5 次即可，所以它具有很高的计算效率，开销 主要在扩展根网页集上。 b h a r a t 等f 2 3 】结合传统信息检索技术进行链接分析来解决主题漂移问题。算 法通过分析网页内容，用相似度概念衡量网页内容与查询的相关程度，并依此 预先去除查询子图中与查询无关的网页。由于查询主题要比查询本身更加广泛， 他们用整个根网页集来定义查询主题，将根网页集中每个网页内容的前1 0 0 0 个 词连接起来，作为查询的主题q 。网页与查询q 的相似度按式( 2 1 ) 定义，其中 关键词在网页中的权重根据t f i d f 5 定义。这种算法的缺点是依赖于根网页集 的质量，可以通过查询扩展和网页聚类来获得高质量的根网页集【2 3 。 2 3 5 2 加权h i t s h i t s 算法假设权威网页的权值是由来自不同组织或个人决定的。如图2 3 a 网站a 的很多网页引用网站b 的某一个网页，这就增加了a 上网页的中心( 1 1 u b ) 权值和b 网站那个网页的权威( a u t h o r i t y ) 权值。反之网站a 上某个网页引用b 上很多网页也有类似的情况。这些不同的链接仅仅代表了单个组织或个人的判 断，导致了不应有的权值增加。b h a r a t 2 3 提出用链接加权解决这个问题，他认 为一个网站内的一个网页或多个网页对另一个网站的网页产生的权值贡献是一 样的。假设网站a 上有k 个网页引用网站b 上的一个网页，则为每条链接分配 权威权重( a u t h o r i t yw e i g h t ) l k ，总贡献为1 ，而不是h i t s 中每个链接贡献l ， 总贡献为k ；假设网站a 上有一个网页链接网站b 上，个网页，分配每条链接 的中心权重( h u bw e i g h t ) l t 。经过修改的迭代公式如下， 口= ( ，k e h ，d “t h w t ( j ，f ) 吩= l 。) e d ，h u b w t ( i ，) ( 2 1 4 ) 其中e 为基本网页集图的边，a z t t h w t ( j ，f ) ，h u b w t ( i ，_ ，) 为链接的权威权值和中 心权值。 第二章网页排序综述 图2 3h i t s 算法的两种不良情况 考虑图2 3 b ，上下分别有膨+ i 中心网页和肘+ 1 个权威网页，前m 个中心 网页指向第一个权威网页，第肼+ 1 个中心网页指向肼+ 1 个权威网页。根据 h i t s 算法第一个权威网页具有最高的权威权值，这是我们所希望的。第肘+ 1 个 中心网页既指向第一个高权值的权威网页，也指向很多低权值的权威网页，所 以它的中心权值应该比前肘个中心网页的权值低，但实际根据h i t s ，它却具 有最高的中心权值。为此b o r o d i n 等人 2 4 】提出中心平均( h u b - a v e r a g e ) 算法，算 法中计算权威权值的操作与h i t s 相同，对计算中心权值的d ”操作按中心 网页出度进行归一