Spark-ALS 分布式实现详解

如今,协同过滤推荐(CollaboratIve Filtering)技术已广泛应用于各类推荐系统中,其通常分为两类,一种是基于用户的协同过滤算法(User-Based CF),它是根据用户对物品的历史评价数据,如喜欢、点击、购买等,计算不同用户之间的相似度,在有相同喜好的用户间进行物品推荐,例如将跟我有相同电影爱好的人看过的电影推荐给我。

另一种是基于物品的协同过滤算法(Item-Based CF),它是根据用户对物品的历史评价数据,计算物品之间的相似度,用户如果喜欢A物品,那么可以给用户推荐跟A物品相似的其他物品,例如如果我们在购物网站上买过尿片,第二天你再到购物网站上浏览时,可能会被推荐奶瓶。更多关于User-Based CF和Item-Based CF的阐述请参考《推荐算法协同过滤》文章。然而,在用户评分不足的情况下,上述两种方法就不是很好使了,近年来,基于模型的推荐算法ALS(交替最小二乘)在Netflix成功应用并取得显著效果提升,ALS使用机器学习算法建立用户和物品间的相互作用模型,进而去预测新项。

基本原理

用户对物品的打分行为可以表示成一个打分矩阵
,例如下表所示:

矩阵中的打分值

表示用户
对物品
的打分,其中"?"表示用户没有打分,这也就是要通过机器学习的方法去预测这个打分值,从而达到推荐的目的。

模型抽象

按照User-Based CF的思想,

的行向量对应每个用户
,按照Item-Based CF的思想,
的列向量对应每个物品
。ALS 的核心思想是,将用户和物品都投影到
维空间,也就是说,假设有
个隐含特征,至于个隐含特征具体指什么不用关心,将每个用户和物品都用
维向量来表示,把它们之间的内积近似为打分值,这样就可以得到如下近似关系:

其中,

为打分矩阵
个用户,
个物品,
为用户对隐含特征的偏好矩阵
为物品对隐含特征的偏好矩阵

上述模型的参数就是矩阵

,即求解出
我们就可以重现打分矩阵,填补原始打分矩阵中的缺失值"?"。

显示反馈代价函数

要求解上述模型中的

,那么就需要一个代价函数来衡量参数的拟合程度,如果有比较明确的显式反馈打分数据,那么可以比较重构出来的打分矩阵与实际打分矩阵,即得到重构误差,由于实际打分矩阵有很多缺失值,所以仅计算已知打分的重构误差,下面函数为显示反馈代价函数。

其中,

表示用户
对物品
的打分,
为矩阵
的第
为矩阵
的第
为正则项系数。

隐式反馈代价函数

很多情况下,用户并没有明确反馈对物品的偏好,需要通过用户的相关行为来推测其对物品的偏好,例如,在视频推荐问题中,可能由于用户就懒得对其所看的视频进行反馈,通常是收集一些用户的行为数据,得到其对视频的偏好,例如观看时长等。通过这种方式得到的偏好值称之为隐式反馈值,即矩阵

为隐式反馈矩阵,引入变量
表示用户
对物品
的置信度,如果隐式反馈值大于0,置信度为1,否则置信度为0。

但是隐式反馈值为0并不能说明用户就完全不喜欢,用户对一个物品没有得到一个正的偏好可能源于多方面的原因,例如,用户可能不知道该物品的存在,另外,用户购买一个物品也并不一定是用户喜欢它,所以需要一个信任等级来显示用户偏爱某个物品,一般情况下,越大,越能暗示用户喜欢某个物品,因此,引入变量

,来衡量
的信任度,其中
为置信系数。

那么,代价函数则变成如下形式:

算法

无论是显示反馈代价函数还是隐式反馈代价函数,它们都不是凸的,变量互相耦合在一起,常规的梯度下降法可不好使了。但是如果先固定

求解
,再固定
求解
,如此迭代下去,问题就可以得到解决了。

那么固定一个变量求解另一个变量如何实现呢,梯度下降?虽然可以用梯度下降,但是需要迭代,计算起来相对较慢,试想想,固定

求解
,或者固定
求解
,其实是一个最小二乘问题,由于一般隐含特征个数
取值不会特别大,可以将最小二乘转化为正规方程一次性求解,而不用像梯度下降一样需要迭代。如此交替地解最小二乘问题,所以得名交替最小二乘法ALS,下面是基于显示反馈和隐式反馈的最小二乘正规方程。

显示反馈

