专栏首页null的专栏推荐算法——基于图的推荐算法PersonalRank算法

推荐算法——基于图的推荐算法PersonalRank算法

一、推荐的概述

在推荐系统中,通常是要向用户推荐商品,如在购物网站中,需要根据用户的历史购买行为,向用户推荐一些实际的商品;如在视频网站中,推荐的则是不同的视频;如在社交网站中,推荐的可能是用户等等,无论是真实的商品,还是视频,再或者是用户,都可以假设成一种物品,如下图所示:

(图片来自参考文献)

在上图中,左侧的A,B,C表示的是三个用户,右侧的a,b,c,d表示的是四个商品,中间的连线表示用户与商品之间有过行为,或者是购买或者是打分,推荐的目的是从商品列表中向指定的用户推荐用户未行为过的商品。

推荐的算法有很多,包括协同过滤(基于用户的协同过滤和基于物品的协同过滤)以及其他的一些基于模型的推荐算法。

二、基于图的推荐算法PersonalRank算法

1、PersonalRank算法简介

在协同过滤中,主要是将上述的用户和商品之间的关系表示成一个二维的矩阵(用户商品矩阵)。

而在基于图的推荐算法中,将上述的关系表示成二部图的形式,为用户A推荐商品,实际上就是计算用户A对所有商品的感兴趣程度。

PersonalRank算法对通过连接的边为每个节点打分,具体来讲,在PersonalRank算法中,不区分用户和商品,因此上述的计算用户A对所有的商品的感兴趣的程度就变成了对用户A计算各个节点B,C,a,b,c,d的重要程度。

PersonalRank算法的具体过程如下(对用户A来说):

  • 初始化: PR(A)=1,PR(B)=0,⋯,PR(d)=0 PR\left ( A \right )=1,PR\left ( B \right )=0,\cdots ,PR\left ( d \right )=0
  • 开始在图上游走,每次选择PR值不为00的节点开始,沿着边往前的概率为α\alpha ,停在当前点的概率为1−α1-\alpha :
    • 首先从A开始,从A到a和c的概率为0.50.5,则此时a和c的PR值为:PR(a)=PR(c)=α×PR(A)×0.5PR\left ( a \right )=PR\left ( c \right )=\alpha \times PR\left ( A \right )\times 0.5,A的PR值变成了1−α1-\alpha
    • 此时PR值不为0的节点为A,a,c,则此时从这三点出发,继续上述的过程,直到收敛为止。

由此可以得出以下的PR计算方法:

PR(v)=⎧⎩⎨⎪⎪α×∑v′∈in(v)PR(v′)|out(v′)|(1−α)+α×∑v′∈in(v)PR(v′)|out(v′)| if vvu if v=vu

PR\left ( v \right )=\begin{cases} \alpha \times \sum _{{v}'\in in\left ( v \right )} \frac{PR\left ( {v}' \right )}{\left | out\left ( {v}' \right ) \right |}& \text{ if } v\neq v_u \\ \left ( 1-\alpha \right )+\alpha \times \sum _{{v}'\in in\left ( v \right )} \frac{PR\left ( {v}' \right )}{\left | out\left ( {v}' \right ) \right |} & \text{ if } v= v_u \end{cases}

2、实验过程

2.1、实验结果:

根据最终的商品的打分,我们对其进行排序,由于A用户对商品c和商品a有过行为,因此根据打分,为用户A推荐商品d。

2.2、实验代码

#coding=utf-8
def PersonalRank(G, alpha, root, max_step):
    rank = dict()  
    for x in G.keys():
        rank[x] = 0

    rank[root] = 1  

    for k in range(max_step):
        print str(k)
        tmp = dict()
            for x in G.keys():
                    tmp[x] = 0
            for i, ri in G.items():  
                    for j, wij in ri.items():
                if j not in tmp:
                    tmp[j] = 0
                        tmp[j] += alpha * rank[i] / (1.0 * len(ri))  
                if j == root:
                        tmp[j] += (1 - alpha)
        # coverage
        check = []
        for k in tmp.keys():
            check.append(tmp[k] - rank[k])

        if sum(check) <= 0.0001:
            break

            rank = tmp
        for n in rank.keys():
                    print "%s:%.3f \t"%(n, rank[n]),
        print
    return rank  


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}} 
    items_dict = {'a':0,'b':0,'c':0,'d':0}

        rank = PersonalRank(G, 0.85, 'A', 50)
    for k in items_dict.keys():
        if k in rank:
            items_dict[k] = rank[k]
    #sort:
    result = sorted(items_dict.items(), key = lambda d: d[1], reverse=True)
    print "\nThe result:"
    for k in result:
        print "%s:%.3f \t"%(k[0], k[1]),
    print

参考文献

  • 《推荐系统实践》

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 自然语言中的重要概念——熵(Entropy)

    熵是热力学中的一个重要的概念,最早是由香农(Claude Shannon)将熵应用于信息的度量。

    zhaozhiyong
  • 利用Theano理解深度学习——Convolutional Neural Networks

    注:本系列是基于参考文献中的内容,并对其进行整理,注释形成的一系列关于深度学习的基本理论与实践的材料,基本内容与参考文献保持一致,并对这个专题起名为“利用The...

    zhaozhiyong
  • 优化算法——遗传算法

    遗传算法是我进入研究生阶段接触的第一个智能算法,从刚开始接触,到后来具体去研究,再到后来利用遗传算法完成了水利水电的程序设计比赛,整个过程中对遗传算法有了更深刻...

    zhaozhiyong
  • Flash/Flex学习笔记(41):碰撞检测

    碰撞检测基本上可能分为二类:对象与对象的碰撞检测、对象与点的碰撞检测 为了方便测试,先写一个box类(生成一个小矩形) package { import ...

    菩提树下的杨过
  • win10下MarkdownPad 2的html渲染出错解决

    今天下载了MarkdownPad 2,打开后发现预览效果出错了,本来以为自己下载了破解版的缘故导致软件不稳定,后来查找了网上,发现这是一个普遍的问题,根据软件的...

    代码咖啡
  • Python爬虫爬取网易云音乐全部评论

    . 2.接下来就打开控制台找我们要的评论藏在哪里就好了。 我们在http://music.163.com/weapi/v1/resource...

    Awesome_Tang
  • Leetcode 13 Roman to Integer

    Given a roman numeral, convert it to an integer. Input is guaranteed to be wit...

    triplebee
  • 8086汇编语言——处理字符串

    zy010101
  • 推荐一些适合新手练手的Python项目

    PHP自然是不会错过这个噱头、C/C++作为元老级的编程语言一直屹立不倒、Java依旧是市场上的香饽饽、当然还有JavaScript、C#、Ruby以及Obje...

    IT派
  • 运维平台的建设思考-元数据管理(四)(r8笔记第16天)

    对于服务器的一些信息,如果数据量大了之后总是感觉力不从心,需要了解,但是感觉得到的这些信息不够清晰明了。 比如我们得到一台服务器,需要知道最基本的硬件配置,内存...

    jeanron100

扫码关注云+社区

领取腾讯云代金券