相关文章

推荐算法深入浅出之协同过滤

 |   

相关推荐是一种常见的推荐场景,比如资讯流推荐中详情页下方的推荐列表(基于物品的相关推荐),微信看一看(基于用户的相关推荐)等。 在这个场景中必然绕不开一个算法:协同过滤算法。

介绍

协同过滤算法并不是单独的一个算法,是一类算法。它通过分析用户或者事物之间的相似性(“协同”),来预测用户可能感兴趣的内容并将此内容推荐给用户。

这里的相似性可以是人口特征(性别、年龄、居住地等)的相似性,也可以是历史浏览内容的相似性(比如都关注过和中餐相关的内容),还可以是个人通过一定机制给予某个事物的回应(比如一些教学网站会让用户对授课人进行评分)。它的重点是协同,也就是群体互帮互助,相互支持,是集体智慧的体现。

这类算法的输入都是用户和物品的关系矩阵。矩阵的行表示所有用户,矩阵的列表示所有物品。矩阵里的值(一般是0/1/?,表示负反馈,正反馈,未知),也就是关系,是指用户对物品的行为,专业的术语叫反馈数据。有两种维度来衡量这个行为,分别是显式反馈和隐式反馈以及正反馈和负反馈。那么便有四种具体行为:

显式隐式
正反馈点赞/收藏/分享点击
负反馈不喜欢/差评曝光未点击

一般的关系矩阵如下表:

item1item2itemN
user1?01
user21?0
userM??1

理论

协同过滤算法通常可以划分为两类:

  • 基于记忆的协同过滤
    • 思想: 记住每个用户消费过什么物品,然后给他推荐消费过的物品相似的物品;或者把相似的用户喜欢的物品推荐给用户。前者叫基于物品的协同过滤,后者叫基于用户的协同过滤。一句话概括为“物以类聚,人以群分”。
    • 经典案例: 啤酒和尿布的故事,微信朋友圈
    • 缺陷:关系矩阵太稀疏,显式反馈及其稀少,隐式反馈也不多
  • 基于模型的协同过滤
    • 思想: 从用户和物品的关系矩阵中学习一个可以泛化的模型,从而把矩阵剩余的空白处填满。
    • 典型方法: SVD矩阵分解

所有的协同过滤算法的基本输入是用户对物品的关系矩阵。现实中用户数M 是远远大于物品数N的。比如某款APP,它的用户数是亿级别的,而物品数是万级别的。

基于用户的协同过滤

算法浓缩为四个字:人以群分。大致思路是先根据用户的历史消费行为找到一群和你“口味”很相似的用户,然后这些用户消费了什么新的,你没有见过的物品,就可以推荐给你。具体的流程如下:

  1. 准备用户向量(向量维度是物品的个数N,稀疏)
  2. 根据用户向量,两两计算用户之间的相似度。(通过相似度阈值或数目作截断)
  3. 为每个用户生成推荐结果,把和他“品味”相同用户喜欢过的其未推荐过的物品推荐给当前用户

算法落地需要解决以下问题:

  • 关系矩阵如何构建以及存储? 稀疏矩阵(CSR,COO)
  • 物品数很多,也就是用户向量很长,计算一个相似度耗时很久? DIMSUMv2算法,Spark和OpenMP可以实现
  • 用户数目庞大,两两计算耗时很久? 只有相似用户喜欢过的物品需要计算或者通过MR来实现

实践中算法的优化:

  • 惩罚对热门物品的喜欢程度 (热门不能反映用户的真实兴趣)
  • 增加喜欢程度的时间衰减
  • 对用户相似度做平滑 (行为较少的用户算出来的置信度不高)

基于物品的协同过滤

算法浓缩为四个字:物以类聚。大致思路是先计算相似物品,然后在根据用户消费过或者正在消费的物品为期推荐相似物品。具体的流程如下:

  1. 构建用户物品的关系矩阵(关系可以是隐式反馈,也可以是显式反馈,也可以是对行为的量化,比如时间,次数,费用,评分等)
  2. 根据物品向量,两两计算物品之间的相似度。(通过相似度阈值或数目作截断)
  3. 可以为每个用户生成推荐结果也可以在物品页推荐相似物品

实践中算法的优化:

  • 物品维度中心化
  • 用户维度中心化

优缺点

优点

以用户的角度来推荐的协同过滤系统有下列优点:

  • 能够过滤机器难以自动内容分析的信息,如艺术品,音乐等。
  • 共享其他人的经验,避免了内容分析的不完全或不精确,并且能够基于一些复杂的,难以表述的概念(如信息质量、个人品味)进行过滤。
  • 有推荐新信息的能力。可以发现内容上完全不相似的信息,用户对推荐信息的内容事先是预料不到的。可以发现用户潜在的但自己尚未发现的兴趣偏好。
  • 推荐个性化、自动化程度高。能够有效的利用其他相似用户的反馈信息。加快个性化学习的速度。

缺点

虽然协同过滤作为一推荐机制有其相当的应用,但协同过滤仍有许多的问题需要解决。整体而言,最典型的问题有

  • 新用户问题(New User Problem) 系统开始时推荐质量较差
  • 新物品问题(New Item Problem) 质量取决于历史资料集
  • 稀疏性问题(Sparsity)
  • 系统延伸性问题(Scalability)。

距离定义

用户/物品的相似性是通过向量距离来确定的,越相似,距离越小。

  • 余弦角

$$ cos(\theta) = \frac{\vec{x}\vec{y}}{|\vec{x}||\vec{y}|} = \frac{\sum_i^n x_iy_i}{\sqrt{\sum_i^n x_i^2}*\sqrt{\sum_i^n y_i^2}}$$

实现

item1item2item3
user1r1r2r3
user2r4r5
user3r6r7

单机版

序号用户数物品数记录数user-cf耗时(秒)核数
1314121064100000961
2314121064100000692
3314121064100000494
4314121064100000918
51116321335614380057711
61116321335614380054232
7111632133561438005内存爆了8

集群版

参考文献

  1. 协同过滤推荐算法
技术茶话会
< 前一篇 后一篇 >