随着互联网的高速发展以及全球定位技术的不断加强，移动终端设备逐渐成为人们日常生活中必不可少的事物，这极大地加速了基于位置的社交网站的崛起(LBSN, location-based social network)，如Twitter、Yelp、Foursquare等。根据Foursquare官网的统计信息，每月使用Foursquare的用户超过5 000万，月位置签到数量超过120亿条，数字相当惊人，并且最高的时候能够在一天之内产生900万条签到记录，这充分说明基于位置的社交网络已经得到广泛的推广和使用^[1-3]。

这些LBSN鼓励用户实时地向朋友分享自己的出行经历以及目前所处的位置，而这些具有一定语义的位置统称为兴趣点(POI, point-of-interest)(如中餐厅和电影院)。这种实时分享位置的移动服务可以让用户的朋友充分参与进来，增进朋友间的感情也丰富了如今的社交网络氛围^[4]。通常情况下，一条典型的签到记录除了包含用户发布的文本信息外，还包括签到时间、签到地点的位置信息如经纬度坐标^[5]。通过收集LBSN上的用户签到记录，可以对用户的个人偏好进行挖掘，从而向用户提供一系列符合其偏好和需求的位置服务，如兴趣点推荐(POI recommendation)。目前，各式各样的社交网站已经产生了大量的用户签到数据，值得去研究其中蕴藏的用户出行模式。这些含有语义和坐标的签到数据既可以帮助用户在新的区域中发现有趣的地方，也能够帮助第三方或商家吸引客流，因此具有很高的研究价值^[6-14]。

上下文是兴趣点推荐中一个非常重要的研究内容。在真实的应用场景中，人们选择访问某个地点的决定受到诸多因素的制约，如天气、路况、场馆开放时间等。传统的推荐系统是依靠用户项目二元关系来进行基于内容的推荐或协同推荐，适用于商品、电影等，但无法有效地处理兴趣点推荐特有的上下文如地理距离。因此，兴趣点推荐旨在通过分析和处理用户历史出行记录，结合多种上下文，考虑地理等有着直接决定作用的因素，来为用户推荐其满意的未知地点^{[5-6, 15-22]}。

LBSN通常会根据地点功能对地点定义类别，而一个地点可能对应多个类别^[21-23]。类别可以反映用户对于地点的潜在偏好，如果用户的签到主要集中在某些类别上，那么可以着重处理这些类别来完成精准的推荐。LBSN中包含大量的用户和地点，而一般情况下一个用户只访过少数地点，甚至有的用户只在两三个地点上有过签到行为，如果构建用户地点二维矩阵，那么该矩阵会显得非常的稀疏，以该矩阵直接进行推荐显得不太合适。因此，笔者将类别信息充分融入兴趣点推荐中，以此来提高推荐的精度。首先根据用户的历史签到记录，构建用户地点类别的签到矩阵，使用矩阵分解技术分别得到用户特征矩阵和地点类别特征矩阵，然后根据一个地点所属的类别去计算该地点的特征向量，再对社交网络中用户对地点类别的偏好差异性进行建模，最后由用户特征向量和地点特征向量做内积运算得到用户对目标地点的分值，将这些分值从高到低排序，取前K个地点为用户生成推荐列表。

文中第2章回顾了相关研究工作；第3章详细阐述了结合地点类别信息和社交网络的兴趣点推荐算法；第4章是算法的实验结果并对其原因进行解析；最后总结全文。为了方便起见，文中所说的位置和地点均代表兴趣点。

1 相关工作

传统的推荐系统是将地点看成简单的项目，然后运用协同过滤之类的方法进行推荐，这种忽略用户移动性以及上下文的处理方式往往使得推荐结果不尽人意。因此，目前许多研究关注于影响用户行为的多种因素，主要可以分为四大类。

1.1 基于地理位置的兴趣点推荐

