云计算环境下时空轨迹伴随模式挖掘研究

发布时间：2018-04-18 20:21

本文选题：伴随模式 + 时空轨迹挖掘　；参考：《南京师范大学》2015年硕士论文

【摘要】：随着卫星定位技术、无线通信以及跟踪检测设备的快速发展,人们能够方便地以低廉的代价获得海量时空轨迹数据。移动对象的位置、属性都可能随着时间的推移而发生变化,人们不仅需要知道某一对象的属性和空间信息,更想要了解与该对象相关事件的来龙去脉,以便对其形成原因作出评估,对未来情况进行预测。时空轨迹数据恰能有效地表达移动对象的这些特性。通过分析各种不同对象的时空轨迹数据,有助于对人类行为模式、交通物流、动物习性以及市场营销等进行研究。时空轨迹模式挖掘作为数据挖掘的重要内容吸引了众多研究者投身其中。时空轨迹伴随模式是时空数据轨迹模式中重要的组成部分,在挖掘具有相同或相似运动模式的移动对象群体以及研究该移动对象群体中各移动对象之间的亲近度等方面有着广泛的应用。本文研究时空轨迹伴随模式挖掘算法,取得的主要研究成果如下：(1)提出了一种基于网格索引的时空轨迹伴随模式挖掘算法MAP-G(Mining Adjoint Pattern of spatial-temporal trajectory based on the Grid index)。利用网格索引不仅可以提高算法搜索候选伴随对象集合的速度,而且可以简化轨迹数据,降低计算量,提高算法的执行效率。实验结果表明该算法不仅比利用DBSCAN算法搜索候选伴随对象集合的伴随模式挖掘算法时间效率更高,并且由于MAP-G算法排除了部分不准确的轨迹模式,因此该算法的结果也相对更加准确。(2)提出了一种基于伴随模式挖掘算法CMC的时空轨迹伴随模式并行挖掘算法P-CMC(Parallel algorithm based on algorithm CMC)。利用Map/Reduce并行编程模型加以实现。将CMC算法中极其耗时的聚类操作分布到各个计算节点并行处理,以此达到提高算法时间效率的目的。实验表明P-CMC算法的执行效率与CMC算法相比有较大提升,而且随着计算节点数量的增加,P-CMC算法的加速比较高,在大数据集上显示出了更大的优势。
[Abstract]:With the rapid development of satellite positioning technology, wireless communication and tracking and detection equipment, people can easily obtain a large amount of space-time trajectory data at a low cost.Moving an object's position and properties can change over time. People need not only to know the properties and spatial information of an object, but also to understand the context of the events associated with that object.In order to evaluate the reasons for its formation and predict the future situation.The spatiotemporal trajectory data can effectively express these characteristics of moving objects.It is helpful to study human behavior patterns, transportation logistics, animal habits and marketing by analyzing the spatiotemporal trajectory data of different objects.As an important part of data mining, spatiotemporal trajectory pattern mining attracts many researchers.Space-time trajectory adjoint pattern is an important component of spatio-temporal data locus pattern.It is widely used in mining moving object groups with the same or similar motion patterns and studying the closeness of moving objects in the moving object groups.In this paper, we study the adjoint pattern mining algorithm of spatio-temporal locus. The main research results are as follows: 1) A spatio-temporal Adjoint Pattern of spatial-temporal trajectory based on the Grid index algorithm based on grid index is proposed.Using grid index can not only improve the speed of searching candidate adjoint object set, but also simplify the track data, reduce the computational cost and improve the efficiency of the algorithm.Experimental results show that the proposed algorithm is not only more efficient than the adjoint pattern mining algorithm using DBSCAN algorithm to search candidate adjoint object sets, but also eliminates some inaccurate trajectory patterns by MAP-G algorithm.Therefore, the result of this algorithm is more accurate. (2) A parallel algorithm P-CMC(Parallel algorithm based on algorithm CMCs based on adjoint pattern mining algorithm (CMC) is proposed.The parallel programming model of Map/Reduce is used to realize it.The extremely time-consuming clustering operations in the CMC algorithm are distributed to each computing node to process in parallel in order to improve the time efficiency of the algorithm.Experiments show that the execution efficiency of P-CMC algorithm is much higher than that of CMC algorithm, and with the increase of the number of nodes, the speedup of P-CMC algorithm is higher, which shows more advantages on big data set.
【学位授予单位】：南京师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP311.13

【参考文献】