0 引言

基于位置的社交网络(location-based social network，LBSN)^[1]是基于位置服务与社交网络的结合体，在LBSN中，用户可以使用移动设备对地点进行签到、公开地理位置、记录在该位置的体验。此外，用户可以看朋友的位置，并对朋友的签到地点进行评论。在收集了大量的用户信息、朋友信息、位置信息后，基于这些数据可以开发好友推荐^[2]、专家发现^[3-4]、活动推荐^[5]、流行路径推荐^[6-7]等应用，从而让商家的服务更加个性化。在众多基于位置社交网络的应用中，个性化位置推荐是其中一个重要的组成部分。

LBSN中地点推荐已经受到了不少研究者的关注。文献^[8]综合利用了基于用户的协同过滤(user-based CF)和地理影响力，给用户推荐感兴趣的位置。文献^[9]在推荐时挖掘了个人兴趣和位置的受欢迎程度。文献^[10]提出了基于评分的位置推荐模型和基于主题的位置推荐模型，基于评分的位置推荐模型提出一种新的签到评分方法——贡献度评分，将协同过滤技术引入到位置推荐中；基于主题的位置推荐模型将文本聚类中的主题模型引入到位置主题中，并对用户签到序列进行主题建模，得出用户的历史签到在主题下的分布和位置在主题下的分布，进而进行主题位置的发现。文献^[11]提出了基于位置流行度的地点推荐模型，在用户对推荐结果的选择上，多数用户更倾向于选择流行度高的位置。文献^[12]研究了基于社交影响的协同过滤算法。

本文提出一种综合考虑用户偏好、朋友关系、位置语义因素的地点推荐方法，从兴趣地点相似度、好友亲密度考察用户间的相似关联，从位置的语义相似度考察地点间的关联性。解决地点推荐时数据稀疏^[13]以及冷启动^[14]问题。

1 基于朋友关系的协同过滤推荐

在进行个性化地点推荐时，基于用户的协同过滤算法对冷启动问题没有很好的解决方案。为了解决这个问题，将社交网络中的朋友关系引入到其中。通过社交网络中朋友这一因素，计算新用户和朋友之间的相似度，把朋友去过的地点推荐给新进入系统的用户，从而解决冷启动问题。在这一推荐中涉及到计算用户间的相似性，分别用兴趣地点相似度以及好友亲密度2个指标考察，将2个相似度利用权重混合后，计算用户对候选地点的兴趣度，最后进行推荐。

1.1 用户间相似度 1.1.1 兴趣地点相似度

利用余弦相似度进行计算,用户u_i、u_j的兴趣地点相似度

${{r}_{ij}}=\frac{\sum\limits_{{{l}_{k}}\in L}{{{s}_{ik}}{{s}_{jk}}}}{\sqrt{\sum\limits_{{{l}_{k}}\in L}{s_{_{ik}}^{^{2}}}}\sqrt{\sum\limits_{{{l}_{k}}\in L}{s_{_{jk}}^{^{2}}}}},$

(1)

式中：s_ik为用户u_i是否在地点k签到，签到取值为1，没签到取值为0；s_jk为用户u_j是否在地点k签到，签到取值为1，没签到取值为0；L为所有地点的集合；l_k为属于L集合的某一地点。

1.1.2 好友亲密度

朋友关系因素是好友间亲密程度的度量。通常用户间的朋友关系亲密程度可以通过他们是不是好友来决定，但这并不起决定性作用，因为在社交网络中用户并不是与他的所有好友都有相似的兴趣爱好，对地点的签到行为也具有差异性。本文在计算用户间的亲密程度时，通过他们是否为好友和他们的共同好友比例计算所得。计算方法为：

${{p}_{ij}}=\varepsilon {{f}_{ij}}+\left( 1-\varepsilon \right)\frac{{{F}_{i}}\cap {{F}_{j}}}{{{F}_{i}}\cup {{F}_{j}}},$

(2)

式中：p_ij为朋友关系因素，表示用户u_i与用户u_j之间的亲密度，p_ij越高则朋友之间关系的亲密度越高，反之，亲密程越低；ε为一个可调节的参数，用来调节权重； f_ij表示用户u_i与用户u_j是否为好友关系，f_ij=1是好友，f_ij=0不是好友;F_i为用户u_i的好友数据集；$\frac{\left| {{F}_{i}}\cap {{F}_{j}} \right|}{\left| {{F}_{i}}\cup {{F}_{j}} \right|}$表示用户u_i与用户u_j共同好友的数量占两个用户所有好友数量的比例，即共同好友比例。

