计算机工程 ›› 2020, Vol. 46 ›› Issue (4): 97-106,122.doi: 10.19678/j.issn.1000-3428.0053910

• 人工智能与模式识别 • 上一篇    下一篇

一种高效的移动对象伴随模式挖掘算法

王齐童1, 王鹏1, 赵郁亮1,2, 汪卫1   

  1. 1. 复旦大学 计算机科学技术学院, 上海 201203;
    2. 公安部第三研究所, 上海 200031
  • 收稿日期:2019-02-13 修回日期:2019-04-24 出版日期:2020-04-15 发布日期:2019-05-27
  • 作者简介:王齐童(1993-),男,硕士研究生,主研方向为时空数据管理;王鹏,副教授、博士生导师;赵郁亮,博士研究生;汪卫,教授、博士生导师。
  • 基金项目:
    国家自然科学基金(U1509213,61672163);上海市软件和集成电路产业发展专项(170512)。

An Efficient Adjoint Pattern Mining Algorithm for Moving Object

WANG Qitong1, WANG Peng1, ZHAO Yuliang1,2, WANG Wei1   

  1. 1. School of Computer Science, Fudan University, Shanghai 201203, China;
    2. The Third Research Institute of the Ministry of Public Security, Shanghai 200031, China
  • Received:2019-02-13 Revised:2019-04-24 Online:2020-04-15 Published:2019-05-27

摘要: 从时空维度中寻找轨迹相似、时间相近的对象集合,即挖掘移动对象的伴随模式,在基于地理位置的用户行为分析中被广泛使用。然而现有移动对象相似性挖掘算法难以处理时间连续、空间离散、时空相关并且数据量大的时空数据。针对此类数据,设计基于滑动窗口、Apriori性质和贪心选择策略的宽度优先搜索算法,对移动对象伴随模式挖掘问题进行求解。同时结合基于哈希的迭代剪枝算法和基于摘要信息的剪枝算法,设计两层剪枝算法以去除冗余的中间结果。在真实数据上的实验结果表明,与仅使用哈希迭代或摘要信息的剪枝算法相比,该算法的剪枝效率较高,并且能够稳定去除99%以上的冗余数据。

关键词: 时空数据, 伴随模式, 滑动窗口, 贪心策略, 剪枝算法, 摘要信息

Abstract: Mining adjoint patterns of moving objects is finding the set of objects with similar trajectories and time from a spatio-temporal perspective,which is widely used in user behavior analysis based on geographical location.However,the existing similarity mining algorithms for moving objects can hardly address large amounts of temporally continuous and spatially discrete data of spatio-temporal correlation.To deal with the problem,this paper proposes a width-first search algorithm based on sliding window,Apriori property and greedy selection strategy to solve the problem of mining adjoint patterns of moving objects.Also,a two-layer pruning algorithm is designed combining the iterative pruning algorithm based on Hash iteration and pruning algorithm based on summary information,so as to remove redundant intermediate results.Experimental results on real data show that the pruning efficiency of the proposed algorithm is higher than that of pruning algorithms using only Hash iteration or summary information,meanwhile it can stably remove over 99% of redundant data.

Key words: spatio-temporal data, adjoint pattern, sliding window, greedy strategy, pruning algorithm, summary information

中图分类号: