Moving object location prediction algorithm based on Markov model and trajectory similarity

doi:10.11772/j.issn.1001-9081.2016.01.0039

Journal of Computer Applications ›› 2016, Vol. 36 ›› Issue (1): 39-43.DOI: 10.11772/j.issn.1001-9081.2016.01.0039

Previous Articles Next Articles

Moving object location prediction algorithm based on Markov model and trajectory similarity

SONG Lujie, MENG Fanrong, YUAN Guan

School of Computer Science and Technology, China University of Mining and Technology, Xuzhou Jiangsu 221116, China

Received:2015-08-27 Revised:2015-09-22 Online:2016-01-10 Published:2016-01-09
Supported by:
This work is partially supported by the National High Technology Research and Development Program (863 Program) of China (2012AA011004), the Fundamental Research Funds for the Central Universities (2013XK10), the Coal Joint Funds of the National Natural Science Foundation of China (U1261201).

基于Markov模型与轨迹相似度的移动对象位置预测算法

宋路杰, 孟凡荣, 袁冠

中国矿业大学计算机科学与技术学院, 江苏徐州 221116

通讯作者: 宋路杰(1990-),男,河南永城人,硕士研究生,主要研究方向:数据挖掘、轨迹预测
作者简介:孟凡荣(1962-),女,辽宁沈阳人,教授,博士,主要研究方向:数据库、数据挖掘;袁冠(1982-),男,江苏徐州人,副教授,博士,主要研究方向:数据挖掘、知识工程。
基金资助:
国家863计划项目(2012AA011004);中央高校基本科研业务费专项资金资助项目(2013XK10);国家自然科学基金煤炭联合基金重点项目(U1261201)。

Abstract

Abstract: Focusing on low prediction accuracy of the low-order Markov model and high sparsity rate of the high-order Markov model, a moving object location prediction algorithm based on Markov Model and Trajectory Similarity (MMTS) was proposed. The moving object's historical trajectory was modeled by using Markov thinking, and trajectory similarity was acted as an important factor of location prediction. With the result set predicted by Markov model as candidate set, the trajectory similarity factor was combined to get the final prediction. The experimental results show that, compared with the k-order Markov model, the predictive capability of the MMTS method is not greatly affected with the change of training sample size and the value of k, and the average accuracy is improved by more than 8% while significantly reducing the sparsity rate of k-order Markov model. So, the proposed method not only solves the problem of high sparsity rate and low prediction accuracy of the k-order Markov model, but also improves the stability of prediction.

Key words: trajectory similarity, location prediction, moving object, Markov model, sparsity

摘要： 针对低阶Markov模型预测精度较差,以及多阶Markov模型预测稀疏率高的问题,提出一种基于Markov模型与轨迹相似度(MMTS)的移动对象位置预测算法。该方法借鉴了Markov模型思想对移动对象的历史轨迹进行建模,并将轨迹相似度作为位置预测的重要因素,以Markov预测模型的预测结果集作为预测候选集,结合相似度因素得出最终预测结果。实验结果表明,与k阶Markov模型相比,该方法的预测性能不会随着训练样本大小及阶数k的变化受到很大的影响,并且在大幅降低k阶Markov模型预测稀疏率的同时将预测精度平均提高了8%以上。所提方法不仅解决了k阶Markov模型的预测稀疏率高及预测精度不足的问题;同时提高了预测的稳定性。

关键词: 轨迹相似度, 位置预测, 移动对象, 马尔可夫模型, 稀疏性

CLC Number:

TP311

SONG Lujie, MENG Fanrong, YUAN Guan. Moving object location prediction algorithm based on Markov model and trajectory similarity[J]. Journal of Computer Applications, 2016, 36(1): 39-43.

宋路杰, 孟凡荣, 袁冠. 基于Markov模型与轨迹相似度的移动对象位置预测算法[J]. 计算机应用, 2016, 36(1): 39-43.

References