1.1.3 混合相似度

用户间的兴趣地点相似度与好友亲密度相混合的混合相似度

${{d}_{ij}}=\delta {{r}_{ij}}+\left( 1-\delta \right){{p}_{ij}},$

(3)

式中：δ为一个可调节参数，取值范围为[0, 1]，使用δ参数调节用户间的兴趣地点相似度和朋友关系因素的权重，使其平衡。δ值越大时推荐效果越好，则表示社交中好友亲密程度比用户间的兴趣地点相似度的影响更大； 如果δ值越小推荐效果越好，则表示用户间的兴趣地点相似度的影响更大。文献^[15]通过试验得出参数δ的最佳取值，当离用户当前位置的距离小于100km，δ的最优取值为0.1；当离用户当前位置的距离大于100km，δ的最优取值为0.9。

计算出用户间的兴趣地点相似度与好友亲密度相混合的相似度d_ij后，选取top-N个d_ij值最高的用户组成用户集U′，其中u_j属于用户集合U′。利用混合相似度，计算用户u_i对没去过的地方l_k的兴趣度

${{w}_{ik}}=\frac{\sum\limits_{{{u}_{j}}\in U\prime }{{{d}_{ij}}{{s}_{jk}}}}{\sum\limits_{{{u}_{j}}\in U\prime }{{{d}_{ij}}}}。$

(4)

将兴趣度排序，选取候选地点中兴趣度高的地点推荐给用户。

2 改进的地点推荐

基于朋友关系的协同过滤推荐虽然对冷启动问题有很好的解决方案，但对数据稀疏问题却是无效的，引入聚类算法能在一定程度上解决这个问题。考虑位置的语义特征，利用聚类算法K-medoids对地点进行分类重组，形成地点组，从而解决数据稀疏问题。将两个算法集成，取两者优势进行互补，提出改进的地点推荐算法，从而解决数据稀疏和冷启动问题。

2.1 地点的语义相似度

在日常生活中，地点有相似性，不能把在语义上不同的地点完全判定为不同的两个地点。在计算地点的语义相似度时，引入了地点标签概念，并且运用词频-逆文档频率(term frequency-inverse document frequency，TF-IDF)这个统计方法。具体步骤如下：

首先，需要对标签中的文本进行预处理，清理各种停用词、乱码等。

然后，将预处理完成的文本用n维向量空间模型(vector space model)表示，文本中的每个关键词用一个维度表示，各个维度的权值则与对应关键词在地点库中出现的频率相关。

计算词频方法为：

$t{{f}_{kv}}=\frac{{{z}_{kv}}}{\sum\limits_{n\in {{d}_{k}}}{{{z}_{kn}}}},$

式中：tf_kv是词v在地点k的标签中所占比例；Z_kv是词v在地点k的标签集合d_k中出现的次数；$\sum\limits_{N\in {{d}_{k}}}{{{z}_{kn}}}$是地点k的标签集合d_k中所有词出现的总次数之和。

计算逆文档频率的方法为：

$id{{f}_{v}}=log\frac{\left| D \right|}{\left| \{d \right|\text{ }{{t}_{v}}\in d,d\in D\}|+1},$

式中：idf_v为词v在地点库中的逆文档频率，最常见的词如“的”“是”“中国”，虽然出现频率较高，但意义不大，所以赋予较小的权重，而一些重要性较高的词，如地点词汇，应赋予较高的权重，这个权重称为逆文档频率，一个词越常见，分母越大，逆文档频率就越小；D为地点库；|D|是地点总数；|{d|t_v∈d，d∈D}|表示在地点库中包含词v的地点数目。分母之所以要加1，是为了避免分母为0(即所有文档都不包含该词)。

每个地点标签中的每个词的综合权重

$tfid{{f}_{kv}}=t{{f}_{kv}}\times id{{f}_{v}},$

每个地点的标签文本中，地点的语义信息向量

$Tag{{s}_{k}}=\left( tfid{{f}_{k1}},tfid{{f}_{k2}}\cdots ,tfid{{f}_{kn}} \right),n=\left| t \right|,$

式中：|t|为地点标签中词的总数量；Tags_k为地点k标签中的每个词的综合权值组成的向量。

