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

作者简介:

吴瑕(1986-),女,云南昆明人,硕士,主要研究领域为轨迹数据管理;唐祖锴(1977-),男,博士,副教授,CCF专业会员,主要研究领域为软件工程,物联网工程,数据库技术;祝园园(1984-),女,博士,副教授,CCF专业会员,主要研究领域为数据库,数据挖掘;彭煜玮(1980-),男,博士,副教授,CCF专业会员,主要研究领域为时空数据管理,数据库管理系统,高端制造业大数据管理;彭智勇(1963-),男,博士,教授,博士生导师,CCF会士,主要研究领域为复杂数据管理,可信数据管理,Web数据管理.

通讯作者:

彭智勇,E-mail:peng@whu.edu.cn

中图分类号:

基金项目:

科技部国家重点研发计划(2016YFB1000700);国家自然科学基金(61502349)


Frequent Pattern Mining With Approximate Arrival-Time in Semantic Trajectories
Author:
Affiliation:

Fund Project:

Ministry of Science and Technology of China, National Key Research and Development Program (2016YFB 1000700); National Natural Science Foundation of China (61502349)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    Abstract:

    Along with the development of the GPS positioning technology and smart mobile devices, more and more trajectory data are collected continuously every day. Thus, managing and mining useful information from these trajectories is critical in many application areas. Compared with raw trajectory data, semantic trajectory data equipped with semantic information has better quality, less volume and higher description ability, and thus it can be used in many applications such as trip recommendation, next location prediction, life pattern understanding, and friend recommendation. Mining frequent pattern in semantic trajectories is the fundamental problem in above tasks. In many circumstances, users may have the requirements on the arrival-time, e.g., users may want to visit a popular view spot at a certain timestamp and then arrive the railway station on time. Most of existing approaches on semantic trajectory pattern mining do not consider the arrival-time, and only a few existing approaches take the accurate arrival-time as the constraint, but they can barely find frequent patterns under such a strict time constraint. This paper, for the first time, studies the approximate arrival-time constrained frequent pattern (AAFP) mining problem. First, a baseline algorithm of mining AAFP is given by dividing the time axis into intervals. Then, an improved flexible algorithm is proposed to significantly improve the efficiency based on the AAP-tree index. Finally, a strategy to maintain the AAP-tree and the set of time axis partitions is introduced based on incremental information entropy. The experimental results on real trajectory datasets validate the effectiveness and efficiency of the proposed algorithms.

    参考文献
    相似文献
    引证文献
引用本文

吴瑕,唐祖锴,祝园园,彭煜玮,彭智勇.近似到达时间约束下的语义轨迹频繁模式挖掘.软件学报,2018,29(10):3184-3204

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2017-05-07
  • 最后修改日期:2017-08-25
  • 录用日期:
  • 在线发布日期: 2018-03-14
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号