推荐系统中协同过滤算法实现分析
博客专区 > Breath_L 的博客 > 博客详情
推荐系统中协同过滤算法实现分析
Breath_L 发表于6年前
推荐系统中协同过滤算法实现分析
  • 发表于 6年前
  • 阅读 27479
  • 收藏 50
  • 点赞 6
  • 评论 18

移动开发云端新模式探索实践 >>>   

      原创博客,欢迎转载,转载请注明:http://my.oschina.net/BreathL/blog/62519

      最近研究Mahout比较多,特别是里面协同过滤算法;于是把协同过滤算法的这个实现思路与数据流程,总结了一下,以便以后对系统做优化时,有个清晰的思路,这样才能知道该如何优化且优化后数据亦能正确。

     推荐中的协同过滤算法简单说明下:

     首先,通过分析用户的偏好行为,来挖掘出里面物品与物品、或人与人之间的关联。

     其次,通过对这些关联的关系做一定的运算,得出人与物品间喜欢程度的猜测,即推荐值。

     最后,将推荐值高的物品推送给特定的人,以完成一次推荐。

     这里只是笼统的介绍下,方便下边的理解,IBM的一篇博客对其原理讲解得浅显易懂,同时也很详细深入推荐引擎相关算法 - 协同过滤》,我这里就不细讲了。

     协同过滤算法大致可分为两类,基于物品的与基于用户的;区分很简单,根据上面的逻辑,若你挖掘的关系是物品与物品间的,就是基于物品的协同过滤算法,若你挖掘的关系是用户与用户间的,就是基于用户的协同过滤算法;由于它们实现是有所不同,所以我分开整理,先来看看基于物品的协同过滤实现,我自己画了一幅图:


基于物品的协同过滤算法流程图

     我通过数字的顺序,来标示数据变化的方向(由小到大);下面分析下每一个步骤的功能以及实现。

     首先,说明下两个大的数据源,用户偏好数据:UserID、ItemID、Preference:表示一个对一个物品的喜好程度;关系数据:ItemIDA(UserIDA)、ItemIDB(UserIDB)、Similarity:表示两个人或物品间的相似程度;接着一个用户来了,我们需要为其推荐,得拿到他的身份标示,一般是UserID,于是:

     .    查找这个用户喜欢过的物品(即偏好的产品,并查出偏好值后面会用),以及还没有喜欢过的商品,前者是推荐运算的根据,后者作为一个产生推荐的一个集合;如画的那样。

     .    这里是一个可扩展的地方(我自己理解);因为这两部分的数据的作用非常明显,修改这两个集合对后面产生的推荐结果可产生非常直观的影响,比如清洗过滤,或根据用户属性缩小集合;不仅使后面推荐效果更优,运算性能也可以大幅度提高。

     .    查找这两个集合之间的关系,这是一对多的关系:一个没有偏好过的物品与该用户所有偏好过的物品间的关系,有一个值来衡量这个关系叫相似度Similarity;这个关系怎么来的,看蓝色箭头的指向。步骤

     .    得到这个一对多的关系后,就可以计算这个物品对于这个用户的推荐值了,图中similarity_i-x表示Item_i 与 Item_x 之间的相似度,Item_x是该用户偏好过得,该用户对其偏好值记为 value_x ,相乘;Item_i 与 该用户偏好过的所有物品以此做以上运算后,得到的值取平均值 便是 Item_i的推荐值了。注:有可能Item_i 不是与所有 该用户偏好过的物品都都存在相似性,不存在的,不计算即可;另外这里方便理解介绍的都是最简单的实现;你也可以考一些复杂的数学元素,比如方差来判断离散性等。

     .    这步就简单多了,刚才对该用户没有偏好过的集合中的所有Item都计算了推荐值,这里就会得到一个list,按推荐值由大到小排序,返回前面的一个子集即可。

     。 前面已经提到,关系数据时怎么来的,也是根据用户的偏好数据;你把其看成一个矩阵,横着看过来,参考两个Item间的共同用户,以及共同用户的偏好的值的接近度;这里的可选择的相似度算法很多,不一一介绍了,前面提到的IBM博客也详细讲解了。

     基于物品的协同过滤算法分析完了,下面是基于用户的协同过滤算法,还是自己画了一幅图:

