为什么spark中只有ALS - 木白的菜园 - 博客园

标签: | 发表时间:2017-11-12 07:55 | 作者:
出处:https://www.cnblogs.com
WRMF is like the classic rock of implicit matrix factorization. It may not be the trendiest, but it will never go out of style

                                                                                                                                                                 --Ethan Rosenthal

前言

spark平台推出至今已经地带到2.1的版本了,很多地方都有了重要的更新,加入了很多新的东西。但是在协同过滤这一块却一直以来都只有ALS一种算法。同样是大规模计算平台,Hadoop中的机器学习算法库Mahout就集成了多种推荐算法,不但有user-cf和item-cf这种经典算法,还有KNN、SVD,Slope one这些,可谓随意挑选,简繁由君。我们知道得是,推荐系统这个应用本身并没有过时,那么spark如此坚定 地只维护一个算法,肯定是有他的理由的,让我们来捋一捋。

ALS算法

ALS的意思是交替最小二乘法(Alternating Least Squares),它只是是一种优化算法的名字,被用在求解spark中所提供的推荐系统模型的最优解。spark中协同过滤的文档中一开始就说了,这是一个基于模型的协同过滤(model-based CF),其实它是一种近几年推荐系统界大火的隐语义模型中的一种。隐语义模型又叫潜在因素模型,它试图通过数量相对少的 未被观察到的底层原因,来解释大量用户和产品之间 可观察到的交互。操作起来就是通过降维的方法来补全用户-物品矩阵,对矩阵中没有出现的值进行估计。基于这种思想的早期推荐系统常用的一种方法是SVD(奇异值分解)。该方法在矩阵分解之前需要先把评分矩阵R缺失值补全,补全之后稀疏矩阵R表示成稠密矩阵R',然后将R’分解成如下形式:
R' =  U T SV
然后再选取U中的K列和V中的S行作为隐特征的个数,达到降维的目的。K的选取通常用启发式策略。

这种方法有两个缺点,第一是补全成稠密矩阵之后需要耗费巨大的存储空间,在实际中,用户对物品的行为信息何止千万,对这样的稠密矩阵的存储是不现实的;第二,SVD的计算复杂度很高,更不用说这样的大规模稠密矩阵了。所以关于SVD的研究很多都是在小数据集上进行的。

隐语义模型也是基于矩阵分解的,但是和SVD不同,它是把原始矩阵分解成两个矩阵相乘而不是三个。
A = XY T
现在的问题就变成了确定X和Y ,我们把X叫做用户因子矩阵,Y叫做物品因子矩阵。通常上式不能达到精确相等的程度,我们要做的就是要最小化他们之间的差距,从而又变成了一个最优化问题。求解最优化问题我们很容易就想到了随机梯度下降,其中有一种方法就是这样,通过优化如下损失函数来找到X和Y中合适的参数:
 
其中p uk就是X矩阵中u行k列的参数,度量了用户u和第k个隐类的关系;q ik是Y矩阵中i行k列的参数,度量了物品i和第k个隐类的关系。这种方式也是一种很流行的方法,有很多对它的相关扩展,比如 加上偏置项的LFM

然而ALS用的是另一种求解方法,它先用随机初始化的方式固定一个矩阵,例如Y
 
然后通过最小化等式两边差的平方来更新另一个矩阵X,这就是“最小二乘”的由来。得到X之后,又可以固定X用相同的方法求Y,如此交替进行,直到最后收敛或者达到用户指定的迭代次数为止,是为“交替”是也。 从上式可以看出,X的第i行是A的第i行和Y的函数,因此可以很容易地分开计算X的每一行,这就为并行就算提供了很大的便捷,也正是如此,Spark这种面向大规模计算的平台选择了这个算法。在3这篇文章中,作者用了embarrassingly parallel来形容这个算法,意思是高度易并行化的——它的每个子任务之间没有什么依赖关系。

在现实中,不可能每个用户都和所有的物品都有行为关系,事实上,有交互关系的用户-物品对只占很小的一部分,换句话说,用户-物品关系列表是非常稀疏的。和SVD这种矩阵分解不同,ALS所用的矩阵分解技术在分解之前不用把系数矩阵填充成稠密矩阵之后再分解,这不但大大减少了存储空间,而且spark可以利用这种稀疏性用简单的线性代数计算求解。这几点使得本算法在大规模数据上计算非常快,解释了为什么spark mllib目前只有ALS一种推荐算法。

显性反馈和隐性反馈

我们知道,在推荐系统中用户和物品的交互数据分为显性反馈和隐性反馈数据的。在ALS中这两种情况也是被考虑了进来的,分别可以训练如下两种模型:
            
  1. val model1=ALS.train(ratings,rank,numIterations,lambda)//显性反馈模型
  2. val model2=ALS.trainImplicit(ratings,rank,numIterations,lambda,alpha)//隐性反馈模型
参数:
rating:由用户-物品矩阵构成的训练集
rank:隐藏因子的个数
numIterations: 迭代次数
lambda:正则项的惩罚系数
alpha: 置信参数

从上面可以看到,隐式模型多了一个置信参数,这就涉及到ALS中对于隐式反馈模型的处理方式了——有的文章称为“加权的正则化矩阵分解”,它的损失函数如下:
 
我们知道,在隐反馈模型中是没有评分的,所以在式子中rui被pui所取代,pui是偏好的表示,仅仅表示用户和物品之间有没有交互,而不表示评分高低或者喜好程度。比如用户和物品之间有交互就让pui等于1,没有就等于0。函数中还有一个c ui的项,它用来表示用户偏爱某个商品的置信程度,比如交互次数多的权重就会增加。如果我们用dui来表示交互次数的话,那么就可以把置信程度表示成如下公式:
这里的alpha就是上面提到的 置信参数,也是这个模型的超参数之一,需要用交叉验证来得到。



