先举个例子
上面的二部图表示 user A 对 item a 和 c 感兴趣，B 对 a b c d 都感兴趣，C 对 c 和 d 感兴趣。本文假设每条边代表的感兴趣程度是一样的。
现在我们要为 user A 推荐 item，实际上就是计算 A 对所有 item 的感兴趣程度。在 personal rank 算法中不区分 user 节点和 item 节点，这样一来问题就转化成：对节点 A 来说，节点 A B C a b c d 的重要度各是多少。重要度用 PR 来表示。
初始赋予 ，即对于 A 来说，他自身的重要度为满分，其他节点的重要度均为 0。
然后开始在图上游走。每次都是从 PR 不为 0 的节点开始游走，往前走一步。继续游走的概率是停留在当前节点的概率是
第一次游走， 从 A 节点以各自 50%的概率走到了 a 和 c，这样 a 和 c 就分得了 A 的部分重要度。第一次游走结束后 PR 不为 0 的节点有 A a c。
第二次游走，分别从节点 A a c 开始，往前走一步。这样节点 a 分得 A 12∗α12∗α的重要度，节点 c 分得 A 12∗α12∗α的重要度，节点 A 分得 a 12∗α12∗α的重要度，节点 A 分得 c 13∗α13∗α的重要度，节点 B 分得 a 12∗α12∗α的重要度，节点 B 分得 c 13∗α13∗α的重要度，节点 C 分得 c 13∗α13∗α的重要度。最后PR(A)PR(A)要加上1−α1−α
经过以上推演，可以概括成公式：
\[ PR(j)= \begin{cases}
a*\sum_{i}\frac{PR(i)}{|out(i)|},\quad if(j \ne u) \\
(1-a)+a*\sum_{I}\frac{PR(i)}{|out(i)|},\quad if(j =u)
\end{cases}\]
u 是待推荐的用户节点。
注意这里有一个现象，上述代码从节点 b 开始游走，最终算得的 PR 重要度最高的不是 b，而是 B。
personalrank 经过多次的迭代游走，使得各节点的重要度趋于稳定，实际上我们根据状态转移矩阵，经过一次矩阵运算就可以直接得到系统的稳态。公式(1)的矩阵表示形式为：
\[r=(1−α)r0+αM^T(2)\]
其中 r 是个 n 维向量，每个元素代表一个节点的 PR 重要度，r0 也是个 n 维向量，第 i 个位置上是 1，其余元素均为 0，我们就是要为第 i 个节点进行推荐。M 是 n 阶转移矩阵：
\[ Mij= \begin{cases}
frac{1}{|out(i)|},\quad if(j \in out(i)) \\
0,\quad else
\end{cases}\]
按照矩阵乘法把(2)展开就可以得到(1)。
由(2)可以得到两种变形：
\[(I−αM^T)r=(1−α)r0\](4)
\[r=(I−αM^T)−1(1−α)r0\](5)
利用(4)，解一次线性方程组就查以得到 r，对 r 中的各元素降序排列取出前 K 个就得到了节点 i 的推荐列表。实践中系数矩阵\( ((I−αM^T) \)是一个高度稀疏的矩阵，解这种线性方程流行的方法是 GMRES。另外在 scipy 中提供了多种稀疏矩阵的存储方法：coo,lil,dia,dok,csr,csc 等，各有各的优缺点，dok 可以快速的按下标访问元素，csr 和 csc 适合做矩阵的加法、乘法运算，lil 省内存且按下标访问元素也很快。更多内容参见 scipy 中的稀疏矩阵。
由于我们只关心 r 中各元素的相对大小，并不关心其真实值，所以(5)可以写为
\[r=(I−αM^T)^{−1}r0\](6)
矩阵\((I−αM^T)^{−1}\)乘以 r0 相当于是取出矩阵的第 i 列，因此为节点 i 进行推荐时对矩阵\((I−αM^T)^{−1}\)的第 i 列排序即可，所以求出矩阵\((I−αM^T)^{−1}\)的逆就得到了所有节点的推荐结果。
但是数据量很大的时候还是出现内存不足的现象，博主在自己的 mac 上测试 10000*10000 的矩阵需要消耗 800m 内存，网站的数据远远不止这些，那么额外消耗的内存会更多，接下来楼主贴出来的代码有点暴力计算的意思，但是会消耗不少的时间吧！
# -*- coding: utf-8 -*-
# @Time : 2018/4/16 上午 10:55
# @Author : Tomcj
# @File : main.py
# @Software: PyCharm
# coding=utf-8
import numpy as np
import time
from scipy.sparse.linalg import gmres, lgmres
from scipy.sparse import csr_matrix
import os
from collections import defaultdict
class personalRank:
def __init__(self,path):
self.curr_dir = path
self.alpha = 0.8
self.zaful_data = []
self.node_degree = defaultdict(set)
self.data_for_csc = []
self.data_for_csc_row = []
self.data_for_csc_col = []
self.zaful_len=0
self.zaful_distinct_data=[]
self.users=set()
self.goods=set()
# 获取所有的数据
def getData(self):
# 实验测试使用 zaful 站采样的 10000 条数据
with open(os.path.join(self.curr_dir),'r') as fp:
fp.readline()
for line in fp:
data=line.strip().split("\t")
self.zaful_data.append([data[0],data[1]])
self.node_degree[data[0]].add(data[1])
self.node_degree[data[1]].add(data[0])
self.users.add(data[0])
self.goods.add(data[1])
#构造 csr 或则 csc 系数矩阵
self.zaful_distinct_data=self.node_degree.keys()
self.zaful_len=len(self.zaful_distinct_data)
zaful_data_map={ self.zaful_distinct_data[x]:x for x in xrange(self.zaful_len)}
for user,goods_id in self.zaful_data:
indexUser=zaful_data_map[user]
indexGoods=zaful_data_map[goods_id]
self.data_for_csc.append(-self.alpha*1.0/len(self.node_degree[user]))
self.data_for_csc.append(-self.alpha*1.0 / len(self.node_degree[goods_id]))
self.data_for_csc_row.append(indexUser)
self.data_for_csc_col.append(indexGoods)
self.data_for_csc_row.append(indexGoods)
self.data_for_csc_col.append(indexUser)
for x in xrange(self.zaful_len):
self.data_for_csc.append(1)
self.data_for_csc_row.append(x)
self.data_for_csc_col.append(x)
# 预测所有数据，基于 item
def predictAll(self):
f=open('result.txt','w')
AA = csr_matrix((self.data_for_csc, (self.data_for_csc_row, self.data_for_csc_col)), shape=(self.zaful_len, self.zaful_len))
# 暴力穷举解法
try :
for xda in xrange(self.zaful_len):
if self.zaful_distinct_data[xda] in self.goods:
curr_goods=self.zaful_distinct_data[xda]
b = np.zeros((self.zaful_len, 1))
b[xda] = 1 * (1 - self.alpha)
r = gmres(AA, b, tol=1e-08, maxiter=1)[0]
# r = lgmres(AA, (1 - alpha) * r0, tol=1e-08,maxiter=1)[0] #lgmres 用来克服 gmres 有时候不收敛的问题，会在更少的迭代次数内收敛
rank = {}
for j in xrange(self.zaful_len):
rank[self.zaful_distinct_data[j]] = r[j]
li = (sorted(rank.items(), cmp=lambda x, y: cmp(x[1], y[1]), reverse=True))
ele_cnt=0
for ele in li:
if ele[0] in self.goods and ele[0]!=curr_goods:
ele_cnt+=1
f.write(self.zaful_distinct_data[xda]+','+ele[0]+'\n')
finally:
f.close()
if __name__ == '__main__':
begin = time.time()
pr=personalRank('path')
pr.getData()
pr.predictAll()
end = time.time()
print end-begin