固定
求解

更直观一点,每个用户向量的求解公式如下:

其中,

为矩阵
的第
行的转置
为矩阵
的第
行的转置

固定

求解

更直观一点,每个物品向量的求解公式如下:

其中,

为矩阵
的第
为矩阵
的第

隐式反馈

固定

求解

更直观一点,每个用户向量的求解公式如下:

其中,

为对角矩阵

固定

求解

更直观一点,每个物品向量的求解公式如下:

其中,

为对角矩阵

Spark 分布式实现

上述ALS算法虽然明朗了,但是要将其实现起来并不是信手拈来那么简单,尤其是数据量较大,需要使用分布式计算来实现,就更加不是那么地容易了。下面详细阐述Spark ML是如何完成ALS分布式实现的。为了更加直观的了解其分布式实现,下面用前面的打分矩阵作为例子,如下图所示。

由前面的原理介绍可知,按照显示反馈模型,固定

求解
,每个物品对隐含特征的偏好向量
由以下公式得到:

计算时,只需要计算得到

,再利用BLAS库即可解方程,初次迭代计算时,随机初始化矩阵
,假设得到如下初始形式:

假如求解

,由于只有
有打分,那么只需基于
来计算,根据相关线性代数知识就可以得到:

有了这个基本求解思路后,考虑

的维度为
,可以在单机上完成上述求解,那么就可以在不同task里完成不同物品
的计算,实现分布式求解,由打分矩阵可以得到如下图所示的关系图。

基于上述思路,就是要想办法把有打分关联的 u 和 v 想办法放到同一个分区里,这样就可以在一个task里完成对 v 的求解。首先对uid和vid以Hash分区的方式分区,假设分区数均为2,那么分区后的大致情况如下图所示,

在同一个分区中被求解,
在同一个分区中被求解。

上面的图仅为感性认识图,实际上手头仅有的数据就是打分矩阵,可以通过一个RDD表示打分矩阵ratings,RDD中的每条记录为(uid, vid, rating)形式,由于是基于

求解
,把uid称之为srcId,vid称之为dstId,按照srcId和dstId的分区方式,将ratings重新分区,得到的RDD为blockRatings,其中的每条记录为((srcBlockId, dstBlockId), RatingBlock)形式,key为srcId和dstId对应的分区id组成的二元组,value(RatingBlock)包含一个三元组(srcIds, dstIds, ratings)。对于前面的打分关系,原始打分矩阵重新分区如下图所示。

对于 u 来说,是要将自身信息发给不同的 v,对于 v 来说,是要接收来自不同 u 的信息,例如,要将

发给
,要接收
。那么基于上述重新分区后的打分RDD,分别得到关于 u 的出口信息userOutBlocks,以及 v 的入口信息itemInBlocks,就可以通过join将两者联系起来计算了。由于后面基于
,也需要求解关于 u 的入口信息userInBlocks,以及 v 的出口信息itemOutBlocks,所以一次性计算好并缓存起来。以计算 u 的入口信息和出口信息为例,在前面得到的重新分区后的blockRatings基础上求解,如下图所示。

首先通过一个map操作,将记录形式((srcBlockId, dstBlockId), RatingBlock)转换为(srcBlockId, (dstBlockId, srcIds, dstLocalIndices, ratings)),其中dstLocalIndices为dstIds去重排序后,每个dstId在其分区中的索引,最后根据srcBlockId做groupByKey,合并相同srcBlockId对应的value,合并过程中,对dstLocalIndices中的每个元素加上其对应的dstBlockId,这里做了一个优化,就是将localIndex和blockId用一个Int编码表示,同时采用类似CSC压缩编码的方式,进一步压缩srcIds和dstIds的对应关系。这样就按照 uid 进行分区后,得到 u 的入口信息,即将跟 u 关联的 v 绑定在一起了。基于该入口信息,可以进一步得到 u 的出口信息,如下图所示。

在userInBlocks基础上根据srcIds和dstIds的对应关系,通过map操作将(srcBlockId, (srcIds, dstPtrs, dstEncodedIndices, ratings))形式的记录转换为(srcBlockId, OutBlock)得到userOutBlocks,其中OutBlock是一个二维数组,有numDstBlock行,每一行为srcId所在srcBlockId中的索引,意为当前srcBlockId应该往每个dstBlockId发送哪些用户信息。

同理,在userInBlocks基础上初始化用户信息,得到userFactors,如下图所示,其中、、为随机初始化的向量。

