0 概述

在互联网时代, 海量规模的数据信息虽然能够满足用户的多样化需求, 却难以让用户在搜索时直接获取目标信息, 信息处理技术的性能具有很大的提升空间。国际数据集团(IDC)2012年的报告显示, 预计2020年的全球数据总量将达到35.2 ZB, 是2011年的22倍^[1]。从信息匮乏到信息过载^[2-3], 数据信息量产生巨大改变, 但用户对信息的使用效率并未大幅提高。在这样的大数据背景下, 推荐系统^[4-5]应运而生, 其根据用户潜在需求和兴趣来提供个性化的推荐服务。文献[6]中的邮件过滤系统被认为是互联网时代较早提出并被广泛应用的协同过滤系统。协同过滤推荐系统^[7-8]可以尽可能地满足用户的需求, 产生与用户喜好相关且数量有限的物品推荐列表。Amazon、NetFlix、淘宝等众多国内外知名网站中的推荐服务皆依赖协同过滤推荐系统, 其中, 用户和物品种类的数量相当庞大, 这对协同过滤推荐系统的准确性、执行效率和排名精度都有非常高的要求。

协同过滤推荐算法^[9]是一种典型的大数据挖掘算法, 其基于用户或物品的相似性来进行推荐。尽管协同过滤推荐算法的应用使推荐系统获得了用户的认可, 但稀疏性高、执行效率与排名精度低等问题依然存在。为此, 研究人员提出一类高效的基于模型的协同过滤算法, 其中, 基于交替最小二乘(Alternating Least Squares, ALS)^[10]的矩阵分解(Matrix Factorization, MF)模型^[11]可实现并行计算, 该特性使其在速度方面具有明显优势, 但是, 该模型存在数据加载时间长、矩阵分解与迭代收敛慢等问题。国内外学者先后围绕上述问题进行了优化, 其中, 快速矩阵分解模型IALS^[12]、LS-WR、NALS-WR^[13]、ALS++^[14]等改进优化方法的侧重点在于缩短数据加载与矩阵分解的时间以及改变ALS预测模型等, 但对于ALS迭代收敛慢的问题研究较少。

本文提出一种在ALS中融入非线性共轭梯度(Nonlinear Conjugate Gradient, NCG)的算法ALS-NCG^[15], 以加速ALS算法的收敛, 提高执行效率和排名精度。

1 基于矩阵分解的ALS算法

MF算法具有伸缩性好、灵活性高的特点^[16]。在Netflix Prize算法比赛中, 文献[17]提出了基于ALS的协同过滤算法, 其能很好地解决矩阵稀疏性问题。

1.1 ALS算法

ALS算法利用迭代求解一系列最小二乘的回归问题。对于用户-项目评分矩阵R, 找到一个低秩矩阵R′来逼近原始数据评分矩阵R, 完整过程如下:

$ \boldsymbol{R} \approx \boldsymbol{R}^{\prime}=\boldsymbol{U} \boldsymbol{V}^{\mathrm{T}} $

(1)

其中, $ \boldsymbol{U} \in \mathbb{C}^{m \times d}, \boldsymbol{V} \in \mathbb{C}^{n \times d}, d$表示特征值个数, r≈min(m, n), r表示矩阵R的秩。

损失函数定义为:

$ L(\boldsymbol{U}, \boldsymbol{V})=\sum\limits_{i, j \in r}\left(\boldsymbol{R}_{i j}-\boldsymbol{X}_{i j}\right)^{2}=\sum\limits_{i, j \in r}\left(\boldsymbol{R}_{i j}-\boldsymbol{U}_{i}, \boldsymbol{V}_{j .}^{\mathrm{T}}\right)^{2} $

(2)

其中, L表示损失函数。

为防止过拟合, 对式(2)进行正则化处理, 得到优化式(3):

