一种自动推断社会关系的移动用户位置预测方法与装置

技术领域

本发明属于移动行为预测技术领域，具体涉及一种自动推断社会关系的移动用户位置预测方法与装置。

背景技术

近些年来，大规模人类行为轨迹数据的产生与采集促使学术界迸发出了一大批刻画人类移动模式的创新研究。有关人类移动的实证分析和模型研究为人类生活中不同领域的实际应用场景发挥了巨大的作用，例如位置预测、疾病预防和控制、交通出行规划、数据共享以及灾害应对等等。作为极其重要的应用之一，预测用户未来位置的课题称为学术界和工业界的研究热点。

目前，有关用户位置预测的方法主要可以分为两大类：一类为基于用户自身历史移动轨迹的方法，另一类则为结合用户社会关系的方法。

早些年研究者们根据用户自身的历史移动轨迹信息设计了一系列预测方法，其中最具有代表性的一种方法为基于马尔可夫链的预测方法。2006年Song等人发表在《IEEETransactions on Mobile Computing》上的《Evaluating Next-Cell Predictors withExtensive Wi-Fi Mobility Data》以及2013年Lu等人发表在《Scientific Reports》上的《Approaching the Limit of Predictability in Human Mobility》等工作介绍了基于不同阶数马尔可夫链的预测方法，文章通过分析发现相比复杂的高阶马尔可夫预测方法，简单的低阶(一阶或二阶)马尔可夫预测方法可以达到较好的预测准确率。该类型方法的优势在于实现比较简单，但预测准确率仍有待提升。

随着社交网络的社交网络、无线通信和移动计算等领域在近些年的飞速发展，研究者们逐步将用户在社交网络上的社会关系利用到位置预测方法的设计中来。2015年Zhang等人在《IEEE Transactions on Computers》上的《NextCell:Predicting LocationUsing Social Interplay from Cell Phone Traces》以及2016年Jia等人在《ACMTransactions on Intelligent Systems and Technology》上发表的《LocationPrediction:A Temporal-Spatial Bayesian Model》等工作利用用户的朋友等社会关系的移动轨迹来预测该用户的未来位置。纵观这类方法，它们的共性在于利用了用户的朋友、同事/同学等熟人社会关系来为用户的位置预测服务，因此相比第一类方法，这类方法在预测准确率上有着比较明显的提升。

然而，在现有的预测方法研究中仍然存在着问题，即对用户社会关系考虑的不全面。现有的利用用户社会关系的预测方法主要考虑了从社交网站上的链接关系、手机通话及短信记录、手机通讯录记录等采集到的用户的朋友、熟人等这类熟人社会关系。而事实上，一方面，社交网络的发展使得用户越来越多的信息暴露在社交网络中，敏感信息暴露在开放的社交网络中所导致的多种隐私信息泄露问题逐渐引起人们对于隐私保护议题的关注，这使得科研工作者们在获取用户社会关系数据方面面临着越来越多的困难和挑战；另一方面，除了这些我们能够直观感受到的紧密社会关系，在我们的日常生活中还存在着一类特殊的社会关系，即“熟悉的陌生人”。熟悉的陌生人是这样的一群人，他们会重复地相遇，但他们却彼此不相识也从未注意到对方，例如在每天上班的公交车上，在每周去的健身馆里，都有可能遇到很多这样熟悉的陌生人，它占据了人们日常所能接触到的人的很大一部分，因而不能被忽略。2016年Liang等人在《Europhysics Letters》上发表的《Identifying Familiar Strangers in Human Encounter Networks》一文设计了熟悉的陌生人分类器用以从不同的社会关系中挖掘出熟悉的陌生人关系。迄今为止，尚未见到将该类社会关系应用到位置预测领域的相关研究工作。

发明内容

本发明目的在于提供了一种自动推断社会关系的移动用户位置预测方法与装置，以解决现有位置预测方法中需要采集用户的社会关系数据和对用户社会关系考虑不足的问题，从而保护用户的个人隐私，提高位置预测方法的准确性。

本发明提供的自动推断社会关系的移动用户位置预测方法，具体步骤为：

(1)获取用户个体行为记录，即从用户移动行为日志数据库中，获取用户的个体行为记录，每条数据记录包括：用户ID、接入起始时间、接入持续时间、接入地点ID；

(2)推断用户间社会关系类型，即利用所述用户个体行为记录推断两用户间的社会关系类型，社会关系类型包括熟悉的陌生人FS(familiar stranger)、熟人F&IR(包括朋友friend和同事in-role)、陌生人S(stranger)；

(3)建立用户社会关系网络，即以用户为节点，两用户间的社会关系类型为连边(不考虑陌生人关系)，构建用户社会关系网络；

(4)建立用户移动轨迹序列，即利用所述用户个体行为记录，构建用户按时间顺序的离散移动轨迹序列；

(5)检测用户群体社会关系模体，即利用杰卡德系数生成社会关系子图；通过度保留断边重连的方法生成随机化用户社会关系网络，构建零模型；比较各社会关系子图在真实网络和零模型下统计指标z值的大小关系，确定用户群体社会关系模体；

(6)用户个体社会关系模体验证，首先利用杰卡德系数生成该用户的社会关系子图；比较该用户个体社会关系子图是否为前述社会关系模体，若是则通过验证，反之则不通过；

(7)建立位置预测器，即分别建立马尔可夫预测器、熟人预测器、熟悉的陌生人预测器和输出调节器；若该个体通过社会关系模体验证，则只需利用马尔可夫预测器、熟悉的陌生人预测器和输出调节器来预测该用户的未来位置，若未通过验证，则需要马尔可夫预测器、熟人预测器、熟悉的陌生人预测器和输出调节器预测该用户的未来位置。

本发明步骤(1)中，所述从用户移动行为日志数据库中，获取用户的个体行为记录，每条记录包括：用户ID、时间、地点、停留时间。

本发明步骤(2)中，所述利用用户个体行为记录推断两用户间的社会关系类型，详见中国专利“一种基于用户移动行为的线下社会关系分类方法及装置”(专利号201611264316.7)，包括：

根据用户行为记录，得到用户集U，地点集L。每条数据记录包括用户ID、接入起始时间、接入持续时间、接入地点ID；

根据用户行为记录中的时间数据，确定用户行为周期T，离散化时间步长度ΔT，其中，所述用户行为周期T将日志数据中的整个时间轴划分为N个周期；

对于每一个周期n，构建用户u的行为矩阵其中，u为用户集U中的第u个用户，n为N个周期中的第n个周期，l表示地点集L中的第l个地点；行为矩阵S_n(u)中的元素为0或1。

用时间空间共现表示用户u与用户v在同一个地点l拥有时间重合的行为记录。时空共现代表用户u与用户v在实际生活中的一次“交互事件”。定义E_n为第n个周期内的所有交互事件的集合，如果用户u与用户v在第n个周期，地点l，时间步t有一次时间空间共现，则交互事件e_n＝(u,v,t,l)∈E_n。

对于每一对拥有至少一次交互事件的用户对(u,v)，构建交互矩阵其中，u为用户集U中的第u个用户，v为用户集U中的第v个用户，l表示地点集L中的第l个地点。交互矩阵M_u,v的元素为一个二元组表示交互权重，表示交互支持度，其中，和可通过如下式(1)、(2)计算:

通过如下式(3)计算用户时空交互矩阵的规律度d_r(u,v)：

通过如下式(4)计算用户时空交互矩阵的时空熵d_e(u,v)：

构建零假设：用户个体行为不受他人的影响，用户个体行为不具有周期偏向性。根据零假设，建立用户个体行为和用户间时空交互矩阵的零模型，即每个周期内的随机用户行为矩阵和随机时空交互矩阵。

根据所述用户行为矩阵计算个体活跃度。用户活跃度表示用户在一个周期内访问一个时空栅格的概率。根据用户行为矩阵建立用户-时空栅格二部图；所述用户-时空栅格二部分图包括：所述用户集中表示每个用户的节点，表示每个时空栅格(t,l)的节点以及存在行为记录的用户和时空栅格之间的连边。用户行为矩阵中的元素时，用户u与时空栅格(t,l)存在连边。

利用保留度的连边交换法随机化用户-时空栅格二部图，得到随机用户-时空栅格二部图。该方法保留每个节点的度不变，节点和连边的数量不变。

根据所述个体活跃度与所述随机用户-时空栅格二部图，重建每个周期内的所述用户个体行为矩阵和用户间时空交互矩阵的零模型，包括：随机用户行为矩阵随机时空交互矩阵随机规律度和随机时空熵

统计零模型中时空熵与规律度的概率分布，并通过预置概率p₀确定时空熵和规律度的零阈值，包括：

预置概率p₀，其中p₀远小于1。

根据所述零模型中时空熵与规律度的概率分布，确定时空熵零阈值e₀和规律度零阈值r₀。其中所述时空熵零阈值e₀满足所述规律度零阈值r₀满足

通过比较真实用户交互矩阵的在时空熵和规律度两个维度上与其零阈值之间的大小关系，确定两用户间的线下社会关系(熟悉的陌生人FS(familiar stranger)，熟人F&IR(包括朋友friend和同事in-role)，陌生人S(stranger))，包括：

若用户交互矩阵的时空熵小于时空熵随机阈值，规律度大于规律度随机阈值,则确定用户间线下社会关系为熟悉的陌生人。若用户交互矩阵的时空熵小于时空熵随机阈值，规律度大于规律度随机阈值，则确定用户间线下社会关系为熟悉的陌生人FS。若用户交互矩阵的时空熵大于时空熵随机阈值，则确定用户间线下社会关系为熟人关系F&IR，其中，若规律度大于规律度随机阈值，则确定用户间线下社会关系为熟人关系中的同事/同学等职业关系IR，若规律度小于规律度随机阈值，则确定用户间线下社会关系为熟人关系中的朋友关系F。

本发明步骤(3)中，所述以用户为节点，两用户间的社会关系类型为连边(不考虑陌生人关系)，构建用户社会关系网络，包括：

每一个用户u作为节点，两用户间的社会关系类型作为连边e，若两用户间的社会关系类型为熟人或熟悉的陌生人关系，则认为该两用户间存在一条连边，连边类型对应社会关系的类型，由此构建用户社会关系网络G＝(U,ε)，其中U为用户集合，ε为连边集合。

本发明步骤(4)中，所述利用用户个体行为记录，构建用户按时间顺序的离散移动轨迹序列，包括：

根据用户行为中的时间数据，确定离散化时间步长度ΔT；对于用户的行为记录，若用户在一个离散化时间步内存在多条记录，则选取访问持续时间最长或访问次数最多的地点作为该离散化时间步的地点，由此构建用户的离散移动轨迹序列。

本发明步骤(5)中，所述利用杰卡德系数生成社会关系子图，包括：

定义Γ(u)和Γ(v)分别为用户u和v的熟人关系邻居集合，通过如下式(5)计算每个用户与其所有社会关系的杰卡德系数(Jarccard’s coefficient)J：

定义用户的n阶社会关系子图为被预测用户的前n个最重要(即移动轨迹最相似)的社会关系个体类型。

将每个用户的社会关系按杰卡德系数从大到小排序取前n个个体由此得到每个用户的n阶社会关系子图。

本发明步骤(5)中，所述通过度保留断边重连的方法生成随机化用户社会关系网络，构建零模型，包括：

给定一个实际社会关系网络G＝(U,ε)，对于社会关系连边集合ε中的一条连边e_st，随机选择一条相同社会关系类型的连边，例如对于连边则随机选择另一条连边

以概率将两条连边(u,v,FS)和(u′,v′,FS)替换为(u,v′,FS)和(u′,v,FS)，否则将它们替换为(u,u′,FS)和(v,v′,FS)。若该断边重连的过程产生了自环边或重边，则终止该次断边重连操作。重复以上过程直至所有连边已被重连过，则获得一个随机社会关系网络。

生成如上的100个随机社会关系网络作为零模型。

本发明步骤(5)中，所述比较各社会关系子图在真实网络和零模型下统计指标z值的大小关系，确定用户群体社会关系模体，包括：

对于某子图类型m，C(m)表示子图m在真实网络中的出现频次，为子图m在真实网络所对应随机网络中的出现频次，μ(*)和σ(*)分别为计算均值和标准差操作，定义描述子图重要性的指标z值为：

分别统计每种类型的社会关系子图在真实网络和零模型所生成的随机网络下的z值，若某种子图的z值显著大于0，则被确定为用户群体社会关系模体。