基于用户的协同过滤算法流程图


     .    同样也是查询,只是查询的对象不一样了,查询的是与该用户相似的用户,所以一来直接查了关系数据源。以及相似用户与该用户的相似度。

     .    与刚才类似,也是对数据集的一个优化,不过作用可能没那么大。(个人感觉)

     .    查询关系数据源,得到相似用户即邻居偏好过的物品;如步骤;图中由于空间小,没有把所有邻居的偏好关系都列出来,用……表示。其次还要得到该用户偏好过的物品集合。

     .    被推荐的Item集合是由该用户的所有邻居的偏好过的物品的并集,同时再去掉该用户自己偏好过的物品。作用就是得到你的相似用户喜欢的物品,而你还没喜欢过的。

     .    集合优化同基于物品的协同过滤算法的步骤

     .    也是对应类似的,依次计算被推荐集合中Item_i 的推荐值,计算的方式略有不同,Value_1_i表示邻居1对,Item_i的偏好值,乘以该用户与邻居1的相似度 Similarity1;若某个邻居对Item_i偏好过,就重复上述运算,然后取平均值;得到Item_i的推荐值。

     ⑦、. 与上一个算法的最后两部完全类似,只是步骤  你竖着看,判断两个用户相似的法子和判断两个物品相似的法子一样。

     详细的实现过程分析完了,但Mahout里面的实现时,似乎不太考虑查询的成本,并非一次全部查出,每计算个Item的推荐值查一次,你计算5000个就查5000次,若数据源都使用的是MySQL的话,我有点根儿颤,但一次全部查出再计算,肯定是个慢查询,且查询后的数据不是规则的,需要整,又添加了计算量;若各位有好的优化思路,望能分享下,先谢过。

     

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
Breath_L
粉丝 221
博文 20
码字总数 26444
评论 (18)
yunitongle
不用Hadoop的话,直接把数据导入到内存,进行计算计算推荐,其速度是OK的。不知道楼主有没有把taste用在企业级的数据上?求指点
Breath_L

引用来自“yunitongle”的评论

不用Hadoop的话,直接把数据导入到内存,进行计算计算推荐,其速度是OK的。不知道楼主有没有把taste用在企业级的数据上?求指点

你是说把原始数据和关系数据都放内存中,我试过,我不知道什么要求算是企业级数据,不过我这120万的用户偏好数据和280万的关系数据都放内存,运算很慢。
yunitongle

引用来自“Breath_L”的评论

引用来自“yunitongle”的评论

不用Hadoop的话,直接把数据导入到内存,进行计算计算推荐,其速度是OK的。不知道楼主有没有把taste用在企业级的数据上?求指点

你是说把原始数据和关系数据都放内存中,我试过,我不知道什么要求算是企业级数据,不过我这120万的用户偏好数据和280万的关系数据都放内存,运算很慢。

120万的用户偏好是指120万条的User-Item-Preference记录还是指的120万用户ID?怎么会只有280万的关系数据呢?关系数据应该是M*(M-1)/2的大小呀?如果是120万或者280万条记录,除掉关系数据的计算时间,其推荐时间应该是ms级别的呀
yunitongle
我指的企业级数据大约是100万的userID,5000万条记录级别的计算,这个可以有好的解决方法吗?
Breath_L

引用来自“yunitongle”的评论

引用来自“Breath_L”的评论

引用来自“yunitongle”的评论

不用Hadoop的话,直接把数据导入到内存,进行计算计算推荐,其速度是OK的。不知道楼主有没有把taste用在企业级的数据上?求指点

你是说把原始数据和关系数据都放内存中,我试过,我不知道什么要求算是企业级数据,不过我这120万的用户偏好数据和280万的关系数据都放内存,运算很慢。

120万的用户偏好是指120万条的User-Item-Preference记录还是指的120万用户ID?怎么会只有280万的关系数据呢?关系数据应该是M*(M-1)/2的大小呀?如果是120万或者280万条记录,除掉关系数据的计算时间,其推荐时间应该是ms级别的呀

用户偏好是User-Item-Preference记录,这个的数量和关系数据没有关系吧,我的M(产品数量)是8000,所以280万是范围内的大小,放在内存肯定是最快的,但前提条件是你内存足够大,在被占用了很多空间后,仍然有足够的空间来运行计算,并且将来数据量增大后,内存仍然够用;那我觉得放内存也OK
yunitongle

引用来自“Breath_L”的评论

引用来自“yunitongle”的评论

引用来自“Breath_L”的评论

引用来自“yunitongle”的评论

不用Hadoop的话,直接把数据导入到内存,进行计算计算推荐,其速度是OK的。不知道楼主有没有把taste用在企业级的数据上?求指点

你是说把原始数据和关系数据都放内存中,我试过,我不知道什么要求算是企业级数据,不过我这120万的用户偏好数据和280万的关系数据都放内存,运算很慢。

120万的用户偏好是指120万条的User-Item-Preference记录还是指的120万用户ID?怎么会只有280万的关系数据呢?关系数据应该是M*(M-1)/2的大小呀?如果是120万或者280万条记录,除掉关系数据的计算时间,其推荐时间应该是ms级别的呀

用户偏好是User-Item-Preference记录,这个的数量和关系数据没有关系吧,我的M(产品数量)是8000,所以280万是范围内的大小,放在内存肯定是最快的,但前提条件是你内存足够大,在被占用了很多空间后,仍然有足够的空间来运行计算,并且将来数据量增大后,内存仍然够用;那我觉得放内存也OK

嗯,关系数据是和user Number或者Item Number有关的,但是8000item的理论关系数据(假设都有关系)就会达到3200万,当user Number或者Item Number上10万的时候,这个理论关系数据就会有50亿了,这样很难放在内存里,所以大数据量的时候应该怎么办呢?非得用数据库吗?
Breath_L

引用来自“yunitongle”的评论

引用来自“Breath_L”的评论

引用来自“yunitongle”的评论

引用来自“Breath_L”的评论

引用来自“yunitongle”的评论

不用Hadoop的话,直接把数据导入到内存,进行计算计算推荐,其速度是OK的。不知道楼主有没有把taste用在企业级的数据上?求指点

你是说把原始数据和关系数据都放内存中,我试过,我不知道什么要求算是企业级数据,不过我这120万的用户偏好数据和280万的关系数据都放内存,运算很慢。

120万的用户偏好是指120万条的User-Item-Preference记录还是指的120万用户ID?怎么会只有280万的关系数据呢?关系数据应该是M*(M-1)/2的大小呀?如果是120万或者280万条记录,除掉关系数据的计算时间,其推荐时间应该是ms级别的呀

用户偏好是User-Item-Preference记录,这个的数量和关系数据没有关系吧,我的M(产品数量)是8000,所以280万是范围内的大小,放在内存肯定是最快的,但前提条件是你内存足够大,在被占用了很多空间后,仍然有足够的空间来运行计算,并且将来数据量增大后,内存仍然够用;那我觉得放内存也OK

嗯,关系数据是和user Number或者Item Number有关的,但是8000item的理论关系数据(假设都有关系)就会达到3200万,当user Number或者Item Number上10万的时候,这个理论关系数据就会有50亿了,这样很难放在内存里,所以大数据量的时候应该怎么办呢?非得用数据库吗?

