相关推荐是一种常见的推荐场景,比如资讯流推荐中详情页下方的推荐列表(基于物品的相关推荐),微信看一看(基于用户的相关推荐)等。 在这个场景中必然绕不开一个算法:协同过滤算法。
介绍
协同过滤算法并不是单独的一个算法,是一类算法。它通过分析用户或者事物之间的相似性(“协同”),来预测用户可能感兴趣的内容并将此内容推荐给用户。
这里的相似性可以是人口特征(性别、年龄、居住地等)的相似性,也可以是历史浏览内容的相似性(比如都关注过和中餐相关的内容),还可以是个人通过一定机制给予某个事物的回应(比如一些教学网站会让用户对授课人进行评分)。它的重点是协同,也就是群体互帮互助,相互支持,是集体智慧的体现。
这类算法的输入都是用户和物品的关系矩阵。矩阵的行表示所有用户,矩阵的列表示所有物品。矩阵里的值(一般是0/1/?,表示负反馈,正反馈,未知),也就是关系,是指用户对物品的行为,专业的术语叫反馈数据。有两种维度来衡量这个行为,分别是显式反馈和隐式反馈以及正反馈和负反馈。那么便有四种具体行为:
显式 | 隐式 | |
---|---|---|
正反馈 | 点赞/收藏/分享 | 点击 |
负反馈 | 不喜欢/差评 | 曝光未点击 |
一般的关系矩阵如下表:
item1 | item2 | … | itemN | |
---|---|---|---|---|
user1 | ? | 0 | … | 1 |
user2 | 1 | ? | … | 0 |
… | … | … | … | … |
userM | ? | ? | … | 1 |
理论
协同过滤算法通常可以划分为两类:
- 基于记忆的协同过滤
- 思想: 记住每个用户消费过什么物品,然后给他推荐消费过的物品相似的物品;或者把相似的用户喜欢的物品推荐给用户。前者叫基于物品的协同过滤,后者叫基于用户的协同过滤。一句话概括为“物以类聚,人以群分”。
- 经典案例: 啤酒和尿布的故事,微信朋友圈
- 缺陷:关系矩阵太稀疏,显式反馈及其稀少,隐式反馈也不多
- 基于模型的协同过滤
- 思想: 从用户和物品的关系矩阵中学习一个可以泛化的模型,从而把矩阵剩余的空白处填满。
- 典型方法: SVD矩阵分解
所有的协同过滤算法的基本输入是用户对物品的关系矩阵。现实中用户数M 是远远大于物品数N的。比如某款APP,它的用户数是亿级别的,而物品数是万级别的。
基于用户的协同过滤
算法浓缩为四个字:人以群分。大致思路是先根据用户的历史消费行为找到一群和你“口味”很相似的用户,然后这些用户消费了什么新的,你没有见过的物品,就可以推荐给你。具体的流程如下:
- 准备用户向量(向量维度是物品的个数N,稀疏)
- 根据用户向量,两两计算用户之间的相似度。(通过相似度阈值或数目作截断)
- 为每个用户生成推荐结果,把和他“品味”相同用户喜欢过的其未推荐过的物品推荐给当前用户
算法落地需要解决以下问题:
- 关系矩阵如何构建以及存储? 稀疏矩阵(CSR,COO)
- 物品数很多,也就是用户向量很长,计算一个相似度耗时很久? DIMSUMv2算法,Spark和OpenMP可以实现
- 用户数目庞大,两两计算耗时很久? 只有相似用户喜欢过的物品需要计算或者通过MR来实现
实践中算法的优化:
- 惩罚对热门物品的喜欢程度 (热门不能反映用户的真实兴趣)
- 增加喜欢程度的时间衰减
- 对用户相似度做平滑 (行为较少的用户算出来的置信度不高)
基于物品的协同过滤
算法浓缩为四个字:物以类聚。大致思路是先计算相似物品,然后在根据用户消费过或者正在消费的物品为期推荐相似物品。具体的流程如下:
- 构建用户物品的关系矩阵(关系可以是隐式反馈,也可以是显式反馈,也可以是对行为的量化,比如时间,次数,费用,评分等)
- 根据物品向量,两两计算物品之间的相似度。(通过相似度阈值或数目作截断)
- 可以为每个用户生成推荐结果也可以在物品页推荐相似物品
实践中算法的优化:
- 物品维度中心化
- 用户维度中心化
优缺点
优点
以用户的角度来推荐的协同过滤系统有下列优点:
- 能够过滤机器难以自动内容分析的信息,如艺术品,音乐等。
- 共享其他人的经验,避免了内容分析的不完全或不精确,并且能够基于一些复杂的,难以表述的概念(如信息质量、个人品味)进行过滤。
- 有推荐新信息的能力。可以发现内容上完全不相似的信息,用户对推荐信息的内容事先是预料不到的。可以发现用户潜在的但自己尚未发现的兴趣偏好。
- 推荐个性化、自动化程度高。能够有效的利用其他相似用户的反馈信息。加快个性化学习的速度。
缺点
虽然协同过滤作为一推荐机制有其相当的应用,但协同过滤仍有许多的问题需要解决。整体而言,最典型的问题有
- 新用户问题(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}}$$
实现
item1 | item2 | item3 | |
---|---|---|---|
user1 | r1 | r2 | r3 |
user2 | r4 | r5 | |
user3 | r6 | r7 |
单机版
序号 | 用户数 | 物品数 | 记录数 | user-cf耗时(秒) | 核数 |
---|---|---|---|---|---|
1 | 31412 | 1064 | 100000 | 96 | 1 |
2 | 31412 | 1064 | 100000 | 69 | 2 |
3 | 31412 | 1064 | 100000 | 49 | 4 |
4 | 31412 | 1064 | 100000 | 91 | 8 |
5 | 111632 | 13356 | 1438005 | 771 | 1 |
6 | 111632 | 13356 | 1438005 | 423 | 2 |
7 | 111632 | 13356 | 1438005 | 内存爆了 | 8 |