李珍　吴青洋

摘要：推荐算法是推荐系统的重要组成部分，交替最小二乘算法ALS（Alternating Least Squares）在许多大规模数据处理过程中，经常用于计算潜在的因子矩阵分解。对于ALS算法迭代次数多、收敛时间长的问题，该文提出了一种采用非线性共轭梯度算法NCG（nonlinear conjugate gradient ）对ALS算法进行改进，来加快ALS算法的收敛速度，并对该方法进行了实验研究，通过在MovieLens 10M数据集上的实验结果表明，ALS-NCG模型推荐算法在收敛过程中，比ALS模型推荐算法迭代次数少，时间消耗少。

关键词：Spark;最小二乘法;矩阵分解;推荐系统;协同过滤

中图分类号  TP311.52        文献标志码  A

文章编号：1009-3044（2019）13-0019-04

Abstract： Recommendation algorithm is an important part of the recommendation system. Many large-scale data processing environments include collaborative filtering models for which the Alternating Least Squares（ALS） algorithm is used to compare latent factor matrix decompositions. To solve the problem that ALS algorithm has too many iterations and too long convergence time， in this paper， we propose an approach to accelerate the convergence of parallel ALS-based optimization methods for collaborative filtering using a nonlinear conjugate gradient（NCG） algorithm wrapper around the ALS iterations. Experimental results on the Movie Lens 10M dataset show that ALS-NCG model recommendation algorithm has less iteration times and less time consuming than ALS model recommendation algorithm in convergence process.

Key words： Spark; alternating least square （ALS）; matrix decomposition; recommended system; collaborative filtering

1 背景

推荐系统通过分析用户行为数据，为其推荐如电影、音乐、或其他商品，并已成为在线服务中的重要组成部分。协同过滤是构建推荐系统的一种策略，即通过收集许多用户的喜好信息来进行推荐。协同过滤方法已用于在线业务，如亚马逊[1]，Netflix[2]。

基于隐语义模型推薦算法的实质是将稀疏的用户评分矩阵分解为若干个组成部分，用户物品评分矩阵R中每一项表示用户对物品的评分，快速求解低维用户矩阵U和物品矩阵M是十分必要的，并满足[R≈UTM]。

矩阵分解与奇异值分解（SVD）联系紧密，但是SVD不能处理含有缺失值的矩阵。由于[R≈UTM]，使R中预测评分和实际评分之间的平方差最小，是获取用户矩阵和物品矩阵的方法之一。通常采用随机梯度下降（SGD）或交替最小二乘（ALS）来最小化这种差异[3]。其中，ALS可以处理含有隐式数据模型，而且也容易并行化。

尽管ALS推荐算法相对其他推荐算法而言有一定的优势，然而ALS推荐算法收敛过程中迭代次数多、收敛时间长，很难适用于实时推荐的场景。于是本文提出一种用来计算用户、物品的矩阵的优化后的ALS算法。本文使用非线性共轭梯度算法（NCG）[4]来融合 ALS算法，从而大大加快ALS算法的收敛，本文将这种组合算法称为ALS-NCG。

本文将在Spark平台上并行实现优化后的ALS算法，其中Spark是一个大型的分布式数据处理环境。在商业环境中，Spark已经广泛应用于大数据分析中。本文在文献[5-6]提出在Spark平台上并行实现ALS模型推荐算法的基础上对ALS模型算法进行优化。

表3显示了ALS算法改进前后的RMSE对比结果， 当正则化参数设置为10时，迭代次数为10、20、30、40，属性数为8、10、12，进行比较。图1是对应于表3的统计柱状图。由图1可知ALS-NCG算法对应RESE的数值要比ALS算法对应的RMSE的数值低得多，当迭代次数为40并且属性个数为10时，RMSE值降低到0.870414，RMSE值越小，表明预测的精度越高，可以看出，利用非线性共轭梯度算法融合ALS算法，不但可以加快ALS算法的收敛速度，还能使模型的评价指标更好。

7 总结

本文介绍了ALS模型推荐算法和Spark平台的概况，对于ALS模型推荐算法在收敛过程中，收敛时间长、迭代次数多的问题，本文采用非线性共轭梯度算法融合ALS算法，并在Spark平台上将优化后的ALS-NCG算法并行化实现了。实验结果表明ALS-NCG算法效果显著，有效地加快了ALS算法的收敛，提高了ALS模型推荐算法在海量数据下的执行效率，并降低了评测指标RMSE值。但是也存在不足之处，本文提出的ALS-NCG 推荐算法是在离线环境下进行的，使用GroupLens提供的电影相关的数据，本文进一步的工作应该包括：在线上环境进行实验和研究其他类型的数据。

参考文献：

[1] Linden G， Smith B， York J. Amazon. com recommendations： Item-to-item collaborative filtering[J]. 2003， 7（1）： 76-80.

[2] Bell M R， Koren Y. Lessons from the Netflix prize challenge[J]. SIGKDD Explor. Newsl， 2007， 9（2）： 75-79.

[3] Koren Y， Bell R， Volinsky C. Matrix factorization techniques for recommender systems[J]. Computer， 2009， 42（8）： 30-37.

[4] Liu Z， Wang Y， Yang S， et al. Differential evolution with a two-stage optimization mechanism for numerical optimization[C]// IEEE Congress on Evolutionary Computation. IEEE， 2016.

[5] Zhou Y， Wilkinson D， Schreiber R， et al. Large-scale parallel collaborative filtering for the netflix prize[C]// Algorithmic Aspects in Information and Management， International Conference， Aaim 2008， Shanghai， China， 2008（6）： 23-25， Proceedings. DBLP， 2008： 337-348.

[6] Koren Y， Bell R， Volinsky C. Matrix factorization techniques for recommender systems[J]. Computer， 2009， 42（8）： 30-37.

[7] PILASZY I， ZIBRICZKY D. Fast als-based matrix factorization for explicit， implicit feedback datasets[C]//Proceedings of the Fourth ACM Conference on Cecommender Systems. New York： ACM Press， 2010： 71-78.

[8] Dena D， Bucicoiu M， Bardac M. A managed distributed processing pipeline with Storm and Mesos[C]. Networking in Education and Research， 2013 RoEduNet International Conference 12th Edition， Iasi， 2013： 1-6.

[9] 夏俊鸳. Spark大数据处理技术[M]. 北京： 电子工业出版社， 2015.

[10] Polak E， Ribière G. Note sur la convergence de méthodes de directions conjuguées[J]. Rev. franaise Informat. recherche Opérationnelle， 1968， 16（16）： 35-43.

【通聯编辑：谢媛媛】