本文是一篇软件工程论文，本论文提出一种新的伴随模式——松散跟踪伴随模式并设计相应的挖掘算法。同时，提出了一种基于分治思想的高效convoy伴随模式挖掘算法。
第一章绪论
1.1研究背景与内容
随着位置获取技术以及移动计算技术的发展，我们可以很容易地获得大量来自于人、车辆、船只、动物等移动对象的轨迹数据，这些数据代表了各种移动物体的移动性。在过去的几十年中，人们已经提出了非常多的数据挖掘技术来管理、分析和挖掘这些轨迹数据中蕴含的规律信息从而获得可用的知识。这些知识可以被广泛使用在各种应用和服务，包括动物行为研究[1]、城市规划[2]、社交推荐[3]以及位置感知广告[4]等方面。轨迹数据挖掘的任务包括轨迹模式挖掘、轨迹不确定性、轨迹分类以及轨迹异常检测等。
轨迹模式挖掘旨在从轨迹数据中发现一个规律性的移动模式，其中四种主要的模式分别为伴随模式、轨迹聚类、频繁序列模式和周期模式[5]。轨迹的不确定性指的是连续移动的对象的位置采样点是离散的，这就造成了每两个相邻的采样点之间的位置的不确定性。一方面，为了提高轨迹数据的实用性，人们通过大量的研究来构建模型从而减少轨迹的不确定性。另一方面，在某些情况下需要通过增加轨迹的不确定性从而达到保护用户位置隐私的目的。轨迹分类指的是通过监督学习的方法来区分不同状态的轨迹数据，如步行的轨迹和驾车的轨迹。轨迹异常检测用来从轨迹数据中发现与其他轨迹在某些度量方面明显不同的对象或者是不符合预期运动模式的对象。
近年来，时空轨迹的伴随模式[5-7]挖掘成为轨迹模式挖掘中的研究热点之一。轨迹伴随模式旨在从给定轨迹数据中发现在一段时间内一起移动的对象。该模式应用场景非常多，如在动物行为研究过程中，我们可以研究一起移动的动物从而发现某一物种的迁徙习惯。又比如在军事监视中，战场的传感器网络通过军事卫星一直监视着潜在入侵者们的移动[8]。识别具有一致轨迹模式的车辆有助于城市建设的车辆吞吐量规划和道路设计规划。发现通勤者之间的共同上班路线可以用于集体运输的调度。识别同时遵循相同路线的车辆可以用于组织拼车来减少车流量从而达到减少道路拥堵、空气污染以及二氧化碳排放的目的。
..................
1.2课题研究现状
从大规模的轨迹数据中挖掘伴随模式是一项重要的任务并且具有广泛的应用前景。近年来，已经有大量的文献对时空轨迹伴随模式的挖掘进行了研究。
在2002年时，Laube等人[9]提出了flock模式的概念。flock模式指的是一组至少包含m个对象的群体在一个半径为r的圆形区域内一起移动至少k个连续时间戳。之后，Gudmundsson等人利用包括近似算法的计算几何技术改进了flock模式挖掘的算法[10]并在这之后进一步研究了最长持续时间的flock[11]。但是flock的挖掘与轨迹数据的分布有关，所以该模式对用户预定义的圆形区域大小非常敏感，这就会造成所谓的lossy-flock问题。
在2008年时，Jeung等人[12,13]提出的convoy模式很好地解决了这个问题。他们采用了基于密度的聚类方法挖掘convoy模式，避免了对移动对象群组的大小和形状的严格限制。第二年，Yoon等人[14]发现Jeung等人提出的convoy模式存在严重的准确性问题，因此他们提出了一种有效convoy模式挖掘算法。他们首先通过PCCD算法挖掘出所有可能的部分相连convoy，然后采用DCVal算法获得满足所有条件的有效convoy集合。然而，flock和convoy都要求移动对象一起移动连续k个时间戳，这种严格的连续时间限制在现实世界中可能并不实际。2010年，Li等人[15]提出的swarm模式是一种更为通用的伴随模式。该模式旨在挖掘至少在k个（可以不连续的）时间戳内一起移动的对象簇。
2012年Tang等人[16]提出了traveling companion模式。他们利用一种叫做traveling buddy的数据结构来存储对象之间的关系而不是存储空间坐标，因此可以动态地从轨迹数据流中发现一起移动的群组。该模式可以看做是convoy和swarm模式的在线和增量的检测方式[5]。之后，Zheng[17,18]等人提出了gathering模式，该模式的目的是从轨迹数据中发现如庆祝活动、游行和交通堵塞等事件。与之前的提到的模式不同的是，gathering中某些个体对象会频繁地加入和离开群组。这个过程中群组的形状和位置不会改变得特别快，因为对于整个群组来说个体对象的移动性很低。
..........................
第二章相关工作
2.1空间索引技术
本节主要对常用的几种空间索引技术作简要的介绍，包括网格索引、四叉树索引、R树索引以及Geohash。
2.1.1四叉树索引
四叉树是一种树形索引结构，最早由Finkel等人[24]提出。如图2.1所示，四叉树通过将整个空间递归地四分，使得每个节点包含其四个叶子节点所对应的区域数据。四叉树可以按照它们所代表的数据类型如区域、点、线和曲线进行分类，也可以根据树的形状是否与数据处理的顺序无关进行分类。常见的四叉树类型有点四叉树[24]（Point Quadtree）、点-区域四叉树[25,26]（Point-region Quadtree）、边四叉树[27]（Edge Quadtree）以及多边形映射四叉树（Polygonal-map Quadtree）[28,29]等。
软件工程论文参考
........................
2.2时空轨迹数据挖掘
本节主要对时空轨迹数据挖掘的方向做简要的介绍，包括包括轨迹模式挖掘、轨迹不确定性、轨迹分类以及轨迹异常检测。
2.2.1轨迹模式挖掘
轨迹模式挖掘旨在从轨迹数据中发现一个规律性的移动模式，其中主要的模式有伴随模式、轨迹聚类和频繁序列模式等。伴随模式旨在从给定轨迹数据中发现在一段时间内一起移动的对象，现有的主要伴随模式有flock模式、convoy模式、swarm模式以及gathering模式等，具体介绍我们在2.3节中给出。
轨迹聚类旨在找到被不同移动对象所共享的代表性轨迹或共同的移动趋势。该模式已经在许多不同的应用中得到了研究，如空间数据库、数据挖掘、交通运输以及可视化等。轨迹聚类可以大致分为两类：基于划分的轨迹聚类[40-43]和基于密度的轨迹聚类[44-47]。给定一组轨迹对象，基于划分的该轨迹聚类讲这些对象划分成k个簇集。其中，相似性度量以及参数k是根据用例事先选好的。基于密度的轨迹聚类首先找到密集的分段，然后将这些分段连接起来生成代表性轨迹。这两种轨迹聚类都需要进行大量的相似性计算，唯一的区别在于是使用整个轨迹计算还是使用子轨迹计算。
频繁序列模式指的是在移动对象在相似的时间间隔内沿着共同的位置序列移动，研究者们提出了多种方法以挖掘该模式。基于线简化的方法[48]主要通过如Douglas-Peucker[49]算法的线简化算法来确定形成轨迹的关键点。基于聚类的方法[50]通过聚类的方式使每个轨迹的坐标点标记为改坐标点所在簇集的id从而将一条轨迹转换为簇集的id序列。基于后缀树的方法[51,52]首先使用地图匹配算法将轨迹映射到路网中从而用路段id序列的字符串来表示一条轨迹，然后利用后缀树存储字符串从而快速挖掘频繁序列模式。
............................
第三章松散跟踪伴随模式挖掘...................................14
3.1问题描述与预备知识....................................14
3.1.1问题描述........................................................14
3.1.2前缀树...................................15
第四章高效的convoy伴随模式挖掘算法........................................23
4.1问题描述..........................................23
4.2高效的convoy伴随模式挖掘算法.............................25
第五章原型系统的设计与实现...................................38
5.1需求分析.........................................38
5.2系统设计.......................................39
第五章原型系统的设计与实现
5.1需求分析
本章所实现的原型系统能够提供轨迹数据的预处理，挖掘以及可视化功能。其中，轨迹数据的预处理是利用Geohash算法将用户上传的轨迹的二维经纬度坐标点编码成一维字符串。轨迹数据挖掘即用第三章与第四章所提方法实现高效的松散跟踪伴随模式以及convoy伴随模式的挖掘。轨迹数据的可视化是系统能够将挖掘出的结果轨迹展现在地图页面中。该原型系统的设计目标如下：
（1）高效性：对于用户上传的轨迹数据，该系统能够实现高效的松散跟踪伴随模式和convoy伴随模式的挖掘。
（2）有效性：在高效挖掘伴随模式的同时，该系统能够保证挖掘结果的正确性，即挖掘出所有满足定义的结果。
（3）可视化：为了使结果的展示更加直观，该系统通过将轨迹结果集渲染在地图页面中从而实现可视化效果。
系统的功能设计流程图如图5.1所示。首先对用户上传的轨迹数据进行预处理，将所有轨迹的每个坐标点用Geohash算法编码成Geohash字符串。接着根据用户不同的请求做相应的操作：
①若用户想要挖掘松散跟踪伴随模式，则先构建基于Geohash的前缀树索引，然后根据用户选定的查询轨迹，执行LTBD+算法从轨迹数据中找到查询轨迹的跟踪者。最后，系统将挖掘出的跟踪者集合渲染在可视化地图中。
②若用户想要挖掘convoy伴随模式，则先利用基于块的划分模型（BP-Model）生成最大相连非空块区域（MOBAs），然后执行ECMA算法依次对每个最大相连非空块区域处理挖掘出convoy结果集；最后，系统将挖掘出的convoy集合渲染在可视化地图中。
软件工程论文怎么写
.............................
第六章总结与展望
6.1论文总结
大数据时代下，位置获取技术以及移动计算技术的发展使我们能够轻易地获得海量的轨迹数据。通过对这些来自于人、车辆、船只、动物等移动对象的轨迹数据进行分析与挖掘能够获得许多可用知识。近年来，时空轨迹伴随模式挖掘是研究热点之一。该模式旨在从给定轨迹数据中发现在一段时间内一起移动的对象，可用于动物迁徙行为分析以及交通堵塞和流量分析等方面。目前的时空轨迹伴随模式挖掘的大部分相关文献都只是关注轨迹对象的群体行为，无法用于需要挖掘给定查询轨迹的跟踪者这个应用场景，而仅有的相关工作因为所提出的跟踪行为的定义在时间连续性上过于严格，因此在真实世界环境下可能并不实际。另一方面，目前对于经典的convoy伴随模式的挖掘所提出的方法因为聚类过于耗时，因而导致挖掘效率低下。针对以上问题，本论文提出一种新的伴随模式——松散跟踪伴随模式并设计相应的挖掘算法。同时，提出了一种基于分治思想的高效convoy伴随模式挖掘算法。本文的主要贡献有：
（1）介绍了轨迹伴随模式的应用场景并重点论述了目前国内外研究者在轨迹伴随模式挖掘方面的相关工作。对现有工作中提到的伴随模式及其相应的挖掘方法在模型定义及挖掘效率两个方面进行了对比与分析。
（2）提出了一种松散跟踪伴随模式用于从轨迹数据中发现给定查询轨迹的潜在跟踪者，并且设计了两个算法LTBD和LTBD+来解决问题。其中，LTBD是按照问题定义的一种直截了当的基础算法，LTBD+则是其改进算法。LTBD+利用基于Geohash的前缀树索引，在保证准确率的情况下提高了挖掘效率。
参考文献（略）