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

需要将用户行为数据表示成图的形式，二元组 (u, i) 表示用户 u 对物品 i 产生过行为,这种数据集很容易用一个二分图表示


基于图的推荐算法

将个性化推荐算法放到二分图模型上，那么给用户 u 推荐物品的任务就可以转化为度量用户顶点v u 和与 v u 没有边直接相连的物品节点在图上的相关性,相关性越高的物品在推荐列表中的权重就越高

度量两个顶点之间相关性的方法很多，但一般来说图中顶点的相关性主要取决于3个因素

两个顶点之间的路径数

两个顶点之间路径的长度

两个顶点之间的路径经过的顶点


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

两个顶点之间有很多路径相连

连接两个顶点之间的路径长度都比较短

连接两个顶点之间的路径不会经过出度比较大的顶点


基于随机游走的PersonalRank算法

从用户 u 对应的节点 v u 开始在用户物品二分图上进行随机游走。游走到任何一个节点时，首先按照概率 α 决定是继续游走，还是停止这次游走并从 v u 节点开始重新游走。如果决定继续游走，那么就从当前节点指向的节点中按照均匀分布随机选择一个节点作为游走下次经过的节点。这样，经过很多次随机游走后，每个物品节点被访问到的概率会收敛到一个数。

推荐列表中物品的权重就是物品节点的访问概率

该算法在时间复杂度上有明显的缺点

因为在为每个用户进行推荐时，都需要在整个用户物品二分图上进行迭代，直到整个图上的每个顶点的 PR 值收敛。这一过程的时间复杂度非常高，不仅无法在线提供实时推荐，甚至离线生成推荐结果也很耗时

两种解决方案
1.减少迭代次数，在收敛之前就停止,会影响最终的精度，但一般来说影响不会特别大
2.从矩阵论出发，重新设计算法


代码分析

def PersonalRank(G, alpha, root, max_step):
    
//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}}
    alpha:0.85
    max_step:100
    root:'A'  起点
    //

    rank = dict()
    rank = {x:0 for x in G.keys()}
    
//rank:存放每个节点访问概率
     {'A': 0, 'B': 0, 'C': 0, 'a': 0, 'b': 0, 'c': 0, 'd': 0}
    //

    rank[root] = 1     起点必然访问
    
//rank:
     {'A': 1, ...}
    //

    #start iteration
    for k in range(max_step):
        
//k:0
	//

        tmp = {x:0 for x in G.keys()}
	
//tmp:{'A': 0, 'B': 0, 'C': 0, 'a': 0, 'b': 0, 'c': 0, 'd': 0} 存放每个节点访问概率
	//

        #get node i and i's out edges set ri
        for i, ri in G.items():
	    
//i:'A' 连线起点
	      ri:{'a': 1, 'c': 1}  连线终点和权重
	    //

            #get node i's edges and its weight
            for j, wij in ri.items():
	        
//j:'a',连线终点
		  wij:1
		//

                tmp[j] += alpha * rank[i] / (1.0*len(ri))
		
//tmp:迭代节点j随机游走到的概率
		  {'A': 0, 'B': 0, 'C': 0, 'a': 0.425, 'b': 0, 'c': 0, 'd': 0}
		//

        
//tmp:
	{'A': 0.0, 'B': 0.0, 'C': 0.0, 'a': 0.425, 'b': 0.0, 'c': 0.425, 'd': 0.0}
	//

        tmp[root] += (1 - alpha)
        rank = tmp
        
//rank:
          {'A': 0.15000000000000002, 'B': 0.0, 'C': 0.0, 'a': 0.425, 'b': 0.0, 'c': 0.425, 'd': 0.0}
	//

        print ('iter: ' + str(k) + "\t"),
        for key, value in rank.items():
	    
//key:'A'
	     value:0.15000000000000002
	    //

            print ("%s:%.3f, \t"%(key, value)),
        print

    return rank
    
//{'A': 0.26930214879395137, 'B': 0.18500264470071592, 'C': 0.08623578723788726, 'a': 0.153766456647525, 'b': 0.0393130527044989, 'c': 0.19041665692922385, 'd': 0.07596325298619776}
    //

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}}
 rank =PersonalRank(G, 0.85, 'A', 100)

 items_dict = {'a': 0, 'b': 0, 'c': 0, 'd': 0}
   
//items_dict:要推荐的用户的物品记录
   //

    for k in items_dict.keys():
        
//k:'a'
	//

        if k in rank:
            items_dict[k] = rank[k]
	    
//赋值记录
	    //

        # sort:
    result = sorted(items_dict.items(), key=lambda d: d[1], reverse=True)
    
//排序
    //

    "\nThe result:"
    for k in result:
        print
        "%s:%.3f \t" % (k[0], k[1]),
    print