Sparse trajectory prediction method based on iterative grid partition and entropy estimation

doi:10.11772/j.issn.1001-9081.2015.11.3161

Journal of Computer Applications ›› 2015, Vol. 35 ›› Issue (11): 3161-3165.DOI: 10.11772/j.issn.1001-9081.2015.11.3161

• DPCS 2015 Paper • Previous Articles Next Articles

Sparse trajectory prediction method based on iterative grid partition and entropy estimation

LIU Leijun¹, ZHU Meng², ZHANG Lei¹

1. College of Computer Science and Technology, China University of Mining and Technology, Xuzhou Jiangsu 221116, China;
2. Department of Computer Science, Xinyang College of Agriculture and Forestry, Xinyang Henan 464006, China

Received:2015-05-13 Revised:2015-07-13 Published:2015-11-13

基于迭代网格划分和熵估计的稀疏轨迹预测

刘磊军¹, 朱猛², 张磊¹

1. 中国矿业大学计算机科学与技术学院, 江苏徐州 221116;
2. 信阳农林学院计算机科学系, 河南信阳 464006

通讯作者: 刘磊军(1991-),男,安徽安庆人,硕士研究生,主要研究方向:移动对象轨迹数据挖掘.
作者简介:朱猛(1977-),男,河南信阳人,讲师,硕士,主要研究方向:智能信息处理; 张磊(1977-),男,江苏徐州人,副教授,博士,CCF会员,主要研究方向:移动对象轨迹数据挖掘.
基金资助:
中央高校基本科研业务费专项资金资助项目(2014XT04);教育部博士点基金资助项目(20110095110010);江苏省自然科学基金资助项目(BK20130208).

Abstract

Abstract: Concerning the "data sparsity" problem of moving object's trajectory prediction, i.e., the available historical trajectories are far from enough to cover all possible query trajectories that can obtain predicted destinations, a Trajectory Prediction Algorithm suffer from Data Sparsity based on Iterate Grid Partition and Entropy Estimation (TPDS-IGP&EE) was proposed. Firstly, the moving region of trajectories was iteratively divided into a two-dimensional plane grid graph, and then the original trajectories were mapped to the grid graph so that each trajectory could be represented as a grid sequence. Secondly, an L-Z entropy estimator was used to calculate the entropy value of trajectory sequence, and a new trajectory space was generated by doing trajectory synthesis based on trajectory entropy. At last combining with the Sub-Trajectory Synthesis (SubSyn) algorithm, sparse trajectory prediction was implemented. The experimental results show when trajectory completed percentage increases towards 90%, the coverage of the Baseline algorithm decreases to almost 25%. TPDS-IGP&EE algorithm successfully coped with it as expected with only an unnoticeable drop in coverage, and could constantly answer almost 100% of query trajectories. And TPDS-IGP&EE algorithm's prediction accuracy was generally 4% higher than Baseline algorithm. At the same time, the prediction time of Baseline algorithm to 100 ms was too long, while the prediction time of TPDS-IGP&EE algorithm could be negligible (10 μs). TPDS-IGP&EE algorithm can make an effective prediction for the sparse trajectory, providing much wider predicting range, faster predicting speed and better predicting accuracy.

Key words: trajectory prediction, data sparsity, iterative grid partition, L-Z entropy estimation, sub-trajectory synthesis

摘要： 针对移动对象轨迹预测所面临的"数据稀疏"问题,即有效的历史轨迹空间不能覆盖所有可能的查询轨迹,提出了一种基于迭代网格划分和熵估计的稀疏轨迹预测算法(TPDS-IGP&EE).首先,对轨迹区域进行迭代网格划分并生成轨迹序列;然后,引入L-Z熵估计计算轨迹序列的熵值,在轨迹熵值的基础上进行轨迹综合形成新的轨迹空间;最后,结合子轨迹综合算法,进行稀疏轨迹预测.实验结果表明,当轨迹完整度达到90%以上,Baseline算法的查询覆盖率只有25%左右;而TPDS-IGP&EE算法几乎不受查询轨迹长度的影响,可以预测几乎100%的查询轨迹;并且TPDS-IGP&EE算法的预测准确率普遍高于Baseline算法4%左右;同时Baseline算法的预测时间非常长,达到100 ms,而TPDS-IGP&EE算法的预测时间(10 μs)几乎可以忽略不计.TPDS-IGP&EE算法能够有效地进行稀疏环境下的轨迹预测,具有更广的预测范围、更快的预测速度和较高的预测准确率.

关键词: 轨迹预测, 数据稀疏, 迭代网格划分, L-Z熵估计, 子轨迹综合

CLC Number:

TP312

LIU Leijun, ZHU Meng, ZHANG Lei. Sparse trajectory prediction method based on iterative grid partition and entropy estimation[J]. Journal of Computer Applications, 2015, 35(11): 3161-3165.

刘磊军, 朱猛, 张磊. 基于迭代网格划分和熵估计的稀疏轨迹预测[J]. 计算机应用, 2015, 35(11): 3161-3165.

References

