论文部分内容阅读
随着卫星定位技术、无线通信以及跟踪检测设备的快速发展,人们能够方便地以低廉的代价获得海量时空轨迹数据。移动对象的位置、属性都可能随着时间的推移而发生变化,人们不仅需要知道某一对象的属性和空间信息,更想要了解与该对象相关事件的来龙去脉,以便对其形成原因作出评估,对未来情况进行预测。时空轨迹数据恰能有效地表达移动对象的这些特性。通过分析各种不同对象的时空轨迹数据,有助于对人类行为模式、交通物流、动物习性以及市场营销等进行研究。时空轨迹模式挖掘作为数据挖掘的重要内容吸引了众多研究者投身其中。时空轨迹伴随模式是时空数据轨迹模式中重要的组成部分,在挖掘具有相同或相似运动模式的移动对象群体以及研究该移动对象群体中各移动对象之间的亲近度等方面有着广泛的应用。本文研究时空轨迹伴随模式挖掘算法,取得的主要研究成果如下：(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算法的加速比较高,在大数据集上显示出了更大的优势。