项目的协同过滤方法利用项目之间相似性预测用户对项目的评分，但相似项的选择面临可扩展性和准确性的问题。为此，提出分布式协同过滤方法，利用模糊分块技术将项目集分成若干块，然后仅在各块内比较项目的相似性。通过裁剪相似关系图进一步改善效率，从图中去除不可能相似的项目之间的边。最后，利用图的分区技术，将相似关系图分割为若干较小的区，在各分区上并行计算项目的相似度。实验结果表明，该方法能改善推荐系统的准确性和可扩展性。
The ratings of items based on the similarities between items are predicted by traditional item-based collaborative filtering methods However, the selections of the similar ones are suffering from limited scalability and accuracy. A distributed collaborative filtering method was proposed. This method clusters items into several blocks using fuzzy blocking, and performs comparisons solely among the items within each block. Additional efficiency enhancements can be achieved through the pruning of the similar relationship graph:edges between items that are not likely to be similar can be removed from the graph. It divides this graph into multiple smaller partitions from each which similarity degrees between items is calculated efficiently in parallel. Experiments show that the proposed method can improve the recommendation scalability and accuracy.
互联网上不断增加的数据量使用户需要花费很多时间才能找到有价值的信息.协同过滤 (CF，collaborative filtering) 被认为是解决信息超载的有效技术之一，已广泛应用于推荐领域.为搜索目标项目或用户的相似项，CF需要对项目或用户进行两两比较.但推荐系统拥有数以百万计的用户和项目，并且其规模持续增长，用传统方法在大数据中搜索相似项难以保证在合理时间内提供较准确的结果.为解决上述问题，笔者提出了一种利用模糊分块技术实现并行化的协同过滤方法 (CFFB，collaborative filtering using fuzzy blocking)，主要贡献包括：1) 利用模糊分块技术将项目集划分为若干块，生成具有冗余特性的项目块集合；2) 利用项目-块的隶属关系构建相似关系图，通过对相似关系图的裁剪，剔除多余的比较；3) 利用图的分区技术，实现项目相似度和预测推荐的并行计算，改进CF的推荐精度和效率.
1 相关研究CF的推荐精度依赖于近邻的选择.在大量的多维数据中搜索前K个相似项是非常低效的.加之推荐系统中数据价值密度分布不均衡，需要探索一种按需约简数据集的方法.
Sobia等[1]利用改进的K-Means算法将评分矩阵划分为K个簇，然后根据与目标用户相似的簇中心的评分给出推荐. Hu等[2]从大数据集中动态地为目标用户构造局部项目-用户矩阵，并在该局部矩阵上实施预测.为缓解数据稀疏性问题，Hu等对每个用户簇中的用户评分采用了平滑策略，在推荐阶段不仅考虑用户对相似项评分，而且还融合志同道合的用户分别对相似项目和同一项目评分. Xu等[3]提出在实施推荐之前先估计缺失项，将单评分转为共同评分，Son[4]在用户相似度中集成了模糊相似度和硬相似度.前者根据人口统计数据计算获得，后者依据用户的历史评分而计算得到.为解决扩展性问题，Xu[3]和Xie等[5]采用Map-Reduce范式对推荐系统中的数据进行并行处理. Apache的Mahout开源项目也采用Map Reduce实现CF.
2 问题定义为避免在全量数据集上计算项目相似性，CFFB利用重叠分块方法依据项目的特征将项目集划分为多个块，获得块集合B，然后只在块集合B中的每个分块内进行项目的两两比较和相似度计算.在一般情况下，块内不必要的比较分为2类：1) 冗余比较.在各块中重复比较相同的项目对，这增加了比较次数，导致低效率；2) 多余比较.多余比较指在不可能相似的项目之间进行比较. CFFB需要丢弃冗余和多余的比较，保证推荐的效率和精度.
分块技术有2类相互竞争的度量：效率和效益.效率直接关系到块内的比较次数，即每块中需比较的项目对总数，由式 (1) 定义，其中|b|为块b∈B包含的项目数，‖b‖为在块b内需比较的项目对数.
| $ \left\| B \right\| = \sum\limits_{b \in B} {\left\| b \right\|} = \sum\limits_{b \in B} {\frac{{\left| b \right|\left( {\left| b \right| - 1} \right)}}{2}} $ | (1) |
效率也可用缩减比 (RR，reduction ratio) 度量，记为R，用于测量效率相比于基准块集Bbs增强的程度，由式 (2) 定义，R取值范围为[0,1]，其数值越高，表示块内比较的次数越少，分块的效率越高.
| $ R\left( B \right) = 1 - \frac{{\left\| B \right\|}}{{\left\| {{B_{{\rm{bs}}}}} \right\|}} $ | (2) |
基于分块技术的推荐算法的效益可用推荐算法的精度度量.这类指标依赖于相似项选择的正确性.项目对比较的次数越多，搜索到正确相似项的可能性越大，但它的效率也越低.因此，块集合的设置存在效益和效率之间的权衡.为识别项目间的冗余和多余的比较，CFFB引入了相似关系图GB结构.
定义1 共现对.已知推荐系统中项目集I={ik|k=1, …, n}、项目块集合B.若项目i∈I和j∈I同时出现在块集合B的同一个块b∈B中，则称项目i和j为共现对，记为〈i, j〉.
定义2 相似关系图GB.已知项目集合I和块集合B，从它衍生出来的无向图GB={VB, EB}，VB为顶点集合，每个顶点对应项目集I中1个项目，即∀vi∈VB:∃i∈I∧b∈B∧i∈b. EB为无向边集合，每条边对应1个共现对，即∀ei, j=〈i, j〉∈EB:i≠j∧∃bk∈B∧i∈bk∧j∈bk.
在GB中，边ei, j∈EB邻接的2个顶点vi和vj对应的项目i和j称为边ei, j的共现项目.边ei, j表示项目间存在可能的相似关系，需在后续步骤中通过相似度计算，确定项目i和j是否为相似对.
3 利用模糊分块技术改进CFCFFB包括2个阶段：相似度计算阶段和预测推荐阶段，其中相似度计算阶段其处理流程如下：
1) 采用笔者[6]提出的方法构建项目偏好向量；
2) 利用项目偏好和基本特征对项目进行模糊分块，产生块集合B；
3) 剪裁块集合B对应的相似关系图GB；
4) 并行计算项目相似度.
3.1 模糊分块由于K-Means聚类算法只允许每个项目指派给1个簇，并依赖于初始簇中心的选择；模糊K-Means可避免出现局部最优.因此，CFFB利用模糊K-Means算法实现重叠分块，将具有相似项目偏好和基本特征的项目组合在一起，构成K个项目簇，并将项目i∈I按一定概率划分到多个簇中.每个项目簇对应1个块，由此产生含K(K≥1) 个块的集合B.
3.2 构建和裁剪相似关系图对于块集合B中每个共现对〈i, j〉，若顶点vi和vj之间不存在1条边，则将项目i和j对应的顶点vi和vj加入到相似关系图GB中，并用1条边ei, j连接顶点vi和vj；否则意味着共现对〈i, j〉为冗余对，需剔除此冗余的比较.因此，每对共现对至多对应1条边.为进一步剔除多余的比较，需量化图GB中每条边的权重.边的权重表示了边的共现项目成为相似对的可能性.在理想状态下，项目对越相似，权重值应越大.
已知Bi⊆B、Bj⊆B分别为项目i和j隶属的块集合，Bi, j=Bi∩Bj为项目i和j共享的集合.项目i和j共享的块越多 (即|Bi, j|值越大)，它们越有可能是相似对.除了考虑|Bi, j|，边的权重还依赖于其共现项目所隶属的块的总数以及边的邻接顶点的度.当某个边共现项目隶属的块数越少，该边的权重应越高；当某个边顶点的度越小，该边的权重应越高.因此，边ei, j的权重wi, j依赖于Bi和Bj集合的Jaccard相似度，有
| $ {w_{i,j}} = \frac{{\left| {{B_{i,j}}} \right|}}{{\left| {{B_i}} \right| + \left| {{B_j}} \right| - \left| {{B_{i,j}}} \right|}}\log \frac{{\left| {{E_B}} \right|}}{{\left| {{v_i}} \right|}}\log \frac{{\left| {{E_B}} \right|}}{{\left| {{v_j}} \right|}} $ | (3) |
其中|vi|为顶点vi的度.上述加权方案依赖于模糊分块的分块原则：在实施分块时，将相似概率高的项目指派到同一个块中.因此，当2个项目分享的块数越多，它们越可能相似. CFFB可依据最小权重阈值wmin删除图GB中权重低于wmin的边，以剔除多余的比较.
3.3 并行计算项目相似度为有效地并行处理拥有大量顶点或边的图，需将图分割成若干更小的区.由于相似关系图中每条边表示一次项目对的比较，所以适宜采用顶点分割法，将边ei, j∈EB唯一指派给某个图的一个分区，从而使得相似度计算任务可以划分为多个并行执行的子任务，每个子任务处理一个分区.
EBp为分区p中包含的边.在分区p中，利用式 (4) 计算边ei, j∈EBp的共现项目i和j之间相似度为
| $ S\left( {i,j} \right) = \omega {S_{\rm{R}}}\left( {i,j} \right)\left( {1 - {\alpha _p}\left( {i,j} \right)} \right) + \left( {1 - \omega } \right){S_{\rm{F}}}\left( {i,j} \right) $ | (4) |
其中：ω为项目评分相似度SR(i, j) 的权值，SF为项目特征相似度，由式 (5) 中的欧氏距离定义，其中Fi=(fi, 1…fi, q) 为项目i的特征向量.
| $ {S_{\rm{F}}}\left( {i,j} \right) = \frac{1}{{1 + \sqrt {\sum\limits_{l = 1}^q {{{\left( {{f_{i,l}} - {f_{j,l}}} \right)}^2}} } }} $ | (5) |
用户对项目的公共评分数对评分相似度有较大影响，项目的公共评分数越多，其越有助于产生更好的推荐.为此，式 (4) 利用式 (6) 的项目公共评分稀疏度αp(i, j) 调整评分相似度.公共评分越多，其相似度越大.
| $ {\alpha _p}\left( {i,j} \right) = 1 - \frac{{{n_{i,j}}}}{{\mathop {\max }\limits_{{e_{i,j}} \in E_B^p} \left( {{n_{i,j}}} \right)}} $ | (6) |
其中ni, j为同时对项目i、j评分的用户数.在每个分区中完成相似度的计算后，需依据相似项搜索方法输出每个项目的相似项，并汇总来自各分区的计算结果实施推荐.
由于CFFB只对相似关系图中的边实施比较，项目相似度计算总次数为|EB|，所以对于项目总数为|I|的推荐系统，其缩减比R(B)=1-|EB|/‖Bbs‖，其中基准块集中比较次数|Bbs|=|I|(|I|-1)/2.只要在模糊分块过程中，每一块b∈B满足|b| < |I|条件，则依据构图原则，|EB| < |Bbs|成立，所以0 < R(B) < 1.
4 算法评估CFFB采用Apache Mahout应用程序编程接口实现模糊聚类，采用Spark实现相似度计算和推荐.为比较各算法的推荐质量和性能，在相同的开发环境中分别实现了新的质心选择 (NCS，novel centroid selection)[1]、采用平滑融合的协同过滤 (CFSF，collaborative filtering using smoothing and fusion)[2]和基于混合用户的模糊协同过滤 (HU-FCF，hybrid user-based fuzzy collaborative filtering)[4]算法. CFFB、HU-FCF和Mahout基于项目的协同过滤 (ICF，item-based collaborative filtering) 均使用Pearson相关系数测量项目之间的评分相似度.搭建的Hadoop平台拥有12台物理计算机，每台计算机的Java虚拟机运行在VMWare中的32位、内存为2 G的ubuntu操作系统上.采用的MovieLens数据集和Yahoo! Movies数据集信息如表 1所示，且分别按8：2比例划分为训练集和测试集.
|
表 1 MovieLens数据集统计属性 |
采用召回率FR、准确率FP和综合评价指标F1度量评估算法的精度.通常情况下，FR和FP并不是孤立讨论的，常采用F1值度量，对于块集B的F1计算如下.
| $ {F_1}\left( B \right) = \frac{{2{F_{\rm{R}}}\left( B \right){F_{\rm{P}}}\left( B \right)}}{{{F_{\rm{R}}}\left( B \right){F_{\rm{P}}}\left( B \right)}} $ | (7) |
为进一步消除多余的比较，通过设置恰当的权重阈值wmin>0，剔除图中低于权重的边，提高缩减比. 表 2显示，若wmin值过高，尽管缩减比提高了，但由于错过有价值的近邻，所以影响推荐精度.
|
|
表 2 wmin的影响 |
为了观察算法在不同稀疏度上的特性，将ML-100 K数据集划分为不同稀疏度的训练集和测试集. 图 1和图 2显示CFFB的召回率和准确率均优于另外4种算法.特别是当数据集稀疏时，改善更为显著.
|
图 1 对召回率的影响 |
|
图 2 对准确率的影响 |
各算法在相似度计算阶段的运行时间如图 3所示. CFSF采取了平滑策略，其运行时间较长，因此，实验只测试CFSF在ML-1 M和ML-100 K下的运行时间.尽管Mahout CF采用了Map-Reduce范式，但由于只在随机选取的500个用户评分数据集上计算项目相似度矩阵，所以其相似度计算阶段的运行时间在各个算法中是最快的，但从图 1、图 2可见，这也影响了其推荐精度. NCS在小数据集上计算相似度的时间与Mahout CF接近，但随着数据集的扩大，其相似度计算时间增长幅度高于CFFB.
|
图 3 相似度计算阶段运行时间 |
提出了一种基于模糊分块的协同过滤方法.为缓解数据集的稀疏性，该方法在相似度计算过程中融合了项目特性信息.为解决扩展性问题，利用模糊聚类算法将项目集分成若干块，然后利用项目和块的隶属关系构建相似关系图，通过裁剪最低权重的边，剔除多余比较.最后在Hadoop和Spark环境中验证了方法的有效性.但该方法依赖于块集合的冗余程度，图裁剪也需通过调整相应参数得到，因此，还需要探寻一种调参少、依赖于块集合的冗余程度低的分块方法.
| [1] | Sobia Z, Mustansar A G, Asra K, et al. Novel centroid selection approaches for K-means-clustering based recommender systems[J]. Information Sciences, 2015, 320(11): 156–189. |
| [2] | Hu Long, Lin Kai, Hassan M M, et al. CFSF:on cloud-based recommendation for large-scale e-commerce[J]. Mobile Networks and Applications, 2015, 20(3): 380–390. doi: 10.1007/s11036-014-0560-5 |
| [3] | Xu Ruzhi, Wang Shuaiqian, Zheng Xuwei, et al. Distributed collaborative filtering with singular ratings for large scale recommendation[J]. The Journal of Systems and Software, 2014, 95(9): 231–241. |
| [4] | Son L H. HU-FCF:a hybrid user-based fuzzy collaborative filtering method in recommender systems[J]. Expert Systems with Applications, 2014, 41(15): 6861–6870. doi: 10.1016/j.eswa.2014.05.001 |
| [5] | Xie Feng, Chen Zhen, Xu Hongfeng, et al. TST:threshold based similarity transitivity method in collaborative filtering with cloud computing[J]. Tsinghua Science and Technology, 2013, 18(3): 318–327. doi: 10.1109/TST.2013.6522590 |
| [6] |
王晓军. 推荐系统中分布式混合协同过滤方法[J]. 北京邮电大学学报, 2016, 39(2): 25–29.
Wang Xiaojun. A distributed hybrid collaborative filtering method in recommender systems[J]. Journal of Beijing University of Posts and Telecommunications, 2016, 39(2): 25–29. |