CN106021290A - 一种基于多尺度地理信息的社交网络关联挖掘方法 - Google Patents

Abstract

本发明涉及一种基于多尺度地理信息的社交网络关联挖掘方法。该方法包括：1)获取用户签到数据，对其进行预处理得到结构化数据；2)设定划分地图的不同方法以及每种方法的尺度标准，根据用户签到数据中的GPS数据计算获得其对应的多个位置ID；3)根据签到人数计算获得不同位置的权重，表征不同位置对社交关系预测的贡献；4)利用位置的权重信息进行特征提取，获得所有用户的位置交互特征；5)利用提取的特征训练分类器，得到关系预测模型；6)利用所得的关系预测模型对目标用户进行预测，获得社交网络关系预测结果。本发明通过充分利用位置签到信息来训练获得更鲁棒的预测模型，能够获得理想稳定的预测结果。

Description

一种基于多尺度地理信息的社交网络关联挖掘方法

技术领域

本发明属于信息技术、社交网络技术领域，具体涉及一种基于多尺度地理信息的社交网络关联挖掘方法。

背景技术

在社交网络研究领域，社交网络关联挖掘是一项重要的研究方向，而且是其他很多研究如社团发现和推荐系统等研究的基础。例如，人们倾向于购买亲朋好友推荐的产品，社团也往往是由相互之间熟悉的人组成。因此，社交网络关联挖掘已经成为社交网络研究领域的热门话题，并且吸引了广泛关注。

传统意义上，社交网络关联挖掘往往是利用图模型的方法进行预测，即把社交网络关联挖掘网络抽象成图模型，并利用拓扑学方法进行预测。近年来，随着基于地理位置信息社交网络的迅速发展，研究人员开始利用用户的位置信息来预测相互之间的社交网络关联。

目前，利用用户的位置信息预测用户之间社交网络关联的研究，主要集中在对于位置特征的提取方面，对于位置属性以及如何充分利用位置属性设计有效关系预测模型的研究较少，主要不足在于：

a.对签到信息的稀疏性的处理欠缺。目前采用的地点确认方法是利用固定的网格或者其他方法划分区域，而各个地点的签到人数和签到次数稀疏差异很大，因而使用固定尺寸划分地图形成地点，可能会导致某些地点的签到人数很多，而某些地点的签到人数又太少。这就导致在进行社交网络关联挖掘时，难以保证预测的稳定性。签到人数多的位置，人们更容易被预测为之间存在社交网络关联，签到人数少的位置，由于观测到的人们之间的互动较少因此更容易预测为相互之间没有好友关系。

b.对于位置属性挖掘不充分。在对人们之间社交网络关联进行预测时，不同的位置贡献大小不同。如果是在一个用户家里检测到另一位用户的访问信息，很大程度上可以确认两人存在社交网络关联。而如果是在公园或者图书馆检测到两人同时出现，则很难仅据此推断出两人是否存在社交网络关联。

c.对数据倾斜问题处理不够。目前利用位置信息预测用户关系的模型研究较少，尤其是在关系预测时，存在社交网络关联的用户较少，造成在训练预测模型时正样本比例太小，从而导致预测模型鲁棒性不强。

发明内容

本发明提出一种基于多尺度地理信息的社交网络关联挖掘方法，通过充分利用位置签到信息，来训练获得更鲁棒的预测模型，从而获得理想稳定的预测结果。

本发明采用的技术方案如下：

一种基于多尺度地理信息的社交网络关联挖掘方法，包括以下步骤：

1)获取用户签到数据，对其进行预处理得到结构化数据；

2)设定划分地图的不同方法以及每种方法的尺度标准，根据用户签到数据中的GPS数据计算获得其对应的多个位置ID；

3)根据签到人数计算获得不同位置的权重，用以表征不同位置对社交关系预测的贡献；

4)利用位置的权重信息进行特征提取，获得所有用户的位置交互特征；

5)利用提取的特征训练分类器，得到关系预测模型；

6)利用所得的关系预测模型对目标用户进行预测，获得社交网络关系预测结果。