$ \begin{aligned} L(\boldsymbol{R}, \boldsymbol{U}, \boldsymbol{V})=& \sum\limits_{i, j \in r}\left(\boldsymbol{R}_{i j}-\boldsymbol{U}_{i.} \boldsymbol{V}_{i.}^{\mathrm{T}}\right)^{2}+\\ & \lambda\left(\left\|\boldsymbol{U}_{i.}\right\|_{2}^{2}+\left\|\boldsymbol{V}_{j.}\right\|_{2}^{2}\right) \end{aligned} $

(3)

其中, λ表示正则化参数。

固定V后对U_i求导, 令$ \frac{\partial L(\boldsymbol{U}, \boldsymbol{V})}{\partial\left(\boldsymbol{U}_{i.}\right)}=0$, 得到U_i.的值:

$ \boldsymbol{U}_{i.}=\boldsymbol{R}_{i.} \boldsymbol{V}_{u i}\left(\boldsymbol{V}_{u i}^{\mathrm{T}} \boldsymbol{V}_{u i}+\lambda n_{u i} I\right)^{-1}, i \in[1, m] $

(4)

其中, R_i.表示用户i对项目的评分矩阵, V_ui表示用户i所评价过的项目涉及的特征向量所形成的特征矩阵, n_ui表示用户i所评价的项目数量。同理, 固定U后对V_i求导, 然后根据求导结果解出V_j.:

$ \boldsymbol{V}_{j .}=\boldsymbol{R}_{. j}^{\mathrm{T}} \boldsymbol{U}_{m j}\left(\boldsymbol{U}_{m j}^{\mathrm{T}} \boldsymbol{U}_{m j}+\lambda n_{m j} I\right)^{-1}, j \in[1, n] $

(5)

$ \begin{aligned} f(\boldsymbol{U}, \boldsymbol{M})=& \sum\limits_{(i, j) \in I}\left(\boldsymbol{r}_{u i}-\boldsymbol{u}_{i}^{\mathrm{T}} m_{j}\right)^{2}+\\ & \lambda\left(\sum\limits_{i} n_{u i}\left\|u_{i}\right\|^{2}+\sum\limits_{j} n_{m j}\left\|m_{u}\right\|^{2}\right) \end{aligned} $

(6)

其中, R_.j表示评分过项目j的用户的评分向量, U_mj表示评分过项目j的用户的特征向量所组成的特征矩阵, n_mj表示评分项目j的用户数量。

可利用式(6)中的$ \lambda\left(\sum\limits_{i} n_{u i}\left\|u_{i}\right\|^{2}+\sum\limits_{j} n_{m j}\left\|m_{u}\right\|^{2}\right)$防止过拟合问题。根据以上过程可以发现, U、M的每列都是单独计算得到的, 适合并行计算, 利用上述过程多次迭代更新U、M, 直到完成所有迭代或达到收敛状态。

1.2 ALS算法存在的问题

基于ALS矩阵分解的协同过滤推荐算法通过对ALS算法的迭代, 在Spark集群环境下训练出最佳模型并获取最优参数, 但是ALS算法自身存在的一些不足无法通过模型训练、参数优化来改进。比如成本消耗问题, 有数据表明, 推荐系统利用基于Spark的ALS算法进行实时推荐, 输入数据114 GB, 训练时间和预测时间总和超过50 min, 是实际要求时间的3倍多, 超出的时间将导致巨大的资源消耗, 且推荐结果的准确性也较低。

针对ALS算法存在的问题, 本文将加速收敛过程以优化ALS模型, 并在优化f(U, M)的过程中提高推送结果的准确性。

2 基于NCG的ALS算法 2.1 NCG算法

NCG算法是线性系统CG的扩展, 其不仅具有良好的收敛性, 而且数值表现较好^[18]。本文选择的非线性共轭梯度法是PRP(Polak, Ribiere and Polyar)^[19]方法, 该方法克服了遇到小步长时收敛缓慢的缺点, 同时也有效地避免了连续产生小步长, 在数值表现上优于其他非线性共轭梯度法, 因此, 常被应于处理最优化问题。利用NCG算法来处理min_{U, M}f(U, M)问题, f(U, M)等价于$\min _{\boldsymbol{x} \in \mathbb{R}^{n}} f(\boldsymbol{x}) $中的f(x), 其中, 规定:

$ \boldsymbol{x}^{\mathrm{T}}=\left[\boldsymbol{U}_{1}^{\mathrm{T}}, \boldsymbol{U}_{2}^{\mathrm{T}}, \cdots, \boldsymbol{U}_{n u}^{\mathrm{T}}, \boldsymbol{M}_{1}^{\mathrm{T}}, \boldsymbol{M}_{2}^{\mathrm{T}}, \cdots, \boldsymbol{M}_{n m}^{\mathrm{T}}\right] $

(7)

NCG算法用递推关系x_k+1=x_k+α_kp_k从初始猜测x₀中生成迭代序列x_i, i≥1, 步长参数α_k>0是沿着搜索方向p_k的线搜索而确定的, 每次迭代包括计算线搜索方向p_k和步长因子α_k两部分, 搜索方向p_k要求为下降的方向, 沿着该方向搜索找到比x_k更好的点。求解min_{U, M}L_λ(R, U, M)的共轭梯度算法是根据求解线性方程组问题推广而来, 搜索方向为负梯度与上一次搜索方向的线性组合。p_k求解如下:

$ \left\{\begin{array}{l} {\boldsymbol{p}_{k+1}=-\boldsymbol{g}_{k+1}+\beta_{k+1} \boldsymbol{p}_{k}, k>0} \\ {\boldsymbol{p}_{0}=-\boldsymbol{g}_{0}, k=0} \end{array}\right. $

(8)

其中, β_k+1表示更新参数, 本文在更新β_k+1时使用PRP共轭梯度法^[20], 如式(9)所示。

$ \beta_{k+1}=\frac{\boldsymbol{g}_{k+1}^{\mathrm{T}}\left(\boldsymbol{g}_{k+1}-\boldsymbol{g}_{k}\right)}{\boldsymbol{g}_{k}^{\mathrm{T}} \boldsymbol{g}_{k}} $

(9)

NCG算法伪代码描述如下:

算法1  NCG算法

输入  x₀

输出  x_k

g₀←▽f(x_k);

p₀←－g₀;

k←0;

while g_k≠0 do

Compute α_k;

x_k+1←x_k+α_kp_k;

g_k←▽f(x_k+1);

Compute β_k+1;

p_k+1←－g_k+1+β_k+1p_k;

k←k+1;

end

2.2 ALS-NCG算法设计

较好的收敛特性和数值表现使得NCG算法在处理最优解问题时具有良好性能, 但是利用NCG算法单独求解min L(R, U, V)时效果并不好, 因此, NCG算法不能代替ALS算法, 也可以认为ALS算法是NCG算法的非线性预因子, 将两者融合后可以达到加速收敛的效果。首先对NCG算法β_k+1和g_k的预处理进行修改, x表示由x_k的ALS算法一次迭代生成的迭代, x=H(x_k), H表示ALS的一次迭代。通过定义由ALS生成的预处理梯度方向, 将该迭代整合到NCG算法中。将式(10)中g_k替换成g_k, 并将更新参数β_k+1重新定义为式(11)β_k+1的形式:

$ \boldsymbol{\bar{g}}_{k}=\boldsymbol{x}_{k}-\boldsymbol{\bar{x}}_{k}=\boldsymbol{x}_{k}-H\left(\boldsymbol{x}_{k}\right) $

(10)

$ \bar{\beta}_{k+1}=\frac{\boldsymbol{g}_{k+1}^{-\mathrm{T}}\left(\boldsymbol{g}_{k+1}-\boldsymbol{g}_{k}\right)}{\boldsymbol{g}_{k}^{-\mathrm{T}} \boldsymbol{g}_{k}} $

(11)

式(11)与式(9)类似, 但是并不代表g_k可以取代任何一个g_k, 经过对替代结果的分析, 给出β_k+1不同形式的概述。本文后续将式(11)应用于对比实验。

ALS-NCG算法伪代码描述如下:

算法2  ALS-NCG算法

输入  x₀

输出  x_k

g₀←x₀－H(x₀);

p₀←－g₀;

k←0;

while g_k≠0 do

Compute α_k;

x_k+1←x_k+α_kp_k;

g_k+1←x_k+1－H(x_k+1);

Compute β_k+1;

p_k+1←－g_k+1+β_k+1p_k;

k←k+1;

end

算法2是改进的ALS算法, 将初始值x₀作为输入, 利用递推关系求解x_k并输出。算法3是步长因子α_k的计算过程, 将算法2求解的x_k作为算法3的输入, 在求解过程中, 需要注意线搜索类型的选择。线搜索类型通常可以分为精确线搜索和非精确线搜索, 参数α_k对线搜索类型选取至关重要，α_k是从x_k在沿着p_k的方向寻找的一个最好的点，将其作为下一个迭代点，此时最好的点就是函数f(x_k+α_kp_k)在该方向上数值最小的点，但是此时属于精确线搜索状态, 其计算量太大, 实际应用时具有较高难度, 因此, 本文算法求解步长因子时选择非精确线搜索类型。c和τ的取值范围为[0, 1], 本文算法3的参数选择最佳经验结果为:c=0.9, τ=0.5。算法3具体描述如下:

算法3  步长因子α_k计算算法

输入  x_k, p_k, c=0.9, τ=0.5

输出  α_k

α_k←10;

while f(x_k+α_kp_k)－f(x_k)>α_k×c×g_k^T×p_k do

α_k←τα_k;

end

在求解线搜索方向p_k时, 需要ALS算法的一次迭代, 算法4是求解ALS一次迭代的算法H(x_k)的伪代码, 其中, 规定x=H(x_k)。将算法2输出结果x_k作为算法4的输入, 首先根据x_k求解得到U和M, 然后求解出u_i和m_j, 最后根据u_i和m_j得到目标值x_k(H(x_k))。搜索方向p_k要求为下降的方向, 标准为p_k^T×▽f(x_k) < 0, 沿着p_k方向找到比x_k更优的点, 这样即可以确定p_k。

算法4  ALS一次迭代算法H(x_k)

输入  x_k

输出  x_k

solve U and M from x_k;

for i=1, 2, …, n_u do

u_i←A_i^－1v_j;

End

for j=1, 2, …, n_m do

m_j←A_j^－1v_j;

End

solve x_k by the combination of the respective u_i and m_j

2.3 ALS-NCG算法的Spark并行实现

将ALS-NCG算法的数据结构在Spark弹性分布式数据集(Resilient Distributed Dataset, RDD)上分区, 每个分区就是一个数据集片段, 并且一个RDD的不同分区可以被保存到集群中不同的节点上, 从而在集群中的不同节点上进行并行计算。本文将因子矩阵U和M存储为单精度列块矩阵, 分别表示用户子集的因子矢量和电影子集的因子矢量。规定单精度列块的每一块作为RDD的一个分区单元, R和R^T的行块均以压缩的稀疏矩阵的方式进行存储。图 1所示为M存储的分配方式, 将M区块分割成若干块, 编号为M₁, M₂, …, M_nb, 共分解成nb块。

U的存储方式与M相同。U和R的RDD分区相同, 存储U的节点也可以存储R。在更新U用户块时, 需要本地评分在R中可用, 而本地U块中用户评分电影的M因子矢量必须混洗。由于电影因子来自不同的节点, 可通过建立路由表存储所需的本地评分数据, 避免重复发送信息。缓冲区一旦构造, 就会被混合集中到R的分区, 此时电影因子和本地评分数据可用来计算新的U子块。

路由表构建在ALS算法的While循环之前, 具体布局如图 2所示, 每次迭代无需重新计算, 同理, 更新M与U类似。矢量x、g、g以及P均被存储在2个单独的RDD中, 使与其相关的分量存储在同一个RDD, 且分割方式与U类似。路由表策略可以确保所有的矢量块在矢量运算中按照成分对齐, 从而实现了各数据的RDD存储以及RDD的分配运行。

3 实验结果与分析 3.1 实验数据集

本文采用MovieLens上10 M大小的数据集进行实验, 该数据集包括71 567个用户、10 681部电影和10 000 054条评分, 为更好地比较算法性能, ALS与ALS-NCG均使用相同的数据集。在实际应用中, 并非所有数据都满足建立实验数据集的要求, 因此, 本文找到原始完整数据集中按照每个用户评分数目进行排序的中位数, 用c表示, 舍弃对电影评分数目与中位数值相差较大的用户, 保留评分数目与中位数相近的用户, 将这些数据组成实验数据集。

3.2 Spark运行环境

Spark是一种类Hadoop MapReduce的基于内存计算的大数据并行计算框架^[21], Spark较Hadoop的优势之一是提出了RDD。RDD的高容错性表现在2个方面:1)若其中一个RDD分片丢失, 则Spark可以根据日志信息重构RDD; 2)在内存中缓存RDD后, 只需从内存中读取数据即可计算, 这样节省了大量的磁盘存取开销, 适合迭代计算的矩阵分解算法。因此, 本文搭建Spark集群作为实验平台。

