软件工程

当前位置: 首页 > 计算机论文 > 软件工程

项目相似度与ALS结合的推荐算法研究

软件工程 时间:2019-08-06 13:00:01 来源:软件导刊 作者:迟玉良 祝永志

迟玉良 祝永志

摘 要:协同过滤算法是当今推荐系统普遍使用的一种推荐算法。面对单机模型已逐渐承受不了大数据给推荐系统带来的负荷问题,提出基于Spark平台的一种项目相似度与ALS相结合的协同过滤推荐算法。它基于Spark分布式并行计算框架,可提高预测计算效率,减少系统响应时间。同时使用“基于项目相似度的协同过滤”与“交替最小二乘的协同过滤(ALS)”相结合的一种混合推荐方法,可提高系统推荐精度。通过在MovieLens数据集上的实验结果表明,该算法在算法融合与推荐精度上有着很好的效果。

关键词:项目相似度;ALS;協同过滤;混合推荐;Spark

DOI:10.11907/rjdk.172903

中图分类号:

文献标识码:A 文章编号:1672-7800(2018)006-0081-04

Abstract:Collaborative filtering algorithm is a recommended algorithm commonly used in today′s recommended systems. In this paper, a collaborative filtering recommendation algorithm based on Spark platform is proposed, which is a kind of project similarity degree and ALS. In this paper, we propose a cooperative filtering algorithm based on Spark platform. It is based on spark distributed parallel computing framework to improve the efficiency of forecasting and reduce system response time. Collaborative filtering based on project similarity and alternating least squares of cooperative filtering (ALS) are used to improve the accuracy recommended by the system. Through the experiment results of the MovieLens dataset, it is concluded that the algorithm has a considerable effect on the algorithm fusion and recommendation accuracy.

Key Words:item similarity; ALS; collaborative filtering; hybrid recommender; Spark

0 引言

当今,互联网+技术发展迅速,信息量出现爆炸式增长,对海量数据进行存取并挖掘出其中隐藏的知识与价值一直是学术界和商业界研究的重点[1]。为了满足用户的个性化需求,推荐系统应运而生。一个优秀的推荐系统[2]能预测出不同用户偏好条件下需要的信息,相比于传统的搜索引擎技术,有着更好的用户体验。据统计,Amazon的商品推荐为其带来了35%的额外销售额。基于协同过滤的推荐算法[3]无疑是使用最广泛的算法,其通过对已有的部分数据构建预测模型,计算其用户或项目的相互关系[4],预测未知用户的偏好并提供个性化推荐服务。其算法也可分为基于用户的推荐算法[5]和基于项目的推荐算法[6]。基于用户的协同过滤推荐算法主要通过计算不同用户之间的相似度,将与目标用户相似性较高的用户对商品的评价信息作为参考,推荐给目标用户;基于项目的协同过滤推荐算法则是通过寻找项目之间的相似性进行推荐。两种算法都有其适用的场合与缺点,如基于用户的推荐算法有冷启动[7]问题,基于项目的推荐算法不适合项目信息频繁变动或数据增长量很大的情形,同时两种算法都存在数据稀疏性问题[8]。如今,采用混合推荐算法[9]可以起到取长补短、提高推荐准确度的效果。文献[10]提出的结合用户偏好和标签的混合算法提高了推荐命中率。本文提出的混合推荐算法针对电影推荐系统目前遇到的问题,采用ALS算法[11]和基于项目相似度融合的思想,并在Spark平台上加以实现,目的是提高算法计算效率并提升预测精度。

1 Spark平台推荐架构

Spark 是一个快速和通用的大规模数据处理平台,其于2009 年诞生于伯克利大学AMP Lab,并在2010 年开源。发展至今,Spark 已经在流处理、图计算、机器学习、结构化数据查询等各个方面取得了很多成果。国内对于Spark 的研究主要集中在互联网行业,如阿里巴巴、腾讯、百度、网易、搜狐等公司。Spark 具有基于内存的处理模式[12],在迭代计算方面的速度远远优于MapReduce[13]。目前国内外有很多公司都利用Spark 平台部署推荐系统。

图1为基于Spark on YARN构建的推荐系统架构,共分为数据存储层、平台计算层、系统推荐层。

(1) 数据存储层。使用目前应用最广泛的Hadoop平台下分布式文件系统HDFS,实现对大数据集的存储与读取。HDFS有着高容错性、适合批处理、成本低等优点。

(2) 平台计算层。采用YARN集群下的Spark平台,可以与HDFS无缝结合,在推荐算法的迭代计算中具有很大优势,并且为多种语言开发提供了大量方法库和接口。

