0 引言

　　互联网和电子商务的迅猛发展已经把人们带入了一个信息爆炸的时代，商品种类和数量的快速增长，使得顾客花费了大量的时间浏览无关的信息，个性化推荐系统作为解决信息过载的方法应运而生，被广泛的应用到了当前的电子商务系统[1]。而基于协同过滤的推荐算法无疑是最广泛使用的算法[2]，其主要分为基于用户（User-based）和基于商品(Item-based)的推荐算法[3]。基于用户的协同过滤算法主要通过计算用户之间的相似性，通过对与目标用户相似性较高的用户对商品的评价信息从而推荐给目标用户。基于项目的协同过滤算法则是查找项目之间的相关性。但是在电子商务网站当中，用户评分数据不会超过项目总数的百分之一[4]，稀疏性以及实时性都是急需解决的问题。

　　针对推荐实时性问题，文献[5]在Hadoop平台上实现了User-based并行协同过滤推荐算法；文献[6]在Hadoop平台上实现了Item-based协同过滤推荐算法，其时间复杂度为O(n2m2)；燕存[7]针对其时间复杂度过高的问题，提出了一种改进的Item-based协同过滤推荐算法。针对数据稀疏性问题，王雪蓉[8]研究了将用户行为关联聚类以实现更好的推荐效果，任帅[9]基于用户行为模型和蚁群聚类以实现更合理的推荐。Spark作为一个新的开源集群计算框架，其基于内存计算以及粗粒度的RDD机制非常适合于迭代型的计算。本文针对推荐实时性以及数据稀疏性问题，基于Spark平台，提出一个分层的协同过滤推荐算法。

1 Spark相关技术

　　Spark作为一个分布式框架，它支持内存计算、多迭代处理、流处理与图计算多种范式，非常适合于各种迭代算法和交互式数据分析，Spark的核心抽象模型是RDD（弹性分布式数据集），基于RDD，Spark提供了一个非常容易使用的编程接口。

　　1.1 弹性分布式数据集

　　RDD是不可变的，RDD一旦创建就没有办法对其进行更改，但是却能创建出新的RDD。其次，RDD的不可变性使得Spark提供了高效的容错机制，由于每个RDD都保留有计算至当前数值的全部历史记录，而且其他进程无法对其作出更改。因此，当某个节点丢失数据时，只需要对该节点的RDD重新计算即可，并不影响其他节点的运行。RDD机制如图1所示。

　　1.2 Spark应用程序框架

　　Spark Application的运行架构由两部分组成：driver program(SparkContext)和executor。Spark Application一般都是在集群中运行，如standalone、yarn、mesos等。在这些集群当中提供了计算资源和资源管理，这些资源即可以给executor执行，也可以给driver program运行。根据driver program 是否在集群中，SparkContext又可以分为cluster与client模式。Spark应用程序框架如图2所示。

　　2 用户偏好模型

　　定义1(用户偏好集合)将用户在网站浏览行为中的平均访问时间、点击数目、购买数目、点击收藏比、点击加入购物车、平均收藏与购买间隔以及平均点击与购买间隔7种特征构成用户偏好集和：IA={A1，A2，A3，…，A7}。

　　为了构建用户偏好模型，需要为用户偏好集合中不同的特征赋予不同的权值，以便区分不同特征对模型的贡献程度，如表1。

　　表1中的7种偏好特征从不同程度上代表了用户的行为习惯，为每一种偏好特征赋予一个权值，从而得出的用户偏好模型如下：

　　使用熵权法[10]来确定每一个偏好特征的权值，它通过统计的方法处理后获得权重。将用户ui的偏好特征表示成n×7阶矩阵B=(bij)n×7，其中bij表示用户i第j个特征的值。熵权法的计算过程如下：

　　(1)标准化数据处理，如式（2）、式（3）：

　　通过以上方法便可计算出用户偏好模型中每一种偏好特征的权值。

　　3 并行化EM算法

　　期望最大化（EM）算法是在模型中寻找参数的最大似然估计或者最大后验估计的算法，它从一个最初的假设开始，迭代计算隐藏变量的期望值。再重新计算极大似然估计，直到收敛于一个局部最大似然估计。算法的实现过程如下：

　　(1)估计参数：利用式（5）将每个对象xi指派到对应的用户簇中。

　　其中，p(xi|Ck)=N(k，E(xi))服从方差为E(xi)、期望为k的正态分布，参数估计是对每一个用户簇计算对象的隶属概率。

　　(2)最大化：利用上一步骤的结果重新估计参数以使针对给定数据的分布似然最大化。

　　(3)重复以上步骤直到参数收敛，聚类过程完成。

　　为了实现EM算法的并行化，首先将用户偏好模型数据划分到集群上的每一个节点，即将用户划分成 M个组：U1，… UM，每一组用户为一张二维关系表，行为用户实例，列为偏好特征值，并行化算法如下：

　　(1)Combine users，分别在不同的结点计算任意两个用户的相似度，并将相似度高的两个类别合并成一个类别；

　　(2)Compute similarity，根据式（6）计算每一个类别的相似性；

　　(3)Shufflle，全局hash划分类别；

　　(4)Checkpoint，将不同类别缓存到内存中；

　　(5)Recycle ,根据式（7）对参数求精，并重复此过程，直到完成聚类；

　　(6)Clean,清除中间数据，并将结果按类别存储在不同计算节点上。

4 并行化协同过滤算法

　　Item-based协同过滤将一个用户所购买的商品推荐其匹配的相似商品，即将所有用户对购买的商品的评价作为一个向量，通过向量计算物品之间的相似度。用U对商品i与商品j共同评价的用户集合，则它们之间的相似度sim(i，j)可通过Pearson相关系数计算：

