在位置社交网络中基于位置与时间的好友推荐方法

摘要

本发明公开了一种基于位置与时间的好友推荐方法，主要解决现有好友推荐方案忽视签到信息中的时间信息和签到位置语义信息导致推荐精度不够高的问题。其实现步骤为：1.建立一个由用户、定位设施、位置服务器构成的通信系统框架；2.用户将位置的经纬度与当前的时间信息发送给社交网络服务器生成签到信息；3.社交网络服务器对存储的大量签到信息进行预处理；4.社交网络服务器计算每个用户对于每个地点类别的词频?逆文档频率分值；5.社交网络服务器计算用户间的相似度，并选取相似度较高的用户做出好友推荐。本发明缓解了推荐系统可用数据稀疏性，提高了推荐精确度。可用于基于位置的无线社交网络服务。

说明书

技术领域：

本发明属于无线网络技术领域，涉及无线社交网络的好友推荐，可应用于基于位置 的无线社交网络服务。

背景技术：

基于位置的社交网络帮助用户在线分享他们的实时位置以便于用户可以发现感兴 趣的位置并结交朋友。例如，用户可以通过好友分享的位置发现自己感兴趣的地点，或 者通过查找与自己分享相似地点的用户来结交新的好友。此外，随着智能手机的普及， 其内置的GPS模块可以更加精确的探测用户的位置，使得用户可以更加便利的分享各 自的位置。因此，这种签到服务吸引了越来越多的用户。如何使用大量的签到信息为用 户进行好友推荐需要得到重视。

推荐系统在社交网络和电子商务网站中扮演了重要的角色，在电子商务网站中，现 有的推荐系统通常使用用户的购买记录来分析用户的偏好，正如电子商务网站的购买记 录，用户在基于位置的社交网络中的签到历史也包含了大量的关于用户偏好的信息。

在使用用户的签到信息进行好友推荐时，由于用户通常只会在数据库中的一小部分 地点进行签到行为，因此进行好友推荐的可用数据较为稀疏。为了缓解数据稀疏的问题， 现有方案分为如下几种：根据签到地点的密度进行分类，将一些地理位置较为接近的签 到地点看作同一个签到地点；使用用户好友的签到数据填充到用户的签到数据中。但是， 地理位置接近的地点可能代表了用户不同的兴趣爱好，同样，好友的爱好并不能完全代 替用户自身的兴趣爱好，这两种行为都在一定程度上降低了好友推荐的精度。

在考虑时间信息的推荐系统方面，现有系统多用在电子商务网站与电影推荐网站， 通过分析用户长期的购买记录与电影的观看记录分析用户的偏好来进行推荐。相比于长 期的趋势，用户的签到行为在一天的具体时间可以提供更多反映用户偏好的信息。而在 现有社交网络推荐系统中，只通过分析签到地点的时间属性对签到地点进行了分类，并 未对用户签到行为的时间分布进行分析来进行好友推荐，因此推荐的准确率不够理想。

发明内容

本发明的目的在于针对上述已有技术的不足，提出一种在位置社交网络中基 于位置与时间的好友推荐方法，以提高推荐的准确率。

本发明通过将拥有相似语义信息的地点归为一类，解决推荐系统中可用数据稀疏的 问题，使用词频-逆文档频率平衡热门地点与用户自身的兴趣，同时通过分析用户签到 行为随时间的分布规律，对用户的相似度计算进行调整，实现更加准确的好友推荐。其 实现方案包括如下：

(1)建立一个由用户、定位设施、社交网络服务器构成的通信系统框架，其中：

用户，用于通过移动蜂窝网络或WiFi与定位设施和社交网络服务器进行通信；

定位设施，用于协同用户GPS模块实现定位；

社交网络服务器，用于存储用户的位置信息，并以此为依据向用户进行好友推荐；

(2)用户将位置的经纬度与当前的时间信息发送给社交网络服务器，生成签到信 息；

