基于作者主题模型和辐射模型的用户位置预测模型

李 琰,刘嘉勇

0 引言

随着移动设备的广泛应用以及定位技术的发展,基于位置的服务(Location Based Service, LBS)越来越受到社会各界的关注[1]。目前,LBS获得的位置信息仅限于移动用户的当前位置,这使得为用户提供的服务缺乏可预见性。为了提高LBS的服务质量,对用户未来位置的预测已成为近年来的研究热点。事实上,良好准确的位置预测算法不仅可以让LBS中的商家根据预测结果挖掘潜在的客户进行商品推送,而且能帮助用户利用商家的精准推送从海量商品中进行高效选择,从而获得更好的用户体验[2]。

文献[3]研究了一种基于变阶的Markov位置预测模型,该模型预测能力高于标准Markov模型;但此类算法通常存在数据稀疏问题,因此凭借单个用户的历史轨迹数据构建状态转移矩阵的Markov位置预测模型准确率不高。文献[4]用已有的先验知识,为用户建立个性化的位置推理模型,一定程度上解决了数据稀疏的问题;但该方法实现过程复杂,适用范围狭窄。文献[5]中提出了在空间维度上基于辐射模型的位置预测方法,提高了预测的准确率;但该方法对地点的吸引力定义不准确,并且在时间维度上只考虑了单个用户的行为规律,限制了模型的预测能力。

针对上述问题,本文提出在时间维度上利用作者主题模型(Author Topic Model, ATM)[6]自动地发现与目标用户移动行为相似的用户群,根据用户群的行为规律来优化个人的行为规律模型,以解决数据稀疏的问题,并扩大预测模型的适用范围;在空间维度上对基于辐射模型的空间预测方法[5]进行了改进和优化,最后通过大量实验和实际数据集测试,验证了该预测模型的有效性。

1 本文模型

本文提出的位置预测模型基于人类移动具有强规律性,文献[7-8]指出可以将人类有强周期性的移动看作往返于“家庭”和“工作”位置状态之间。如图1所示:图1(a)展示用户在一天时间内处于家庭/工作位置状态的概率分布；图1(b)描述在家庭/工作位置状态下用户签到数据在地理空间上的分布情况。其中,圈和叉分别表示在家庭位置状态和工作位置状态下用户的签到数据,图1(b)中圈围成区域是工作位置状态区域,而叉围成的则是家庭位置状态区域。

图1 用户周期性移动规律展示图

本文模型操作流程如图2所示:

图2 模型预测流程

1)在时间维度上,先依据作者主题模型自动地发现用户在移动行为规律上相似的群体,然后计算在时刻t相似用户群在位置状态(家庭H/工作W)的概率,即用户的概率p(H|t)和p(W|t)。

2)在空间维度上,对文献[5]中提出的基于辐射模型的空间预测进行改进,对用户的家庭和工作位置状态区域进行单独的辐射模型训练,并计算在t时刻,用户的候选签到地点集Venues分别在H和W位置状态区域成为签到地点x的概率p(x|H)和p(x|W),其中Venues指在所有用户位置数据中出现过的地点。

3)综合以上结果,根据式(1)计算得到Venues成为签到地点x的概率p(x|t),比较候选地点的概率大小,取概率值最大的地点作为预测的签到地点x,如式(2)所示:

p(x|t)=p(x|H)·p(H|t)+p(x|W)·p(W|t)

(1)

x=arg max{p(x|t),x∈Venues}

(2)

2 基于作者主题模型的时间-位置状态预测

作者主题模型是一个级联生成模型[9],它是隐含狄利克雷分布(Latent Dirichlet Allocation, LDA)[10]结合元数据作者的衍生模型,可以解决计算作者间的相似度问题。

基于作者主题模型(ATM)的时间-位置状态预测模型凭借用户历史签到数据训练ATM后自动发现用户在移动行为规律上相似的群体,然后用ATM训练结果中权重排名前N的表示用户位置状态转移的词去描述该群体的移动行为规律,最后依据群体的行为规律以及本文提出的时间-用户位置状态概率算法得到在时间t用户处于位置状态(H/W)的概率。模型实现流程如图3所示。

图3 时间-位置状态预测模型实现流程

2.1 位置数据预处理

