一种时空轨迹群体运动移动簇模式的排序算法  

Algorithm for Ranking Group Moving Clustering Pattern from Spatio-temporal Trajectories

作　　者：张玉洁 吉根林 赵斌[1] 张书亮[2] ZHANG Yu-jie;JI Gen-lin;ZHAO Bin;ZHANG Shu-liang(School of Computer Science and Technology,Nanjing Normal University,Nanjing 210023,China;School of Geography Science,Nanjing Normal University,Nanjing 210023,China)

机构地区：[1]南京师范大学计算机科学与技术学院,南京210023 [2]南京师范大学地理科学学院,南京210023

出　　处：《小型微型计算机系统》2018年第10期2169-2175,共7页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(41471371)资助

摘　　要：移动对象的群体运动移动簇模式是时空轨迹模式挖掘的重要内容,可用于发现群体运动规律、运动趋势以及群体事件.轨迹模式挖掘过程中通常会产生大量移动簇模式,然而用户感兴趣的只是少数一部分.我们可以通过对移动簇模式进行排序,从而帮助用户找出其感兴趣的少数移动簇模式,但目前针对移动对象群体运动移动簇模式排序的研究工作尚未报道,为此本文提出群体运动移动簇模式排序算法.首先利用移动簇所包含的空间属性,建立"移动簇-兴趣点"的图模型,并基于该模型提出重启式随机游走的群体运动移动簇模式排序算法RWR-Ranking,对大量移动簇进行排序,使得用户感兴趣的结果尽可能排在前面;此外,对RWR-Ranking方法进行改进,结合移动簇所包含的时空属性提出带权重的重启式随机游走的群体运动移动簇模式排序算法WRWR-Ranking;最后,利用真实轨迹数据集进行实验,验证了本文所提出的方法的有效性.Group moving clustering pattern is an essential problem in spatio-temporal trajectory pattern mining which is used to get group moving rules, group moving trend and group events. A large number of group moving clustering patterns are produced in trajectory data mining, but users are interested in a few patterns, we can sort the moving clustering pattern and help users find interested moving clustering patterns. However, the related research has not been reported yet, so we propose a ranking algorithm of group moving clustering pattern. Firstly, we bulid a moving cluster-POI graph which uses the spatial attributes. Based on such model, we propose RWR-Ranking algorithm which uses random walk with restart to rank group moving clustering pattern. RWR-Ranking can rank a large number of moving clusters so that those well-performed patterns rank in front. Additionally, RWR-Ranking is improved, we propose WRWR-Ranking algorithm which uses weighted random walk with restart to rank group moving clustering pattern. Finally, experiment results show the effectiveness of our method RWR-Ranking and WRWR-Ranking.

关 键 词：轨迹数据挖掘 群体运动移动簇模式 移动簇模式排序 重启式随机游走模型 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]