本发明步骤(6)中，所述利用杰卡德系数生成该用户的社会关系子图，同步骤(3)，即将每个用户的社会关系按杰卡德系数从大到小排序取前n个个体得到每个用户的n阶社会关系子图。

本发明步骤(6)中，所述比较该用户个体社会关系子图是否为前述社会关系模体，若是则通过验证，反之则不通过，包括：

将该用户生成的社会关系子图与步骤(5)中得到的社会关系模体相比较，若该社会关系子图为步骤(5)中的社会关系模体，则通过验证，反之则不通过验证。

本发明步骤(7)中，所述建立马尔可夫预测器、熟人预测器、熟悉的陌生人预测器和输出调节器，包括：

在马尔可夫预测器中，用随机变量X_t表示一个个体于离散时间步t所在的地点，随机变量所有可能的状态{x₁,x₂,…,x_t+1}均可从实际数据中检测，每个状态x_t∈{1,2,…,L}为地点编号，L为不同地点的总数目，那么用户的移动轨迹用一阶马尔可夫链来进行建模，即用户的下一个地点只依赖于前一个访问的地点，可表示为：

P_M(X_t+1＝x_t+1|X_t＝x_t,X_t-1＝x_t-1,…,X₁＝x₁)＝P_M(X_t+1＝x_t+1|X_t＝x_t)>

给定用户u在离散时间步t-1的地点以及从历史地点数据中提取到的一阶马尔可夫转移矩阵，可得到该用户u在离散时间步t的马尔可夫地点访问概率向量：

在熟人预测器中，用户受到其熟人关系F&IR的驱使在短时间内朝向其熟人关系所在的位置进行移动。

假设用户u在离散时间步t+1的位置将被预测，给定用户u的某个熟人关系v在离散时间步t的地点l并且v从时间步t到t+1始终位于地点l，用表示用户u在离散时间步t+1访问地点l，表示用户u和用户v在离散时间步t+1于地点l相遇的概率，表示用户v从时间步t到t+1始终位于地点l的概率，那么用户u在离散时间步t+1将会访问地点l的条件概率可表示为：

给定用户u的熟人关系集合S_F&IR＝{v₁,v₂,…,v_K}，用w_i表示用户u和用户v_i的归一化交互频率那么用户u在离散时间步t+1访问地点l的概率可表示为：

获得用户u在时间步t访问每个地点的概率后，可得用户u在离散时间步t的地点访问概率向量其中归一化过程将被应用以确保

在熟悉的陌生人预测器中，由于用户与其熟悉的陌生人交互的显著周期性，用户的访问地点可由其熟悉的陌生人关系来复现。

如步骤(2)所述，在每一个周期n中，用户u的行为矩阵可构建为其中，u为用户集U中的第u个用户，n为N个周期中的第n个周期，l表示地点集L中的第l个地点。行为矩阵S_n(u)中的元素为0或1。用户u的累积行为矩阵可表示为用表示用户v在时间步t访问地点l的累积次数，那么用户v在时间步t访问地点l的概率可以表示为：

给定用户u的熟悉的陌生人关系集合S_FS＝{v₁,v₂,…,v_K}，用w_i表示用户u和用户v_i的归一化交互频率那么用户u在离散时间步t访问地点l的概率可表示为：

获得用户u在时间步t访问每个地点的概率后，可得用户u在离散时间步t的地点访问概率向量其中归一化过程将被应用以确保

在输出调节器中，利用多元线性回归模型对马尔可夫预测器、熟人预测器和熟悉的陌生人预测器的输出进行加权融合。设α、β和γ为权重参数，且α+β+γ＝1，那么最终输出地点访问概率向量P_aggr可表示为：

P_aggr＝αP_M+βP_F&IR+γP_FS>

用P_real表示用户实际的地点访问概率向量，则权重参数可通过最小化损失函数J获得：

对于用户u，若其可通过发明步骤(4)中的社会关系模体验证，则只需使用马尔可夫预测器、熟悉的陌生人预测器和输出调节器得到最终预测输出，即令参数β＝0，否则需要完整利用马尔可夫预测器、熟人预测器、熟悉的陌生人预测器和输出调节器得到最终预测输出，即参数β不一定为0。

另一方面，本发明还提供自动推断社会关系的移动用户位置预测装置，包括：

(1)用户个体行为记录获取模块，用于从用户移动行为日志数据库中，获取用户个体行为记录，得到用户集U，地点集L。每条用户行为记录包括用户ID，开始时间，持续时间，地点。

(2)用户间社会关系类型推断模块，用于利用所述用户个体行为记录，建立用户间时空交互矩阵，提取时空熵和规律度，建立零模型，通过预置概率p确定零阈值，对用户间社会关系推断。

(3)用户社会关系网络建立模块，用于以用户为节点，两用户间的社会关系类型为连边(不考虑陌生人关系)，构建用户社会关系网络。

(4)用户移动轨迹序列建立模块，用于利用所述用户个体行为记录，构建用户按时间顺序的离散移动轨迹序列。

(5)用户群体社会关系模体检测模块，用于利用杰卡德系数生成社会关系子图；通过随机断边重连的方法生成随机化用户社会关系网络，构建零模型；比较各社会关系子图在真实网络和零模型下统计指标z值的大小关系，确定用户群体社会关系模体。

(6)用户个体社会关系模体验证模块，用于利用杰卡德系数生成该用户的社会关系子图；比较该用户个体社会关系子图是否为前述社会关系模体，若是则通过验证，反之则不通过。

(7)位置预测器建立模块，用于分别建立马尔可夫预测器、熟人预测器、熟悉的陌生人预测器和输出调节器；若该个体通过社会关系模体验证，则只需利用马尔可夫预测器、熟悉的陌生人预测器和输出调节器来预测该用户的未来位置，若未通过验证，则需要马尔可夫预测器、熟人预测器、熟悉的陌生人预测器和输出调节器预测该用户的未来位置。

上述七个模块，具体执行本发明预测方法的七个步骤的操作。其中：

所述用户个体社会关系模体验证模块，包括：

社会关系子图生成子模块，用于利用杰卡德系数生成该用户的社会关系子图；

社会关系模体验证子模块，用于比较该用户个体社会关系子图是否为前述社会关系模体，若是则通过验证，反之则不通过。

所述位置预测器建立模块，包括：