进一步地，步骤1)所述结构化数据包括用户的签到时间、签到地点、签到次数等基本信息，将这些数据以矩阵形式存储。

进一步地，步骤4)提取的特征包括：基于加权位置信息的共同访问地点特征、基于加权位置信息的Jaccard相似度特征、基于加权位置信息的余弦相似度特征。

进一步地，步骤5)从两个角度训练基准分类器：一方面，以每一个尺度的所有特征为特征集合，即每个尺度对应训练一个基准分类器；另一方面，以多个尺度的单个特征计算方法为特征集合，即每个特征计算方法对应训练一个基准分类器。然后使用训练所得的基准分类器对测试集进行分类，对应得到置信度集合，并从两个角度对置信度集合分别进行加权平均，根据置信度均值进行排序，分别采用top方法选取一定比例置信度较大的样本；如果样本在两个角度筛选出的样本集合中均出现，则设定该样本为推荐样本，将推荐样本加入到训练集中，进而得到最终的分类器，即关系预测模型。

本发明的有益效果如下：

1)本发明提出利用多个标准分割地图，使每一条签到信息对应多个位置ID，以此克服由于单一标准难以得到稳定预测结果的问题；

2)本发明根据每个位置对预测用户关系的影响大小分配权重，从而更合理充分的应用位置和签到信息；

3)本发明提出一种推荐的位置信息挖掘方法，训练获得更鲁棒的预测模型；采用本发明进行社交网络关联挖掘，预测结果包括精度、召回率、F值和准确率均获得理想效果，具有很好的鲁棒性和泛化性能，可以得到稳定的预测效果。

附图说明

图1是本发明的社交网络关联挖掘方法的基本步骤流程图。

图2是本发明的社交网络关联挖掘方法的具体步骤流程图。

具体实施方式

为使本发明的上述目的、特征和优点能够更加明显易懂，下面通过具体实施例和附图，对本发明做进一步说明。

本发明由数据预处理、位置ID定义、位置权重计算、特征提取、预测模型训练五个模块(步骤)组成，经过五个模块的处理，即能够利用用户的签到信息完成用户的社交网络关联挖掘。下面对五个模块的功能和原理进行介绍。

模块一数据预处理

在LBSN网站获取到的用户签到数据往往是非结构化数据，难以进行数据分析，因此首先将这些数据处理成结构化数据。经过处理，用户的签到时间、签到地点(GPS格式)、签到次数等基本信息以矩阵形式存储。

模块二位置ID定义

设定划分地图的n种方法以及每种方法的尺度标准，根据签到信息的GPS数据，计算获得其对应的n个位置ID。

划分地图的方法包括但不限于：利用经纬线交错形成的网格对地图进行划分。尺度标准是指每两条经线或者每两条纬线之间的经纬度距离，可根据实际应用需求，人为指定，例如采用0.1度作为尺度标准，即每两条经线之间和每两条纬线之间的距离均为0.1度。

模块三位置权重计算

位置权重由签到人数计算获得。在对用户之间的社交网络关联进行预测时，一个地点的访问人数越多，该地点对关系预测的贡献越小，例如在公园、图书馆等公共场所的相遇，很难据此证明两个用户之间存在社交网络关联。反之一个地点的访问人数越少，对关系预测的贡献就越大。然而特殊情况是，当一个地点仅有一个用户或者没有用户访问时，该地点的权重设定为0。这是因为这类地点对于用户之间的交互信息没有任何表征，因此也便不能对用户的关系预测提供参考信息。根据描述，设定位置权重的计算公式如下：