用户通过实时的签到与地点进行交互，不同签到地点之间的距离往往反映用户签到在地理上的行为模式，通常可以采取幂率分布、高斯分布等来对不同地点间的距离进行刻画。Ye等^[5]对Foursquare和Whrrl的公开数据集进行处理后，发现用户在某个地点签到的概率与这个地点到当前位置的距离呈现幂率分布。Cheng等^[16]认为用户的签到往往是围绕某些区域中心的，因此提出了多中心高斯模型。相反地，Zhang等^[21]认为不同的用户对于地理因素具有不同的行为模式，不能统一使用幂率分布或高斯分布来模拟，而使用核密度模型则可以实现用户的个性化。

1.2 基于时间因素的兴趣点推荐

用户的签到通常呈现出一定的时间规律性，如满足周期性或连续性。Yuan等^[6]将一天分为24 h，构建时间用户地点三维矩阵并利用时间之间的相似度去填充该三维矩阵，继而改进传统的协同过滤中存在的不足。Gao等^[10]同样将一天分为24 h，为每个时间段分别构建用户地点矩阵，然后进行矩阵分解求得不同时间段下的偏好。Cheng等^[7]和Feng等^[8]认为短时间内的签到具有较强的关联性，可以利用马尔科夫链去模拟序列变化来推荐序列下一个地点。

1.3 基于社交网络的兴趣点推荐

随着近几年社交网络的崛起，越来越多的研究开始重视社交关系。Ye等^[15]早期就提出了在协同过滤中运用社交关系，因为朋友之间可能会去相同的地点。后来Cheng^[16]等提出朋友间很大程度上不会签到同一地点，也通过实验表明了无法有效地利用社交关系中的相同地点去提升推荐结果的精度。因此直接从朋友处获得地点推荐也就存在不合理^[15]。在传统的推荐系统中推荐目标大多是电影、商品之类的比较单一、简单的线上项目，不具备实时移动的物理性质。

1.4 基于地点类别的兴趣点推荐

目前，很少有研究会考虑位置的所属类别，而恰恰类别会在某些真实场景下发挥重要作用。Bao等^[24]采用HITS算法为不同城市下的每个地点类别创建“本地专家”，当用户访问一个新城市时，通过对用户偏好进行建模并匹配相应的“本地专家”来寻找合适的推荐地点。Liu等^[23]计算出用户的位置偏好后基于k-means算法对用户进行聚类，接着对用户类别矩阵使用矩阵分解技术从而得到下一个可能访问的类别，同时结合以幂率分布表示的地理模型共同产生最终推荐结果。Zhao等^[25]将用户划分为不同群组并以地点类别签到向量去表示每个用户，接着根据不同群组之间在地理区域上的相似性采用协同过滤方法来完成推荐。Hu等^[26]认为用户对一个地点的评分与其近邻地点类别无关，因此应该过滤掉近邻类别的影响来完成目标地点的推荐。

上述相关工作均没有考虑社会化关系在推荐中的作用。因此，文章从该角度出发，对用户的地点类别偏好进行建模，同时结合社交关系来挖掘用户感兴趣的地点。

2 结合地点类别和社交网络的兴趣点推荐算法 2.1 问题定义

定义1：基于位置的社交网络。随着互联网和全球定位技术的高速发展，社交网络已经不再局限于传统的定点模式，而是在可移动终端的基础上实时地进行交互，不断将用户的地点数据实时地进行刷新，因此，这种以位置为主要载体的社交网络被称为基于位置的社交网络^{[5, 15-16, 18-22]}。

定义2：签到。用户在一个地点上的签到记录通常用＜u, l, t＞三元组来表示，其意思是某个用户u在t这个时间点访问了某个位置l。用户的签到在很大程度上反映了用户对于某地点的行为模式。

定义3：兴趣点。兴趣点是根据地点的语义和功能而概括出的精炼表达，如餐厅、电影院、博物馆。兴趣点的相关信息通常包括名称、类别、经纬度等。文中所提及的地点都视为兴趣点。