马尔可夫预测器建立子模块，用于利用用户历史位置信息预测用户未来位置；

熟人预测器建立子模块，用于利用用户的熟人关系预测用户未来位置；

熟悉的陌生人预测器建立子模块，用于利用用户的熟悉的陌生人关系预测用户未来位置；

输出调节器建立子模块，用于对马尔可夫预测器建立子模块、熟人预测器建立子模块和熟悉的陌生人预测器建立子模块的输出进行融合，得到最终预测输出。

本发明提供的技术方案将有如下优点：

本发明所提供的自动推断社会关系的移动用户位置预测方法与装置，在传统的通过用户历史轨迹信息和熟人社会关系预测用户位置的基础上，首次将“熟悉的陌生人”关系引入位置预测方法，提高了位置预测的准确性，为位置预测方法设计提供了新的思路。本发明通过定义并挖掘用户社会关系模体，异质处理不同类型的用户，在减小了计算代价的同时提高整体的预测性能。本发明基于利用用户线下行为数据直接推断到的不同类型的社会关系，不需要专门额外采集用户社会关系数据，减少了预测所需的原始数据信息，很好地保护了用户的个人隐私，降低了数据获取的难度。本发明所提供的方法适用于Wi-Fi等地理分辨率较高的场景，有别于传统方法多依赖于基站、POI等地理分辨率较低的场景，可做到对细粒度地理位置进行较好地预测。

附图说明

图1为本发明实施例提供的一种自动推断社会关系的移动用户位置预测方法的流程方框示意图。

图2为本发明实施例提供的一种用户移动行为日志数据样例图。

图3为本发明实施例提供的一种用户社会关系类型判定示意图。

图4为本发明实施例提供的一种社会关系网络生成示意图。

图5为本发明实施例提供的一种用户社会关系子图示意图。

图6为本发明实施例提供的一种自动推断社会关系的移动用户位置预测装置的组成结构示意图。

图7为本发明实施例提供的用户间社会关系类型推断模块的组成结构示意图。

图8为本发明实施例提供的用户时空交互矩阵建立模块的组成结构示意图。

图9为本发明实施例提供的零模型建立及零阈值选取模块的组成结构示意图。

图10为本发明实施例提供的用户群体社会关系模体检测模块的组成结构示意图。

图11为本发明实施例提供的用户个体社会关系模体验证模块的组成结构示意图。

图12为本发明实施例提供的位置预测器建立模块的组成结构示意图。

具体实施方式

为使本申请的目的、技术方案和优点更加清楚明白，下文中将结合附图，以国内某高校无线网络登录行为日志数据为例，对本申请的发明实施例进行详细说明。

图1为本发明自动推断社会关系的移动用户位置预测方法的流程方框示意图，如图1所示，包括：

步骤100、从用户移动行为日志数据库中，获取用户的个体行为记录，包括用户ID、接入时间、持续时间、地点ID。

以国内某大学采集的无线网络登录行为日志数据为例，校园内的无线网络登录行为日志由学校信息办采集并存储，记录了校园内所有使用校园无线网络的用户的无线网络登录行为，原始数据格式如图2所示。每条数据记录包括用户ID、接入起始时间、接入持续时间、接入地点ID。在本套数据集中，所有不同的无线热点(AP)构成了地点集合。由于无线热点覆盖范围较小，用户往往自动连接与其距离最近的无线热点，因此，当用户从一个地点移至另一个地点时，其接入的无线热点也会自动切换。每条无线网络登录记录刻画了用户接入无线网络的时间和地点，而一个用户的一系列无线网络登录记录则刻画了该用户的移动行为。

本实施例中，步骤100从用户移动行为日志数据库中，获取用户个体行为记录，得到用户集U，地点集L。每条数据记录包括用户ID、接入起始时间、接入持续时间、接入地点ID。原始数据格式如图2所示，每条记录以四元组(u,t_a,δt,l)的形式表示，其中u表示用户集U中的用户编号，t_a为接入起始时间，δt为接入持续时间，l为地点集L中的地点(无线热点)编号。

步骤101、利用所述用户个体行为记录推断两用户间的社会关系类型，包括熟悉的陌生人，熟人和陌生人，详见中国专利“一种基于用户移动行为的线下社会关系分类方法及装置”(专利号201611264316.7)，具体包括如下步骤：

(1)利用所述用户个体行为记录，建立用户间时空交互矩阵。

首先根据用户行为记录中的时间数据，确定用户行为周期T，离散化时间步长度ΔT，其中，所述用户行为周期T将日志数据中的整个时间轴划分为N个周期。通过统计用户返回相同地点的时间间隔的概率分布(该概率分布是在整个用户集上的概率分布)，找到在概率上显著突出的时间间隔，即可视为用户行为周期T。通常，人类的行为周期为1天或7天。在该实施例中，T＝7天。T将观测记录的整个时间轴划分为N个周期。另一方面，为了充分挖掘用户移动移动行为的时间，空间模式以便后续分析，需要将连续的时间轴离散化，确定离散化时间步长度ΔT可以简化用户移动行为的表示，将连续的时间离散为长度为ΔT的时间段。ΔT的选取需依照具体数据而定，通常需要ΔT即能够去除数据中的一些噪声，又能够充分表现出用户行为的变化。在该实施例中，取ΔT＝3小时。

对于每一个周期n，构建用户u的行为矩阵其中，n为上段所述N个周期中的第n个周期；t属于表示第n个周期中的第t个时间步，其中ΔT为上段所述时间步长度，它将一个周期分为个时间步；l表示地点集L中的第l个地点。所述用户行为矩阵S_n(u)的行数为(一个周期内的时间步数量)，列数为地点集L中的地点总数量|L|。S_n(u)中的元素为1或0，当用户u存在一条行为记录发生在地点l，第n个周期的时间步t时，否则，需要说明的是，一个周期内的用户行为矩阵相当于将一个周期内的时间和空间划分为个时空栅格，每个时空栅格可由二元组(t,l)表示，表示用户在该周期内访问了时空栅格(t,l)。

根据时间空间共现建立两两用户间时空交互矩阵。所述时间空间共现表示用户u与用户v在同一个地点l拥有时间重合的行为记录。时间空间共现代表用户u与用户v在实际生活中的一次“交互事件”。定义E_n为第n个周期内的所有交互事件的集合，如果用户u与用户v在第n个周期，地点l，时间步t有一次时间空间共现，则交互事件e_n＝(u,v,t,l)∈E_n。