$D_k\left\{\begin{array}{ccc}0,& if& \underset{i=1}{\overset{m}{\Σ}}d(i,l_k)\≤1\\ \frac{1}{\ln \frac{{\Σ}_{i=1}^{m}d(i,l_k)}{{\Σ}_{x=1}^t{\Σ}_{i=1}^{m}d(i,l_x)}},& if& \underset{i=1}{\overset{m}{\Σ}}d(i,l_k)>2\end{array}\right.$

其中，D_k为位置权重，t为位置总数，m为用户总数，d(i,l_k)表示用户i是否会在位置k出现。如果出现则d(i,l_k)＝1，否则d(i,l_k)＝0。

模块四特征提取

特征提取是对用户位置交互信息的计算，在此基于位置属性定义三种特征计算方法。

a.基于加权位置信息的共同访问地点特征

如果两个用户有共同访问的地点，这两个用户之间可能会存在社交网络关联。而访问地点的权重越大，存在的可能性也就越大。因此结合位置权重和共同访问地点设定特征提取方法为：

其中和分别为用户i和用户j访问过的位置ID的集合。

b.基于加权位置信息的Jaccard相似度特征

共同访问地点特征虽然有效，然而对于活跃用户(签到次数和签到地点多的用户)的处理容易出现偏差，因此提出结合位置权重和Jaccard相似度设计特征。特征计算公式为：

其中D_x表示用户i和用户j共同去过的位置的权重，D_y表示用户i或者用户j去过的位置的权重。

c.基于加权位置信息的余弦相似度特征

用户签到习惯的相似度是另一个值得关注的问题，用户在某一地点位置签到的次数可以一定程度上表征用户的签到习惯。在此利用余弦相似度来计算用户的签到习惯相似度。用c(i,l_k)表示用户i在地点k的签到次数，则用户i在地点k出现的概率可以描述为 那么该用户在每个地点出现的概率可以用向量表示：

P(i)＝<P(i,1),P(i,2)…P(i,t)＞

相应的，位置加权概率向量为：

WP(i)＝<D₁·P(i,1),D₂·P(i,2)…D_t·P(i,t)＞

最终该特征可以表示为：

${\mathrm{WS}}_{ij}=\frac{WP\left(i\right)\&CenterDot;WP\left(j\right)}{\left|WP\left(i\right)\right|\left|WP\left(j\right)\right|}$

利用上述三种特征计算方法，对每一对用户进行计算，获得所有用户之间位置信息的特征。

模块五预测模型训练

利用上一模块计算的特征，从两个角度训练基准分类器。如图2所示，一方面，以每一个尺度的所有特征为特征集合，即每个尺度对应训练一个基准分类器；另一方面，以多个尺度的单个特征计算方法为特征集合，即每个特征计算方法对应训练一个基准分类器。使用训练所得的基准分类器对测试集进行分类，对应得到置信度集合。从两个角度，对置信度集合分别进行加权平均，根据置信度均值进行排序，分别采用top方法选取一定比例置信度较大的样本。如果样本在两个角度筛选出的样本集合中均出现，则设定该样本为推荐样本。将推荐样本加入到训练集中，以完备特征集(在各尺度标准下以所有特征计算方法计算所得特征值组成的特征集)训练得到最终的分类器，即关系预测模型。

最后利用所得的关系预测模型对目标用户进行预测，获得关系预测结果。

下面提供一个应用实例。该实例采用一个基于位置的社交网站Gowalla进行用户社交网络关联挖掘。在此处，对社交网络关联的定义是：如果两个用户在通信网络中存在邻接点，则认为这两个用户存在社交网络关联。

Gowalla是基于地理位置的社交网络，用户能够在网站上进行签到，签到信息包括用户的签到时间、签到地点(GPS格式)、签到时间等。选取签到数据最多的城市奥斯丁为目标地，对该地的用户进行研究。选取2010年签到数据多于50条的用户做为研究目标，共有1585个用户，722,598条签到数据，这些用户中有7356对之间存在通话关系。

经过预处理，将用户的签到信息处理为结构化数据，然后以经纬度0.1度，0.01度，0.001度为边的正方形划分区域，根据签到信息中的GPS数据确定签到地点的位置ID，每条签到信息对应三个位置ID。利用本发明提出的三种基于位置权重的特征计算方法提取用户位置交互特征，然后将样本集合划分为训练集和测试集，其中50％样本作为训练集，50％样本作为测试集。然后采用逻辑斯蒂回归模型作为基准分类器，利用训练集从两个角度训练基准分类器。推荐样本设定为测试集中待测样本正样本数量的20％。预测达到理想效果。算法伪代码如下：

以上实施例仅用以说明本发明的技术方案而非对其进行限制，本领域的普通技术人员可以对本发明的技术方案进行修改或者等同替换，而不脱离本发明的精神和范围，本发明的保护范围应以权利要求书所述为准。

Claims (9)

1.一种基于多尺度地理信息的社交网络关联挖掘方法，其特征在于，包括以下步骤：

1)获取用户签到数据，对其进行预处理得到结构化数据；

