基于空间邻近搜索的移动轨迹相对时间模式挖掘方法

doi:10.11772/j.issn.1001-9081.2018051023

计算机应用 ›› 2018, Vol. 38 ›› Issue (11): 3326-3331.DOI: 10.11772/j.issn.1001-9081.2018051023

• 应用前沿、交叉与综合 • 上一篇下一篇

基于空间邻近搜索的移动轨迹相对时间模式挖掘方法

张海涛¹, 周欢², 张国楠³

1. 南京邮电大学地理与生物信息学院, 南京 210023;
2. 南京邮电大学通信与信息工程学院, 南京 210003;
3. 南京邮电大学计算机学院、软件学院、网络空间安全学院, 南京 210023

收稿日期:2018-05-17 修回日期:2018-06-15 出版日期:2018-11-10 发布日期:2018-11-10
通讯作者: 周欢
作者简介:张海涛(1978-),男,河南商水人,副教授,博士,主要研究方向:移动GIS理论方法与关键技术、时空数据挖掘、LBS隐私保护;周欢(1993-),男,江苏连云港人,硕士研究生,主要研究方向:轨迹数据挖掘、隐私保护;张国楠(1997-),男,青海西宁人,主要研究方向:轨迹数据挖掘、隐私保护。
基金资助:
国家自然科学基金资助项目（41201465）；江苏省自然科学基金资助项目（BK2012439）；江苏省社会发展项目（BE2016774）。

Mining method of trajectory interval pattern based on spatial proximity searching

ZHANG Haitao¹, ZHOU Huan², ZHANG Guonan³

1. School of Geographic and Biologic Information, Nanjing University of Posts and Telecommunications, Nanjing Jiangsu 210023, China;
2. School of Telecommunications & Information Engineering, Nanjing University of Posts and Telecommunications, Nanjing Jiangsu 210003, China;
3. School of Computer Science, Nanjing University of Posts and Telecommunications, Nanjing Jiangsu 210003, China

Received:2018-05-17 Revised:2018-06-15 Online:2018-11-10 Published:2018-11-10
Supported by:
This work is partially supported by the National Natural Science Foundation of China (41201465), the Jiangsu Provincial Natural Science Foundation (BK2012439), the Jiangsu Social Development Project (BE2016774).

摘要/Abstract

摘要： 针对传统移动轨迹模式挖掘方法挖掘速度慢、占用最大内存大的问题，提出一种基于空间邻近搜索的移动轨迹相对时间模式挖掘方法。该方法包括5个阶段：1）对移动轨迹数据进行时空划分，并基于移动轨迹数据与时空格的匹配得到移动轨迹数据对应的时空格序列。2）扫描所有的时空格序列数据得到空间网格集合，并通过空间网格与时空格序列的包含运算得到所有的频繁空间网格。3）频繁空间网格转变为长度为1的频繁相对时间模式。4）基于空间邻近搜索的方式进行模式增长，得到以频繁空间网格为单元的候选相对时间模式，并通过相对时间模式与时空格序列的匹配运算，计算相对时间模式的支持度。5）基于设定的支持度阈值，得到所有频繁的相对时间模式。实验结果表明：所提方法由于采用了基于空间邻近搜索的方式进行模式扩展，大幅减小候选相对时间模式的搜索范围。与传统方法相比，所提方法具有挖掘速度快、占用最大内存少的优点。另外，方法在运行时间上具有更好的稳定性和可扩展性，而在占用最大内存上的稳定性与可扩展性与传统方法基本相近。该方法有助于移动轨迹模式挖掘方法提升挖掘速度、减少占用最大内存。

关键词: 移动轨迹数据, 空间邻近搜索, 时空格, 支持度, 相对时间模式

Abstract: Concerning the problem that traditional trajectory pattern mining methods have the problems of slow mining and large maximum amount of memory, a method of mining trajectory interval patterns based on spatial proximity searching was proposed. The implementation of the proposed method consists of five phases:1) Space-time discretization is performed on the trajectories, and space-time cell sequences corresponding to trajectories are achieved. 2) All the space-time cell sequences are scanned to get all no-duplication spatial cells, and all frequent spatial cells are obtained by the inclusion operation of the spatial cells and the cell sequences. 3) Frequent spatial cells are transformed into frequent interval patterns of length one. 4) Candidate interval patterns with the frequent spatial cells as units are generated by spatial proximity searching, and the support value of the candidate patterns are calculated by matching the patterns and the space-time cell sequences. 5) Based on the set support threshold, all frequent interval patterns are obtained. The experimental results show that the proposed method has the advantages of faster mining and less maximum amount of memory than traditional methods. Furthermore, in terms of running time, the proposed method has better stability and scalability performance than traditional methods. This method is helpful to the trajectory pattern mining methods to increase the mining speed and reduce the maximum amount of memory.

Key words: trajectory data, spatial proximity searching, space-time cell, support value, interval pattern

中图分类号:

TP208

张海涛, 周欢, 张国楠. 基于空间邻近搜索的移动轨迹相对时间模式挖掘方法[J]. 计算机应用, 2018, 38(11): 3326-3331.

ZHANG Haitao, ZHOU Huan, ZHANG Guonan. Mining method of trajectory interval pattern based on spatial proximity searching[J]. Journal of Computer Applications, 2018, 38(11): 3326-3331.

参考文献

