影响未来的十大算法之一：机器学习与数据挖掘的PageRank算法( 二 ) _PageRank算法

文章插图

公式中， Bi表示所有链接到Pi的网页集合。
为了方便数学分析，我们定义一个超链矩阵M[Mij]：

文章插图

其中第i行j列的值Mij表示用户从页面j转到页面i的概率。
按照这个定义，图1的超链矩阵为

文章插图

设初始时每个页面的rank值为1/N ，这里就是1/4 。按A—D顺序得到向量v：v=[1/4,1/4,1/4,1/4]
此时如果做矩阵乘法，使M*v就得到一个新的rank阵v'：M第一行分别是A、B、C和D转移到页面A的概率，而v的第一列分别是A、B、C和D当前的rank ，因此用M的第一行乘以v的第一列，所得结果就是页面A最新rank的合理估计，故M*v的结果v'就分别代表A、B、C、D新rank值。
然后用M再乘以这个新的rank向量v' ，又会产生一个rank向量。迭代这个过程，可以证明v最终会收敛，即v≈Mv ，此时计算停止，最终得到的v'就是rankpage的排序结果：
V'=M*V----------(1)
3、复杂数学模型（带a的数学模型）
但是我们也注意到，要想上述迭代结果最终收敛，必须满足一个条件：图是强连通的，即从任意网页可以到达其他任意网页。假设我们把上面图中C到D的链接丢掉， C变成了一个终止点。再进行迭代，那么迭代的最终结果是v'=[0,0,0,0] ，显然算法失效了。除了终止点问题外，还有一个陷阱问题，即将图1中D到C的链接删除后，再加一条C指向C自身的链接。那么按上述迭代过程，最终v'=[0,0,1,0] ，此时算法也是失效的。

文章插图

图2 终止点问题

文章插图

图3 陷阱问题
为了解决终止点问题和陷阱问题，我们需要对算法进行改进：假设用户在选择下一个跳转的页面时，选择当前页及当前页上的链接的概率为a ，选择其他页面的概率为（1-a）,选择其他页面中每个页面的概率都相同为1/n ，则计算PR值的公式演变为：
v′=αMv+(1?α)(1/n)-----(2)
四、PageRank算法的Python实现
下面我们以图3为例，分别用代码实现公式（1）和公式（2）的排序结果：
import numpy as np
M = [[0,1/2,0,1/2], [1/3,0,0,1/2], [1/3,1/2,1,0],[1/3,0,0,0]
U = [1/4,1/4,1/4,1/4]
U0 = np.array(U)
U_past_none_alpha = []
while True:
U = np.dot(M,U)
if str(U) == str(U_past_none_alpha):
Break
U_past_none_alpha = U
print('公式1的结果:',U)
U_past_has_alpha = []
while True:
U = 0.8*(np.dot(M,U))+0.2*U0
if str(U) == str(U_past_has_alpha):
Break
U_past_has_alpha = U
print('公式2的结果:',U)
输出结果如下：
C:Users1009PycharmProjects20190329venvIncludeIncludeScriptsPython.exe C:/Users/1009/PycharmProjects/20190329/pagerank.py
公式1的结果：[0. 0. 1. 0.]
公式2的结果：[0.13172043 0.11917563 0.6639785 0.08512545]
Process finished with exit code 0
显然，公式（2）的结果更加科学准确！
五、后记：
PageRank算法就介绍到这里了，我的感觉就是按公式编码实现其实并不难，难的在于公式背后的数学逻辑思维。通过和做算法开发的同事交流，我才知道原来算法最最重要的就是思维，没有思维的算法就如同没有灵魂的躯体一样，完全不能适应复杂的现实场景的需求。谨以此文为开端，开始我的算法之旅，希望与广大测试同行一起进步！