位置数据预处理主要是将用户每天的原始签到数据表示为由48个位置词按照时间先后顺序构成的位置词转移序列[11]。位置词用来表示用户在某时段的位置状态转移过程,包含3个连续位置标签和1个时间段标签,位置标签标记签到位置所处的位置状态区域,时间段标签用签到时间对应的时段标记,例如:位置词HHH1,其位置标签是HHH,时间段标签是1,它表示用户在时间段1的位置转移是HHH,即在时段1该用户一直在家庭位置状态区域活动。本节的位置数据表示可分为以下三个步骤:

1)确定签到位置数据集中每个位置的标签,即根据用户在访问位置的时间空间分布规律,确定该位置所处的位置状态区域(H:家,W:工作,O:其他,N:缺失数据)。

2)确定用户每天的位置标签转移序列。位置标签转移序列的定义与位置词转移序列的类似,它是由48个位置标签按照时间先后顺序构成的转移序列。本文以30 min作为划分时间单位,将一天划分为48个时间块,对于每个时间块,选择用户停留时间最长的位置作为用户在该时间块的停留位置,从而确定该时间块的位置标签,以此便形成用户每天的位置标签转移序列。

3)确定用户每天的位置词转移序列,即先从用户每天的位置标签转移序列中从头依次取3个连续位置标签,然后由步骤2)可知,3个位置标签跨越1.5 h,通过时间累加的计算可得到它们对应的时段,取包含位置标签多的时段为位置词的时段标签,进而结合3个连续位置标签和对应的时段标签得到一个完整的位置词。以此类推,可获得48个位置词,并按照时间先后顺序构成位置词转移序列。本文将人的一天分为8个时间段:1)00:00—07:00;2)07:00—09:00;3)09:00—11:00;4)11:00—14:00;5)14:00—17:00;6)17:00—19:00;7)19:00—21:00;8)21:00—24:00。

2.2 用户-用户群模型的生成

用户-用户群模型是作者主题模型在本文的应用,本文凭借该模型来自动发现与目标用户在移动行为规律上相似的用户群体。

在用户-用户群模型中，每个位置词w和两个潜在变量(用户u和用户群g)相联系。如图4所示,该模型的生成过程包括两个步骤:1)挑选一个用户u和一个用户群g;2)根据用户-用户群概率分布Θ和用户群-位置词概率分布Φ生成位置词w。其中α和β是模型的先验参数[9]。

图4 用户-用户群模型的概率图模型

凭借所有用户的位置词转移序列数据训练用户-用户群模型,得到参数Θ和Φ。从图4中用户-用户群的概率图模型易知,有以下条件概率:

P(w|A,α,β)=∬P(w|A,Θ,Φ)P(Θ,Φ|α,β)dΘdΦ

(3)

其中:Θ表示用户-用户群概率分布;Φ表示用户群-位置词概率分布;A表示位置数据集中的用户。当Θ和Φ被看作随机变量时,位置数据集的边缘概率可以通过对它们进行积分得到。一些估计推断方法可用来估计级联贝叶斯模型的后验分布,本节采用吉布斯采样[10]来进行推断,从而获得参数Θ和Φ的值。其推导过程如下:

在用户群G数量固定时,θ和φ的条件下w的概率可以表示为:

(4)

同时,可以得到每个位置词转移序列中的位置词wd的概率:

(5)

根据式(4)和(5),式(3)可表示为:

P(w|A,α,β)=

考虑到这里采用离散随机变量和多项式分布,位置词集的分布可以进一步转换为向量u、g的所有可能组合的和形式,因此,式(4)可以转换为如下形式:

P(w|A,α,β,G)=

其中:

P(u,g,w,Θ,Φ|A,α,β)=

(9)

对式(8)中的Θ和Φ进行积分可得:

P(u,g,w|A,α,β)=

(10)

根据吉布斯采样,需要估计P(u,g|Dtrain,α,β)。其中,Dtrain为训练数据中的用户和位置词集合。根据贝叶斯准则,吉布斯采样可以使用如下条件分布:

P(ui=a,gi=t|wi=w,u-i,g-i,w-i,A,α,β)=

(11)

可以得到:

P(ui=a,gi=t|wi=w,u-i,g-i,w-i,A,α,β)∝

(12)

在第s次采样中,在用户群gN+1=G条件下位置词wN+1=W的概率为:

(13)

同样,在用户uN+1=a条件下用户群gN+1=t的位置词概率为:

(14)

