0 引言

海量信息的增长导致了严重的信息过载，如何从大量的信息中快速地分析出用户的兴趣爱好, 主动为用户推荐感兴趣的信息成为当前研究的热点问题。Slope One算法是由Lemire等^[1]提出的一种协同过滤推荐算法，该算法具有简单、高效、推荐准确率高并且能够缓解冷启动问题等优点; 但随着数据规模的不断增大，该算法面临的数据稀疏性、实时性、可扩展性等问题越来越严重，导致推荐质量大幅下降。

针对这些问题，学者们提出了许多改进方法。刘林静等^[2]提出一种基于用户相似性的加权Slope One算法，首先根据项目相似性进行预测填充，然后根据用户相似性形成最近邻居集合并进行推荐预测，有效地缓解了数据稀疏性问题。Zhang等^[3]提出一种引入用户兴趣相似性计算的Slope One算法，在用户最喜爱的项目中计算相似度矩阵，从而提高推荐准确性。文献[4-6]通过引入聚类，从而减小算法计算复杂度，提高推荐实时性。于洪等^[7]提出利用三分图的形式结合用户、标签、项目属性、时间等信息获得个性化推荐的算法，在一定程度上解决了新项目的冷启动问题。针对运行效率问题，文献[8-10]提出基于Hadoop平台的推荐算法，有效提高了算法的可扩展性。

本文基于以上研究，针对加权Slope One算法仅考虑利用项目评分来度量对象之间的相似性，较少考虑项目本身的属性特征和用户兴趣随时间的变化特征，这在很大程度上影响了推荐准确性。因此本文综合项目评分、项目属性、时间权重等信息，结合聚类算法和具有内存计算、迭代计算优势的Spark框架^[11]，提出一种改进的基于聚类和Spark框架的加权Slope One算法，以进一步提高Slope One算法的预测准确性、运行效率和可扩展性。

1 相关工作 1.1 用户—项目评分矩阵

在传统的协同过滤推荐算法中，利用m×n阶用户—项目矩阵储存用户对项目的评分信息。使用集合{u₁, u₂, …, u_m}表示m个用户，使用集合{i₁, i₂, …, i_n}表示n个项目，使用R_{i, j}表示用户对项目的评分值。表 1为用户—项目评分矩阵的一个例子。

1.2 传统的Slope One算法

Slope One算法的预测形如一个线性函数f(x)=x+b，假设一个用户对两个项目的评分分别为x、y(该算法假设x和y之间是线性的，形如y=x+b)。通过将这两个项目有过共同评分的用户评分集进行线性拟合，得到b的估计值，从而对未评分项目预测评分。因此，在进行推荐预测时，只需要在预处理过程中根据式 (1) 计算出所有项目之间的平均偏好差异值矩阵{dev_{j, i}}，然后再根据式 (2) 即可计算出目标用户对某个未评分项目的预测评分值P(u)_j。

$ de{v_{j,i}} = \sum\limits_{u \in {S_{j,i}}(\chi )} {\frac{{{R_{u,j}} - {R_{u,i}}}}{{card({S_{j,i}}(\chi ))}}} $

(1)

$ \begin{array}{l} P{(u)_j} = \frac{1}{{card({R_j})}}*\sum\limits_{i \in {R_j}} {(de{v_{j,i}}} + {R_{u,i}});\\ \;\;\;\;{R_j} = \{ i\left| {i \in S(u),i \ne j.card({S_{j,i}}(\chi ))} \right. > 0\} \end{array} $

(2)

其中:χ表示训练集，S_{j, i}(χ) 表示评价过项目i, j的用户集合，R_{u, j}、R_{u, i}分别表示用户u对项目j，i的评分值 (u∈S_{j, i}(χ))，R_j为用户u已经评价过的项目集合，card(N) 表示集合N中的元素个数。

以表 1为例，预测用户u₁对项目i₃的评分。考虑对项目i₃已评分的用户u₂、u₃，则首先使用式 (1) 计算评分偏差值dev_{3, 2}=[(3-3)+(4-2)]/2=1，dev_{3, 4}=(3-3)/1=0；然后使用式 (2) 计算用户u₁对项目i₃的评分P(u₁)₃=[(4+1)+(5+0)]/2=5；最后在预测所有的未评分项目之后根据预测评分高低为目标用户生成Top-N推荐。

1.3 项目评分相似性

相似性的度量是推荐算法中非常重要的一部分，用来衡量项目之间的相关程度, 其计算结果的准确性决定了最近邻居集合的准确性，因而也决定了评分预测值的准确性。相关相似性 (Pearson系数) 是以用户评分为基础，并在此基础上减去项目的平均评分，保留了用户的打分偏好，更能反映出项目之间的相关性，因此本文使用式 (3) 计算项目之间的评分相似性:

$ sim\_score(i,j) = \frac{{\sum\limits_{u \in {U_{ij}}} {({R_{u,i}} - {{\bar R}_i})({R_{u,j}} - {{\bar R}_j})} }}{{\sqrt {\sum\limits_{u \in {U_{ij}}} {{{({R_{u,i}} - {{\bar R}_i})}^2}} } \sqrt {\sum\limits_{u \in {U_{ij}}} {{{({R_{u,j}} - {{\bar R}_j})}^2}} } }} $

(3)

其中：U_ij表示同时评价项目i和项目j的用户集合，R_i表示项目i的平均评分，R_j表示项目j的平均评分。

2 基于聚类的加权Slope One算法 2.1 时间衰减函数

由于时间的变化，用户的关注点会随之改变, 而用户最近的行为对用户影响程度相对较大，对推荐贡献的作用也相对较高，所以应该赋予较大权重^[12]。然而传统Slope One算法并没有考虑到用户兴趣随时间的变化，同等看待不同时间的评分值，因此得到的平均偏好差异值矩阵和评分预测值在某种程度上是不准确的，严重降低了推荐准确性。

本文采用改进的时间衰减函数对项目评分值进行加权处理，对距离当前时间较近的评分值赋予较大的权重，对距离当前时间较远的评分值赋予较小的权重，以此来反映用户兴趣随时间的变化。时间衰减函数如式 (4)、(5) 所示：

$ f(\left| {t({R_{u,j}}) - t({R_{u,i}})} \right|) = 1/(1 + \alpha \left| {t({R_{u,j}}) - t({R_{u,i}})} \right|) $

(4)

$ f\left( {t({R_{u,i}})} \right) = 1/(1 + \alpha \left| {{t_0} - t({R_{u,i}})} \right|) $

(5)

其中：t₀表示当前的时间；t(R_{u, i}) 表示用户u对项目i的评分时间；t(R_{u, j}) 表示用户u对项目j的评分时间；α是时间衰减因子，α值的大小代表用户兴趣变化的快慢。用户兴趣变化大，α取较大值；用户兴趣变化小，α取较小值。

本文在项目评分相似性计算时考虑时间因素的影响，为每个项目评分值赋予相应的时间权重, 这样更能体现出项目之间的实际相似程度，从而进一步提高相似性度量的准确率。优化后的Pearson系数计算公式如式 (6) 所示：

$ \begin{array}{l} tsim\_score(i,j) = \\ \frac{{\sum\limits_{u \in {U_{ij}}} {({R_{u,i}} * f(t({R_{u,i}})) - {{\bar R}_i})({R_{u,j}} * f(t({R_{u,j}})) - {{\bar R}_j})} }}{{\sqrt {\sum\limits_{u \in {U_{ij}}} {{{({R_{u,i}} * f(t({R_{u,i}})) - {{\bar R}_i})}^2}} } \sqrt {\sum\limits_{u \in {U_{ij}}} {{{({R_{u,j}} * f(t({R_{u,j}})) - {{\bar R}_j})}^2}} } }} \end{array} $

(6)

2.2 项目属性相似性

对于系统刚刚加入的新项目，由于用户对其进行评分的信息相对较少，仅利用评分相似性加权实现预测和推荐，会造成较大误差，影响推荐质量。因此，本文考虑引入项目属性相似性来缓解此问题。对于任何一个项目，不管是被用户评价过的项目还是刚刚加入系统的新项目，都具备相应的属性信息。故本文在相似度计算时加入项目属性信息，利用n×g阶矩阵储存该信息^[7]，使用集合{i₁, i₂, …, i_n}表示n个项目，集合{p₁, p₂, …, p_g}表示g个属性，Attr_{i, k}表示项目i具备第k个属性。那么项目i和项目j之间的属性相似性计算公式如式 (7) 所示：

$ sim\_attr\left( {i,j} \right) = \sum\limits_{k = 1}^g {1/(1 + \left| {Att{r_{i,k}} - Att{r_{j,k}}} \right|)} $

(7)

2.3 项目综合相似性

当用户对项目的评分信息比较多时，考虑到应该更多地倾向于使用项目评分相似性来度量项目相似度; 在新项目刚刚加入或者用户评分信息非常少时，应该更多地倾向于使用项目属性相似性来度量项目相似度, 故本文将项目评分相似性和项目属性相似性进行融合，并采用Sigmoid函数对其进行平滑过渡处理^[13]，融合后的综合相似度计算公式如 (8) 所示：

$ sim(i,j)\_mix = \gamma \cdot tsim\_score(i,j) + \beta \cdot sim\_attr\left( {i,j} \right) $

(8)

其中:β=1-1/[1+e^-card(U_i)]; γ=1-β。

2.4 Canopy-K-means项目聚类算法

随着项目数量的不断增长，在全局计算平均偏好差异值矩阵将更加费时费力，不能满足推荐实时性的要求^[4]。故本文引入聚类算法，通过聚类，将特征、评分值相似的项目快速划分到相同的簇中。然后在与目标项目相似的部分类中查找最近邻居，从而缩短查找时间，提高算法的实时响应速度。由于传统K-means聚类算法初始中心点的选择是随机的，不确定性较大，因此本文利用Canopy算法对其进行优化，避免初始聚类中心和k值选取的盲目性，提高聚类准确性。其具体实现的伪代码描述如下。

Input：项目评分向量集I={I₁, I₂, …, I_n}，Canopy距离阈值T1, T2(采用交叉检验方式获得)

Output：个项目聚类集合，聚类中心集合W′

1) If (Q=null)

2)     从I中任取一个向量, 加入Q并从中删除

3) End If

4) While (I！=null)

5)     遍历I, 利用欧氏距离快速计算每个向量点与Q中点的距离dist[i]

6)     If (dist[i] < T2), 将该点加入到此点所属的Canopy, 并从中删除

7)         Else If (dist[i] > T1), 将该点加入Q，并从中删除

8)         Else将该点加入到此点所属的Canopy

9)     End If

10) End While

11) K-means算法初始中心点W←Q

12) While (I！=null)

13)     按式 (8) 依次计算I中其他向量点到W中各点的相似度，并将其划分到相似度最高的类中

14)     For (W! =W′)

15)         对每个类重新计算均值，并作为新的聚类中心W′

16)     End For

17) End While

2.5 预测和推荐

传统加权Slope One算法评分预测时将项目之间的共同评分用户数作为权重，共同评分用户较多的项目所占权重相对较大，容易产生较大的误差，而且该方法忽略了项目相似性的问题，其对目标项目的评分预测影响作用更大。为进一步提高预测准确性，本文将项目综合相似度作为评分预测权重，并结合时间衰减函数，进一步优化Slope One模型，优化后的平均偏好差异值矩阵{dev_{j, i}}计算公式和预测评分值计算公式分别为式 (9)、(10)：

$ de{v_{j,i}} = \sum\limits_{u \in {S_{j,i}}(\chi )} {\frac{{({R_{u,j}} - {R_{u,i}})*f(\left| {t({R_{u,j}}) - t({R_{u,i}})} \right|)}}{{card({S_{j,i}}(\chi ))}}} $

(9)

$ P{(u)_j} = \frac{1}{{sim(i,j)\_mix}}\sum\limits_{i \in Nei} {(de{v_{j,i}}} + {R_{u,i}} * f\left( {t({R_{u,i}})} \right) $

(10)

2.6 基于聚类的加权Slope One算法描述

综合上述所述，基于聚类的加权Slope One算法的具体步骤如下：

1) 初始化数据集，构造目标用户u的未评分项目集合Items。

2) 利用式 (6)、(7) 分别计算评分相似性、属性相似性，再利用式 (8) 计算综合相似度。

3) 根据2.4节所示，利用Canopy-K-means算法完成项目聚类。

4) 利用式 (8) 计算目标项目I_j与每个聚类中心的相似度，在相似度大于阈值ε的部分聚类中搜索该项目的最近邻居集合，并选取k个相似度较高的项目I_j构成目标项目的最近邻居集合Nei={I₁, I₂, …, I_n}，其中sim(i, j)_mix(I₁, I_j) 最高，sim(i, j)_mix(I₂, I_j) 次之，相似度依次递减。

5) 在目标项目I_j的最近邻居集合中利用式 (9)、(10) 进行评分预测。

6) 根据预测评分值P(u)_j, 为目标用户u生成Top-N个推荐项目。

2.7 时间复杂度分析

由于项目数量很多，导致综合相似度计算的时间复杂度非常大，为O(mn²)。但考虑到项目更新缓慢，故可对其进行离线并行计算，从而不会影响在线推荐效率。另外对于比较耗时的聚类，本文也选择进行离线周期并行化聚类，离线计算聚类中心，在线计算目标项目与k个类别内的p个项目的相似度，p是每个类中的项目数。因为k≪n，p≪n，所以计算目标项目与聚类中心、聚类内项目相似度的时间复杂度O(k*n)+O(p*n)≪O(mn²)，故本文算法可有效降低时间复杂度。

3 基于聚类和Spark框架的加权Slope One算法

随着项目数和用户数的不断增多，Slope One算法在执行过程中的中间结果也随之增多，当超过内存容量时只能先写到读取速度缓慢的磁盘中，严重影响了推荐效率。因此本文利用具有内存计算优势的Spark框架，加快数据处理速度，提高算法的运行效率。

3.1 Spark框架

Spark是一套开源的、基于内存的可以运行在分布式集群上的并行计算框架，具有高效性、通用性、高容错性等优点^[14]。利用弹性分布式数据集 (Resilient Distributed Dataset, RDD) 实现应用任务调度、远程过程调用 (Remote Procedure Call, RPC)、序列化和压缩等操作；利用有向无环图 (Directed Acyclic Graph, DAG) 实现各阶段任务的并行执行；利用Cache机制降低数据共享和迭代计算中的I/O负载问题，从而有效提高了数据处理速度。

每个Spark应用由驱动器程序 (drive program) 发起并负责创建相应的SparkContext。在获取到集群进行所需的资源后，SparkContext将得到集群中工作节点上对应的Executor，之后再将应用程序代码发送到各Executor, 最后将任务 (Task) 分配给executors执行。本文中使用基于YARN的Spark，具体工作流程如图 1所示。

3.2 基于聚类的加权Slope One算法的并行化实现

在推荐过程中由于项目数量非常多，在聚类、寻找K近邻和预测过程中需要进行大量的相似度计算和平均偏好差异值计算，因此本文利用并行化来提高计算效率，提高算法的运行速率。该过程具体化为两个阶段:阶段一为Canopy-K-means聚类并行化，阶段二为加权Slope One算法的并行化。

在阶段一中，首先对数据集进行预处理形成〈key, value〉键值对，并将结果存入HadoopRDD中。然后调用groupBykey () 函数获取User-Item，Attribute-Item的倒排表，并调用reduceBykey () 函数统计Item之间的共同评分的User及自己的评分用户数、属性数等。然后利用Similaritymap () 函数计算评分相似性、属性相似性，并在此基础上计算综合相似性并存入SimilarityRDD中。接着利用Clustermap () 迭代执行Canopy-K-means算法，直到完成所有数据向量点的聚类，利用ClusterReduce () 归并、汇总最终聚类结果，并将其广播到各子节点中。

在阶段二中，首先调用groupByKey函数计算Item之间的平均偏好差异值，然后利用partitionNum () 从partitionRDD中读入上述聚类结果并确定分区个数，同时调用itemsClustersLines.map () 为目标项目生成最近邻居集合Nei。接着利用itemsSimi=itemsSimiLines.map{}.cache导入综合相似度，并利用predict () 函数生成预测评分 ((〈item1, item2〉, sim_mix) $\xrightarrow{{{\text{join}}}}$ (〈item1, item2〉, dev) $\xrightarrow{{{\text{map}}}}$ (〈user, item〉, predict〉))。最后通过recommendations=bestModel.get.predict (candidates.map ()).collect ().sortBy (-_.rating).take (10) 函数向用户推荐Top-10部电影，完成项目推荐。

4 实验结果与分析 4.1 实验环境、测试数据集及评价指标

实验平台是在Hadoop2.6.0的YARN基础上部署Spark框架，在Vcenter中创建4台虚拟机，包含1个Master节点和3个Slave节点。操作系统版本均为Ubuntu 14.04.3-Server-AMD 64，Hadoop版本为2.6.0，Spark版本为1.4.0，Java开发包版本为JDK1.7.0_79。