(3)社交网络服务器对存储的签到信息进行预处理：

(3a)针对签到信息中的经纬度，查找服务器的位置语义数据库获取与签到地点对 应的语义信息，然后将每个用户的签到信息按其签到地点的语义信息分类统计签到次数；

(3b)针对签到信息中的时间信息，在步骤(3a)的基础上，统计每个用户在每个 地点类别下的签到行为随时间的分布；

(4)根据用户在各地点类别的签到次数，社交网络服务器计算每个用户u对于每 个地点类别c的词频-逆文档频率分值TF-IDF_u,c；

(4a)根据用户u在各地点类别下的签到次数，社交网络服务器计算用户u在每个 地点类别c下签到信息的词频分值TF_u,c；

(4b)根据所有用户在各地点类别下的签到次数，社交网络服务器计算每个地点类 别c的逆文档频率分值IDF_c；

(4c)社交网络服务器将用户u在地点类别c下的词频分值TF_u,c与地点类别c的逆 文档频率分值IDF_c相乘，得到其在该地点类别下的词频-逆文档频率分值 TF-IDF_u,c＝TF_u,c×IDF_c；

(5)社交网络服务器计算用户间的相似度：

(5a)使用用户在每个地点类别下签到行为随时间的分布，计算两个用户在相同地 点类别下签到分布的相对熵D(P□Q)，其中P和Q为两个用户u_i和u_j在相同地点类别的 签到次数随时间的概率分布，然后使用相对熵计算相似度调整因子

(5b)针对用户在每一地点类别的词频-逆文档频率分值TF-IDF_u,c，使用对应的相 似度调整因子调整余弦相似度计算公式，计算两个用户间的相似度cos(u_i,u_j)；

(6)社交网络服务器对请求推荐的用户与所有其他用户之间重复上述步骤(3)至 步骤(5)，得到该用户与其他用户的相似度分值，选取分值最高的n个用户作为推荐结 果发送给请求推荐的用户，n为请求推荐的用户所请求的好友推荐数量。

本发明与现有技术相比具有如下优点：

1)本发明由于使用了签到地点的语义信息进行分类，在缓解推荐可用数据稀疏性 的同时，保持了较高的推荐精度。

2)本发明由于使用了词频-逆文档频率模型对签到数据进行量化，平衡了热门签到 地点与用户自身的偏好。

3)本发明由于对用户的签到行为随时间的分布进行了分析，并通过计算用户间签 到行为随时间分布的差异得到计算用户相似度的调整因子，充分利用了签到信息的地理 信息与时间信息，从而保证了较高的推荐准确性。

附图说明

图1是本发明使用的通信系统框架图；

图2是本发明的实现流程图；

图3是本发明所用推荐方案与未考虑时间因素的推荐方案的推荐准确率对比图；

图4是本发明所用推荐方案与未考虑时间因素的推荐方案的推荐召回率对比图。

具体实施方案

本发明的核心思想是在基于位置的社交网络场景下，通过分析用户签到地点的语义 信息将签到数据进行分类以缓解可用数据较为稀疏的问题，并综合分析了签到地点的热 度，用户个人的偏好以及用户签到行为随时间的分布规律用来对用户进行好友推荐，提 高推荐的准确度。

参照图2，本发明实现步骤如下：

步骤1，建立通信系统框架。

参照图1，本步骤建立的通信系统包括：用户、定位设施、社交网络服务器，其中 用户与定位设施和社交网络服务器均通过移动蜂窝网或WiFi进行双向无线连接；

所述用户，包含应用模块、数据库模块和GPS模块三个功能模块；应用模块主要用 于生成并发送签到信息给社交网络服务器；GPS模块主要用于向定位设施查询位置信息 并向应用模块提供用户的地理位置信息；数据库模块主要用于存储和管理用户签到和好 友信息；

所述定位设施，主要包含GPS模块，该GPS模块主要用于对用户的位置查询进行 响应并返回用户的地理位置信息；

