（计算机应用技术专业论文）distancerank与hits混合的网页排序算法研究.pdf

： 独创性声明 本人郑重声明：所提交的学位论文是本人在导师指导下独立进行研究工作所取得 的成果。据我所知，除了特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果。对本人的研究做出重要贡献的个人和集体，均已在文中作了 明确的说明。本声明的法律结果由本人承担。 学位论文作者签名：律午三牛日期：2 ：型丝么皿 学位论文使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定，即：东 北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和电子版，允许 论文被查阅和借阅。本人授权东北师范大学可以采用影印、缩印或其它复制手段保存、 汇编本学位论文。同意将本学位论文收录到中国优秀博硕士学位论文全文数据库 ( 中国学术期刊( 光盘版) 电子杂志社) 、中国学位论文全文数据库( 中国科学技 术信息研究所) 等数据库中，并以电子出版物形式出版发行和提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 日期： 学位论文作者毕业后去向： 工作单位： 通讯地址： 指导教师签名： 呼 电话： 邮编： 摘要 随着计算机应用的迅速发展，w e b 的规模呈现爆炸式增长。搜索引擎作为人们网上 冲浪必不可少的工具，得到了空前的发展。为了更好的完善搜索引擎的功能和性能，为 人们上网时提供更多的方便，也为了更好的实现其商业价值，越来越多的人开始投入到 搜索引擎的改进和提高上，作为搜索引擎的核心算法搜索排序算法更是变得炙手可热。 为了方便叙述，本文就将搜索排序统称为排序。 本文要讨论的就是网页的排序问题。现在的网页排序算法虽多，但各有利弊。考虑 到各种算法的长短，我们采用一种取长补短的方法将两种性质不同的方法进行结 合，以获取一种可以尽量扬长避短的新算法。h i t s 算法作为一种基于查询的排序算法， 正受到人们越来越多的重视；而d i s t a n c e r a n k 算法作为一种基于强化学习的离线全局排 序算法刚被提出不久，有着优异的性能和良好的发展潜力。基于上述考虑，本文将 d i s t a n c e r a n k 改进成一种基于查询的算法q d i s t a n c e r a n k ( q u e r y d e p e n d e n t d i s t a n c e r a n k ) ，并将这种算法与h i t s 算法进行结合，得到了另一种算法，我们称之为 q d r h i t s ( q d i s t a n c e r a n ka n dh i t sa l g o r i t h m ) 。 本文算法的采用j a v a 语言实现，在实验过程中借助经典p a g e r a n k 算法对算法性能 进行评估。实验结果表明，作为基于查询的排序算法，本文的两种方法在网页排序质量 方面要优于经典的h i t s 算法。 关键字：d i s t a n c e r a n k ：h i t s ；q d r h i t s ；q d i s t a n c e r a n k ；p a g e r a n k ；网页排序 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 fc o m p u t e ra p p l i c a t i o n s ，w e bs c a l es h o w i n ge x p l o s i v e g r o w t h s e a r c he n g i n ea si n d i s p e n s a b l et o o l f o rp e o p l et os u r ft h ew e b ，h a sb e e na l l u n p r e c e d e n t e dd e v e l o p m e n t i no r d e rt ob e t t e ri m p r o v et h es e a r c he n g i n ef u n c t i o n a l i t ya n d p e r f o r m a n c ef o rp e o p l et op r o v i d em o r ec o n v e n i e n ta c c e s s ，a sw e l la st ob e t t e ra c h i e v et h e i r c o m m e r c i a lv a l u e ，m o r ea n dm o r ep e o p l eb e g a nt op u ti n t oas e a r c he n g i n e t h es e a r c h i n g a n dr a n k i n ga l g o r i t h mw h i c hi st h ec o r ea l g o r i t h mo fs e a r c he n g i n ei sb e c o m i n gh o t t ob e c o n v e n i e n tt oa d d r e s s ，t h es e a r c h i n ga n dr a n k i n ga l g o r i t h mc a l lb ec a l l e dr a n k i n ga l g o r i t h m f o rs h o r t i nt h i sa r t i c l ew ew i l ld i s c u s sr a n k i n ga l g o r i t h m so fs e a r c he n g i n e a l t h o u g ht h e r ea r e m a n yr a n k i n ga l g o r i t h m s ，t h e yh a v em a n ya d v a n t a g e sa n dd i s a d v a n t a g e s t a k i n gi ti n t o a c c o u n tt h a tt h ea d v a n t a g e sa n dd i s a d v a n t a g e sa r ed i f f e r e n tf o rv a r i o u sa l g o r i t h m s ，w ep l a nt o j o i nt w oo ft h e mt o g e t h e ra n dm a k ei tan e wa l g o r i t h m t h en e wa l g o r i t h mw i l lh a v et w o k i n d so ft h ei n t e g r a t e dn a t u r eo ft h ed i f f e r e n tm e t h o d sa n dc a l lb ea sf a ra sp o s s i b l ea v o i d i n g w e a k n e s s e s h i t sa l g o r i t h m ，a saq u e r y d e p e n d e n tr a n k i n ga l g o r i t h m ，i sb e c o m i n gm o r ea n d m o r ep o p u l a r , a n dd i s t a n c e r a n ka l g o r i t h mb a s e do nr e i n f o r c e m e n tl e a r n i n ga sag l o b a l o f f - l i n er a n k i n ga l g o r i t h mh a sb e e ni n t r o d u c e di nt h en e a r p a s t ，w h i c hh a se x c e l l e n t p e r f o r m a n c ea n dv e r yg o o dp o t e n t i a lo fd e v e l o p m e n t b a s e do nt h ec o n s i d e r a t i o na b o v ew e i m p r o v e dd i s t a n c e r a n k t ob eaq u e r y - d e p e n d e n t r a n k i n ga l g o r i t h mw h i c hi sc a l l e d q d i s t a n c e r a n k ，a n dw em i xt h i sr a n k i n ga l g o r i t h mw i t hh i t sa n do b t a i n e dan e wa l g o r i t h m ， w ec a l li tq d r h i t s ( q d i s t a n c e r a n ka n dh i t sa l g o r i t h m ) t h i sa l g o r i t h mi si m p l e m e n t e di nj a v al a n g u a g e ，a n dw et u mt ot h ec l a s s i c a lp a g e r a n k a l g o r i t h mt oe v a l u a t et h ep e r f o r m a n c eo ft h et w oa l g o r i t h m s e x p e r i m e n t a lr e s u l t ss h o wt h a t ， t h er a n k i n g q u a l i t yo ft h et w oa l g o r i t h m sa r eb e t t e rt h a nt h ec l a s s i c a lh i t sa l g o r i t h m k e yw o r d s ：d i s t a n c e r a n k ；h i t s ；q d r h i t s ；q d i s t a n c e r a n k ；p a g e r a n k ；r a n k i n gp a g e s n 参考文献2 1 致谢2 3 在学期间公开发表论文及著作情况2 4 i v 目录 摘要i a b s t r a c t i i 目录j i i i 引言1 第一章绪论2 1 1 网页排序算法的研究背景及意义2 1 2 国内外研究现状2 1 2 1 国外研究现状3 1 2 2 国内研究现状3 1 3 本文研究工作4 1 4 全文组织结构4 第二章相关算法介绍5 2 1p a g e r a n k 算法5 2 2d i s t a n c e r a n k 算法5 2 2 1 算法介绍6 2 2 2 算法计算7 2 3h i t s 算法8 2 3 1 构建关于给定查询提问的w e b 子图9 2 3 2h i t s 算法计算过程9 2 4 各种算法评价与分析1 0 2 5 本章小结1 0 第三章d i s t a n c e r a n k 与h i t s 混合的网页排序算法1 l 3 1 问题描述1 1 3 2 算法思路1 1 3 2 1 运行h r r s 算法1 1 3 2 2d i s t a n c e r a n k 与q d i s t a n c e r a n k 1 2 3 2 3q d i s t a n c e r a n k 向量标准化1 3 3 2 4q d r h i t s 1 4 3 3 算法实现与分析1 4 3 3 1 数据集1 4 3 3 2 确定重要网页集1 5 3 3 3 确定参数叩1 5 3 3 4 实验结果与对比分析1 7 3 4 本章小结1 9 第四章结束语2 0 m 东北师范大学硕士学位论文 引言 网页排序，顾名思义，就是对固定的网页集合按照特定的标准进行有序排列，使得 排在前面的网页有着更好的特性，能够更好地满足人们的需要。 随着因特网的飞速发展，它所提供的文档( 网页) 也以惊人的速度在增长。有关的 调查统计表明，w e b 上的网页平均每不到一年的时间就会增长一倍。统计表明，在2 0 0 5 年的时候，w e b 上的网页数就已经超过了1 1 5 亿【l j 。人们开始更多地依赖网络，在互联网 上发布和获取的信息也越来越多，这使得w e b 目前已经变成了信息制造、信息发布、信 息加工和处理的主要平台。互联络发展的已经超出了一般人所能想象的，它几乎包容了 人类历史上所累积下来的全部知识，而且还在以网页数每天超过1 0 0 万张的速度迅速扩 充。要从如此庞大的信息库中提取出有用的信息就不得不依赖于搜索引擎的功能【2 引，而 网页的排序算法则是搜索引擎核心功能要解决的一个关键问题。 最初的网页排序技术很多都是基于文档的内容，这主要是来源于与经典的信息检索 技术和数据库技术但是，互联网中许多特有的问题，比如说非结构化文档数规模庞大、 网页的质量良莠不齐、文档中夹杂着的大量多媒体信息，以至用户查询表示的含糊以及 不规范的等等，都使得基于信息检索技术和数据库技术的网页排序算法很难在w e b 中有 效地运用。 后来人们发现了互联网的超链接结构i 射，其中包含了传统数据环境所没有丰富信息。 网页间的超链接一方面引导用户完成浏览网页和相互跳转的过程，另一方面也体现了网 页制作者对网页内容的一种判断，可以这样认为，如果网页a 存在一条指向网页b 的超链 接，那么制作网页a 的人认为网页b 包含了有价值的信息。因此，如何充分利用互联网的 超链接拓扑结构，将对互联网技术的应用和研究产生深远的影响。 东北师范大学硕士学位论文 第一章绪论 1 1 网页排序算法的研究背景及意义 w c b 出现于1 9 8 9 年3 月，是由欧洲粒子物理研究所( c e r n ，e u r o p e a no r g a n i z a t i o n f o r n u c l e a r r e s e a r c h ) 的科学家t i m b e m e r s l e e 发明的。在随后的二十年里，w e b 取得 了迅猛的发展，人们对网络的应用日益普及，这使得w e b 上的网页数迅速增长。为了 更好地运用网络，帮助人们高效快捷地找到所需要的网络资源，搜索引擎应运而生，并 取得了迅猛的发展。人们无论在工作、学习还是生活当中，运用搜索引擎找寻网络资源， 搜索引擎有着不可替代的作用【5 】o 然而，w 曲的发展速度远远超出了人们的预料。它有 三个显著地特点：一、数据规模庞大。据统计，早在2 0 0 5 年的时候，全世界的网页数 已经突破了1 1 5 亿，而且现在还在以无法预知的速度增长。网页的庞大规模涵盖了人们 生活的各个方面而且日益丰富。二、更新代谢速度快。目前，新网页在以每周8 的速 度被制造出来【6 1 ，并充斥到w e b 当中去，同时也有一部分网页因为内容更新的需要或者 网站改造等原因消失在网络当中。如果搜索引擎不采取任何应对措施，那么一年后就只 有2 0 的网页可以被检索的n 1 7 , 8 。三、网页质量的良莠不齐。由于网页制作者的水平 参差不齐，网页内容的千差万别，以及各种商业利益的驱使，使得网页的质量存在着巨 大的差异【9 1 。这就需要搜索引擎能够应对庞大的数据量和快速的更新速度，并把质量最 好的网页第一时间呈现给用户。这对搜索引擎，尤其是其核心算法一网页排序算法来 说，是一个严峻的考验。 目前，p a g e r a n k 和h i t s 等算法作为搜索引擎的核心算法被不断改进并成功应用到 搜索引擎当中。像大家所熟知的g o o g l e 搜索引擎采用的核心算法就是p a g e r a n k 1 0 , 1 1 】。 虽然如此，对已有算法的改进和新算法的研究却也是迫在眉睫。一方面网页数据量的加 大和网页更新速度的加快，使得已有算法越来越显得力不从心。在这种情况下，无论对 已有算法的改进，还是对新算法的研发，都是势在必行；另一方面，我国在搜索排序算 法方面的研究起步较晚，无论从经济利益还是国家安全的角度，我们都应该在这方面投 入更多的力量1 1 2 】。 1 2国内外研究现状 目前，对于排序算法的研究已经成为一个热门，国外在这方面已经做得非常得成熟， 并出现了像g o o g l e 这种世界著名的搜索引掣1 3 】。国内的研究还处于发展阶段，到目前 为止我们还没有提出属于自己的核心算法，所做工作大多处于对现有算法的研究和改进 上，要做的东西还有很多。下面就分两个方面对国内外的研究现状做以介绍： 2 东北师范大学硕士学位论文 1 2 1 国外研究现状 网页之间的链接和链接文本携带着重要的信剧1 4 , 1 5 】，于是在1 9 9 8 年由斯坦福大学的 s e r g e yb r i n 和l a w r e n c ep a g e 提出了基于链接分析的一个新算法p a g e r a n k 2 1 ，开启了网 络链接分析研究的热潮。p a g e r a n k 算法是基于在随机冲浪模型设计的，具体来说，假设 冲浪者跟随链接访问了若干步之后重新转向一个随机的网页并跟随链接浏览，那么一个 网页的重要程度值就应该由这个随机网页被随机冲浪模型所访问的概率所决定。1 9 9 8 年 底，美国康奈尔大学的j o nk l e i n b e r g 博士提出了h i t s ( h y p e r t e x t i n d u c e dt o p i cs e a r c h ) 算法【1 6 1 。目前，它为i b m 公司阿尔马登研究中心( i b ma l m a d e nr e s e a r c hc e n t e r ) 的研究 项目之一。随后在2 0 0 0 年，l e m p e l 和m o r a n 提出t s a l s a 算法旧，该算法是基于m a r k o v 链 的。同年，由c o h n 和c h a n g 提出了一种基于概率模型的p h i t s 算法【1 8 l ，该算法是对h i t s 算法的一种改进。2 0 0 1 年，a l l a nb o r o d i n 等人则给出了一些k l e i n b e r g 算法的修正算 法：h u b a v e r a g i n g k l e i n b e r g 、t h r e s h o l d k l e i n b e r g 和b r e a d t h f i r s t s e a r c h 算法， 并提出了一种基于贝叶斯概率模型的网页排序算法【1 9 】。而后，大量的研究被投入到 p a g e r a n k 算法的研究与改进方面，主要包括对p a g e r a n k 算法的收敛效率、计算速度的研 究和对“主题漂移 现象的改进。在1 9 9 9 年，斯坦福大学计算机科学系t a h e rh a v e l i w a l a 就提出了一种利用矩阵迭代来实现p a g e r a n k 算法计算的思想，使得p a g e r a n k 的计算和收 敛速度得到了极大的提耐删。在2 0 0 2 年，他又提出了一种主题敏感( t o p i c s e n s i t i v e ) 的 p a g e r a n k 2 1 ，该算法可以有效地避免一些明显的主题漂移现象，提供高质量的推荐结果 集。其后也有许多关= j = p a g e r a n k 算法的改进，包括考虑锚文本、网页内容等的加权方式 的改进算法。直至1 j 2 0 0 7 年，a l im o h a m m a dz a r e hb i d o k i ，n a s s e ry a z d a n i 等人将对数距离 这一概念引入到网页链接当中，并将其用于表示网页间的链接权值【6 】。经过这样的表示 后，任何一个网页到另一个网页的距离就是其通过最短路径到达另一个网页的距离。通 过网页间的距离来衡量网页的重要程度，并将强化学习算法用于计算网页间距离，这就 是d i s t a n c e r a n k 算法。实验证明，d i s t a n c e r a n k 算法在网页爬取、网页排序以及克服“础c h g e tr i c h e r 问题等方面都有着很好的效果。目前，该算法还在实验和进一步的完善中。 1 2 2 国内研究现状 国内目前对搜索引擎排序算法的介绍和研究较少，从已有的文献来看，多集中于对 更具影响力的p a g e r a n k 算法的介绍、分析和改进方面的研究。由于网页采用的是半结构 化的h t m l 语言，所以其中包含了丰富的结构信息。2 0 0 3 年，上海交通大学的宋聚博士【捌 认为，在抽取网页的主题内容时，网页的h t m l 语言标记h i 、 、 以 及 等标记之内的关键字在计算时应该赋予较大的权重系数，他给出权重系数的 定义，并以此改进了算法。北京大学计算机系也提出了利用h t t p 协议，记录每个页面最 近一次的修改时间。他们将页面修改时间作为运行分析算法时候的控制参数，并且将较 3 东北师范大学硕士学位论文 高的权值赋予新修改的页面，而将较低权值给予老页面。在2 0 0 4 年的时候，上海交通大 学的张岭博士提出了一个加速评估算法p j ，这种算法可以使那些陈旧页面的评估值加速 下滑，而网络上有价值的内容则能够以更快的速度传播。该算法解决t p a g e r a n k 偏重旧 网页的问题。2 0 0 4 年，清华大学的余锦、史树明等对分布式网页排序算法进行了研究， 并提出了相应的传输模式【2 4 1 。2 0 0 7 年4 月，浙江大学的琚洁慧解决了中文搜索引擎中 p a g e r a n k 算法的实现问题【2 5 1 。同年，由大连理工大学的刘菁菁、林鸿飞、赵晶等人对 p a g e r a n k 算法进行改进，提出了基于p a g e r a n k 和锚文本的网页排序算法【2 6 1 。 1 3 本文研究工作 网页排序算法作为搜索引擎的核心算法之一，对它的研究有着重要的意义。同时搜 索引擎在下载网页的时候为了能够更好地获取高质量的网页，在爬虫中也融入了排序算 法【6 , 2 7 。所以对排序算法的研究有利于搜索引擎整体性能的提升。 本文首先将d i s t a n c e r a n k 算法改进成为一种基于查询的算法q d i s t a n c e r a n k ，然后 从取长补短的角度考虑【2 8 1 ，将q d i s t a n c e r a n k 算法与h i t s 算法所得的计算结果进行整合， 并赋予一定的参数，使得所得的新的排序向量可以兼具两者的长处，取得更好的排序效 果。之后我们会通过实验详细介绍算法的衡量标准重要网页集获取以及参数的确定 过程，在最后我们将进行实验并对实验结果进行分析和评估。 1 4 全文组织结构 本文主体共分为四个部分，内容安排如下： 第一章绪论，概述了本文的研究背景及意义、国内外研究现状、本文研究工作以 及全文的组织结构等。 第二章相关算法介绍，详细介绍了本文所要用到的两个算法d i s t a n c e r a n k 和h i t s ， 并对两个算法的特性进行了评价分析；简单介绍了p a g e r a n k 算法，为实验部分做准备。 第三章d i s t a n c e r a n k 与h i t s 混合的网页排序算法研究，这一章共分为四节：第一 节进行问题描述；第二节详细介绍算法的基本思想、算法公式以及参数设置。第三节首 先介绍了参数确定以及算法评估的衡量指标重要网页集确定，然后通过实验分析确 定了算法参数，最后通过与h i t s 算法进行对比实验，并对实验结果进行评价很分析。 第四节进行了简单的总结。 第四章结束语，总结全文，归纳工作要点，对本文算法所存在的不足之处给出建 议和展望。 4 东北师范大学硕士学位论文 第二章相关算法介绍 作为搜索引擎的经典核心算法，p a g e r a n k 在业内一直处于主要地位。目前绝大多数 的研究都是对p a g e r a n k 算法的研究和改进，并且取得了很好的应用效果。h i t s 算法近 年来也不断得到人们的关注，并且已经开始应用到搜索引擎当中。然而，由a 1 im o h a m m a d z a r e hb i d o k i 等人在2 0 0 7 年提出的d i s t a n c e r a n k 算法却还未引起人们的普遍关注。介 于以上原因以及本文需要，我们将对d i s t a n c e r a n k 以及h i t s 算法做详细介绍，而对 p a g e r a n k 算法只做简单介绍。 2 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 最早提出来的。g o o g l e 搜索 引擎采用了p a g e r a n k 算法【3 】，它通过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 值越大的网页就越靠前。 p a g e r a n k 算法的基本思想是：如果某网页a 存在一条指向网页b 的链接，那么就 认为网页a 认为网页b 比较重要，它会把自己的一部分重要性( p a g e r a n k 值) 分给b 。 而a 到底会分多少p a g e r a n k 值给b ，则是由a 自身的重要性p r ( a ) 和它指向其他页面 的链接数o ( 砷所决定的。因而，网页a 分给网页b 的p a g e r a n k 值可以表示成 p r ( a ) o ( a ) 。那么网页b 的p a g e r a n k 值就可以计算成所有指向它的网页所分给它的 p a g e r a n k 值之和。网页b 的p a g e r a n k 值p r ( b ) 可以表示成下面的计算公式： 袱陋) 一p r ) d “) + 咫0 ：) o ( a ：) + + p r ( a 。) o ( a 。)( 2 1 ) 其中4 、彳：彳。为包含指向b 的链接的页面。 由于w e b 上存在一些没有输入链接或输出链接的页面，我们无法计算出它们的 p a g e r a n k 值，即所谓的链接下沉( i j l l l 【s i l l l 【) 问题。为避免这个问题，p a g e 等人为其添加 一个系数口，于是公式( 2 1 ) 就表示成下面的形式： p r ( b ) - o t 枣l 碾0 。) o ( a 。) + + p r ( a 。) o ( a 。) + ( 1 一口) ( 2 2 ) 在g o o g l e q 丁，口的取值为0 8 5 1 2 1 。这样整个网页集合内的页面经过多次迭代计算直到收 敛，就可以求得页面i 拘p a g e r a n k 值。 2 2d i s t a n c e r a n k 算法 d i s t a n c e r a n k 是由德黑兰大学的a l im o h a m m a dz a r e hb i d o k i 和n a s s e ry a z d a n i 等 5 东北师范大学硕士学位论文 人提出来的，是一种基于强化学习的排序算法。它将网页的重要性理解为网页间的距离 长短，任何一个网页，只要它到其它所有网页的距离之和的平均值( 即平均距离) 越小， 那么这个网页就越重要，它的排名就越靠前【6 】。 为了便于对算法的理解，先将w r e b 图进行一下表示。将整个w 曲图表示成o ( v ，e ) ， 其中y 表示整个w e b 中网页的集合，那么网页集中的网页数就可以用叫来表示。e 表示 w e b 中的链接，有向边( f ，j ) e 表示i 指向j 。其中网页f 的出度( 从f 链出的网页数量) 用o ( ) 表示，网页j 的入度( 链向网页j 的网页数量) 用b ( j ) 表示。 2 2 1 算法介绍 图2 1 一部分w e b 图 d i s t a n c e r a n k 用距离来衡量网页的重要性，那么首先介绍一f 距离的定义： 定义1 、如果网页对旨向网页j ，那么f 和_ 之间的权重为l o g o ( ) ，这里d ( f ) 是网页f 的出度。 定义2 、网页i 和j 之间的距离定义为从i 到j 的最短路径的权重之和。我们称之为 对数距离，并且用d 。，表示。 为了便于理解，我们看一下图2 1 。图中p 、，和f 所发出的链接的权重分别为l o g ( 2 ) 、 l o g ( 3 ) 乘 l o g ( 4 ) 。现在以p 到q 的距离来看，p 到q 有两条路径p 呻r q 和p _ 卜留。 前者的权重和为l o g ( 2 ) + l o g ( 3 ) ，后者的权重和为l o g ( 2 ) + l o g ( 4 ) 。所以在此图中 p - ，一q 为最短路径，p 和g 间的距离为l o g ( 2 ) + l o g ( 3 ) 。 定义3 、如果略表示网页i 和网页j 间的距离，那么网页j 的平均距离( a v e r a g e 东北师范大学硕士学位论文 d i s t a n c e ) dj 就可以用下面的式子来表示： 铲毕 ( 2 3 ) o y 、 在这种定义方法中，定义了平均距离，d i s t a n c e r a n k 算法就是将它作为衡量网页重 要性的标准。在这种方法中，网页间的链接的权重被表示成l o g d g ) 。如果网页f 和j 之 间没有路径，那么d 西将被赋给一个很大的值( 如l o g ( n ) ) 。为了便于称呼，下面就把平均 距离称之，为距离。 2 2 2 算法计算 在d i s t a n c e r a n l 【算法中，距离的计算复杂度为d 0 y 卜i e i ) ，这对于现实当中拥有超过 1 1 5 亿网页的w e b 来说，根本是无法实现的。为了实现对平均距离的计算，只有依赖于 它的后向链接。举例来说，若网页j 只有一条后向链接，它来自网页i ，那么要计算网 页j 的距离d ，通过前面的定义1 、2 和3 ，就可以得到下面的关系式： d ，- d j + d f = d j + l o g ( d g ) ) ( 2 4 ) 现在进一步来说，用d ( f ) 表示网页f 的出度，用b ( _ ) 表示指向网页j 的网页集。那么 网页j 的距离矗，可以表示成 d ，2 唧n ( d ；+ l o g ( d o ) ) ) ，f b ( j ) ( 2 5 ) 于是在图2 1 中，网页g 的距离d 。的具体计算过程可以这样表示： d qmm i n e d t + l 0 9 4 。dr + l 0 9 3 f f im i n e dp + l 0 9 2 + l 0 9 4 。dp + l 0 9 2 + l 0 9 3 、 。0 p + l 0 9 2 + 1 。9 3 ) 考虑到( 2 5 ) 式，并引入强化学习算法【2 9 】，就可以得到下面的距离计算公式： d + 。一( 1 一口) 宰d 五+ 口幸n 呼n ( y 掌d + l o g ( d o ) ) ) ，f 曰( ，) ，0 口s1 , os ys 1 ( 2 6 ) 这里a 是学习率，l o g o ( f ) 是从网页f 到网页j 所受到的瞬时惩罚( p u n i s h m e n t ) 。d 和吒是在时间f 时网页和f 的距离，而d 。是在时间f + 1 时网页j 的距离。换句话说， 网页f 在时间t + 1 的距离依赖于它在时间t 的距离、它的后向结点i 在时间t 的距离以及 7 东北师范大学硕士学位论文 从i 到j 所受到的瞬时惩罚。阻尼系数) ，用来调整指向j 的路径中的各节点的距离对| 的 距离的影响。假设有s t 呻u 呻v 这样一条路径，那么s 的距离对y 的距离影响将会受 到) ，3 这样一个因素限制，在这里) ，通常取值为0 9 1 3 0 l 。 这里的口如果能够很好地选取，可以极大的提高收敛的速度。以下是a l i 等人给出 的口的选取方案： 口= e 一声町 c 7 ) 卢是一个静态值，a l i 等人在实验中将其取值为0 1 。在算法开始的时候，所有网页的距 离都不知道，所以口取值为1 ，然后随着迭代次数的递增口取值逐渐减小。 该算法很好地模拟了一个用户的上网浏览过程。直观地，当一个用户随机的浏览一 个网页，他对w e b 上的内容一无所知。然而随着不断地浏览网页，他不再随意打开一 个网页，而是基于他之前的经验和当前网页的内容。随着时间的推移，他积累了越来越 多的知识，也就能够更快地找到他想要的网页。d i s t a n c e r a n k 算法就很好地模拟了这一 过程。开始的时候系统知道的很少，学习率口设为1 ，它更多依赖于当前所看到的。随 着时间推移，它学会了一些知识，它开始更多地依赖于它所积累的知识，口开始下降。 从式( 2 6 ) 可以看出，d i s t a n c e r a n k 算法的计算公式和p a g e r a n k 非常相似，它也需要 通过一定的迭代最终达到收敛状态。通过引入强化学习算法，d i s t a n c e r a n k 的计算复杂 度表示成d b 书吲) ，而p l v i ，这极大地降低了计算复杂度。通过舢i 等人的实验，对 于五百万网页的数据集大约只需要5 次迭代就可以得到满意的结果。 2 3h i t s 算法 k l e i n b e r g 认为网页本身具备双重特性：一个是权威性( a u t h o r i t y ) ) 一个是中心 性( h u b ) 。网页的权威性依赖于网站的内容，而中心性则是依赖于它所指向的网页的权 威性。 为便于理解，依旧用图来表示网页间的链接关系。假设存在超链接页面的集合y ， 那么它的有向图可以表示为g ；缈，e ) ，这里f y 表示页面集合y 中的一个网页，有向 边0 ，q ) e e 表示网页集y 中的网页p 存在一条指向网页q 的超链接，节点p 的出度 ( o u t d e g r e e ) 指节点p 有超链接指向的其他网页的数量，而节点p 的入度( i n d e g r e e ) 则指的存在指向p 的链接的网页的数量。现在我们给定一个查询仃，然后需要通过算法 来计算该查询的权威页。首先是要确定运行h i t s 算法的w e b 子集s 。 理想的作用集合s 。应该具有以下特点：1 、s 。相对较小；2 、s 。中相关网页的内容 r 东北师范大学硕士学位论文 丰富；3 、s 口中包含绝大多数最有价值的权威网页1 1 6 1 。 2 3 1 构建关于给定查询提问的w e b 子图 具体做法如下： a 用基于文本的搜索引擎如a l t a v i s t a 等来得到盯的查询结果集【3 ，取排名最高的 前t ( t 值通常取2 0 0 ) 位的结果集，称之为根集( r o o ts e t ) ，用尺。来表示。在k l e i n b e r g 看来，尺。满足前两个特点，但远不能满足第三个特点，因此需要对进行扩充。 b 扩充r 。有两种扩充方式：一是将所有指向尺。中页或r 。中页所指向的页面都扩 充进去，这种扩充方式在数量上没有限制；二是将指向r 。中页的页面取其中任意d ( d 通常的取值为5 0 ，这里当d 大于5 0 时任选5 0 个，当d 小于5 0 取其所有页面) 个并且将r 。 中页所指向的所有页面扩充到原来的心中形成基本集( b a s es e t ) ，用s 。来表示。实验 表明，这样的集合s 。能够满足理想的作用集合所具有的三个特点。 c 去除内部链接。k l e i n b e r g 将网页间的链接分为两种：一种是指有链接关系的两 个页面属于不同的域名，他把这种链接称为横向链接；还有一种情况是存在链接关系的 两个页面处于相同的域名之下，这样的链接称为纵向链接( 或内部链接) 3 2 1 。k l e i n b e r g 认为纵向链接主要用于网站内部的导航，而不具备传递网页间的a u t h o r i t y 值的作用， 因此他将这种链接从基本集s 。中删去，形成g 。 2 3 2h i t s 算法计算过程 在k l e i n b e r g 的算法中，权威网页和中心网页之间是一种相互增强的关系。如果一 个h u b 页指向许多好的a u t h o r i t i e s 页，那么它的h u b 值就大，同样，一个a u t h o r i t y 页被许多好的h u b s 页指向，那么它的a u t h o r i t y 值也大。这种关系就可以表示成网页 传递的两个基本过程，k l e i n b e r g 称之为，操作和d 操作，这里，操作为h u b 到a u t h o r i t y 的传递，而d 操作则为a u t h o r i t y 到h u b 的传递。对于某一主题查询仃的作用集合g 。中 的任何页面p ，用彳0 ) 表示页面p 的权威权重，用何0 ) 表示页面p 的中心权重，这种 关系可以用下面的式子来表示： 彳0 ) - 粕，p 廖日( g ) ， o 东北9 币范大学硕士学位论文 日0 ) - 确，p 目爿( q ) 。 ( 2 8 ) 以上的式子可以通过固定的迭代次数达到收敛。在每一次迭代结束时，还需要对 彳0 ) 和h ) 进行下面的规范化计算： 峨0 0 ) ) 2 = 1 ， 飚0 ) ) 2 = 1 。 ( 2 9 ) 可以预先设定固定的迭代次数k ，经实验证明，经过有限次的迭代，算法会收敛， 通常情泖下取k = 2 5 就可以获得很好的效果【1 6 1 。 2 4 各种算法评价与分析 p a g e r a n k 、d i s t a n c e r a n k 和h i t s 都是基于网页链接结构的网页排序算法，而且都 是利用了特征向量作为理论基础和收敛依据。由于p a g e r a n k 与d i s t a n c e r a n k 在算法性 能特征方面有着很高的相似性，而且也不作为本文研究的重点，所以接下来我们就 d i s t a n c e r a n k 与h i t s 两种算法的特征进行评价与分析。 d i s t a n c e r a n k 算法是对整个w e b 的整体分析，因此它的排序结果更具有客观性和全 局性，它独立于用户查询( q u e r y i n d e p e n d e n t ) ，因此可以离线计算并获得排序结果，一 旦用户发来请求可以直接做出回应而不需要在线计算；它的不足在于没有考虑页面的内 容，因此不能作为用户查询的结果直接反馈回去。而h i t s 算法是依赖于用户查询 ( q u e r y d e p e n d e n t ) 的，它的计算结果可以作为反馈给用户的结果；但它的作用范围是 通过用户查询所获取的基本集，所以它的排序结果具有局部性，而且基本集的获得必须 要用户在线查询所产生的，并且需要在线计算，然后才能将计算结果反馈给用户，实时 性差f 2 8 1 。 通过以上分析，我们对两种算法的各自优缺点有了比较深刻的认识，这也为将算法 进行改进和结合可以得到更好的排序算法提供了一定的理论依据。 2 5 本章小结 在这一章中我们从算法原理和算法的计算方面详细介绍了d i s t a n c e r a n k 和h i t s 算 法，并对两种算法的优势和不足进行了阐述，从而为算法改进和结合的价值和意义提供 了依据。在下一章里我们将详细介绍这两种结合的具体过程。 1 0 东北师范大学硕士学位论文 第三章d i s t a n c e r a n k 与h i t s 混合的网页排序算法 在前面的章节里，我们对d i s t a n c e r a n k 算法和h i t s 算法进行了详细的介绍，并对 两种算法的优缺点进行了评价分析。在这一章里，我们将详细介绍d i s t a n c e r a n k 算法的 改进以及与h i t s 算法混合的理论依据和实现过程，并通过实验来证明算法的有效性， 对算法的优势与不足给出分析和评价。 3