基于高斯分析的马尔可夫位置预测方法

乔岩磊，杜永萍，赵东玥

(北京工业大学 计算机学院,北京 100124)

0 引 言

随着当今互联网移动化的潮流推进，类似导航、交通管理等基于位置的服务发展迅速。为了提高位置服务体验，很多基于位置服务的应用需要预先知道用户的位置信息，如路径推荐、兴趣点推荐、广告推荐等等。假设用户A在下午3点经过位置1，如果可以比较精准地预测到用户A在5点的位置2，就可以在3点钟，针对性地给A发送位置2相关的广告信息，引导A在对位置2的访问过程中访问广告内容。借助其他信息，如果可以知道用户A在5点左右进行进餐，那么就可以在广告中投放位置2周边的餐厅信息。因此，对于用户在某一真实时间区域内的位置预测，就变得非常重要。

在轨迹数据挖掘方面，郑宇[1]从多方面阐述了轨迹数据挖掘的相关工作，其中包括轨迹数据预处理，模式挖掘、分类等。Zheng等[2]提出了一种发现不确定轨迹中top-k个可能路径的方法，基于历史记录的路径推断系统，利用历史数据进行出行模式推断，用于降低用户轨迹不确定性。

在位置预测方面，Xue等[3]提出了SubSyn算法，将用户的历史轨迹分解为子轨迹，利用子轨迹合成新轨迹，从而增加轨迹数目，扩大了训练集规模，提高了预测目的地点的准确率。目前在轨迹预测方面，基于马尔可夫模型的方法[4-5]使用比较广泛，其核心思想是构建一个马尔可夫链，通过前k步来推测第k+1步。Yu等[6]提出了SMLP算法，该算法在马尔可夫模型的基础上，利用网络内用户的相关性，对位置进行预测。Lian等[7]提出了CEPR算法，该算法利用协同过滤和用户历史行为对用户未来位置进行推荐与预测，另外他们还在Jiepang和Gowalla两个数据集上进行了用户统计信息和位置可预测性的相关性分析[8]。Zhang等[9]利用前缀树和启发式搜索策略进行个性化路径推荐。Li等[10]利用用户社交网络关系和流动性特点相关性分析对用户建立多层友谊模型，提高了位置相关预测的性能。

另外，其他研究还包括基于关联规则的方法[11]、基于近期活动序列与历史活动匹配的方法[12]、基于多层感知机的方法[13]等。

传统方法在利用马尔可夫模型进行位置预测时，往往要将时间划分为若干个时间片段，然后在离散的时间段上进行建模和预测。这就导致时间片段长短的取值对预测结果会产生较大影响。若时间片段取得过长，则导致预测结果粗糙，应用价值变低；若时间片段取得过短，则导致模型序列过长，影响算法效率。为了解决上述问题，文中提出了基于高斯分析的马尔可夫模型(Markov model based on Gaussian analysis，GA-MM)。该模型通过对位置转移时间进行高斯混合分析，确定马尔可夫过程中的状态转移节点，并且不需要对时间片段进行划分，从而解决了上述问题。

1 基于高斯分析的马尔可夫模型

1.1 GA-MM预测算法

已知用户在tstart时刻对Lstart进行了访问，要预测在tend时用户的位置Lend。该问题可转化为对式(1)进行求解，其中X(t)表示t时刻用户的位置。

(1)

为了求解式(1)，建立的模型如图1所示。

图1 GA-MM示意图

其中，⊗节点是概率流出节点，表示用户在该时间点转移出该位置;⊕节点是概率流入节点，表示用户在该时间点从其他位置转移至该位置。这两种节点相当于马尔可夫模型中的状态转移节点。

假设用户的行为符合马尔可夫过程，即用户下一个位置出现在Lβ的概率P(Lβ)只与其位于前一个位置Lα的概率P(Lα)和在t时刻的转移概率P(t|Lα→Lβ)有关。故⊗节点的概率可由式(2)计算得出：

P(Lα→Lβ,t)=P(X(t)=Lα)×P(t|Lα→Lβ)

(2)

⊕节点的概率计算由马尔可夫随机性可知：用户会按照不同的转移概率从若干个位置Lα转移至位置Lβ，故用户在t时刻位于Lβ的概率P(X(t)=Lβ)为用户从所有可能位置Lα转移概率之和。