接着对userOutBlocks和userFactors做join就可以模拟发送信息了,userOutBlocks中保存了应该往哪里发送的信息,userFactors中保存了用户信息,即一个掌握了方向,一个掌握了信息,如下图所示:

完成了从 u 到 v 的信息发送,后面就是基于 v 的入口信息来收集来自不同 u 的信息了,计算 v 的入口信息跟计算 u 的入口信息一样,只是先要把打分数据blockRatings的src和dst交换一下,如下图所示。

将itemInBlocks与前面的userOut做join,即可将具有相同dstBlockId的记录拉到一起,userOut中包含来自 u 的信息,itemInBlocks包含了与src的对应关系以及打分数据,针对每个 v 找到所有给它发送信息的 u,进而套最小二乘正规方程计算得到itemFactors。

得到itemFactors后可以以同样的方法基于求解,如此交替求解,直到最大迭代次数为止。

总结

ALS从基本原理上来看应该是很好理解的,但是要通过分布式计算来实现它,相对而言还是较为复杂的,本文重点阐述了Spark ML库中ALS的实现,要看懂以上计算流程,请务必结合源代码理解,凭空理解上述流程可能比较困难,在实际源码实现中,使用了很多优化技巧,例如使用在分区中的索引代替实际uid或vid,实现Int代替Long,使用数组等连续内存数据结构避免由于过多对象造成JVM GC后的内存碎片等。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏携程技术中心

干货 | 机器学习在web攻击检测中的应用实践

作者简介 岳良, 携程信息安全部高级安全工程师。2015年加入携程,主要负责渗透测试,安全评审,安全产品设计。 一、背景 在web应用攻击检测的发展历史中,到目...

2695
来自专栏PPV课数据科学社区

【学习】推荐算法实践

前言 推荐系统并不是新鲜的事物,在很久之前就存在,但是推荐系统真正进入人们的视野,并且作为一个重要的模块存在于各个互联网公司,还是近几年的事情。 随着互联网的深...

2783
来自专栏新智元

【揭秘】美团如何用机器学习优化推荐系统算法

本文介绍了美团网推荐系统的构建和优化过程中的一些做法,包括数据层、触发层、融合过滤层和排序层五个层次,采用了HBase、Hive、storm、Spark和机器学...

3576
来自专栏CSDN技术头条

干货 | 机器学习在web攻击检测中的应用实践

一、背景 在web应用攻击检测的发展历史中,到目前为止,基本是依赖于规则的黑名单检测机制,无论是web应用防火墙或ids等等,主要依赖于检测引擎内置的正则,进行...

1879
来自专栏开源优测

大数据测试学习笔记之Python工具集

这是2018年度业余主要学习和研究的方向的笔记:大数据测试 整个学习笔记以短文为主,记录一些关键信息和思考 预计每周一篇短文进行记录,可能是理论、概念、技术、工...

3996
来自专栏数据派THU

手把手教你用Prophet快速进行时间序列预测(附Prophet和R代码)

对于任何业务而言,基于时间进行分析都是至关重要的。库存量应该保持在多少?你希望商店的客流量是多少?多少人会乘坐飞机旅游?类似这样待解决的问题都是重要的时间序列问...

1003
来自专栏华章科技

一文看懂数据可视化:从编程工具到可视化表现方式

说到可视化,就不得不说一下大数据,毕竟可视化是解决大数据的一种高效的手段,而如今人人都在谈论大数据,大数据 ≠ 有数据 ≠ 数据量大, 离谱的是,如今就连卖早点...

732
来自专栏深度学习

机器学习在web攻击检测中的应用实践

一、背景 通俗地讲,任何一个的机器学习问题都可以等价于一个寻找合适变换函数的问题。例如语音识别,就是在求取合适的变换函数,将输入的一维时序语音信号变换到语义空间...

3585
来自专栏机器学习算法原理与实践

强化学习(五)用时序差分法(TD)求解

    在强化学习(四)用蒙特卡罗法(MC)求解中,我们讲到了使用蒙特卡罗法来求解强化学习问题的方法,虽然蒙特卡罗法很灵活,不需要环境的状态转化概率模型,但是它...

1022
来自专栏PPV课数据科学社区

【学习】用SPSS绘制质量控制图

控制图(Control Chart)又称管理图,它是用来区分是由异常原因引起的波动,还是由过程固有的原因引起的正常波动的一种有效的工具。控制图通过科学的区分正常...

2715

扫码关注云+社区