本文将Spark计算集群搭建在Hadoop分布式平台上, 以Hadoop中的HDFS作为集群的分布式文件存储系统, 选择Spark原生语言Scala^[22]作为编程语言, 该语言比较简洁完善, 是Spark领域较为常用的程序设计语言。本文实验的集群环境配置如表 1所示。

3.3 ALS-NCG算法与ALS算法时间性能比较

在本次实验中, 算法循环的终止条件是期望的收敛值$ \frac{\left\|g_{k}\right\|}{N}$小于等于给定值, N=n_f×(n_u+n_m)。

实验1进行ALS-NCG算法与ALS算法的时间性能比较, 采用若干不同规格的数据集在Spark平台上反复实验, 以验证ALS-NCG算法是否能达到预期目标。分别统计ALS-NCG与ALS 2种算法达到期望收敛值$ \frac{\left\|g_{k}\right\|}{N} \leqslant 10^{-6}$和$\frac{\left\|g_{k}\right\|}{N} \leqslant 10^{-3} $时各自所需的时间, 用n_u表示用户数量, n_m表示电影数量, 时间对比结果如表 2、表 3所示。其中, 加速倍数表示ALS与ALS-NCG的时间比值。

从表 2、表 3可以看出, ALS-NCG达到目标收敛值较快, 相对ALS的加速效果明显。