(3)

其中，初始概率P(X(tstart)=Lstart)=1。

1.2 基于高斯混合模型的转移点发现

利用马尔可夫模型进行位置预测时，往往都采用等间隔的时间划分作为一个状态的转移点。例如以小时为单位进行序列建模，每个状态转移点则相距1个小时，预测过程中则也采用小时为单位进行预测。然而，用户位于不同地点的行为不同，停留时间也不尽相同，统一的时间划分必然导致预测结果的不准确。为了解决这个问题，采用高斯混合模型对马尔可夫模型中的状态转移点进行发现。

由于用户在每个位置可能发生转移的时间都不相同，所以首先提取用户从每一个位置Lα转移至Lβ的时间点ti，然后学习一个高斯混合模型，如图2所示。

图2 高斯混合分布

图2为一个由3个高斯分布混合而成的概率分布，从中可以看出高斯混合模型可以较好地拟合转移时间点的分布。

故在t时刻，用户从位置Lα转移至位置Lβ的概率P(t|Lα→Lβ)可由高斯混合模型计算得出：

(4)

其中，P(t|Lα→Lβ)为关于时间t的函数，由若干个带权重的高斯分布Nαβ(t|μi,σi)叠加而成；μi为第i个高斯分布的期望，对应于第i个高斯分布的概率最大值。这表明用户在该时间点从位置Lα转移至位置Lβ的概率最大，于是用该值作为位置的一个转移时间点t。

至此，所有相关概率值已经求得，可用式(1)进行迭代求解，迭代结束条件为当前时刻t大于等于结束时刻tend。

1.3 位置预测算法实现

基于时间序列的位置预测算法采用递归形式进行求解，过程中通过数组R记录每个地点的预测概率，具体算法描述如下：

算法：GA-MM预测算法。

全局变量：R=(RL0,RL1,…,RLm) //初值为0

输入：

Lcur：当前位置，初值为Lstart

tnow：当前时间，初值为tstart

tend：结束时间

Pcur：当前概率值，初值为1

Start:

For 0≤i≤m：

RLi=RLi+Pcur

continue

Else:

End

算法运行结束后，全局变量R中保存着在时间tend时，用户位于各个位置的概率。将其中概率最大值对应的地点作为最终用户的位置。

2 实 验

2.1 数据集

GeoLife是由微软亚洲研究院提供的一份中国用户户外活动数据集，其中包含了182名用户的出行记录，共有17 621条轨迹，总里程超过 1292 951 km。

考虑到绝大多数轨迹点位于北京，故实验中只针对北京的轨迹点进行预测与分析。经过数据预处理工作，包括数据过滤与聚类，得到如图3所示的地点统计数据分布，其中DBSCAN参数设置为：类簇内点数量最小阈值=20,最大密度=0.000 5。

图3展示了每个地点的用户平均停留时间，可以发现对于81%以上的地点，用户的平均停留时间不超过5 min。

图3 位置平均停留时间分布

从以上的统计信息可以看出，该数据集中轨迹点分布相对分散，用户移动频率相对较快，这将会给实验结果带来一定的影响。

2.2 实验结果

选取160名用户相邻20天的轨迹数据作为训练集，与其时间相邻5天的轨迹数据作为测试集(对于轨迹天数低于25天的用户按其所有轨迹数据4∶1进行划分，其中有22个用户由于轨迹数量过少被过滤掉)，分别对不同时间段以及不同用户的预测性能进行了评价。

采用准确率(Precision)对预测结果进行评价。

(5)

2.2.1 不同时间间隔△t对预测性能的影响

为了探究算法性能，将GA-MM算法与同样不需要序列等值划分的GMM算法进行了对比。对用户在不同时刻t，经过不同时间间隔△t(min)之后的位置预测性能进行了评价，如图4所示。

观察图4可以发现，在不同时段利用不同模型，预测准确率都有所不同。总体来说，夜晚和下午的准确率相对较高，上午的准确率则相对较低。这可能是由于用户在上午进行活动的多样性和不确定性较高，导致了很难对用户的习惯进行建模；而在下午和夜间，用户的行动较为固定，预测的准确率也较高。另一方面，不同的预测时间间隔△t对算法性能的影响也较大。当△t∈(0,60)时，GA-MM算法相比GMM算法具有一定的优势；当△t大于一小时后，GA-MM算法出现较大性能的下降。

