基于Spark的K近邻ALS的推荐算法

刘佳耀 王佳斌

摘要：传统的协同过滤推荐算法在面对海量数据时表现出处理速度慢和效率低下的瓶颈，与Hadoop平台相比，Spark计算框架具有迭代计算优势，提出了基于spark的K近邻ALS推荐算法。由于一般的矩阵分解算法只考虑隐含信息忽略了相似度的信息，所以将相似度信息加权到评分预测的公式中，并采用交替最小二乘法进行模型训练得出结果。在MovieLens数据集上验证，该改进算法能够提高推荐的准确性，提高对大数据集的处理效率。

关键词：协同过滤；Hadoop；Spark；ALS

中图分类号：TP391.1 文献标识码：A 文章编号：1009-3044（2018）11-0006-02

A Recommendation Algorithm Based on Spark's K neighbor ALS

LIU Jia-yao， WANG Jia-bin

（Institute of Technology Huaqiao University， Quanzhou 362021， China）

Abstract： Traditional collaborative filtering recommendation algorithm in the face of huge amounts of data show the processing speed is slow and inefficient bottleneck， compared with the Hadoop platform， Spark computing framework has the advantages of iterative calculation， and puts forward the K neighbor ALS recommendation algorithm based on the Spark.Due to generally only considered implicit information of the matrix decomposition algorithm ignores the similarity of information， so will be weighted similarity information to score prediction formula， and alternating least squares method is adopted to model the training results.n the MovieLens data set， the improved algorithm can improve the accuracy of recommendation and improve the processing efficiency of large data sets.

Key words： Collaborative filtering； Hadoop； Spark； ALS

1 引言

随着互联网的迅速发展，各种信息也呈爆炸性增长，接踵而来的是出現了“信息过载”的问题。为了解决这个问题，推荐系统由此产生，推荐系统[1]可以通过用户对各种商品的评分或用户以前的浏览记录，来为用户推荐他们所需的信息。协同过滤[2]算法是推荐系统中运用最常用的算法，但是在大数据背景下随着用户和项目数量的不断增长，用户-项目矩阵的稀疏和单机上的瓶颈导致推荐质量和准确性不断下降。

针对以上问题，许多研究人员提出了有效的改进方法。文献[3]提出了基于矩阵分解的协同过滤算法，该算法通过降低数据稀疏性，提高了推荐准确性。文献[4]提出了一种基于矩阵分解与用户近邻模型的混合推荐模型，最大程度上利用用户信息和降维的思想来提升推荐效率，但是没有实现并行化，推荐效率低。文献[5]提出了基于Spark的矩阵分解与最近邻结合算法，该算法通过运用Spark平台的优势，提高了算法的可扩展性和减少了推荐时间。交替最小二乘法ALS通过矩阵分解把评分缺失值给填充了，降低了数据的稀疏性，提高了推荐质量。

现在应用广泛的大数据平台有两种分别为Hadoop和Spark。由于在Hadoop2.6.1[6]YARN上的分布式计算框架MapReduce[7]完成每次的map和reduce任务，都需要经过磁盘，会引起高延迟性。而Spark计算框架的Job中间输出和结果可保存在内存中，能尽量减少了访问硬盘次数，提高迭代速度。

本文围绕解决上述问题展开研究，并在已有研究的基础上，把相似度因子加权到矩阵分解的模型中，并结合Spark[8]平台，提高推荐精确度和推荐效率。

2 Spark计算框架

2.1 搭建Spark平台

本实验的Spark平台采用的VMware Workstation的三台虚拟机来搭建，包含一个主节点和三个从节点，三个节点的系统均为Centos6.5。

软件安装：Hadoop版本为hadoop-2.6.1.tar.gz；JAVA版本为jdk-7u75-linux-i586.gz；Spark版本为1.6.0-bin-hadoop2.6.tgz；Scala版本为2.12.4.tgz。在三台虚拟机上分别配置好这些软件，然后先启动yarn，在yarn的基础上再启动spark。

2.2 Spark内存计算框架

Spark大数据处理框架通过一种弹性分布式数据集RDD，可以把对数据的处理都封装为对RDD的处理，RDD数据集有两个特点：第一个是：适合在内存中存取，这样在迭代计算时，可以减少或避免向磁盘读数据或写数据，都在内存中计算，提高数据处理效率。第二个是：很好的容错性，避免了数据冗余的麻烦和检查费时的问题。

3 基于矩阵分解的K近邻ALS模型

3.1 矩阵分解思想

矩阵分解方法的关键思想是将用户-物品评分矩阵从高维矩阵分解为几个低维矩阵的相互乘积，不同于一般的协同过滤算法，该算法是评分预测算法，最近几年来在推荐算法中使用最为频繁，其主要思想就是将评分矩阵中大量缺失的评分值通过逻辑回归的形式进行填充，具体方法如下：

假设有X个用户Y个项目，首先把矩阵中大量的缺失值填充成R矩阵，然后再将这个矩阵分解：把R矩阵分解为用户矩阵[p∈Rf×m]和物品矩阵[Q∈Rf×n]，通过分解后的矩阵估计评分为：

[rui=puqi] （1）

风险构造函数为：

[C（p，q）=min（u，i）n（rui-puqTi）2+λ（||pu||2+||qi||2）] （2）

其中[λ]参数用来正则化模型，成为正则化系数；k表示预测评分项，评分预测的目的就是将上面的损失函数尽可能最小化。

求解上面的模型，目前效率高的方法有两种：最小二乘法（ALS）[9]和随机梯度下降法[10]（SGD）。

3.2 基于K近邻ALS的推荐模型

Spark 机器学习库中的常用的推荐算法是基于矩阵分解的ALS算法，其方法是通过评分预测的方式填充稀疏用户-物品矩阵，填充采用ALS算法。基于Spark的ALS算法的核心就是将稀疏矩阵进行分解为用户矩阵和物品矩阵，然后用交替最小二乘法进行物品与用户的特征向量不断更新直到使其误差平方和最小。由于在训练模型过程中，用户矩阵和物品矩阵中会丢失部分相似性信息，于是将K近邻算法得到的相似度信息加权到ALS算法中的损失函数，进行模型训练。

在公式（1）中，通过将用户和物品与隐因子联系起来，因此在评分预测公式中加入偏置项，得到的评分预测公式如下：

[rui=μ+bu+bi+puqi] （3）

其中[μ]表示训练集中所有记录评分的全局平均数，[bi]是物品偏置项，[bu]是用户偏置项。

物品-物品，用户-用户之间的相似度用皮尔森相似距离计算，公式如下：

[S（i，j）=c∈Ii（Ri，c-Ri）（Rj，c-Rj）c∈Ii（Ri，c-Ri）2c∈Ii（Rj，c-Rj）2] （4）

根据公式（2）中ALS推荐模型训练的损失函数，在使用训练模型求解物品矩阵和用户矩阵的过程中，发现忽略了用户或物品相似度，由此进一步考虑将用户或物品相似度与损失函数进行加权以缩小系统误差，得到K近邻ALS推荐模型，相似度误差计算如下：

[P=u∈Nu（puk-pv∈KNN（pu）（Spupvpvk）pv∈KNN（pu）Spupv）2] （5）

[Q=i∈Ni（qik-qj∈KNN（qi）（Spipjqjk）qj∈KNN（qi）Spipj）2] （6）

其中的N表示物品或用户的集合总数，KNN表示物品或用户的K近邻集合，S表示用户之间相似度，k表示某一个特征（或隐含因子），上述公式从相似物品或用户的信息进行用户-物品评分误差的计算，并将得到的相似度误差信息加权到基于ALS的评分误差预测中，得到改进算法，K近邻ALS模型的损失函数计算公式如下：

[C（p，q）=min（u，i）∈kn（rui-puqTi）2+λ（||pu||2+||qi||2）]（7）

4 实验设计与结果分析

本文采用的数据来自GroupLens的MovieLens标准数据集，包含3个大小不同的数据集，从小到大依次为ml-100k的数据集、ml-1M的数据集和ml-10M的数据集。用户对电影评分的等级分为1 ～ 5级别，分数越高，表示用户对电影越喜爱。

4.1 运行时间

根据不同大小的数据集在Spark平台下的运行时间，如下图1所示。

可知，同一数据集上，在Spark计算框架下，增加集群中的节点数可以明显减少处理时间，提高处理速度和扩展性。

4.2 平均绝对误差（MAE）

本文采用推荐领域中常用的平均绝对误差MAE作为度量指标。MAE计算实际用户评分值与预测的评分值之间的差值，根据这个值来衡量推荐的精确性，计算公式如下：

[MAE=1N|pi-qi|N] （8）

其中N为评分总个数，[pi]为用户对项目i预测评分值，[qi]为实际评分值。因此，MAE越小代表误差越小，预测准确性越高。

4.3 算法对比

为了对比本文改进算法与其他算法的效果，本文在Spark框架下对同一数据集ml-1M进行了实验测试，选用的对比算法是Spark MiLib库中的ALS算法模型，评价指标是MAE，如下图2所示：

其中KNN算法横坐标表示K近邻值，两个ALS模型表示最小化损失函数过程中的迭代次数，其他两个参数lambda和ranks分别使用了0.2和10。

从图2中看出，随着最近邻居的增加和迭代次数的增加，加权了相似度信息后的ALS算法的MAE值小于ML库中的ALS算法，推荐精度更高。

5 总结

在当前信息数据量以爆炸式增长的环境下，提出了把推荐算法和大数据平台相结合来提高推荐效率，通过对MAE值的观察，在ALS算法基础上加入K近邻相似度信息，随着迭代次数的增加以及正则化系数的调整，提高了推荐算法的准确性，也减少了推荐的时间，但由于算法过于依赖用户数据，存在数据稀疏的问题，是在后续研究中需要补充和完善的地方。

参考文献：

[1] Amatriain X. Past， Present， and Future of Recommender Systems： An Industry Perspective[C]//International Conference on Intelligent User Interfaces. ACM， 2016：1-1.

[2] DietmarJannach. 推荐系统[M]. 人民邮电出版社， 2013：1-8.

[3] 李改， 李磊. 基于矩阵分解的协同过滤算法[J]. 计算机工程与应用，2011，47（30）：4-7.

[4] 杨阳，向阳，熊磊.基于矩阵分解与用户近邻模型的协同过滤推荐算法.计算机应用，201232（2）：395-398

[5] 王振军， 黄瑞章. 基于Spark的矩阵分解与最近邻融合的推荐算法[J]. 计算机系统应用， 2017， 26（4）：124-129.

[6] Tom White. Hadoop权威指南[M]. 3版.清华大学出版社， 2015：205-240.

[7] 杜江， 张铮， 张杰鑫，等. MapReduce并行编程模型研究综述[J]. 计算机科学， 2015，42（S1）：2635-2642.

[8] 高彦杰. Spark大数据处理：技术、应用与性能优化[M]. 机械工业出版社， 2014.

[9] 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， June 23-25， 2008. Proceedings. DBLP， 2008：337-348.

[10] 李衛平， 杨杰. 基于随机梯度矩阵分解的社会网络推荐算法[J].计算机应用研究，2014，31（6）：1654-1656.