图 3表示不同规模的评分矩阵下2种算法在迭代次数相同时所用时间比值的变化趋势, 可以看出, ALS-NCG在时间消耗上比ALS小很多, 随着矩阵规模的增大, ALS-NCG的加速效果更明显, 性能更加优越。在不同收敛值时, ALS与ALS-NCG的时间性能比值变化趋势近似一致, 可见, 将改进的组合算法应用于大数据环境中, 即使收敛值扩大到10^-3, 也可以达到同样的加速效果。

3.4 ALS-NCG算法与ALS算法排名精度比较

由于实验条件限制, 本文仅对排名前20的电影进行准确度实验, 使用电影排名矢量转化所需的成对互换次数作为度量。本次实验借助Kendall-Tau距离来计算向量之间的差异, 将距离归一化范围限制在[0, 1]之间, 再求取所有用户的距离平均值。

若p₁=[6, 3, 1, 4, 2, 5]、p₂=[3, 4, 5, 2, 6, 1]是用户u对2个不同电影的排名, 设置t=4表示对排名前4的电影进行排名精度计算。p₁中排名第1的电影6在p₂中排名第5, 若要将p₂中电影6排在第1位, 需要交换4次位置, 此时产生第1次迭代排名顺序p₂₁=[6, 3, 4, 5, 2, 1], p₁中排名第2位的是电影3, 在p₂₁中电影3同样排在第2位, 此时不需要转换, 即p₂₂=p₂₁, 同理可得p₂₃=[6, 3, 1, 4, 5, 2], 转换3次, p₂₄=p₂₃, 转换0次。匹配p₂到p₁所需成对互换的距离总数s_i=4+0+3+0=7。若匹配时相同位置的电影相同, 则不需要转换, 否则将会发生转换, 若匹配与被匹配的序列相反, 则会出现最大交换次数, 在第1次匹配发生n_m－1次交换, 第2次匹配发生n_m－2次交换, 以此类推, 最大交换次数可表示为:

$ \begin{aligned} s_{\max }=&\left(n_{m}-1\right)+\left(n_{m}-2\right)+\cdots+\left(n_{m}-t\right)=\\ & \frac{1}{2}\left(2 n_{m}-t-1\right) \end{aligned} $

根据最大交换次数公式可以推导出排名精度指标为: $p_{i}=1-\frac{s_{i}}{s_{\max }} $, 将该计算指标应用于接下来的实验中。

实验2选取400×80和800×160两种规模的评分矩阵, 2种算法都以20个不同的随机起始值进行迭代运行求解, 达到给定的不同排序精度, 记录时间数据, 结果如表 4、表 5所示。从表 4、表 5可以看出, 在排序精度为70%时, ALS对于2种规模矩阵的收敛速度相对较快, 而在排序精度大于70%时, ALS收敛时间较长, ALS-NCG的收敛时间比ALS算法小很多, 其效率较高。

图 4、图 5分别呈现矩阵规模为400×80、800×160时2种算法的运行时间趋势。从中可以看出, 随着排序精度的提高, ALS-NCG算法的时间消耗变化较为平缓, 更符合实际需求, 而ALS算法需要更长的时间才能达到目标精度。

3.5 ALS-NCG算法与ALS算法性能指标比较

本文采用推荐系统领域常用的均方根误差(Root Mean Squared Error, RMSE)来度量算法的性能。RMSE是预测值与真实值偏差的平方与预测值的比值的平方根, 其值越小说明测量的精确度越高。

ALS-NCG算法在执行速度与排序精度上都优于ALS算法, 实验3将在ALS训练的最优参数模型的基础上对2种算法的RMSE值进行求解, 其中, ALS算法最佳迭代次数为25, 实验结果如表 6所示。从表 6可以看出, ALS-NCG算法达到与ALS算法相近的RMSE值仅需迭代7次, 迭代次数明显减少。

3.6 ALS-NCG算法与其他算法性能指标比较

将ALS-NCG算法与受限玻尔兹曼机(RBM)、k=21时的k近邻(kNN)算法、ALS算法、ALS+kNN+RBM组合方法以及均值模型的RMSE值进行比较, 结果如表 7所示。从表 7可以看出, ALS-NCG算法具有明显优势, 它相对其他算法的RMSE改善率最高可达25.17%。

ALS算法虽然应用于推荐系统时效果较好, 但是其迭代时间过长, 影响推荐系统性能。NCG算法数值表现良好, 并且具有较高的收敛性, 可以加速ALS算法的收敛, 提高推荐效果。虽然ALS-NCG算法的每一步迭代复杂度较高, 但是算法整体收敛程度增大, 使得总迭代次数减少, 在Spark环境中, 其收敛速度明显高于ALS算法, 当两者的RMSE值接近时, ALS-NCG算法的迭代次数仅为ALS算法的1/3左右。

4 结束语

基于矩阵分解的ALS算法应用于推荐系统时, 执行速率与排名精度均较低。本文分析ALS算法自身存在的问题, 提出一种融合NCG与ALS的协同过滤推荐算法ALS-NCG, 并在Spark集群环境中进行实验, 结果表明, ALS-NCG算法在收敛速度和排名精度上都优于ALS算法。下一步将通过卷积神经网络对用户评论中的文本特征进行学习, 并将提取的文本特征引入到ALS-NCG算法中, 以进一步改善推荐效果。