一.基本的PageRank算法

PageRank算法是用于网页权重计算的算法,它本质就是一个马尔可夫模型,每个网页$Page(i),i=1,2,..,n$就是一个状态,状态的转移概率由该页面超链接的其他网页均摊,而PageRank值即是马尔可夫模型的平稳态概率分布,平稳态概率分布的每个分量即是对应的每个网页的PageRank值,比如如下的网页A、B、C、D的链接关系:
avatar

可以很方便的写出它的状态转移矩阵(A,B,C,D分别对应0,1,2,3):

$$ P=\begin{bmatrix} 0 & 1/2 & 1 & 0 \\ 1/3 & 0 & 0 & 1/2 \\ 1/3 & 0 & 0 & 1/2\\ 1/3 & 1/2 & 0 & 0 \end{bmatrix} $$

下面,我们可以直接利用其马尔可夫模型求解其PageRank值

In [1]:
import os
os.chdir('../')
from ml_models.pgm import SimpleMarkovModel
import numpy as np
In [2]:
#定义初始概率
init_prob=np.ones(shape=(4,1))/4.0
#定义概率转移矩阵
trans_matrix=np.asarray([
    [0.,0.5,1.0,0],
    [1.0/3,0,0,1.0/2],
    [1.0/3,0,0,1.0/2],
    [1.0/3,1.0/2,0,0],
])
In [3]:
#求解pagerank:即通过足够长的step后的平稳态概率分布
smm=SimpleMarkovModel(status_num=4)
smm.predict_prob_distribution(set_init_prob=init_prob,set_prob_trans_matrix=trans_matrix,time_steps=10)
Out[3]:
array([[0.33325195],
       [0.22224935],
       [0.22224935],
       [0.22224935]])
In [4]:
#校验:设置其他的step校验一下
smm.predict_prob_distribution(set_init_prob=init_prob,set_prob_trans_matrix=trans_matrix,time_steps=20)
Out[4]:
array([[0.33333325],
       [0.22222225],
       [0.22222225],
       [0.22222225]])

二.带平滑项的PageRank算法

但是,实际情况往往会比较复杂,比如某些网页只进不出,如下图网页C就只进不出,这样会导致马尔可夫链无法收敛到一个稳定态

avatar

这时,它的概率转移矩阵为:

$$ P=\begin{bmatrix} 0 & 1/2 & 0 & 0 \\ 1/3 & 0 & 0 & 1/2 \\ 1/3 & 0 & 0 & 1/2\\ 1/3 & 1/2 & 0 & 0 \end{bmatrix} $$

我们再求解一下它的PageRank值

In [5]:
trans_matrix=np.asarray([
    [0.,0.5,0,0],
    [1.0/3,0,0,1.0/2],
    [1.0/3,0,0,1.0/2],
    [1.0/3,1.0/2,0,0],
])
smm.predict_prob_distribution(set_init_prob=init_prob,set_prob_trans_matrix=trans_matrix,time_steps=50)
Out[5]:
array([[2.55407417e-08],
       [3.72237693e-08],
       [3.72237693e-08],
       [3.72237693e-08]])

几乎都逼近到0了,我们可以通过添加一个平滑项来解决这个问题,即:

$$ A=dP+\frac{(1-d)}{n}E $$

这里,$0\leq d \leq 1$,$E$是元素均为1的方阵,$n$表示状态数,注意,这样对每一列求和后可能由某些列的概率概率值<1(比如我们上面问题中的第三列),所以对于每一步更新:

$$ \pi_{t+1}=A\pi_t $$

都需要对$\pi_{t+1}$做一次归一化操作,一般取无穷范数作归一化,即$\pi_{t+1}$中绝对值最大的分量:

$$ \pi_{t+1}=\frac{\pi_{t+1}}{\mid\mid \pi_{t+1}\mid\mid} $$

下面对PageRank算法做一个单独的实现:

In [6]:
"""
PageRank算法实现,封装到ml_models.pgm
"""

class PageRank(object):
    def __init__(self, init_prob, trans_matrix):
        self.init_prob = init_prob
        self.trans_matrix = trans_matrix

    def get_page_rank_values(self, time_steps=None, set_init_prob=None, set_prob_trans_matrix=None):
        init_prob = self.init_prob if set_init_prob is None else set_init_prob
        trans_matrix = self.trans_matrix if set_prob_trans_matrix is None else set_prob_trans_matrix
        for _ in range(0, time_steps):
            init_prob = trans_matrix.dot(init_prob)
            init_prob = init_prob / np.max(np.abs(init_prob))
        return init_prob / np.sum(init_prob)
In [7]:
trans_matrix=0.85*np.asarray([
    [0.,0.5,0.0,0],
    [1.0/3,0,0,1.0/2],
    [1.0/3,0,0,1.0/2],
    [1.0/3,1.0/2,0,0],
])+0.15*np.ones(shape=(4,4))/4.0
pr=PageRank(init_prob=init_prob,trans_matrix=trans_matrix)
pr.get_page_rank_values(10)
Out[7]:
array([[0.1960504],
       [0.2679832],
       [0.2679832],
       [0.2679832]])
In [8]:
#检验下其他step
pr.get_page_rank_values(100)
Out[8]:
array([[0.19605034],
       [0.26798322],
       [0.26798322],
       [0.26798322]])
In [ ]: