当今社会, 基于互联网技术的电子商务不断普及, 大数据分析和大数据挖掘已成为迫切要解决的问题. 推荐系统是指根据用户的兴趣特点和购买行为, 向用户推荐用户感兴趣的信息和商品的系统. 其中协同过滤推荐(collaborative filtering recommendation)是推荐系统中应用最早和最为成功的技术之一, 它一般采用最近邻技术, 利用用户的历史喜好信息计算用户之间的距离, 然后 利用目标用户的最近邻居用户对商品评价的加权评价值来预测目标用户对特定商品的喜好程度, 系统从而根据这一喜好程度来对目标用户进行推荐. 协同过滤最大优 点是对推荐对象没有特殊的要求, 能处理非结构化的复杂对象, 如音乐、电影等媒体数据^[1]. 其中的潜在因素模型(latent factor models)的核心思想是: 通过分析历史数据来预测事物的发展趋势, 矩阵分解算法(matrix factorization)是其中最为成功的算法之一^[2]. 但随着互联网数据的不断扩大, 应用传统的矩阵分解算法构造大数据潜在因素模型, 算法性能会大大下降, 难以实现有效的协同过滤, 其关键问题体现在数据稀疏性和算法可扩展性的改进上.

针对上述问题, 国内外学者专家们提出了一些改进想法: Pilaszy I最先提出基于ALS的协同过滤算法, 相对传统算法而言, 能有效提高过滤质量和推荐速度, 但该算法只考虑用户的相似性^[3]; 李改等对前者进行改进, 提出了ALS-WR 协同过滤算法, 该算法考滤到可扩展性方面, 但需要专门设计迭代式算法^[4]; 王辉等把用户聚类思想引入到协同过滤算法中, 改进了传统算法的数据稀疏性和可扩展性, 但精确度较低^[5] .

本文提出一种基于BC-AW的协同过滤推荐算法, 在传统算法的基础上, 引入联合聚类BC(BlockClust)和正则化迭代最小二乘法(Alternating least squares with Weighted regularization, AW). 首先分解原始评分矩阵的用户项目双维度, 然后使用联合聚类计算出多个同类评分块的子矩阵, 最后使用正则化迭代最小二乘法预测各个子矩阵的未知评分, 从而计算出推荐结果. 使用联合聚类所求得的子矩阵远比初此矩阵规模小, 可以大大减少过滤推荐的计算量. 通过与BaseMF算法、RSTE算法、TidaTrust算法、MoleTrust算法进行对比实验, 分析结果表明, 本文算法可以有效缓解传统算法并行化、可扩展性差的问题.

1 AW算法

设定矩阵 ${\rm R}$ 代表 $m$ 个用户、 $n$ 个对象的评分矩阵、矩阵 ${\rm U}$ 代表用户特征矩阵、矩阵 $V$ 代表推荐对象特征矩阵. ${{ R}_{i,j}}$ 代表 ${\rm R}$ 中的某个元素, ${R_i}$ 代表 ${\rm R}$ 的第 $i$ 行, ${R_j}$ 代表 ${\rm R}$ 的第 $j$ 列, ${{\rm R}^{\rm T}}$ 代表 ${\rm R}$ 的转置. ${{\rm R}^{ - 1}}$ 代表 ${\rm R}$ 的逆. 传算法一般使用SVD算法来分解 ${\rm R}$ ^[6], 但本文算法是通过计算低秩矩阵 ${\rm X}$ 来逼近 ${\rm R}$ , 使得 ${\rm X} = {\rm U}{{\rm V}^{\rm T}}$ , ${\rm U} \in {C^{m \times d}}$ , ${\rm V} \in {C^{n \times d}}$ (其中 $d$ 代表 ${\rm R}$ 的特征数), 一般状态下, $d \leqslant r$ , $r$ 代表 ${\rm R}$ 的秩, $r \leqslant \min (m,n)$ .

Step1: 我们通过最小化Frobenius的损失函数来算出一个低秩矩阵 ${\rm X}$ , 令 ${\rm X}$ 的得尽量接近 ${\rm R}$ , 如公式(1)所示:

${ L}({\rm X}) = {\sum\nolimits_{{ij}} ({ R}_{{ij}} - { X}_{{ij}})^2} $

(1)

上述公式(1)中, ${({R_{ij}} - {X_{ij}})^2}$ 为低秩逼近中一般平方误差项.

Step 2: 求解 ${ L}({\rm X})$ 的最优化问题 ${\rm arg}\;{\rm min}_{ x}{ L}({\rm X})$ , 于是改写公式(1)如下:

