MapReduce 基础算法【PageRank网页排名算法】

左手的ㄟ右手 2022-05-17 13:20 454阅读 0赞

### 目录 ###

*   *   *  目录
         *  PageRank网页排名算法
         *  基本思想
         *  简单计算
         *  PageRank 的简化模型
         *  简化模型的问题
            
             *  排名泄露
             *  排名下沉
         *  PageRank的随机浏览模型
         *  PageRank幂法计算
            
             *  完整公式
         *  求解步骤
            
             *  P概率转移矩阵的计算过程：
             *  A矩阵的计算过程：
             *  循环迭代计算PageRank的过程
         *  PageRank优缺点
         *  参考文献

### PageRank网页排名算法 ###

PangeRank算法是Google公司创始人之一Larry Page发明的，它是一个用来衡量评估网页重要性或者等级的算法。Google公司据此标识网页的PR值，最直观的条件就是有很多网页链接到它，尤其是要有很高Rank值的网页链接到该网页。  
![PageRank网页排名算法][PageRank]

### 基本思想 ###

如果网页T存在一个指向网页A的连接，则表明T的所有者认为A比较重要，从而把T的一部分重要性得分赋给A，这个重要性得分值为:PR(T)/L(T)  P R ( T ) / L ( T ) .其中PR(T)  P R ( T ) 为T  T 的PangeRank值，L(T) L ( T )为T  T 的输出链数。则A的PangeRank值为一系列类似于T T的页面重要性得分值的累加。

即一个页面的得票数`由所有链向它的重要性来决定的`，到一个页面的超链接相当于`对该页面投一票`。一个页面的PangeRank是由所有链向它的页面的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级，相反如果第一个页面没有任何链入页面，那么它没有等级。

### 简单计算 ###

假设一个由只有4个页面组成的集合：A,B,C和D  A , B , C 和 D 。如果所有页面都链向A  A ，那么A的PR值将是B，C,D B，C , D的和。

PR(A)=PR(B)\+PR(C)\+PR(D)  P R ( A ) = P R ( B ) + P R ( C ) + P R ( D )

继续假设  B  B  也有链接到  C C ，并且  D  D  也有链接到包括  A A 的3个页面。一个页面不能投票2次。所以  B  B  给每个页面半票。同样，  D D 投出的票只有三分之一算到了A的PangeRank上。

PR(A)=PR(B)2\+PR(C)1\+PR(D)3  P R ( A ) = P R ( B ) 2 + P R ( C ) 1 + P R ( D ) 3

换句话说，根据链出的总数平分一个页面的PR值。

PR(A)=PR(B)L(B)\+PR(C)L(C)\+PR(D)L(D)  P R ( A ) = P R ( B ) L ( B ) + P R ( C ) L ( C ) + P R ( D ) L ( D )

### PageRank 的简化模型 ###

互联网上的各个网页之间的连接关系我们都可以看成一个有向图，对于任意的网页，它的PR值可以表示为：

PR(u)=∑v∈BuPR(v)L(v)  P R ( u ) = ∑ v ∈ B u P R ( v ) L ( v )

其中，  Bu  B u  是所有链接到网页  u  u  的网页集合，网页  v v 是属于集合  Bu  B u  的网页，  L(v)  L ( v )  则是网页  v  v  的对外链接数（即出度）。

### 简化模型的问题 ###

#### 排名泄露 ####

![这里写图片描述][14955829.jpg]

如上图所示，如果存在网页没有出度链接，如A点，则会产生排名泄露问题，经过多次迭代之后，所有网页的PR值会趋向于0。其中，有向图可以得出如下的初始的转移矩阵：

M=⎡⎣⎢⎢⎢⎢000000100001121200⎤⎦⎥⎥⎥⎥ M =\[0001 20001 201000010\]

在这个矩阵中，第一列表示用户网页A跳转到其他页面的概率。即用户分别有B、C、D、都没向A跳转。

`注意：` 这里所有点的初始PR值都是**假设**为0.25.

如下表所示(各个点的迭代计算)：