定义4：兴趣点推荐^[26-28]。在LBSN中，根据用户的历史签到记录，结合多种因素，为用户推荐符合其偏好的兴趣点，帮助人们发现新事物。兴趣点推荐可以分为普通兴趣点推荐和连续兴趣点推荐^{[7-8, 13-14, 29-30]}，文中主要研究前者，即普通兴趣点的推荐。

文中使用U={u₁, u₂, u₃, ..., u_|U|}和L={l₁, l₂, l₃, ..., l_|L|}分别表示用户的集合和兴趣点的集合，其中|U|和|L|分别代表各自的总数量。给定U和L构成的用户历史签到记录、社会化关系S、地点类别C，为某个用户i推荐兴趣点的任务即可表示为

$ U{\rm{ }} \times L{\rm{ }} \times S \times C \to {\mathit{\boldsymbol{E}}_i}, $

(1)

式中，E_i是面向用户i的推荐列表，以向量形式展示。计算出所有目标地点的分值后进行排序，将前K个分值较高的兴趣点作为结果推荐给用户。

2.2 地点类别影响分析

LBSN通常会预先定义地点的类别信息^[23]，例如Foursquare中的地点类别是一个三级的分层框架，如图 1所示。用户类别矩阵显然在稀疏性方面优于用户地点矩阵，而且类别很大程度上可以反映用户对于某种功能或语义的地点的喜好。根据历史签到数据计算出类别偏好差异，然后结合这些类别信息为用户推荐兴趣点，继而提升推荐的准确性。

相比传统的推荐系统，文中提出的算法不是直接使用用户地点关系来进行推荐，因为这种方式会在矩阵的强稀疏性下导致推荐结果不佳。文中算法首先从原始数据集中提取出用户类别矩阵R，采用01的形式，如果用户i曾经访问过某个类别j，那么R_ij的值为1，如果没有访问过则为0，R∈ |U|×|C_a|，|C_a|代表的是类别的总数量。矩阵分解技术被很多推荐系统算法所使用和推广，在此启发下，笔者也使用矩阵分解来对类别矩阵进行剖析，继而得到了用户的特征矩阵P∈ f×|U|和类别的特征矩阵Q∈ f×|C_a|，f表示特征维度，可以根据经验来进行选取。分解过程中的损失为

$ \mathit{\Gamma = }\frac{1}{2}\sum\limits_{i = 1}^{\left| U \right|} {\sum\limits_{j = 1}^{{C_a}} {{\mathit{\boldsymbol{I}}_{ij}}{{({\mathit{\boldsymbol{R}}_{ij}} - {\mathit{\boldsymbol{P}}_i}^T{\mathit{\boldsymbol{Q}}_j})}^2} + } } \frac{{{\lambda _1}}}{2}{\left\| {{P_i}} \right\|_{\mathop F\limits^2 }} + \frac{{{\lambda _2}}}{2}{\left\| {{\mathit{\boldsymbol{Q}}_j}} \right\|_{\mathop F\limits^2 }}, $

(2)

式中，I是指示函数，它的作用是来制约那些用户没有访问过的位置，使他们的权重为0，而那些正例(即用户真正访问过的位置)则为1。P_i和Q_j分别是由式(1)初始化的关于用户i和类别j的特征向量。正则化损失对于矩阵分解而言，可以有效地防止过拟合，λ₁和λ₂是正则化项的权重，||.||表示Frobenius范数。最后，通过经典的梯度下降算法不断地去迭代和更新用户和类别的特征向量。

通常情况下，一个位置不止有一个类别，因此它对应了多个类别的特征向量，对这些类别向量进行集成即可得到该地点的特征向量。首先，将地点和类别进行映射，得到地点和类别的表示矩阵M∈ |L|×|C_a|，同样采用01的形式，如果一个地点属于某个类别，那么在矩阵中的对应元素即为1。为0的时候恰好相反，代表地点与这个类别无关。接着，根据地点类别矩阵可得到地点的特征矩阵H为

