1.1.3 轨迹数据分析的关键技术[4-11]
轨迹数据是移动对象运动过程的典型表征，在以人类生活轨迹为典型代表的轨迹数据中，个体行为具有差异性和多样性，但是不同个体之间的交互及个体与环境之间的交互不是独立的，而是存在不同程度的相互影响，这种影响在行为上体现出关联性和规律性，如餐厅的高峰期基本都在早、晚，大型音乐会吸引着具有相同音乐爱好的人群等，都证明了这种影响的存在。轨迹数据分析的意义和价值在于发现这种关联性和规律性，并利用这种关联性和规律性解释社会生活中的复杂问题和现象，为生产生活提供技术和知识支撑。轨迹数据的大量涌现为数据关联性和规律性的发现提供了保障，研究人员可以通过相关轨迹数据分析技术开展时空结构和规律的建模，从而为诸多领域的决策支撑提供服务。轨迹数据分析和处理框架如图1.2所示。
1.轨迹数据预处理
轨迹数据预处理是轨迹数据分析的第一个环节，主要目的是通过数据清洗、停止点检测、轨迹分段、路网匹配、轨迹压缩等手段将原始轨迹数据转换成后续用于完成轨迹数据挖掘、轨迹索引与检索、隐私保护、可视化任务的高质量目标数据。预处理效果直接影响下游任务开展的效果。因此，针对不同的数据特征、应用场景与挖掘目标，采用不同的预处理方式，对后续任务的有效开展具有重要意义。
图1.2 轨迹数据分析和处理框架
（1）数据清洗。数据清洗的主要目的清除冗余、噪声或空值。冗余多是移动对象在静止、匀速状态或设备故障情况下采集的轨迹点，噪声和空值则是由环境干扰，或者软/硬件设备异常导致的错误采样。冗余和噪声的存在一方面增加了轨迹数据分析与处理的时空开销，另一方面也降低了分析结果的可靠性。常用的数据清洗方法包括滤波方法、子空间方法、影响空间方法、回归与插值等。
（2）停止点检测。停止点（Stay Points）也叫停留点，是移动对象某一段时间内在某个区域内停留产生的点。如图1.3所示，虚线圈中的点即为轨迹数据的停止点。停止点聚集的区域通常为某些有意义的区域，如图1.3中的办公室和超市。在热点区域检测、频繁模式挖掘中通常会先对停止点进行提取，并将提取的点作为后续行为模式分析的数据对象。因此，停止点检测也被作为轨迹数据预处理的方法之一。常用的停止点提取方法包括基于速度阈值、加速度阈值和位置偏移阈值的方法，空间密度聚类方法，以及时空密度聚类方法等。这些方法通常以某种空间或时空度量为基础，将满足阈值约束的点标记为停止点。
（3）轨迹分段。轨迹分段也是很常见的一种预处理方法。分段的目的有两个：一是降低长轨迹分析与处理的复杂性；二是能够使轨迹的语义特征更加明确，便于子轨迹模式分析和挖掘。轨迹分段也是一个很容易影响下游任务性能的预处理手段，分段的标准主要有：时间（或空间）阈值、特征拐点、几何拓扑、语义特征等。在基于时间阈值的分段中，以等时间间隔（分钟或小时为单位）进行分段；在基于特征拐点的分段中，以速度特征值、方向特征值、相似性特征值等变化的拐点为基准进行分段；在基于几何拓扑的分段中，首先分析轨迹的几何拓扑结构，根据几何拓扑结构将轨迹分成若干段；在基于语义特征的分段中，首先考察待分段轨迹的语义，将语义发生明显变化的点作为分段点进行分段。
图1.3 停止点示意图
（4）路网匹配。路网匹配是指将轨迹中一系列有序的地理位置与电子地图中的路网进行关联，然后通过地图匹配算法得到车辆位置的偏差信息并进行实时修正，从而实现对车辆的定位和追踪。例如，网络打车平台将出租车的GPS轨迹匹配到实际路网上，对出租车位置进行追踪，从而确保乘客的出行安全。隐马尔可夫模型（Hidden Markov Model, HMM）、几何匹配、拓扑匹配、概率匹配是其中较为常用的方法。
（5）轨迹压缩。随着大数据时代的不断发展，轨迹的数据规模越来越大，给存储、管理、查询等均带来了巨大的压力。因此，轨迹压缩越来越受到研究者的重视，它能够在保持决策能力不变的条件下尽可能地减少轨迹的数据规模，以便对数据进行存储、传输和处理。常见的轨迹压缩算法可以分为以下几类：基于路网约束的轨迹压缩，这类方法主要用在车辆轨迹压缩上；基于相似性度量的轨迹压缩，压缩的前提是度量不同轨迹的相似性，将相似性高的轨迹作为一类，统一压缩；基于特征点的轨迹压缩，受特征提取的影响较大，提取不同的特征点，最终压缩效果的差异可能较大；基于语义信息的轨迹压缩，压缩后轨迹的可读性较好，但是容易导致空间信息丢失。
2.轨迹索引与检索
时空轨迹数据分析已经广泛应用于社会生活的各个领域，如城市规划、交通管理、物流管理、旅游路径推荐、自然灾害预测与预警、疫情传播监测等，上述任务的完成与轨迹检索（或查询）息息相关，海量轨迹中的相似性轨迹查询已经成了时空轨迹数据分析的重要研究内容之一。而高效查询的实现与索引密不可分。索引能够通过减少轨迹间相似度计算的工作量来提高轨迹查询效率。
（1）轨迹检索。轨迹检索也叫轨迹查询，是指在用户给定的查询条件下，返回用户需要的轨迹数据。Deng等人根据轨迹查询范围将轨迹查询分为点或点集查询、区域查询，以及线查询三类。点或点集查询通过用户给定的查询条件返回兴趣点或兴趣点的集合。K近邻兴趣点查询是这一类方法的典型代表，其通过相似性度量获取与目标查询条件最相近的K个兴趣点。区域查询返回的是符合查询约束的特定区域内的轨迹段，典型查询方法包括Voronoi图和K近邻区域查询。线查询的主要目的是获取相似或满足距离约束的轨迹，在该类方法中以Top-K查询最为常见，主要包括基于索引的Top-K查询、基于距离的Top-K查询及基于新硬件（并行GPU）的To p-K查询等。
（2）轨迹索引。通过遍历的方式来从海量数据库中检索满足条件的轨迹的时空开销是难以接受的。轨迹索引为高效查询的实现提供了解决方案，现有的多数查询方法都以索引为基础，索引和检索已经密不可分。例如，在经典的Top-K查询中引入KD-Tree、B-Tree、R-Tree、四叉树等索引来提升查询效率。
3.轨迹数据挖掘
轨迹数据挖掘是轨迹数据分析的主要内容，可以在轨迹数据预处理之后进行，也可以在轨迹索引与检索之后进行，主要目的是挖掘轨迹数据中有价值的知识或模式，主要任务包括轨迹模式挖掘、轨迹聚类、轨迹分类、轨迹预测以及异常检测等。
4.隐私保护
移动终端、全球定位系统及移动互联网的发展，促进了基于位置服务（LBS）技术的发展，通过数据分析来提高用户服务质量已经成为趋势，这使得轨迹隐私泄露问题更加显著。轨迹隐私属于个人隐私的范畴，主要指轨迹中的敏感信息或从轨迹中推断出的其他个人敏感信息（如移动对象的家庭或工作地点、兴趣爱好、健康状况等）。恶意攻击者可能利用上述信息开展不法行为，从而造成不良社会影响。因此，在轨迹大数据背景下进行隐私保护对于个人及社会意义重大。现阶段，轨迹隐私保护主要有地理位置隐私保护、时间相关性隐私保护、行程特征隐私保护三大类。例如，K-匿名模型通过地理匿名区域隐藏用户的真实位置；借助生成对抗网络（Generative Adversarial Network, GAN）、HMM、贝叶斯网络（Bayesian Network, BN）等对轨迹进行伪造，然后将伪造的轨迹代替原始数据进行发布，消除时间相关性；将轨迹中的主要特征以直方图的形式进行表示，再对直方图中的各区间添加噪声后发布，以掩盖轨迹行程特征。
5.可视化
广义的可视化是数据可视化、信息可视化、科学可视化等多个领域的统称，轨迹数据的可视化原指根据地理信息和空间数据模型，有效表示和分析地理现象与空间实体的关系，这种可视化多被作为GIS中的一种服务。随着轨迹数据分析技术的不断发展，人们对轨迹数据分析的可理解性越来越关注，轨迹可视化已经从服务发展成涵盖轨迹数据分析多个阶段、多种任务的技术手段。例如，可视化技术能够将轨迹数据转换成易于理解和操作的形式，使得人们能够直观地观察轨迹数据的时空分布；对特征提取后的轨迹点进行可视化可以帮助人们理解轨迹特征，发现热点位置；对天体运行轨迹的可视化可以帮助人们理解不同天体运行的周期性特点。