云计算环境下时空轨迹聚集模式挖掘算法研究

发布时间：2017-07-08 14:18

  本文关键词：云计算环境下时空轨迹聚集模式挖掘算法研究

  更多相关文章： 聚集模式 时空数据挖掘 轨迹模式挖掘 并行数据挖掘

【摘要】：随着位置采集技术,包括遥测技术、车载GPS、无线网络以及智能手机的应用,人们可以记录任何移动对象的行走轨迹,从而形成了以轨迹作为表现形式的庞大时空数据库。分析各种不同移动对象的时空轨迹数据,有助于我们对人类行为模式、交通物流、动物习性以及市场营销等进行研究。时空轨迹模式挖掘是数据挖掘的重要研究内容。时空轨迹聚集模式是时空轨迹模式重要的组成部分,它是指一组时空移动对象在一定时间内一起移动形成的行为模式。对时空轨迹数据进行挖掘,可提取出有意义的聚集模式,从而帮助人们监控和预测一些不寻常的群体事件。本文研究时空轨迹聚集模式挖掘算法,取得的主要研究成果如下：(1)提出了一种时空轨迹gathering聚集模式并行挖掘算法PDGP(Parallel algorithm for Discovering Gathering Pattern),并利用MapReduce并行编程模型加以实现。PDGP算法将gathering聚集模式挖掘算法中极其耗时的聚类操作分发到各个计算节点并行处理,以此达到提高算法运行效率的目的。实验结果表明PDGP算法的运行效率与原挖掘算法相比有较大提升,而且随着计算节点数量的增加,并行算法的加速比较高,在大数据集上显示出了明显的性能优势。(2)提出了一种基于网格索引的时空轨迹聚类算法GTRAJ-DBSCAN(Grid-based algorithm for TRAJectory-DBSCAN),在云环境下实现基于网格索引的时空轨迹并行聚类算法GPTRAJ-DBSCAN(Grid-based Parallel algorithm for TRAJectory-DBSCAN).实验结果表明本文提出的GTRAJ-DBSCAN和GPTRAJ-DBSCAN算法性能优于TRAJ-DBSCAN算法,这两个算法通过建立网格索引,在进行轨迹聚类时,利用网格索引实现对轨迹段的区域查询,从而降低了计算量,有效地提高了轨迹聚类的速度。(3)提出了一种基于中心距离的闭合聚集检测算法CDCC(algorithm based on Center-distance for Discovering Closed Crowds),该算法计算簇内所有移动对象位置均值从而获得该簇的聚类中心,通过计算各个簇聚类中心的距离从而获得各个簇之间的距离从而极大地减少了计算量。实验结果表明本文提出的CDCC算法相比较于DCC算法在保证结果精确性的同时,在时间效率方面有一定的提升。
【关键词】：聚集模式 时空数据挖掘 轨迹模式挖掘 并行数据挖掘
【学位授予单位】：南京师范大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP311.13
【目录】：

• 摘要4-5
• Abstract5-10
• 第1章 绪论10-16
• 1.1 研究背景及意义10-11
• 1.2 研究现状11-14
• 1.3 本文研究内容14-15
• 1.4 本人组织结构15-16
• 第2章 时空轨迹模式挖掘研究进展16-30
• 2.1 时空轨迹模式挖掘简介16-17
• 2.1.1 时空轨迹频繁模式16
• 2.1.2 时空轨迹伴随模式16-17
• 2.1.3 时空轨迹异常模式17
• 2.1.4 时空轨迹聚集模式17
• 2.2 时空轨迹聚集模式分类17-21
• 2.2.1 Group模式17
• 2.2.2 Flock模式17-18
• 2.2.3 Moving Cluster模式18-19
• 2.2.4 Convoy模式19
• 2.2.5 Evolving Convoy模式19-20
• 2.2.6 Swarm模式20
• 2.2.7 Gathering模式20-21
• 2.3 时空轨迹聚集模式挖掘方法21-25
• 2.3.1 基于近似查询的聚集模式挖掘算法22-23
• 2.3.2 基于关联规则剪枝的挖掘算法23
• 2.3.3 基于密度聚类的聚集模式挖掘算法23-25
• 2.4 时空轨迹Gathering聚集模式挖掘算法25-29
• 2.4.1 背景知识25-26
• 2.4.2 轨迹简化26-27
• 2.4.3 轨迹聚类27-28
• 2.4.4 聚集检测28-29
• 2.5 本章小结29-30
• 第3章 时空轨迹Gathering聚集模式并行挖掘算法30-41
• 3.1 并行编程模型30-33
• 3.1.1 Hadoop30-32
• 3.1.2 Spark32
• 3.1.3 GPU32-33
• 3.2 算法思想33
• 3.3 算法描述33-36
• 3.4 实验与结果分析36-40
• 3.4.1 实验环境36
• 3.4.2 实验数据源36
• 3.4.3 实验结果分析36-40
• 3.5 本章小结40-41
• 第4章 时空轨迹Gathering聚集模式挖掘算法的改进41-52
• 4.1 基于网格索引的时空轨迹并行聚类算法41-48
• 4.1.1 引言41-43
• 4.1.2 GPTRAJ-DBSCAN算法思想43-46
• 4.1.3 实验与结果分析46-48
• 4.2 基于中心距离的闭合聚集检测算法48-51
• 4.2.1 引言48-49
• 4.2.2 CDCC算法思想49-50
• 4.2.3 实验与结果分析50-51
• 4.3 本章小结51-52
• 第5章 总结与展望52-54
• 5.1 总结52-53
• 5.2 展望53-54
• 参考文献54-59
• 附录 攻读硕士学位期间发表论文情况59-60
• 致谢60