　　将用户评分数据文件存放在HDFS上，每一行数据代表一个用户的历史购买项目记录，详细算法如下：

　　(1)data=sc.textFile(“hdfs://”)，加载数据，每行数据代表一个用户的历史购买项目记录；

　　(2)getItemsAndRatings(data，items，ratings，len)，划分数据，获取到所有项目及评分存入items数组与ratings数组中；

　　(3)(item_a，item_b)=zip(items 1 to len)，将项目两两组成对；

　　(4)(ratings_a，ratings_b)=zip(ratings 1 to len)；

　　(5)shuffle ,全局hash划分数据，将相同项目对划分到同一个结点；

　　(6)Compute Pearson()，由式(8)计算两项目之间的相似度；

　　(7)readItem(key，item1，item2)，从项目对中解析出两个项目；

　　(8)Shuffle，将包含某一项目的所有项目划分到同一个结点中；

　　(9)Cache(key，value)，缓存项目及其相似度列表；

　　(10)Prediction()，预测未购买商品的评分；

　　(11)saveAsTextFile()，输出并存储用户推荐商品列表。

5 基于Spark分层协同过滤推荐算法

　　在执行算法之前，首先需要将数据集加载到HDFS文件系统中，首先Spark会生成一个SparkContext全局常量，将基于SparkContext从HDFS上读取数据，textFile()这个函数有助于从HDFS上读取数据并形成一行一行为基础的RDD。可以使用cache将数据加载到内存以便重复使用。详细算法实现如下：

　　(1)准备：搭建Hadoop与Spark集群，并将数据存放到HDFS；

　　(2)由用户行为计算偏好特征权值；

　　(3)存储用户偏好特征数据；

　　(4)并行EM算法对用户聚类；

　　(5)将不同用户簇存放不同结点；

　　(6)将用户－评分数据存入相同用户结点，数据本地性；

　　(7)并行运行协同过滤算法；

　　(8)预测用户－商品评分；

　　(9)形成推荐列表并保存。

6 实验及分析

　　在实验集群当中，有一个master节点、3个slaves节点，每个节点的内存为8 GB，2核。集群当中安装的是Hadoop2.4.1与Spark1.3.0版本。程序采用IntelliJ集成开发环境完成，本实验主要实现了基于Spark的分层协同过滤算法并与基于MapReduce的并行算法的对比。

　　(1)准确率、时间复杂度分析

　　实验一数据采用阿里巴巴云平台的天池数据，总共十万多条行为记录，MapReduce使用并行Item-based协同过滤算法，Spark使用分层协同过滤推荐算法，实验结果如表2所示。

　　从表1可以看出，基于Spark的分层协同过滤算法在准确率上比普通的协同过滤算法更高，并且大大节约了时间，提高了性能。

　　(2)性能表现

　　实验二测试Spark实现的分层协同过滤算法的扩展性，分析了在不同节点个数上的性能表现，如图3所示。

　　从图中可以看到，当节点数量达到一定程度以后，其所消耗的时间并没有减小得太厉害。接下来将会测试在不同大小的数据集上算法所表现出来的性能。

7 结束语

　　协同过滤是推荐算法中最为广泛使用的推荐算法，研究协同过滤的并行化算法也非常多。本文在前人的基础上，提出一种基于Spark的分层协同过滤推荐算法，其核心是把用户按不同的偏好特征划分不同的用户簇，之后针对不同的用户簇作协同过滤推荐。另外，在Spark平台上实现该算法并与MapReduce的算法比较。实验结果表明，算法提高了推荐准确率与时间性能，并具有一定的拓展性。

参考文献

　　[1] MALTONI D，MAIO D，JAIN.A handbook of fingerprint recognication[M].Berlin，Springer，2009.

　　[2] LINDEN G，SMITH B，YORK J.Amazeon.com recommenda-tions：item-to-item collaborative filtering[J].IEEE Internet Computing，2003，7(1)：76-80.

　　[3] SCHAFER J B，FRANKOWSKI D，HERLOCKER J，et al.Collaborative filtering recommender systems[M].Berlin Heidelberg：Springer，2007：291-324.

　　[4] SUN X H，KONG F S，YE S.A comparison of several algorithms for collaborative filtering in startup stage[C].Proceedings of the 2006 IEEE International Conference on Networking，Sensing and Controlling.Washington，DC：IEEE  Computer Society，2006：25-28.

　　[5] ZHAO Z D，SHANG M S.User-based collaborative-filteringrecommendation algorithms on hadoop[C].Third International

　　Conference on Knowledge Discovery and Data Mining.Thailang：IEEE，2010：478-481.

　　[6] JIANG J，LU J，ZHANG G，et al.Scaling-up item-based collaborative filtering recommendation algorithm based on hadoop[C].2011 IEEE World Congress on Services(SER-VICES).Washington：IEEE，2011：490-497.

　　[7] 燕存，吉根林.Item-Based并行协同过滤推荐算法的设计与实现[J].南京师大学报(自然科学版)，2014，37(1)： 71-76.

　　[8] 王雪蓉，万年红.云模式用户行为关联聚类的协同过滤推荐算法[J].计算机应用，2011，31(9)：2421-2426.

　　[9] 任帅，王浙明，王明敏.基于用户行为模型和蚁群聚类的协同过滤推荐算法[J].微型电脑应用，2014，30(3)：5-9.

　　[10] COVER T M，THOMAS J A.Elements of information theory[M].[S.1.]：Wiley-Interscience，2006.