$L({rm U,V}) = {\sum\nolimits_{ij} {({R_{ij}} - {U_i}{V_j}^{\rm T})} ^2}$

(2)

上述式(2)会产生过于拟合的问题, 因此需要通过正则化项来解决这个问题, 则改写如下:

${{L}}\left( {{\rm {U}},{\rm {V}}} \right) = \mathop \sum \limits_{{{ij}}} {\left( {{{{R}}_{{{ij}}}} - {{{U}}_{{i}}}{{V}}_{{j}}^{\rm{T}}} \right)^2} + \lambda \left( {{{{U}}_{{i}}}_{{F}}^2 + {{{V}}_{{j}}}_{{F}}^2} \right)$

(3)

Step3: 对上面公式(3), 设定 ${\rm V}$ 不变, 对 ${U_i}$ 求导 $\partial L({\rm U,V})/\partial {U_i} = 0$ , 求解 ${U_i}$ , 如公式(4)所示:

${U_i} = {R_i}{V_{ui}}{(V_{ui}^{\rm T}{V_{ui}} + \lambda {n_{ui}}I)^{ - 1}},\;i \in [1,m]$

(4)

公式(4)中, ${R_i}$ 为用户所评过影片的向量矩阵, 由评分组组成, ${V_{ui}}$ 为用户 $i$ 所评过影片的特征矩阵, 由特征向量组成, ${n_{ui}}$ 为用户 $i$ 所评过的影片数, ${\rm I}$ 为 $d \times d$ 阶的单位矩阵.

Step4: 上述对公式(4)中, 设定 ${\rm U}$ 不变, 可以通过公式(5)求解 ${V_j}$ :

${V_j} = R_j^{\rm T}{U_{mj}}{(U_{mj}^{\rm T}{U_{mj}} + \lambda {n_{mj}}{\rm I})^{ - 1}},\;j \in [1,m]$

(5)

上述公式(5)中, ${R_j}$ 为用户 $i$ 所评过影片 $j$ 的评分所形成的向量, ${U_{mj}}$ 为用户 $i$ 评过影片 $j$ 的特征矩阵, 它由用户群中的特征向量组成, ${n_{mj}}$ 为用户 $i$ 评过影片 $j$ 的用户数量.

2 BC算法

BC算法能够将用多个较小且高相似度的评分矩阵来替代原始数据^[7]. 通过扫描该矩阵中的评分, 使用聚类方法计算行和列, 计算一次后, 重新评估每个子矩阵中用户、项目的概率, 如此类推, 直到产生收敛为止^[8]. 然后将评分匹配到最大概率的子矩阵中. 其算法思想如下:

首先扫描评分矩阵, 通过计算各评分的所属概率 $p(k|u,v,r)$ 来判断该评分是否属于某个子矩阵, 其参数包括: 用户—项目属于某子矩阵的概率 $p(k|u)$ 和 $p(k|v)$ 、该评分值属于某子矩阵中的概率 $p(r|k)$ . 其算法公式如下(其中 $\alpha = 0.000\; 0001$ , $\beta = 0.000\; 0001$ , $\theta = 0.000\; 0001$ ):

$p(k|u,v,r) = \frac{{(p(k|u) + \alpha ) \times (p(k|v) + \beta ) \times (p(r|k) + \theta )}}{{\sum\nolimits_{{k'} \in k} {(p({k'}|u) + a) \times (p({k'}|v) + \beta ) \times (p(r|{k'} + \theta ))} }}$

(6)

$p(k|u) = \frac{{\sum\nolimits_{V \in V(u)} {p(k|u,v,r)} }}{{\sum\nolimits_{{k'} \in k} {\sum\nolimits_{V \in V(u)} {p({k'}|u,v,r)} } }}$

(7)

$p(k|v) = \frac{{\sum\nolimits_{u \in U(V)} {p(k|u,v,r)} }}{{\sum\nolimits_{{k'} \in k} {\sum\nolimits_{u \in U(V)} {p({k'}|u,v,r)} } }}$

(8)

$p(r|k) = \frac{{\sum\nolimits_p {(k|u,v,r)} }}{{\sum\nolimits_{{r'}} {\sum\nolimits_{V \in U(V)} {p({k'}|u,v,r)} } }}$

(9)

以上公式中, $u$ 表示当前用户, $v$ 表示当前项目, $r$ 表示评分值, ${r'}$ 表示1到5的整数, $k$ 表示当前聚类, ${k'}$ 表示当前累加聚类, $U(v)$ 表示对 $v$ 评了分的所有用户集合, $V(u)$ 表示 $u$ 已评过分的所有项目集合. BC算法把原矩阵分为 $k$ 个具有高密度、高相似度的子矩因此, 该算法具有一定的降维作用^[9].

