推荐算法图推荐-基于随机游走的personalrank算法实现

推荐算法图推荐

基于图的模型(graph-based model)是推荐系统中的重要内容。其实,很多研究人员把基于邻域的模型也称为基于图的模型,因为可以把基于邻域的模型看做基于图的模型的简单形式

在研究基于图的模型之前,首先需要将用户的行为数据,表示成图的形式,下面我们讨论的用户行为数据是用二元数组组成的,其中每个二元组(u,i)表示用户u对物品i的产生过行为,这种数据很容易用一个二分图表示

令G(V,E)表示用户物品二分图,其中

由用户顶点集合

和物品顶点集合

组成。对于数据集中每一个二元组(u, i),图中都有一套对应的边

,其中是用户u对应的顶点

, 是物品i对应的顶点。下图是一个简单的用户物品二分图模型,其中圆形节点代表用户,方形节点代表物品,圆形节点和方形节点之间的边代表用户对物品的行为。比如图中用户节点A和物品节点a、b、d相连,说明用户A对物品a、b、d产生过行为。

原理展示

将用户的行为数据表示为二分图后,接下来的就是基于二分图为用户进行推荐,那么给用户u推荐物品就可以转化为度量用户顶点Vu和Vu没有直接边相连的顶点在图上的相关性,相关性越高的物品在推荐列表上的权重九越高,推荐位置就越靠前。 那么如何评价两个顶点的相关性?一般取决于三个因素

  • 1:两个顶点之间的路径数
  • 2:两个顶点之间路径的长度
  • 3:两个顶点之间的路径经过的顶点

而相关性较高的一对顶点一般具有如下特征:

  • 1:两个顶点之间有很多路径相连
  • 2:连接两个顶点之间的路径长度都比较短
  • 3:连接两个顶点之间的路径不会经过出度比较大的顶点

举一个简单的例子,如图2-19所示,用户A和物品c、e没有边相连,但是用户A和物品c有1条长度为3的路径相连,用户A和物品e有2条长度为3的路径相连。那么,顶点A与e之间的相关性要高于顶点A与c,因而物品e在用户A的推荐列表中应该排在物品c之前,因为顶点A与e之间有两条路径——(A, b, C, e)和(A, d, D, e)。其中,(A, b, C, e)路径经过的顶点的出度为(3, 2, 2,2),而(A, d, D, e)路径经过的顶点的出度为(3, 2, 3, 2)。因此,(A, d, D, e)经过了一个出度比较大的顶点D,所以(A, d, D, e)对顶点A与e之间相关性的贡献要小于(A, b, C, e)。

下面介绍一种基于随机游走的PersonalRank算法(和PangRank算法相似,pageRank算法参考,直通车1,textRank直通车2直通车3) 假设要给用户u进行个性化推荐,可以从用户u对应的节点Vu开始在用户物品二分图上进行随机游走。游走到任何一个节点时,首先按照概率α决定是继续游走,还是停止这次游走并从Vu节点开始重新游走。如果决定继续游走,那么就从当前节点指向的节点中按照均匀分布随机选择一个节点作为游走下次经过的节点。这样,经过很多次随机游走后,每个物品节点被访问到的概率会收敛到一个数。最终的推荐列表中物品的权重就是物品节点的访问概率。 如果将上面的描述表示成公式,可以得到如下公式:

alpha表示随机游走的概率 PR(v’)表示访问v’的概率 out(v’)表示v’指向的顶点集合

案例代码

#-*-coding:utf-8-*-
'''''
Created on 2018-4

'''

'''''
G:二分图   alpha:随机游走的概率   root:游走的初始节点     max_step;最大走动步数
'''
import time
def PersonalRank(G, alpha, root, max_step):
    rank = dict()
    rank = {x:0 for x in G.keys()}
    rank[root] = 1
    #开始迭代
    begin=time.time()
    for k in range(max_step):
        tmp = {x:0 for x in G.keys()}
        #取节点i和它的出边尾节点集合ri
        for i, ri in G.items():  #i是顶点。ri是与其相连的顶点极其边的权重
            #取节点i的出边的尾节点j以及边E(i,j)的权重wij, 边的权重都为1,在这不起实际作用
            for j, wij in ri.items():   #j是i的连接顶点,wij是权重
                #i是j的其中一条入边的首节点,因此需要遍历图找到j的入边的首节点,
                #这个遍历过程就是此处的2层for循环,一次遍历就是一次游走
                tmp[j] += alpha * rank[i] / (1.0 * len(ri))
        #我们每次游走都是从root节点出发,因此root节点的权重需要加上(1 - alpha)
        #在《推荐系统实践》上,作者把这一句放在for j, wij in ri.items()这个循环下,我认为是有问题。
            tmp[root] += (1 - alpha)
            rank = tmp
            end=time.time()
            print ('use_time',end-begin)
            # 输出方法一
            lst=sorted(rank.items(),key=lambda x:x[1],reverse=True)
            for ele in lst:
                 print ("%s:%.3f, \t" %(ele[0],ele[1]))
            # 输出方法二
            #输出每次迭代后各个节点的权重
            # print ('iter:  ' + str(k) + "\t",)
            # for key, value in rank.items():
            #     print ("%s:%.3f, \t"%(key, value),)

    return rank

