PageRank是[Google]专有的[算法]，用于衡量特定网页相对于索引中的其他网页而言的重要程度。
不同的网页直接存在着引用的关系，就像一张图一样：
屏幕快照 2018-04-24 下午11.26.03.png
这个图也可以转化为矩阵表示，其中W[1][0]=0.3333表示从网页A到B的概率，其他它的也是同理：
[[ 0. 0.5 1. 0. ]
[ 0.33333333 0. 0. 0.5 ]
[ 0.33333333 0. 0. 0.5 ]
[ 0.33333333 0.5 0. 0. ]]
直接看代码，从其他地方拿过来直接改的：
from numpy import *
import numpy as np
a = array([[0, 1, 1, 0],
[1, 0, 0, 1],
[1, 0, 0, 1],
[1, 1, 0, 0]], dtype=float)
def graphMove(a):
b = transpose(a) #
c = zeros((a.shape), dtype=float)
for i in range(a.shape[0]):
for j in range(a.shape[1]):
c[i][j] = a[i][j] / max((b[j].sum()),1)
return c
def firstPr(c):
pr = zeros((c.shape[0], 1), dtype=float)
for i in range(c.shape[0]):
pr[i] = float(1) / c.shape[0]
# print pr,"\n==================================================="
return pr
def pageRank(p, m, v):
vv=v
while (sum((p * dot(m, v) + (1 - p) * v-v)**2)>1e-9):
print(sum(p * dot(m, v) + (1 - p) * v-v)**2)
v = p * dot(m, v) + (1 - p) * v
print (v)
return v
if __name__ == "__main__":
M = graphMove(a)
print(M)
pr = firstPr(M)
print(pr)
p = 0.8
print pageRank(p, M, pr)
其中 m 和 v 分别为：
[[ 0. 0.5 1. 0. ]
[ 0.33333333 0. 0. 0.5 ]
[ 0.33333333 0. 0. 0.5 ]
[ 0.33333333 0.5 0. 0. ]]
[[ 0.25]
[ 0.25]
[ 0.25]
[ 0.25]]
运算结果如下：
3.08148791102e-33
[[ 0.333328]
[ 0.222224]
[ 0.222224]
[ 0.222224]]
看样子是和书中说得一样，下面我们修改m，及m对应的图如下（终止点问题）：
[[ 0. 0.5 0. 0. ]
[ 0.33333333 0. 0. 0.5 ]
[ 0.33333333 0. 0. 0.5 ]
[ 0.33333333 0.5 0. 0. ]]
屏幕快照 2018-04-24 下午11.32.43.png
运算结果如下：
4.77908611974e-09
[[ 4.64238536e-05]
[ 6.76593827e-05]
[ 6.76593827e-05]
[ 6.76593827e-05]]
虽然收敛了，但是结果看着并不是我们想要的。
修改实现代码：
def pageRank(p, m, v):
e=v
while (sum((p * dot(m, v) + (1 - p) * e-v)**2)>1e-9):
print(sum(p * dot(m, v) + (1 - p) * e-v)**2)
v = p * dot(m, v) + (1 - p) * e
print (v)
return v
运算结果如下：
4.58712913112e-09
[[ 0.10136897]
[ 0.12840406]
[ 0.12840406]
[ 0.12840406]]
修改m，以及m对应的图（陷阱问题）：
[[ 0. 0.5 0. 0. ]
[ 0.33333333 0. 0. 0.5 ]
[ 0.33333333 0. 1. 0.5 ]
[ 0.33333333 0.5 0. 0. ]]
屏幕快照 2018-04-24 下午11.34.08.png
运算结果如下：
4.77908611974e-09
[[ 4.64238536e-05]
[ 6.76593827e-05]
[ 6.76593827e-05]
[ 6.76593827e-05]]
我的理解，既然是相对与其他网页的重要程度，那么就可以理解为：
SUM=p其他网页对该网页的引用数+q该网页对其他网页的引用数
对这个SUM进行排序。
实际在矩阵相乘中的作用就是如此，权重就在一定程度上代表了重要程度，所以这个计算最终一定是收敛的。
数学之美中公式记录如下：
屏幕快照 2018-04-25 上午12.00.08.png
屏幕快照 2018-04-25 上午12.01.06.png
网友评论