近似到达时间约束下的语义轨迹频繁模式挖掘

来源：软件学报杂志2018年第10期北京时间：

作者：吴瑕,唐祖锴,祝园园,彭煜玮,彭智勇

单位：吴瑕，软件工程国家重点实验室(武汉大学), 湖北 武汉 430072;武汉大学 计算机学院, 湖北 武汉 43007211,唐祖锴，武汉理工大学 计算机科学与技术学院, 湖北 武汉 43007002,祝园园，软件工程国家重点实验室(武汉大学), 湖北 武汉 43007203,彭煜玮，武汉大学 计算机学院, 湖北 武汉 43007204,彭智勇，武汉大学 计算机学院, 湖北 武汉 43007205

摘要：随着GPS定位技术的不断发展与智能移动设备的普及，轨迹数据的获取变得越来越容易，同时，轨迹数据相关应用的需求也逐渐增多.在轨迹数据上加入语义信息，可以得到体积较小、质量较高、能够更好地反映用户行为的语义轨迹，在其上实现旅游线路推荐、路线预测、用户生活模式挖掘、朋友推荐等应用，可以更好地满足用户需求.挖掘语义轨迹的频繁模式是实现这些应用的技术基础，而在很多情况下，用户对语义轨迹频繁模式常存在到达时间方面的需求，比如按特定时间游玩热门景点的同时需要按时到达车站候车.现有的语义轨迹模式挖掘方法大多没有考虑到达时间的约束，挖掘出的频繁模式缺少到达时间信息；少数方法考虑了精确的到达时间，但因为约束太强会导致无法挖掘到频繁的模式.因此，首次对近似到达时间约束下的语义轨迹频繁模式（approximate arrival-time constrained frequent pattern，简称AAFP）挖掘方法进行了研究，并给出了其形式化定义；通过时间轴划分提出了挖掘AAFP的基线算法，并通过建立索引AAP-tree提出了改进后的高效、灵活的AAFP挖掘算法；之后提出了信息熵增量公式，并给出了时间轴划分及AAP-tree的高效维护方法；最后在真实数据集上进行实验，验证了方法的有效性及高效性.

关键词：轨迹数据;语义轨迹;近似到达时间;轨迹频繁模式;频繁模式挖掘

基金资助：科技部国家重点研发计划（2016YFB1000700）；国家自然科学基金（61502349）