对于每一对拥有至少一次交互事件的用户对(u,v)，构建交互矩阵其中u为所述用户集U中的第u个用户，v为所述用户集U中的第v个用户，t属于表示第n个周期中的第t个时间步，l表示地点集L中的第l个地点。所述交互矩阵M_u,v的行数为(一个周期内的时间步数量)，列数为地点集L中的地点总数量|L|。交互矩阵M_u,v相当于将一个周期内的时间和空间划分为个时空栅格，每个时空栅格可由(t,l)表示。M_u,v的元素为一个二元组为交互权重，表示用户u和v在时空栅格(t,l)发生交互事件的周期数目，为交互支持度，表示用户u和v在时间-地点栅格(t,l)发生交互事件的概率。其中和可通过如下方式计算:

交互权重体现了两个用户(u,v)发生交互事件时，对时空栅格(t,l)的偏爱程度，交互支持度表示当u,v相互独立时，在时空栅格(t,l)产生一次交互事件的概率。当用户时空栅格(t,l)的行为周期性越强时，交互支持度则越大。

(2)对于每对用户的时空交互矩阵，提取两个交互特性：时空熵和规律度。其中时空熵用于衡量两个用户间的社会相似性，规律度用于衡量两个用户间交互事件产生的周期化程度。

通过如下方式计算用户时空交互矩阵的规律度d_r(u,v)：

通过如下方式计算用户时空交互矩阵的时空熵d_e(u,v)：

(3)建立零模型，通过预置概率p确定零阈值。

为了通过时空熵和规律度两个交互特性区分不同的社会关系，需要建立零假设用户间时空交互矩阵的零模型，得到零模型下的时空熵和规律度分布。

通过对用户个体行为的随机化处理，建立用户个体行为和用户间时空交互矩阵的零模型：每个周期内的随机用户行为矩阵和随机时空交互矩阵，根据零模型及预置概率确定时空熵随机阈值和规律度随机阈值，具体包括如下步骤：

(a)根据所述用户行为矩阵计算个体活跃度，所述用户活跃度表示用户在一个周期内访问一个时空栅格的概率。根据所述用户行为矩阵建立用户-时空栅格二部图G_US，所述用户-时空栅格二部分图包括：所述用户集中表示每个用户的节点，表示每个时空栅格(t,l)的节点以及存在行为记录的用户和时空栅格之间的连边。所述用户行为矩阵中的元素时，用户u与时空栅格(t,l)存在连边。

在计算个体活跃度时，定义L(u)为用户u访问过的所有地点集合，结合步骤100中的用户行为矩阵，用户活跃度act(u)可由下式计算：

在建立用户-时空栅格二部图时，遍历每个周期下的用户行为矩阵若存在元素则用户u与时空栅格(t,l)存在连边。

(b)利用保留度的连边交换法随机化用户-时空栅格二部图G_US，得到随机用户-时空栅格二部图该方法保留每个节点的度不变，节点和连边的数量不变。

在随机化用户-时空栅格二部图时，使用保留度的连边交换法。该方法随机选取二部图中的两条连边(u,(t1,l1)),(v,(t2,l2))进行交互，得到新的连边(u,(t2,l2)),(v,(t1,l1))，将新连边添加到二部图中，并删除原来的两条连边。当进行足够过次的连边交换后，随机化过程完成。经随机化后的用户-时空栅格二部图拥有与原图相同的节点数量，连边数量和节点度，也就是说，每个用户节点连接与原图相同数量的时空栅格节点，每个时空栅格节点连接与原图数量相同的用户节点。这样的方法保证了原本活跃的节点依然活跃，原本被访问数量多的时空栅格依然被访问数量多。随机用户-时空栅格二部图用表示。

在该步骤中，每个用户的用户-时空栅格二部图随机化过程是独立的，保证了随机化后用户连接的时空栅格不受其社会关系的影响，满足了零假设中的第一个假设。

(c)根据所述(a)中个体活跃度与(b)中所述随机用户-时空栅格二部图与重建每个周期内的所述用户个体行为矩阵和用户间时空交互矩阵的随机化模型，包括：随机用户行为矩阵随机时空交互矩阵随机规律度和随机时空熵

在建立随机用户行为矩阵时，对于每一个周期n，如果随机用户-时空栅格二部图中存在连边(u,(t,l))，则中元素以概率act(u)置为1，否则为0。该步骤使每个周期下，用户对每个可连接的时空栅格的连接概率相同，不存在周期性时空偏向的情况，满足零假设中的第二个假设。

在建立随机时空交互矩阵时，首先建立每个周期的随机交互事件集对于随机用户行为矩阵和中的元素，如果则随机交互事件

相应的，根据所述(1)中的交互矩阵定义，可以得到随机交互矩阵M_u,v的元素为一个二元组计算如下：

其中为随机用户行为矩阵元素

根据所述(1)中的交互特性计算方法，可以通过下式计算随机规律度和随机时空熵

其中为随机交互矩阵元素。

(d)预置概率p₀，其中p₀远小于1。根据所述零模型下规律度和随机时空熵概率分布，确定时空熵零阈值e₀和规律度零阈值r₀。其中e₀满足r₀满足通常p₀的取值小于0.001以保证足够的置信度，当p₀足够小时，意味着在在完全随机的情况下，用户交互矩阵的规律度或时空熵几乎不可能大于他们所对应的零阈值，在现实场景中，如果用户间的交互特性出现大于零阈值的情况，是由于他们之间的某种非随机的社会关系所导致的。

(4)通过比较用户交互矩阵在时空熵和规律度两个维度上与其随机阈值之间的大小关系，包括熟悉的陌生人FS(familiar stranger)，熟人F&IR(朋友friend和职业关系in-role)，陌生人S(stranger)。

在本实施例中，两用户社会关系类型判定示意图如图3所示。

若用户交互矩阵的时空熵d_e(u,v)小于时空熵零阈值e₀，规律度d_r(u,v)小于规律度零阈值r₀，则确定用户间社会关系为陌生人关系；若用户交互矩阵的时空熵小于时空熵零阈值，规律度大于规律度零阈值，则确定用户间社会关系为熟悉的陌生人关系；若用户交互矩阵的时空熵大于时空熵零阈值，规律度小于规律度零阈值，则确定用户间社会关系为朋友关系；若用户交互矩阵的时空熵大于时空熵零阈值，规律度大于规律度零阈值，则确定用户间社会关系为同事/同学等职业关系。

