随着信息技术快速发展，信息化数据急剧增加.推荐系统通过学习用户的行为，了解和掌握用户的偏好，从而可以更有针对性地向用户推荐内容.在众多推荐算法中，协同过滤是目前应用最多的算法.协同过滤推荐算法借助目标用户的偏好信息来计算与目标用户相似的邻域用户集，进而将有效项目推荐给目标用户^[1].然而，推荐算法在推荐过程中仍然会有冷启动、数据稀疏性，以及面对大数据时存在的计算性能问题.

随着并行数据处理工具与数据处理技术不断发展，研究者开始尝试在分布式计算平台上实现协同过滤推荐算法. Xu等^[2]通过将用户和项目信息聚类，形成若干个用户-项目子群. Jiang等^[3]在MapReduce上开发并实现了一个基于项目的可扩展协同过滤推荐算法，将运算过程中最消耗计算的3个步骤划分为4个MapReduce阶段. Zhao和Shang^[4]在Hadoop平台上实现了基于用户的协同过滤推荐算法，解决了可扩展性问题.李改等^[5]提出将基于ALS(alternating-least-sqares)的协同过滤推荐算法在Hadoop上进行并行化，解决了传统的基于ALS的协同过滤推荐算法在大规模数据集上的运算问题.以上研究证实，利用MapReduce计算框架实现并行化基于邻域的协同过滤推荐算法是可行的，但是MapReduce仍存在一系列的缺陷：只提供Map和Reduce 2个操作，在表达力上有所欠缺，复杂计算需要大量的job完成，而job之间的依赖关系需要由开发者自己管理；中间结果存放在Hadoop分布式文件系统中，需要多次IO操作^[6]等. Winlaw等^[7]采用并行ALS优化融合方法进行协同过滤，并基于Spark并行化实现该方法，实验结果显示该方法的加速比随着数据集的增加呈线性增长. Kupisz和Unold^[8]采用Tanimoto系数计算相似度，并通过比较基于Hadoop和Spark的运行效率，从而验证了基于Spark平台的推荐更有效率. Li和Liu^[9]提出一种基于Spark的混合推荐算法PRABS(personalized recommendation algorithm based on spark)，通过加权基于用户和基于内容的协同过滤推荐算法，提高了推荐效率和推荐精度. Tu等^[10]提出一种基于Spark的加权正则化交替最小二乘法的协同过滤推荐算法NALS-WR(normalized-alternating-least-squares with weighted-λ-regularization)，通过对比基于ALS-WR(alternating-least-squares with weighted-λ-regularization)和SVD(singular value decomposition)的推荐系统，该算法的推荐准确率显著提高. Hammou等^[11]提出一种基于Spark的专门处理大规模数据的推荐算法APRA(approximate parallel recommendation algorithm)，通过使用Spark基于内存的操作，大大提高了大数据环境下的推荐性能.

粒子群优化(PSO，particle swarm optimization)算法是由Kennedy和Eberhart^[12]提出的一种基于群体智能的随机优化方法. RLPSO(reverse-learning and local-learning PSO)算法是一种改进的PSO算法，该算法通过粒子种群历史位置的差分结果进行局部搜索，同时引入反向学习子粒子种群^[13]避免出现早熟收敛.

为了解决协同过滤推荐算法针对大数据带来的计算性能问题以及结合Spark在内存计算和迭代计算上的优势，提出了一种基于PSO算法的并行化协同过滤推荐算法.该算法根据与目标用户具有相似兴趣的用户群比其他用户具有更高的参考价值，提出基于KM(K-means)聚类算法对评分数据进行聚类分析，从而将兴趣相似的用户聚成一类，通过类内的相似用户运用推荐算法预测目标用户对其他未评价物品的评分，进而将其推荐给目标用户.本文算法针对KM聚类算法初始化因子的不确定性，通过RLPSO算法对其初始化因子进行优化.

笔者的主要研究工作和贡献点如下：①针对协同过滤推荐算法面对大数据存在的计算性能问题，提出了基于Spark的并行化协同过滤推荐算法；②针对协同过滤推荐算法中，与用户兴趣相似的用户具有更高的参考价值，提出了对用户进行聚类分析；③针对KM聚类算法中初始化因子的不确定性，提出了基于RLPSO算法对初始化因子进行优化.

1 基于Spark的RLPSO_KM_CF算法相关工作及算法实现

下面对所提出的并行化协同过滤推荐算法进行详细描述.

1.1 基于RLPSO的RLPSO_KM算法 1.1.1 RLPSO算法^[13]

1) 粒子速度和位置更新公式为

