基于Spark Streaming的增量协同过滤算法

曾志武 蔡明

摘 要：针对协同过滤算法处理大数据流时响应慢的缺陷，在改善推荐准确度的情况下，提出增量更新算法以加快响应速度，提高推荐系统性能。介绍了当前协同过滤算法以及KNN和Spark的相关知识，阐述了协同过滤算法的增量模型。采用Group Lens网站提供的Movie Lens数据集作为实验数据，应用Socket模拟流和Spark并行计算技术实现增量模型。实验结果显示，在保证推荐准确度的前提下，响应时间明显缩短，说明增量模型适合实时处理大数据流，可缓解数据处理不及时问题。

关键词：协同过滤；推荐系统；增量计算；实时流计算；Spark Streaming

DOI：10.11907/rjdk.173047

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2018）006-0088-04

Abstract：Because of the slow response of collaborative filtering algorithm in dealing with large data streams， this paper presents an incremental updating algorithm to speed up the response times and improve the recommendation system performance under the condition of guaranteeing the accuracy of recommendation. Firstly， this paper presents the background and purpose of the study， and then introduces the current collaborative filtering algorithm and its related knowledge of KNN and Spark. Secondly， the incremental model of collaborative filtering algorithm is proposed . Finally， we used Movie Lens dataset provided by Group Lens website was used as the experimental data source， with Spark Stream to receive stream data from Socket and Spark to parallel computing increment data . The experimental results showed that in the case of reliable recommendation accuracy， response times is significantly improved and it proves that the incremental model proposed in this paper is very suitable for real-time processing of large data stream to alleviate the problem of no timely processing data.

Key Words：collaborative filtering； recommender system； incremental computing； real-time stream computing； Spark streaming

0 引言

在大数据流环境下，各大电子商務网站都希望及时捕获、分析处理用户的偏好信息，及时响应用户的兴趣变化，给用户推荐喜欢的商品。以前一般是进行批量或小批量的全量分析，这样响应时间明显滞后于用户喜好的变化。目前推荐系统算法一般分为基于内容的推荐算法[1]、协同过滤推荐算法[2]以及混合推荐算法[3]3类，其中协同过滤推荐算法提出最早、应用范围最广。因此，本文针对该算法进行改进，在保证推荐准确度的前提下提出增量模型，解决推荐延迟或响应慢的问题。

1 协同过滤算法与实时流计算

1.1 协同过滤算法

协同过滤算法一般分为基于内存的协同过滤和基于模型的协同过滤。基于内存的协同过滤比较简单、高效，但遇到大规模数据时难以扩展、响应时间相对滞后。基于模型的协同过滤运用机器学习算法离线训练数据获得适当的模型，然后应用到实际场景中，这样不能及时反映用户喜好的变化。基于内存的协同过滤分为基于用户的协同过滤和基于项目的协同过滤，基于用户的协同过滤一般应用在用户偏好经常变化的场景，比如新闻视频等网站，而基于项目的协同过滤一般应用在物品数量变化相对较少的情况，比如购物网站。基于模型的协同过滤有基于矩阵分解的协同过滤[4]以及基于神经网络的协同过滤[5]等，本文主要研究基于项目的协同过滤，以改善推荐精度和响应时间，提高系统可扩展性。

基于项目协同过滤算法流程如图1所示。

首先形成用户项目评分矩阵，然后计算相似度矩阵，接着从相似度矩阵获取K个相似近邻，然后基于K近邻集预测用户未评分项目的分数，最后对未评分项目进行排序，推荐前N个物品给用户。

目前项目相似度计算方法有余弦相似度、修改的余弦相似度以及Pearson相似度，其中Pearson相似度比较常见，如式（1）所示。

相似度计算在整个推荐流程中至关重要，本文选用文献[6]提出的规范化Dice系数（Generalized Dice Coefficient）计算项目间的GDC相似度，该方法是Pearson相似度计算公式的改进，如式（2）所示。

利用KNN最近邻模型[7-8]（k-NearestNeighbor）获取与用户最相似的K个用户。为保证推荐精度，将K的取值与项目评分个数相关，如式（3）所示。

最后，依次计算用户未评分项，并排序选择前N个未评分项作为该用户的推荐项。

1.2 实时流计算

Spark Streaming是基于Spark内核的一个分布式流计算应用框架，基于时空对数据流进行分割形成DStream，然后批量输送给Spark引擎进行分布式内存计算。它是一个高效的分布式流计算引擎，在机器学习、数据挖掘等场合为用户提供实时响应。

Spark是UC Berkeley AMP lab开源的通用分布式并行计算框架。该框架基于内存迭代计算，减少了I/O输入输出操作，从而提高了数据处理效率。Spark创新性地提出了弹性分布式数据集（Resilient Distributed Dataset，RDD）[9]。RDD作为Spark的核心具有如下特性：①只读性数据集，易于多线程并发执行；②一种分区的分布式存储数据结构，易于分布式并行计算；③提供丰富的算子，同时每一个分区均有一个算子，方便用户进行数据处理；④记录了数据操作依赖关系，解决了数据容错问题，且根据依赖关系实现了延迟调度机制，有效提高了执行效率。其工作原理如图2所示。

Spark Streaming工作流程是对流数据按照DStream Graph模板生成Job，然后通过JobScheduler线程池方式提交给Spark Cluster，如图3所示。

2 增量模型与并行化实现

2.1 增量模型

采用基于项目的相似度，其中相似度计算采用GDC相似度增量[10]，如式（2）所示。将该公式首先分解为7个因子，如表1所示。当有新的评分记录时更新缓存因子，增量更新如式（5）所示。