都可以用,就看你的场景合适么?放数据库也可以,用NoSQL数据库也行,就看你对实时的要求了,算的程度也可以控制:http://my.oschina.net/BreathL/blog/60725
yunitongle
楼主,我真心想知道,我如果想把关系数据全本存储起来,当用户很多的时候这个数量是相当巨大的,我如果只能用MySQL进行存储的话,应该怎么办,能不能承受的住呀?
Breath_L

引用来自“yunitongle”的评论

楼主,我真心想知道,我如果想把关系数据全本存储起来,当用户很多的时候这个数量是相当巨大的,我如果只能用MySQL进行存储的话,应该怎么办,能不能承受的住呀?

一个你可以考虑分布式存储,推荐引擎的数据都比较大,另一个你可以考虑存储关系数据的子集,比如存一个用户的邻居,不用存储所有邻居,只存最相似的N即可
yunitongle

引用来自“Breath_L”的评论

引用来自“yunitongle”的评论

楼主,我真心想知道,我如果想把关系数据全本存储起来,当用户很多的时候这个数量是相当巨大的,我如果只能用MySQL进行存储的话,应该怎么办,能不能承受的住呀?

一个你可以考虑分布式存储,推荐引擎的数据都比较大,另一个你可以考虑存储关系数据的子集,比如存一个用户的邻居,不用存储所有邻居,只存最相似的N即可

嗯,看来也只能这样办了,实在是想把所有的都存储下来,一遍下一步的分析利用呀,没办法,放不下呀!
yunitongle

引用来自“Breath_L”的评论

引用来自“yunitongle”的评论

楼主,我真心想知道,我如果想把关系数据全本存储起来,当用户很多的时候这个数量是相当巨大的,我如果只能用MySQL进行存储的话,应该怎么办,能不能承受的住呀?

一个你可以考虑分布式存储,推荐引擎的数据都比较大,另一个你可以考虑存储关系数据的子集,比如存一个用户的邻居,不用存储所有邻居,只存最相似的N即可

嗯,看来也只能这样办了,实在是想把所有的都存储下来,一遍下一步的分析利用呀,没办法,放不下呀!
只是因为你

引用来自“yunitongle”的评论

楼主,我真心想知道,我如果想把关系数据全本存储起来,当用户很多的时候这个数量是相当巨大的,我如果只能用MySQL进行存储的话,应该怎么办,能不能承受的住呀?

实际上,你的数据很稀疏的,要存储的关系也不多,比如100万用户,8000个商品,没必要为每个用户推荐8000个商品,可能只要只要top10,最多就top100吧, 也就一亿。
pengkui
我也在研究taste 遇到一些问题,大家有兴趣的讨论下,我邮箱是:pengkui201208@163.com
haoranjunzi
博主您好 我特意申请了个账号来咨询您 希望不吝赐教 我想问的是 由于评分矩阵非常稀疏 所有可以在推荐前对评分矩阵通过某种方法进行填充 降低洗属性 利用slopeone就是一种方法 但是如何利用mahout中的slopeon进行填充预测 博主是否知道什么思路 以下是我的思路:
文中slopeone 是对某一个用户的未评分项目的预测 是否可以依照文中方法遍历所有用户,最后就能得到所有用户的未评分项目的预测 这样就将评分矩阵填充 但是这个评分矩阵用什么对象可以取得 similarity?

还有个问题 我是一名研究生 需要对推荐算法进行研究并写论文 但是我现在比较迷茫的是我该利用什么平台进行仿真,mahout还是其他?,我肯定要对算法进行改进 我该怎么mahout里改进算法呢?
haoranjunzi
不好意思 博主 我发错地方了 我应该在您的“Apache Mahout中推荐算法Slope one源码分析”发表
babyxiayuan
请问下博主,文章的框图是用什么软件? 谢谢
babyxiayuan
请问下博主,文章的框图是用什么软件? 谢谢
仙人指路有人用了

引用来自“babyxiayuan”的评论

请问下博主,文章的框图是用什么软件? 谢谢
同问
×
Breath_L
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: