云环境中基于海量签到数据的并行地点推荐算法研究

金宁+栾方军+师金钢

摘要：目的：提出一种基于MapReduce架构的并行推荐算法，提高在超大规模且结构复杂的数据集中的推荐效率。方法：在MapReduce并行计算模型中分析用户访问真实地理位置的行为轨迹，将用户的签到行为量化为用户对签到地点的喜好程度，综合分析用户间的相同签到记录及不同用户对签到地点的偏好程度，计算用户间的相似性，实现个性化地点推荐。利用Gowalla和Foutsquare社交网站真实的签到数据集进行实验验证。结果：推荐结果在召回率及精度上均优于传统的协同过滤推荐算法且具有较高的加速比。结论：该推荐算法具有良好的可扩展性及高效的执行性能，能够适用于云计算环境中针对海量数据的推荐。

关键词：推荐系统；云计算；基于位置服务

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）36-0012-02

1 基于海量签到数据的推荐算法

在基于位置的社交网络中，如果两个用户是好友，那么他们在相同地点签到次数是两个陌生用户的三倍，说明了用户间的地理位置特征与其社会关系互相补充. 用户的每次签到行为都具有一定意义，用户的每个签到记录能够反映其偏好，在同一地点进行签到的用户之间具有某种共性。

2 基于MapReduce架构的并行推荐系统模型

2.1 并行推荐框架

MapReduce是Google 公司首先提出的一种能在大型计算机集群上并发处理海量数据的分布式计算框架模型。它是一种简化的分布式编程模式，以充分发挥廉价计算机集群的计算能力，以解决单一普通计算机由于处理器以及存储资源的限制而无法有效处理海量数据计算的问题。该模型会解决输入数据的分布细节，跨越机器集群的程序执行调度，处理机器失效问题，并且管理机器之间的通讯请求。对大规模数据的计算过程可以简化为Map 和Reduce两大基本操作，Map就是将一个任务分解成为多个任务，Reduce就是将分解后多任务处理的结果汇总起来，得出最终的分析结果。初始状态下，数据集进行划分并存储在分布式文件系统中。用户通过重写自己的Map函数处理初始的数据key/value 对，产生一系列的中间key/value 对，并且使用重写的Reduce 函数将具有相同key 值的中间键值对聚集起来进行处理，最后将结果输出。

Map （k1，v1） → list（k2，v2）

Reduce （k2，list（v2）） → list（k3，v3）

Hadoop是Apache 开源社区开发的一个MapReduce的Java 实现，提供了在由通用计算设备组成的大型集群上执行分布式应用的框架。图1 展示了在Hadoop计算中的数据流向，Hadoop将输入数据分为N个Split，启动相应的N个Map 函数应用到输入数据的不同分块上，输出key/value值对；然后通过merge 过程对中间键值对进行分配，将相同key 值的所有键值对发送到同一Reduce 节点上；最后Reduce 计算过程被触发，对相同key 的键值对列表进行处理，将最终的结果输出到分布式文件系统HDFS（hadoop distributed file system）中。

2.2 海量签到数据存储

Gowalla和Foutsquare提供的簽到数据格式为，将海量签到数据以分块的形式存储到HDFS分布式文件存储系统中，导入的数据格式为txt文本格式。HDFS具有高容错性，为了保证数据的安全和高效，存入的签到数据均备份副本，保证了数据的鲁棒性。

2.3 相似度计算与推荐算法

签到地点对用户偏好的贡献度计算构建过程如下：其中CheckinDate为用户的签到数据信息，包括用户编号user_id，签到地点point_id，用户的签到数checkin_num等。

Map阶段。将签到数据作为输入，Map函数根据CheckinDate数据格式特点，按照偏移量提取< point_id，（ user_id+ checkin_num）>键值对作为输出。

