Research on ALS Acceleration Algorithm Based on Spark Platform

doi:10.19678/j.issn.1000-3428.0054147

Abstract

Abstract: Collaborative filtering algorithm plays an important role in recommendation system,but its execution efficiency and ranking accuracy are both low.Alternating Least Squares(ALS) algorithm can implement parallel computing,thus improving the execution efficiency,but the time between data loading and iterative convergence of the algorithm is a bit long.Therefore,by combing the Nonlinear Conjugate Gradient(NCG) algorithm and the ALS algorithm,this paper proposes an ALS-NCG algorithm to accelerate the ALS algorithm.The performance of the ALS-NCG algorithm is evaluated in the Spark distributed data processing environment.Experimental results show that compared with the ALS algorithm,the ALS-NCG algorithm needs less iterations and time to obtain high-precision recommended ranking.

Key words: collaborative filtering, recommendation algorithm, Alternating Least Squares(ALS) algorithm, Nonlinear Conjugate Gradient(NCG), Spark platform

摘要： 协同过滤推荐算法在推荐系统中发挥着重要作用，但其存在执行效率与排名精度较低的问题，交替最小二乘（ALS）算法可实现并行计算，从而提高执行效率，但是该算法数据加载与迭代收敛的时间较长。为此，将非线性共轭梯度（NCG）算法与ALS算法相结合，提出一种ALS-NCG算法，以达到加速ALS算法的目的。在Spark分布式数据处理环境中对ALS-NCG算法进行性能评估，实验结果表明，相比ALS算法，ALS-NCG算法获取高精度推荐排名时需要的迭代次数与时间更少。

CLC Number:

TP312

JIA Xiaofang, SANG Guoming, QI Wenkai. Research on ALS Acceleration Algorithm Based on Spark Platform[J]. Computer Engineering, 2020, 46(2): 103-109.

贾晓芳, 桑国明, 祁文凯. 基于Spark平台的ALS加速算法研究[J]. 计算机工程, 2020, 46(2): 103-109.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0054147

http://www.ecice06.com/EN/Y2020/V46/I2/103

Figures/Tables 12

References

[1] GANTZ J,REINSEL D.The digital universe in 2020:big data,bigger digital shadows,and biggest growth in the far east[EB/OL].[2019-02-10].https://www.speicherguide.de/download/dokus/IDC-Digital-Universe-Studie-iView-11.12.pdf.
[2] ISINKAYE F O,FOLAJIMI Y O,OJOKOH B A.Recommendation systems:principles,methods and evaluation[J].Egyptian Informatics Journal,2015,16(3):261-273.
[3] KOREN Y,BELL R,VOLINSKY C.Matrix factorization techniques for recommender systems[J].Computer,2009,42(8):30-37.
[4] LIU Yingnan,XIE Jinkui,ZHANG Jiali,et al.Recommendation algorithm based on trust in social network[J].Journal of Chinese Computer Systems,2015,36(6):1165-1170.(in Chinese) 刘英南,谢瑾奎,张家利,等.社交网络中基于信任的推荐算法[J].小型微型计算机系统,2015,36(6):1165-1170.
[5] BOKDE D,GIRASE S,MUKHOPADHYAY D.Matrix factorization model in collaborative filtering algorithms:a survey[J].Procedia Computer Science,2015,49(1):136-146.
[6] MENG Xiangwu,LIANG Bi,DU Yulu,et al.Study on the utility evaluation of location-based mobile recom-mendation system[J].Chinese Journal of Computers,2019,42(12):2695-2721.(in Chinese) 孟祥武,梁弼,杜雨露,等.基于位置的移动推荐系统效用评价研究[J].计算机学报,2019,42(12):2695-2721.
[7] HERNANDO A,BOBADILLA J,ORTEGA F.A non negative matrix factorization for collaborative filtering recommender systems based on a Bayesian probabilistic model[J].Knowledge-Based Systems,2016,97(4):188-202.
[8] DU Dongfang,XU Tong,LU Yanan,et al.User rating prediction based on trust-driven probabilistic matrix factorization[J].Journal of Software,2018,29(12):3747-3763.(in Chinese) 杜东舫,徐童,鲁亚男,等.基于信任机制下概率矩阵分解的用户评分预测[J].软件学报,2018,29(12):3747-3763.
[9] KOREN Y.Collaborative filtering with temporal dynamics[J].Communications of the ACM,2010,53(4):447-456.
[10] DESHPANDE M,GEORGE K.Item-based top-n recommendation algorithms[J].ACM Transactions on Information Systems,2004,22(1):143-177.
[11] WANG Jianfang,MIAO Yanling,HAN Pengfei,et al.Probabilistic matrix factorization algorithm of colla-borative filtering based on trust mechanism[J].Journal of Chinese Computer Systems,2019,40(1):31-35.(in Chinese) 王建芳,苗艳玲,韩鹏飞,等.一种基于信任机制的概率矩阵分解协同过滤推荐算法[J].小型微型计算机系统,2019,40(1):31-35.
[12] CONDIE T,MINEIRO P,POLYZOTIS N,et al.Machine learning on big data[C]//Proceedings of 2013 IEEE International Conference on Data Engineering.Washington D.C.,USA:IEEE Press,2013:1242-1244.
[13] TU Xiaohan,LIU Siping,LI Renfa.Improving matrix factorization recommendations for problems in big data[C]//Proceedings of 2017 IEEE International Conference on Big Data Analysis.Washington D.C.,USA:IEEE Press,2017:193-197.
[14] THAN H A,RACHSUDA J T.Alternating least squares with incremental learning bias[C]//Proceedings of 2015 International Joint Conference on Computer Science and Software Engineering.Washington D.C.,USA:IEEE Press,2015:297-302.
[15] STERCK H D,WINLAW M.A nonlinearly preconditioned conjugate gradient algorithm for rank-R canonical tensor approximation[J].Numerical Linear Algebra with Applications,2015,22(3):410-432.
[16] YE Hanmin,ZHANG Qiuling,BAI Xue.A new collaborative filtering algorithm based on modified matrix factorization[C]//Proceedings of 2017 IEEE Advanced Information Technology Electronic and Automation Control Conference.Washington D.C.,USA:IEEE Press,2017:147-151.
[17] ZHOU Y H,WILKINSON D,SCHREIBER R,et al.Large-scale parallel collaborative filtering for the netflix prize[C]//Proceedings of the 4th International Conference on Algorthmic Aspects in Information and Management.Berlin,Germany:Springer,2008:337-348.
[18] QI Changxia.Study on several fusion nonlinear conjugate gradient methods[D].Qinhuangdao:Yanshan University,2017.(in Chinese) 齐昌霞.几种融合非线性共轭梯度法的研究[D].秦皇岛:燕山大学,2017.
[19] LIU Zhengrong.Several new nonlinear conjugate gradient methods[D].Nanning:Guangxi University,2016.(in Chinese) 刘峥嵘.几种新的非线性共轭梯度法[D].南宁:广西大学,2016.
[20] ZAHARIA M,CHOWDHURY M,DAS T,et al.Resilient distributed datasets:a fault-tolerant abstraction for in-memory cluster computerin[C]//Proceedings of USENIX Conference on Networked Systems Design and Implementation.San Diego,USA:USENIX Association,2012:141-146.
[21] WU Xindong,JI Shengwei.Comparative study on MapReduce and Spark for big data analytics[J].Journal of Software,2018,29(6):1770-1791.(in Chinese) 吴信东,嵇圣硙.MapReduce与Spark用于大数据分析之比较[J].软件学报,2018,29(6):1770-1791.

Please choose a citation manager

Content to export