`
zhangxiong0301
  • 浏览: 363852 次
社区版块
存档分类
最新评论

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

 
阅读更多

今天我们讲一个下怎么使用随机游走算法PersonalRank实现基于图的推荐。

在推荐系统中,用户行为数据可以表示成图的形式,具体来说是二部图。用户的行为数据集由一个个(u,i)二元组组成,表示为用户u对物品i产生过行为。本文中我们认为用户对他产生过行为的物品的兴趣度是一样的,也就是我们只考虑“感兴趣”OR“不感兴趣”。假设有下图所示的行为数据集。


其中users集U={A, B, C},items集I = {a,b,c,d}。则用户物品的二部图如下所示:

我们用G(V, E)来表示这个图,则顶点集V=U∪I,图中的边则是由数据集中的二元组确定。二元组(u, i)表示u对i有过行为,则在图中表现为有边相连,即e(u,i)。【注意】,本文中我们不考虑各边的权重(即u对i的兴趣度),权重都默认为1。感兴趣即有边相连,不感兴趣则没有边相连。

那有了二部图之后我们要对u进行推荐物品,就转化为计算用户顶点u和与所有物品顶点之间的相关性,然后取与用户没有直接边相连的物品,按照相关性的高低生成推荐列表。说白了,这是一个图上的排名问题,我们最容易想到的就是Google的pageRank算法。

PageRank是Larry Page 和 Sergey Brin设计的用来衡量特定网页相对于搜索引擎中其他网页的重要性的算法,其计算结果作为google搜索结果中网页排名的重要指标。网页之间通过超链接相互连接,互联网上不计其数的网页就构成了一张超大的图。PageRank假设用户从所有网页中随机选择一个网页进行浏览,然后通过超链接在网页直接不断跳转。到达每个网页后,用户有两种选择:到此结束或者继续选择一个链接浏览。算法令用户继续浏览的概率为d,用户以相等的概率在当前页面的所有超链接中随机选择一个继续浏览。这是一个随机游走的过程。当经过很多次这样的游走之后,每个网页被访问用户访问到的概率就会收敛到一个稳定值。这个概率就是网页的重要性指标,被用于网页排名。算法迭代关系式如下所示:


上式中PR(i)是网页i的访问概率(也就是重要度),d是用户继续访问网页的概率,N是网页总数。in(i)表示指向网页i的网页集合,out(j)表示网页j指向的网页集合。

用user节点和item节点替换上面的网页节点就可以计算出每个user,每个item在全局的重要性,给出全局的排名,显然这并不是我们想要的,我们需要计算的是物品节点相对于某一个用户节点u的相关性。怎么做呢?Standford的Haveliwala于2002年在他《Topic-sensitive pagerank》一文中提出了PersonalRank算法,该算法能够为用户个性化的对所有物品进行排序。它的迭代公式如下:


我们发现PersonalRank跟PageRank的区别只是用替换了1/N,也就是说从不同点开始的概率不同。u表示我们推荐的目标用户,这样使用上式计算的就是所有顶点相对于顶点u的相关度。

与PageRank随机选择一个点开始游走(也就是说从每个点开始的概率都是相同的)不同,如果我们要计算所有节点相对于用户u的相关度,则PersonalRank从用户u对应的节点开始游走,每到一个节点都以1-d的概率停止游走并从u重新开始,或者以d的概率继续游走,从当前节点指向的节点中按照均匀分布随机选择一个节点往下游走。这样经过很多轮游走之后,每个顶点被访问到的概率也会收敛趋于稳定,这个时候我们就可以用概率来进行排名了。

在执行算法之前,我们需要初始化每个节点的初始概率值。如果我们对用户u进行推荐,则令u对应的节点的初始访问概率为1,其他节点的初始访问概率为0,然后再使用迭代公式计算。而对于pageRank来说,由于每个节点的初始访问概率相同,所以所有节点的初始访问概率都是1/N (N是节点总数)。

我自己用Python实现了一下PersonalRank:(可执行,感兴趣的童鞋可通过附件下载源码文件,若有错误恳请指正^_^)

 

[python] view plaincopy
 
 
  1. #coding=utf-8  
  2. __author__ = 'Harry Huang'  
  3.   
  4.   
  5. def PersonalRank(G, alpha, root, max_step):  
  6.     rank = dict()  
  7.     rank = {x:0 for x in G.keys()}  
  8.     rank[root] = 1  
  9.     #开始迭代  
  10.     for k in range(max_step):  
  11.         tmp = {x:0 for x in G.keys()}  
  12.         #取节点i和它的出边尾节点集合ri  
  13.         for i, ri in G.items():  
  14.             #取节点i的出边的尾节点j以及边E(i,j)的权重wij, 边的权重都为1,在这不起实际作用  
  15.             for j, wij in ri.items():  
  16.                 #i是j的其中一条入边的首节点,因此需要遍历图找到j的入边的首节点,  
  17.                 #这个遍历过程就是此处的2层for循环,一次遍历就是一次游走  
  18.                 tmp[j] += alpha * rank[i] / (1.0 * len(ri))  
  19.         #我们每次游走都是从root节点出发,因此root节点的权重需要加上(1 - alpha)  
  20.         #在《推荐系统实践》上,作者把这一句放在for j, wij in ri.items()这个循环下,我认为是有问题。  
  21.         tmp[root] += (1 - alpha)  
  22.         rank = tmp  
  23.   
  24.         #输出每次迭代后各个节点的权重  
  25.         print 'iter: ' + str(k) + "\t",  
  26.         for key, value in rank.items():  
  27.             print "%s:%.3f, \t"%(key, value),  
  28.         print  
  29.   
  30.     return rank  
  31.   
  32.   
  33. if __name__ == '__main__' :  
  34.     G = {'A' : {'a' : 1'c' : 1},  
  35.          'B' : {'a' : 1'b' : 1'c':1'd':1},  
  36.          'C' : {'c' : 1'd' : 1},  
  37.          'a' : {'A' : 1'B' : 1},  
  38.          'b' : {'B' : 1},  
  39.          'c' : {'A' : 1'B' : 1'C':1},  
  40.          'd' : {'B' : 1'C' : 1}}  
  41.   
  42.     PersonalRank(G, 0.85'A'100)  


数据集使用的本文一开始讲的那个,最终各个节点的概率结果如下所示:

 

 


上面的代码是对本文一开始描述的数据集中的用户A进行推荐。上图给出了不同迭代次数后各节点的概率值。发现46次迭代之后,所有节点的概率值全都收敛。在这个例子中,A用户没有产生过行为的物品是b和d,相对于A的访问概率分别是0.039,0.076,d的访问概率显然要大于b,所有给A用户的推荐列表为{d,b}。

分享到:
评论

相关推荐

    基于随机游走的PersonalRank算法

    **PersonalRank算法**是一种基于图模型的推荐算法,它借鉴了PageRank算法的思想,通过对用户-物品交互数据构建图模型,利用随机游走的方式来评估用户对物品的兴趣度。 ##### 图模型与二分图 在基于图的推荐系统中...

    基于社交网络推荐算法

    PersonalRank算法是一种常用的基于随机游走的方法,但它的计算成本较高,可以通过矩阵运算等方式来优化性能。 综上所述,基于社交网络的推荐算法不仅能够有效利用社交网络的数据来提升推荐质量,还能够在一定程度上...

    HugeGraph图数据库算法应用实践.pdf

    PersonalRank算法是一种基于随机游走的推荐算法,用于推荐用户可能喜欢的商品或服务。最短路径算法是一种常用的图算法,用于计算两个实体之间的最短路径。环路检测算法是一种常用的图算法,用于检测图形数据中的环路...

    山东大学软件学院数据科学导论2018-2019试题回忆版

    PersonalRank是一种基于图的个性化推荐算法,结合用户的偏好信息和物品之间的关联性来进行推荐。 **实现步骤**: 1. **构建商品图**:将用户和商品表示为图中的节点,用户对商品的评分或者行为作为边的权重。 2. *...

    基于ARM架构服务器部署docker-compose

    基于arm64版本的docker-compose文件

    附件3-4:台区智能融合终端全性能试验增值税发票开具确认单.docx

    台区终端电科院送检文档

    埃夫特机器人Ethernet IP 通讯配置步骤

    埃夫特机器人Ethernet IP 通讯配置步骤

    rv320e机器人重型关节行星摆线减速传动装置研发.rar

    rv320e机器人重型关节行星摆线减速传动装置研发

    气缸驱动爬杆机器人的设计().zip

    气缸驱动爬杆机器人的设计().zip

    软件工程中期答辩1234567

    56tgyhujikolp[

    基于OpenCV的数字身份验证系统:人脸检测、训练与识别的Python实现

    内容概要:本文档提供了基于OpenCV的数字身份验证系统的Python代码示例,涵盖人脸检测、训练和识别三个主要功能模块。首先,通过调用OpenCV的CascadeClassifier加载预训练模型,实现人脸检测并采集多张人脸图像用于后续训练。接着,利用LBPH(局部二值模式直方图)算法对面部特征进行训练,生成训练数据集。最后,在实际应用中,系统能够实时捕获视频流,对比已有的人脸数据库完成身份验证。此外,还介绍了必要的环境配置如依赖库安装、文件路径设置以及摄像头兼容性的处理。 适合人群:对计算机视觉感兴趣的研发人员,尤其是希望深入了解OpenCV库及其在人脸识别领域的应用者。 使用场景及目标:适用于构建安全认证系统的企业或机构,旨在提高出入管理的安全性和效率。具体应用场景包括但不限于门禁控制系统、考勤打卡机等。 其他说明:文中提供的代码片段仅为基本框架,可根据实际需求调整参数优化性能。同时提醒开发者注意隐私保护法规,合法合规地收集和使用个人生物识别信息。

    Java并发编程面试题详解:123道经典题目解析与实战技巧

    内容概要:本文档详细介绍了Java并发编程的核心知识点,涵盖基础知识、并发理论、线程池、并发容器、并发队列及并发工具类等方面。主要内容包括但不限于:多线程应用场景及其优劣、线程与进程的区别、线程同步方法、线程池的工作原理及配置、常见并发容器的特点及使用场景、并发队列的分类及常用队列介绍、以及常用的并发工具类。文档旨在帮助开发者深入理解和掌握Java并发编程的关键技术和最佳实践。 适合人群:具备一定Java编程经验的研发人员,尤其是希望深入了解并发编程机制、提高多线程应用性能的中级及以上水平的Java开发者。 使用场景及目标:①帮助开发者理解并发编程的基本概念和技术细节;②指导开发者在实际项目中合理运用多线程和并发工具,提升应用程序的性能和可靠性;③为准备Java技术面试的候选人提供全面的知识参考。 其他说明:文档内容详尽,适合用作深度学习资料或面试复习指南。建议读者结合实际编码练习,逐步掌握并发编程技巧。文中提到的多种并发工具类和容器,均附有具体的应用场景和注意事项,有助于读者更好地应用于实际工作中。

    个人健康与健身追踪数据集,包含了日常步数统计、睡眠时长、活跃分钟数以及消耗的卡路里,适用于数据分析、机器学习

    这个数据集包含了日常步数统计、睡眠时长、活跃分钟数以及消耗的卡路里,是个人健康与健身追踪的一部分。 该数据集非常适合用于以下实践: 数据清洗:现实世界中的数据往往包含缺失值、异常值或不一致之处。例如,某些天的步数可能缺失,或者存在不切实际的数值(如10,000小时的睡眠或负数的卡路里消耗)。通过处理这些问题,可以学习如何清理和准备数据进行分析。 探索性分析(发现日常习惯中的模式):可以通过分析找出日常生活中的模式和趋势,比如一周中哪一天人们通常走得最多,或是睡眠时间与活跃程度之间的关系等。 构建可视化图表(步数趋势、睡眠与活动对比图):将数据转换成易于理解的图形形式,有助于更直观地看出数据的趋势和关联。例如,绘制步数随时间变化的趋势图,或是比较睡眠时间和活动量之间的关系图。 数据叙事(将个人风格的追踪转化为可操作的见解):通过讲述故事的方式,把从数据中得到的洞察变成具体的行动建议。例如,根据某人特定时间段内的活动水平和睡眠质量,提供改善健康状况的具体建议。

    《基于YOLOv8的港口船舶靠泊角度偏差预警系统》(包含源码、可视化界面、完整数据集、部署教程)简单部署即可运行。功能完善、操作简单,适合毕设或课程设计.zip

    资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。

    nginx 访问访问日志按天切割 shell脚本

    nginx

    《基于YOLOv8的核废料运输容器密封性检测系统》(包含源码、可视化界面、完整数据集、部署教程)简单部署即可运行。功能完善、操作简单,适合毕设或课程设计.zip

    资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。

    《基于YOLOv8的农业无人机播种深度监测系统》(包含源码、可视化界面、完整数据集、部署教程)简单部署即可运行。功能完善、操作简单,适合毕设或课程设计.zip

    资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。

    uniapp知识付费(流量主)demo

    模拟知识付费小程序,可流量主运营模式

    java高并发之分片上传

    什么是普通上传 调用接口一次性完成一个文件的上传。 普通上传2个缺点 文件无法续传,比如上传了一个比较大的文件,中间突然断掉了,需要重来 大文件上传太慢 解决方案 分片上传

    英二2010-2021阅读理解 Part A 题干单词(补).pdf

    英二2010-2021阅读理解 Part A 题干单词(补).pdf

Global site tag (gtag.js) - Google Analytics