一种用户频繁移动模式并行挖掘算法

doi:10.3969/j.issn.0253-2778.2018.01.008

中国科学技术大学学报 ›› 2018, Vol. 48 ›› Issue (1): 57-64.DOI: 10.3969/j.issn.0253-2778.2018.01.008

一种用户频繁移动模式并行挖掘算法

朱一波，鲍培明，吉根林

南京师范大学计算机科学与技术学院，江苏南京 210046

收稿日期:2017-05-20 修回日期:2017-06-23 出版日期:2018-01-01 发布日期:2018-01-01
通讯作者: 鲍培明
作者简介:朱一波，男，1994年生,硕士生.研究方向：数据挖掘及其应用. E-mail: zyb0619@163.com
基金资助:
国家自然科学基金（41471371）资助.

A parallel algorithm for mining user frequent moving patterns

ZHU Yibo, BAO Peiming, JI Genling

College of Computer Science and Technology, Nanjing Normal University, Nanjing 210046, China）

Received:2017-05-20 Revised:2017-06-23 Online:2018-01-01 Published:2018-01-01

摘要/Abstract

摘要： 针对用户的日常移动轨迹进行挖掘，可以有效地发现隐藏在用户生活中频繁出现的移动规律，即用户频繁移动模式,提出了一种基于PrefixSpan算法的用户频繁移动模式并行挖掘算法PASFORM.该算法利用了新的剪枝策略，缩小了搜索空间;引入了时间约束，挖掘出的频繁移动模式带有时间属性；使用前缀树存储频繁移动模式，缩小了存储空间；采用了并行化方法，适用于海量时空数据的挖掘.实验结果表明，该方法能够快速有效地挖掘出用户频繁移动模式.

关键词: 频繁移动模式挖掘, 序列模式挖掘, 前缀树, 并行化

Abstract: Through daily moving trajectories, one can effectively find the frequent moving rules, i.e., user frequent moving patterns. Based on PrefixSpan algorithm, a parallel algorithm named PASFORM is presented for mining user frequent moving patterns. PASFORM uses a new pruning strategy to reduce the search space and several time constraints to make mining results time-tagged. It also employs the parallel method to mine mass data and a prefix tree to save the store space. Experimental results show that PASFORM is effective and efficient.

Key words: frequent moving pattern mining, sequential pattern mining, prefix tree, parallelization

中图分类号:

TP391

朱一波，鲍培明，吉根林. 一种用户频繁移动模式并行挖掘算法[J]. 中国科学技术大学学报, 2018, 48(1): 57-64.

ZHU Yibo, BAO Peiming, JI Genling. A parallel algorithm for mining user frequent moving patterns[J]. Journal of University of Science and Technology of China, 2018, 48(1): 57-64.

参考文献

［1］
PENG W C, CHEN M S. Developing data allocation schemes by incremental mining of user moving patterns in a mobile computing system[J]. IEEE Transactions on Knowledge & Data Engineering, 2003, 15(1):70-85.
[2] 陈勐, 刘洋, 王月,等. 基于时序特征的移动模式挖掘[J]. 中国科学信息科学, 2016, 46(9): 1288-1297.
[3] 李雄, 马修军, 王晨星,等. 城市居民时空行为序列模式挖掘方法[J]. 地理与地理信息科学, 2009, 25(2): 10-14.
[4] LI Z H, DING B L, HAN J W, et al. Mining periodic behaviors for moving objects[C]// Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington: ACM Press, 2010: 1099-1108.
[5] YAVA��塁 G, KATSAROS D, ULUSOY , et al. A data mining approach for location prediction in mobile environments [J]. Data & Knowledge Engineering, 2005, 54(2): 121-146.
[6] LI Z H, HAN J W, JI M, et al. MoveMine: Mining moving object data for discovery of animal movement patterns[J]. ACM Transactions on Intelligent Systems & Technology, 2011, 2(4): No. 37(1-32).
[7] HUNG C C, PENG W C, LEE W C. Clustering and aggregating clues of trajectories for mining trajectory patterns and routes[J]. The VLDB Journal, 2015, 24(2):169-192.
[8] LEE J G, HAN J W, LI X L. A unifying framework of mining trajectory patterns of various temporal tightness[J]. Knowledge & Data Engineering IEEE Transactions on, 2015, 27(6):1478-1490.
[9] 王亮, 汪梅, 郭鑫颖,等. 面向移动时空轨迹数据的频繁闭合模式挖掘[J]. 西安科技大学学报, 2016, 36(4): 573-576.
[10] HUANG Q Y, LI Z L, LI J, et al. Mining frequent trajectory patterns from online footprints[C]// Proceedings of the ACM SIGSPATIAL International Workshop on Geostreaming. Burlinggame, USA: ACM Press, 2016: No. 10(1-7).
[11] LEE J W, PAEK O H, RYU K H. Temporal moving pattern mining for location-based service[J]. Journal of Systems & Software, 2004, 73(3):481-490.
[12] Qiu M, Pi D. Mining Frequent Trajectory Patterns in Road Network Based on Similar Trajectory[M]// Intelligent Data Engineering and Automated Learning: IDEAL 2016, Springer International Publishing, 2016.
[13] 刘素杰. 时间标识的移动对象频繁模式发现[D]. 徐州：中国矿业大学, 2014.

