矩阵ubuntu12.10

JournalofComputerApplicationsISSN1001-90812015-【-10计算机应用,2015,CODENJYIIDUhttp://www.
joca.
cn收稿日期:2015-6-17;修回日期:2015-7-6.
作者简介:郑凤飞(1990-),男,甘肃会宁,硕士研究,主要研究方向:云计算技术;黄文培(1967-),男,陕西西安,副教授,博士,主要研究方向:信息安全、网络安全;贾明正(1990-),男,硕士研究生,主要研究方向:数据挖掘、云计算.
基于Spark的矩阵分解推荐算法郑凤飞*,黄文培,贾明正(西南交通大学信息科学与技术学院,成都611756)(*通信作者电子邮箱1207264887@qq.
com)摘要:针对传统矩阵分解算法在处理海量数据信息时所面临的处理速度和计算资源的瓶颈问题,利用Spark在内存计算和迭代计算上的优势,提出了Spark框架下的矩阵分解并行化算法.
首先,依据历史数据矩阵初始化用户因子矩阵和项目因子矩阵;其次,迭代更新因子矩阵,将迭代结果置于内存中作为下次迭代的输入;最后,迭代结束时得到矩阵推荐模型.
通过在GroupLens网站上提供的MovieLens数据集上的实验表明,Speedup值达到了线性的结果,该算法可以提高协同过滤推荐算法在大数据规模下的执行效率.
关键词:协同过滤;推荐算法;矩阵分解;迭代最小二乘法;Spark中图分类号:TP301.
6(算法理论)文献标志码:ARecommendationAlgorithmwithMatrixFactorizationMethodBasedonSparkZHENGFengfei*,HUANGWenpei,JIAMingzheng(SchoolofInformationScienceandTechnology,SouthwestJiaotongUniversity,Chengdu611756,China)Abstract:Inordertosolvethebottleneckproblemsofprocessingspeedandresourceallocation,asparkbasedmatrixfactori-zationrecommendationalgorithmwasproposed.
Firstly,userfactormatrixanditemfactormatrixwereinitializedaccordingtohistorydata;Secondly,factormatrixwereiterativelyupdatedandtheresultwerestoredinmemoryastheinputofnextiteration;Finally,recommendationmodelweregeneratedwheniterationended.
TheexperimentonMovieLensshowsthatthespeedupwaslinerandsparkbasedalgorithmcansavetimeandsignificantlyimprovetheexecutionefficiencyofcollaborativefilteringrecommendationalgorithm.
Keywords:collaborativefiltering;recommendationalgorithm;matrixfactorization;alternatingleastsquare;Spark0引言随着互联网的迅猛发展,为了满足人们在繁多的信息中获取自己需要内容的需求,个性化推荐应用而生.
协同过滤推荐[1]是其中运用最为成功的技术之一.
其中,基于用户的最近邻法根据相似用户的评分来预测当前用户的评分[2].
然而,在用户数量以及用户评分不足的情况下,该方法存在冷启动和数据稀疏的问题.
文献[3]中提出了基于项的最近邻法,利用项之间相似性稳定的特点可以离线计算相似性,降低了在线计算量,提高了推荐效率,但同样存在冷启动和数据稀疏问题.
文献[4]使用矩阵分解中的奇异值分解(SingularValueDecomposition,SVD)减少评分矩阵的维数,之后应用最近邻法预测评分,一定程度上解决了同义词问题,但由于评分矩阵中大部分的评分是分解之前填充的,所以得到的特征矩阵不能直接用于评分.
文献[5]提出了一种基于矩阵分解和用户近邻模型的算法,解决了数据稀疏的问题,但存在模型过拟合的问题.
文献[6]提出了一种支持不完整评分矩阵的矩阵分解方法,不用对评分矩阵进行估值填充,有很好的推荐精度.
在Netflix推荐系统竞赛中的应用表明,该矩阵分解相比于其他的推荐算法能产生更精确的推荐[7].
在矩阵分解推荐算法中,每项评分预测都需要整合现有评分集的信息.
因此,随着用户数与项目数的增长,算法的计算量也会随着增长,单机模式的推荐算法逐渐难以满足算法的计算以及推送的即时性需求.
因此分布式推荐算法成为推荐算法中研究的一个新的方向.
文献[8,9]中提出了分布式的矩阵分解算法,为矩阵分解的并行计算提供了一种可行的解决方案,但其使用的MapReduce框架在各计算节点的迭代计算中会产生过多的文件读取操作,影响了算法的执行效率.
本文旨在将文献[6]中提出的矩阵分解推荐算法与专长于内存计算和迭代计算的Spark并行计算框架结合,探索矩2计算机应用第35卷阵分解算法在Spark上的实现,来解决大数据情况下矩阵分解推荐算法时间代价过高的问题.
1矩阵分解推荐算法与Spark平台1.
1矩阵分解推荐算法在协同过滤推荐中,输入数据可以用一个m行n列的评分矩阵R来表示,本文称之为User-Item矩阵.
1112121222123nnmmmmnRRRRRRRRRRR=""##%#其中,n表示项目数量,m表示用户数量,矩阵元素Rij表示用户i对项目j的偏好评估值,例如1~5分范围内,1代表很不喜欢,5代表很喜欢.
协同过滤中矩阵分解的目标是把用户和项目映射到同一个维数为f的潜在因子空间[10],这样用户与项目之间的关系就可以通过潜在因子空间中的内积来建模,如式(1)所示:TRPQ≈(1)其中,P是一个nu*f的矩阵(nu表示用户的数量,也即是矩阵R中横向量的个数,f表示因子个数,也即是低维矩阵的维数),Q是一个ni*f的矩阵(ni表示项目的数量).
我们称P为用户因子矩阵,Q为项目因子矩阵,则每个用户对应的向量为pu,每个项目对应的向量为qi.
矩阵分解的目标就是计算得到每个用户的因子向量pu和每个项目的因子向量qi,使得预测用户u对项目i感兴趣的程度uTuiipqr=能够尽可能的接近真实评分rui.
当给定的矩阵不完全时,此模型容易导致过拟合,因此,当前的很多研究都建议仅对存在的评分项进行建模,采用正则化[6]6-7模型避免过拟合问题,目标函数定义如式(2):22minnuipquikTuiuirpqpqλ∈++∑2||)(2)其中,λ参数用来正则化模型,称为正则化系数,k代表训练集中存在的评分项,求解上面的模型,目前常用的方法有两种:随机梯度下降法[11](SGD,stochasticgradientdescent)和交替最小二乘迭代法(ALS,alternatingleastsquares)[12].
1.
2Spark平台Spark是UCBerkeleyAMPLab开源的通用并行计算框架[13].
该框架提出了内存集群计算,通过将数据集缓存到内存中,减少数据的I/O操作,从而提高数据的读写速率.
Spark创新的提出了ResilientDistributedDataset(RDD)弹性分布数据集[14].
RDD本质是自定义的可并行的数据容器,不同的数据集格式对应不同类型的RDD.
弹性表现在若一个RDD分片丢失,Spark可以根据日志信息重构它;分布式表现在可以用操作本地集合的方式来操作分布式数据集.
此外,RDD可以被缓存在内存中,在之后的计算过程中可以直接从内存中读入,省去了大量的磁盘存取开销,适合需要迭代计算的矩阵分解算法.
图1显示了Spark的基本工作流程,每个SparkApplication都有自己的Executor进程,进程的生命周期和整个Application的生命周期相同,而且其内部维持着多个线程来并行的执行分配给它的Task.
这种运行模式有利于进行不同Application之间的资源、调度隔离.
SparkExecutorClusterManagerSparkContextSparkExecutor图1Spark基本工作流程图2基于spark矩阵分解并行化2.
1Spark下算法描述对于目标函数式(1),交替最小二乘方法在求解时可以固定P求解Q,然后再固定Q求解P,重复交替这两步直至算法收敛.
在实现上,SGD方法比ALS方法更容易实现,而且能够更快收敛,但是ALS算法更易于并行化,因此本文采用ALS算法.
本文中基于Spark的矩阵分解并行化,主要是基于图模型来完成的,用每个用户元组或项目元组作为图的顶点,这样评分矩阵R可使用如下二部图来描述,如图2所示:U1UserFactorItemFactorU2U3v1v2表示实际交互表示消息发送图2基于Spark的矩阵分解图示在Spark框架下的并行化,不同于Hadoop的并行化,Hadoop中,每个任务需要写一个MapReduce程序,那么实现一个需要多次MapReduce的操作就需要编写多个MapReduce任务实现并行处理.
而在Spark中,并行化主要是通过能对其进行并行操作的分布式数据集RDD实现的.
在需要并行化的时候,将数据按照指定的分片个数封装在RDD中不同的分区,然后对RDD进行map、filter、union等并行数据集的互相转化操,如图3所示,RDD中不同的数第*期郑凤飞等:基于Spark的矩阵分解推荐算法3据分区便可实现数据的并行处理.
对于矩阵分解的并行化,主要是通过设定RatingsOfUserBlock和RatingsOfItemBlock的分区数进行的.
由图3可以看出,在进行迭代计算时,用户对于项目的评分位于用户与项目交互的边上,评分时首先需要计算参数梯度,例如111lp和111lq(其中21()2Tuiuiuiplqr=),然后将这两个梯度更新的信息,也即用户或项目的因子矩阵更新信息发送给需要的顶点,即UpdateSendList中包含的顶点,在此图中接收的顶点为U1和V1,在各个顶点需要将接收到的所有梯度信息汇总,形成,再进行用户或者项目因子矩阵更新,即Updateuser或UpdateItem.
(,)uiuikl∈∑Map,filterunoin图3RDD分区操作示意图2.
2Spark框架下的矩阵分解并行化算法输入:评分数据及Ratings输出:矩阵分解模型1.
varpartitionNum//分区个数2.
varsc=newsparkContext()3.
读入数据生成Ratings:RDD[Rating],Rating是序列4.
依据用户设置或者默认的并行化数生成RatingsOfUserBlock和RatingsOfItemBlock的RDDRatingOfUserBlock:Ratingmap→RatingsOfItemBlockRatingmap→5.
生成基于User或者Item的InLinkRDD(内连接信息)和OutLinkRDD(外连接信息);6.
将内外连接信息缓存在内存中,避免重复计算;7.
以各自外连接信息初始化用户和项目的因子矩阵OutLink{(index,itr)itermap→(x,y)}mapPartition→8.
WhileiterUbuntu12.
10,Spark版本1.
2.
0.
实验采用来自GroupLens[15]网站的MovieLens作为数据源,文中使用了ml-100k的数据包,其中包括了943个用户对1682部电影的90571条评分记录.
从数据包中分别选取50、200、400、800和943个用户作为实验数据,得出在不同节点下算法的运行时间,如图4所示.
00.
30.
60.
91.
21.
51.
82.
12.
402004006008001000运行时间/min用户数(无单位)单节点2节点3节点图4并行化运行时间比较从实验结果图中可以看出,对于同规模的数据集,增加Slave节点的数量可以减少运行时间,提高算法的执行效率,而且用户数据集越大,Spark集群的耗时增长更趋平滑,这体现了Spark基于内存计算的实时性优势.
同时,对于同一数据集2节点与单节点的运行时间差小于2节点与3节点的时间差,这是因为两个节点的Spark集群包括一个Master节点和Slave节点,Master节点除了负责计算任务外还需要负责集群的任务分配.
实验采用Speedup[16]衡量同一数据集下增加节点时并行算法的表现.
1()1,2,.
.
.
.
pSpeeduppTTp==(3)式(3)中,T1为单个节点执行任务的时间,Tp为p个节点执行任务的时间,理想情况下依次增加节点时(如从一个节点增加到3个节点)Speedup与直线y=x重合.
从图5中可以看出本实验Speedup值达到了线性的结果,可以预期对更大规模的数据处理时,Speedup性能会进一步提升,表明该算法可以提高矩阵分解算法在大规模数据下的执行效率.
4计算机应用第35卷00.
30.
60.
91.
21.
5RMSE(无单位)非分布式分布式图5并行化性能比较实验采用RMSE作为评价标准[17],RMSE通过计算实际的用户评分与预测的用户评分与之间的偏差来衡量推荐的准确性.
其公式为:21()niiiprRMSEN==∑(4)其中,N为项目数量,pi为实际评分,ri为预测的分数,RMSE越小,代表算法的推荐精度越高.
本文实现的矩阵分解推荐算法与传统矩阵分解算法的RMSE比较如图7所示:00.
30.
60.
91.
21.
502004006008001000RMSE(无单位)用户数(无单位)非分布式分布式图6RMSE比较从图6中可以看出,在用户数据集相对较小,数据稀疏的条件下,本文分布式算法的推荐精度优势不明显,而随着用户数据集逐渐扩大算法的推荐精度逐渐提高,与传统矩阵分解算法的推荐精度基本相同.
这说明,本文提出的基于Spark的矩阵分解并行化算法可以适应海量数据背景下的推荐.
4结语本文介绍了传统矩阵分解算法和Spark云平台的概况,根据Spark的编程模型,将传统的矩阵分解推荐算法改进为适应Spark平台的并行矩阵分解推荐算法.
实验结果表明,基于Spark的矩阵分解推荐算法能带来较高的加速比,从而提高了矩阵分解算法在大规模数据下的执行效率.
但是也存在不足之处,在用户数据集相对稀疏的情况下,该算法的精度优势不明显,这说明该算法在应对数据稀疏方面还有待进一步的改进.
参考文献[1]LIUZB,QUWY,LIHT,etal.
AhybridcollaborativefilteringrecommendationmechanismforP2Pnetworks[J].
FutureGenerationComputerSystems,2010,26(8):1409–1417.
[2]BREESEJS,HECKERMAND,KADIEC.
Empiricalanalysisofpredictivealgorithmsforcollaborativefiltering[C],Proceedingsofthe14thConferenceonUncertaintyinArtificialIntelligence,NewYork:ACM,1998:43-52.
[3]SARWARB,KARYPISG,KONSTANJ,etal.
Item-basedcollabora-tivefilteringrecommendationalgorithms[C],Proceedingsofthe10thInternationalConferenceonWorldWideWeb.
NewYork:ACM,2001:285-295.
[4]VOZALISMG,MARGARITISKG.
ApplyingSVDonitem-basedfiltering[C],Proceedingsofthe5thInternationalConferenceonIntelligentSystemsDesignandApplications.
Washington,DC:IEEE,2005:464-469.
[5]YANGY,XIANGY,XIONGL.
Collaborativefilteringrecommendationalgorithmbasedonmatrixfactorizationusernearestneighbormodel[J],JournalofComputerApplications,2012,32(2):395-398.
(杨阳,向阳,熊磊.
基于矩阵分解与用户近邻模型的协同过滤推荐算法[J].
计算机应用,2012,32(2):395-398.
)[6]PATEREKA.
Improvingregularizedsingularvaluedecompositionforcollaborativefiltering[C],//ProceedingsofKDDCupandWorkshop.
NewYork:ACM,2007:5-8.
[7]NETFLIX.
Netflixprize[EB/OL].
[2015.
1.
10].
http://www.
netflx.
com[8]GEMULLAR,HAASPJ,SISMANISY,etal.
Large-scalematrixfactorizationwithdistributedstochasticgradientdescent[J],.
KDD,2011:69--77.
[9]ZHANGY,CHENGJJ.
StudyonrecommendationalgorithmwithmatrixfactorizationmethodbasedonMapReduce[J].
ComputerScience,2013,40(1):19-18.
(张宇,程久军.
基于MapReduce的矩阵分解推荐算法研究.
计算机科学,2013,40(1):19-21)[10]KORENY,BELLR,VOLINSKYC.
Matrixfactorizationtechniquesforrecommendersystems[J].
Computer,2009,42(8):30-37.
[11]TAKACSG,PLIASZYI,NEMETHB,etal.
Investigationofvariousmatrixfactorizationmethodsforlargerecommendersystems[C]//ProceedingsoftheIEEEInternationalConferenceonDataMiningWorkshops.
WashingtonDC:IEEE,2008:553-562.
[12]PILASZYI,ZIBRICZKYD,TIKKD.
Fastals-basedmatrixfactorizationforexplicitandimplicitfeedbackdatasets[C]//ProceedingsofthefourthACMconferenceonrecommendersystems.
NewYork:ACM,2010:71-78.
[13]JONESMT.
Spark,analternativeforfastdataanalytics[EB/OL].
[2015.
1.
10].
http://www.
ibm.
com/developerworks/library/os-spark/.
[14]ZAHARIAM,CHOWDHURYM,DAST,etal.
Resilientdistributeddatasets:afault-tolerantabstractionforin-memoryclustercomputing[D].
California:UniversityofCalifornia,2011.
[15]GROUPLENS.
Grouplens[EB/OL].
[2015.
1.
20].
http://www.
grouplens.
org.
[16]ZHANGJ,LIT,DAR,etal.
Aparallelmethodforcomputingroughsetapproximations[J].
InformationSciences,2012,194(5):209–223.
[17]RICCIF,ROKACHL,SHAPIRAB,etal.
RecommenderSystemsHandbook[M].
Germany:Springer,2011:109.