[1] GONZALEZ M C, HIDALGO C A, BARABASI A L. Understanding individual human mobility patterns[J]. Nature, 2008, 453(7196): 779-782.
[2] SONG C, QU Z, BLUMM N, et al. Limits of predictability in human mobility[J]. Science, 2010, 327(5968): 1018-1021.
[3] ZHENG Y, ZHOU X. Computing with spatial trajectories[M]. Berlin: Springer, 2011: 3-20.
[4] Microsoft Research. T-drive trajectory data sample[EB/OL]. [2011-08-12]. http://research.microsoft.com/apps/pubs/?id=152883.
[5] ASHBROOK D, STARNER T. Using GPS to learn significant locations and predict movement across multiple users[J]. Personal and Ubiquitous Computing, 2003, 7(5): 275-286.
[6] LIU Z, FU J, ZHAO N. Users mobile track prediction method based on mobile communication data[J]. Computer Applications and Software, 2013, 30(2): 10-13.(刘震, 付俊辉, 赵楠. 基于移动通信数据的用户移动轨迹预测方法[J]. 计算机应用与软件, 2013, 30(2): 10-13.)
[7] PENG Q, DING Z, GUO L. Prediction of trajectory based on Markov chains[J]. Computer Science, 2010, 37(8): 189-193.(彭曲, 丁治明, 郭黎敏. 基于马尔可夫链的轨迹预测[J].计算机科学, 2010, 37(8): 189-193.)
[8] XUE A Y, ZHANG R, ZHENG Y, et al. Destination prediction by sub-trajectory synthesis and privacy protection against such prediction[C]// Proceedings of the 2013 IEEE 29th International Conference on Data Engineering. Piscataway: IEEE, 2013: 254-265.
[9] XUE A Y, QI J, XIE X, et al. Solving the data sparsity problem in destination prediction[J]. VLDB Journal, 2014, 24(2):1-25.
[10] LEMPEL A, ZIV J. On the complexity of finite sequences[J]. IEEE Transactions on Information Theory, 1976, 22(1): 75-81.
[11] GAO Y, KONTOYIANNIS I, BIENENSTOCK E. Estimating the entropy of binary time series: methodology, some theory and a simulation study[J]. Entropy, 2008, 10(2): 71-99.
[12] MCLNERNEY J, STEIN S, ROGERS A, et al. Exploring periods of low predictability in daily life mobility[C/OL].[2015-01-20].http://eprints.soton.ac.uk/339940/1/paper_extended_past2.pdf.
[13] ASHBROOK D, STARNER T. Using GPS to learn significant locations and predict movement across multiple users[J]. Personal and Ubiquitous Computing, 2003, 7(5): 275-286.
[14] KRUMM J, HORVITZ E. Predestination: Inferring destinations from partial trajectories[M]. Berlin: Springer, 2006: 243-260.
[15] WEI L Y, ZHENG Y, PENG W C. Constructing popular routes from uncertain trajectories[C]// Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2012: 195-203.

Sparse trajectory prediction method based on iterative grid partition and entropy estimation

基于迭代网格划分和熵估计的稀疏轨迹预测

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 10

Recommended Articles

Metrics

[1]	DAI Yurou, YANG Qing, ZHANG Fengli, ZHOU Fan. Trajectory prediction model of social network users based on self-supervised learning [J]. Journal of Computer Applications, 2021, 41(9): 2545-2551.
[2]	LI Xujuan, PI Jianyong, HUANG Feixiang, JIA Haipeng. Self-generated deep neural network based 4D trajectory prediction [J]. Journal of Computer Applications, 2021, 41(5): 1492-1499.
[3]	GAO Jian, MAO Yingchi, LI Zhitao. Trajectory prediction based on Gauss mixture time series model [J]. Journal of Computer Applications, 2019, 39(8): 2261-2270.
[4]	SUN Yasheng, JIANG Qi, HU Jie, QI Jin, PENG Yinghong. Attention mechanism based pedestrian trajectory prediction generation model [J]. Journal of Computer Applications, 2019, 39(3): 668-674.
[5]	WEN Kai, ZHU Chuanliang. Regularized matrix decomposition recommendation model integrating social networks and interest correlation [J]. Journal of Computer Applications, 2018, 38(9): 2523-2528.
[6]	LIU Jiangdong, LIANG Gang, FENG Cheng, ZHOU Hongyu. Collaborative filtering recommendation based on entropy and timeliness [J]. Journal of Computer Applications, 2016, 36(9): 2531-2534.
[7]	ZHANG Nan, LIN Xiaoyong, SHI Shenghui. Collaborative filtering recommendation method based on improved heuristic similarity model [J]. Journal of Computer Applications, 2016, 36(8): 2246-2251.
[8]	WANG Xing JIANG Xinhua LIN Jie XIONG Jinbo. Prediction of moving object trajectory based on probabilistic suffix tree [J]. Journal of Computer Applications, 2013, 33(11): 3119-3122.
[9]	LI Wangao ZHAO Xuemei SUN Dechang. Prediction of trajectory based on modified Bayesian inference [J]. Journal of Computer Applications, 2013, 33(07): 1960-1963.
[10]	. Effective hybrid collaborative filtering algorithm for alleviating data sparsity [J]. Journal of Computer Applications, 2009, 29(06): 1590-1593.