欢迎光临本站!

Page Rank

来源:技术探讨    更新时间:2019-12-12 09:34:47    编辑:老王    浏览:520

  网页搜索的本质是网页信息的聚合,把本来很难聚合在一起的网页通过共同包含的关键词聚合起来。网页被聚合后就自然会产生排序问题。归纳起来就是既不能不排,也不能乱排,需要通过科学有效的方法将“好”的搜索结果按照“好”的程度依次排列。当然“好”是一个相当主观的且难以量化的概念,因此如何评价这个“好”成为搜索质量的关键。在搜索引擎的发展史中Google发明的 PageRank无疑是浓墨重彩的一笔。

  Page Rank的来由


  Google公司的两位创始人L.Page及S.Brin在1998年提出了 Page Rank的概念[Page,etal.,1998]。在他们提出这个概念时,一方面,万维网的发展正处于信息大爆炸的时期。当时估计大约有1亿5千万网页,而且不到一年的时间网页的数目就会翻倍;另一方面,网页质量参差不齐,例如文献[Page,etal.,1998]中提到的网页信息“从Joe在哪里吃午饭到信息检索的期刊”无所不包,可以说实际有意义的、有价值的,以及经常被用户检索的网页规模井没有想像中的那么大,一个基本的方法是通过为网页排名使得重要性高且有价值的网页能够被优先检索。 Page Rank(网页排名)就是在这样的应用背景下诞生的。

  PageRank的基本想法


  人们在万维网上冲浪的过程中常常从一个起始网页开始例如新闻门户网站),之后被那些带有链接文字(锚文本)所描述的网页吸引,从而点击并打开另一个网页。并依次往复,直到对冲浪感觉厌倦,而正是由于网页和网页通过链接关系构成的这个网络使得网上冲浪成为可能。然而直到 Google提出了 PageRank模型,这种网页间彼此链接关系的价值才被挖掘出来,这种挖掘过程也称为"链接分析"( link analyze)。简单地说,如果网页A链接到B,那么表示网页A的编写者(网页工程师或者其他网页创造者)对网页B的一种认可。或者说网页A为网页B投了一票,网页B的重要性被网页A认可。

  直觉上说,如下3点可以认为是网页重要性的一种评价。

  (1)认可度越高的网页越重要,即反向链接( backlink)越多的网页越重要。

  (2)反向链接的源网页质量越高,被这些高质量网页的链接指向的网页越重要。

  (3)链接数越少的网页越重要。

  举个例子,假定在一次比赛中一个网球选手A被另一个网球选手B击败。定义一个A指向B的链接表示这种胜负关系。即A→B,表示A输给B,或者说A认可了B的厉害。那么很显然,对照上面得出下面结论。

  (1)如果B的反向链接越多,即认可B厉害的人越多,因此B的排名越高。

  (2)如果输绐B的选手的排名越高,即认可B厉害的人也是厉害的人,那么B的排名越高。

  (3)如果B输给的选手越少,即B认可厉害的人越少,那么B的排名越高。

  综上所述,赢的次数多、赢得对手质量高且输的少的选手的排名高是很自然的, PageRank的算法的基本思想也来自于此。

  在描述下载系统时曾提到过“随机冲浪”模型[ Bernardo AHuberman,etal,1998],它是 PageRank的理论基础,该模型描述网民访问网页的如下行为。

  1)用户随机选择一个网页作为上网的起始网页。

  (2)看完这个网页后从该网页内所含的超链接随机选择个页面继续浏览。

  (3)沿着超链接重复浏览,直到对某个主题感到厌倦而重新随机选择另一个网页浏览。如此反复,直到结束。

  PageRank的计算公式


  图4-17为文献[Page,etal.1998]的塬图。图中我们看到一个直观并简单的计算方法。以最左上角的网页为例,这个网页被3个箭头指向,假定共计得到了100分。然后通过两个链接(小横线表示网页内部的链接,方块表示一个网页)平均将这100分均分给了它所指向的两个网页。平均的意义在于假定用户是随机冲浪的,也就是点击第1个链接和第2个链接的可能性相等。这种由于指向关系而得到一定的分数,最后通过计算每个网页得到分数的多寡评价网页重要性的方法,就是 PageRank的基本设计想法,也称作链接关系分析( link analyze)。

Page Rank

  如果分数被这样不断地传递下去,因为万维网彼此相连,这样的计算会没完没了吗?或者说 PageRank的计算会收敛吗?

  图4-18所示为对叁个网页分别计算它们 PageRank的一个迭代收敛的例子。

Page Rank

  在图4-18种,无论怎样迭代的计算,不难发现,每个网页的得分都是固定不变的。网页A的分数平均分给了网页B和网页C,网页B又完全给了C最后网页C把得到的分数又还给了网页A。可以看出这3个网页得到的分数之和总是1,而且无论如何循环计算,这种分数分布不再发生变化。这种特性在数学上称为“不变分布”,这也是 PageRank计算收敛的最终奥秘。当然 PageRank实际的计算公式考虑了各种因素,使得这种不变分布必然存在。这些数学上的塬理,请读者参阅相关随机过程的书籍或论文予以透彻了解,下面我们将介绍 PageRank的计算公式。