3 BC-AW算法

以下通过联合聚类和AW协同过滤两阶段来对评分矩阵的未知项进行预测.

1) 联合聚类

输入: 子矩阵个数 $k$ , 用户—项目评分矩阵 ${\rm R}$ .

输出: 子矩阵数 $k$ .

Step1: $u$ 表示用户量, $v$ 表示项目数, $p(k|u,v,r)$ 表示评分 $r$ 属于聚类 $k$ 的概率, 分别初始化 $u$ 、 $v$ 、 $p(k|u,v,r)$ , 使得 $\sum {^{'}} kp({k'}|u,v,r) = 1$ .

Step2: 应用公式(7)计算用户 $u$ 属于聚类 $k$ 的概率 $p(k|u)$ ; 应用公式(8)计算用户 $v$ 属于聚类 $k$ 的概率 $p(k|v)$ ; 应用公式(9)算出分值概率 $p(r|k)$ ; 应用公式(6)算出 $p(k|u,v,r)$ .

Step3: 最后选择概率 $k$ 的最大值作为该评分的子矩阵.

Step4: 跳回步骤2, 直到出现收敛, 结束循环.

2) AW协同过滤

首先用偏差小于等于的高斯随机数初始化矩阵 ${\rm V}$ , 接着分别用公式(4)和公式(5)更新 ${\rm U}$ 和 ${\rm V}$ , 重复进行多次迭代, 直到得出的RMSE值出现收敛为止, 结束迭代.

输出: 用户评分矩阵 ${\rm R}$ , 特征个数 $d$ .

输出: ${\rm R}$ 的逼近矩阵 ${\rm X}$ .

Step1: 用偏差小于等于0.01的高斯随机数初始化 ${\rm V}$ ;

Step2: 分别用公式(4)和公式(5)更新 ${\rm U}$ 和 ${\rm V}$ ;

Step3: 重复迭代公式(4)、公式(5), 判断得出的RMSE值是否收敛, 如果是, 则迭代结束;

Step4: 令 ${\rm X = U}{{\rm V}^{\rm T}}$ , 返回矩阵 ${\rm X}$ .

下面我们分析该算法的时间复杂度: 设 ${n_r}$ 为在矩阵 ${\rm R}$ 里的评分点个数, ${n_r} \leqslant m \times n$ (一般情况下, 矩阵 ${\rm R}$ 稀疏). ${n_f}$ 为特征个数, ${n_t}$ 为该算法的迭代数; 设 ${n_u}$ 为用户数; 设 ${n_m}$ 为对象推荐数. 变量 ${\rm U}$ 每次更新的时间为 ${\rm O}(n_f^2({n_r} + {n_f}{n_m}))$ , 变量 ${\rm V}$ 每次更新的时间为 ${\rm O}(n_f^2({n_r} + {n_f}{n_m}))$ , 如此类推, 在迭代 ${n_t}$ 次后的时间则为 ${\rm O}(n_f^2({n_r} + {n_f}{n_u} + {n_f}{n_m}){n_t})$ . 由此可见, 在 ${n_f}$ 、 ${n_r}$ 、 ${n_u}$ 以及 ${n_t}$ 恒定的情况下, ${\rm O}(n_f^2({n_r} + {n_f}{n_u} + {n_f}{n_m}){n_t})$ 取决于 ${n_r}$ , 也就是说, 算法的总时间复杂度与 ${n_r}$ 成正比, 可证该算法具有一定的可扩展性. 在AW协同过滤中, Step 2是最关键的步骤, 在这个步聚里, 每次应用公式(4)和公式(5)只能更新 ${\rm U}$ 和 ${\rm V}$ 中的一行值, 效率较低. 因此可以先将 ${\rm U}$ 和 ${\rm V}$ 分解为 $n$ 个列相等的子矩阵, 然后, 应用公式(4)和公式(5)对每个子矩阵并行更新, 这样可以大大提高运算效率.

综上所述, 本文基于矩阵分解的BC-AW协同过滤推荐算法改进传统算法的串行运算方式, 实现并行运算, 可以有效地解决传统算法中存在的可扩展性差问题.

4 实验分析 4.1 数据准备

本实验目的是通过分析比较本文算法和传统算法的性能, 硬件方面选用基于云计算的分布式硬件实验平台, 该平台由20台电脑组成20个运算节点, 每个节点配有 4.0 Hz的Intel处理器和32 G的内存, Linux操作系统. 实验数据来自美国Minnesota大学GroupLens项目组的MovieLens数据集. MovieLens数据集是GroupLens项目组开发的一个互联网研究型推荐系统数据集. MovieLens数据集中含有943个用户对1682部电影的100 000条评分数据, 平均每个用户评分的电影大于等于20部^[10].

