• 为了保证你在浏览本网站时有着更好的体验,建议使用类似Chrome、Firefox之类的浏览器~~
    • 如果你喜欢本站的内容何不Ctrl+D收藏一下呢,与大家一起分享各种编程知识~
    • 本网站研究机器学习、计算机视觉、模式识别~当然不局限于此,生命在于折腾,何不年轻时多折腾一下

PersonalRank算法以及实现

ml admin 3个月前 (04-16) 268次浏览 0个评论 扫描二维码

先举个例子

上面的二部图表示 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


Deeplearn, 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明PersonalRank 算法以及实现
喜欢 (0)
admin
关于作者:

您必须 登录 才能发表评论!