地点与地点之间的语义相似度为2个向量的余弦相似度,语义相似度

$Simi(Tag{{s}_{k}},Tag{{s}_{j}})=\frac{\sum\limits_{v=1}^{n}{tfid{{f}_{kv}}\times tfid{{f}_{jv}}}}{\sqrt{\sum\limits_{v=1}^{n}{tfidf_{_{kv}}^{2}}}\times \sqrt{\sum\limits_{v=1}^{n}{tfidf_{_{jv}}^{^{2}}}}}。$

2.2 改进的地点推荐算法

改进算法的具体流程如图 1所示。

改进的地点推荐算法过程需要7个步骤。

(1) 使用聚类算法k-medoids对所有地点进行相似性聚类

$Similarity\left( {{p}_{k}},{{p}_{j}} \right)=Simi\left( Tag{{s}_{k}},Tag{{s}_{j}} \right),$

式中：Similarity(p_k，p_j)是地点k和j的语义相似度。

(2) 将每个用户对地点的签到向量转化为对地点组的签到向量

${{\overrightarrow{U}}_{l}}\prime ={{\overrightarrow{U}}_{l}}\times \left( \begin{matrix} {{a}_{11}} & \cdots & {{a}_{1n}} \\ \vdots & {{a}_{kg}} & \vdots \\ {{a}_{m1}} & \cdots & {{a}_{mn}} \\ \end{matrix} \right),$

(5)