2.2.2 不同用户的位置预测性能

此外，还对不同用户进行了预测实验并进行对比，以此来估计准确率波动的幅度，具体数据如图5所示。

图4 GA-MM与GMM的预测准确率对比

图5 用户平均预测准确率分布

从图5可见，在不同时间间隔△t下，对于不同用户的预测准确率距离平均准确率约在±15%以内，性能较为稳定。对△t小于30 min的用户进行预测时，实验结果显示GA-MM相比于GMM，预测准确率提高了约12%。

将文中算法与马尔可夫模型和PST模型[14]进行了准确率对比，从表1所示。可见，相比于其他算法，GA-MM的预测准确率较高。

表1 不同算法的Precision比较

3 结束语

提出了基于高斯分析的马尔可夫地理位置预测模型。该模型通过高斯混合模型拟合连续时间下地点轨迹的转移概率，发现位置转移节点，然后对马尔可夫过程求取最终的位置预测概率，预测准确率在42%左右，相比传统算法平均准确率提高了10%左右。在今后的工作中，为了进一步提高预测准确率并降低时间复杂度，将考虑用其他模型结合贝叶斯定理对位置的后验概率进行建模，并将结合签到数据、用户数据等其他信息对位置预测进行辅助工作，以进一步提高预测性能。

[1] ZHENG Y.Trajectory data mining:an overview[J].ACM Transactions on Intelligent Systems & Technology,2015,6(3):1-41.

[2] ZHENG Kai，ZHENG Yu，XIE Xing，et al．Reducing uncertainty of low-sampling-rate trajectories[C]//International conference on data engineering.Arlington,Virginia,USA：IEEE,2012:1144-1155.

[3] XUE A Y,ZHANG R,ZHENG Y,et al.Destination prediction by sub-trajectory synthesis and privacy protection against such prediction[C]//International conference on data engineering.Brisbane,Australia:IEEE,2013:254-265.

[4] 彭 曲,丁治明,郭黎敏.基于马尔可夫链的轨迹预测[J].计算机科学,2010,37(8):189-193.

[5] SONG C,QU Z,BLUMM N,et al.Limits of predictability in human mobility[J].Science,2010,327(5968):1018-1021.

[6] 于瑞云,夏兴有,李 婕,等.参与式感知系统中基于社会关系的移动用户位置预测算法[J].计算机学报,2015,38(2):374-385.

[7] LIAN D,XIE X,ZHENG V W,et al.CEPR:a collaborative exploration and periodically returning model for location prediction[J].ACM Transactions on Intelligent Systems & Technology,2015,6(1):1-27.

[8] LIAN D,ZHU Y,XIE X,et al.Analyzing location predictability on location-based social networks[C]//Pacific-Asia conference on knowledge discovery and data mining.[s.l.]:[s.n.],2014:102-113.

[9] ZHANG C, LIANG H, WANG K, et al. Personalized trip

recommendation with POI availability and uncertain traveling time[C]//24th ACM international on conference on information and knowledge management.New York,NY,USA:ACM,2015:911-920.

[10] LI N,CHEN G.Multi-layered friendship modeling for location-based mobile social networks[C]//International conference on mobile and ubiquitous systems:networking and services.Toronto,Canada:IEEE,2009:1-10.

[11] MORZY M.Mining frequent trajectories of moving objects for location prediction[C]//International conference on machine learning and data mining in pattern recognition.Berlin:Springer,2007:667-680.

[12] BURBEY I.Predicting future locations and arrival times of individuals[D].Virginia:Virginia University,2011.

[13] KOSKELA T,LEHTOKANGAS M,SAARINEN J,et al.Time series prediction with multilayer perceptron,FIR and Elman neural networks[C]//Proceedings of the world congress on neural networks.[s.l.]:IEEE,1996:491-496.

[14] 王 兴,蒋新华,林 劼,等.基于概率后缀树的移动对象轨迹预测[J].计算机应用,2013,33(11):3119-3122.