随着互联网的普及和电子商务的发展，推荐系统逐渐成为电子商务IT技术的一个重要研究内容，得到越来越多研究者的关注[1]。例如，Amazon、CDNOW、e－Bay、京东等电子商务网站，都开始逐渐引入了各种形式的推荐系统。协同过滤推荐是当今被广泛使用的推荐技术[4]，其中，潜在因素模型（latentfactormodels）是协同过滤推荐使用的技术之一。潜在因素模型是通过分析消费历史记录来推测潜在的发展趋势。矩阵分解算法（matrixfactorization）[2]
是潜在因素模型中被广泛使用的技术之
一。但是，随着网站消费记录的增多，传统的矩阵分解算法不能高效地为大规模消费记录构建潜在因素模型，无法实现推荐系统的实时性。本文针对大规模历史消费记录，提出了高效地特征矩阵分解算法，该算法是
收稿日期：2012-12-21作者简介：张海建（1978-），男，北京人，硕士，讲师，主要研究方向：计算机软件，数据库系统。
分布式矩阵分解算法在推荐系统中的研究与应用张海建（北京信息职业技术学院，北京100018）
摘要：随着互联网信息技术的高速发展，越来越多的人开始接触网络。网上购物成为当今社会的购物的主要方式之一，各大电子商务网站每天都有大量的消费者购买及浏览记录。电子商业往往希望通过分析大量的网站购买记录以及消费者浏览记录，对消费者提供有价值地商品推荐，以便于提高销售量。矩阵分解广泛地应用在推荐系统中的协同过滤算法中，但是，随着网站数据量的增大，传统的矩阵分解算法不能有效地处理这些大规模海量数据。本文针对推荐系统中大规模的网站数据，提出了基于云平台的分布式矩阵分解算法，该算法能够分布式完成推荐系统中的协同过滤过程。实验结果表明，本文提出的算法能够高效地完成推荐系统中的协同过滤，并且，该算法具有很好的可扩展性。关键词：推荐系统；分布式；云平台；mapReduce；矩阵分解；协同过滤
中文分类号：ＴＰ３文献标识码：Ａ文章编号：1001-7119（2013）12-0151-03TheResearchandApplicationofDistributedMatrixFactorizationAlgorithminRecommendSystem
ZhangHaijian(BeijingInformationTechnologyCollege,Beijing100018,China)
Abstract:Withthehigh-speeddevelopmentofinternetinformationtechnology,moreandmorepeoplebegintogetintouchwithinternet.On-lineshoppingisbecomingoneofthemainshoppingmethods,severalbige-commercesitespro－
ducebigamountofconsumerpurchasingandbrowsingrecords.E-commercesitesusuallyhopetoanalyzetheserecordsandprovidetotheconsumerswithvaluablecommodityrecommendation,inordertopromotesales.Matrixfactorizationispopularlyusedincollaborativefilteringalgorithminrecommendationsystem.However,withtheincensementofwebdata,traditionalmatrixfactorizationcouldnotdealwiththishugeamountofdata.Inthispaper,focusingonbigscalewebsitedata,weproposedistributedmatrixfactorizationbasedonCloudcomputingplatform.Throughtheexperimentalresults,thealgorithminthispapercouldcompletecollaborativefilteringinrecommendationsystemeffectively,andithasgoodscalability.Keywords：recommendersystems;distributed;cloudplatforms;mapReduce;matrixdecomposition,andcollaborativefiltering
第29卷第12期2013年12月
科技通报BULLETINOFSCIENCEANDTECHNOLOGYVol.29No.12Dec.2013技通报科第29卷
基于MapReduce[5]分布式云计算平台[7]，能够高效、快速地完成潜在因素模型的构建。实验结果进一步表明，本文提出的算法具有很高的加速比，并且有很好的可扩展性。
1矩阵分解算法矩阵分解模型中，引入一组二进制值pui,pui代表用户u对项目i的偏好：
pui=1ulikei0udislikei如果用户u已经购买了项目，那么令pui=1，否则，令
pui=0。在购买历史记录中，不存在pui=0的样本值，因此该矩阵分解算法只能用于对正训练数据进行推荐。在矩阵分解模型中，偏好度被假定为内积形式：pui=xTuyi。矩阵分解模型的目标是求解向量xu和yi满足最
小化训练数据的预测错误平方值。用户因素和项目因素是通过最小化如下方程求解的：minx*,y*
∑（u,i）∈R（pui-xTuyi）2+λ（∑u||xu||2+∑i||yi||2
）
其中，λ是正则化参数，用于防止过拟合问题。通过固定用户参数或者项目参数，成本函数变为二次方程，因此该问题转化为最小平方优化问题，步骤如下：首先，通过重新计算用户因素xu最小化如下成本方程：xu=（YTY+λI）-1YTp（u）其中，p(u)包含所有用户u的购买项目记录。然后，通过相同的方法重复计算项目因素：yi=（XTX+λI）-1XTp（i）通过迭代重复计算项目因素和用户因素xu和yi，矩
阵分解模型将p赞ui中top-N项目推荐给用户u，其中p赞ui代表用于u对项目i的预测偏好度。
2分布式矩阵分解算法通过前面的介绍，可以看出算法的执行时间与矩阵相乘有关，并且与因式分解的个数相关，如果矩阵X的维度非常大，那么大矩阵相乘问题将严重影响算法的执行时间。本节部分针对大规模数据计算矩阵相乘求解慢问题，基于MapReduce分布式计算平台，设计分布式矩阵分解算法。下面，详细介绍算法的执行流程。（1）将数据集平均分配到各个不同节点中，即将初始化矩阵X，Y平均分配到K的个计算节点中，每个计算节点的子矩阵表示为：Y1，Y2,..,Yk;X1，X2,..,Xk。并且，
将p(u)和p(i)的信息传递到各个计算节点。（2）每个计算节点中，分别求解子矩阵转置与该子矩阵的乘积，即：YTkY,XTkX以及YTkp（u）和XT
kp（i）
。
（3）当所有计算节点计算完毕后，将所有的计算结果YTkY,XTkX做和作为YTY和XTX
最终的结果；同时，将
YTkp（u）和XTkp（i）结果按照列号合并，最为最终的矩阵结果。（4）对YTY和XTX分别求逆运算，与矩阵和XTp（i）
分别相乘，求解出相应的xu和yi。迭代步骤(2)、(3)、(4)，直
至收敛为止，完成最小化成本函数求解。
（5）将最终的xu转置和yi相乘，得出预测p赞ui，并将top-N项目推荐给用户u。下面是基于MapReduce的分布式矩阵分解算法的伪代码：Input：User-FactorMatrixX,Item-FactorMatrixY,p(u),p(i)
Output:p赞uiMapperProgram:
图1可扩展性测试结果Fig.1ScalabilityTestingResults
表1实验数据描述Table1ExperimentalDataDescription数据集名称D1D2D3D4D5D6记录条数1,000,0002,000,0004,000,0008,000,00010,000,00012,000,000
表2算法执行时间比较Table2AlgorithmRunningTimeComparison
实验数据D1D2D3D4D5D6分布式矩阵分解（D-MF）执行时间/s3867781523312336704632传统算法（T-MF）执行时间/s48251058019296409114660959289加速比12.513.612.6713.112.712.8
152第12期1:foreachnodek2:compute(YTkY,XTkX);3:compute(YTkp（u）和XTkp（i）);4:endfor5:ItermediateResult=store(k,YTkY,XTkX,YTkp（u）,
XTkp（i）);ReducerProgram:1:foreachkeyk2:YTY=Matrix_Add(YTkY)3:XTX=Matrix_Add(XTkX)4:YTp（u）=Matrix_Combine(YTkp（u）)5:XTp（i）=Matrix_Combine(XTkp（i）))6:xu=Compute(YTY,YTp（u）)7:yi=Compute(XTX,XTp（i）)ControllerProgram:1:InitializeX,Y,p(u),p(i)2:DistributeX,Y,p(u),p(i)toKnodes3:Transmitdatatomappers4:StartMapper5:StartReducer6:while(|Ccurrent-Cbefore|>β){7:repeat4),5)8:}9:Store(xu,yi)=Output(Reducer)
10:p赞ui=MatrixMulti(xu,yi)
3实验结果实验部分的数据集是使用公开的互联网消费记录中获取的，其中数据集的记录格式如下所示：用户ID项目ID数量时间戳每条记录描述了用户购买某一项目的数目以及时间。表1详细地描述了使用的大规模数据的信息。由于本文是基于分布式计算框架，本文的所有计算都是基于最新版本的Hadoop[6]-0.20.2做为MapRe－
duce分布式编程环境。本文的实验环境是分布式云计算平台，该平台含有20个运算节点，每个节点的配置为：4.0Hz的Intel处理器，32G内存，CentOsLinux操作系统。本文的实验分为两个部分，第一部分测试分布式矩阵分解加速比，主要测试分布式矩阵分解算法（D-MF）与传统算法（T-MF）在执行时间上的比较。表2描述了分布式算法在20个计算节点上对6组实验数据的执行时间和传统矩阵分解算法的执行时间，以及加速