#### 排名下沉 ####

![排名下降][23016059.jpg]  
若有网页没有入度链接，如节点A，其所产生的贡献会被由B、C、D构成的强连通分量“吞噬”掉，就会产生排名下沉，节点A的PR值会在迭代后趋向于0。

### PageRank的随机浏览模型 ###

由于存在一些出链为0，也就是那些不连接任何其他网页的网，也称孤立网，使得很多网页能被访问到。因此，对PageRank公式进行修正，即在简单模型的基础上增加了`阻尼系数q`,q 一般取值q=0.85.  q = 0.85. 其意义是，在任意时刻，用户到达某页面后并继续向后浏览的概率。1−q=0.15  1 − q = 0.15 就是用户停止点击，随机跳到新的URL的概率的算法被用到了所有页面上，估算页面可能被上网者放入书签的概率。

公式如下:

PR(A)=(PR(B)L(B)\+PR(C)L(C)\+PR(D)L(D)\+...)q\+(1−q)  P R ( A ) = ( P R ( B ) L ( B ) + P R ( C ) L ( C ) + P R ( D ) L ( D ) + . . . ) q + ( 1 − q )

所以一个页面的PageRank是由其他页面的PageRank计算得到。Google不断的重复计算每个页面的PageRank。如果给每个页面一个随机PageRank值，那么经过不断的重复计算，这些页面的PR值会趋向于正常和稳定。

### PageRank幂法计算 ###

#### 完整公式 ####

PageRank(pi)=1−qN\+q∑pjPageRank(pj)L(pj)  P a g e R a n k ( p i ) = 1 − q N + q ∑ p j P a g e R a n k ( p j ) L ( p j )

p1,p2,p3....,pn  p 1 , p 2 , p 3 . . . . , p n  是被研究的页面，  M(pi)  M ( p i )  是  pi  p i  链入页面的数量，  L(pj)  L ( p j )  是  pj  p j  链出页面的数量，而N是所有页面的数量。  
**PageRank**值是一个特殊矩阵中的特征向量，这个特征向量为：

R=⎡⎣⎢⎢⎢⎢PageRank(p1)PageRank(p2).....PageRank(pn)⎤⎦⎥⎥⎥⎥  R = \[ P a g e R a n k ( p 1 ) P a g e R a n k ( p 2 ) . . . . . P a g e R a n k ( p n ) \]

R的一个解是：

R=⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢(1−q)/N(1−q)/N...(1−q)/N⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥\+⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢φ(p1,p1)φ(p2,p1)...φ(pN,p1)φ(p1,p2)......φ(p1,pN)φ(pN,pN)⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥R  R = \[ ( 1 − q ) / N ( 1 − q ) / N . . . ( 1 − q ) / N \] + \[ φ ( p 1 , p 1 ) φ ( p 1 , p 2 ) . . . φ ( p 1 , p N ) φ ( p 2 , p 1 ) . . . . . . φ ( p N , p 1 ) φ ( p N , p N ) \] R

如果网页  i  i  有指向网页  j j 的一个链接，则  ∑Ni=1φ(pi,pj)=1  ∑ i = 1 N φ ( p i , p j ) = 1  ,否则  φ(pi,pj)=0  φ ( p i , p j ) = 0  .

### 求解步骤 ###

#### P概率转移矩阵的计算过程： ####

p 概率转移矩阵：

P=⎡⎣⎢001100110⎤⎦⎥(网页链接矩阵)，P′=⎡⎣⎢00112001210⎤⎦⎥(网页链接概率矩阵)，P′T=⎡⎣⎢⎢01212001100⎤⎦⎥⎥（P′的转置矩阵）  P = \[ 0 1 1 0 0 1 1 0 0 \] ( 网 页 链 接 矩 阵 ) ， P ′ = \[ 0 1 2 1 2 0 0 1 1 0 0 \] ( 网 页 链 接 概 率 矩 阵 ) ， P ′ T = \[ 0 0 1 1 2 0 0 1 2 1 0 \] （ P ′ 的 转 置 矩 阵 ）