所述社交网络服务器，包含应用模块和数据库模块两个功能模块；应用模块主要用 于对用户的签到信息进行分析整理并为用户的好友推荐请求返回推荐结果，数据库模块 主要用于存储用户的签到数据和签到地点的语义信息。

步骤2，采集签到信息。

用户借助定位设施获得自身所在的地理位置信息，并将此地理位置信息与当时的时 间信息发送给社交网络服务器生成签到信息。

步骤3，社交网络服务器对存储的大量签到信息进行预处理。

(3a)针对签到信息中的地理位置信息，查找服务器的位置语义数据库获取与签到 地点对应的语义信息，然后将每个用户的签到信息按其签到地点的语义信息分类统计签 到次数；

(3b)针对签到信息中的时间信息，将一天时间分成5个区间，分别为2：00-7：00， 7：00-11：00，11：00-17：00，17：00-22：00，22：00-2：00，统计用户u在地点类别 c上每一时间区间上的签到次数vis(c,u)和用户在该地点类别总的签到次数sum(c)，得到 用户在地点类别c每一时间区间的签到频率P(c,v)＝vis(c,v)/sum(c)，由此得到用户在某 个地点类别签到行为随时间的分布。

步骤4，社交网络服务器计算每个用户u对于每个地点类别c的词频-逆文档频率分 值TF-IDF_u,c。

(4a)社交网络服务器计算用户u在地点类别c下签到信息的词频分值TF_u,c：

${\mathrm{TF}}_{u,c}=\frac{\left|\right\{u.v_i:v_i.D=c\left\}\right|}{|u.V|},$

其中，|{u.v_i:v_i.D＝c}|是用户u在地点类别c下签到的次数，|u.V|是用户u在所有地点签 到的总次数；

(4b)社交网络服务器计算每个地点类别c的逆文档频率分值IDF_c：

${\mathrm{IDF}}_c=log\frac{\left|U\right|}{\left|\right\{u_j:c\in u_j.D\left\}\right|},$

其中，|U|表示服务器中所有用户的数量，|{u_j:c∈u_j.D}|表示曾在地点类别c签到的用户 的数量；

(4c)社交网络服务器将用户u在地点类别c下的词频分值TF_u,c与地点类别c的逆 文档频率分值IDF_c相乘，得到其在该地点类别下的词频-逆文档频率分值 TF-IDF_u，c＝TF_u，c×IDF_c。

步骤5，社交网络服务器计算用户间的相似度。

(5a)社交网络服务器分别计算第i个用户u_i与第j个用户u_j在地点类别c的相对熵 D(P_c||Q_c)与第j个用户u_j与第i个用户u_i在地点类别c的相对熵D(Q_c||P_c)，其计算公 式如下：

其中，P_c为第i个用户u_i在地点类别c的签到随时间的概率分布，Q_c为第j个用户u_j在 地点类别c的签到随时间的概率分布，i＝1,2,3,4,5分别对应步骤(3b)计算用户签到随 时间的概率分布时所划分的5个时间区间；

(5b)社交网络服务器根据(5a)的结果计算地点类别c签到信息相似度的调整因 子如下：

$F_{u_i,u_j,c}=\frac{2}{D\left(P_c\right|\left|Q_c\right)+D\left(Q_c\right|\left|P_c\right)+1};$

(5c)社交网络服务器在步骤(4c)得到的用户在每一地点类别的词频-逆文档频率 分值TF-IDF_u,c的基础上，使用调整因子调整余弦相似度计算公式，计算两个用户间的 相似度cos(u_i,u_j)：

$\cos (u_i,u_j)=\frac{\underset{k=1}{\overset{n}{\Sigma }}{I}_k\times J_k\times (F_{\max }-F_{u_i,u_j,k})}{\sqrt{\underset{k=1}{\overset{n}{\Sigma }}{\left(I_k\right)}^2}\times \sqrt{\underset{k=1}{\overset{n}{\Sigma }}{\left(J_k\right)}^2}},$

