基于位置转移时空规律的用户签到位置预测*

刘攀登，李 川，李晓娟

四川大学 计算机学院，成都 610065

1 引言

随着Foursquare、Gowalla、Micro-blogging、大众点评网等基于位置的社交网络（location-based social network，LBSN）的广泛应用，基于LBSN的位置预测成为近年来的研究热点之一。准确的位置预测在城市规划[1-2]、交通预测[3-4]、广告推送[5-6]以及疾病预防[7]等方面具有非常重要的应用价值。

现存用户移动性规律发现方法，如马尔科夫模型、PMM（periodic mobility model）、W3（who，when，where）等虽各有所长，但仍存在如下缺陷：（1）不能将时间对于用户访问位置变化的影响真实、量化地反映出来；（2）不能将地理位置间前后相继、相互关联的影响真实、量化地反映出来。

现实生活中，人类的移动行为在时间上是连续的，前一时刻的移动行为必然影响下一时刻的行为，前一状态的位置必然影响下一状态的位置。马尔科夫过程与这种直观的移动行为相吻合，被广泛应用于位置预测模型中[8-11]。然而，该方法有如下缺陷：（1）难于实现复杂度和预测精度间的平衡：虽然马尔科夫模型阶数的增加会提高算法的准确率，但算法复杂度也会随之增加。（2）忽略时间的影响：用户移动行为和时间有着紧密的联系，但使用马尔科夫模型来预测用户的位置会忽略时间的影响。如，工作日上午9:00，人们一般在公司上班，但周末的上午9:00，他们可能在家休息或者在旅行。（3）忽略移动轨迹的前后地理位置间的关联：轨迹绝不是孤立的，它们彼此联系。如，从家出发去商场，接着到办公室（家庭—商场—办公室）这条轨迹与（家庭—商场—餐厅）轨迹是有关联的。但使用马尔科夫模型建立转移概率时，研究者则假设轨迹独立。……