随着智能手机的爆炸式发展, 用户可随时随地在各大社交平台分享自己的地理位置信息. 无论是视频、图片或文本信息, 都可轻易地嵌入当前用户的地理位置标签(Location Tag). 大量的位置Tag构成了基于地理位置的社交网络^[1](Location-Based Social Networks, LBSN), 结合现有的各种定位系统, 可以为用户提供一些个性化服务. 根据LSBN中已经存在的链接和节点信息, 可以预测出用户位置网络中遗失的Tag或即将出现的Tag链接, 该方法称之为链接预测^[2]. 例如, 在微博、微信等社交平台中, 用户等同于节点, 链接预测可用于建立新的好友关系.

文献[3]表明, 同一时间出现在同一位置的用户成为好友的概率要远高于处于不同地理位置的用户. 因此, 挖掘LBSN中潜在的标签信息对实现链接预测具有重大意义. 目前, 国内外已有很多科研工作者专注于基于地理位置标签的推荐算法研究, 判断用户地理位置的途径主要有两种: 第一, 挖掘用户发布到互联网中的内容信息可推断出用户的地理位置信息^[4]. 第二, 通过社交平台中好友的地理位置推测用户的位置^[5]. 近年来也有很多学者研究基于LDA主题建模的层次聚类^[6]、无监督学习^[7]、标签关联^[8]推荐算法. 为提高位置预测的准确性, 可对用户位置信息进行筛选, 过滤掉无用的信息. 还可对用户签到信息建立LDA主题生成模型, 分析地理位置标签的特征, 设计出基于地理位置的推荐系统^[9].

从用户签到信息中提取出时间特征和位置特征对于链接预测算法至关重要, 因为这些特征可用于评估用户之间的相似度, 进而提高预测的准确度. 然而实际的LBSN签到信息中, 地理位置的分布十分稀疏, 想要挖掘出位置和时间信息相当困难. 基于用户地理位置标签, 本文建立了新的LBSN链接预测模型, 提高了链接预测的准确度. 首先, 本文对Gowalla数据集进行聚类分析, 改善了地理位置分布的稀疏性问题. 其次, 本文对用户地理位置标签进行语义分析, 建立基于用户地理标签的LDA主题模型, 采用Gibbs抽样算法进行参数估算, 分析出用户的地理位置标签的相似性特征. 最后, 本文综合网络结构相似性特征和基于用户地理位置信息的相似度特征, 采用有监督策略的链接预测在Gowalla数据集上进行实验. 实验结果表明, 本文提出的模型能有效提高LBSN的链接预测准确度.

1 基于地理位置的LDA主题模型

本文对LBSN中的用户地理位置标签建立LDA主题模型, 以便挖掘出用户的行为偏好. 用户的位置标签集合可当作一篇文档, 位置标签集合中的某条具体位置相当于构成文档的词汇. 对该主题模型进行求解, 可得出用户地理位置标签中隐藏的主题分布和地理标签主题下的位置分布.

假定用户 $u$ 对应的地理位置标签集合为 ${\vec D_u} = {[{w_{u,1}},{w_{u,2}}, \cdots ,{w_{u,m}}]^{\rm{T}}}$ , ${\vec D_u}$ 相当于一篇文档, 其中 $m$ 代表用户 $u$ 的位置标签条数, ${w_{u,i}}$ 代表用户 $u$ 的第 $i(1 \leqslant i \leqslant m)$ 条位置标签信息, 相当于构成文档 ${\vec D_u}$ 的某个词汇. 地理位置文档集合为 $D = {[{\vec D_1},{\vec D_2}, \cdots ,{\vec D_M}]^{\rm{T}}}$ , 其中M代表用户数量. 假定具体的位置数量为 $V$ , 则可建立基于地理位置的LDA主题模型, 如图1所示.

模型中的位置主题概率分布可用Gibbs^[10]采样算法估算得出, 该分布可用一个doc-topic矩阵 $\Theta {\rm{ = [}}{\vec \theta _1}{\rm{,}}\cdots{\rm{,}}{\vec \theta _M}{{\rm{]}}^{\rm{T}}}$ 来描述, 用户 $u$ 在地点主题 ${t_k}$ 下出现的概率分布可表示为 ${\vec \theta _u} = {[{p_u}\left({{t_1}} \right), \cdots, {p_u}\left({{t_K}} \right)]_u} = [{p_u}\left({{t_1}} \right),\cdots,$ $ {p_u}\left({{t_K}} \right)] $ . 同理, 每个位置主题下对应的位置概率分布可用一个topic-word矩阵 ${\vec \varphi _k}{\rm{ = [}}{{{p}}_k}\left({{\varphi _1}} \right){\rm{,}}{{{p}}_k}\left({{\varphi _2}} \right){\rm{,}} \cdots, $ $ {{\rm{p}}_k}\left({{\varphi _V}} \right){\rm{]}}$ 来描述, 其中 ${{\rm{p}}_k}\left({{\varphi _v}} \right)$ 代表位置 $v$ 在主题 $k$ 下出现的概率.

2 基于位置信息的相似度分析 2.1 位置信息语义化

本文实验使用的数据集是Gowalla的地理位置标签数据集, 可从SNAP官网直接下载得到, 用户地理位置标签的存储格式为:

$\begin{aligned}Checki{n_{i,j}} = &\left\{ {user\;ID,\;latitude,\;longitude,} \right.\\& \left. {timestamp,\;location\;ID} \right\}\end{aligned}$

$Checki{n_{i,j}}$ 表示用户 $i$ 的第 $j$ 条位置信息. 此外, 该数据集还记录了用户之间的好友关系. 具体示例见表1和表2.

由于数据集并没有具体的地理语义信息, 故需要先对其进行语义化. 本文采用百度公司免费的Place API和Geocoding API进行语义转换, 可将数据集中的地理坐标转换为具体的地址以及附近的POI (Point Of Interest)信息.

由于很多用户只在某一个地点签到过, 或跟其他用户没有共同的签到地点, 这类用户称之为孤点用户. 大量的孤点用户造成了数据的稀疏性, 严重影响链接预测的准确性. 为解决该问题, 本文降低了具体地点的限制, 对地点标签进行层次聚类, 以签到区域来构建用户关系网络. 设定一个距离阈值 $\delta $ , 若不同签到地点的距离不超过该值, 则认为两个地点属于一个区域, 本文在实验章节会对该参数进行调优试验. 然后利用该距离阈值对签到数据集进行聚类, 可得到区域集合 $D = \left\{ {{d_1},{d_2}, \cdots, {d_n}} \right\}$ , 由此可得到区域矩阵:

$CH = \left[ \begin{array}{c}{d_{1,1}}, \cdots ,{d_{1,n}}\\{d_{2,1}}, \cdots ,{d_{2,n}}\\ \vdots \;\;\;\;\vdots \;\;\;\; \vdots \\{d_{m,1}}, \cdots ,{d_{m,n}}\end{array} \right]$

(1)

式(1)中的 ${d_{i,j}}$ 代表第i个用户在区域j处的签到. 显然, 利用区域矩阵来构建用户网络关系可极大地减小孤点用户的数量, 对签到地点标签信息的挖掘也更充分, 因此可降低数据稀疏性的影响.

2.2 基于位置信息的相似度分析

上文提到, 采用Gibbs采样算法可估算出LDA主题模型中的两个概率分布: 位置主题分布 $\Theta $ 和所有主题下的地理位置分布 $\Psi $ . 每个用户的签到主题分布可以表示成K个位置主题的概率组合, 所有用户的签到主题分布构成矩阵 $\Theta $ . 每个主题下的位置分布可以表示为签到位置的概率组合, 所有主题下的签到位置分布构成矩阵 $\Psi $ . 利用本文的签到语义数据集, Gibbs采样可输出矩阵 $\Theta $ 和 $\Psi $ .