【相似文献】

中国期刊全文数据库 前10条

1 王宇新;田佳;郭禾;吴树朋;杨元生;;应用模糊方法的设计模式挖掘策略研究[J];计算机工程与应用;2010年02期

2 陆亿红;王子仁;黄燕;;适合稀少空间特征的同位模式挖掘算法[J];浙江工业大学学报;2007年04期

3 郭燕萍;辛伯宇;;高选票例外模式挖掘研究与实现[J];电脑开发与应用;2007年08期

4 徐显九;杨燕;岳爱萍;;高效的用户移动模式挖掘方法[J];计算机应用研究;2007年09期

5 李帆;夏士雄;张磊;;基于模糊理论的不确定轨迹模式挖掘[J];微电子学与计算机;2011年08期

6 李中元;边馥苓;;空间同位模式挖掘研究进展[J];地理空间信息;2013年06期

7 邢东山,沈钧毅,宋擒豹;用户浏览偏爱模式挖掘算法的研究[J];西安交通大学学报;2002年04期

8 刘洪辉;吴岳芬;;用户行为模式挖掘问题的研究[J];计算机技术与发展;2006年05期

9 付晓翠;许盈;车路;;游戏访问模式挖掘的研究与应用[J];郑州大学学报(理学版);2007年04期

10 颜一鸣;郭鑫;李仁发;;一种非确定树模式挖掘算法[J];计算机工程与应用;2011年15期

中国重要会议论文全文数据库 前10条

1 王肃;杜军平;高田;;基于本体与知识背景的模式挖掘框架研究[A];2009年中国智能自动化会议论文集（第二分册）[C];2009年

2 缪裕青;尹东;;分布式存储结构的频繁闭合模式挖掘并行算法[A];2007年全国开放式分布与并行计算机学术会议论文集(下册)[C];2007年

3 王淼;尚学群;谢华博;李战怀;;行常量差异共表达基因模式挖掘算法研究[A];第29届中国数据库学术会议论文集（B辑）（NDBC2012）[C];2012年

4 刘玉葆;蔡嘉荣;印鉴;黄志兰;;基于最大访问模式挖掘的数据库异常行为检测[A];第二十三届中国数据库学术会议论文集（研究报告篇）[C];2006年

5 陆叶;王丽珍;陈红梅;赵丽红;;基于可能世界的不确定空间co-location模式挖掘研究[A];NDBC2010第27届中国数据库学术会议论文集(B辑)[C];2010年

6 王丽珍;陆叶;陈红梅;肖清;;基于前缀树结构的空间co-location模式挖掘算法研究[A];NDBC2010第27届中国数据库学术会议论文集(B辑)[C];2010年

7 胡伟成;曹三省;李丹;;一种基于QPop增量时域分割升维的媒体内容应用模式挖掘改进算法[A];第二十二届中国数据库学术会议论文集（技术报告篇）[C];2005年

8 薛丹;李德敏;裴仁林;;移动计算中基于PrefixSpan算法的用户移动模式挖掘[A];第二十一届中国数据库学术会议论文集（技术报告篇）[C];2004年

9 宋国杰;马帅;唐世渭;杨冬青;;基于模式挖掘的交通预测模型[A];第十九届全国数据库学术会议论文集（技术报告篇）[C];2002年

10 夏庆;马元元;孙志挥;;路径遍历模式挖掘方法的改进[A];第十六届全国数据库学术会议论文集[C];1999年

中国重要报纸全文数据库 前1条

1 辛苑薇;谁将分享“大数据”的智慧盛宴？[N];21世纪经济报道;2012年

中国博士学位论文全文数据库 前7条

1 Shafqat Ali Shad;移动用户轨迹与行为模式挖掘方法研究[D];中国科学技术大学;2013年

2 钱烽;同位模式挖掘研究[D];浙江大学;2012年

3 刘勇;图模式挖掘技术的研究[D];哈尔滨工业大学;2010年

4 覃桂敏;复杂网络模式挖掘算法研究[D];西安电子科技大学;2012年

5 王乐;数据流模式挖掘算法及应用研究[D];大连理工大学;2013年

6 林耀进;多源环境中数据预处理与模式挖掘的研究[D];合肥工业大学;2014年

7 曾海泉;时间序列挖掘与相似性查找技术研究[D];复旦大学;2003年

中国硕士学位论文全文数据库 前10条

1 张子瀚;面向大数据的高效用模式挖掘方法研究[D];北方工业大学;2016年

2 张刚领;一种基于团的闭频繁Co-location模式挖掘方法[D];云南大学;2016年

3 江万国;基于领域驱动的空间高效用Co-location模式挖掘[D];云南大学;2016年

4 吴锡宇;基于约束的城市co-location模式挖掘[D];云南大学;2016年

5 冯鲁桥;基于C/C++代码库的API调用模式挖掘研究及实现[D];电子科技大学;2016年

6 王敏;云计算环境下时空轨迹聚集模式挖掘算法研究[D];南京师范大学;2016年

7 岳爱萍;基于时间的用户移动模式挖掘研究[D];西南交通大学;2008年

8 卢荣;基于动态扭曲算法的时间序列部分周期模式挖掘研究[D];天津大学;2009年

9 胡德勇;基于电信数据的模式挖掘与分析[D];北京邮电大学;2010年

10 甘海燕;基于动态链表结构的时间序列异步周期模式挖掘研究[D];天津大学;2010年

，

本文编号：534926