推荐系统是根据用户现在的兴趣,预测用户将来可能感兴趣的物品,并推荐给用户[1]。根据推荐算法不同,可以分为:基于内容的推荐(Content-based Recommendation)算法、协同过滤和混合推荐[2]。协同过滤算法主要是利用用户-物品评分矩阵分析用户兴趣,在用户群中找到与目标用户兴趣相似的用户,综合这些用户对某一物品的评分,形成目标用户对该物品喜好程度的预测。协同过滤推荐算法主要的阶段是近邻集合的查找,其准确率直接影响到推荐的准确率。在实际的电子商务系统和视频网站系统中(比如Amazon、NetFlix等),用户和物品种类的数量都非常巨大,这对于协同过滤算法准确率和效率都是非常大的挑战。
目前协同过滤算法主要面临以下几点问题:1)数据稀疏性是制约协同过滤推荐算法准确率的最主要问题。用户对物品评分的数量较少,造成用户-物品评分矩阵非常稀疏。在这种情况下,用户之间共同评分的物品数量少,计算出的最近邻居用户集合质量不高,会造成推荐的准确率低。2)算法的可扩展性是制约推荐系统实施的重要因素。协同过滤算法面对日益增加的用户维度和物品维度时,用户间相似性计算的耗费也很大,这样会导致算法遇到严重的扩展性问题。3)大数据背景下,系统难以及时响应用户的请求,影响用户的实时性体验。
为了解决上述问题,提出基于边界矩阵低阶近似(Bounded Matrix low rank Approximation, BMA)和近邻模型的协同过滤并行化算法(Collaborative Filtering algorithm based on BMA and Nearest neighbor model, BMAN-CF)。BMAN-CF是根据实际推荐系统的评分范围,将评分矩阵R分解为子矩阵P和Q,降低矩阵维度和稀疏性;挖掘子矩阵中P、Q中的隐含特征,提高近邻集合查找准确率;综合考虑用户和物品对预测结果的影响,利用平衡因子动态平衡两种协同过滤算法的预测结果,得到最终的预测结果。
1 相关工作协同过滤推荐算法主要分为基于内存的协同过滤算法和基于模型的协同过滤算法两类。
基于内存的协同过滤算法分为4个过程:1)构建用户-物品评分矩阵;2)计算用户(物品)间相似度;3)查找近邻集合;4)预测用户对物品的评分。文献[3]利用典型性相关概念对物品和用户进行聚类降低数据稀疏性,提高了预测准确率;文献[4]将隐式数据作为用户积极或者消极偏好的指示,与置信度联系起来,训练出针对隐式反馈推荐的因子模型降低数据稀疏性;文献[5]使用关联检索框架和相关的实际算法,根据用户历史反馈来探索用户间的传递性关联,用这种传递性关联来描述用户的兴趣,从而解决数据稀疏性的问题。
基于模型的协同过滤算法利用用户历史行为,依托机器学习或数据挖掘算法来构建用户兴趣模型,利用该模型为用户推荐物品。此类算法构建用户兴趣模型需要耗费大量时间,但在建立用户兴趣模型后,数据规模明显降低,所以可以离线训练模型,在线推荐及时响应用户请求。基于模型协同过滤算法主要有隐语义模型、贝叶斯分类、神经网络等,隐语义模型由于高预测精度成为目前使用较为广泛的技术。文献[6]提出基于转移学习的方法,利用变分期望最大化(Variational Expectation-Maximization, VEM)来学习出概率矩阵分解模型,利用多方面具有密集数据的辅助信息来解决数据稀疏问题,实验结果证明该算法在每个用户只对一个物品评分时能得到最好的效果;文献[7]提出用概率矩阵分解来填充用户-物品评分矩阵,然后融合基于用户的协同过滤和基于物品的协同过滤,但该算法以固定的权重融合基于用户和基于项目预测的评分值,忽略了用户和物品间的关系,并且不同的数据集权值分配差别很大;文献[8]将流形正则化与矩阵分解结合构成新模型,此模型有全局最优和封闭形式的解决方法,使用交替迭代和不精确的内部迭代来求解新模型,对矩阵分解算法效率和准确率都有很大的提升。
2 BMAN-CF设计非负矩阵分解(Nonnegative Matrix Factorization, NMF)是针对实际应用中矩阵元素为负数没有意义而提出的,但在推荐系统中用户-物品评分矩阵元素不仅非负,还有固定的评分区间。矩阵分解算法在应用到推荐系统时,将超过评分区间的预测评分设为区间的最大值,这会限制预测准确率。而边界矩阵低阶近似根据实际推荐系统的评分区间确定近似矩阵PQ元素的一个上界和一个下界,而不仅仅在子矩阵P、Q的元素上保证非负[9]。
2.1 边界矩阵分解边界矩阵分解主要是将原始用户-物品评分矩阵Rn*m分解为两个低阶矩阵Pn*k和Qk*m,P和Q分别由列向量px和行向量qxT组成,接下来详细介绍近似矩阵元素在评分区间的界定下,如何通过最小化目标函数来求解列向量px和行向量qxT,即式(1):
$ \begin{array}{l} \mathop {\min }\limits_{{\mathit{\boldsymbol{p}}_x}, {\mathit{\boldsymbol{q}}_x}^{\rm{T}}} \;\;\;\;||\mathit{\boldsymbol{M}} \cdot *{\rm{(}}\mathit{\boldsymbol{R}}- \mathit{\boldsymbol{T}}- {\mathit{\boldsymbol{p}}_x}{\mathit{\boldsymbol{q}}_x}^{\rm{T}}{\rm{)}}||_F^{\rm{2}};\\ \;\;\;\;\forall x = {\rm{[1, }}k{\rm{], }}\mathit{\boldsymbol{T}} = \sum\limits_{j = 1, j \ne x}^k {{\mathit{\boldsymbol{p}}_j}{\mathit{\boldsymbol{q}}_j}^{\rm{T}}} \\ {\rm{s}}{\rm{.}}\;{\rm{t}}{\rm{.}}\;\;\mathit{\boldsymbol{T}} + {\mathit{\boldsymbol{p}}_x}{\mathit{\boldsymbol{q}}_x}^{\rm{T}} \le {r_{\max }}, \;\;\mathit{\boldsymbol{T}} + {\mathit{\boldsymbol{p}}_x}{\mathit{\boldsymbol{q}}_x}^{\rm{T}} \ge {r_{\min }} \end{array} $ | (1) |
假设px,已知根据px求解qxT。为了不失一般性,固定px求解qxT的情景同样适用于固定qxT求解px, 这样就会产生两种不同的更新策略:p1→q1T→…→pk→qkT和p1→…→pk→q1T→…→qkT。
根据文献[10]对不同损失函数如何选择相应更新策略作出的说明,本文算法选择交替更新px和qxT策略。本文算法利用块坐标下降算法来迭代求解问题,从块坐标下降算法性质中可以发现,qxi、qxj∈qxT是相互独立的,计算qxi并不影响元素qxi求解过程,qxT中其他元素的求解方法相同。qxi的计算过程如图 1所示。
固定px求解qxi就可以转换为式(2)定义的目标函数。求解qxi的问题可以转换为求解目标函数极小值的问题,也就是目标函数对qxi的导数为0,求导过程为式(3)。导数为0时可以得到
$ \begin{array}{l} f{\rm{(}}{q_{xi}}{\rm{)}} = \mathop {\min }\limits_{{q_{xi}}} ||\mathit{\boldsymbol{M}}{\rm{(}}:, \;i{\rm{)}} \cdot *{\rm{((}}\mathit{\boldsymbol{R}}- \mathit{\boldsymbol{T}}{\rm{)(}}:, \;i{\rm{)}}- {\mathit{\boldsymbol{p}}_x}{q_{xi}}{\rm{)}}||_F^{\rm{2}};\\ \;\;\;\;\forall i = {\rm{[1}}, \;m{\rm{]}}, \;\forall x = {\rm{[1}}, \;k{\rm{]}} \end{array} $ | (2) |
$ \begin{array}{l} {\rm{s}}{\rm{.}}\;{\rm{t}}{\rm{.}}\;\;\mathit{\boldsymbol{T}}{\rm{(}}:, i{\rm{)}} + {\mathit{\boldsymbol{p}}_x}{\mathit{\boldsymbol{q}}_{xi}} \le {r_{\max }}, \mathit{\boldsymbol{T}}{\rm{(}}:, i{\rm{)}} + {\mathit{\boldsymbol{p}}_x}{q_{xi}} \ge {r_{\min }}\\ \;\;\;\;\;\frac{{\partial f}}{{\partial {q_{xi}}}} = \frac{\partial }{{\partial {q_{xi}}}}\left( {\sum\limits_{{\rm{all}}\;{\rm{known}}\;{\rm{ratings}}\;{\rm{in}}\;{\rm{column}}\;i}^{} {{{{\rm{(}}{\mathit{\boldsymbol{E}}_i}- {\mathit{\boldsymbol{p}}_x}{q_{xi}}{\rm{)}}}^{\rm{2}}}} } \right){\rm{(}}\mathit{\boldsymbol{E}} = \mathit{\boldsymbol{R}}- \mathit{\boldsymbol{T}}{\rm{)}} = \\ \;\;\;\;\;\;\;{\rm{2}}||\mathit{\boldsymbol{M}}{\rm{(}}:, \;i{\rm{)}} \cdot *{\mathit{\boldsymbol{p}}_x}||_{\rm{2}}^{\rm{2}}{q_{xi}}\;- \;\\ \;\;\;\;\;\;\;{\rm{2[}}\mathit{\boldsymbol{M}}{\rm{(}}:, \;i{\rm{)}} \cdot *{\rm{(}}\mathit{\boldsymbol{R}}-\mathit{\boldsymbol{T}}{\rm{)(}}:, \;i{\rm{)}}{{\rm{]}}^{\rm{T}}}{\mathit{\boldsymbol{p}}_x} \end{array} $ | (3) |
$ {{\hat q}_{xi}} = \frac{{{{{\rm{[}}\mathit{\boldsymbol{M}}{\rm{(}}:, \;i{\rm{)}} \cdot * {\rm{(}}\mathit{\boldsymbol{R}}-\mathit{\boldsymbol{T}}{\rm{)(}}:, \;i{\rm{)]}}}^{\rm{T}}}{\mathit{\boldsymbol{p}}_x}}}{{||\mathit{\boldsymbol{M}}{\rm{(}}:, \;i{\rm{)}} \cdot *{\mathit{\boldsymbol{p}}_x}||_{\rm{2}}^{\rm{2}}}} $ | (4) |
在计算
$ l_j = \left\{ \begin{array}{l} \left[{{r_{\min }}-T{\rm{(}}j, \;i{\rm{)}}} \right]/{p_{jx}}, \;\;\;\;{p_{jx}} > 0\\ \left[{{r_{\max }}-T{\rm{(}}j, \;i{\rm{)}}} \right]/{p_{jx}}, \;\;\;\;{p_{jx}} < 0\\ -\infty, \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;其他 \end{array} \right. $ | (5) |
$ {u_j} = \left\{ \begin{array}{l} \left[{{r_{\max }}-T{\rm{(}}j, \;i{\rm{)}}} \right]/{p_{jx}}, \;\;\;\;{p_{jx}} > 0\\ \left[{{r_{\min }}-T{\rm{(}}j, \;i{\rm{)}}} \right]/{p_{jx}}, \;\;\;\;{p_{jx}} < 0\\ \infty, \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;其他 \end{array} \right. $ | (6) |
$ {\hat q_{xi}} = \left\{ \begin{array}{l} \max {\rm{(}}\mathit{\boldsymbol{l}}{\rm{)}}, \;\;\;{{\hat q}_{xi}} < \max {\rm{(}}\mathit{\boldsymbol{l}}{\rm{)}}\\ \min {\rm{(}}{\bf{u}}{\rm{)}}, \;\;\;\hat q{}_{xi}\; > \min {\rm{(}}\mathit{\boldsymbol{u}}{\rm{)}}\\ {{\hat q}_{xi}}, \;\;\;\;\;\;\;\;\;\;其他 \end{array} \right. $ | (7) |
交替求解矩阵P和矩阵Q的各个向量,从而完成算法的一次迭代,当迭代结果符合结束条件时停止迭代,最终得到分解后的矩阵P和矩阵Q,满足R≈P×Q。
这里面的结束迭代条件有必要说明一下。由文献[12]可知,迭代停止标准应该是对于给定低阶阶数k,低阶子矩阵P与Q的乘积应该接近原有矩阵R的阶数。所以可以定义停止迭代标准ε如式(8):
$ \varepsilon = \sqrt {\frac{{\left\| {\mathit{\boldsymbol{M}}*(\mathit{\boldsymbol{R}}-\mathit{\boldsymbol{PQ}})} \right\|_F^2}}{{numRatings\;{\rm{in}}\;\mathit{\boldsymbol{R}}}}} $ | (8) |
当取浮点数精度为1E-5时,在精度范围内,迭代标准ε在成功迭代之后不再发生变化,此时迭代结束。
2.2 推荐列表计算 2.2.1 相似用户查找接下来充分挖掘子矩阵P、Q的隐含特征,矩阵P和Q的潜在特征可以描述为,矩阵Pn*k每行可以看成用户对k个特征的喜爱程度,矩阵Qk*m每列可以看成物品对k个属性的拥有程度。这样通过对k个特征喜爱程度和k个属性拥有程度的差异来计算用户间和物品间的相似度。在矩阵P上利用挖掘出的隐语义特征来查找目标用户u的近邻集合Nu,在矩阵Q上利用挖掘出的隐含义属性查找目标物品i的近邻集合Ni。
2.2.2 物品评分预测根据用户u的近邻集合Nu,利用传统基于用户的协同过滤算法和式(9)可以计算出目标用户u对物品i的评分Pu:
$ {P_u} = \overline {{r_{{N_a}(u)}}} + \frac{{\sum\limits_{v \in {N_a}(u)} {Sim{\rm{(}}u, \;v{\rm{)}} \cdot {\rm{(}}{r_{v, i}}-\overline {{r_v}} {\rm{)}}} }}{{\sum\limits_{v \in {N_a}(u)} {Sim{\rm{(}}u, \;v{\rm{)}}} }} $ | (9) |
然后根据物品i的近邻集合Ni,利用基于物品的协同过滤算法与式(10)可以计算出目标用户对物品i评分Pi:
$ {P_i} = \overline {{r_i}} \; + \;\frac{{\sum\limits_{j \in {N_i}} {Sim(i, \;j) \times ({r_{u, j}}\;-\;\overline {{r_j}} )} }}{{\sum\limits_{j \in {N_i}} {Sim(i, \;j)} }} $ | (10) |
如果只使用基于用户的协同过滤或者只使用基于物品的协同过滤,容易忽略一些有用信息,所以本算法利用基于近邻的协同过滤算法,即同时从用户和物品两个角度考虑,分别预测用户u对物品i的评分,然后利用平衡因子来动态平衡两个预测评分。文献[11]提出使用系数λ将两个算法进行整合如式(11):
$ {P_{u, i}} = \lambda \times {P_u} + (1-\lambda ) \times {P_i} $ | (11) |
但是系数λ没有考虑用户间和物品间的内在相关性,为了进一步提升预测准确率,本算法采用平衡因子mu、mi和系数θ相结合的方法来动态平衡两种算法预测的评分[13]。mu、mi的计算方法为式(12):
$ \left\{ \begin{array}{l} {m_u} = \sum\limits_{v \in {N_u}} {\frac{{{{(Sim(u, \;v))}^2}}}{{\sum\limits_{v \in {N_u}} {Sim(u, \;v)} }}} \\ {m_i} = \sum\limits_{j \in {N_i}} {\frac{{{{(Sim(i, \;j))}^2}}}{{\sum\limits_{j \in {N_i}} {Sim(i, \;j)} }}} \end{array} \right. $ | (12) |
由于多个近邻用户与目标用户之间的相似度不同,平衡因子mu的作用就是得到一个能够用来代表用户间的相似度权值,同理mi是代表物品间相似度权值。根据平衡因子mu、mi和系数λ组合出新的系数tu和ti,计算方法如式(13):
$ \left\{ \begin{array}{l} {t_u} = \frac{{{m_u} \times \lambda }}{{{m_u} \times \lambda + {m_i} \times \left( {1-\lambda } \right)}}\\ {t_i} = \frac{{{m_i} \times \left( {1-\lambda } \right) }}{{{m_u} \times \lambda + {m_i} \times \left( {1-\lambda } \right)}} \end{array} \right. $ | (13) |
目标用户u对物品i的评分就可以转换为式(14),最终可以计算出用户u对未评分物品集合Iu中所有物品的评分,评分排序后将评分最高的Top-N个物品推荐给目标用户u,这样就完成了对用户u推荐列表的计算。
$ {P_{u, i}} = {t_u} \times {P_u} + {t_i} \times {P_i} $ | (14) |
BMA矩阵分解是利用块坐标下降迭代求解子矩阵,块坐标下降并行化思想应用到边界矩阵分解并行化就是,将初始化后的矩阵P和矩阵Q按照集群节点数分别进行列分块和行分块,得到P={P1, P2, …, Ps},Q={Q1, Q2, …, Qs}(s为集群节点个数);根据矩阵P和Q分块结果,将R分解为这样的形式:R=R1+R2+…+Rs,其中矩阵Ri依然是n行m列,这样就完成了参数集合和相应数据集的划分;并行化执行阶段每个Map任务都读入矩阵P和Q的一个分块Pi、Qi以及相应的数据集Ri,在Map函数中就可以利用2.1节的方法对Pi和Qi中的各个行列向量进行迭代更新,直到收敛为止,Reduce阶段的Reduce函数就是将各个Map的结果进行整合输出两个更新后的矩阵P和Q。边界矩阵分解MapReduce并行化流程如图 2所示。
推荐列表并行化是在获取到分解后的矩阵P和Q后,预测出用户对未评分物品的评分,然后将评分最高Top-N个物品推荐给用户。本并行化算法假设查找近邻集合时用户和物品都是独立的,基于这个假设可以直接利用MapReduce的特性对算法进行并行化。推荐列表计算MapReduce并行化的流程如图 3所示。进行评分预测之前需要找到目标用户未评分的物品集合,结果保存以〈TargetUserID, list〈TargetItemID〉〉形式保存在Hadoop分布式文件系统(Hadoop Distributed File System, HDFS)文件中。下面介绍利用矩阵P和矩阵Q进行评分预测得到Pu、Pi的数据流。
MapReduce(MR1)中Setup函数是用来读取第一步保存的文件,数据缓存格式为〈TargetUserID, list〈TargetItemID〉〉;Map阶段输入为矩阵P的一行,数据格式为〈UserID, list〈Feature, rate〉〉, 通过map函数计算用户间的相似度输出为〈TargetUserID, 〈UserID, Similarity〉〉;经过Shuffle后相同的TargetUserID会被送到同一个Reduce中,Reduce阶段reduce函数先将相似度排序,选取相似度最高的Top-k个相似用户作为近邻集合,根据式(4)预测目标用户对这些物品的评分,输出为〈TargetUserID, list〈TargetItemID, Rate〉〉。
3.2.2 利用矩阵Q预测评分MapReduce(MR2)与MR1Map和Shuffle操作类似,只是MR2中Map阶段输入的是矩阵Q的转置的一行。Reduce阶段reduce函数先将TargetItemID相同的数据聚集在一起,然后根据相似度大小为每个TargetItem选择Top-k个物品作为近邻集合,依次计算出目标用户对各个TargetItem的评分,输出为〈TargetUserID, list〈TargetItemID, Rate〉〉。
3.2.3 最终评分预测MapReduce(MR3)Map阶段输入为MR1和MR2的输出〈TargetUserID, list〈TargetItemID, Rate〉〉,经过Shuffle后TargetUserID相同的数据会被送到同一reduce函数中;在reduce函数中对每个TargetItemID都有两个评分,利用式(14)来平衡两个评分,得到对TargetItemID的最终评分,然后将评分最高的N个物品输出〈TargetUserID, list〈TargetItemID, Rate〉〉。
4 实验结果与分析串行实验是在单机上对BMAN-CF进行实验,主要是在算法准确率上基于近邻模型的协同过滤(Nearest-based Model Collaborative Filtering, NMCF)算法、概率矩阵分解与近邻模型相结合的协同过滤(Probabilistic Matrix Factorization and Nearest-based Model Collaborative Filtering, PNCF)算法、边界矩阵低阶近似(BMA)算法进行比较分析。
并行实验是在Hadoop分布式集群上对并行化算法进行实验,通过与串行实验运行时间的比较,得到算法加速比,分析算法的可扩展性。
4.1 算法串行实验与分析 4.1.1 MAE指标下算法准确率比较分析由于矩阵分解的阶数k可能会影响平均绝对误差(Mean Absolute Error, MAE)指标下的算法准确率,所以首先测试k值对准确率影响,选取合适的k值,实验时选取k值依次是10、20、30、40、50,实验数据集选取MovieLens-100k,图 4为不同k值下算法的准确率。
从图 4纵坐标轴的间隔来看,不同k值下算法MAE差异很小,但是在k为20时达到最小,所以接下来实验选取k=20。
本文算法在选取近邻集合使用Top-k选择策略,近邻的个数对算法准确率有很大影响,所以接下来是比较各算法在不同近邻个数时MAE的大小,实验结果如图 5所示。
从图 5中可以看出,本文算法受近邻个数影响较小,并且跟其他算法相比,本文算法MAE值始终最小,也就是本文算法准确率最高。BMAN-CF的MAE相比NMCF至少提升了1.87个百分点,说明近邻模型不能更好地为用户兴趣建模,导致近邻集合查找不准确,从而影响算法准确率;相比PNCF,BMAN-CF的MAE至少提升了1.86个百分点,PNCF也是在概率矩阵分解后结合近邻模型产生推荐,但本文算法在矩阵分解时限制了近似矩阵元素上、下界,因此比概率矩阵分解更适合推荐系统;BMAN-CF的MAE相比BMA至少提升了4.2个百分点,本文算法通过挖掘子矩阵的隐含信息,提高了算法预测精度。
4.1.2 RMSE指标下算法准确率比较分析首先对比本文算法与改进的奇异值分解(Singular Value Decomposition, SVD++)算法、带偏置的奇异值分解(Biased Singular Value Decomposition, Bias-SVD)算法、随机梯度下降(Stochastic Gradient Descent, SGD)算法、正则化交替最小二(Alternating Least Squares with Regularization, ALSWR)乘法在不同阶数k下的均方根误差(Root Mean Square Error, RMSE)结果,如表 1所示。
从表 1中可以看出,k值不同时,本文算法的RMSE比其他算法都要高一些。随着k值增加虽然各个算法精度都有稍许的增加,但k值增大会增加矩阵分解阶段计算时间复杂度,所以要选取适合的k值;本文算法的RMSE相比其他算法有一定程度的提升,是因为其他算法都专注于子矩阵P和Q乘积与原始矩阵的近似程度,将更多的精力放在了如何优化矩阵分解上,而没有利用子矩阵隐含信息来进行评分预测。
比较本文算法与其他算法在不同近邻个数下的RMSE结果,进行比较的算法有基于非负矩阵分解和近邻模型结合的协同过滤(Nonnegative Matrix Factorization and Nearest neighbor model CF, NMFN-CF)算法、边界矩阵分解BMA,实验结果如图 6所示。从图 6中可以看出,随着近邻个数的增加,各个算法的RMSE都有一定程度的下降,本文算法与BMA相比RMSE至少提升了2.5个百分点,与NMFN-CF相比RMSE至少提升了1.6个百分点。
本文算法结合边界矩阵分解和基于近邻模型的协同过滤算法,在矩阵分解阶段利用实际推荐系统中的评分区间来限制子矩阵P和Q的元素取值范围,从而使近似矩阵PQ更加接近于原始评分矩阵R,由于得到的子矩阵P和Q是低阶子矩阵,且它们并不是稀疏矩阵,所以这样可以很好地解决推荐系统数据稀疏所带来的一系列问题。在查找近邻集合时利用子矩阵P和Q中的隐含语义,提高了近邻集合查找的准确率,并且查找近邻集合时,两个子矩阵可以看作原始矩阵降维而来,所以可以降低计算复杂度,算法有较好的可扩展性;预测用户对物品的评分时,先利用基于用户和基于物品两种协同过滤算法分别预测用户对物品的评分,再利用平衡因子和控制因子来动态平衡两种算法的预测评分,使最终预测评分更加准确。
4.2 算法并行实验与分析算法并行化实验环境是有7个节点的集群环境,数据集是MovieLens-latest,评价指标是加速比。通过实验得到本文算法与理想情况下的加速比,实验结果如图 7所示。
从图 7中可以看出,随着集群中节点数量的增加,并行化的优势渐渐体现出来,MapReduce任务由多个节点来执行,所以加速比增速较大;但最后加速比增速缓慢,这是因为子矩阵阶数k没发生变化,矩阵分解阶段对参数划分不能太小,否则文件读取时间耗费太多,所以只使用部分节点执行MapReduce任务来迭代分解矩阵,造成加速比增速缓慢,从加速比实验结果可以看出,本文算法有较好的可扩展性。
5 结语针对矩阵分解应用到协同过滤算法中的局限性和准确率等问题,本文提出基于边界矩阵低阶近似和近邻模型的协同过滤算法(BMAN-CF)来提高物品评分预测的准确率。该算法根据实际推荐系统的评分范围界定近似矩阵及目标函数,找出目标用户和目标物品近邻集合,并利用平衡因子和控制因子动态平衡两个预测结果,得到目标用户对物品的评分。在Hadoop环境下并行化实现了该算法。实验结果表明,所提算法能够提高算法的预测准确率,且并行环境下的加速比实验表明,所提算法具有较好的可扩展性。由于并行化后的加速比受矩阵分解的阶数k和并行化节点数量两个参数的影响,接下来将进一步研究如何选择及优化矩阵分解的阶数k和并行化节点数量。
[1] | BARJASTEH I, FORSATI R, ROSS D, et al. Cold-start recommendation with provable guarantees:a decoupled approach[J]. IEEE Transactions on Knowledge & Data Engineering, 2016, 28(6): 1462-1474. |
[2] | ADOMAVICIUS G, SANKARANARAYANAN R, SEN S, et al. Incorporating contextual information in recommender systems using a multidimensional approach[J]. ACM Transactions on Information Systems, 2005, 23(1): 103-145. DOI:10.1145/1055709 |
[3] | CAI Y, LEUNG H F, LI Q, et al. TyCo:towards typicality-based collaborative filtering recommendation[J]. IEEE Transactions on Knowledge & Data Engineering, 2014, 2(3): 97-104. |
[4] | HU Y, KOREN Y, VOLINSKY C. Collaborative filtering for implicit feedback datasets[C]//Proceedings of the 8th IEEE International Conference on Data Mining. Washington, DC:IEEE Computer Society, 2008:263-272. http://ieeexplore.ieee.org/document/4781121/ |
[5] | HUANG Z, CHEN H, ZENG D. Applying associative retrieval techniques to alleviate the sparsity problem in collaborative filtering[J]. ACM Transactions on Information Systems, 2004, 22(1): 116-142. DOI:10.1145/963770 |
[6] | JING H, LIANG A C, LIN S D, et al. A transfer probabilistic collective factorization model to handle sparse data in collaborative filtering[C]//Proceedings of the 2014 IEEE International Conference on Data Mining. Washington, DC:IEEE Computer Society, 2014:250-259. https://www.computer.org/csdl/proceedings/icdm/2014/4302/00/4302a250-abs.html |
[7] | WANG J, DE VRIES A P, REINDERS M J T. Unifying user-based and item-based collaborative filtering approaches by similarity fusion[C]//Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development In Information Retrieval. New York:ACM, 2006:501-508. http://portal.acm.org/citation.cfm?id=1148170.1148257 |
[8] | ZHANG Z, ZHAO K. Low-rank matrix approximation with manifold regularization[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2013, 35(7): 1717-1729. |
[9] | KANNAN R, ISHTEVA M, PARK H. Bounded matrix low rank approximation[C]//Proceedings of the 2013 IEEE 13th International Conference on Data Mining. Washington, DC:IEEE Computer Society, 2012:319-328. http://dl.acm.org/citation.cfm?id=2472542 |
[10] | KIM J, HE Y, PARK H. Algorithms for non-negative matrix and tensor factorization:a unified view based on block coordinate descent framework[J]. Journal of Global Optimization, 2014, 58(2): 285-319. DOI:10.1007/s10898-013-0035-4 |
[11] | MA H, KING I, LYU M R. Effective missing data prediction for collaborative filtering[C]//Proceedings of the 2007 International ACM SIGIR Conference on Research and Development in Information Retrieval. New York:ACM, 2007:39-46. http://dl.acm.org/citation.cfm?id=1277751 |
[12] | KANNAN R, ISHTEVA M, DRAKE B, et al. Bounded matrix low rank approximation[C]//Proceedings of the 8th IEEE International Conference on Data Mining. Washington, DC:IEEE Computer Society, 2012:319-328. http://dl.acm.org/citation.cfm?id=2472542 |
[13] | 陈彦萍, 王赛. 基于用户-项目的混合协同过滤算法[J]. 计算机技术与发展, 2014, 24(12): 88-91. (CHEN Y P, WANG S. A hybrid collaborative filtering algorithm based on user-item[J]. Computer Technology and Development, 2014, 24(12): 88-91.) |