纯技术:谷歌PageRank算法原理及实现

2018/11/09 08:00 · SEO教程 ·  · 0评论

  PageRank算法原理介绍

  PageRank算法是google的网页排序算法,在《The Top Ten Algorithms in Data Mining》一书中第6章有介绍。大致原理是用户搜索出的多个网页需要按照一定的重要程度(即后面讲的权重)排序,每个网页的权重由所有链接到它的其他 网页的权重的加权和,加权系数为每个网页链出的网页数的倒数,也就是说每个网页的权重会平均分配到其链向的所有网页。

  例如A链接到B和C,B链接到C,C链接到A,P(X)表示X的权重,如下图所示

谷歌PageRank

  则每个节点的权重关系为:

  P(A) = P(C)

  P(B) = P(A)/2

  P(C) = P(A)/2 + P(B)

  一般地,可以写成个线性方程组形式:

  P = AP

  如此通过迭代即可求出最终各个网页的权重值。

  但是,当存在某些特殊情况时,如某个网页的链入或链出数为0,则迭代不会收敛。因此在上述算法中增加了个阻尼系数d,d表示用户会继续点击下一网页的概率,同时用户在1-d的概率下会随机访问到任意网页,那么上面的公式会修正为:

  P = (1-d)/N * ones(N,1) + d*AP

  其中N为所有网页数,ones(N,1)表示N行1列的全1矩阵。通过上述公式可以迭代计算出最终各网页权重。

  详细介绍可以参考wiki百科。

  算法实现

  首先声明这个CPageRank类:

CPageRank类

  下面就是具体各个函数的实现了。

  首先构造函数主要是初始化一些迭代相关变量,分配空间等,这里把生成节点指向图的工作也放在这里,支持直接随机生成和读取二进制文件两种方式。

函数

  析构函数自然就是释放内存了:

析构函数

  下面就是随机生成或读取文件产生节点指向关系,如果随机生成的话,会自动保存当前生成的图,便于遇到问题时可复现调试:

  既然已经产生了各个节点的关系了,那PageRank的核心思想就是根据关系,生成出上面的转移矩阵P:

PageRank的核心
PageRank的核心

  接下来就需要求解出各个节点的权重,process函数里先调用GenerateP生成出P矩阵,然后采用迭代法求解,当时为了测试收敛速度,直接返回了迭代次数:

process函数
process函数

  最后的结果已经存在了m_pf32OutWeight中了,下面函数直接传出结果:

m_pf32OutWeight

  这样,整个算法就算完成了,考虑到篇幅,贴上来的代码把opencv显示相关的代码去掉了,完整代码见

  下面是结果图,即便节点数较多时,算法收敛也比较快。

算法收敛

  分析总结

  对于上面这个公式,看到网上有人假定P的总能量是1,则可以改写为P=BP 的形式来进行迭代,这种方法也实现了一下,问题仍然是当存在网页链入或者链出数为0时,每次迭代后不能保证能量守恒,那么下一次就会导致P=BP这个公式 不成立,从而出现迭代不收敛;一种有效的做法是每次迭代后就将P进行能量规一化,这样是可以保证结果的收敛性的。但是这种做法与原始算法的结果会有一点细 微的出入。因此建议按照原始的公式进行迭代求解。

本文地址:https://www.foxizhanzhang.com/17.html
文章标签:
版权声明:本文为原创文章,版权归 佛系站长 所有,欢迎分享本文,转载请保留出处!

文件下载

上一篇:
下一篇:

 发表评论


表情