基于ALS算法的简易在线推荐系统

根据作者的后一篇文章的介绍,这应该是他在Intel做实习生的时候两个半月做个一个实习项目: 《Spark上流式机器学习算法实现”终期检查报告 》
原文地址: 基于ALS算法的简易在线推荐系统

继前期完成广义线性模型的在线流式机器学习的代码后,我们对spark的mllib中的推荐系统这一部分比较感兴趣,因为推荐系统这一部分在现实生活中也非常实用,尤其是基于地理位置的在线推荐系统目前非常火热,很多商业软件如大众点评,淘点点等都希望能根据用户以往的一些行为和当前所处的地理位置给用户做出最佳的推荐,给用户带来意想不到的惊喜。

在推荐系统领域,目前市面上中文的参考书并不多,我们主要学习了目前就职于hulu公司的项亮编著的《推荐系统实战》这本书,这本书详细的介绍了推荐系统方面的一些典型算法和评估方法,并且结合作者的实际经验给出了很多推荐系统的相关实例,是学习推荐系统不可多得的一本好书,我们也受益匪浅。

在spark的例程中作者是根据movielens数据库(采用spark自带的小型movielens数据库在spark的data/mllib/sample_movielens_data.txt中)通过ALS(alternating leastsquares)算法来做的推荐系统。参考链接 http://spark.apache.org/docs/latest/mllib-collaborative-filtering.html

最初我们也是用上面所说的1500个的数据集进行在线ALS算法的有效性,效果还不错,后面我们采用中等规模的movielens数据集进行测试,取得比较好的效果,具体过程记录如下。数据集的链接如下http://grouplens.org/datasets/movielens/.

这种ALS算法不像基于用户或者基于物品的协同过滤算法一样,通过计算相似度来进行评分预测和推荐,而是通过矩阵分解的方法来进行预测用户对电影的评分。即如下图所示。

已知的用户对电影的评分的数据如下图所示。

第一项表示用户的ID号,第二项表示电影的ID号,第三项表示用户对电影评分的分值。

因此可以通过数据集中的数据构建用户评分矩阵,但是往往用户的评分不会填满所有的矩阵,因此就需要通过矩阵分解的方法,将矩阵X分解为AB,也即尽量满足X=AB这个等式。ALS算法中,通过首先随机化矩阵A,然后通过目标函数求得B,再对B进行归一化处理后,再去求A,不断地迭代下去,直到AB满足一定的收敛条件为止。

在我们的在线推荐系统中,我们借用spark的ALS算法的训练和预测函数,每次收到新的数据后,将其更新到训练数据集中,然后更新ALS训练得到的模型,然后对整个movielens数据集进行评分预测计算RMSE,来看RMSE的收敛情况来推断算法的训练效果。(注:由于水平有限,我们发现更改spark的ALS的训练模型为在线训练模型比较困难,也即在接收到新的数据后,通过更低的算法复杂度的算法得到新的分解的矩阵,而不是重新计算分解的矩阵AB的数据值)

流程图如下图所示。

在编程的时候得注意第一步训练ALS模型的时候,给ALS模型的初始化数据集是对movielens数据集中的1500个数据根据每个用户的评分数据随机提取20%的数据组合而成的。另外每个用户随机选取20%的数据组合在一起作为测试数据集。剩下的60%的数据作为流式学习的数据集。

有一个初始化模型数据集的原因是因为ALS算法是基于矩阵分解来做的,如果最开始的数据集的取值空间不够大的话,在下图中的测试结果中可以看到,最初的数据集在测试集上只能预测14670个点,其实测试集是有20000个数据集的,因此很多点我们的模型无法预测,不过没有关系,随着训练数据的不断增加,我们可以预测的数据逐渐趋近于20000个,并且预测的RMSE逐渐减小,达到了在线训练的效果。

注: 由于ALS算法复杂度较高,我们最初在1G内存的linux上跑,出现了一些bug,换到4G内存的机器才能进行简易的ALS模型的计算,而且ALS模型的rank, lambda, iter这几个参数都比较重要,我们选择了比较小的参数,使模型训练简单,但是可以说明问题,如果增加参数,模型会更好,由于机器条件限制,难以测试更好的模型的效果。
另外,编程的时候碰到好多数据结构不对,或者成员函数用法不对的问题,这里给出一些相关的网站参考链接,以备不时之需。由于各种数据结构的继承关系,编程中的所有的数据结构及其成员函数的用法在下面链接中都可以找到。