$ \mathit{\boldsymbol{H}} = \mathit{\boldsymbol{Q}}{\mathit{\boldsymbol{M}}^T}。$

(3)

通过式(4)可以计算用户u对未知地点l的分值Score，其中，P_u是根据公式(2)更新得到的用户u的特征向量，H_l是由公式(3)得到的地点l的特征向量。最后对所有分数进行排序，即可为用户推荐Top-K个兴趣点。

$ {\rm{Scor}}{{\rm{e}}_{{\rm{ul}}}} = {\mathit{\boldsymbol{P}}_u}^{\rm{T}}{\mathit{\boldsymbol{H}}_l}。$

(4)

2.3 社会正则化研究

目前大多数有关兴趣点推荐的研究都是直接根据相似度来考虑朋友之间的社交关系。而文中已经阐明了朋友之间对于相同地点的偏好其实存在较大的差异^[16]。因此，传统的推荐系统依靠朋友间的相似性或者直接从朋友处获取地点就变得非常不合适^{[5, 15, 31]}。

地点类别是对地点功能和语义的提炼，能够反映用户的个人倾向。Yelp数据集充分表明了用户间共同签到类别的比例远远超过共同签到地点。因此，从该角度出发，提出使用社会正则化对这种差异性建模^[31]：

$ \frac{{{\lambda _3}}}{2}\sum\limits_{i = 1}^{\left| U \right|} {\sum\limits_{oF + \left( i \right)} {{\rm{Sim}}\left( {\mathit{\boldsymbol{i}}, \mathit{\boldsymbol{o}}} \right)} } {\left\| {{\mathit{\boldsymbol{P}}_i} - {\mathit{\boldsymbol{P}}_o}} \right\|_{\mathop F\limits^2 }}, $

(5)

式中：λ₃是权衡社会正则化作用的权重参数；F⁺(i)为用户i在社交网络中主动关注的朋友列表；Sim(i, o)计算用户i和用户o在位置类别上的偏好相似性。相似度的计算方式有很多种，较为传统的是余弦相似度，而文中采用的是杰卡德系数，为

$ {\rm{Sim}}\left( {i, o} \right) = \frac{{\left| {{C_i} \cap {C_o}} \right|}}{{\left| {{C_i} \cup {C_o}} \right|}}。$

(6)

式中，C_i是用户i访问过的全体类别，式(4)主要反映的是2个用户在位置类别上的匹配程度。在目前的推荐系统研究进展中，社会正则化已经得到了很多研究者的认可和使用，它缓解了协同过滤的数据稀疏难题，对推荐的质量有一定的保障。

2.4 结合地点类别和社交网络的兴趣点推荐算法

基于2.2节和2.3节阐述的内容，提出了一种将地点类别和社交网络进行结合的兴趣点推荐算法CSRS(category and social network based recommendation system)，在图 2中展示了其整体的框架。一方面用户类别矩阵相对于用户地点矩阵能够缓解稀疏性；另一方面，利用社会正则化对社交关系中类别偏好差异进行约束可以使得该算法更贴近现实。式(2)是梯度下降更新参数的损失，式(5)是引入社会化关系的损失，CSRS算法的总损失(最终的目标函数)如式(7)所示，其中所有的参数在之前的小节中已经进行了阐述。

同样对目标函数采用随机梯度下降法求解P和Q，式(8)和式(9)为求导公式。其中，F^-(i)为主动关注用户i的朋友集合。求得P和Q之后就可以结合式(3)和式(4)来计算用户u对未知地点l的最终分值，最后对所有地点的分数按从高到低进行排序，选取Top-K个兴趣点作为推荐结果。