用spark的ALS模型进行推荐

1.为指定用户进行topN推荐
            
  1. model.recommendProducts(userID,N)
2.为 用户-物品 对进行预测评分,显式和隐式反馈都可以,是根据两个因子矩阵对应行列相乘得到的数值,可以用来评估系统。既可以传入一对参数,也可以传入以(user,item)对类型的RDD对象作为参数,如下
            
  1. model.predict(user,item)
  2. model.predict(RDD[int,int])
3.根据物品推荐相似的物品
这其实不算是一种模型内置的推荐方式,但是ALS可以为我们计算出物品因子矩阵和用户因子矩阵:
          
  1. model.productFeatures
  2. model.userFeatures
这是一种降维,让我们可以用更少的维度表示,同时也意味着如果我们要算物品相似度或者用户相似度可以用更少的特征进行计算。进而得到“和这个物品相似的物品”这种类型的推荐。

参考资料

1.《spark机器学习》
2.《spark高级数据分析》

相关 [spark als 菜园] 推荐:

为什么spark中只有ALS - 木白的菜园 - 博客园

- -
                                                                                                                                                                 --Ethan Rosenthal.

如何使用Spark ALS实现协同过滤

- - 鸟窝
转载自 JavaChen Blog,作者: Junez. 本文主要记录最近一段时间学习和实现Spark MLlib中的协同过滤的一些总结,希望对大家熟悉Spark ALS算法有所帮助. 【2016.06.12】Spark1.4.0中MatrixFactorizationModel提供了recommendForAll方法实现离线批量推荐,见 SPARK-3066.

ALS-WR算法原文译文

- - CSDN博客云计算推荐文章
经过3个晚上的翻译,终于把ALS-WR算法的介绍论文翻译完成. 此次翻译目的是加强对ALS-WR算法的理解和练习自己对专业性英文的能力,由于本人英文水平有限并且该算法使用到了多个高数甚至超越高数和线性代数的一些知识,所以如哪里翻译不对或理解有误,望英语强人,数学高人,算法牛人给个纠正,先于此谢过. 原文见:http://link.springer.com/chapter/10.1007%2F978-3-540-68880-8_32?LI=true#page-1,最好是看英文版的,因为该算法的主要精髓是在那几个数学公式上.

Spark概览

- - 简单文本
Spark具有先进的DAG执行引擎,支持cyclic data flow和内存计算. 因此,它的运行速度,在内存中是Hadoop MapReduce的100倍,在磁盘中是10倍. 这样的性能指标,真的让人心动啊. Spark的API更为简单,提供了80个High Level的操作,可以很好地支持并行应用.

Spark与Mapreduce?

- - 崔永键的博客
我本人是类似Hive平台的系统工程师,我对MapReduce的熟悉程度是一般,它是我的底层框架. 我隔壁组在实验Spark,想将一部分计算迁移到Spark上. 年初的时候,看Spark的评价,几乎一致表示,Spark是小数据集上处理复杂迭代的交互系统,并不擅长大数据集,也没有稳定性. 但是最近的风评已经变化,尤其是14年10月他们完成了Peta sort的实验,这标志着Spark越来越接近替代Hadoop MapReduce了.

Spark迷思

- - ITeye博客
目前在媒体上有很大的关于Apache Spark框架的声音,渐渐的它成为了大数据领域的下一个大的东西. 证明这件事的最简单的方式就是看google的趋势图:. 上图展示的过去两年Hadoop和Spark的趋势. Spark在终端用户之间变得越来越受欢迎,而且这些用户经常在网上找Spark相关资料. 这给了Spark起了很大的宣传作用;同时围绕着它的也有误区和思维错误,而且很多人还把这些误区作为银弹,认为它可以解决他们的问题并提供比Hadoop好100倍的性能.

Spark 优化

- - CSDN博客推荐文章
提到Spark与Hadoop的区别,基本最常说的就是Spark采用基于内存的计算方式,尽管这种方式对数据处理的效率很高,但也会往往引发各种各样的问题,Spark中常见的OOM等等. 效率高的特点,注定了Spark对性能的严苛要求,那Spark不同程序的性能会碰到不同的资源瓶颈,比如:CPU,带宽、内存.

Spark&Spark性能调优实战

- - CSDN博客互联网推荐文章
       Spark特别适用于多次操作特定的数据,分mem-only和mem & disk. 其中mem-only:效率高,但占用大量的内存,成本很高;mem & disk:内存用完后,会自动向磁盘迁移,解决了内存不足的问题,却带来了数据的置换的消费. Spark常见的调优工具有nman、Jmeter和Jprofile,以下是Spark调优的一个实例分析:.

Mesos上部署spark

- - 开源小站
还是回到之前一直持续的 Mesos话题. 在之前的环节里,我们已经尝试了Mesos的安装,Marathon守护服务以及相对比较主流的Mesos作为Hadoop的资源管理器的实际操作. 这次就说说同属于伯克利出品的Spark. 其实spark最初0.7以前的版本还没有自己的资源管理系统,资源的调度都是通过Mesos来执行的.

Spark容错机制

- - zzm
一般来说,分布式数据集的容错性有两种方式: 数据检查点和记录数据的更新. 面向大规模数据分析,数据检查点操作成本很高,需要通过数据中心的网络连接在机器之间复制庞大的数据集,而网络带宽往往比内存带宽低得多,同时还需要消耗更多的存储资源. 因此,Spark选择记录更新的方式. 但是,如果更新粒度太细太多,那么记录更新成本也不低.