实验采用由GroupLens Reaearch提供的MovieLens数据集 (http://grouplens.org/dataset/)，包括ml-100k的数据包 (包含943个用户对1 682部电影的100 000条评分记录) 和ml-1M的数据集 (包含6 040个用户对3 952部电影的1 000 209条评分记录)。实验采用十折交叉验证法进行验证，将数据集随机分为不相交的10个包，轮流将其中的9份作为训练集，其余1份作为测试集，每次实验重复执行10次，最后的实验结果采用10次实验结果的平均值。

本文使用平均绝对误差 (Mean Absolute Error，MAE) 来衡量算法的评分预测准确性，MAE值越小，预测精度越高；反之，则越差；并在此基础上探究本文算法在不同平台和不同节点下的运行时间和加速比 (Speedup)、扩展比 (Scaleup)，以验证算法的执行效率。

$ MAE = \frac{1}{{card\left( {\chi '} \right)}}\sum\limits_{u \in \chi '} {\frac{1}{{card\left( {S\left( u \right)} \right)}}} \sum\limits_{i \in S\left( u \right)} {\left| {P{{\left( u \right)}_i} - {R_{u,i}}} \right|} $

其中χ′表示测试集。

$ Speedup = {T_s}/{T_p} $

其中：T_s是单节点运行时间，T_P是P个节点运行时间。

$ Scaleup = Speedup/{T_p} $

其中：P为集群节点数目。

4.2 实验结果

实验一    探究时间衰减因子权重α、相似度阈值ε对实验结果的影响。

采用ml-100k的数据集，假定在聚类未引入时间权重情况下，最近邻居数k=30时，将α从0.1依次递增到0.9，分别观察ε=0.2，ε=0.3，ε=0.4时MAE的变化。实验结果如图 2所示，无论ε为何值，当α逐渐增大时，MAE都是先减小后增大，并在α=0.3时取得最小值，而且变化幅度不大，这说明该系统用户对电影的兴趣变化比较缓慢。另外，在ε=0.4时，MAE较高，推荐准确性较差。这是因为相似度阈值设置较高，在构造最近邻居集时，只需要在符合阈值条件的几个候选聚类中查询、计算即可，提高了算法的响应速度。但另一方面，由于查询候选聚类过少，在某种程度上造成一部分真正邻居项目的遗漏，从而影响了推荐结果的准确性。因此，基于保证推荐准确性和提高算法响应速度两方面的考虑，设定α=0.3，ε=0.3。

实验二    验证本文算法的准确性、有效性。

采用ml-100k的数据集，将本文算法与传统Slope One算法、文献[2]中基于用户相似性的加权Slope One算法、本文提出的优化算法、基于Spark框架的该算法 (4个节点) 在不同的邻居数下k的MAE比较 (α=0.3，ε=0.3，最近邻居数k从25依次递增到200，间隔为25) 如表 2所示。

从表 2可以看出，随着k值的增大，各个算法的MAE值都是会随之降低:当k≥50时，本文算法MAE值小于传统Slope One算法；当k≥75时，其MAE值小于文献[2]算法；当邻居数k≥150时，其MAE值慢慢趋于稳定。另外，基于Spark框架下的优化算法MAE值和串行方式下基本相平，这说明基于Spark框架的该算法在保证准确率的同时更适合用于大规模数据的推荐预测中。

另外，为进一步验证本文算法的有效性，将传统Slope One算法、基于聚类的Slope One算法、本文优化的Slope One算法 (引入聚类和综合相似度) 在不同邻居数k下的MAE值进行比较。如图 3所示，在k=175时，引入聚类后的算法MAE值降低了9.9%，进一步引入综合相似度后，MAE值又降低了4.2%，这说明引入聚类和综合相似度，可有效提高算法的预测准确性。

实验三    比较本文算法在不同平台、不同数据集的运行效率。

采用ml-100k、ml-1M的数据集，分别统计本文算法在Hadoop平台和Spark框架下不同节点数时的运行时间。实验结果如表 3所示，随着节点数目增多，两种框架下的运行时间都逐渐减小，并且Spark框架下的运行时间更短。这说明Spark框架的执行性能要优于Hadoop平台，运行效率平均可提高3.5~5倍。主要原因是算法在Hadoop平台中的数据计算、I/O传输时花费时间较多，这在大样本数据集中尤为明显。而Spark框架将中间结果缓存在内存中，减少了数据读取和传输时间，从而大幅提高了运行速度。

为进一步测试Spark框架下本文算法的可扩展性，分别测试ml-100k、ml-1M数据集在不同节点下的加速比、扩展比。实验结果如图 4、图 5所示，随着节点数目的增加，较大规模的数据集加速比提高更快，基本呈线性增长，扩展比变化趋势也比较平缓。这说明Spark框架在处理本文算法上具有良好的可扩展性，并且这种优势会随节点数目的增加、数据集的增大而更加明显。

5 结语

本文主要对影响Slope One算法的预测准确性和可扩展性等各因素进行优化，将项目综合相似度与Slope One算法相结合，利用Canopy-K-means聚类算法生成最近邻居集合; 并在相似度计算、预测过程中引入时间权重，有效地提高了Slope One算法的推荐准确性。另一方面针对可扩展性问题，结合Spark框架实现其并行化，有效地提高了该算法对大规模数据集的处理效率，提高了算法的可扩展性。下一步工作将在改善数据稀疏性方面^[15]展开研究，以进一步提高算法的综合性能。