'''''
主函数,G表示二分图,‘A’表示节点,后边对应的字典的key是连接的顶点,value表示边的权重
'''
if __name__ == '__main__':
    G = {'A' : {'a' : 1, 'c' : 1},
         'B' : {'a' : 1, 'b' : 1, 'c':1, 'd':1},
         'C' : {'c' : 1, 'd' : 1},
         'a' : {'A' : 1, 'B' : 1},
         'b' : {'B' : 1},
         'c' : {'A' : 1, 'B' : 1, 'C':1},
         'd' : {'B' : 1, 'C' : 1}}

    PersonalRank(G, 0.85, 'A', 100)

'''''
主函数,G表示二分图,‘A’表示节点,后边对应的字典的key是连接的顶点,value表示边的权重
'''
if __name__ == '__main__':
    G = {'A' : {'a' : 1, 'c' : 1},
         'B' : {'a' : 1, 'b' : 1, 'c':1, 'd':1},
         'C' : {'c' : 1, 'd' : 1},
         'a' : {'A' : 1, 'B' : 1},
         'b' : {'B' : 1},
         'c' : {'A' : 1, 'B' : 1, 'C':1},
         'd' : {'B' : 1, 'C' : 1}}

    PersonalRank(G, 0.85, 'A', 100)

结果说明:

与A相关度最高的依次是 A(0.269),c(0.190),B(0.185),a(0.154),C(0.086),d(0.076),b(0.039),去除A已经连接的a,c,剩下的推荐依次为B,a,C,d,b   其中大写的代表用户小写的代表item

问题说明

虽然PersonalRank算法可以通过随机游走进行比较好的理论解释,但该算法在时间复杂度上有明显的缺点。因为在为每个用户进行推荐时,都需要在整个用户物品二分图上进行迭代,直到整个图上的每个顶点的PR值收敛。这一过程的时间复杂度非常高,不仅无法在线提供实时推荐,甚至离线生成推荐结果也很耗时。 为了解决PersonalRank每次都需要在全图迭代并因此造成时间复杂度很高的问题,这里给出两种解决方案。第一种很容易想到,就是减少迭代次数,在收敛之前就停止。这样会影响最终的精度,但一般来说影响不会特别大。另一种方法就是从矩阵论出发,重新设计算法。 对矩阵运算比较熟悉的读者可以轻松将PersonalRank转化为矩阵的形式。令M为用户物品二分图的转移概率矩阵,即:

那么,迭代公式可以转化为:

对矩阵论稍微熟悉的读者都可以解出上面的方程,得到:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏PPV课数据科学社区

【大数据问答】SPSS是如何做到发现数据质量问题,例如,如何发现缺失值?

SPSS是如何做到发现数据质量问题,例如,如何发现缺失值? (1)系统缺失值、空白值 每一个变量均有可能出现系统缺失或者空白,当数据量巨大时我们根本无法用眼睛...

4274
来自专栏深度学习计算机视觉

贪心算法+回溯算法

贪心算法 先来比较一下贪心算法和动态规划 贪心算法是指在对问题求解时,总是做出在当前看来是最好的选择,不考虑整体,只考虑局部最优,所以它不一定能得到最优解; ...

4209
来自专栏Vamei实验室

概率论01 计数

概率 概率论研究随机事件。它源于赌徒的研究。赌博中有许多随机事件,比如投掷一个骰子,是否只凭运气呢? 赌徒逐渐发现随机事件的规律。投掷两个骰子是常见的赌博游戏。...

2346
来自专栏数据结构与算法

2853 方格游戏(三维棋盘)

 时间限制: 1 s  空间限制: 128000 KB  题目等级 : 钻石 Diamond 题解  查看运行结果 题目描述 Description 菜菜看到了...

3606
来自专栏机器之心

EMNLP 2018 | 结合通用和专用NMT的优势,CMU为NMT引入「语境参数生成器」

神经机器翻译(NMT)无需单独训练或调整系统的任何部分就可以直接建模源语言到目标语言的映射。这使得 NMT 快速发展,并在许多大规模环境中成功应用 (Wu et...

1381
来自专栏磐创AI技术团队的专栏

【Github 4K星】BAT头条滴滴小米等笔试面经+深度学习/算法/NLP资源汇总!

最近,在GitHub上有位id为imhuay的热心人带头建立了一个关于国内知名互联网企业笔试和面试经验的资源库,光从名称上就能看出其内容有多丰富:《2018/2...

2413
来自专栏AI派

【Github 5K星】BAT头条滴滴小米等笔试面经+深度学习/算法/NLP资源汇总!

最近,在GitHub上有位id为imhuay的热心人带头建立了一个关于国内知名互联网企业笔试和面试经验的资源库,光从名称上就能看出其内容有多丰富:《2018/2...

1241
来自专栏新智元

【邓侃】哈佛大学机器翻译开源项目 OpenNMT的工作原理

【新智元导读】 2016年12月20日,哈佛大学自然语言处理研究组,宣布开源了他们研发的机器翻译系统 OpenNMT ,并声称该系统的质量已经达到商用水准。本文...

5315
来自专栏生信技能树

比较不同的对单细胞转录组数据聚类的方法

背景介绍 聚类之前必须要对表达矩阵进行normalization,而且要去除一些批次效应等外部因素。通过对表达矩阵的聚类,可以把细胞群体分成不同的状态,解释为什...

88412
来自专栏数说工作室

机器学习/深度学习代码速查:6大工具库 &27种神经网络图览

Kailash Ahirwar,Mate Lab 联合创始人,Github的一位资深作者,也是一位活雷锋,近日在其Github个人主页上发表了一个机器学习/深度...

5135

扫码关注云+社区

领取腾讯云代金券