步骤102、以用户为节点，两用户间的社会关系类型为连边(不考虑陌生人关系)，构建用户社会关系网络。

将用户集U中的每一个用户u作为节点，利用步骤101中所获取到的两用户间的社会关系类型作为连边e。由于对于一对互为陌生人关系的用户对来说，他们之间只发生过一次交互，对于双方的位置预测来说没有实质性的帮助，因此这里将不考虑陌生人关系S。如果两用户间的社会关系类型为熟人关系F&IR或者熟悉的陌生人关系FS，则该两用户间认为存在一条社会关系连边，该条连边的类型对应该两用户社会关系的类型，由此构建用户社会关系网络G＝(U,ε)，其中U为用户集合，ε为连边集合。社会关系网络的生成示例图见图4。以国内某大学采集的无线网络登录行为日志数据为例，生成的社会关系网络规模为10146个节点，5182743条连边。

步骤103、利用所述用户个体行为记录，构建用户按时间顺序的离散移动轨迹序列。根据步骤101所述，利用用户行为数据可确定离散化时间步长度ΔT。在该实施例中，取ΔT＝3小时。根据用户的原始行为记录，若用户在一个离散化时间步内存在多条记录，则选取访问持续时间最长或访问次数最多的地点作为该离散化时间步的地点。例如某用户u在某离散化时间步内分别在地点l₁、l₂和l₃访问53分钟、28分钟和1小时，那么在构建该用户的离散移动轨迹序列时，该用户在该离散化时间步内的访问地点即选取l₃。由此得到每个用户的离散移动轨迹序列。在本实施例中，由于数据集的时间跨度为84天

步骤104、利用杰卡德系数生成社会关系子图；通过随机断边重连的方法生成随机化用户社会关系网络，构建零模型；比较各社会关系子图在真实网络和零模型下统计指标z值的大小关系，确定用户群体社会关系模体。

本实施例中，具体包括如下步骤：

(1)利用杰卡德系数生成社会关系子图。首先定义用户的n阶社会关系子图为被预测用户的前n个最重要(即移动轨迹最相似)的社会关系个体类型，示例图见图5。图5所示为3阶社会关系子图的四种不同形式，其中每个子图的中心节点为待预测位置的用户，其所连接的3个节点为该待预测位置用户的前3个最重要(即移动轨迹最相似)的用户，连边类型对应该用户对的社会关系类型。杰卡德系数是社会网络研究中一种刻画用户间社会邻近程度的代表性指标，其与用户对的轨迹相似度呈现明显的正相关性，同时计算杰卡德系数相比直接计算用户对的轨迹相似度具有更低的计算复杂度。因此，利用杰卡德系数挖掘用户的前n个最重要的社会关系个体。定义Γ(u)和Γ(v)分别为用户u和v的熟人关系F&IR邻居集合，通过如下方式计算每个用户与其所有社会关系的杰卡德系数(Jarccard’scoefficient)J：

将每个用户的社会关系按杰卡德系数从大到小排序取前n个个体由此得到每个用户的n阶社会关系子图。

(2)通过度保留断边重连的方法生成随机化用户社会关系网络，构建零模型。给定一个实际社会关系网络G＝(U,ε)，零模型的生成步骤可表示为：

(a)对于社会关系连边集合ε中的一条连边e_st，随机选择一条相同社会关系类型的连边，例如对于连边则随机选择另一条连边

(b)以概率将两条连边(u,v,FS)和(u′,v′,FS)替换为(u,v′,FS)和(u′,v,FS)，否则将它们替换为(u,u′,FS)和(v,v′,FS)；

(c)若步骤(b)断边重连的过程产生了自环边或重边，则终止该次断边重连操作。重复以上过程直至所有连边已被重连过，则获得一个随机社会关系网络；

(d)生成如上的100个随机社会关系网络作为零模型。

(3)比较各社会关系子图在真实网络和零模型下统计指标z值的大小关系，确定用户群体社会关系模体。一般来说，在真实网络和随机网络中统计数目呈现显著差异的子图被认为是模体，而z值即为模体研究中刻画子图数目在真实网络和随机网络中差异是否显著的一种代表性指标。对于某子图类型m，C(m)表示子图m在真实网络中的出现频次，为子图m在真实网络所对应随机网络中的出现频次，μ(*)和σ(*)分别为计算均值和标准差操作，定义描述子图重要性的指标z值为：

分别统计每种类型的社会关系子图在真实网络和零模型所生成的随机网络下的z值，若某种子图的z值显著大于0，则被确定为用户群体社会关系模体。

在本实施例中，以3阶社会关系子图为例(示例图见图5)，统计得到的4种不同类型的社会关系子图的z值如下表所示：

由于3阶社会关系子图③和④的z值显著大于0，因此，在本实施例中，3阶社会关系子图③和④即为用户群体的社会关系模体，并且3阶社会关系子图③和④均由熟悉的陌生人关系所主导(3阶子图的3条连边中熟悉的陌生人关系占多数或全部)。

步骤105、利用杰卡德系数生成该用户的社会关系子图；比较该用户个体社会关系子图是否为前述社会关系模体，若是则通过验证，反之则不通过。

首先同步骤104中所述，即将该用户的社会关系按杰卡德系数从大到小排序取前n个个体得到每个用户的n阶社会关系子图，在本实施例中，n取3，即生成该用户的3阶社会关系子图。

将上述该用户的3阶社会关系子图与步骤104中所确定的用户群体社会关系模体(在本实施例中即3阶社会关系子图③和④)相比较，若该用户的3阶社会关系子图为社会关系模体中的一种，那么则通过验证，否则验证不通过。

步骤106、分别建立马尔可夫预测器、熟人预测器、熟悉的陌生人预测器和输出调节器；若该个体通过社会关系模体验证，则只需利用马尔可夫预测器、熟悉的陌生人预测器和输出调节器来预测该用户的未来位置，若未通过验证，则需要马尔可夫预测器、熟人预测器、熟悉的陌生人预测器和输出调节器预测该用户的未来位置。具体包括如下步骤：