[1] 王兴,蒋新华,林劼,等.基于概率后缀树的移动对象轨迹预测[J].计算机应用,2013,33(11):3119-3122.(WANG X, JIANG X H, LIN J, et al. Prediction of moving object trajectory based on probabilistic suffix tree [J]. Journal of computer applications, 2013, 33(11): 3119-3122.)
[2] BELLOTTI V, BEGOLE B, CHI E H, et al. Activity-based seren-dipitous recommendations with the Magitti mobile leisure guide [C]// Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. New York: ACM, 2008: 1157-1166.
[3] GIDÓFALVI G, BORGELT C, KAUL M, et al. Frequent route based continuous moving object location-and density prediction on road networks [C]// Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York: ACM, 2011: 381-384.
[4] YING J J C, LEE W C, WENG T C, et al. Semantic trajectory mining for location prediction [C]// Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York: ACM, 2011: 34-43.
[5] ABRAHAM S, SOJAN LAL P. Spatio-temporal similarity of net-work-constrained moving object trajectories using sequence alignment of travel locations [J]. Transportation research part C: emerging technologies, 2012, 23: 109-123
[6] 余雪岗,刘衍珩,魏达,等.用于移动路径预测的混合Markov模型[J].通信学报,2006,27(12):61-69.(YU X G, LIU Y H, WEI D, et al. Hybrid Markov mode for mobile path prediction [J]. Journal on communications, 2006, 27(12): 61-69.)
[7] FANG D. Moving object trajectory based spatio-temporal mobility prediction [D]. Stockholm: Royal Institute of Technology, 2012.
[8] CHEN M, LIU Y, YU X. NLPMM: a next location predictor with Markov modeling [C]// PAKDD 2014: Proceedings of the 18th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining. Berlin: Springer, 2014: 186-197.
[9] BURBEY I, MARTIN T L. Predicting future locations using prediction-by-partial-match [C]// Proceedings of the First ACM International Workshop on Mobile Entity Localization and Tracking in GPS-less Environments. New York: ACM, 2008: 1-6.
[10] JACQUET P, SZPANKOWSKI W, APOSTOL I. An universal predictor based on pattern matching: preliminary results 1 [M]// Mathematics and computer science. Berlin: Springer, 2000: 75-85.
[11] JACQUET P, SZPANKOWSKI W, APOSTOL I. A universal predictor based on pattern matching [J]. IEEE transactions on information theory, 2002, 48(6): 1462-1472.
[12] 刘奎思,肖俊超,丁治明,等.轨迹数据库中热门区域的发现[J].软件学报,2013,24(8):1816-1835.(LIU K S, XIAO J C, DING Z M, et al. Discovery of hot region in trajectory databases [J]. Journal of software, 2013, 24(8): 1816-1835.)
[13] VLACHOS M, KOLLIOS G, GUNOPULOS D. Discovering similar multidimensional trajectories [C]// Proceedings of the 18th International Conference on Data Engineering. Piscataway, NJ: IEEE, 2002: 673-684.
[14] VLACHOS M, KOLLIOS G, GUNOPULOS D. Elastic translation invariant matching of trajectories [J]. Machine learning, 2005, 58(2/3): 301-334.
[15] KRUMM J. A Markov model for driver turn prediction [C]// SAE 2008 World Congress. Detroit, MI: [s.n.], 2008: No. 2008-01-0195.
[16] CHENG C, JAIN R, VAN DEN BERG E. Location prediction algorithms for mobile wireless systems [C]// Wireless Internet Handbook. Boca Raton, FL: CRC Press, 2003: 245-263.
[17] XUE A, ZHANG R, ZHENG Y, et al. Destination prediction by sub-trajectory synthesis and privacy protection against such prediction [C]// ICDE 2013: Proceedings of the 2013 IEEE 29th International Conference on Data Engineering. Piscataway, NJ: IEEE, 2013: 254-265.
[18] SONG L, KOTZ D, JAIN R, et al. Evaluating location predictors with extensive Wi-Fi mobility data [C]// INFOCOM 2004: Proceedings of the Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies. Piscataway, NJ: IEEE, 2004: 1414-1424.

Moving object location prediction algorithm based on Markov model and trajectory similarity

基于Markov模型与轨迹相似度的移动对象位置预测算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	Chenyu GE, Liang DONG, Yikun XU, Yi CHANG, Hongming ZHANG. Global-scale radar data restoration algorithm based on total variation and low-rank group sparsity [J]. Journal of Computer Applications, 2021, 41(11): 3353-3361.
[2]	Yusheng HU, Bingwei HE, Qingkang DENG. Moving object detection and static map reconstruction with hybrid vision system [J]. Journal of Computer Applications, 2021, 41(11): 3332-3336.
[3]	LIN Tengtao, ZHA Siming, CHEN Lei, LONG Xianzhong. Graph trend filtering guided noise tolerant multi-label learning model [J]. Journal of Computer Applications, 2021, 41(1): 8-14.
[4]	HUO Weigang, WANG Huifang. Time series anomaly detection method based on autoencoder and HMM [J]. Journal of Computer Applications, 2020, 40(5): 1329-1334.
[5]	LYU Yike, XU Kai, HUANG Zhenqiang. Trajectory similarity measurement method based on area division [J]. Journal of Computer Applications, 2020, 40(2): 578-583.
[6]	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.
[7]	CHEN Shanxue, CHU Chengquan. Hyperspectral unmixing based on sparse and orthogonal constrained non-negative matrix factorization [J]. Journal of Computer Applications, 2019, 39(8): 2276-2280.
[8]	MA Lan, CUI Bohua, LIU Xuan, YUE Meng, WU Zhijun. Hidden semi-Markov model-based approach to detect DDoS attacks in application layer of SWIM system [J]. Journal of Computer Applications, 2019, 39(7): 1973-1978.
[9]	WANG Jince, DENG Yueping, SHI Ming, ZHOU Yunfei. Time series trend prediction at multiple time scales [J]. Journal of Computer Applications, 2019, 39(4): 1046-1052.
[10]	YANG Zhen, WANG Hongjun. Location prediction method of mobile user based on Adaboost-Markov model [J]. Journal of Computer Applications, 2019, 39(3): 675-680.
[11]	YU Jianglan, LI Xiangli, ZHAO Pengfei. Sparse non-negative matrix factorization based on kernel and hypergraph regularization [J]. Journal of Computer Applications, 2019, 39(3): 742-749.
[12]	HUO Zheng, ZHANG Kun, HE Ping, WU Yanbin. Crowdsourcing location data collection for local differential privacy [J]. Journal of Computer Applications, 2019, 39(3): 763-768.
[13]	YANG Shiqiang, LUO Xiaoyu, QIAO Dan, LIU Peilei, LI Dexin. Continuous action segmentation and recognition based on sliding window and dynamic programming [J]. Journal of Computer Applications, 2019, 39(2): 348-353.
[14]	XU Han, LUO Liang, SUN Peng, MENG Sa. Cloud system security and performance modeling based on Markov model [J]. Journal of Computer Applications, 2019, 39(11): 3304-3309.
[15]	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.