$ v_{ij}^{t + 1} = \omega v_{ij}^t + {c_1}{r_1}\left( {p_{ij}^t - x_{ij}^i} \right) + {c_2}{r_2}\left( {p_{kj}^t - x_{ij}^i} \right) $

(1)

$ x_{ij}^{t + 1} = x_{ij}^t + v_{ij}^t $

(2)

其中：v_ij^t、x_ij^t、P_ij^t表示第i个粒子在第j维在第t代的速度、位置和最优位置，c₁和c₂表示粒子个体向个体和种群历史最优解学习能力的大小，r₁和r₂为[0, 1]的随机数，ω为惯性权重：

$ {\omega ^t} = {\omega _{\max }} - \left( {{\omega _{\max }} - {\omega _{\min }}} \right)t/{t_{\max }} $

(3)

其中：t、t_max、ω_max、ω_min表示当前迭代次数、最大迭代次数、最大迭代次数时的惯性权重和初代惯性权重.

2) 初始化最差粒子种群W.算法根据粒子间的排异半径判定该粒子是否加入最差粒子种群.

3) 局部搜索.定义局部搜索的公式为

$ P_{g1}^\prime = {P_1} + r{d_t}\left( {{P_{g1}} - {P_{g2}}} \right) $

(4)

其中：r为[-1, +1]的随机数，服从均匀分布；P_g1和P_g2分别为粒子群的最优和次优位置；d_t为第t次局域缩放因子，其取值为

$ {d_{t + 1}} = {d_t}\left( {1 - t/{t_{\max }}} \right) $

(5)

4) 粒子反向学习.当算法进入停滞状态时，根据初始化最差粒子种群并结合粒子种群中的一部分粒子进行反向学习.同时定义第i个粒子进行反向学习的速度公式如下：

$ v_{ij}^{t + 1} = \omega v_{ij}^t + {c_3}{r_3}\left( {x_{ij}^t - w_{ij}^t} \right) + {c_4}{r_3}\left( {x_{ij}^t - w_{kj}^0} \right) $

(6)

其中：w_ij^t(1≤i≤n)为第i个粒子t次迭代历史最差位置W_i^t的第j维取值；c₃和c₄为反向学习因子，r₃为[0, 1]的随机数；w_kj⁰(1≤i≤m)为粒子群中最差粒子个体位置W_k⁰第j维所取的值.

1.1.2 正则化飞行时间

为了避免粒子在最优解周围出现振荡现象，加快粒子群的收敛时间，加入了飞行时间因子，从而粒子的位置更新公式调整为

$ x_{ij}^{t + 1} = x_{ij}^t + {H_0}\left( {1 - t/{t_{\max }}} \right)v_{ij}^{t + 1} $

(7)

其中H₀为飞行时间因子.

1.1.3 适应度函数

定义粒子的适应度函数为

$ f(x) = \sum\limits_{j = 1}^k {\sum\limits_{{s_i} \in {C_j}} {\left\| {{S_i} - {Z_j}} \right\|} } $

(8)

其中：S_i为聚类C_j的一个数据项，Z_j为聚类C_j的中心. f(x)越小，聚类效果越好.粒子i在第t+1次迭代时，若f(x_i(t+1))<f(P_i(t))，则P_i(t+1)=f(x_i(t+1))；否则P_i(t+1)=P_i(t).同样，若min(f(P_i(t+1)))<f(P′_g1(t))，则P′_g1(t+1)=min(f(P_i(t+1)))；否则P′_g1(t+1)=P′_g1(t).

1.1.4 适应度方差

通过适应度方差表征粒子群的收敛度.适应度方差定义为

$ \rho = 1/N\sum\limits_{i = 1}^N {{{\left[ {f\left( {{x_i}} \right) - {f_{{\rm{avg}}}}} \right]}^2}} $

(9)

其中:N为粒子群规模，f(x_i)为粒子i的适应度值，f_avg为所有粒子的适应度均值. ρ越小，整个粒子群越收敛.

1.1.5 算法描述

输入：实验数据集D，聚类数目k，粒子群规模N和反向学习粒子种群规模n，粒子群学习因子c₁、c₂和反向学习因子c₃、c₄，粒子群最大迭代次数t_max和反向学习迭代次数L_times，最大惯性权重ω_max和最小惯性权重ω_min，扰动系数d₀，飞行时间因子H₀和粒子最大飞行速度v_max.

输出：优化后的k个聚类中心.

Begin

1 初始化粒子群.从数据集D中随机选择k个数据项作为粒子位置和速度每一维值的初始值，将粒子位置的个体最优位置设为X_i⁰，循环执行这一过程N次.

2 初始化粒子群最优位置和次优位置.根据式(8)计算粒子群中每个粒子的适应度值，并依次选择适应度值最小和次小粒子的位置作为粒子群体最优和次优位置的初始值.

3 初始化最差粒子种群W.

4 迭代搜索粒子.

$ {\rm{while}}\left( {t < {t_{{\rm{ max }}}}||\rho < {{10}^{ - 6}}} \right) $

1) 根据式(3)，调整惯性权重；

2) 根据式(7)和式(1)分别对粒子的位置和粒子的速度进行更新；

3) 根据式(8)依次计算粒子群中每个粒子的适应度值；

4) 更新粒子的个体最优值；

5) 更新粒子群次优和最优位置；

6) 根据式(4)计算粒子群历史位置的差分结果并进行局部搜索；

7) 根据式(5)调整缩放因子权重；

8) If满足反向学习条件(算法局部收敛或者达到设定的阈值收敛次数)，调整粒子速度v_max；根据式(6)和式(7)分别更新反向学习粒子的速度和位置；根据式(7)和式(1)更新除反向学习的剩余粒子的位置和速度；

End If

9) 根据式(9)计算适应度方差ρ；

10) if (适应度方差>阈值)

break；

11) t ++;

End while

5 输出粒子群最优解.

6 运行KM聚类算法并输出优化后的聚类中心.

End

1.2 基于RLPSO_KM的RLPSO_KM_CF算法

根据与目标用户相似性更高的用户比其他用户更具有价值的参考作用，采用RLPSO_KM算法对用户信息进行聚类，然后在每个聚类内部通过运用传统基于用户的协同过滤推荐算法对目标用户进行有效推荐.同时，给新加入的目标用户推荐流行度最高的项目.项目流行度公式为

$ {M_i} = \frac{{\left| {{U_i}} \right|}}{{\sqrt {\sum\limits_{i \in I} {{{\left| {{U_i}} \right|}^2}} } }} $

(10)

其中：M_i为项目i流行度，定义项目流行度与浏览过该项目的用户量成正比, U表示用户集合{u₁, u₂, u₃, …, u_i}，I表示项目集合{i₁, i₂, i₃, …, i_n}；

RLPSO_KM_CF算法描述如下：

输入：聚类因子k和聚类迭代次数m，用户-项目评分信息和推荐项目个数N.

输出：对目标用户的Top-N推荐.

Begin

1 If(目标用户是否是新用户)

1) 根据式(10)计算项目的流行度形成集合W；

2) 对集合W进行降序排序形成集合W_new；

3) 从集合W_new中选取前N个流行度最高的项目，从而形成集合Target；

4) 将集合Target推荐给目标用户；

End If

2根据RLPSO_KM算法计算聚类中心.

3根据式(11)用户相似度公式计算目标用户所属聚类.

$ \begin{array}{l} \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\mathop{\rm sim}\nolimits} \left( {{u_i}, {u_j}} \right) = \\ \frac{{\sum\limits_{{i_c} \in {I_{i, j}}} {\left( {{R_{{u_i}, {i_c}}} - {{\bar R}_{{u_i}}}} \right)} \left( {{R_{{u_j}{i_c}}} - {{\bar R}_{{u_i}}}} \right)}}{{\sqrt {\sum\limits_{{i_c} \in {I_{i, j}}} {{{\left( {{R_{{u_i}, {i_c}}} - {{\bar R}_{{u_i}}}} \right)}^2}} } \sqrt {\sum\limits_{{i_c} \in {l_{i, j}}} {{{\left( {{R_{{u_j}, {i_c}}} - {{\bar R}_{{u_i}}}} \right)}^2}} } }} \end{array} $

(11)

其中：R_ui和R_uj分别为用户u_i和u_j对所有项目的平均评分；R_ui, i_c和R_uj, i_c分别为用户u_i和u_j对项目i_c的评分.用户对项目的预测评分公式为

$ \beta \left( {{u_i}, {i_i}} \right) = {{\bar R}_{{u_i}}} + \frac{{\sum\limits_{{u_j} \in {N_{{u_i}}}} {{\mathop{\rm sim}\nolimits} } \left( {{u_i}, {u_j}} \right)\left( {{R_{{u_i}, {i_i}}} - {{\bar r}_{{u_j}}}} \right)}}{{\sum\limits_{{u_j} \in {N_{{u_i}}}} {{\mathop{\rm sim}\nolimits} } \left( {{u_i}, {u_j}} \right)}} $

(12)

其中N_ui为用户u_i的邻域集合.

4 聚类中运用协同过滤推荐算法为目标用户进行推荐.

5 输出Top-N推荐列表.

End

1.3 基于Spark的RLPSO_KM_CF算法

RLPSO算法中，每个粒子的迭代过程相互独立且每个粒子迭代相同任务，加大了处理的任务粒度，而随着任务粒度增加，计算时间也相对越长. KM聚类算法中，由于每个数据对象彼此独立，计算每个数据对象所属的聚类，随着聚类迭代次数增加，需要不断更新聚类中心.针对以上情况，提出基于Spark的RLPSO_KM_CF算法，从而有效地支持迭代运算，提高算法效率. RLPSO_KM_CF算法的具体程序流程如图 1所示.

RLPSO_KM_CF算法分为3个阶段.

第1阶段.针对RLPSO算法进行并行化设计与实现.通过将粒子群映射到RDD数据集，从而将构造粒子群最优解的过程进行并行化，将每个粒子群初始化粒子群信息、构造解、局部搜索和反向学习的过程独立成为一个并行单元.在Spark分布式处理平台上，并行处理RDD1至RDDn个粒子群信息，从而求解每个粒子群的最优解，最终更新整体粒子群最优解.

第2阶段.在第1阶段输出粒子群最优解的基础上，将粒子群最优解进行有效分解，从而作为RLPSO_KM算法的初始化聚类中心.在Spark上，利用RDD将数据样本分布至集群中的n个计算节点，并且将聚类中心借助SparkContext的broadcast()函数使其在各个计算节点间实现共享.与此同时，针对每个数据分片，计算其与最近聚类中心的欧氏距离，并根据每个聚类中心计算属于该聚类的数据之和，对每个节点的累加数据和进行合并求和，判断sum和是否小于阈值，通过使用map()和reduce()函数完成更新聚类中心的操作，直到算法收敛或完成迭代从而输出聚类中心和聚类结果.

第3阶段.在第2阶段基础上，首先对目标用户进行判断，如果是新加入用户，根据式(10)计算项目流行度最高的N个项目，从而推荐给目标用户；否则，通过map()函数对评分信息进行排序同时执行持久化操作.然后根据聚类中心计算用户所属聚类，使用groupByKey()函数获取目标用户评分的项目信息RDD1；根据式(11)计算聚类内用户之间的相似度，从而通过filter()函数过滤与目标用户相似度最高的用户信息RDD2；使用groupByKey()函数获取目标用户邻域的用户评价过的项目信息RDD3；通过将RDD1与RDD3进行distinct()操作，返回目标用户未评价过的项目信息RDD4.最后根据式(12)计算目标用户对RDD4中项目信息的预测评分，将评分最高的N个项目推荐给目标用户.

2 实验 2.1 实验数据集

实验环境为centos7.0设备系统服务器，部署了8台设备，其中包含7个工作节点和1个主节点，Spark版本为2.0，Hadoop版本为2.7.采用明尼苏达大学Movie Lens作为实验数据，如表 1所示.

2.2 评估标准

运用召回率α，准确率δ，召回率α与准确率δ的调和平均值(F-Measure)F，平均绝对误差η来评估实验结果.定义为

$ \alpha = \frac{{\sum\limits_{i \in U} | N(i) \cap T(i)|}}{{\sum\limits_{i \in U} | T(i)|}} $

(13)

$ \delta = \frac{{\sum\limits_{i \in U} | N(i) \cap T(i)|}}{{\sum\limits_{i \in U} | N(i)|}} $

(14)

$ F = \frac{{2\delta \alpha }}{{\delta + \alpha }} $

(15)

其中：集合N(i)为推荐给目标用户的N个项目；T(i)为目标用户u_i喜欢的项目集合.平均绝对误差可由下式计算：

$ \eta = \frac{{\sum\limits_{i = 1}^N {\left| {{p_i} - {q_i}} \right|} }}{N} $

(16)

其中：{q₁, q₂, …, q_N}为实际评分集合；{p₁, p₂, …, p_N}为预测项目评分集合.平均绝对误差越小，推荐质量越高.

2.3 比较算法及参数设定

选取了传统User-CF推荐算法、改进的Top-N聚类协同过滤推荐算法KCF(K-means clustering collaborative filtering recommendation algorithm)以及所提出的RLPSO_KM_CF算法进行对比实验.实验中，为了能够使模型计算的复杂度降低，RLPSO算法设定的参数采用文献[13]提出的参数设置.同时，假定Top-N推荐值为10，算法参数设置如表 2所示.

2.4 实验结果分析