本文首先筛选出位置主题概率最大的K个主题来表达用户的位置主题. K的取值可按照经验预设, 剩下的主题概率可先置0. 本文先设定K=5, 在模型学习的过程中会对K值进行不断的修正. 然后对这K个地理位置主题分布函数进行归一化处理, 如公式(2)所示:

${p'_u}\left({{t_k}} \right) = \frac{{{p_u}\left({{t_k}} \right)}}{{\sum\nolimits_{k \in Top - K} {{p_u}\left({{t_k}} \right)} }}$

(2)

其中, ${p'_u}\left({{t_k}} \right)$ 代表归一化的结果, 即用户 $u$ 的地理位置出现在主题 $k$ 下的概率, ${p_u}\left({{t_k}} \right)$ 代表归一化之前的概率分布函数. 因此能够得到全新的概率分布矩阵 $\Theta '$ 和 $\Psi '$ .

对于两个不同用户产生的概率分布函数, 需要计算出二者之间的距离. 统计学中的KL 散度(KL-Divergence)可用于测量不同概率分布的差异, 被广泛应用于基于LDA的推荐算法. 然而KL散度并不适用于本文基于地理位置标签的链接预测算法, 因为该方法具备非对称性特征. 如果两个用户对某主题都无兴趣, KL散度得出的结论是这两个用户具有很高的相似性. 同理, 如果两个用户都没有在某个地点签到, 那么KL散度会认为他们具有很高的相似度, 这显然会造成极大的误差. 因此, 本文采用一种新的方法来评估用户之间地理位置主题的差异性. 用户i在 $k$ 个地理位置主题下的位置总数设为 $N\left({i,{t_k}} \right)$ , 则不同用户 $x,y$ 之间的相似度可用公式(3)计算得到:

${f_W}\left({x,y} \right) = \frac{{\sum\limits_{k \in Top - K} {\min \left({N\left({x,{t_k}} \right),N\left({y,{t_k}} \right)} \right)} }}{{\sqrt {\sum\limits_{k \in Top - K} {N\left({x,{t_k}} \right)} } \cdot \sqrt {\sum\limits_{k \in Top - K} {N\left({y,{t_k}} \right)} } }}$

(3)

其中, 分子代表用户x和y在k个主题下的位置总数最小值之和, 该值越大, 说明用户x和y在同一区域签到的数量越大, 二者的相似度越高. 式(3)进行了归一化处理, 最终结果可用于计算用户之间的相似度.

最后, 为了验证 ${f_W}\left({x,y} \right)$ 的有效性, 基于从当前数据集中获取的网络关系, 本文将对比分析 ${f'_P}\left({x,y} \right)$ 和 ${f_W}\left({x,y} \right)$ 的性能. LBSN链接网络中基于 ${f_W}\left({x,y} \right)$ 的好友用户对与非好友用户对的累积分布图(CDF)如图2所示.

从图2可看出, 基于位置标签语义分析的用户相似性特征 ${f_W}\left({x,y} \right)$ 能够有效地识别好友与非好友的区别. 因此可得出结论, ${f_W}\left({x,y} \right)$ 对于分析用户之间的链接预测具有重要意义.

3 基于地理标签的LBSN链接预测模型 3.1 实现方法

本文通过对用户地理位置信息的充分挖掘, 得出了基于地理位置语义分析的相似性特征. 这是本文所提出的链接预测模型的基础. 机器学习中的监督式学习算法经常被用于推荐系统的设计, 将收集到的海量训练数据集作为先验知识, 建立一个模型, 并根据输入的标签不断修正该模型, 最终该模型可针对新的输入预测出相应结果. 本文的链接预测算法基于有监督学习的思想, 输入为Gowalla数据集中的位置标签, 建立用户特征向量函数, 对其进行模型训练, 最终可用于链接预测.

接下来, 本文将采用有监督学习的策略对其进行链接预测. 实验中, LBSN链接预测采用Gowalla数据集进行仿真, 使用LBSN基于地理位置语义分析的相似性特征进行辅助实验. 本文实施的链接预测实验步骤如下:

(1)筛选原始数据集, 过滤掉其中无用的冗余信息和独立用户(即无任何好友关系的用户), 最总得到一个可用的LBSN社交关系网络图 $G = \left({V,E} \right)$ .

(2)对集合 $E$ 进行随机采样, 其中2/3的数据作为训练集 ${E^T}$ , 余下1/3的链接数据作为测试数据集 ${E^P}$ , 显然 $E = {E^T} + {E^P}$ 且 ${E^T} \cap {E^P} = \emptyset $ . 从集合 ${E^T}$ 中取出现有链接中所有的用户集合 $V' \in V$ 且 $V' \ne V$ , 则子网络图 $G' = \left({V',E'} \right)$ . 由 $V'$ 可将测试数据集修正为 ${E^P}{\rm{ = }}E' \cap {E^P}$ , 所以空间集合 $\left({V' \times V'} \right) - {E^T}$ 可用来表示一切隐含节点对的集合.

(3)由 $V'$ 可得出所有用户的位置标签列表, 获取这个列表集合中的地理位置信息, 对其进行聚类, 最终得出一个新的用户-位置矩阵.

(4)分析求解隐藏的用户节点信息中基于地理位置的相似性特征 ${f_{UP}}\left({x,y} \right)$ .

(5)同理, 分析求解隐藏的用户节点对基于时间戳的相似性特征 ${f_T}\left({x,y} \right)$ .

(6)采用Gibbs抽样算法估算出用户基于地理位置主题的概率分布函数, 然后进一步求解隐藏用户节点对基于地理位置信息的用户相似度特征 ${f_W}\left({x,y} \right)$ .

(7)对社交网络中所有隐藏用户节点之间的相似度进行分析计算, 此处主要记录预测性能最佳的Resource allocation (RA)系数指标 $S_{x,y}^{RA}$ .

(8)利用有监督学习策略的算法, 对上文计算得出的各类相似性特征做链接预测, 最终可得出特征向量 $\mathop {feature}\limits^{\rightharpoonup} \left( {x,y} \right) = \left( {{f_{UP}}\left( {x,y} \right),{f_T}\left( {x,y} \right),{f_W}\left( {x,y} \right),S_{x,y}^{RA}} \right)$ , 然后对其进行模型训练, 最后再对测试数据集进行链接预测, 得出基于地理标签的LBSN链接预测结果. 最终得到的结果集中, 用1标注确实存在的链接节点信息, 0标注不存在链接的节点信息.

3.2 评估方法

将上文求解得到的结果集与测试数据集做对比, 可分析出本文链接预测算法的性能. 由于本文采用有监督的链接预测算法, 故采用信息检索算法中常用的四大性能评估指标来衡量本文算法的性能优劣: 精度(Accuracy)、准确率(Precision)、召回率(Recall)以及综合Accuracy和Precision的加权调和平均(F-measure).

由于实验数据中链接分布不均匀, 本文还采用了一个新的评估指标AUC(area under the receive operating characteristic curve)^[11], 如公式(4)所示:

$AUC = \frac{{n' + 0.5n''}}{n}$

(4)

其中, $n$ 代表测试数据集中所有标签对被随机独立抽样的次数, 对于链接节点对而言, 包含了存在和不存在两种情况. $n'$ 表示链接节点对存在时的相似度分数大于不存在时的次数, $n''$ 则表示两种情况相似度分数相等的次数. 从上式可看出, 若存在链接的相似度值大于不存在时, 则相似度值加1, 若相等则加0.5. 因此, AUC指标能够整体地评估链接预测模型的准确度, 其值得取值范围是 $(0.5,{\kern 1pt} {\kern 1pt} {\kern 1pt} 1)$ , AUC的值越大, 表示链接预测模型的精准度越好.

3.3 参数调优

本文采用有监督学习的方式对样本进行分类学习, 基于前人对的研究, 我们可获取关于类别特征的先验知识. 基于已有的类别特征信息, 可对模型进行训练并构造相应的分类器. 由于本文采用的是真实的Gowalla数据集, 故存在样本数据分布不均匀的情况. 为深入挖掘该数据集中的隐藏信息, 可采用机器学习中常用的k-折交叉验证(k-fold cross Validation)法, 该方法得到的实验结果更加真实. 实验证明, 当k值取10的时候可得到最佳的实验效果^[12], 故本文采取10倍交叉验证来评估模型的性能.

上文提到, 本文利用有监督的学习思想对模型中需要输入的参数根据经验预先给出, 然后通过实验对其不断修正. 本文模型中有三个输入参数需要进行调优: 对地理位置信息聚类处理时的距离阈值 $\delta $ , 基于用户地理位置标签的LDA主题模型中的主题K的取值, 以及分析用户相似度时 $TOP{\rm{ - }}K$ 中K的取值.

对距离阈值 $\delta $ 分别取不同的值, 可得到用户基于地理位置标签的相似度特征函数 ${f_{UP}}\left({x,y} \right)$ , 现将该特征函数导入样本分类器进行链接预测, 实验得出的距离阈值 $\delta $ 与加权调和平均F值的关系如图3所示.

由图3可知, 当链接预测距离阈值 $\delta {\rm{ = }}500$ m时, 链接预测的结果最优. 当 $\delta \in \left[ {400,700} \right]$ 时, 该算法的链接预测效果较为良好. 此外, 随着 $\delta $ 的不断增大, 加权调和平均F值不断减小, 即距离越大, 链接预测效果越差. 当 $\delta > 1km$ 时, F值的值显著降低, 说明人与人之间的地理位置距离越远, 两者之间的关系也会越生疏, 该结论显然符合人类社会客观事实. 基于以上分析, 本文对地理位置标签进行层次聚类时的最优距离阈值设定为500 m.

上文提到, 基于地理位置的LDA主题模型可采用Gibb采样算法进行分析求解, 最后得出用户地理位置主题分布 $\Theta $ 和每个主题下的具体地点分布 $\Psi $ . 根据 $\Theta $ 和 $\Psi $ 这两个概率分布函数计算出基于地理位置标签信息的相似性特征函数 ${f_W}\left({x,y} \right)$ . Gibbs采样算法需要预设的参数是 $\alpha $ , $\beta $ 和 $K$ . 其中, $\alpha $ 和 $\beta $ 是Dirchlet先验分布的经验参数, 由于在对数据进行抽样的过程中会不断地更新 $\alpha $ 和 $\beta $ , 因此这两个值先根据经验预设即可, 本文设定 $\alpha = 0.1$ , $\beta = 0.01$ . LDA主题模型中主题个数K值的选取十分重要, 故本文对其进行参数调优实验. 分别对不同的K值计算基于地理位置标签信息的相似性特征函数 ${f_W}\left({x,y} \right)$ , 然后根据 ${f_W}\left({x,y} \right)$ 进行链接预测实验. 实验结果如图4所示, 该图展示了主题个数K和加权调和平均F值的关系. 由图可知, 当主题个数为13时链接预测性能最优, 因此本文实验设定 $K = 13$ .

为了以最低的时间复杂度计算出特征函数 ${f_W}\left({x,y} \right)$ , 并取得最优的链接预测效果, 本文将对地理位置标签主题进行 $TOP{\rm{ - }}K$ 选择, 然后根据选取的 $TOP{\rm{ - }}K$ 个主题计算基于地理位置标签信息的相似性特征函数 ${f_W}\left({x,y} \right)$ . 实验结果如图5所示, 途中展示了 $TOP{\rm{ - }}K$ 值与加权调和平均F值的关系. 从图中观察到当 $TOP{\rm{ - }}K \geqslant 10$ 时, F值较高且相对平稳, 而当 $TOP{\rm{ - }}K{\rm{ = }}5$ 时F值达到巅峰, 故本文选取 $TOP{\rm{ - }}K{\rm{ = }}5$ 进行链接预测实验.

3.4 实验结果与分析

本文在第3.3小节进行了相关参数调优, 接下来本文将使用开源的智能分析环境WEKA提供的几种分类器对Gowalla数据集进行链接预测实验: 朴素贝叶斯分类器(NB)、随机森林分类器(RF)以及决策树分类器(J48). 分别对特征向量 $ \mathop {feature}\limits^{\rightharpoonup} \left({x,y} \right) =\left({{f_{UP}}\left({x,y} \right),{f_T}} \right.$ $ \left. {\left({x,y} \right),{f_W}\left({x,y} \right),S_{x,y}^{RA}} \right)$ 和单一的用户网络特征 $S_{x,y}^{RA}$ 进行实验, 并对比分析两种不同算法的性能. 采用的评估指标是Precision、Recall、F-measure和AUC, 这些指标值是通过对比链接预测的实验结果和测试数据集中真是的数据作对比所得出的, 如表3所示.

从表3中可看出, 基于地理位置标签的特征向量 $\mathop {feature}\limits^{\rightharpoonup} \left({x,y} \right)$ 在三种分类器上的链接预测效果均比基于单一用户网络特征 $S_{x,y}^{RA}$ 取得的效果要好. 综合三个分类器的实验结果, $\mathop {feature}\limits^{\rightharpoonup} \left({x,y} \right)$ 算法的加权调和平均 $f{\rm{ - }}measure$ 值比 $S_{x,y}^{RA}$ 平均高出4.9%, $\mathop {feature}\limits^{\rightharpoonup} \left({x,y} \right)$ 算法的AUC比 $S_{x,y}^{RA}$ 平均高7.9%. 显然, 本文提出的基于地理标签的LBSN链接预测算法由于引入了地理标签语义特征, 其性能得到了明显的提升. 此外, $\mathop {feature}\limits^{\rightharpoonup} \left({x,y} \right)$ 的精度Precision平均值为0.920, 比 $S_{x,y}^{RA}$ 的0.848高出了8.6%. 而 $\mathop {feature}\limits^{\rightharpoonup} \left({x,y} \right)$ 的召回率Recall也比 $S_{x,y}^{RA}$ 平均提高了4.1%. 因此, 从用户地理位置标签信息中挖掘出来的信息纬度更加广阔, 能够得到更多的用户相似性特征, 从而降低了链接预测出错的概率.

从表3中还可看出, 以上两个实验中链接预测性能优劣为随机森林算法优于朴素贝叶斯算法, 而朴素贝叶斯算法又优于决策树算法, 单三者之间并无明显差异, 说明本文提出的算法具有良好的稳定性, 不同分类器对该算法的影响几乎可以忽略不计.

4 结论与展望

为解决地理位置分布的稀疏性问题, 本文对测试数据集进行聚类分析, 并建立了基于用户地理标签的LDA主题模型, 分析出用户的地理位置标签的相似性特征. 最后, 本文综合了网络结构相似性特征和基于用户地理位置信息的相似度特征, 采用有监督策略的链接预测在Gowalla数据集上进行实验. 实验结果表明, 本文提出的模型能有效提高LBSN的链接预测准确度, 且具有良好的稳定性. 然而随着互联网的发展, LBSN的数据规模呈现指数级的增长, 未来可进一步研究基于大数据分布式平台的链接预测算法.