基于Spark的矩阵分解推荐算法
作者：郑凤飞　黄文培　贾明正
来源：《计算机应用》2015年第10期
        摘要：针对传统矩阵分解算法在处理海量数据信息时所面临的处理速度和计算资源的瓶颈问题，利用Spark在内存计算和迭代计算上的优势，提出了Spark框架下的矩阵分解并行化算法。首先，依据历史数据矩阵初始化用户因子矩阵和项目因子矩阵；其次，迭代更新因子矩阵，将迭代结果置于内存中作为下次迭代的输入；最后，迭代结束时得到矩阵推荐模型。通过在GroupLens网站上提供的MovieLens数据集上的实验结果表明，加速比（Speedup）值达到了线性的结果，该算法可以提高协同过滤推荐算法在大数据规模下的执行效率。
        关键词：协同过滤；推荐算法；矩阵分解；迭代最小二乘法；Spark
        中图分类号： TP301.6
        文献标志码：A
        Abstract： In order to solve the bottleneck problems of processing speed and resource
allocation， a Spark based matrix factorization recommendation algorithm was proposed. Firstly， user factor matrix and item factor matrix were initialized according to historical data. Secondly， factor matrix was iteratively updated and the result was stored in memory as the input of next iteration. Finally， recommendation model was generated when iteration ended. The experiment on MovieLens shows that the speedup is linear and the proposed Spark based algorithm can save time and significantly improve the execution efficiency of collaborative filtering recommendation algorithm.
        Key words： collaborative filtering； recommendation algorithm； matrix factorization； Alternating Least Square （ALS）； Spark
        0引言
        随着互联网的迅猛发展，为了满足人们在繁多的信息中获取自己需要内容的需求，个性化推荐应用而生。协同过滤推荐[1]是其中运用最为成功的技术之一。其中，基于用户的最近邻法根据相似用户的评分来预测当前用户的评分[2]。然而，在用户数量以及用户评分不足的情况下，该方法存在冷启动和数据稀疏的问题。文献[3]提出了基于项的最近邻法，利用项之
间相似性稳定的特点可以离线计算相似性，降低了在线计算量，提高了推荐效率，但同样存在冷启动和数据稀疏问题。文献[4]使用矩阵分解中的奇异值分解（Singular Value Decomposition， SVD）减少评分矩阵的维数，之后应用最近邻法预测评分，一定程度上解决了同义词问题，但由于评分矩阵中大部分的评分是分解之前填充的，所以得到的特征矩阵不能直接用于评分。文献[5]提出了一种基于矩阵分解和用户近邻模型的算法，解决了数据稀疏的问题，但存在模型过拟合的问题。文献[6]提出了一种支持不完整评分矩阵的矩阵分解方法，不用对评分矩阵进行估值填充，有很好的推荐精度。在Netflix推荐系统竞赛中的应用表明，该矩阵分解相对于其他的推荐算法能产生更精确的推荐。
        在矩阵分解推荐算法中，每项评分预测都需要整合现有评分集的信息。随着用户数与项目数的增长，算法的计算量也会随着增长，单机模式的推荐算法逐渐难以满足算法的计算以及推送的即时性需求，因此分布式推荐算法成为推荐算法中研究的一个新的方向。文献[7-8]提出了分布式的矩阵分解算法，为矩阵分解的并行计算提供了一种可行的解决方案，但其使用的MapReduce框架在各计算节点的迭代计算中会产生过多的文件读取操作，影响了算法的执行效率。
        本文旨在将文献[6]提出的矩阵分解推荐算法与专长于内存计算和迭代计算的Spark并行计算框架结合，探索矩阵分解算法在Spark上的实现，来解决大数据情况下矩阵分解推荐算法时间代价过高的问题。
        1矩阵分解推荐算法与Spark平台
        1.1矩阵分解推荐算法
        其中：n表示项目数量，m表示用户数量，矩阵元素 Rij 表示用户i 对项目 j 的偏好评估值，例如：1～5分范围内，1代表很不喜欢，5代表很喜欢。
        协同过滤中矩阵分解的目标是把用户和项目映射到同一个维数为f的潜在因子空间[9]，这样用户与项目之间的关系就可以通过潜在因子空间中的内积来建模，如式（1）所示：
        R≈PQT（1）
        其中： P是一个nu× f的矩阵（nu表示用户的数量，也即是矩阵R中横向量的个数， f表示因子个数，也即是低维矩阵的维数）；Q是一个ni× f 的矩阵（ni表示项目的数量）。本文