式中：${{a}_{kg}}=\left\{ \begin{align} & 1,地点k属于地点组g, \\ & 0,地点k不属于地点组g; \\ \end{align} \right.$${{{\vec{U}}}_{l}}\prime $为用户i对签到地点组的签到情况向量，1表示签到了该地点组，0表示没有签到该地点组；${{{\vec{U}}}_{l}}$为用户i对签到地点的签到情况向量，1表示签到了该地点，0表示没有签到该地点。

(3) 计算目标推荐用户与其余用户间的兴趣地点组相似度r′_ij

利用式(5)得到所有用户在地点组空间上的向量后，由式(1)，将目标推荐用户与其余用户之间对地点的兴趣相似度改为对地点组的兴趣相似度

$r{{\prime }_{ij}}=\frac{\sum\limits_{{{g}_{k}}\in G}{{{s}_{i{{g}_{k}}}}{{s}_{j{{g}_{k}}}}}}{\sqrt{\sum\limits_{{{g}_{k}}\in G}{s_{_{i{{g}_{k}}}}^{^{2}}}\sum\limits_{{{g}_{k}}\in G}{s_{j{{g}_{k}}}^{2}}}},$

式中：g_k为通过步骤(2)后聚类的某个地点组；s_igk为用户u_i是否在地点组g_k签到,签到取为1，没有签到取为0；s_jgk为用户u_j是否在地点组g_k签到，签到取为1，没有签到取为0。

(4) 计算目标推荐用户与其好友亲密度p_ij

由式(2)计算好友亲密度。

(5) 计算混合相似度

利用一个线性的融合框架集成，将步骤(3)的用户间的兴趣地点组相似度与步骤(4)的好友亲密度相集成，由式(3)，可得混合相似度

$d_{_{ij}}^{\prime }=\delta *r_{_{ij}}^{\prime }+\left( 1-\delta \right)*{{p}_{ij}},$

展开后

$d_{_{ij}}^{\prime }=\delta *\frac{\sum\limits_{{{g}_{k}}\in G}{{{s}_{i{{g}_{k}}}}{{s}_{j{{g}_{k}}}}}}{\sqrt{\sum\limits_{{{g}_{k}}\in G}{s_{_{i{{g}_{k}}}}^{2}}}\sqrt{\sum\limits_{{{g}_{k}}\in G}{s_{_{j{{g}_{k}}}}^{2}}}}+\left( 1-\delta \right)[\varepsilon *{{f}_{ij}}+\left( 1-\varepsilon \right)*\frac{\left| {{F}_{i}}\cap {{F}_{j}} \right|}{\left| {{F}_{i}}\cup {{F}_{j}} \right|}。$

(6) 计算目标推荐用户对候选地点组兴趣度w_igk

计算出混合相似度d′_ij后，选取top-N个d′_ij值最高的用户，组成用户集U′，其中u_j属于用户集合U′。利用步骤(5)计算的混合相似度，对目标推荐用户没去过的地方g_k，计算用户u_i对地点组g_k的感兴趣程度，用w_igk表示。由式(4)，将目标推荐用户对地点的混合相似度改为对地点组的混合相似度，将用户对地点是否进行签到改为对地点组是否进行签到。w_igk计算式为：

${{w}_{ig}}_{k}=\text{ }\frac{\sum\limits_{{{u}_{j}}\in U\prime }{d_{_{ij}}^{\prime }{{s}_{j{{g}_{k}}}}}}{\sum\limits_{{{u}_{j}}\in U\prime }{d_{_{ij}}^{\prime }}}。$

(7) 取出兴趣度最高的一些地点作为推荐结果

对兴趣度w_igk按降序进行排列，选取最前面的结果优先推荐给用户u_i。

3 试验验证与结果分析 3.1 试验数据集

通过调用 Twitter 的开放 API，抓取Foursquare 签到数据，从而构成开始的签到数据集，其中用户7360名，签到地点60591个，签到记录363124条。 签到数据集中包含的数据格式如表 1所示。

表 1中，Checkin表示用户签到的日志记录，其中UserID表示用户在 Twitter 上的 ID 号，CheckinID表示用户发布的签到信息的 ID 号，VenueInfo表示位置信息，Longitude和Latitude分别表示用户签到位置的经度和纬度，Time表示用户发布该信息的时间；Category表示地点的类别信息；Tag表示地点的标签信息，其中Description表示对地点的描述；Friend list表示用户的朋友关系数据，其中FriendID表示用户好友的ID号，FriendNum表示用户的好友数量。

本文釆用金标准(Ground Truth)评估，首先从抓取的数据集中划分出训练数据集和测试数据集两个部分，这里采用80/20这个公认的分界点划分，即将每个用户签到地点的前80%作为训练集，后20%作为与推荐地点对比的标准。

在试验中，有2个可调节参数。在好友亲密度中，是否是好友对于推荐用户的影响大于潜在好友的影响，故将ε设为0.7。

3.2 推荐效果评测方法

本文采用准确率(Precision rate)、召回率(Recall rate)、单个主题的平均准确率 (mean average precision，mAP)作为评测方法，准确率为系统检索到的相关信息与系统所有检索到的信息总数之比，召回率为系统检索到的相关信息与系统所有相关的信息总数之比，单个主题的平均准确率

$mAP=\int _{0}^{1}P\left( R \right)dR,$

式中:P，R分别为准确率与召回率。mAP同时考虑了准确率和召回率。

3.3 聚类算法对推荐效果的影响

将改进的推荐方法(C)与基于地点的协同过滤(ICF)方法、基于地点标签语义的协同过滤 (WCF) 方法进行对比，结果如图 2所示。

由图 2可知：与ICF方法相比，C方法在各个方面都表现的更好，当推荐数目较少时，C在准确率以及mAP的效果更理想，而当推荐数目较多时，C在召回率上的优势更为明显。与WCF方法相比，无论推荐数目是何种情况，C方法的推荐效果都提高了一倍左右。此试验证明在位置社交网络中地点推荐时，对地点按照语义进行聚类可以增强推荐效果。

3.4 改进算法对数据稀疏影响

数据稀疏是影响地点推荐效果的主要问题。将抓取的用户签到数据分别去掉10%、30%、50%的签到记录，从而创造了3种不同的稀疏度。将地点推荐数目定为10个，将推荐地点离用户当前位置距离定为5km。

如图 3所示，将在数据稀疏情况下计算出的算法的平均准确率，与在标准情况下计算出的算法的平均准确率结果进行比较，计算出两种情况下准确率降低的比例。图 3中U为基于用户的协同过滤算法，F为基于朋友关系的协同过滤算法，C为改进的算法。

由图 3可知：算法U的准确率下降最多，算法C下降最少。与算法F相比，算法C的准确率下降更少，说明与协同过滤相比，聚类能更好的解决数据稀疏问题。

4 结语

本文针对基于位置的社交网络中地点推荐时面临的数据稀疏和冷启动问题，提出解决方案。利用朋友关系协同过滤推荐解决冷启动问题。再与聚类算法集成，利用其优势，从而解决数据稀疏问题。本文的重点在于相似度的计算，对于用户间相似度采用兴趣地点相似度、好友亲密度。对于地点间相似度采用地点语义相似度进行聚类。通过试验分析，改进的算法可以有效提高推荐效果，提高推荐质量。