PersonalRank算法以及实现

3,479次阅读
一条评论

PersonalRank算法以及实现

先举个例子

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 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

admin
版权声明:本站原创文章,由admin2018-04-16发表,共计4002字。
转载提示:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(一条评论)
薰衣草苗圃 评论达人 LV.1
2018-10-29 15:50:17 回复

数据集请问可以传出来么?