协同过滤算法在位置推荐上的运用

王森 林勤花

摘 要：随着信息技术的普及与移动互联网的发展，用户每年都会产生海量的数据，目前我们已经进入了大数据时代。面对海量数据，如何寻找感兴趣的信息已经成为困扰用户的问题。由于每个人的兴趣爱好不太相同，使用一个大众版的排行榜并不能满足每个人的需求。位置推荐算法就是在大量数据作为支撑的情况下，对用户进行相似性计算，最后根据相似用户的签到地点做出推荐。本文主要通过经典的协同过滤方式实现一个位置推荐算法。

关键词：海量数据;位置推荐;协同过滤

随着移动互联网的兴起，用户可以方便快捷地记录当前的位置坐标，产生了许多有名的软件，比如微博、forsqure、ins等。Foursquare作为位置信息服务的巨头，目前積累了超过80亿的签到数据，全球每天都有用户使用该软件用来分享他们的生活。通过这些位置社交软件，用户对他们去过的地点进行签到，同时可以分享视频、音乐、图片等信息。本文以新加坡签到数据为例，对经典的协同过滤算法进行了位置推荐方面的实现。

一、相关知识

（一）基于位置的社交网络

基于位置的社交网络（Location-Based Social Networks，简称为LBSN）是在社交网络的基础上融合了位置服务的一种新的社交模式。这种新的模式不仅将用户和用户进行了联系（这种联系包括同学、同事、家人等），也将用户与地点进行了联系，形成了一个更加深层次的社交网络。随着智能手机的广泛运用，用户可以随时通过GPS定位自己的位置，这种基于位置的软件也越来越广泛地被人们使用，因此产生了大量的基于位置的软件，foursqure就是其中之一。

（二）Foursquare

Foursquare是Dennis Crowley于2009年在美国创立的基于用户位置信息的网站，用于使用户方便深入了解当地，并可对当地景点或餐厅等进行评分。目前已在全球积累了海量的用户。

二、协同过滤算法

（一）协同过滤算法公式介绍

相似的用户往往会有相同的兴趣，因此位置推荐算法常用的方式是先计算出每个用户的相似用户，再根据相似用户对相关地点进行推荐。

推荐算法中最经典的就是协同过滤算法。假设用U表示与当前用户最相似的用户组，用L来表示用户签到的地点集合， 则是指某个用户（这里用i表示）在某个地点（用j来表示）进行签到的概率，则该概率的计算公式如公式3-1所示：

这里的  表示是用户  在是否曾经去过地点j， 值零表示该用户未曾去过j，有值说明该用户去过。 是指用户K和用户i之间的相似性，具体计算公式如公式3-2所示：

（二）协同过滤算法在LBSN上的运用

下面通过一个小实验来说明基于位置的协同过滤推荐算法是如何工作的，假设   的值只能是0和1。1代表去过该地点而0代表没有去过，具体的签到矩阵如表1所示。

通过表1可知，用户A去过景点B、景点C，用户B则去过景点A、景点D。通过协同过滤算法，首先需要用公式3-2算出用户两两之间的相似性，以用户A为例：

最终可算出用户相似性矩阵如表2所示。通过用户两两之间的相识程度，可以找到每个用户最相似的N个用户，通过最相似的N个用户的签到情况即可进行推荐，即使用公式3-1计算用户在某个地点的签到可能性，很明显签到可能性最好的地点就是我们最终的推荐结果。

以用户A为例，假设采用最相似的两个用户进行位置推荐，则用户A最相似的用户是B和C。通过公式可以算出：

可以看出      >      ，说明在历史数据的基础上用户A去景点1的可能性要大于景点4，最终的推荐结果是景点1而不是景点4。

三、通过foursquare数据进行实验

（一）foursquare数据集介绍

本文实验中使用的数据是Foursquare数据集。该数据是位置推荐算法相关领域常用的经典数据集，是新加坡学者在2010年与2011年之间收集的新加坡签到数据，Foursquare上2010年8月～2011年7月新加坡的签到记录，共计342，850条。

（二）实验过程

首先将数据集合按照80%和20%的数据划分为训练集和测试集，然后计算每个用户的相似用户，最后根据相似用户去过的地点推荐得分最佳的地点。通过最终的实验，我们完成了协同过滤算法在位置推荐上的运用。

四、结束语

面对海量的数据，用户越来越难以获取感兴趣的信息，通过推荐算法可以较好地完成该任务。本文介绍了经典的协同过滤算法，并且介绍了该算法如何在位置推荐服务上使用。最后我们计划通过一个网页实现对数据可视化展示。

参考文献

[1] 宋亚伟，司亚利，刘文远，等. 融合时间特征和协同过滤的兴趣点推荐算法[J].小型微型计算机系统，2016，37（6）：1153-1158.

[2] 刘袁柳.面向LBSN的兴趣点和用户推荐方法研究[D].苏州大学，2015.

[3] 周翔宇，高仲合.基于地理位置和用户行为特征的推荐算法研究[J].通信技术，2019，52（8）：1928-1931.