$ \begin{array}{*{20}{l}} {\mathit{\Gamma } = \frac{1}{2}\sum\limits_{i = 1}^{\left| U \right|} {\sum\limits_{j = 1}^{\left| {{C_a}} \right|} {{{\bf{I}}_{ij}}{{\left( {{{\bf{R}}_{ij}} - {\bf{P}}_i^{\rm{T}}{{\bf{Q}}_j}} \right)}^2} + \frac{{{\lambda _1}}}{2}{{\left\| {{{\bf{P}}_i}} \right\|}_{\mathop F\limits^2 }}} } }\\ { + \frac{{{\lambda _2}}}{2}{{\left\| {{{\bf{Q}}_j}} \right\|}_{\mathop F\limits^2 }} + \frac{{{\lambda _3}}}{2}\sum\limits_{i = 1}^{\left| U \right|} {\sum\limits_{o \in F + \left( i \right)} {{\rm{Sim}}\left( {i,o} \right){{\left\| {{{\bf{P}}_i} - {{\bf{P}}_o}} \right\|}_{\mathop F\limits^2 }}} } ,} \end{array} $

(7)

$ \begin{array}{l} \frac{{\partial \mathit{\Gamma }}}{{\partial {\mathit{\boldsymbol{P}}_i}}} = \sum\limits_{j = 1}^{\left| {{C_a}} \right|} {{\mathit{\boldsymbol{I}}_{ij}}\left( {\mathit{\boldsymbol{P}}_i^{\rm{T}}{\mathit{\boldsymbol{Q}}_j} - {\mathit{\boldsymbol{R}}_{ij}}} \right){\mathit{\boldsymbol{Q}}_j} + {\lambda _1}{\mathit{\boldsymbol{P}}_i} + {\lambda _3}\sum\limits_{o \in F + \left( i \right)} {Sim\left( {i, o} \right)\left( {{\mathit{\boldsymbol{P}}_i} - {\mathit{\boldsymbol{P}}_o}} \right)} } \\ {\lambda _3}\sum\limits_{g \in F - \left( i \right)} {{\rm{Sim}}\left( {i, g} \right)\left( {{\mathit{\boldsymbol{P}}_i} - {\mathit{\boldsymbol{P}}_g}} \right)} , \end{array} $

(8)

$ \frac{{\partial \mathit{\Gamma }}}{{\partial {Q_j}}} = \sum\limits_{i = 1}^{\left| U \right|} {{\mathit{\boldsymbol{I}}_{ij}}\left( {\mathit{\boldsymbol{P}}_i^{\rm{T}}{\mathit{\boldsymbol{Q}}_j} - {\mathit{\boldsymbol{R}}_{ij}}} \right){\mathit{\boldsymbol{P}}_j} + {\lambda _1}{\mathit{\boldsymbol{Q}}_j}。} $

(9)

3 实验及结果 3.1 数据集

Yelp是一个面向大众、主流热门的在线社交应用。用户在Yelp应用里可以进行地点的签到并发表评论。Yelp已经发布了很多开源数据集供研究者使用，因此，笔者选择Yelp的数据集来进行实验。该数据集包含用户的社交关系、签到评分、地点经纬度、签到时间等。由于原数据过于庞大，为了验证文中提出算法的有效性，在预处理数据时，首先选择社交关系最为广泛的用户，以该用户为起点，在整个数据集上进行深度遍历，就得到了研究所需要的用户集合，这些用户的签到记录即作为我们实验所使用的签到数据。最终的数据集包括7 933个用户，18 995个地点，624个类别。用于训练集的签到数量是517 516，而用于测试集的签到数量是171 396。

3.2 评价指标

在推荐系统中，常用的评价指标有准确率(P_Pre@K)和召回率(R_Rec@K)，它们也是机器学习领域中最为常见的指标。准确率是指为用户产生的推荐列表中，被正确推荐的地点所占的比例。而召回率是指在用户的测试集中，被正确推荐的地点所占的比例。这2种指标具体的计算公式为