2)设定划分地图的不同方法以及每种方法的尺度标准，根据用户签到数据中的GPS数据计算获得其对应的多个位置ID；

3)根据签到人数计算获得不同位置的权重，用以表征不同位置对社交关系预测的贡献；

4)利用位置的权重信息进行特征提取，获得所有用户的位置交互特征；

5)利用提取的特征训练分类器，得到关系预测模型；

6)利用所得的关系预测模型对目标用户进行预测，获得社交网络关系预测结果。

2.如权利要求1所述的方法，其特征在于：步骤1)所述结构化数据包括用户的签到时间、签到地点、签到次数，将这些数据以矩阵形式存储。

3.如权利要求1所述的方法，其特征在于：步骤3)按照如下公式计算位置权重：

$D_k=\left\{\begin{array}{cc}0,& if\underset{i=1}{\overset{m}{\&Sigma;}}d(i,l_k)\&le;1\\ \frac{1}{ln\frac{{\mathrm{\&Sigma;}}_{i=1}^{m}d(i,l_k)}{{\mathrm{\&Sigma;}}_{x=1}^t{\mathrm{\&Sigma;}}_{i=1}^{m}d(i,l_x)}},& if\underset{i=1}{\overset{m}{\&Sigma;}}d(i,l_k)>2\end{array}\right.$

其中，D_k为位置权重，t为位置总数，m为用户总数；d(i,l_k)表示用户i是否会在位置k出现，如果出现则d(i,l_k)＝1，否则d(i,l_k)＝0。

4.如权利要求3所述的方法，其特征在于，步骤4)提取的特征包括：基于加权位置信息的共同访问地点特征、基于加权位置信息的Jaccard相似度特征、基于加权位置信息的余弦相似度特征。

5.如权利要求4所述的方法，其特征在于，所述基于加权位置信息的共同访问地点特征的计算公式为：

其中和分别为用户i和用户j访问过的位置ID的集合。

6.如权利要求4所述的方法，其特征在于，所述基于加权位置信息的Jaccard相似度特征的计算公式为：

其中D_x表示用户i和用户j共同去过的位置的权重，D_y表示用户i或者用户j去过的位置的权重。

7.如权利要求4所述的方法，其特征在于，所述基于加权位置信息的余弦相似度特征的计算公式为：

${\mathrm{WS}}_{ij}=\frac{WP\left(i\right)\&CenterDot;WP\left(j\right)}{\left|WP\left(i\right)\right|\left|WP\left(j\right)\right|},$

其中，WP(i)和WP(j)用户i和j在每个地点出现的位置加权概率向量。

8.如权利要求1所述的方法，其特征在于：步骤5)从两个角度训练基准分类器：一方面，以每一个尺度的所有特征为特征集合，即每个尺度对应训练一个基准分类器；另一方面，以多个尺度的单个特征计算方法为特征集合，即每个特征计算方法对应训练一个基准分类器。

9.如权利要求8所述的方法，其特征在于：步骤5)使用训练所得的基准分类器对测试集进行分类，对应得到置信度集合，并从两个角度对置信度集合分别进行加权平均，根据置信度均值进行排序，分别采用top方法选取一定比例置信度较大的样本；如果样本在两个角度筛选出的样本集合中均出现，则设定该样本为推荐样本，将推荐样本加入到训练集中，进而得到最终的分类器，即关系预测模型。