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

An Efficient Adjoint Pattern Mining Algorithm for Moving Object

作　　者：王齐童 王鹏[1] 赵郁亮 汪卫[1] WANG Qitong;WANG Peng;ZHAO Yuliang;WANG Wei(School of Computer Science,Fudan University,Shanghai 201203,China;The Third Research Institute of the Ministry of Public Security,Shanghai 200031,China)

机构地区：[1]复旦大学计算机科学技术学院,上海201203 [2]公安部第三研究所,上海200031

出　　处：《计算机工程》2020年第4期97-106,122,共11页Computer Engineering

基　　金：国家自然科学基金(U1509213,61672163);上海市软件和集成电路产业发展专项(170512)。

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

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]