PersonalRank算法以及实现

4,691次阅读

PersonalRank算法以及实现

先举个例子

上面的二部图表示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 $\frac{1}{2} * α$ 的重要度，节点c分得A $\frac{1}{2} * α$ 的重要度，节点A分得a $\frac{1}{2} * α$ 的重要度，节点A分得c $\frac{1}{3} * α$ 的重要度，节点B分得a $\frac{1}{2} * α$ 的重要度，节点B分得c $\frac{1}{3} * α$ 的重要度，节点C分得c $\frac{1}{3} * α$ 的重要度。最后 $P R (A)$ 要加上 $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

发表至：ml

2018-04-16

# 算法