通过上述的吉布斯采样过程可以对参数Θ和Φ的值进行估计。

2.3 相似用户群体的发现

本文用100名用户的位置数据训练用户-用户群模型,并将用户群数设定为50,然后根据模型估计的参数Θ和Φ,选择用户群5、20和28按指定概率排序,得到的结果如表1～2所示。本文使用2.2节生成的模型自动地发现相似用户群以及他们的特征路径。在表1中,如用户群5所示,排名靠前的位置词大多都包含工作标签W,这说明与用户群5移动行为相似的用户(如:用户10)工作时间较长,且工作时间集中在4～6时间段。如表2所示,用户16和19与用户群20相似,从表1中可知,他们2、7、8时间段在家,并在4和5时间段处于工作状态。以此类推,可以发现用户11和8在1和8时间段处于家庭位置状态,4～6时间段在工作并且在时间段8回家。再者,用户群20的工作时间比用户群5和28的工作时间短,可推测对于与用户群5相似度高的用户(如:用户10和5),他们的工作量比与用户群20相似度高的用户(如:用户16和19)大。

表1 不同用户群中按 P(w|g)排序排名前9的位置词

表2 不同用户群中按 P(g|u)排序排名前4的用户

如图5所示,用户10的移动行为规律主要与用户群30相似,而用户13与多个用户群相似。由此可知,用户10在行为移动方面的生活方式是几乎不变,而用户13可能具有高度变化的生活方式。此外,还可以发现,图6中所有用户排名前三相似用户群的概率之和都大于0.5，并且大约有1/3用户的概率接近1,这说明用户的行为移动模式可以凭借其排名前三的相似用户群行为规律共同去描述。

图5 不同用户的相似用户群概率分布

图6 所有用户排名Top3用户群的概率和分布

2.4 时间-用户位置状态概率算法

时间-用户位置状态概率算法是用来计算在指定时间t用户处于位置状态(H/W)概率的算法,该算法的实现步骤如下:

1)根据2.2节训练模型得到的参数Θ定位到与用户相似排名前N的用户群以及相应的概率user_sim_ug。

2)通过参数Φ和user_sim_ug可获得目标用户相似用户群分别在8个时段中概率最大的位置词以及计算相应概率p_i。

3)最后计算出目标用户在时间t所处的位置状态的概率p(S|i)。

概率p_i和p(S|i)的计算公式如下：

p_i=p_g·p_l;i∈[1,8]

(15)

S∈{H,W},i∈[1,8] (16)

其中:p_i为i时段概率最大位置词的概率;p_g是目标用户属于用户群g的概率;p_l是i时段概率最大位置词在Φ中的概率;p(S|i)是目标用户在i时段时位置状态为S的概率;count_S是i时段用户位置词中包含S的数值;l_word是位置词的长度。另外,根据图6的结果,说明用户的行为移动模式可以用其排名前三的相似用户群行为模式共同去描述,所以,本文将排名前N位设定为前3位。

3 基于辐射模型的位置状态-候选地点预测

3.1 基于辐射模型的空间预测模型

辐射模型最初用于对移动性和迁移模式的建模[12],该模型用于计算彼此距离r处的位置i和j之间的流动强度Tij(位置i、j分别具有群体m和n)，如式(17)[13]所示:

(17)

其中:Ti是离开位置i的用户总数;sij是以i为中心、半径为rij的圆中的用户总数(该数不包括在位置i和j上停留的用户数)。

文献[5]中提出在空间预测建模上对家庭H和工作W位置状态区域进行单独的辐射模型训练,他们假设在每个位置状态区域中有一个中心地点,即用户经常签到的地点并且用户通常从该地点移动到同一区域内的不同候选地点,其中候选地点指在所有用户位置数据中出现过的地点。例如,用户工作地点即可视为W区域的中心地。在他们的研究中,假设移动仅在中心地点与其他地点之间发生,对于给定的区域,在j签到的概率等于用户从中心地i移动到地点j的概率,如式(18)所示:

(18)

其中:n代表地点j的吸引力。文献[5]将它定义为在所有用户位置数据集中在该地点进行签到的总次数。m与n的定义相同,但m仅用于代表家庭或工作中心地点i的吸引力。然而,地点的吸引力越大,其成为用户签到地点的概率也就越大。

3.2 基于辐射模型的位置状态-候选地点预测模型