称P为用户因子矩阵，Q为项目因子矩阵，则每个用户对应的向量为pu，每个项目对应的向量为qi。矩阵分解的目标就是计算得到每个用户的因子向量pu和每个项目的因子向量qi，使得预测用户u对项目i 感兴趣的程度ui=puqTi能够尽可能地接近真实评分rui。当给定的矩阵不完全时，此模型容易导致过拟合，因此，当前的很多研究都建议仅对存在的评分项进行建模，采用正则化[6]6-7模型避免过拟合问题，目标函数定义如式（2）：
        minp*，q*∑n（u，i）∈k（rui-puqTi）2+λ（‖pu‖2+‖qi‖2） （2）
        其中：λ 参数用来正则化模型，称为正则化系数； k代表训练集中存在的评分项。求解上面的模型，目前常用的方法有两种：随机梯度下降（Stochastic Gradient Descent， SGD）法[10]和交替最小二乘迭代（Alternating Least Squares， ALS）法[11]。
        1.2Spark平台
        Spark是UC Berkeley AMP Lab开源的通用并行计算框架[12]。该框架提出了内存集计算，通过将数据集缓存到内存中，减少数据的I/O操作，从而提高数据的读写速率。
        Spark创新地提出了弹性分布数据集（Resilient Distributed Dataset， RDD）[13]。RD
D本质是自定义的可并行的数据容器，不同的数据集格式对应不同类型的RDD。弹性表现在若一个RDD分片丢失，Spark可以根据日志信息重构它；分布式表现在可以用操作本地集合的方式来操作分布式数据集。此外，RDD可以被缓存在内存中，在之后的计算过程中可以直接从内存中读入，省去了大量的磁盘存取开销，适合需要迭代计算的矩阵分解算法。图1显示了Spark的基本工作流程，每个Spark Application都有自己的Executor进程，进程的生命周期和整个Application的生命周期相同，而且其内部维持着多个线程来并行地执行分配给它的Task。这种运行模式有利于进行不同Application之间的资源、调度隔离。
        2基于Spark矩阵分解并行化
        2.1Spark框架下矩阵分解算法
        对于目标函数式（1），交替最小二乘方法在求解时可以固定P求解Q，然后再固定Q求解P，重复交替这两步直至算法收敛。在实现上，SGD方法比ALS方法更容易实现，而且能够更快收敛，但是ALS算法更易于并行化， 因此本文采用ALS算法。
        本文中基于Spark的矩阵分解并行化，主要是基于图模型来完成的，用每个用户元组或项目元组作为图的顶点，这样评分矩阵R可使用图2来描述。
        在Spark框架下的并行化，不同于Hadoop 的并行化，Hadoop 中，每个任务需要写一个MapReduce程序，那么实现一个需要多次MapReduce的操作就需要编写多个MapReduce任务实现并行处理；而在Spark中，并行化主要是通过能对其进行并行操作的分布式数据集RDD实现的。在需要并行化的时候，将数据按照指定的分片个数封装在RDD中不同的分区，然后对RDD进行map、 filter、union等并行数据集的互相转化操作，如图3所示，RDD中不同的数据分区便可实现数据的并行处理。对于矩阵分解的并行化，主要是通过设定RatingsOfUserBlock和RatingsOfItemBlock的分区数进行的。由图3可看出，在进行迭代计算时，用户对于项目的评分位于用户与项目交互的边上，评分时首先需要计算参数梯度，例如：l11p1和l11q1，其中：lui=12（puqTi-rui）2；然后，将这两个梯度更新的信息，也即用户或项目的因子矩阵更新信息发送给需要的顶点，即UpdateSendList中包含的顶点，在此图中接收的顶点为U1和V1，在各个顶点需要将接收到的所有梯度信息汇总，形成∑（u，i）∈klui，再进行用户或者项目因子矩阵更新，即Update user或Update Item。
        2.2Spark框架下的矩阵分解并行化算法
        代码中：第1）～2）行初始化了参数、初始化了SparkContext；第4）行按分区数partiti
onNum分片生成了用户、项目因子矩阵；第8）～12）行迭代更新了用户因子矩阵和项目因子矩阵，其中第10） 行将更新信息发给了目标因子矩阵。
        3实验结果分析
        依据上述研究，用3台配备了Intel Core双核主频为3.00GHz、 内存为2GB、 硬盘为160GB的计算机作为硬件配置。实验环境信息为：操作系统Ubuntu12.10，Spark版本1.2.0。
        实验采用来自GroupLens（http：//uplens. org）网站的MovieLens作为数据源，文中使用了ml100k的数据包，其中包括了并行计算框架943个用户对 1682部电影的90571条评分记录。从数据包中分别选取50、200、400、800和943个用户作为实验数据，得出在不同节点下算法的运行时间，如图4所示。
        从图4可看出，对于同规模的数据集，增加节点的数量可以减少运行时间，提高算法的执行效率，而且用户数据集越大，Spark集的耗时增长更趋平滑，这体现了Spark基于内存计算的实时性优势。同时，对于同一数据集2节点与单节点的运行时间差小于2节点与3节点
的时间差，这是因为两个节点的Spark集包括一个Master节点和Slave节点，Master节点除了负责计算任务外还需要负责集的任务分配。
        实验采用Speedup[14]衡量同一数据集下增加节点时并行算法的表现。
        Speedup（p）=T1/Tp； p=1，2，… （3）
        其中：T1为单个节点执行任务的时间；Tp为p个节点执行任务的时间。理想情况下依次增加节点时（如从1个节点增加到3个节点）Speedup与直线y=x重合。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。