Machine Learning：PageRank算法

由于存在一些出链为0，也就是那些不链接任何其他网页的网， 也称为孤立网页，使得很多网页能被访问到。因此需要对 PageRank公式进行修正，即在简单公式的基础上增加了阻尼系数（damping factor）q， q一般取值q=0.85。

其意义是，在任意时刻，用户到达某页面后并继续向后浏览的概率。 1- q= 0.15就是用户停止点击，随机跳到新URL的概率）的算法被用到了所有页面上，估算页面可能被上网者放入书签的概率。

最后，即所有这些被换算为一个百分比再乘上一个系数q。由于下面的算法，没有页面的PageRank会是0。所以，Google通过数学系统给了每个页面一个最小值。

这个公式就是.S Brin 和 L. Page 在《The Anatomy of a Large- scale Hypertextual Web Search Engine Computer Networks and ISDN Systems 》定义的公式。

所以一个页面的PageRank是由其他页面的PageRank计算得到。Google不断的重复计算每个页面的PageRank。如果给每个页面一个随机PageRank值（非0），那么经过不断的重复计算，这些页面的PR值会趋向于正常和稳定。这就是搜索引擎使用它的原因。

4. PageRank幂法计算(线性代数应用)

4.1 完整公式：

关于这节内容，可以查阅：《谷歌背后的数学》

首先求完整的公式：

Arvind Arasu 在《Junghoo Cho Hector Garcia - Molina, Andreas Paepcke, Sriram Raghavan. Searching the Web》 更加准确的表达为：

是被研究的页面，是链入页面的数量，是链出页面的数量，而N是所有页面的数量。

PageRank值是一个特殊矩阵中的特征向量。这个特征向量为：

R是如下等式的一个解：

如果网页i有指向网页j的一个链接，则

否则＝0。

4.2 使用幂法求PageRank

那我们PageRank 公式可以转换为求解的值，

其中矩阵为 A = q  × P + ( 1 一 q) *  /N 。 P 为概率转移矩阵，为 n  维的全 1 行. 则 =

幂法计算过程如下：

X  设任意一个初始向量, 即设置初始每个网页的 PageRank值均。一般为1.

R = AX;

while (1 )

    ( if ( l X - R I < )

    { //如果最后两次的结果近似或者相同，返回R return R;

    }

else {

       X =R; R = AX;

      }

}

4.3 求解步骤：

一、 P概率转移矩阵的计算过程:

先建立一个网页间的链接关系的模型,即我们需要合适的数据结构表示页面间的连接关系。

1) 首先我们使用图的形式来表述网页之间关系：

现在假设只有四张网页集合：A、B、C，其抽象结构如下图1：

图1 网页间的链接关系

显然这个图是强连通的（从任一节点出发都可以到达另外任何一个节点）。

2）我们用矩阵表示连通图：

用邻接矩阵 P表示这个图中顶点关系 ，如果顶（页面）i向顶点（页面）j有链接情况 ，则pij   =   1 ，否则pij   =   0 。如图2所示。如果网页文件总数为N ， 那么这个网页链接矩阵就是一个N x N  的矩 阵 。 

注：相关网站建设技巧阅读请移步到建站教程频道。

（编辑：应用网_镇江站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!