作者:vivo 互联网服务器团队-Tang Shutao
现如今推荐无处不在,例如抖音、淘宝、京东App均能见到推荐系统的身影,其背后涉及许多的技术。
本文以经典的协同过滤为切入点,重点介绍了被工业界广泛使用的矩阵分解算法,从理论与实践两个维度介绍了该算法的原理,通俗易懂,希望能够给大家带来一些启发。
笔者认为要彻底搞懂一篇论文,最好的方式就是动手复现它,复现的过程你会遇到各种各样的疑惑、理论细节。
一、 背景
1.1 引言
在信息爆炸的二十一世纪,人们很容易淹没在知识的海洋中,在该场景下搜索引擎可以帮助我们迅速找到我们想要查找的内容。
在电商场景,如今的社会物质极大丰富,商品琳琅满目,种类繁多。消费者很容易挑花眼,即用户将会面临信息过载的问题。
为了解决该问题,推荐引擎应运而生。例如我们打开淘宝App,JD app,B站视频app,每一个场景下都有推荐的模块。
那么此时有一个幼儿园小朋友突然问你,为什么JD给你推荐这本《程序员颈椎康复指南》?你可能会回答,因为我的职业是程序员。
接着小朋友又问,为什么《Spark大数据分析》这本书排在第6个推荐位,而《Scala编程》排在第2位?这时你可能无法回答这个问题。
为了回答该问题,我们设想下面的场景:
在JD的电商系统中,存在着用户和商品两种角色,并且我们假设用户都会对自己购买的商品打一个0-5之间的分数,分数越高代表越喜欢该商品。
基于此假设,我们将上面的问题转化为用户对《程序员颈椎康复指南》,《Spark大数据分析》,《Scala编程》这三本书打分的话,用户会打多少分(用户之前未购买过这3本书)。因此物品在页面的先后顺序就等价于预测用户对这些物品的评分,并且根据这些评分进行排序的问题。
为了便于预测用户对物品的评分问题,我们将所有三元组(User, Item, Rating),即用户User给自己购买的商品Item的评分为Rating,组织为如下的矩阵形式:
其中,表格包含 m 个用户和n个物品,将表格定义为评分矩阵 ,其中的元素 表示第u个用户对第i个物品的评分。
例如,在上面的表格中,用户user-1购买了物品 item-1, item-3, item-4,并且分别给出了4,2,5的评分。最终,我们将原问题转化为预测白色空格处的数值。
1.2 协同过滤
协同过滤,简单来说是利用与用户兴趣相投、拥有共同经验之群体的喜好来推荐给用户感兴趣的物品。兴趣相投使用数学语言来表达就是相似度 (人与人,物与物)。因此,根据相似度的对象,协同过滤可以分为基于用户的协同过滤和基于物品的协同过滤。
以评分矩阵为例,以行方向观测评分矩阵,每一行代表每个用户的向量表示,例如用户user-1的向量为 [4, 0, 2, 5, 0, 0]。以列方向观测评分矩阵,每一列表示每个物品的向量表示,例如物品item-1的向量为[4, 3, 0, 0, 5]。
基于向量表示,相似度的计算有多种公式,例如余弦相似度,欧氏距离,皮尔森。这里我们以余弦相似度为例,它是我们中学学过的向量夹角 (中学只涉及2维和3维) 的高维推广,余弦相似度公式很容易理解和使用。给定两个向量 和 ,其夹角定义如下:
例如,我们计算user-3和user-4的余弦相似度,二者对应的向量分别为 [0, 2, 0, 3, 0, 4],[0, 3, 3, 5, 4, 0]
向量夹角的余弦值越接近1代表两个物品方向越接近平行,也就是越相似,反之越接近-1代表两个物品方向越接近反向,表示两个物品相似度接近相反,接近0,表示向量接近垂直/正交,两个物品几乎无关联。显然,这和人的直觉完全一致。
例如,我们在视频App中经常能看到“相关推荐”模块,其背后用到的原理之一就是相似度计算,下图展示了一个具体的例子。
我们用《血族第一部》在向量库 (存储向量的数据库,该系统能够根据输入向量,用相似度公式在库中进行检索,找出TopN的候选向量) 里面进行相似度检索,找到了前7部高相似度的影片,值得注意的是第一部是自己本身,相似度为1.0,其他三部是《血族》的其他3部同系列作品。
1.2.1 基于用户的协同过滤 (UserCF)
基于用户的协同过滤分为两步
-
找出用户相似度TopN的若干用户。
-
根据TopN用户评分的物品,形成候选物品集合,利用加权平均预估用户u对每个候选物品的评分。
例如,由用户u的相似用户{u1, u3, u5, u9}可得候选物品为
我们现在预测用户u对物品i1的评分,由于物品在两个用户{u1, u5}的购买记录里,因此用户u对物品i1的预测评分为:
其中 表示用户 u与用户 的相似度。
在推荐时,根据用户u对所有候选物品的预测分进行排序,取TopM的候选物品推荐给用户u即可。
1.2.2 基于物品的协同过滤 (ItemCF)
基于物品的协同过滤分为两步
-
在用户u购买的物品集合中,选取与每一个物品TopN相似的物品。
-
TopN相似物品形成候选物品集合,利用加权平均预估用户u对每个候选物品的评分。
例如,我们预测用户u对物品i3的评分,由于物品i3与物品{i6, i1, i9}均相似,因此用户u对物品i3的预测评分为:
其中 表示物品 与物品 的相似度,其他符号同理。
1.2.3 UserCF与ItemCF的比较
我们对ItemCF和UserCF做如下总结:
UserCF主要用于给用户推荐那些与之有共同兴趣爱好的用户喜欢的物品,其推荐结果着重于反映和用户兴趣相似的小群体的热点,更社会化一些,反映了用户所在的小型兴趣群体中物品的热门程度。在实际应用中,UserCF通常被应用于用于新闻推荐。
ItemCF给用户推荐那些和他之前喜欢的物品类似的物品,即ItemCF的推荐结果着重于维系用户的历史兴趣,推荐更加个性化,反应用户自己的兴趣。在实际应用中,图书、电影平台使用ItemCF,比如豆瓣、亚马逊、Netflix等。
除了基于用户和基于物品的协同过滤,还有一类基于模型的协同过滤算法,如上图所示。此外基于用户和基于物品的协同过滤又可以归类为基于邻域 (K-Nearest Neighbor, KNN) 的算法,本质都是在找”TopN邻居”,然后利用邻居和相似度进行预测。
二、矩阵分解
经典的协同过滤算法本身存在一些缺点,其中最明显的就是稀疏性问题。我们知道评分矩阵是一个大型稀疏矩阵,导致在计算相似度时,两个向量的点积等于0 (以余弦相似度为例)。为了更直观的理解这一点,我们举例如下:
rom sklearn.metrics.pairwise import cosine_similarity
a = [
[ ],
[ ],
[ ],
[ ]
]
cosine_similarity(a)
我们从评分矩阵中抽取item1 – item4的向量,并且利用余弦相似度计算它们之间的相似度。
通过相似度矩阵,我们可以看到物品item-1, item-2, item-3的之间的相似度均为0,而且与item-1, item-2, item-3最相似的物品都是item-4,因此在以ItemCF为基础的推荐场景中item-4将会被推荐给用户。
但是,物品item-4与物品item-1, item-2, item-3最相似的原因是item-4是一件热门商品,购买的用户多,而物品item-1, item-2, item-3的相似度均为0的原因仅仅是它们的特征向量非常稀疏,缺乏相似度计算的直接数据。
综上,我们可以看到经典的基于用户/物品的协同过滤算法有天然的缺陷,无法处理稀疏场景。为了解决该问题,矩阵分解被提出。
2.1 显示反馈
我们将用户对物品的评分行为定义为显示反馈。基于显示反馈的矩阵分解是将评分矩阵Rm×n 用两个矩阵 和Yn×k的乘积近似表示,其数学表示如下:
其中, 表示隐性因子,以用户侧来理解, 表示的就是用户的年龄和性别两个属性。此外有个很好的比喻就是物理学的三棱镜,白光在三棱镜的作用下被分解为7种颜色的光,在矩阵分解算法中,分解的作用就类似于”三棱镜”,如下图所示,因此,矩阵分解也被称为隐语义模型。矩阵分解将系统的自由度从 降到了,从而实现了降维的目的。
为了求解矩阵