为了对RLPSO_KM_CF算法的推荐效率和推荐准确度进行分析，采取了以下几组实验：1)对比RLPSO_KM_CF算法在不同聚类下的平均绝对误差值、召回率及F-Measure值，进而判断算法所选择的聚类参数值K；2)对比RLPSO_KM_CF算法与传统基于用户的协同过滤推荐算法User-CF、基于聚类的协同过滤推荐算法KCF，进而判定本文算法的有效性；3)对比RLPSO_KM_CF算法与其他改进推荐算法的平均绝对误差值，验证RLPSO_KM_CF算法的推荐准确度；4)对比基于Spark的RLPSO_KM_CF算法与基于Hadoop的User-CF与Item-CF算法，验证算法的推荐效率.利用RLPSO_KM算法分别将用户划分成1~8个簇，同时，运用协同过滤推荐算法于每次迭代的每个簇类中，并且计算平均召回率和平均绝对误差值. 表 3为RLPSO_KM_CF算法在聚类数分别为1~8时得到的推荐结果的召回率.其中，聚类数为1时，RLPSO_KM_CF算法与传统的User-CF算法效果相当.

图 2所示为Movie Lens100K数据集下绘制的平均绝对误差曲线.可以明显看出，在实验开始阶段随着聚类数增加，RLPSO_KM_CF算法的平均绝对误差值下降速度最快，当聚类数为4时，RLPSO_KM_CF算法的平均绝对误差值最小，此时推荐结果最好.随着聚类数增加，平均绝对误差值也逐渐呈现先递减后递增的趋势，说明目标用户邻域集相对较少，推荐精度降低.

图 3所示为RLPSO_KM_CF算法在不同迭代步数下推荐结果的召回率.当迭代步数在25左右时，各种情况下推荐结果的召回率基本都取得了最大值.当聚类因子k为4并且迭代步数为15左右时，算法明显收敛，此时召回率达到了0.117 136.相对于传统的协同过滤添加算法，RLPSO_KM_CF算法提升了3.2%，同时比KCF算法提高了1.1%.随着聚类因子的增加，与目标用户进行相似度计算的用户数会随之减少.因此，算法的推荐准确度下降，推荐结果变差.

从图 4中的F-Measure值来看，假定不考虑随机因素的影响，RLPSO_KM_CF算法和KCF算法优于传统的User-CF算法，而且RLPSO_KM_CF算法更甚于KCF算法.同时也可以明显看到，随着聚类数的增加，KCF算法和RLPSO_KM_CF算法的F-Measure值都逐渐呈现递减趋势.从总体上来说，本文算法提高了推荐的准确率.

统计了RLPSO_KM_CF算法与NALS-WR、PRABS、APRA算法在数据集为Movie Lens10M时，不同比例训练集与测试集下的平均绝对误差值.由图 5可知，随着训练集数据不断增加，几种算法的平均绝对误差值都呈现下降的趋势，相比于NALS-WR算法，RLPSO_KM_CF算法在推荐准确度上有显著提高.对于PRABS算法，RLPSO_KM_CF算法在训练集与测试集比例为8:2时，平均绝对误差值降低了1.07%，相比于ARPA算法，RLPSO_KM_CF算法的优势不太明显.

通过采用不同大小的实验数据集进行实验，在Spark环境下(4个节点)并行化执行RLPSO_KM_CF算法.从图 6可以看出，数据集为100 K和1 M时，并行算法优势并不明显.但是随着数据集规模不断增大，Spark并行化优势逐渐变得明显，这充分体现了Spark基于内存计算模式在时间开销上的巨大优势.同时，对比了本文算法与Hadoop-ItemCF^[8]和Hadoop-UserCF^[9]算法的加速比，在数据集为10 M时，加速比达到了其他算法的10倍.这是由于Spark是基于内存的分布式计算框架，在处理初始阶段，通信节点间的通信使得时间消耗增加，而随着数据集的增加，加速比则逐渐提高，这充分体现了Spark基于内存的计算的优势.

3 结束语

传统协同过滤推荐算法用户邻域的选择参考了所有用户的评分信息.然而当为一个目标用户进行推荐时，与其相似性更高的用户显然比其他用户具有更有价值的参考作用.笔者提出在Spark上并行化实现了基于粒子群优化算法的协同过滤推荐算法.通过RLPSO算法寻找粒子群最优解，输出优化后的聚类中心；运用RLPSO_KM算法对用户信息进行聚类，从而将传统协同过滤推荐算法与RLPSO_KM聚类结合，对目标用户进行有效推荐.笔者只选取了KM聚类算法进行研究，在今后的研究中，面对冷启动问题和评分矩阵稀疏性问题，可以考虑选取一些适合稀疏性矩阵的聚类算法与传统的协同过滤推荐算法相结合进行研究.