位置状态-候选地点预测模型是在文献[5]中提出的空间预测模型上进行改进得到,具体模型实现流程如图7所示。

图7 位置状态-候选地点预测模型流程

文献[5]将地点的吸引力n定义为所有用户在该地点进行签到的总次数,本文作者认为该定义存在不合理性。假设研究对象是在学校区域内活动的用户群体并在此基础上计算学校食堂的吸引力n值,众所周知,目标群体在学校食堂签到的总次数较多,按文献[5]对n的定义来计算食堂的吸引力n,必然得到的结论是:无论何时,食堂的n值大。实际上,在非就餐时间食堂处于关闭状态,它的吸引力n大大降低,这与根据n的原定义得出的结论矛盾。因此,本文加入时间因素更准确地定义n为:在指定时间所属时段所有用户在该地点进行签到的总次数。最后通过实验验证了这种改进方法的有效性。具体确定地点n值的改进算法伪代码如算法1。

算法1get_N():获得地点的n值。

输入 指定时间t,check_in_dataset(用户位置数据集)。

输出n。

确定时刻t所处的时段i(i∈[1,8]);

从check_in_dataset中筛选出属于i时段的签到数据,并存入check_in_period中;

fordataincheck_in_perioddo

从data中找到不同的签到地点venues;

forvenueinvenusdo

对venue进行计数,再将相应的值存入n[venue]中;

endfor

endfor

returnn;

4 实验与分析

4.1 数据及评价标准

本文采用美国著名LBS网站Gowalla的签到数据集来进行用户位置预测。其中,本文选取的实验数据集包含2009年8月3日—11月10日90天共1万多用户的60多万条位置数据。从数据集中抽取较活跃的100名用户进行实验。每条签到数据包括用户移动设备串号、签到id、签到时间、签到点经度以及签到点纬度。

对于每个用户的位置数据,将其80%数据设定为训练集,剩余20%设定为测试集,并采用准确率来评判位置预测算法的有效性。

验证步骤如图8所示。

图8 算法验证步骤流程

本文采用准确率作为评价标准。

准确率是指预测正例与预测样本的比例,是广泛用于信息检索和统计学领域的度量值,用来评价结果的质量。其计算公式如下:

(19)

表3是两分类器混淆矩阵(confusion matrix)。

表3 两分类混淆矩阵

其中:TP表示实际为正类,实验结果也为正类的样本数量;FN表示实际为正类,实验结果为反类的样本数量;FP表示实际为反类,结果为正类的样本数量;TN表示实际为反类,结果也为反类的样本数量。

4.2 结果与分析

与本文模型对比的是文献[3,5]模型。对比模型介绍如下:

模型A:文献[3]中提出的基于变阶的Markov模型,利用训练好的变阶Markov模型,根据文献[3]已定义的公式结合该用户当前所处的位置,来计算其出现在每一可能位置的概率,然后将概率最大的那个位置选作预测结果。

模型B:文献[5]中提出的辐射模型(Radiation Model, RM),在空间维度上采用辐射模型,在时间维度上采用一维混合高斯模型,并综合以上两个维度来预测用户位置。

模型C:本文提出的预测模型,在模型B的基础上进行改进,在时间维度上改用基于ATM的时间-位置状态预测模型。

模型D:本文提出的预测模型,在模型C的基础上进行改进,在空间维度上采用本文改进的基于辐射模型的位置状态-候选地点预测模型。

各个模型所有实验用户周一至周日预测准确率均值的对比结果如表4所示。

从表4可看出：1)本文模型C和D的平均预测准确率均优于对比模型；模型D的预测准确率高于C,这说明在空间维度上对模型C改进是有效的。本文提出的模型D的平均预测准确率比基于Markov的预测模型A[3]提高了近28个百分点,比同类型预测模型B[5]提高了近31个百分点。2)与模型A[3]相比,由于模型B、C、D的预测准确率受用户移动规律性的影响且一般用户在工作日的移动规律性强于周末,因而本文提出的模型更适用于预测在工作日中用户的位置。

表4 各种模型的平均预测准确率 %

5 结语

