基于前缀投影技术的大规模轨迹预测模型

发布时间：2018-01-21 11:21

本文关键词： 轨迹预测前缀投影频繁序列模式轨迹匹配马尔可夫链　出处：《软件学报》2017年11期 　论文类型：期刊论文

【摘要】：智能手机、车载GPS终端、可穿戴设备产生了海量的轨迹数据,这些数据不仅描述了移动对象的历史轨迹,而且精确地反映出移动对象的运动特点.已有轨迹预测方法的不足在于:不能同时兼具预测的准确性和时效性,有效的轨迹预测受限于路网等局部空间范围,无法处理复杂、大规模位置数据.为了解决上述问题,针对海量移动对象轨迹数据,结合频繁序列模式发现的思想,提出了基于前缀投影技术的轨迹预测模型PPTP(prefix projection based trajectory prediction model),包含两个关键步骤:(1)挖掘频繁轨迹模式,构造投影数据库并递归挖掘频繁前序轨迹模式;(2)轨迹匹配,以不同频繁序列模式作为前缀增量式扩展生成频繁后序轨迹,将大于最小支持度阈值的最长连续轨迹作为结果输出.算法的优势在于:可以通过较短的频繁序列模式,增量式生成长轨迹模式;不会产生无用的候选轨迹,弥补频繁模式挖掘计算代价较高的不足.利用真实大规模轨迹数据进行多角度实验,表明PPTP轨迹预测算法具有较高的预测准确性,相对于1阶马尔可夫链预测算法,其平均预测准确率可以提升39.8%.基于所提出的轨迹预测模型,开发了一个通用的轨迹预测系统,能够可视化输出完整的轨迹路线,为用户路径规划提供辅助决策支持.
[Abstract]:Smart phones, on-board GPS terminals, and wearable devices produce massive amounts of track data, which not only describe the historical trajectory of moving objects. And accurately reflects the movement characteristics of moving objects. The shortcomings of existing trajectory prediction methods are that they can not simultaneously have the accuracy and timeliness of prediction, and effective trajectory prediction is limited to the local space range such as road network. In order to solve the above problem, aiming at the massive moving object trajectory data, combining the idea of frequent sequence pattern discovery. A trajectory prediction model PPTPbased on prefix projection technique is proposed. Prefix projection based trajectory prediction model). It consists of two key steps: 1) mining frequent trajectory patterns, constructing projection database and recursively mining frequent preorder trajectory patterns; (2) trajectory matching, using different frequent sequence patterns as prefix incremental expansion to generate frequent post-sequence trajectories. The maximum continuous trajectory larger than the minimum support threshold is taken as the result output. The advantage of the algorithm lies in that the incremental growth trajectory mode can be obtained through shorter frequent sequence patterns; It will not produce useless candidate trajectories, and make up for the high cost of frequent pattern mining. Using real large scale trajectory data to carry out multi-angle experiments. The results show that the PPTP trajectory prediction algorithm has high prediction accuracy. Compared with the first-order Markov chain prediction algorithm, the average prediction accuracy can be improved by 39.8%, based on the proposed trajectory prediction model. A general trajectory prediction system is developed, which can visualize the complete trajectory path and provide a decision support for user path planning.
【作者单位】：成都信息工程大学网络空间安全学院;成都信息工程大学管理学院;西南交通大学信息科学与技术学院;深圳大学计算机与软件学院;Department
【分类号】：TP311.13
【正文快照】： 随着位置大数据分析处理技术[1]的快速发展,离散的时空位置点中蕴藏的移动行为规律被人们挖掘和利用.不同于简单的位置签到数据,轨迹数据是连续和完整的具有时效性的运动个体移动规律和社交信息的展示,因此,理解并利用好时空轨迹数据具有实际意义.车载GPS等设备采集的轨迹数据

【相似文献】