Google网页排序算法中PageRank值.docx
《Google网页排序算法中PageRank值.docx》由会员分享，可在线阅读，更多相关《Google网页排序算法中PageRank值.docx（59页珍藏版）》请在冰点文库上搜索。
Google网页排序算法中PageRank值
社会环境下网页重要性的研究
指导老师：
陈强
邓青云信息工程20060003014
中文摘要
近年来，随着internet的不断发展，Web已经成为人们的重要信息来源，为人们提供了丰富的信息资源。
与此同时，它所具有的海量数据、复杂性、极强的动态性和用户的多态性等特点也给We资源的发展发掘造成了相当的难度。
通过分析和研究作为一种相当成功的基于超链分析的算法GooglePageRank，可以有效地衡量网页重要度权值,然而进一步的研究也表明,这种纯粹依赖于超链分析的算法由于没有考虑到网页访问者对网页重要度权值的影响,所以在一定程度上会造成偏差。
因此,合理的将两者进行结合,充分利用访问者的知识水平和网页内容特征对PageRank算法进行改进，得出最终搜索引擎排序优化算法，可以极大的提高这种算法的有效性和正确性。
关键词：
超链分析，PageRank，算法，访问者，优化
ABSTRACT
Inrecentyears,alongwiththecontinuousdevelopmentoftheInternet,Webhasbecomeanimportantsourceofinformation,thepeopleforthepeopleprovidesabundantinformationresources.Meanwhile,ithasthemassdata,complexity,andstrongdynamicsandcharacteristicsoftheusertoshippolymorphismofthedevelopmentofresourcesofexcavationcausedconsiderabledifficulty.ThroughtheanalysisandresearchasafairlysuccessfulbasedontheanalysisofthealgorithmishyperlinkedPageRankGoogle,whichcaneffectivelymeasurewebimportanceweights,however,furtherstudieshavealsoshownthatthiskindofdinkumchainanalysisdependsnotconsideringthealgorithmduetowebpagevisitorstheinfluencedegreeofimportantvalue,sotosomeextent.Therefore,botharereasonable,fullyutilizetheknowledgelevelandvisitorstopagefeaturesPageRankalgorithmwasimproved,thesearchengineoptimizationalgorithm,cansortofimprovingthecorrectnessandvalidityofthisalgorithm.
Keywords:
hyperlinkanalysisalgorithm,thevisitor,PageRankoptimization
目录
1．Google搜索引擎简介5
1.1Google的软件文化理念5
1.2搜索引擎的分类5
1.3Google搜索引擎工作原理[3]6
2．传统GooglePageRank算法分析9
2.1传统GooglePageRank算法概述[4]9
2.2传统PageRank算法回顾10
2.2.1传统PageRank算法代数表达形式10
2.2.2传统PageRank算法向量表达形式12
2.3传统GooglePageRank的缺陷和改进方法13
3．GooglePageRank算法改进15
3.1由访问者知识水平及其投票的情况决定网页排名的PageRank算法15
3.1.1算法中PR值的含义15
3.1.2从投票角度分析算法的本质15
3.1.3算法改进的详细设计思路16
3.2计算每个访问者的PageRank值17
3.2.1计算访问者PR值的数学表达式17
3.2.2访问者PR值的循环收敛计算方法19
3.2.3访问者PR值算法的简单模型21
3.2.4VisualBasic编程验证算法收敛23
3.2.5matlab编程验证算法收敛29
3.3网页PR值的计算方法37
3.3.1计算网页PR值的理论基础37
3.3.2建立数学模型38
3.3.3VisualBasic编程验证算法的正确性39
3.3.4matlab编程验证算法的正确性42
4．改进算法的事实可行性44
5．将改进算法与GooglePageRank传统算法结合的最完美排序方法46
6．小结48
附录49
参考文献51
致谢52
1．Google搜索引擎简介
1.1Google的软件文化理念
根据《中国互联网络发展状况统计报告（2005/1）》用户在互联网上获取信息最常用的方法是通过搜索引擎:
占70.7%。
远远高于位于第二位的直接访问已知的网站:
占24.6%。
搜索引擎的后起之秀Google每天处理的搜索请求已达2亿次。
现在全球有75%的网上信息搜索是靠Google的技术完成，大大促进了人类的信息搜索的效率。
而作为品牌价值，仅Google这个名字的无形资产，竟出人意料地在如此短的时间，一下子超过了苹果、IMB、可口可乐，真正实现了跳跃性的发展。
Google主页面不以花哨取胜，而以功能表现为本。
它的先进的软件理念正是建立在软件功能模块上，研究其功能特点，我们发现Google技术上的先进，来自于文化理念上的先进，并敢于打破传统独树一帜[1]。
首先，Google用先进的PageRank技术理念，以平等、实用、公正为组织原则，优化整合全球Web网页资源。
在搜索方法上，Google更是化繁为简，为大多数网民利益考虑，做到软件使用大众化。
其次，在对待语言工具的问题上，不搞大国沙文主义，真正摈弃了语言上的贵贱之分，将多种语言平等地整合在同一界面，实现了以人为本的软件理念。
同时注重创新，注意吸纳新网站，以组成世界信息大家庭，并且充分尊重新网站的特殊要求和选择权利，再进行搜索引擎数据库的录入处理。
再次，Google的中文搜索引擎的完美设计，体现了设计者的国际市场合作精神，Google搜索引擎对中文的支持力度，使它成为目前是收集亚洲网站最多的搜索引擎，同时能够取他人之长，与他人联手，以团队合作精神推出新技术新功能。
1.2搜索引擎的分类
搜索引擎是指因特网上专门提供查询服务的一类网站,它以一定的策略在互联网中搜集、发现信息，对信息进行理解、提取、组织和处理,并为用户提供检索服务，从而起到信息导航的作用。
搜索引擎系统可以分为：
目录式搜索引擎、机器人搜索引擎和元搜索引擎。
目录式搜索引擎因为加入了人的智能，所以信息准确、导航质量高，缺点是需要人工介入、维护量大、信息量少、信息更新不及时。
机器人搜索引擎:
是指通过网络搜索软件（又称为网络蜘蛛[2],网络爬行机器人,网络搜索机器人）或网站登录等方式,以某种策略自动地在互联网中搜集和发现信息,经过加工处理后建库,从而能够对用户提出的各种查询作出响应,提供用户所需的信息。
该类搜索引擎的优点是信息量大、更新及时、毋需人工干预，缺点是返回信息过多，有很多无关信息，用户必须从结果中进行筛选。
这类搜索引擎的代表是：
AltaVista、NorthernLight、Excite、Infos2eek、Inktomi、FAST、Lycos、Google;国内代表为：
“天网”、“XX”等。
本文论述的Google搜索引擎就是机器人搜索引擎，通过网络蜘蛛（Crawler）搜集和发现网页排序所需要的信息。
目录式搜索引擎和机器人搜索引擎，各有优缺点，应用都很广泛。
机器人搜索引擎的自动化程度比目录式搜索引擎高。
网络信息量太大了，用计算机代替人去查找，可以节省大量的人力。
元搜索引擎：
这类搜索引擎没有自己的数据，而是将用户的查询请求同时向多个搜索引擎递交，将返回的结果进行重复排除、重新排序等处理后，作为自己的结果返回给用户。
服务方式为面向网页的全文检索。
这类搜索引擎的优点是返回结果的信息量更大、更全，缺点是不能够充分使用搜索引擎的功能，用户需要做更多的筛选。
这类搜索引擎的代表是WebCrawler、InfoMarket等.
1.3Google搜索引擎工作原理[3]
搜索引擎一般由网络爬行机器人crawler、知识库Repository、索引系统（包括索引器indexer，桶barrels,文件索引等）、排序器Sorter和搜索器Searcher5个部分组成。
GooglePageRank一般一年更新四次（由crawler程序的效率及搜索引擎的规模决定），所以刚上线的新网站不可能获得PR值。
你的网站很可能在相当长的时间里面看不到PR值的变化，特别是一些新的网站。
PR值暂时没有，这不是什么不好的事情，耐心等待就好了。
GooglePageRank每更新一次都是按照以下的步骤进行：
（1）Google使用高速的分布式爬行器（Crawler）系统中的漫游遍历器（Googlebot）定时地遍历网页，将遍历到的网页送到存储服务器（StoreServer）中。
（2）存储服务器使用zlib格式压缩软件将这些网页进行无损压缩处理后存入数据Repository中。
Repository获得了每个网页的完全Html代码后，对其压缩后的网页及URL进行分析，记录下网页长度、URL、URL长度和网页内容，并赋予每个网页一个文档号（docID）。
（3）索引器（Indexer）从Repository中读取数据，以后做以下四步工作：
（4）（a）将读取的数据解压缩后进行分析，它将网页中每个有意义的词进行统计后，转化为关键词（wordID）的若干索引项（Hits），生成索引项列表，该列表包括关键词、关键词的位置、关键词的大小和大小写状态等。
索引项列表被存入到数据桶（Barrels）中，并生成以文档号（docID）部分排序的顺排档索引。
索引项根据其重要程度分为两种：
当索引项中的关键词出现在URL、标题、锚文本（AnchorText）和标签中时，表示该索引项比较重要，称为特殊索引项（FancyHits）；其余情况则称为普通索引项（PlainHits）。
顺排档索引和Hit的存储结构如图1.1所示。
（b）索引器除了对网页中有意义的词进行分析外，还分析网页的所有超文本链接，将其AnchorText、URL指向等关键信息存入到Anchor文档库中。
（c）索引器生成一个索引词表（Lexicon），它包括两个部分：
关键词的列表和指针列表，用于倒排档文档相连接（如图1.1所示）。
（d）索引器还将分析过的网页编排成一个与Repository相连接的文档索引（DocumentIndex），并记录下网页的URL和标题，以便可以准确查找出在Repository中存储的原网页内容。
而且把没有分析的网页传给URLServer，以便在下一次工作流程中进行索引分析。
（5）URL分析器（URLResolver）读取Anchor文档中的信息，然后做⑥中的工作。
（6）（a）将其锚文本（AnchorText）所指向的URL转换成网页的docID；（b）将该docID与原网页的docID形成“链接对”，存入Link数据库中；（c）将AnchorText指向的网页的docID与顺排档特殊索引项AnchorHits相连接。
（7）数据库Link记录了网页的链接关系，用来计算网页的PageRank值。
（8）文档索引（DocumentIndex）把没有进行索引分析的网页传递给URLServer，URLServer则向Crawler提供待遍历的URL，这样，这些未被索引的网页在下一次工作流程中将被索引分析。
（9）排序器（Sorter）对数据桶（Barrels）的顺排档索引重新进行排序，生成以关键词（wordID）为索引的倒排档索引。
倒排档索引结构如图所示：
图1.1
（10）将生成的倒排档索引与先前由索引器产生的索引词表（Lexicon）相连接产生一个新的索引词表供搜索器（Searcher）使用。
搜索器的功能是由网页服务器实现的，根据新产生的索引词表结合上述的文档索引（DocumentIndex）和Link数据库计算的网页PageRank值来匹配检索。
在执行检索时，Google通常遵循以下步骤（以下所指的是单个检索词的情况）：
（1）将检索词转化成相应的wordID；
（2）利用Lexicon，检索出包含该wordID的网页的docID；
（3）根据与Lexicon相连的倒排档索引，分析各网页中的相关索引项的情况，计算各网页和检索词的匹配程度，必要时调用顺排档索引；
（4）根据各网页的匹配程度，结合根据Link产生的相应网页的PageRank情况，对检索结果进行排序；
（5）调用DocumentIndex中的docID及其相应的URL，将排序结果生成检索结果的最终列表，提供给检索用户。
这些过程都是离线进行的。
当用户在线提交一个查询时，先从反向索引库中查找含有查询关键词的网页，返回一系列相关的网页的docID，由docID在存储PageRank的库中找到它们对应的PageRank值，然后将所有结果进行排序输出给用户。
可以看出，整个过程中在线进行的只是查询，所有的计算都是离线进行的，因此搜索引擎能以较快的速度将结果返回给用户。
另外，查询过程没有考虑用户提交的关键词和访问者的自身情况。
基于链接的PageRank离线进行计算一次后，会在一段时间保持不变。
据资料称，Google的PageRank计算周期大概是三个月。
2．传统GooglePageRank算法分析
2.1传统GooglePageRank算法概述[4]
我要做的工作是将PageRank的算法改进，所以先简述GooglePageRank的情况方便下面的改进修改和对照。
超链分析技术主要是指利用网页间存在的各种超链指向,对网页之间的引用关系进行分析，依据网页链入数的多少计算该网页的重要度权值，一般认为,如果A网页有超链指向B网页，相当于A网页投了B网页一票，即A认可B网页的重要性。
深入理解超链分析算法，可以根据链接结构把整个网页文档集看作一个有向的拓扑图，其中每个网页都构成图中的一个结点，网页之间的链接就构成了结点间的有向边，按照这个思想，可以根据每个结点的出度和入度来评价网页的作用。
其中有代表性的算法主要是LarryPage等人设计的PageRank算法和Kleinberg创造的HITS算法。
其中PageRank算法在实际使用中的效果要好于HITS算法，这主要是由于以下原因:
a.PageRank算法可以一次性、脱机并且独立于查询地对网页进行预计算，以得到网页重要度的估计值，然后在具体的用户查询中，结合其他查询指标值再一齐对查询结果进行相关性排序，从而节省了系统查询时的运算开销；b.PageRank算法是利用整个网页集合进行计算的，不像HITS算法易受到局部连接陷阱的影响而产生“主题漂移”,所以现在这种技术广泛地应用在许多信息检索系统和网络搜索引擎中，Google搜索引擎的成功也表明了以超链分析为特征的网页相关度排序算法日益成熟。
但是PageRank算法由于只考虑到网页间的超链关系并仅仅以此进行网页重要度的分析，所以不可避免地会产生很多问题，其中，比较明显的问题在于它在计算每个网页具体的重要度权值的时候，根本没有考虑到任何网页本身内容特征对权值的影响，如PageRank算法完全忽略了网页具有的不同主题，不同的主题应该具有不同的重要度权值，进一步说，在用户查询的时候，网页的重要程度值的大小与查询所表达的主题关系很大，其实，在HITS算法[5]中恰恰考虑了这种因素，所以它更易于表达与特定查询主题的相关度排序，有效地在PageRank算法中考虑查询主题对网页权重值的影响是一个有效改进此算法的重要方法，再如，PageRank算法也没有考虑网页的创建时间,并不对新旧网页进行有效的区分,相反,按照PageRank的既有算法甚至会产生旧网页比新网页具有较高重要度权值的可能性。
这些都是GooglePageRank存在的缺点，也是本文对PageRank算法进行改进的原因。
2.2传统PageRank算法回顾
PageRank技术：
通过对由超过50,000万个变量和20亿个词汇组成的方程进行计算，PageRank能够对网页的重要性做出客观的评价。
PageRank并不计算直接链接的数量，而是将从网页A指向网页B的链接解释为由网页A对网页B所投的一票。
这样，PageRank会根据网页B所收到的投票数量来评估该页的重要性。
虽然PageRank认为网页的链入超链数可以反应该网页的重要程度,但是现实中人们在设计网页的各种超链时往往并不严格，有很多网页的超链纯粹是为了诸如网页导航、商业推荐等目的而制作的，显然这类网页对于它所指向网页的重要度贡献程度并不高，但是，由于算法的复杂性，PageRank没有过多考虑网页超链内容对网页重要度的影响,只是使用了两个相对简单的方法：
其一，如果一个网页的链出网页数太多，则它对每个链出网页重要度的认可能力相应降低；其二，如果一个网页由于本身链入网页数很低造成它的重要度降低，则它对它的链出网页重要度的影响也相应降低。
综上而言，一个网页的重要性决定着同时也依赖于其他网页的重要性。
PageRank绝对是个很科学的小创意。
说他科学，你会在我以后的文章中看到Google是如何将数学（具体来说多数是统计学）理论淋漓尽致地发挥在搜索技术之中。
说他“小”，因为这些理论对于搞数学的人来说实在太微不足道了，甚至稍微有些科学高数知识的人都能理解。
他所用到的统计学就是循环迭代计算收敛值的方法！
[6]
2.2.1传统PageRank算法代数表达形式
按照上面思路，Page给出了PageRank的简单定义[7]：
（2.1）
此处的u表示一个网页，R（u）表示网页u的PageRank值，B（u）表示链接到网页u的网页集合，即网页u的链入网页集合，N（v）表示从网页v向外的链接数量，即网页v的链出网页数，C为规范化因子，用于保证所有网页的PageRank总和为常量（如为1）。
这就是算法的形式化描述，也可以用矩阵来描述此算法，设A为一个方阵，行和列对应网页集的网页。
如果网页i有指向网页j的一个链接，则Aij=1/Ni，否则Aij=0。
设V是对应网页集的一个向量，有V=cAV，V为A的特征根为c的特征向量。
实际上只需要求出最大特征根的特征向量，就是网页集对应的最终PageRank值，这可以用迭代方法计算。
具体计算时，可以给每个网页一个初始的PageRank值，然后反复迭代运算，即：
R（i+1）（v）=
R（i）（u）/Nu（2.2）
此处的v代表所有的网页集合,每一个第i+1次的PageRank值都是基于上次的PageRank值重新计算的。
具体的迭代次数在实际运算中是有限的。
LawrencePage和SergeyBrin在个别场合描述了PageRank最初的算法。
这就是
PR（A）=（1-d）+d（PR（T1）/C（T1）+...+PR（Tn）/C（Tn））
式中：
PR（A）:
网页A页的PageRank值；
PR（Ti）:
链接到A页的网页Ti的PageRank值；
C（Ti）:
网页Ti的出站链接数量；
d:
阻尼系数，0上式最初算法只是表达了PageRank的基本计算原理，并不具有普遍性，因为没有迭代收敛的步骤。
所有PR（Ti）之和还要乘以一个阻尼系数d，它的值在0到1之间。
阻尼系数的使用，减少了其它页面对当前页面A的排序贡献。
一个页面通过随机冲浪到达的概率就是链入它的别的页面上的链接的被点击概率的和。
并且，阻尼系数d减低了这个概率。
阻尼系数d的引入，是因为用户不可能无限的点击链接，常常因无聊而随机跳入另一个页面。
PageRank的特性可以通过以下范例用插图表示。
图2.1
假设一个小网站由三个页面A、B、C组成，A连接到B和C，B连接到C，C连接到A。
虽然Page和Brin实际上将阻尼系数d设为0.85，但这里我们为了简便计算就将其设为0.5。
尽管阻尼系数d的精确值无疑是影响到PageRank值的，可是它并不影响PageRank计算的原理。
因此，我们得到以下计算PageRank值的方程：
PR（A）=0.5+0.5PR（C）
PR（B）=0.5+0.5（PR（A）/2）
PR（C）=0.5+0.5（PR（A）/2+PR（B））
这些方程很容易求解，以下得到每个页面的PageRank值：
PR（A）=14/13=1.07692308
PR（B）=10/13=0.76923077
PR（B）=15/13=1.15384615
很明显所有页面PageRank之和为3，等于网页的总数。
就像以上所提的，此结果对于这个简单的范例来说并不特殊。
对于这个只有三个页面的简单范例来说，通过方程组很容易求得PageRank值。
但实际上，互联网包含数以亿计的文档，是不可能解方程组的。
下面阐述迭代过程。
由于实际的互联网网页数量，Google搜索引擎使用了一个近似的、迭代的计算方法计算PageRank值。
就是说先给每个网页一个初始值，然后利用上面的公式，循环进行有限次运算得到近似的PageRank值。
我们再次使用“三页面”的范例来说明迭代计算，这里设每个页面的初始值为1。
迭代次数
PR（A）
PR（B）
PR（C）
0
1
1
1
1
1
0.75
1.125
2
1.0625
0.765625
1.1484375
3
1.07421875
0.76855469
1.15283203
4
1.07641602
0.76910400
1.15365601
5
1.07682800
0.76920700
1.15381050
6
1.07690525
0.76922631
1.15383947
7
1.07691973
0.76922993
1.15384490
8
1.07692245
0.76923061
1.15384592
9
1.07692296
0.76923074
1.15384611
10
1.07692305
0.76923076
1.15384615
11
1.07692307
0.76923077
1.15384615
12
1.07692308
0.76923077
1.15384615
重复几次后，我们的到一个
升级会员 