(3)系统推荐层。主要针对模型构建和算法实现,对数据集作预处理并分别传给基于项目相似度的协同过滤算法和基于交替最小二乘的协同过滤算法进行训练,利用Spark集群同时进行算法计算得到预测结果,然后将其传入经预测验证后的基于权重的融合算法中,最后得到各用户对不同电影的预测评分。

2 混合推荐

2.1 基于项目相似度的协同过滤

由于不同用户的评分尺度有所差异,有的用户喜欢评高分,也有用户评分很苛刻,因而评分尺度在一定程度上对项目整体评分有所影响。所以本文使用改进的基于项目相似度的协同过滤算法,通过对余弦相似度算法[14]的修正,在用户对每个项目评分的基础上与该用户的总体平均打分取差值,从而判定该项目的相对评分,以弥补用户差异问题,其中当前用户u∈U,待评分项目 i∈I,j∈I且i≠j。

如图2所示,首先计算项目 i 與 I 中其它所有项目的相似性 sim*(i,j),然后结合最流行的中心最近邻选取方法,对于i∈I构建相似性矩阵A-sim*(i,j),按从大到小顺序排列,可得到每个项目与其它所有项目的相似关系。

在评分预测算法上,选取一定数量相似度高的项目,过滤掉噪声和低关联信息[15],利用基于项目均值的加权平均值计算推荐评分。其中P-u,i表示用户u对项目i的预测评分,KNNI(i) 表示项目i的K最邻集合,-i和-j分别表示项目i和j的评分均值。

2.2 基于交替最小二乘的协同过滤

交替最小二乘(ALS)通过矩阵分解观察用户给项目的打分,基于评分矩阵是低秩矩阵,主要思想是找到两个低维矩阵 X-(m×k)和矩阵Y-(n×k)近似逼近R-(m×n)。

ALS的具体求解方法是一个交替迭代计算过程,先固定其中一个矩阵如Y,将损失函数L-(X,Y)对x-u求偏导,并令导数等于0,得到:

如图3所示,迭代计算分解矩阵特征值,计算得到的特征值向量代表用户对项目及项目对用户的隐式关系,最后矩阵相乘得到预测评分。

2.3 混合方法

为了结合基于项目相似度和ALS算法的优点并弥补其缺点,本文采用基于权重的混合方法。如图4所示,将两种模型计算的结果机遇比例λ融合,其中 S-(u,i) 代表基于项目相似度的预测评分,A-(u,i) 代表交替最小二乘模型的预测评分。

为验证对应权值的混合效果,将预测结果和测试数据进行比较,计算其平均绝对误差(MAE)值。

MAE作为推荐系统常用的评估标准,表示推荐系统对某个项目的预测值与真实值之间的关系,能够很好地反映推荐结果质量。如图4所示通过对比不同权值计算得出的MAE值,选取误差最小的λ作为混合比例,最终得出预测结果。

3 实验与分析

3.1 实验数据与环境

本文使用GroupLens 研究小组提供的MovieLens数据集,数据集版本选择包含约700位用户对9 000部电影评分的最新版本,评分数据约10万条。实验环境采用架设在Macbook上的ubuntu16.04虚拟Hadoop集群,共包含3个节点,存储方式采用HDFS,Spark集群依赖于YARN,编程语言使用Python。

3.2 实验结果与分析

将评分数据拆分为训练数据与测试数据,训练数据作为数据源导入算法中计算预测评分,测试数据用于对预测评分的验证,两者对比计算出的MAE值作为预测精准度。

对于基于项目相似度的协同过滤算法,在不同稀疏度下选取不同数量的相似邻居进行实验。其中不同稀疏度可将训练数据占总数据的比例划分为[20%, 40%, 60%, 80%],其余作为测试数据。

实验结果如图5所示,表明在不同稀疏程度下,源数据越充分,获得的预测结果精确度越高,并且不同比例下的MAE值也大致呈等比例。在相邻项目数量的选择上,提高数量基数可以提高预测准确度,但随着邻居数量的逐渐增加,提高程度逐渐缩小,同时对应的数据计算量和运行时间也会成比例增加。因此,在实际应用中,需要对数据准确度和计算时间进行平衡,才能有效提升用户体验。

对ALS算法在相同数据,且在不同迭代次数和特征数量条件下做实验,源数据使用80%作为训练数据,其中迭代次数选择[5, 10, 15, 20],特征数量选择[4, 8, 12, 16]。