Reduce阶段。Reduce的输入为< point_id，list（ user_id+ checkin_num）>记录列表，将point_id作为key值，将相同key值的签到数据分配给同一个Reduce任务.Reduce函数分别累加两个变量pn、un，对每个新出现的point_id同时对pn、un加1，对每个已现的point_id仅对pn加1，对每个user_id的pn除以对应的checkin_num求得签到频率，将用户总数N除以un并取对数，然后将两结果相乘计算得出签到地点对其偏好的贡献度pw.Reduce阶段输出格式为<（ point_id+ user_id）， pw >。

用户相似性计算阶段的MapReduce构建过程中，首先计算在一个地点的相似性，然后汇总在各地的相似值，计算出用户间相似度，具体构建过程为：

Map阶段。输入键值对为， Map函数比较用户间pw，计算出用户间在该点的相似性Sim（m，n，c），其输出形式为

Reduce阶段。该阶段重新分配Map阶段的输出，以< user_m+user_n >作为复合键，将相同< user_m+user_n >的任务分配到同一个Reduce函数，累加其在各签到地点的相似值，并按照相似值度高低排序，其输出的键值对表示为：，其中samelist（point_id）为相同的签到序列用于下阶段地点推荐。

地点推荐阶段首先读取用户的签到序列，按对用户偏好贡献度排序输出，得到推荐地点序列，其MapReduce构建过程为：

Map阶段。Map函数读取user_m相似度最高的用户user_n的签到序列并按照pw排序，其输出形式为。

Reduce阶段。Reduce函数判断point_id是否在samelist（point_id）中，如不在，则将point_id输出，得到推荐序列键值对< user_id ，recommend（point_id）>

本阶段在MapReduce架构下实现了并行协同过滤推荐算法，整个构建过程功能划分明确，各阶段依次衔接，上一次MapReduce的输出即为下一次的输入。

3 實验分析

为了评估基于MapReduce架构的并行地点推荐算法的性能，将基于MapReduce架构的并行推荐方法与传统的协同过滤推荐方法在推荐准确度及执行效率上进行了实验，对实验结果进行了分析讨论。

3.1 实验设置

实验中搭建了一个由7台电脑组成的计算机集群，其中一台作为master控制几点，其余6台作为slaver计算节点，每台电脑搭配Inter酷睿 i3 CPU，2G内存，操作系统为Ubuntu10.10，Hadoop版本为1.0.4.实验测试采用Gowalla和Foursquare社交网站真实的签到数据集，包括美国旧金山市2009 年3 月到2010 年10月的155254条签到记录。

3.2 推荐结果准确度评价

实验采用多次实验方法，抽取一定比例的用户签到数据作为训练集，余下的位置作为测试集，使用召回率和精度模型验证。从表1和表2中结果可以看出，本文提出的MR-CF算法的推荐效果优于采用余弦相似度的传统协同过滤推荐算法CF，说明签到行为可以体现出用户的偏好，将用户的位置信息作为新的考虑因素添加到推荐系统中可以为用户提供更加有效、符合用户个性化需求的地点推荐，提高推荐的准确度。

4 结论

针对云计算环境中海量数据的推荐问题，提出了一种基于MapReduce架构的并行协同过滤地点推荐算法，将地理位置信息加入传统推荐算法中，并在Hadoop应用框架上设计了相应的并行推荐模式。实验证明，基于MapReduce架构的并行协同过滤地点推荐在推荐精度、应时间及对大数据集的适应上表现较好，具有良好的可扩展性和高效的执行性能，适用于云计算环境中针对海量数据的推荐。文章的相似度计算算法并不是很完善，在今后的研究组将进行改进。

参考文献：

[1] Sheng C， Zheng Y， Hsu W， et al. Answering Top-k Similar Region Queries[C]. In Database Systems for Advanced Applications. 2010： 186-201.

[2] 荣鑫. 基于地理位置的社交网络潜在用户和位置推荐模型研究[D]. 南京邮电大学， 2013.