(1)建立马尔可夫预测器。马尔可夫预测器利用用户历史的位置信息预测将来的位置。在马尔可夫预测器中，用户的移动轨迹序列可以用一个一阶马尔可夫链来建模，也就是说用户的下一个访问地点仅依赖于前一个访问的地点。用随机变量X_t表示一个个体于离散时间步t所在的地点，随机变量所有可能的状态{x₁,x₂,…,x_t+1}均可从实际数据中检测，每个状态x_t∈{1,2,…,L}为地点编号，L为不同地点的总数目，可表示为：

P_M(X_t+1＝x_t+1|X_t＝x_t,X_t-1＝x_t-1,…,X₁＝x₁)＝P_M(X_t+1＝x_t+1|X_t＝x_t)

给定用户u在离散时间步t-1的地点以及从历史地点数据中提取到的一阶马尔可夫转移矩阵，可得到该用户u在离散时间步t的马尔可夫地点访问概率向量

(2)建立熟人预测器。熟人预测器基于用户具有在短时间内朝向其熟人关系当前所在位置移动的显著倾向的事实来设计。例如若某用户的某个朋友在食堂地点吃饭，那么该用户很有可能会为了与其朋友一起吃饭而移动至其朋友关系当前所在的位置。

假设用户u在离散时间步t+1的位置将被预测，给定用户u的某个熟人关系v在离散时间步t的地点l并且v从时间步t到t+1始终位于地点l，用表示用户u在离散时间步t+1访问地点l，表示用户u和用户v在离散时间步t+1于地点l相遇的概率，表示用户v从时间步t到t+1始终位于地点l的概率，那么用户u在离散时间步t+1将会访问地点l的条件概率可表示为：

给定用户u的熟人关系集合S_F&IR＝{v₁,v₂,…,v_K}，用w_i表示用户u和用户v_i的归一化交互频率那么用户u在离散时间步t+1访问地点l的概率可表示为：

即该用户在离散时间步t+1访问地点l的概率为其每个好友关系施加影响的加权和。

获得用户u在时间步t访问每个地点的概率后，可得用户u在离散时间步t的地点访问概率向量在本实施例中，由于该概率向量之和不一定为1，为了之后计算的方便，在这里将应用一个归一化过程以确保

(3)建立熟悉的陌生人预测器。用户与其熟悉的陌生人关系交互(即地理相遇)具有显著的周期性特点，他们会在某些固定的地点进行频繁地周期性交互，因此，通过用户的熟悉的陌生人关系群体，可以反向复现出该用户的部分移动轨迹信息。

如发明步骤(2)所述，在每一个周期n中，用户u的行为矩阵可构建为其中，u为用户集U中的第u个用户，n为N个周期中的第n个周期，l表示地点集L中的第l个地点。行为矩阵S_n(u)中的元素为0或1。用户u的累积行为矩阵可表示为用表示用户v在时间步t访问地点l的累积次数，那么用户v在时间步t访问地点l的概率可以表示为：

给定用户u的熟悉的陌生人关系集合S_FS＝{v₁,v₂,…,v_K}，用w_i表示用户u和用户v_i的归一化交互频率那么用户u在离散时间步t访问地点l的概率可表示为：

获得用户u在时间步t访问每个地点的概率后，可得用户u在离散时间步t的地点访问概率向量在本实施例中，由于该概率向量之和不一定为1，为了之后计算的方便，在这里将应用一个归一化过程以确保

(4)建立输出调节器。根据步骤106所述(1)(2)(3)部分已可获得马尔可夫预测器、熟人预测器和熟悉的陌生人预测器的三个地点访问概率向量，为了得到最终唯一的地点访问概率向量输出，需要对上述的三个地点访问概率向量进行融合。

利用多元线性回归模型对马尔可夫预测器、熟人预测器和熟悉的陌生人预测器的输出进行加权融合。设α、β和γ为权重参数，且α+β+γ＝1，那么最终输出地点访问概率向量P_aggr可表示为：

P_aggr＝αP_M+βP_F&IR+βP_FS

用P_real表示用户实际的地点访问概率向量，则权重参数可通过最小化损失函数J获得：

对于用户u，若其可通过发明步骤(4)中的社会关系模体验证，则只需使用马尔可夫预测器、熟悉的陌生人预测器和输出调节器得到最终预测输出，即令参数β＝0，否则需要完整利用马尔可夫预测器、熟人预测器、熟悉的陌生人预测器和输出调节器得到最终预测输出，即参数β不一定为0。

在本实施例中，将原始数据按时间先后顺序划分50％为训练集，50％为测试集，训练集用于训练得到权重参数α、β和γ，测试集用于测试预测方法的性能。在本实施例中，方法的评价指标为预测准确率，用户u的预测准确率用ζ_u表示，即：

其中若用户u的第i次预测是正确的，也就是说用户u确实访问了所预测的地点，那么η_i＝1，否则η_i＝0。本实施例对每个用户做时间长度为1周的预测。

本实施例设计3个基线方法以作对比评价，分别为：

(a)基线方法1：一阶马尔可夫链预测方法

(b)基线方法2：结合一阶马尔可夫链和熟人关系的预测方法

(c)基线方法3：结合一阶马尔可夫链和熟悉的陌生人关系的预测方法

本实施例所提供的自动推断社会关系的移动用户位置预测方法和3个基线方法的预测结果比较如下：

可以看到本发明所提供的自动推断社会关系的移动用户位置预测方法相比3种基线方法预测准确率最高，效果最好。

为便于更好的实施本发明实施例的上述方案，下面还提供用于实施上述方案的相关装置。

请参阅图6所示，本发明实施例提供的一种自动推断社会关系的移动用户位置预测装置600，可以包括：用户个体行为记录获取模块601、用户间社会关系类型推断模块602、用户社会关系网络建立模块603、用户移动轨迹序列建立模块604、用户群体社会关系模体检测模块605、用户个体社会关系模体验证模块606和位置预测器建立模块607。

用户个体行为记录获取模块601，用于从用户移动行为日志数据库中，获取用户个体行为记录，得到用户集U，地点集L。每条用户行为记录包括用户ID，开始时间，持续时间，地点；

用户间社会关系类型推断模块602，用于利用所述用户个体行为记录，建立用户间时空交互矩阵，提取时空熵和规律度，建立零模型，通过预置概率p确定零阈值，对用户间社会关系类型进行推断；