从图6的结果看,在迭代次数增加的情况下,整体MAE值是减小的,并且对当前数据最友好的特征数量是8。

利用训练数据所占的不同比例代表不同稀疏度,对ALS算法做实验,其中特征数量选择8,迭代次数选择20。

由图7可以看出,训练数据的量是影响算法精确度的一个重要因素。在数据量较少的情况下,随着源数据增加,算法精确度提升空间较大;在训练数据较为充足的情况下,提升数据量,MAE误差值下降的速度会有所放缓。

考虑将两个算法利用融合算法混合,这里选取最近邻的数量为100,对基于项目算法占不同比例下混合的情况做实验。实验结果如图8所示,在混合算法权值不同的条件下,模型对训练数据的预测有较为明显的差别。训练数据较为稀疏时,基于项目相似度的模型可以更好地解决冷启动问题;在源数据充足的情况下,ALS算法能更好地提升混合算法的精确度。

综合以上实验,利用相同的源数据对比,在各推荐算法选用合适参数的情况下,推荐结果精度对比如表1所示。

图9为其对比图,通过分析可以得出,本文提出的基于项目相似度和ALS结合的协同过滤推荐算法在各种数据稀疏程度下都可较好地提高预测评分的准确性,并且对混合算法权值进行动态调整可以有效解决数据的冷启动问题。

4 结语

本文首先对Spark平台和建立在Spark平台上的推荐框架进行了介绍,指出其优点和使用的广泛性;然后对当前流行的基于项目相似度的协同过滤算法和交替最小二乘算法进行分析,提出使用修正的余弦相似度算法计算项目相似度,并提出利用权值将两种算法进行融合的算法;最后,在Spark集群环境下,利用MovieLens数据集对各算法进行实验,通过对比分析证实了该算法的优越性。

参考文献

[1] EPPLER M J, MENGIS J. The concept of information overload: a review of literature from organization science, accounting, marketing, MIS, and related disciplines[J]. IEEE Engineering Management Review, 2010,38(1):3.

[2] BOBADILLA J, ORTEGA F, HERNANDO A, et al. Recommender systems survey[J]. Knowledge-Based Systems, 2013,46(1):109-132.

[3] YANG X, GUO Y, LIU Y, et al. A survey of collaborative filtering based social recommender systems[J]. Computer Communications, 2014,41(5):1-10.

[4] 文俊浩,舒珊.一种改进相似性度量的协同过滤推荐算法[J].计算机科学,2014,41(5):68-71.

[5] ZHAO Z D, SHANG M. User-based collaborative-filtering recommendation algorithms on Hadoop[C].Third International Conference on Knowledge Discovery and Data Mining,IEEE Computer Society, 2010:478-481.

[6] HU W, YANG F, FENG Z. Item-based collaborative filtering recommendation algorithm based on MapReduce[M]. Multimedia, Communication and Computing Application,2015.

[7] 郭艳红,邓贵仕.协同过滤系统项目冷启动的混合推荐算法[J].计算机工程,2008,34(23):11-13.

[8] 郁雪,李敏強.一种有效缓解数据稀疏性的混合协同过滤算法[J].计算机应用,2009,29(6):1590-1593.

[9] GEUENS S. Factorization machines for hybrid recommendation systems based on behavioral, product, and customer data[C].ACM Conference on Recommender Systems,ACM, 2015:379-382.

[10] 张新猛,蒋盛益,李霞,等.基于网络和标签的混合推荐算法[J].计算机工程与应用,2015,51(1):119-124.

[11] KOREN Y, BELL R, VOLINSKY C. Matrix factorization techniques for recommender systems[J]. Computer, 2009,42(8):30-37.

[12] ZAHARIA M, CHOWDHURY M, DAS T, et al. Resilient distributed datasets: a fault-tolerant abstraction for in-memory cluster computing[C]. Usenix Conference on Networked Systems Design and Implementation. USENIX Association, 2012:2.

[13] DEAN J, GHEMAWAT S. MapReduce: simplified data processing on large clusters[M]. ACM, 2008.

[14] WANG P. A personalized collaborative recommendation approach based on clustering of customers[J]. Physics Procedia, 2012,24(24):812-816.

[15] BATES D, KLIEGL R, VASISHTH S, et al. Parsimonious mixed models[J]. Statistics, 2015.

[16] JAMALI M, ESTER M. A matrix factorization technique with trust propagation for recommendation in social networks[C].ACM Conference on Recommender Systems,ACM, 2010:135-142.

(责任编辑:黄 健)