其中，I_k为第i个用户u_i对于地点类别k的词频-逆文档频率分值，J_k为第j个用户u_j对 于地点类别k的词频-逆文档频率分值，F_max为所有调整因子中的最大值。

步骤6，社交网络服务器做出最终的好友推荐。

社交网络服务器对请求推荐的用户与所有其他用户之间重复上述步骤(3)至步骤 (5)，得到该用户与其他用户的相似度分值，选取分值最高的n个用户作为推荐结果发 送给请求推荐的用户，n为请求推荐的用户所请求的好友推荐数量。

本发明的效果可通过以下仿真实验进一步说明：

1.实验条件设置

条件1，在Foursquare获得签到数据集，选取其中旧金山的签到数据组成数据集合， 并选取其中签到数量最多的100名用户的50765条签到数据作为实验的源数据。

条件2，在Intel(R)Celeron(R)G540处理器，Windows7Ultimate操作系统的台式计 算机上测试实验的结果。

2.实验内容与结果

实验1：将过滤后的实验数据划分为训练集与测试集，首先在训练集上运行本发明 的推荐程序，将得到的与请求推荐用户最相似的20个用户作为请求推荐的用户的好友； 随后在测试集上运行相同的推荐程序，分别取最相似的n个用户做出推荐， n＝1,2,3,...,20；然后在训练集和测试集上运行未考虑时间因素的传统好友推荐方案得到 相应的好友列表和推荐结果，最后对两种推荐方法的准确率进行计算，计算公式如下：

$\mathrm{Pr}ecision=\frac{{\Sigma }_{u\in U}|R\left(u\right)\cap T\left(u\right)|}{\left|T\left(u\right)\right|}$

其中R(u)表示从训练集计算出的好友列表，T(u)表示通过测试集做出的好友推荐列 表，U表示数据集中所有的用户。

比较二者准确率随推荐好友数量增加的变化情况，结果如图3所示。

从图3可见，当推荐的好友数量超过5位之后，本发明所用的好友推荐方案的准确 率均高于未考虑时间因素的传统的好友推荐方案。在现实的使用场景下，推荐的好友数 量通常高于5位，因此可以说本发明所用的好友推荐方案的准确率明显优于传统的未考 虑时间因素的推荐方案。

实验2：将过滤后的实验数据划分为训练集与测试集，首先在训练集上运行本发明 的推荐程序，将得到的与请求推荐用户最相似的20个用户作为请求推荐的用户的好友； 随后在测试集上运行相同的推荐程序，分别取最相似的n个用户做出推荐， n＝1,2,3,...,20；然后在训练集和测试集上运行未考虑时间因素的传统好友推荐方案得到 相应的好友列表和推荐结果，最后对两种推荐方法的召回率进行计算，计算公式如下：

$\mathrm{Re}call=\frac{{\Sigma }_{u\in U}|R\left(u\right)\cap T\left(u\right)|}{\left|R\left(u\right)\right|}$

其中R(u)表示从训练集计算出的好友列表，T(u)表示通过测试集做出的好友推荐列 表，U表示数据集中所有的用户。

比较二者召回率随推荐好友数量增加的变化情况，结果如图4所示。

从图4可见，当推荐的好友数量较少时，本发明所用的好友推荐方案与传统的未考 虑时间因素的好友推荐方案的召回率差别不大，随着推荐好友数量的增加，本发明所用 的方案召回率渐渐超过传统的未考虑时间的好友推荐方案。同样由于在现实的使用场景 下，推荐的好友数量通常较多，因此可以说本发明所用的好友推荐方案的召回率明显优 于传统的未考虑时间因素的推荐方案。

综上所述，本发明在推荐结果的准确率与召回率方面均优于传统的好友推荐系统， 可以为基于位置社交网络的用户提供质量更高的好友推荐服务。