[14] AGRAWAL R, SRIKANT R. Mining sequential patterns[C]// Proceedings of the 7th International Conference on Data Engineering. Taipei, China: IEEE Press, 1995:3-14.
[15] 王虎, 丁世飞. 序列模式挖掘研究与发展[J]. 计算机科学, 2009, 36(12): 14-17.
[16] RAO V C S, SAMMULAL P. Survey on sequential pattern mining algorithms[J]. International Journal of Computer Applications, 2013, 76(12): 24-31.
[17] SRIKANT R, AGRAWAL R. Mining sequential patterns: Generalizations and performance improvements[C]// Proceedings of the 5th International Conference on Extending Database Technology. London: Springer, 1996: 3-17.
[18] HAN J W, PEI J, MORTAZAVI-ASL B, et al. FreeSpan: Frequent pattern-projected sequential pattern mining[C]// Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Boston: ACM Press, 2000: 355-359.
[19] PEI J, HAN J W, MORTAZAVI-ASL B, et al. PrefixSpan: Mining sequential patterns efficiently by prefix-projected pattern growth[C]// Proceedings of the 17th International Conference on Data Engineering. Heidelberg, Germany: IEEE Press, 2001: 215-224.
[20] LIU J, YAN S, REN J. The design of frequent sequence tree in incremental mining of sequential patterns[C]// Proceedings of the 2nd International Conference on Software Engineering and Service Science. Beijing: IEEE Press, 2011: 679-682.
[21] Reality Commoms[EB/OL]. [2017-05-06]http://realitycommons.media.mit.edu/realitymining.html.
[22] System Data[EB/OL]. [2017-05-06]https://www.citibikenyc.com/system-data.

()
(

[1]	占永昆, 杨文飞, 张天柱. 基于关系建模的弱监督时序动作定位[J]. 中国科学技术大学学报, 2021, 51(10): 753-765.
[2]	梁启鹏, 朱巧慧, 康宇, 赵云波. 基于估计的无线网络化控制系统逼近控制策略[J]. 中国科学技术大学学报, 2021, 51(4): 327-334.
[3]	李慧聪, 傅孝明∗ . 基于局部等距嵌入的各向异性曲面网格生成[J]. 中国科学技术大学学报, 2020, 50(12): 1460-1471.
[4]	于俊，李雅洁，程礼磊，连顺，谭昶，丁德成，刘淇. 高教程序代码作业抄袭检测的方法研究与实践[J]. 中国科学技术大学学报, 2020, 50(8): 1048-1057.
[5]	张文静，班志杰. 基于全局的引文网络影响力最大化算法[J]. 中国科学技术大学学报, 2020, 50(8): 1058-1063.
[6]	任敏，许玲，王峰，吴超. 基于知识推荐的校园百科平台研究[J]. 中国科学技术大学学报, 2020, 50(8): 1072-1076.
[7]	孙磊，张义宁，薛艳芳，乔立山，张丽梅. 自适应功能连接网络学习及其在脑疾病识别中的应用[J]. 中国科学技术大学学报, 2020, 50(8): 1102-1109.
[8]	白江波，杨阳，张文生. 基于改进CycleGAN的合成孔径雷达图像仿真[J]. 中国科学技术大学学报, 2020, 50(8): 1181-1186.
[9]	辛守宇，郑蕊蕊，周瑜，刘文鹏，贺建军. 训练过程中使用支持集信息的单样本学习算法[J]. 中国科学技术大学学报, 2020, 50(8): 1187-1192.
[10]	汪志华，康红梅. 使用三角网格上的样条求解带有非齐次边界的PDE[J]. 中国科学技术大学学报, 2020, 50(7): 901-905.
[11]	龚乐君，周佘海，程逸飞，高志宏，李华康. 单细胞RNA序列数据的PBMC相关细胞的识别[J]. 中国科学技术大学学报, 2020, 50(7): 1013-1018.
[12]	杜淑颖，杜鹏，丁世飞. 基于CNN的假冒域名识别方法研究[J]. 中国科学技术大学学报, 2020, 50(7): 1019-1025.
[13]	李永军，曹为华，凌强. 基于特征点轨迹的多目标跟踪算法[J]. 中国科学技术大学学报, 2020, 50(6): 726-732.
[14]	江琦，刘建宏，关勇，白浩波，刘刚，田扬超. 一种针对不完善数据的基于全变分约束的相干衍射算法[J]. 中国科学技术大学学报, 2020, 50(4): 418-427.
[15]	王旭辉，燕明叶，吴梦. 适用于等几何分析退化光滑插值曲面片构造[J]. 中国科学技术大学学报, 2020, 50(3): 335-342.

一种用户频繁移动模式并行挖掘算法

A parallel algorithm for mining user frequent moving patterns

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价