第一章 绪论
1.1 研究背景及意义
随着现如今通信技术的成熟和车辆的普及，为了加强道路运输的车辆监督管理，交通运输部门要求车辆使用具有行驶记录功能的 GPS 或北斗定位装置[1]。大量的车辆运动轨迹点信息是可以通过 GPS 终端实时采集而得到的。随着时间的增长，收集的车辆轨迹数据的量越来越大，达到了 TB 甚至 PB 级别的数据量。这些数据中包含着大量未发掘的有价值的信息，可以通过对这些信息的挖掘，找出车辆行驶、异常[2]、拥堵和热区分布[3][4]等规律性时空知识，并将这些信息运用到交通安全控制、车流量管控等实际应用领域。利用这样的关系不但可以预测车辆的行驶轨迹、发现司机的驾驶习惯、监控道路的拥堵情况，也可以将新增数据用于实时交通状况的预报等各种智能交通应用场景。
轨迹聚类分析是发现车辆轨迹共同行为模式最直观、最有价值的一类方法。现有大部分轨迹聚类分析的研究大多是依据轨迹的形状特征和时空特征展开，很少关注轨迹速度、方向等运动学特征，更缺乏对多类轨迹特征的融合分析，这样可能造成度量的轨迹间相似度精确不高，不能全面体现轨迹间的实际相似情况。此外，在轨迹聚类分析的算法选择方面，虽然适用于轨迹或轨迹点数据本身的聚类算法种类繁多，但是在实际应用中，不同的聚类算法得出的聚类结果在效果、精度和效率都存在明显差异，所以对面向轨迹数据的聚类算法的选择对于轨迹聚类分析是否有效起着决定意义的作用，特别是聚类算法中轨迹相似度的定义和度量方法是聚类准确度的直接决定因素。
在轨迹数据的聚类分析效率方面，现有研究大多针对已经收集好的历史轨迹数据进行分析。然而，轨迹数据是实时更新的，并且呈现指数级爆炸增加的趋势，这对轨迹聚类算法的效率提出了更高的要求。一方面大规模轨迹数据的聚类分析已经很难在单机系统完成，需要对聚类过程进行分布并行处理。虽然已有很多研究关注了并行聚类方法的研究，但分布式聚类过程在提高算法数据处理规模和效率的同时，也势必带来了聚类结果在全局精度方面的损失。另一方面，轨迹数据作为一种实时更新的实体，每次的少量数据更新都需要全部轨迹数据的重新聚类，严重影响了轨迹聚类的分析结果对于时延敏感型智能交通的应用，研究有效的轨迹增量聚类方法也是亟待解决的问题。
图 3. 3 EDR 的操作
1.2 研究内容
本文以轨迹数据聚类为主要研究内容，希望通过聚类操作准确发现具有不同特征的轨迹簇集，以支持基于此分析结果的更深入研究，例如预测轨迹异常、交通安全预警等现实场景。下面给出本文各部分的研究内容及主要技术路线。
总体而言，本文的研究内容包括四个方面：轨迹特征选择，轨迹聚类算法、轨迹聚类的并行化及增量化模型与实现。在轨迹数据的特征选择方面，通过对轨迹经纬度、速度、角度等多维度特征的提取和融合，将轨迹数据的时空和运动特征体现的更加完整，同时使用这些特征作为轨迹关键点的筛选标准，从而可以在尽量不丢失轨迹信息的前提下，将轨迹数据进行精简，以便加快后续轨迹数据聚类分析的速度。在轨迹数据的聚类分析方面，利用离散Fréchet 距离度量具有多种特征的轨迹间的相似程度，并选择了高效的 K-Means 算法作为轨迹聚类的主要实现方法，提出了支持多特征的轨迹聚类算法 FK-Means。通过模拟生成符合现实情况的多种类型的轨迹数据集，验证了 FK-Means 算法的聚类效果。在大规模轨迹数据的高效聚类方面，分别研究了面向大量历史轨迹的离线并行聚类算法和面向少量增量轨迹的在线增量聚类算法。首先，在轨迹并行聚类研究方面，将 MapReduce 框架与 FK-Means 聚类算法结合，使用 LOF 算法优化聚类结果，提高轨迹聚类的处理效率和精度；其次，在轨迹增量聚类研究方面，将聚类过程分为两个阶段，第一阶段先对新增数据使用 FK-Means 算法进行聚类，得出新增数据的聚类结果，然后在第二阶段将新增数据的聚类结果和历史数据的聚类结果进行整合，这一阶段中由于新增数据的数量级比历史数据的数量级小很多，为了加快搜索的速度，所以在对聚类结果的遍历过程中加入了 DBFS 算法，在聚类结果整合中，为了保证聚类结果的准确度，引入了 Chameleon 算法对最终得出的聚类结果重新整合，使得局部聚类的效果尽可能接近全局聚类的效果。
.............................
第二章 相关研究工作
2.1 轨迹相似度度量
在轨迹相似度度量研究方面，现有工作中最常采用的方法是根据不同轨迹间地理位置距离的相近程度判断他们是否相似。例如，文献[5]将了欧几里得距离与轨迹经纬度相结合计算轨迹间的相似度，通过计算两条轨迹中对应点之间经纬度的欧式距离的均值或其他统计特征值来表征轨迹间的相似度。这种方法在面对大量高纬度轨迹数据的时候，效率会明显的降低。为了提高轨迹相似度度量的处理速度，Chan 等人将离散小波技术和距离计算方式相结合，实现了对轨迹数据的降维处理[6][7]。但是由于每个轨迹集实际采样的情况是不尽相同的，例如采样频率不同，传感器错误导致的采样缺失等，上述方法是没有办法在这种情况下准确地找到两条轨迹中的对应轨迹点的。针对该问题，文献[8]将整条轨迹数据划分为多个轨迹段，再通过欧几里得公式计算轨迹段之间的距离，当两条轨迹采样率不同时，会单独进行比较和处理。文献[9]提出了一种快速匹配相似性查询的方法，该方法利用最长公共子序列 LCS 算法对轨迹间相似度进行度量，通过计算最长公共子序列数，选出数值高于指定阈值的轨迹序列，将这样的一对轨迹序列定义为相似序列。由于该方法不需要比较所有的轨迹点，所以即使轨迹集中含有大量的噪声点也不会太影响相似度的计算结果。面对不同的采样情况，文献[10]则提出通过对时空轨迹特征的分析，利用轨迹所在路径和速度曲线定义新的轨迹，使轨迹符合动态时间封装算法（DTW）的条件，并使用 DTW 算法来计算轨迹间相似度，即根据时间时序对轨迹数据进行局部缩放，解决轨迹数据由于采样频率不同或缺失轨迹点导致的模板匹配问题，使得求出的轨迹相似度更加合理。不过 DTW 算法要求轨迹点之间具有时间连续性，因此，算法没有办法在小部分区间内识别轨迹完全不相似的情况。
上述的方法对轨迹相似度的度量大多仅依赖轨迹的经纬度属性，然而轨迹作为一种复杂的时空数据，还具有速度、方向、路网约束等多种特征。融合轨迹的多种不同特征分析轨迹间的相似度，能更加准确地反映移动对象的运动特征。文献[11]是通过时间和空间两个角度对轨迹数据进行过滤，增加后续对轨迹相似度计算的精度。但是由于该算法模型中对轨迹的定义并不清晰，较少考虑路网的情况，所以面对不同类型的路网时，其相似度度量的准确度会受到一定影响。仅仅对轨迹数据进行过滤，而不对轨迹相似性度量的概念重新定义，对轨迹相似度度量精度改进有限。为此，文献[12]从时空维度给出了一种基于单位时间平均值Hausdorff 距离的轨迹相似性度量方法，该方法有效提高了轨迹数据聚类结果的质量。、
.........................
2.2 聚类算法
轨迹数据聚类是轨迹分析的重要方面，是将具有不同时间和空间相似度特征的时空对象划分为多个类或簇，使同一类内的对象相似性程度高，而不同类之间数据的相异程度高[19]。针对轨迹聚类分析已有不少研究成果。吴笛等人[20]对南海旋涡轨迹进行时空聚类分析，在空间聚类的基础上提出轨迹线段时间距离的度量方法和阈值确定原则，验证了基于密度的轨迹时空聚类方法的有效性。文献[21]使用改进后的 TRACLUS 算法对划分后的轨迹数据进行聚类分析，以此来推测轨迹的运动趋势。文献[22]在 TRACLUS 算法的基础上加入了方向、速度等语义时空信息，提出了一种新的轨迹聚类算法，实验证明该算法有效提高了聚类精度。但由于 TRACLUS 算法受输入参数和噪声数据影响较大。为了解决这个问题，文[23]提出了一种基于密度峰值的轨迹聚类算法（TCDP），实验结果表明 TCDP 算法具有更好的轨迹聚类效果。为了解决轨迹过长导致的聚类困难问题，文献[24]提出一种新的轨迹聚类算法 iBTC，算法将 Dijkstra 算法和独立森林的思想相结合，求出轨迹的最佳分段并整合，并使用细分-合并过程对轨迹数据进行聚类。文献[25]提出一种以轨迹子段为聚类目标的聚类算法 CTIHD，实验结果表明该算法相比同类算法具有更好的轨迹聚类效果。考虑到轨迹聚类研究在智能交通场景中的应用，廖律超等提出了一种基于路网下的轨迹潜在语义关联的谱聚类方法[26]，实现了轨迹空间向量的建模，可快速提取轨迹的关键特征信息，通过降维划分语义子空间，实验结果表明潜在的语义相关性对轨迹进行快速谱聚类具有一定的处理优势。夏英等人在对交通系统进行进一步研究的时候，创新性的引用了流量、拥堵状态等数据，并且根据具体应用过程中的实际情况对每一个所使用的属性在时间和空间上进行分析，研究各个变量之间的相关性，通过研究表明，这种创新性的算法是能够提高准确性并且使效率大大提高的[27]。
图 3. 1 DTW 的操作
第三章 轨迹聚类方法...........................................10
3.1 相关理论基础..........................................................10
3.1.1 轨迹相似性度量算法..........................................10
3.1.2 聚类算法................................................12
第四章 轨迹并行聚类.......................................28
4.1 相关理论基础.....................................................28
4.1.1 Hadoop 介绍................................................28
4.1.2 MapReduce 分布式框架介绍......................................28
第五章 轨迹增量聚类....................................................43
5.1 相关理论基础......................................................43
5.1.1 变色龙算法......................................................43
5.1.2 双向广度优先搜索算法..............................44
第五章 轨迹增量聚类
5.1 相关理论基础
在面对新增数据聚类结果与历史数据聚类结果融合的问题上， 变色龙（Chameleon）算法比第四章使用的 LOF 算法更合适。Chameleon 算法的执行需要对聚类集中全部的类进行搜索，而 LOF 算法只对局部类簇进行搜索，由于新增数据与历史数据的类属关系不明确，如果采用局部搜索的方法会降低聚类结果精度。
5.1.1 变色龙算法
Chameleon 算法涉两个环节：结合 hMetic 算法获取相对较小的类集合按照相似度将最小类集合并获取新的类集。在第一个环节中，主要思路为：基于 K-最近邻算法，hMetic 算法按照边的权重实际分割关系图，随机指定一个点，再找到类中与之相似度最高的 K 个点，便构成了最小类，其中，相似度的分析借助点间距大小实现。在第二个阶段中，主要思路为：深入分析两个类的相似性，大多是结合类的邻近性以及类内对象的连接状况分析类的相似性，也就是说，若两个类均存在非常大的互连性，同时两者临近，则可以将两者合并起来。
5.1.2 双向广度优先搜索算法
双向广度优先搜索（DBFS）算法是对 BFS 的延伸。BFS 算法会按照广度优先原则由一个方向启动搜索，直至检索所有节点或者获取目标节点。不同于 BFS 算法，DBFS 算法基于两个方向进行搜索，会按照广度优先的原则启动，能够按照实际需求、数据的特点等制定搜索方向，当两个搜索方向重合时或者获取目标节点时，这一算法停止。所以，相比 BFS 算法，DBFS 算法所获取的搜索树深度大幅降低，不管是时间上还是空间上，这一算法均比较优异。按照搜索速度以及最初搜索方向的差异，DBFS 算法可分成两类：一是在两个方向上轮流搜索；二是先从有限搜索点数相对较少的方向开始。至于两个方向节点数是否相同，第二种方式未做限定，能更好的的贴合现实状况。在搜索前，广度优先搜索算法（BFS）未设定具体的目标。
..........................
第六章 总结与展望
6.1 总结
本文调研了轨迹聚类方面的相关研究工作，针对调研结果阐明了本文的研究目的，主要思路以及研究的主要内容。在充分分析轨迹多属性特征的基础上，通过对已有聚类方法的改进、并行化和结合，提出了和通过一套面向大规模轨迹数据的高效聚类算法，并通过大量实验验证了算法的有效性和高效性。主要贡献包括如下三个方面：
（1）通过对轨迹数据关键点、代表点的选取，可以在尽量不丢失聚类准确度的前提下加快轨迹数据的聚类分析速度。使用离散 Fréchet 距离度量方法计算轨迹多个属性的相似度并融合，再将该相似度与 K-Means 算法相结合提出了基于轨迹多属性融合的 FK-Means 算法，实现了更全面体现轨迹特征的聚类分析过程。
（2）为了提高轨迹数据的聚类分析效率，在对大规模轨迹数据处理方面使用了并行化聚类的思想，将 MapReduce 框架与 FK-Means 算法结合，实现了聚类的并行化操作，在尽量不影响聚类准确度的前提下可以更快的处理大量数据，并使用改进后的 LOF 因子对得出的聚类结果进行优化，提高并行聚类结果的准确度。
（3）在对新增轨迹数据的聚类分析方面，使用了增量聚类的思想。首先利用 FK-Means聚类算法新增数据进行聚类；然后将双向广度算法与 Chameleon 算法相结合提出了 DC 算法，实现了对新增轨迹数据高效并准确的聚类分析。
参考文献（略）