Page Rank

  (1)PRn(A):网页A的 PageRank值。

  2)PRn-1(Ti):网页T存在指向A的链接,并且网页Ti在上一次迭代时的 PageRank值。

  (3)C(Ti):网页T的外链数量。

  (4)d:阻尼系数,图片.png表示在随机冲浪模型中网页T将自身d的份额的 PageRank值平均分给每个外链。由于网页Ti指向网页A,因此网页A获得来自网页Ti的C(Ti)分之一的 PageRank值。

  从整体上来看这个公式,一个网页A的 PageRank值,由两方面得分决定,其比例分别为1-d和d

  方面,任何网页都有可能跳转到网页A来(不通过链接方式)假定全集为n个网页,那么其中任意一个网页就有n个可能的无条件跳转的去处。每种跳转的概率相等,均为1/n。因此网页A得到了每个网页的1/mn的(1-d)的分数,每个网页的分数初始值都为1。每次分数不论如何流动,其总值都为n。因此,图片.png的分数被分配到了网页A上 PageRank中1-d的分数也可以理解为一个网页的基本分数,这是在整个计算中固定不变的常数。

  另一方面,由于有些网页存在明确的指向网页A的链接,因此图片.png的分数被分配给了网页A,

  因此对于公式

图片.png

  第1个部分可以认为是固有得分;第2个部分可以认为是因为被其它网页指向而得到其它网页的一部分得分。

  在数学上可以证明, PageRank由两方面因素共同决定的计算方法可以避免 Dangling page和 Page sink的问题[ angville et al2003]。

  PageRank的计算涉及随机过程方面的数学塬理,接下来通过一系列的例子来深入理解。假定存在如图4-19所示的简单的网页链接关系。

Page Rank

  由 Page Rank的计算方法得到下列方程组,假定d=0.5:

  PR(A)=0.5+0.5×PR(C)

  PR(B)=0.5+0.5×(PR(A)12)

  PR(C)=0.5+0.5×(PR(A)12+PR(B))

  解这个叁元方程组,得到:

  PR(A)=14/13=1.0769

  PR(B)=10/13=0.76923

  PR(C)=15/13=1.1538

  从最后的 PageRank值可以清楚地看出,在这3个网页中,网页C的重要性最高,它的得分为11538分;其次是网页A;最后是网页B。这种通过链接关系的分析得到网页重要性是合理的网页C在这个局部是更被“认可"的,它被网页A和网页B指向网页A被更高级别的网页C"认可”,而网页B被网页A“认可”这样网页A和网页B同样具有一个 Backlink由于网页C的级别大于网页A,因此最终网页A的重要性大于网页B

  此外, PageRank还可以通过迭代计算的方法得到,计算过程如表4-2所示。

Page Rank

  这里初始向量为5=[1 1 1]T,表示每个网页的初始 PageRank值均为1。到达第7次迭代时,迭代结果和第6次迭代的结果基本相同,因此迭代停止。继续计算下去, PageRank值不再变化或仅有很小的变化,这种稳定的 PageRank值被用于衡量网页的重要性。然而当网页数量很大,这种链接关系复杂时,采用这些方法是低效的。

  PageRank的计算方法


  在实践中,采用幂法( Power method)来计算 PageRank。

  PageRank的这个经典公式:

Page Rank

  可以转化为求解图片.png的值,其中矩阵为图片.png(A也被称为“ Google matrix”)d为阻尼系数,P为概率转移矩阵,e为n维的全1行,m为全部网页个数(概率转移矩阵大小,x是各个网页的初始 PageRank值,初始每个网页的 PageRank值均为1。因此,eem矩阵在每次迭代时与全部网页的 PageRank向量乘积总是保持一个n维的全1-d的向量(在下面的例子中会提到)这可以理解为总能够从其他网页得到1-d的分数,幕法计算过程的伪码如下。

  (1)x←任意一个初始向量

  (2)r←Ax

  (3)if(xrl)<ε,返回r

  (4)eler x←r,goto2

  使用图419的例子来理解上面的计算过程。

  (1)P概率转移矩阵的计算过程。

  初始化一个矩阵Pi,若网页i存在一个指向网页j的链接,则Pij;否则=0,在圈4-19的例子中,图片.png然后将每100行除以该行非零数字之和。例如矩阵P的第1行除以该行数字之和等于图片.png每一行均按照这样的方法处理得到如下矩阵:

Page Rank

  这样的矩阵也称为“马尔可夫转移矩阵”( markov transmit matrix),它记录了每个网页跳转到其他网页的概率。对于第1行,网页A跳转到网页B和网页C的概率各为1/2。通常使用其转置矩阵进行计算,即:

Page Rank

  (3)循环迭代计算 PageRank的过程。

  第1步

Page Rank

Page Rank

  在最后两次的结果近似或相同的情况下迭代结束,这个结果和解方程、简单迭代的方法求出的结果是一致的。用幕法计算PageRank总是收敛的,即总会在有限的迭代计算轮次内结束。

  参考文献[ Longville et al2003][ Haveliwala et al2003][Lars Elden2003]可以进一步深入理解 PageRank计算过程收敛的奥秘,以及参数d是如何影响收敛速度的基本塬理。

  在实际应用中,计算 PageRank的过程要比想像的更为复杂。例如从提高收敛效率角度,加快计算速度;采用将 Google matrixPageRank这个概率转移矩阵学术上也称作 Google matrix)分块的思想执行并行计算减少磁盘IO。从而发挥多CPU的作用,有兴趣的读者可以进一步探索。

  自从 PageRank的计算方法被公开后,各种为了提高排名而进行的作弊行为也随之而来。 Google及其他采用类似技术的搜索引擎公司都面临着前所未有的压力, PageRank的科学性和可信度也受到了极大怀疑。但是科学家们采用了各种反作弊的技术手段,沉重打击了作弊者的不道德行为,维护了 PageRank应有的价值。

  至此,我们结束了分析系统的全部旅程,为了更好的从全局理解分析系统各个模块的工作关系,下一节中将和大家一起从宏观全局的视角重新回顾分析系统。

上一篇:中文分词

下一篇:分析系统结构图

评论区

表情

共0条评论
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~

相关内容

点击排行

随机新闻

评论排行榜