#### A矩阵的计算过程： ####

PageRank公式可以转换为limx→∞AnX  lim x → ∞ A n X 的值。  
其余矩阵为A=q×P\+(1−q)∗eet/N  A = q × P + ( 1 − q ) ∗ e e t / N ,P为概率转移矩阵，et  e t 为n维的全1行（即单位矩阵）。

P概率转移矩阵

P=⎡⎣⎢⎢01212001100⎤⎦⎥⎥  P = \[ 0 0 1 1 2 0 0 1 2 1 0 \]

ee^t/N为

eet/N=⎡⎣⎢⎢131313131313131313⎤⎦⎥⎥  e e t / N = \[ 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 \]

A矩阵为：  q×P\+(1−q)∗eet/N=0.85×P\+0.15∗eet/N  q × P + ( 1 − q ) ∗ e e t / N = 0.85 × P + 0.15 ∗ e e t / N

A=⎡⎣⎢0.050.450.450.050.050.90.90.050.05⎤⎦⎥  A = \[ 0.05 0.05 0.9 0.45 0.05 0.05 0.45 0.9 0.05 \]

初始的每个网页的PageRank值均为1，即：

x∼=(1,1,1)  x ∼= ( 1 , 1 , 1 )  .

#### 循环迭代计算PageRank的过程 ####

第一步：

AX=⎡⎣⎢0.050.450.450.050.050.90.90.050.05⎤⎦⎥∗⎡⎣⎢111⎤⎦⎥=⎡⎣⎢0.05\+0.05\+0.90.45\+0.05\+0.050.45\+0.9\+0.05⎤⎦⎥=⎡⎣⎢10.551.4⎤⎦⎥=R  A X = \[ 0.05 0.05 0.9 0.45 0.05 0.05 0.45 0.9 0.05 \] ∗ \[ 1 1 1 \] = \[ 0.05 + 0.05 + 0.9 0.45 + 0.05 + 0.05 0.45 + 0.9 + 0.05 \] = \[ 1 0.55 1.4 \] = R

因为X与R的差别较大，继续迭代。 第二步：

AX=⎡⎣⎢0.050.450.450.050.050.90.90.050.05⎤⎦⎥∗⎡⎣⎢10.551.4⎤⎦⎥=⎡⎣⎢1.3370.4551.109⎤⎦⎥=R  A X = \[ 0.05 0.05 0.9 0.45 0.05 0.05 0.45 0.9 0.05 \] ∗ \[ 1 0.55 1.4 \] = \[ 1.337 0.455 1.109 \] = R

继续迭代这个过程，直到最后两次结果近似或者相同，即R最终收敛。最终的R就是各个页面的PageRank值。用幂法计算PageRank值总是收敛的，即计算过程是有限的。  
由于互联网上的网页的数量是巨大的，这样，矩阵的元素会较多，矩阵相乘是非常的大，`稀疏矩阵` 简化了计算量。

### PageRank优缺点 ###

优点：

是一个与查询无关的静态算法，所有网页的PageRank值通过离线计算获得；有效减少在线查询时的计算量，极大降低了查询响应时间。

缺点：

*  人们的查询具有主题特征，PageRank忽略了主题相关性，导致结果的相关性和主题性降低
 *  旧的页面等级会比新页面高。因为即使是非常好的新页面也不会有很多上游链接，除非它是某个站点的子站点。

### 参考文献 ###

1、[维基百科][Link 1]  
2、**《深入理解大数据大数据处理与编程实践》**  
3、**《这就是搜索引擎:核心技术详解》**

[PageRank]: http://oz3ijy2k5.bkt.clouddn.com/18-8-12/28270833.jpg
[14955829.jpg]: http://oz3ijy2k5.bkt.clouddn.com/18-8-12/14955829.jpg
[23016059.jpg]: http://oz3ijy2k5.bkt.clouddn.com/18-8-12/23016059.jpg
[Link 1]: http://en.wikipedia.org/wiki/Page_rank