基于Spark的Slope One算法优化与实现

梁化强 唐坚刚

摘 要：传统Slope One算法未考虑用户相似性和項目相似性对评分效果的影响，从而导致推荐准确率不高，并且在当前大数据背景下，传统Slope One算法运行效率低下。针对以上问题，提出一种基于Spark的改进加权Slope One算法，该算法融入了相似性计算、活跃用户筛选和用户聚类等技术，并在Spark平台上实现了并行化。通过在MovieLens数据集上进行试验验证，并比较算法在Spark和Hadoop平台并行化的运行效率，证实了该算法可以有效降低MAE，且在Spark平台下运行效率更高，更适用于大数据处理场景。

关键词：Slope One；聚类；用户相似性；项目相似度；Spark

DOI：10.11907/rjdk.172877

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2018）006-0092-03

Abstract：The traditional slope one algorithm does not consider low user similarity and item similarity on scoring effect， which leads to low recommendation accuracy， and in the current big data background， it suffers from low efficiency of operation. In order to solve the above problems， an improved weighted Slope One algorithm based on Spark is proposed in this paper. The algorithm integrates similarity computing， active user filtering and user clustering technology， and implements parallelization on Spark platform. Through the experiments on MovieLens data sets， this article confirms that the algorithm can effectively reduce MAE， and compares the running efficiency of the parallel algorithm in Spark and Hadoop platform to confirm this algorithm in Spark platform runs more efficiently， more suitable for big data processing.

Key Words：Slope One； clustering； user similarity； project similarity； Spark

0 引言

随着信息资源的爆炸式增长，人们对个性化服务的需求逐渐增加，推荐系统已成为电子商务、社交网络等领域的重要技术。Slope One算法是由Lemire等在2005年提出的一种推荐算法，其是一种基于项目的算法，且原理简单，推荐准确率高。但该算法也存在一些不足，如未考虑数据稀疏性，以及用户与物品相似性等问题。

因此，很多人对Slope One算法进行了优化改进。例如，刘伟江[1]采用平均值和SVD技术对用户项目评分矩阵进行填充，但未考虑项目相似度和用户相似度的影响；李剑锋[2]提出一种局部近邻Slope One算法，该算法需要计算用户针对不同商品的邻居用户，但是对于每一次推荐都要计算目标用户的近邻用户，对于一个有几百万活跃用户的电子商务网站而言，计算量非常大；蒋宗礼[3]提出一种基于聚类的Slope One算法，但没有对用户进行筛选，将全部用户进行聚类容易混入噪声数据，聚类效果并不理想。

本文提出一种基于聚类与Spark的改进加权Slope One算法，首先依据活跃函数筛选出活跃用户，采用K-means算法确定k个聚类中心。因为在现实环境中，用户是很少评分或不评分的，用那些评分较多的优质用户进行聚类，不仅可以减少计算量，而且可以去除噪声，提高聚类效果；然后分别计算每个聚类的项目评分偏差表和物品相似度表。因为相似用户对物品具有相似偏好，因此不同类用户应该使用不同的项目评分偏差表和项目相似度表。上述两步都可以离线计算，并将计算结果保存在数据库或文件系统中，方便以后使用；最后对于目标用户确定其所属聚类，采用该类的项目评分偏差表和项目相似度表，并将项目相似度权重乘以共同评价物品数作为混合权重，运行Slope One算法。

1 Slope One算法理论

1.1 基本Slope One算法

Slope One算法基本思想是用一元线性方程计算两物品之间的平均偏差，对所有用户在不同项目间的评分数据计算得到最终偏移值参数b的平均值，最后结合目标用户对已有商品的评分，将偏移值带入一元方程，以估计目标用户对待推荐商品的评分情况。定义项目i和j之间的平均评分偏差为dev-i，j，（u）-j代表目标用户u对项目j的预估评分。

1.2 两种SlopeOne改进算法

（1）加权Slope One算法。基本的Slope One算法并没有考虑到共同评分的项目数量，假如有100个用户同时对项目j和i进行评分，而只有10个用户对项目j和k进行评分，显然dev-j，i比dev-j，k效果更好。因此，将用户数目card（U-i，j）作为权重，则目标用户u对j的评分公式如下：

（2）双极Slope One算法。双极Slope One的基本思想是将用户评分矩阵划分为“like”和“dislike”两类，并将用户对该项目评分与用户对所有商品的平均评分进行对比，大于平均评分记为“like”，小于平均评分则记为“dislike”。

其中，式（4）、式（5）中，S（u）表示用户u有评分记录的项目集合，r-u 表示用户u对所有物品的平均评分。

2 基于聚类与Spark的加权Slope One算法

2.1 项目相似度计算

相似度可用来衡量项目之间的相似程度，皮尔逊相关相似性是以用户评分减去项目平均评分，从而更好地反映出项目之间的相关程度。因此，本文使用皮尔逊相似性计算项目之间的相似度：

2.2 项目综合权重

加权Slope One算法中使用项目之间的共同评分数量作为权重。例如，项目i和j的共同评分数量为10，项目i与k的共同评分数量为100，但项目j与i的相似度很高，项目j有可能是新加入的项目，用户对项目j的评分数量并不多，从而导致评分越少的项目被推荐的可能性越低。因此，本文使用项目综合权重如式（11）所示：

2.3 活跃用户评定

在实际生产环境中，存在活跃性极小的用户，他们对项目的评分数据极少，这些用户大多是新用户。在对新用户进行推荐时，往往推荐热门产品效果较好。因此，为了减少时间消耗并提高聚类效果，本文在预测评分前筛选出活跃用户，从而既能提高预测精度，又能减少时间消耗。

当用户的项目评分数量小于0.01%时为不活跃用户，定义为Uina；当用户项目评分数量大于0.01%时为活跃用户，定义为Uact。因此，用户总集合U=Uina∪Uact。用户u对所有项目的评分总数记为Num（itemu），所有项目总数为Num（item），则：

在预测评分时，仅对Uact集合中的用户进行聚类。

2.4 K-means用户聚类

K-means算法是典型的基于距离的聚类算法，采用距离作为相似性评价指标，即认为两个对象的距离越近，其相似度越大。k个初始类聚类中心点的选取对聚类结果具有較大影响，因为K-means算法容易产生局部最优，为此本文对k进行多次选取，并对每个选定的k值进行多次重复试验。

2.5 算法流程

综上所述，基于聚类的加权Slope One算法的具体步骤如下：①在总项目集中查找目标用户u的未评分项目集合记为Items；②利用公式（13）筛选出活跃用户集Uact；③对活跃用户集Uact进行K-means聚类，得到k个聚类中心，以及k个用户集合U-1，U-2，…，U-k；④根据式（1）、（10）分别计算k个用户集合的项目评分偏差矩阵与项目相似度矩阵，得到项目评分偏差矩阵K-U-1，K-U-2，…，K-U-k，项目相似度矩阵L-U-1，L-U-2，…，L-U-k；

⑤计算用户u到k个聚类中心的距离，确定用户u所属的用户集合U-u，U-u为U-1，U-2，…，U-k其中之一；⑥根据K-U-u、L-U-u（K-U-u为用户u所在用户集合的项目评分偏差矩阵，L-U-u为用户u所在用户集合的项目相似度矩阵）可以计算式（11）、（12），其中dev-ij在K-U-u中查找，得到p（u）-j；⑦根据P（u）-j为目标用户u生成前N个推荐项目。

3 试验结果与分析

3.1 实验环境、测试数据集及评价指标

在VMware中创建4台虚拟机，包含1个Master节点和3个Slave节点。操作系统均为Ubuntu14，Spark版本为2.1.0，JDK版本为1.8。实验数据采用GroupLensMovieLens数据集中的ml-100k数据。本文采用十折交叉验证法，将数据集随机分为10等份，并将其中9份作为训练数据集，最后1份作为测试数据集，每次试验重复执行10次，采用10次试验结果的平均值作为最后结果。

3.2 试验结果

实验一：验证本文算法的准确性、有效性。本文算法与传统Slope One算法以及加权Slope One算法在不同K值选择下的MAE比较如表1与图1所示。

图1中k为对活跃用户划分的聚类个数，可以看出随着聚类个数k的增大，本文优化的Slope One算法MAE值降低，但当k≥11时，MAE值有所回升，且当k取11左右时得到最低的MAE。试验证明将用户分为11个类时，Slope One算法运行效果最好，MAE值最低。

试验二：比较本文算法在不同平台上的运行效率。比较本文算法在Hadoop平台和Spark平台的运行效率，试验结果如表2所示，说明Spark平台的执行性能优于Hadoop平台。

4 结语

针对传统Slope One算法未考虑用户与物品相似性，以及在当前大数据环境下运行效率较低的问题，提出一种基于聚类与Spark的改进加权Slope One算法。该算法通过少而精的数据从数据来源角度提升算法的性能和准确率。试验结果表明，本文算法相比于其它Slope One算法，预测精度有所提高。而且通过在Hadoop和Spark大数据平台上的比较，说明基于Spark的Slope One算法更适用于大数据场景。然而，该算法还存在不足之处，例如如何在数据稀疏性条件下产生精确推荐，将是以后需要完善的地方。

参考文献：

[1] 刘伟江，王颖.奇异值分解法在预测用户页面兴趣度中的应用[J].数理统计与管理， 2012，31（2）：325-332.

[2] 李剑锋，秦拯. 一种基于局部近邻Slope One协同过滤推荐算法[J].计算机工程与科学， 2017，39 （7）：1346-1351.

[3] 蒋宗礼，杜倩. 基于聚类和项目相似性的Slope One算法优化[J].计算机与现代化，2016（8）：22-26.

[4] 陆胜伟，唐振民，吕建勇. 基于时间因子的Slope One协同过滤推荐算法[J].信息技术，2016（10）：1-5.

[5] LEMIRE D， MACLACHLAN A. Slope One predictors for online rating-based collaborative filtering[J]. Computer Science， 2007.

[6] ZHANG Z，TANG X，CHEN D.Applying user-favorite-item-based similarty into Slope One scheme for collaborative filtering[C]. Proceeding of the 2014 World Congress on Computing and CommunicationTechnologies.Washington，DC：IEEE Computer Society，2014：5-7.

[7] YOU H，LI H，WANG Y，et al.An improved collaborative filtering recommendation algorithm combining item clustering and Slope One scheme[J].Lecture Notes in Engineering & Computer Science，2015，2215（1）：313-316.

[8] ZHANGY L，MA M M，WANG S P.Research of userbased co11aborative filtering recommendation algorithm based on Hadoop [EB/OL].[2016-06-20].http：∥www.atlantis-press.Com/php/downloadpaper.php？id=22451.

[9] WANG Y，LOU H Y.Improved Slope One algorithm for collaborative filtering[J]. Computer Science，2011，38（A1）：192-194.

[10] LIU QI，CHEN ENHONG，XIONG HUI，et al.Enhancing collaborative filtering by user interestexpansion personalized ranking[J].IEEE Transactions on Systems，Man，and Cybernetics，Part B：Cybernetics，2012，42（1）：218-233.

[11] GOLDBERG K，ROEDER T，GUPTA D，et al.Eigentaste：a constant time collaborative filtering algorithm[J].Information Retrieval，2001，4（2）：133-151.

（責任编辑：黄 健）