[1] WU G, DING Y, LI Y, et al. Mining spatio-temporal reachable regions over massive trajectory data[C]//Proceedings of the 2017 IEEE 33rd International Conference on Data Engineering. Piscataway, NJ:IEEE, 2017:1283-1294.
[2] 谢邦昌,斯介生.大数据分析中轨迹数据挖掘的现状与挑战[J].中国统计,2016(8):13-15.(XIE B C, SI J S. Current status and challenges of trajectory data mining in big data analysis[J].China Statistics,2016(8):13-15.)
[3] SHAW A A, GOPALAN N P. Finding frequent trajectories by clustering and sequential pattern mining[J]. Journal of Traffic and Transportation Engineering (English Edition), 2014, 1(6):393-403.
[4] 张昕,宋顶利.城市道路交通数据挖掘研究与应用[J].办公室业务,2015(4):87,89.(ZHANG X, SONG D L. Research and application of urban road traffic data mining[J]. Office Service, 2015(4):87,89.)
[5] YING J C, LEE W C, TSENG V S. Mining geographic-temporal-semantic patterns in trajectories for location prediction[J]. ACM Transactions on Intelligent Systems & Technology, 2013, 5(1):1-33.
[6] DJENOURI Y, COMUZZI M. Combining Apriori heuristic and bio-inspired algorithms for solving the frequent itemsets mining problem[J]. Information Sciences, 2017, 420:1-15.
[7] VIJAYALAKSHMI V, PETHALAKSHMI A. Mining of frequent itemsets with an enhanced Apriori algorithm[J]. International Journal of Computer Applications, 2013, 81(4):1-4.
[8] 袁晓建,张岐山,甘智平,等.Apriori算法的改进及在电子商务中的应用[J].福州大学学报(自然科学版), 2018, 46(3):330-334.(YUAN X J, ZHANG S S, GAN Z P, et al. Improvement of Apriori algorithm and its application in electronic commerce[J]. Journal of Fuzhou University (Natural Science Edition), 2018, 46(3):330-334.)
[9] 倪政君,夏哲雷.一种基于fp-tree的Apriori算法改进研究[J].中国计量大学学报,2018,29(1):50-54. (NI Z J, XIA Z L. Study on an improved Apriori algorithm based on fp-tree[J]. Journal of China Measurement University, 2018, 29(1):50-54.)
[10] ALOYSIUS G, BINU D. Original article:an approach to products placement in supermarkets using prefixspan algorithm[J]. Journal of King Saud University:Computer & Information Sciences, 2013, 25(1):77-87.
[11] 王晓雪.序列模式挖掘算法的研究[J].智能计算机与应用,2016,6(6):132-133,138. (WANG X X. Study on sequential pattern mining algorithm[J]. Intelligent Computer and Applications, 2016,6(6):132-133,138.)
[12] CAO H, MAMOULIS N, CHEUNG D W. Mining frequent spatio-temporal sequential patterns[C]//Proceedings of the 5th IEEE International Conference on Data Mining. Washington, DC:IEEE Computer Society, 2005:82-89.
[13] SHAW A A, GOPALAN N P. Frequent pattern mining of trajectory coordinates using Apriori algorithm[J]. International Journal of Computer Applications, 2011, 22(9):1-7.
[14] PASQUIER C, SELMAOUI-FOLCHER N. Frequent pattern mining in attributed trees:algorithms and applications[J]. Knowledge and Information Systems, 2016, 46(3):1-24.
[15] GATUHA G, JIANG T. Novel frequent pattern mining algorithm based on parallelization scheme[J]. International Journal of Engineering Research in Africa, 2016, 23:131-140.
[16] KHOSHAHVAL S, FARNAGHI M, TALEAI M. Spatio-temporal pattern mining on trajectory data using ARM[EB/OL].[2018-01-20]. https://www.int-arch-photogramm-remote-sens-spatial-inf-sci.net/XLⅡ-4-W4/395/2017/isprs-archives-XLⅡ-4-W4-395-2017.pdf.
[17] 张海涛, 葛国栋, 黄慧慧,等. 匿名集序列规则与转移概率矩阵的空间预测和实验[J]. 地球信息科学学报, 2015, 17(4):391-400. (ZHANG H T, GE G D, HUANG H H, et al. Space prediction and experiment of anonymous set sequence rules and transition probability matrix[J]. Journal of Geo-Information Science, 2015, 17(4):391-400.)

基于空间邻近搜索的移动轨迹相对时间模式挖掘方法

Mining method of trajectory interval pattern based on spatial proximity searching

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 9

编辑推荐

Metrics

[1]	杜媛, 张世伟. 基于重构的改进自然排序树算法[J]. 计算机应用, 2019, 39(2): 441-445.
[2]	张海清, 李代伟, 刘胤田, 龚程, 于曦. 最大模糊频繁模式挖掘算法[J]. 计算机应用, 2017, 37(5): 1424-1429.
[3]	李学明, 张朝阳, 佘维军. 基于用户回复内容观点支持度的评论有用性计算[J]. 计算机应用, 2016, 36(10): 2767-2771.
[4]	刘旭辉邵世煌余光柱. 基于激励的关联规则的挖掘[J]. 计算机应用, 2009, 29(1): 189-192.
[5]	张慧哲王坚. 多重最小支持度频繁项集挖掘算法研究[J]. 计算机应用, 2007, 27(9): 2290-2293.
[6]	张健王蔚. 基于支持度与置信度阈值优化技术的关联分类算法[J]. 计算机应用, 2007, (12): 3032-3034.
[7]	吴安阳，赵卫东. 基于多最小支持度的空间关联规则发现[J]. 计算机应用, 2005, 25(09): 2171-2174.
[8]	徐泉清，朱玉文，刘万春. 基于概念格的关联规则算法[J]. 计算机应用, 2005, 25(08): 1856-1857.
[9]	尹群，王丽珍，田启明. 一种基于概率的加权关联规则挖掘算法[J]. 计算机应用, 2005, 25(04): 805-807.