用户社会关系网络建立模块603，用于以用户为节点，两用户间的社会关系类型为连边(不考虑陌生人关系)，构建用户社会关系网络；

用户移动轨迹序列建立模块604，用于利用所述用户个体行为记录，构建用户按时间顺序的离散移动轨迹序列；

用户群体社会关系模体检测模块605，用于利用杰卡德系数生成社会关系子图；通过随机断边重连的方法生成随机化用户社会关系网络，构建零模型；比较各社会关系子图在真实网络和零模型下统计指标z值的大小关系，确定用户群体社会关系模体；

用户个体社会关系模体验证模块606，用于利用杰卡德系数生成该用户的社会关系子图；比较该用户个体社会关系子图是否为前述社会关系模体，若是则通过验证，反之则不通过；

位置预测器建立模块607，用于分别建立马尔可夫预测器、熟人预测器、熟悉的陌生人预测器和输出调节器；若该个体通过社会关系模体验证，则只需利用马尔可夫预测器、熟悉的陌生人预测器和输出调节器来预测该用户的未来位置，若未通过验证，则需要马尔可夫预测器、熟人预测器、熟悉的陌生人预测器和输出调节器预测该用户的未来位置。

在本发明的实施例中，请参阅图7所示，所述用户间社会关系类型推断模块602，包括：

用户间时空交互矩阵建立和交互特性提取子模块6021，用于利用所述用户个体行为记录，建立用户间时空交互矩阵，提取时空熵和规律度；

零模型建立及交互特性零阈值选取子模块6022，用于建立零模型，通过预置概率p确定零阈值；

用户间线下社会关系类型判定子模块6023，用于通过比较用户真实交互矩阵时空熵和规律度与其零阈值之间的大小关系，确定两用户间的线下社会关系；

在本发明的实施例中，请参阅图8所示，所述用户间时空交互矩阵建立和交互特性提取子模块6021，包括：

用户交互事件建立子模块60211，用于根据时空共现确定用户间的所有交互事件，建立交互事件集合；

时空交互矩阵建立子模块60212，用于对拥有至少一次交互事件的两个用户建立用户间的时空交互矩阵，其中每个矩阵元素为一个二元组，共同描述交互的权重与概率；

交互特性提取子模块60213，用于根据用户间的时空交互矩阵提取交互特性，包括时空熵与规律度；

在本发明的实施例中，请参阅图9所示，所述零模型建立及零阈值选取模块6022，包括：

用户个体行为随机化子模块60221，用于对用户行为进行随机化处理，得到随机用户行为矩阵；

随机时空交互矩阵建立子模块60222，用于根据随机用户行为矩阵简历用户间随机时空交互矩阵；

交互特性零阈值提取子模块60223，用于提取零模型下的时空熵与规律度，统计其概率分布，并通过预置概率p₀确定时空熵零阈值和规律度零阈值；

在本发明的实施例中，请参阅图10所示，所述用户群体社会关系模体检测模块605，包括：

用户社会关系子图生成子模块6051，用于利用杰卡德系数生成社会关系子图；

零模型建立子模块6052，用于通过随机断边重连的方法生成随机化用户社会关系网络，构建零模型；

用户社会关系模体确定子模块6053，用于比较各社会关系子图在真实网络和零模型下统计指标z值的大小关系，确定用户群体社会关系模体；

在本发明的实施例中，请参阅图11所示，所述用户个体社会关系模体验证模块606，包括：

社会关系子图生成子模块6061，用于利用杰卡德系数生成该用户的社会关系子图；

社会关系模体验证子模块6062，用于比较该用户个体社会关系子图是否为前述社会关系模体，若是则通过验证，反之则不通过；

在本发明的实施例中，请参阅图12所示，所述位置预测器建立模块607，包括：

马尔可夫预测器建立子模块6071，用于利用用户历史位置信息预测用户未来位置；

熟人预测器建立子模块6072，用于利用用户的熟人关系预测用户未来位置；

熟悉的陌生人预测器建立子模块6073，用于利用用户的熟悉的陌生人关系预测用户未来位置；

输出调节器建立子模块6074，用于对子模块6071、子模块6072和子模块6073的输出进行融合，得到最终预测输出。

通过前述实施例对本发明的描述可知，首先从用户移动行为日志数据库中，获取用户的个体行为记录，推断两用户间的社会关系类型；构建用户社会关系网络；构建用户离散移动轨迹序列；利用杰卡德系数生成社会关系子图，通过随机断边重连生成随机化用户社会关系网络，构建零模型，通过z值挖掘用户群体社会关系模体；比较待预测用户个体社会关系子图是否为前述社会关系模体，若是则通过验证，反之则不通过；建立马尔可夫预测器、熟人预测器、熟悉的陌生人预测器和输出调节器；若该个体通过社会关系模体验证，则只需利用马尔可夫预测器、熟悉的陌生人预测器和输出调节器，若未通过验证，则需要马尔可夫预测器、熟人预测器、熟悉的陌生人预测器和输出调节器。本发明所提供的自动推断社会关系的移动用户位置预测方法与装置，在传统的通过用户历史轨迹信息和熟人社会关系预测用户位置的基础上，首次将“熟悉的陌生人”关系引入位置预测方法，提高了位置预测的准确性，为位置预测方法设计提供了新的思路。本发明通过定义并挖掘用户社会关系模体，异质处理不同类型的用户，在减小了计算代价的同时提高整体的预测性能。本发明基于利用用户线下行为数据直接推断到的不同类型的社会关系，不需要专门额外采集用户社会关系数据，减少了预测所需的原始数据信息，很好地保护了用户的个人隐私，降低了数据获取的难度。本发明所提供的方法适用于Wi-Fi等地理分辨率较高的场景，有别于传统方法多依赖于基站、POI等地理分辨率较低的场景，可做到对细粒度地理位置进行较好地预测。

本领域普通技术人员可以理解实现上述实施例方法中的全部或部分步骤是可以通过程序来指令相关的硬件来完成。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来，该计算机软件产品存储在可读取的存储介质中，如计算机的软盘，U盘、移动硬盘、只读存储器(ROM，Read-Only Memory)、随机存取存储器(RAM，Random Access Memory)、磁碟或者光盘等，包括若干指令用以使得一台计算机装置(可以是个人计算机，服务器，或者网络装置等)执行本发明各个实施例所述的方法。

以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应以所述权利要求的保护范围为准。