$ {P_{{\rm{Pre}}@{\rm{K}}}} = \frac{1}{{\left| {{U_{{\rm{test}}}}} \right|}}\sum\limits_{u \in {U_{{\rm{test}}}}} {\frac{{\left| {L_u^{{\rm{rec}}} \cap L_u^{{\rm{test}}}} \right|}}{K}} , $

(10)

$ {P_{{\rm{Rec}}@{\rm{K}}}} = \frac{1}{{\left| {{U_{{\rm{test}}}}} \right|}}\sum\limits_{u \in {U_{{\rm{test}}}}} {\frac{{\left| {L_u^{{\rm{rec}}} \cap L_u^{{\rm{test}}}} \right|}}{{\left| {L_u^{{\rm{test}}}} \right|}}} , $

(11)

式中，U_test代表测试集用户集合。L_urec是算法为用户产生的推荐列表，而L_utest是用户u在测试集中的地点集合(即需要预测的真实地点)。实验中K值参照多数算法取10、20、50。

3.3 实验结果对比分析

文中所提出的算法充分结合了地点类别和社交关系，旨在改进传统经典的推荐模型，因此，研究选取的对比算法有下列几种：

1) UserCF算法：热门且经典的基于用户的协同过滤算法，根据用户地点矩阵来计算用户之间的相似性从而完成对目标用户的推荐。

2) UC算法：基于地点类别的推荐算法，没有考虑社会化关系，其核心公式可以根据文中关于地点类别分数的求解过程中得到。

3) Basic MF算法：基于矩阵分解技术的推荐算法，通过分解原始的用户地点矩阵来对其进行填充以寻找潜在的未知地点。

文中提出的算法是以层层递进的方式结合类别与社交关系以求得用户的偏好，最后基于协同过滤进行推荐，所以不存在需要调整的参数。相似用户的个数根据绝大多数论文的经验而设置，由于目前基础的协同过滤已经相当成熟，因此该数值不是文中考察的重点。

图 3与图 4展示了准确率和召回率的实验结果，当推荐列表的长度分别为10、20、50时，文中提出的CSRS算法在2种评价指标下都优于其他的推荐算法，这充分说明考虑地点类别和社交关系有利于提升推荐效果。值得一提的是，UC算法代表了CSRS算法的中间过程，即在地点类别影响下的推荐结果。但相比Basic MF算法和UserCF算法，其准确率和召回率仍具有明显优势，这也体现了地点类别的重要性。

然而，UC算法没有结合社交关系，当推荐个数为10时，文中提出的结合类别与社交关系的CSRS算法远超过UC算法。但随着推荐个数的增加，这种差距逐渐缩小，这表明社交关系的提升作用有限。无论是在准确率还是召回率方面，UserCF的效果都是最差的，笔者分析这可能是由于数据稀疏造成的。直接构建用户地点矩阵会使得该矩阵相当稀疏，因此在计算用户相似度时存在明显缺陷，导致最终的推荐效果不佳。

4 结论

兴趣点推荐是推荐系统中极为重要的一个子领域。文章首先总结了已有的关于兴趣点推荐的研究工作，然后提出了一种基于地点类别和社交关系的推荐算法CSRS。地点类别与地点本身相比，不仅更能反映用户的倾向，而且在构建矩阵时也能有效地缓解稀疏性。同时，Yelp数据集表明朋友之间访问相同类别的比例远高于访问相同地点。因此，CSRS算法适合运用于兴趣点推荐的研究中。最后与目前主流经典的推荐算法进行了对比，其实验结果充分证明了CSRS算法的优势和有效性。

文中提出的推荐算法主要研究了地点类别和社交关系。在以后的工作中，笔者会将其他一些因素如流行度、时间规律等加入到算法中，以进一步提升推荐效果。