4.2 评价指标

本次实验采用均方根误差RMSE和评分覆盖率 $CO{V_R}$ (Rating Coverage)作为算法推荐质量的评价指标.

$RMSE = \sqrt {\sum\nolimits_{(u,i)|{R_{\rm test}}} {{{({r_{ui}} - {{\widehat r}_{ui}})}^2}/{R_{\rm test}}} } $

(12)

其中 ${r_{ui}}$ 代表用户的实际评分, ${\widehat r_{ui}}$ 代表用户对影片的预测评分, ${R_{\rm test}}$ 代表影片的评分数. RMSE的值越小表示算法的精度越高. Rating Coverage是指在测试集中, 推荐系统可预测的评分数量占总评分的百分比^[11].

$CO{V_R} = \frac{{\text{可预测的评分数}}}{{\text{整个测试集的评分个数}}}$

(13)

4.3 实验结果及分析

本文算法分别与BaseMF (基于矩阵分解算法) ^[12]; RSTE (概率矩阵分解算法) ^[13]; TidaTrust (基于TidaTrust模型推荐算法) ^[14]; MoleTrust (基于MoleTrust模型推荐算法) ^[15]这4种推荐方法通过分析RMSE和 $CO{V_R}$ 的结果值进行分析比较. 实验开始, 首先随机选取两组训练集GROUP1和GROUP2: GROUP1为80%的Epinions数据集, GROUP1为90%的Epinions数据集. 然后分别把本文算法、BaseMF 算法、RSTE算法、TidaTrust算法、MoleTrust算法所建立的模型应用到训练集上进行学习, 指定 $y$ 、 $\lambda $ 和 $f$ 为潜在维度( $y = 0.005$ , $\lambda = 0.003$ , $f = 0.001$ ), $k$ 为实验基础( $k = 4$ ). 反复实验5次, 求平均值作为最终实验结果. 图1为这5种算法得出的RMSE值比较图.

从上图可以看出, 针对RMSE值, 当训练集为80%时, 本文算法比BaseMF算法降低了22%, 比RSTE算法降低了11%, 比TidaTrust算法降低了8%, 比MoleTrust 算法降低了7%; 当训练集为90%, 本文算法比BaseMF算法降低了21%, 比RSTE算法降低了10%, 比TidaTrust算法降低了7%, 比MoleTrust算法降低了7%; 由此可知, 本文算法的误差值明显低于传统的4种推荐算法.

图2(a)、图2(b)分别表示本文算法在GROUP1、GROUP2这两组训练集中, RMSE在不同 $k$ 值下的变化情况. $k$ 值越大, RMSE值越小, 证明推荐精度越高. 当 $k \in [0,4]$ 时, RMSE减小的幅度最大, 迭代时间的增幅最小; 当 $k \geqslant 4$ 时, RMSE的变化幅度趋于0. 从而得出当 $k = 4$ 时, 算法的推荐性能最佳.

下面分析5种算法的 $CO{V_R}$ . 我们知道, $CO{V_R}$ 直接影响用户对影片的可选择范围, $CO{V_R}$ 越高, 用户对影片的可选择范围越广, 从而用户满意度越高. 采用GROUP1数据集(即80%的训练集), 实验结果如表1所示.

分析表1可以看出, 当训练集为80%时, 本文算法的 $CO{V_R}$ 比BaseMF算法提高了68.52%,比RSTE算法提高了38.09%, 比TidaTrust算法提高了4.84%, 比MoleTrust算法提高了6.58%. 由此可见, 本文算法比传统4种算法具有更广的覆盖范围.

4 结论与展望

本文针对现有协同过滤算法中普遍存在的数据稀疏、可扩展性低这两个核心问题, 提出BC-AW(基于联合聚类和迭代最小二乘法)两阶段协同过滤算法. 首先由该算法通过对原评分矩阵进行用户—项目双维度联合聚类后得到的若干个子矩阵(这些子矩阵均为模式相同的评分块), 其规模比原矩阵小得多, 因此可以有效减少预测工作量; 再者, 采用正则化迭代最小二乘法预测子矩阵的未知评分可以优化推荐效率. 该算法在模拟大数据实验中(美国Minnesota大学GroupLens项目组的MovieLens数据集), 通过与几个经典的协同过滤算法(BaseMF算法、RSTE算法、TidaTrust、MoleTrust算法)作比较. 实验结果表明, 本文算法能有效改进推荐系统的稀疏性、可扩展性问题, 系统预测评分与用户实际评分接近, 并能为用户提供良好的使用体验.