计算过程中有多个新增评分项时，每个评分项都可能对Sim（i，j）进行修改，一个Sim（i，j）值会受到新增项目i和项目j的同时修改，也就是说新增项目i和项目j必须在一个线程内执行。所以，要在并行化执行之前隔离这些冲突项，让非冲突项尽可能地并行计算。

微批量形式的增量更新预测项目评分步骤如下：①根据初始数据初始化缓存因子并读入内存，为后续增量计算作准备；②当微批量形式的增量数据到来时，从增量数据中提取出冲突项评分，对冲突项评分单线程进行并发计算，对非冲突项进行并行计算，并将增量评分加入评分集合；③并行化获取用户的未评分项，应用第②步计算结果预测用户未评分项目的评分。先通过B/E得到相似度，然后通过式（3）得到未评分项的最近邻，根据预测评分式（4）计算用户未评分项目，整个过程都利用Spark基于内存的并行化计算；④不断接受新数据，执行步骤②、步骤③。

2.2 并行化实现

输入评分数据Ratings，输出项目相似度集合，代码如下：

上述代码中：第①～②步为初始化参数和SparkStreamContext；第③步并行初始化7个缓存因子；步骤⑤和步骤⑥聚合更新缓存因子所需要的数据；步骤⑦更新7个缓存因子，步骤⑨直接计算相似度矩阵。

3 实验结果分析

实验采用Intel 4Core主频为2×2.2GHz、内存为8GB、硬盘160GB的计算机硬件配置，Spark版本2.2.0，基于Spark本地运行模式。采用Group Lens[11]网站的Movie Lens作为数据源，使用ML-2M的数据包，其中包括671个用户对9 066部电影的100 004条评分记录，评分值为1-5。从数据包中按时间排序分别选取1万、2万、3万、…、8万、9万、10万个评分记录作为实验数据，其中80%作为训练数据集，20%作为测试数据集。

实验采用平均绝对误差MAE[12]作為评价标准，MAE通过计算用户实际评分与预测评分之间的绝对偏差衡量推荐准确度，如式（6）所示。

其中：T为项目数量，r-ui为用户u对项目i的实际评分，r′-ui为用户u对项目i的预测评分。MAE越小，代表算法的推荐精度越高。本文对增量协同过滤算法与全量协同过滤算法的MAE进行比较，如图4所示。

从图4可以看出，在用户评分数据集相对较小、数据稀疏的条件下，本文增量算法的推荐精度低于全量算法。随着用户评分数据集逐渐扩大，算法推荐精度逐渐提高，趋向于全量协同过滤算法推荐精度，这说明本文提出的基于Spark Streaming的增量协同过滤算法可以适应海量数据背景下的推荐。

在不同数据量情况下发现，增量运行时间和全量运行时间明显不同，如图5所示。

实验采用Speedup[13]衡量同一数据集下增量算法和全量算法表现。

其中：F-p为p个数据集全量计算时间；I-p为p个数据集增量计算时间。增量计算与全量计算的加速比如图6所示。

从图6可以看出，本实验Speedup值由较大幅度增长到趋于平缓。随着数据量增加，系统资源逐渐成为性能提升的瓶颈。在对更大规模数据处理时，增加系统资源使Speedup进一步提升，表明该增量算法在大规模数据下的执行效率高于全量更新算法，并且数据规模越大，精度越趋向于全量更新。

4 结语

基于Sprak Streaming计算的增量协同过滤算法缓解了大数据流处理的响应时间，在大数据环境下得到了较好应用。但如何从大规模数据中利用数据的多样性获取精准用户偏好模型以提高推荐准确度，是今后的研究方向。

参考文献：

[1] PAZZANI M J， BILLSUS D. Content-based recommendation systems[M]. The adaptive web. Springer Berlin Heidelberg，2007：325-341.

[2] LINDEN G，SMITH B， YORK J. Amazon.com recommendations： item-to-item collaborative filtering[J]. Internet Computing， IEEE，2003，7（1）：76-80.

[3] 俞騁超.基于深度神经网络的用户会话推荐算法研究[D].杭州：浙江大学，2016.

[4] KOREN Y， BELL R， VOLINSKY C. Matrix factorization techniques for recommender systems[J].Computer，2009，42（8）：30-37.

[5] 何佳知.基于内容和协同过滤的混合算法在推荐系统中的应用研究[D].上海：东华大学，2016.

[6] LUO X， XIA Y N， ZHU Q S. Applying the learning rate adaptation to the matrix factorization based collaborative filtering， knowledge-based systems[EB/OL]. https：//doi.org/10.1016/j.knosys.2012.07.016.

[7] LUO X， XIA Y N， ZHU Q S. Boosting the K-Nearest-Neighborhood based incremental collaborative filtering[J]. Knowledge-Based Systems，2013（53）：90-99.

[8] HERLOCKER， KONSTAN J A， RIEDL J. An empirical analysis of design choices in neighborhood-based collaborative filtering algorithms[J]. Information Retrieval，2002，5（4）：287-310.

[9] Apache Spark[EB/OL].http：//spark.apache.org/

[10] LUO X， XIA Y N， ZHU Q S. Incremental collaborative filtering recommender based on regularized matrix factorization， knowledge-based systems[EB/OL]. https：//grouplens.org/datasets/movielens/.

[11] BREESE J S， HECKERMAN D， KADIE C. Empirical analysis of predictive algorithms for collaborative filtering[C]. Proceedings of the Fourteenth conference on Uncertainty in artificial intelligence. Morgan Kaufmann Publishers Inc.，1998：43-52.

[12] ZHANG J， LI T， DAR， et al. A parallel method for computing rough set approximations[J]. Information Sciences，2012，194（5）：209-223.

（责任编辑：杜能钢）