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

doi:10.11772/j.issn.1001-9081.2016.01.0039

计算机应用 ›› 2016, Vol. 36 ›› Issue (1): 39-43.DOI: 10.11772/j.issn.1001-9081.2016.01.0039

• 第32届中国数据库学术会议(NDBC 2015) • 上一篇下一篇

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

宋路杰, 孟凡荣, 袁冠

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

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

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).

摘要/Abstract

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

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

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

中图分类号:

TP311

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

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.

参考文献

[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.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	霍纬纲, 王慧芳. 基于自编码器和隐马尔可夫模型的时间序列异常检测方法[J]. 计算机应用, 2020, 40(5): 1329-1334.
[2]	马兰, 崔博花, 刘轩, 岳猛, 吴志军. 基于隐半马尔可夫模型的SWIM应用层DDoS攻击的检测方法[J]. 计算机应用, 2019, 39(7): 1973-1978.
[3]	王金策, 邓越萍, 史明, 周云飞. 多时间尺度时间序列趋势预测[J]. 计算机应用, 2019, 39(4): 1046-1052.
[4]	杨震, 王红军. 基于Adaboost-Markov模型的移动用户位置预测方法[J]. 计算机应用, 2019, 39(3): 675-680.
[5]	余江兰, 李向利, 赵朋飞. 基于核技巧和超图正则的稀疏非负矩阵分解[J]. 计算机应用, 2019, 39(3): 742-749.
[6]	霍峥, 张坤, 贺萍, 武彦斌. 满足本地化差分隐私的众包位置数据采集[J]. 计算机应用, 2019, 39(3): 763-768.
[7]	杨世强, 罗晓宇, 乔丹, 柳培蕾, 李德信. 基于滑动窗口和动态规划的连续动作分割与识别[J]. 计算机应用, 2019, 39(2): 348-353.
[8]	许瀚, 罗亮, 孙鹏, 孟飒. 基于马尔可夫模型的云系统安全性与性能建模[J]. 计算机应用, 2019, 39(11): 3304-3309.
[9]	李登刚, 陈香香, 李华丽, 王忠美. 基于超像素的流形正则化稀疏约束NMF混合像元分解算法[J]. 计算机应用, 2019, 39(10): 3100-3106.
[10]	冯钧, 李顶圣, 陆佳民, 张立霞. 基于HBase的路网移动对象时空索引方法[J]. 计算机应用, 2018, 38(6): 1575-1583.
[11]	李琰, 刘嘉勇. 基于作者主题模型和辐射模型的用户位置预测模型[J]. 计算机应用, 2018, 38(4): 939-944.
[12]	袁正午, 陈然. 基于多层次混合相似度的协同过滤推荐算法[J]. 计算机应用, 2018, 38(3): 633-638.
[13]	张全贵, 蔡丰, 李志强. 基于耦合多隐马尔可夫模型和深度图像数据的人体动作识别[J]. 计算机应用, 2018, 38(2): 454-457.
[14]	郭雷勇, 李宇, 林胜义, 谭洪舟. 用于隐马尔可夫模型语音带宽扩展的激励分段扩展方法[J]. 计算机应用, 2017, 37(8): 2416-2420.
[15]	李方伟, 李骐, 朱江. 改进的基于隐马尔可夫模型的态势评估方法[J]. 计算机应用, 2017, 37(5): 1331-1334.