本文从用户历史位置数据中研究了预测用户位置的算法,提出一种基于作者主题模型和辐射模型的用户位置预测模型。该模型在时间维度上,采用了作者主题模型训练出用户的两个概率分布矩阵,依据矩阵可得到用户在某时刻下的状态(“家”或“工作”);在空间维度上,依据辐射模型得到在用户所处状态下最可能出现的地点,将此地点作为预测地点。通过大量实验结果验证了本文模型在预测用户位置上的有效性。然而,预测用户下一时刻的位置,不仅与用户自身的行为习惯有关,还受朋友关系等其他因素影响,下一步将致力于进行基于社交关系和用户行为习惯的位置预测。

参考文献(References)

[1] BAO J, ZHENG Y, MOKBEL M F. Location-based and preference-aware recommendation using sparse geo-social networking data[C]// Proceedings of the 20th International Conference on Advances in Geographic Information Systems. New York: ACM, 2012: 199-208.

[2] NOULAS A, SCELLATO S, LATHIA N, et al. Mining user mobility features for next place prediction in location-based services[C]// ICDM 2012: Proceedings of the 2012 IEEE 12th International Conference on Data Mining. Washington, DC: IEEE Computer Society, 2012: 1038-1043.

[3] Yang j, J X, M Xu, et al. Predicting next location using a variable order Markov model[C]// IWGS 2014: Proceedings of the 5th ACM SIGSPATIAL International Workshop on GeoStreaming. New York: ACM, 2014: 37-42.

[4] 薛迪, 吴礼发, 李华波, 等.TraDR: 一种基于轨迹分解重构的移动社交网络位置预测方法[J]. 计算机科学, 2016, 43(3): 93-98.(XUE D, WU L F, LI H B, et al. TraDR: a destination prediction method based on trajectory decomposition and reconstruction in geo-social networks[J]. Computer Science, 2016, 43(3): 93-98.)

[5] TARASOV A, KLING F, POZDNOUKHOV A. Prediction of user location using the radiation model and social check-ins[C]// UrbComp 2013: Proceedings of the 2nd ACM SIGKDD International Workshop on Urban Computing. New York: ACM, 2013: Article No. 8.

[6] ROSEN-ZVI M, GRIFFITHS T, STEYVERS M, et al. The author-topic model for authors and documents[C]// UAI 2004: Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence. Arlington, Virginia, USA: AUAI Press, 2004: 487-494.

[7] EAGLE N, PENTLAND A. Eigenbehaviors: identifying structure in routine[J]. Behavioral Ecology and Sociobiology, 2009, 63(7): 1057-1066.

[8] LI Z, DING B, HAN J, et al. Mining periodic behaviors for moving objects [C]// KDD 2010: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2010: 1099-1108.

[9] 李杰, 王小伟.基于作者主题模型的遥感图像自动类别标注方法[J]. 计算机应用与软件, 2013, 30(10): 263-265.(LI J, WANG X W. Automatic category tagging of remote sensing images using author topic model[J]. Computer Applications and Software, 2013, 30(10): 263-265.)

[10] 徐戈, 王厚峰.自然语言处理中主题模型的发展[J]. 计算机学报, 2011, 34(8): 1423-1436.(XU G, WANG H F. The development of topic models in natural language processing[J]. Chinese Journal of Computers, 2011, 34(8): 1423-1436.)

[11] FARRAHI K, GATICA-PEREZ D. What did you do today? Discovering daily routines from large-scale mobile data[C]// MM 2008: Proceedings of the 16th ACM International Conference on Multimedia. New York: ACM, 2008: 849-852.

[12] SIMINI F, GONZLEZ M C, MARITAN A, et al. A universal model for mobility and migration patterns[J]. Nature, 2012, 484(7392): 96-100.

[13] McARDLE G, LAWLOR A, LLXREY E, et al. City-scale traffic simulation from digital footprints[C]// UrbComp 2012: Proceedings of the 2012 ACM SIGKDD International Workshop on Urban Computing. New York: ACM, 2012: 47-54.

[14] ZHENG J, NI L M. An unsupervised framework for sensing individual and cluster behavior patterns from human mobile data[C]// UbiComp 2012: Proceedings of the 2012 ACM Conference on Ubiquitous Computing. New York: ACM, 2012: 153-162.

[15] 张莹, 李智, 张省.基于位置的社交网络用户轨迹相似性算法[J]. 四川大学学报(工程科学版), 2013, 45(增刊2): 140-144.(ZHANG Y, LI Z, ZHANG S. Users trajectory similarity algorithmic research on location-based social network[J]. Journal of Sichuan University (Engineering Science Edition), 2013, 45(S2): 140-144.)