1.2.1 轨迹数据挖掘方法分类[12-20]

轨迹数据挖掘方法的分类方式有多种：根据数据挖掘所关注的时空维度可以分为空间轨迹挖掘和时空轨迹挖掘；根据数据挖掘的主要任务可以分为轨迹模式挖掘、轨迹聚类、轨迹分类、轨迹预测、异常检测等。本节将根据不同的挖掘任务对轨迹数据挖掘的主要方法进行介绍。

1.轨迹模式挖掘

轨迹模式挖掘是轨迹数据挖掘的主要任务之一。其目标是从轨迹数据中发现移动对象运动的时空模式。这对于人类理解人群流动、动物迁徙、城市规划、天体运行与宇宙演化等诸多问题具有重要价值。轨迹模式主要有伴随模式、频繁模式、周期模式、聚集模式、异常模式5种。对于不同模式的挖掘任务，挖掘方法也不同。上述5种模式挖掘比较在表1.2中给出。

伴随模式挖掘是指从时间和空间两个维度出发，挖掘大量时空轨迹数据集中与给定轨迹最相似的K条轨迹，这些轨迹在地理空间中表现为同时运动，在交通规划与资源配置、服务推荐、疫情防控、治安管理等多个领域中具有重要应用。伴随模式挖掘主要通过持续时间和空间地理区域约束来查找范围，常用方法包括Apriori、频繁模式树（Frequent Pattern-Tree, FP-Tree）、动态时间规整（Dynamic Time Warping, DTW）、最长公共子序列（Longest Common Subsequence, LCSS）等。

时空轨迹的频繁模式挖掘与序列数据的频繁模式挖掘类似，但由于轨迹数据的异频采样性、数据质量差、数据漂移等特征，直接采用传统序列模式进行挖掘的效果并不好。因此，研究者对序列挖掘模式的相关方法进行了扩展，T模式是扩展方法的典型代表，被用来提取轨迹数据中位置、时间和语义维度等信息。借鉴T模式也出现了一些跟踪性的研究。Apriori、FP-Tree也是频繁模式挖掘的经典算法，相关算法还有AprioriTraj、FPS-Tree（单遍扫描频繁模式树）、MR-PFP（并行频繁模式增长）等，这些算法都在轨迹数据的频繁模式挖掘中取得了不错的效果。

移动对象的活动具有很强的随机性，在空间上是多重交叉的，不仅表现出序列性，还表现出周期性，周期模式挖掘也是一类典型的模式挖掘任务。周期模式是指轨迹中不同时间内周期性出现的序列观测值，这种模式在日常生活中很常见，如运动爱好者每天早上在一定时间段内晨跑或在特定时间去健身房健身，旋转机械在特定时间反复经过某一位置。周期模式挖掘的常见做法：首先对活动周期、停留时间、位置等与周期性活动相关的兴趣点（Point of Interest, POI）进行提取，然后对这些POI进行分析，判断是否符合周期模式，傅里叶变换、自相关等都是其中常用的分析方法。轨迹数据的周期性特征可以帮助人们合理地配置规划资源，同时利用周期性可以对轨迹进行压缩与存储，从而降低轨迹数据的存储开销，加速轨迹数据分析和处理的效率。

聚集是一种典型的活动方式，聚集的区域通常为有意义的地理区域，聚集活动通常对应着不平常的事件。聚集模式挖掘有助于发现、监测、预测日常生活中非平凡的群体事件，促进社会安全和稳定。此外，聚集模式挖掘也有助于合理配置资源，开展交通规划等。遗传算法、神经网络、聚类技术、属性分析在聚集模式挖掘中应用相对广泛。

轨迹数据的异常模式挖掘旨在发现轨迹数据中偏离大多数轨迹的轨迹。进行异常模式挖掘的好处是，一方面挖掘出的异常轨迹本身可能具有重要的研究价值，另一方面可以为其他任务的开展提供更可靠的数据。轨迹异常模式挖掘的常用方法包含机器学习、统计分析、距离、网格划分、轨迹特征分析等几大类，应用场景主要涉及交通分析、事故预警等。

2.轨迹聚类

轨迹聚类是一种典型的时空聚类分析技术，主要目标是将轨迹点或轨迹按照某种时空相似性度量分为不同组，使得同一组内的轨迹点或轨迹相似性足够高。轨迹聚类方法的分类如图1.4所示。

基于密度的方法根据密度约束将轨迹点归为不同簇。高效的密度度量方式是这一类方法取得好的聚类结果的关键。基于密度的噪声空间聚类（Density-Based Spatial Clustering of Applications with Noise, DBSCAN）、点顺序识别聚类结构（Ordering Points to Identify The Clustering Structure, OPTICS）、密度连接聚类（Densest-Join Clustering, DJ-Cluster）、基于群体智能和多目标优化的聚类（Clustering Based on Swarm Intelligence and Multi-Objectine Optimization, CB-SMoT）等算法是这一类方法的典型代表。这一类方法是轨迹聚类中经典且常用的方法，能够发现任意形状的簇且对噪声不敏感，但是这一类方法计算量大，通常涉及多个参数且参数的取值难以确定。

基于距离的方法利用某种距离度量手段获得轨迹点之间的距离并以此来衡量轨迹的相似性，最后将相似的轨迹聚为一类。轨迹聚类中应用比较广泛的距离度量有欧氏距离、DTW距离、LCSS距离、实序列编辑距离（Edit Distance on Real Sequence, EDR）、Hausdorff距离、Frechet距离等。不同距离度量对数据的要求不同：欧氏距离简单，但是不能处理长度不一致的轨迹且对噪声敏感；DTW距离相对灵活，对轨迹长度不做限制，但是结果受离群点影响大；LCSS距离对噪声不敏感，但是其中的最小阈值参数较难确定；EDR对噪声不敏感，能够处理不同长度的轨迹和时间漂移，但是该计算方法的时空复杂度高；Hausdorff和Frechet都是基于形状的距离度量，Hausdorff距离计算时需要考虑双向距离的不同，Frechet距离利用动态规划的思想，二者受噪声影响都较大。

基于特征的方法并不直接对轨迹本身进行比较，而是先从轨迹中提取特征，然后根据特征定义相似性度量，最后利用相似性度量的结果将轨迹分为不同簇。轨迹聚类中利用的特征并不唯一，包括密度、速度、加速度、方向角、转向角、地理标记和属性标记等。基于特征的方法中所涉及的特征度量方式多是人为定义，最终结果受人为因素影响较大，且不同特征度量下获得的特征值差异可能较大。

基于分段的方法根据不同的分段规则将一条完整的轨迹分割成多个较小的轨迹段，将这些轨迹段作为聚类的基本单元。例如，将每个线段的端点视为位置；利用矢量线来表示轨迹并选择特征点来打断整条轨迹，以轨迹段为聚类对象。基于分段的方法能够降低长轨迹处理的复杂度，便于抓住轨迹的局部特征，但是可能损失轨迹的整体特征，且聚类效果受分段的影响较大。

上述轨迹聚类方法多以传统轨迹聚类技术为基础，部分方法已经难以适应轨迹大数据体量大、时效性高、质量低等多方面的需求了。随着人工智能、神经网络、深度学习等技术浪潮的不断推进，高性能的轨迹聚类、基于学习的轨迹聚类技术迎来了研究热潮。例如，利用图形处理器（Graphics Processing Unit, GPU）优化算法，降低轨迹相似性度量、特征提取及聚类过程中的时间开销；基于Spark、MapReduce等实时并行分布式计算框架优化轨迹聚类算法的性能；利用自编码器（AutoEncoder, AE）、卷积神经网络（Convolutional Neural Network, CNN）、循环神经网络（Recurrent Neural Network, RNN）、图神经网络（Graph Neural Network, GNN）等学习轨迹的表征，并通过表征对轨迹进行聚类。

轨迹聚类在整个轨迹数据分析的框架中尤为重要，它既是轨迹数据分析中一个独立的分析任务，又可以用作其他任务中的辅助技术手段。例如，在数据预处理中，通过聚类识别噪声，提高数据质量；在轨迹压缩过程中，通过聚类减少对轨迹数据挖掘的计算资源和存储资源的消耗；在停止点提取中，通过聚类提取满足时空约束的停止点；在轨迹数据分类中，首先通过聚类提取特征，然后根据提取的特征建立分类模型并进行数据分类。除此以外，轨迹聚类在模式挖掘、隐私保护等任务中也有交叉应用，后续章节中的噪声处理、特征提取都与聚类技术息息相关。

3.轨迹分类

轨迹分类与聚类类似，都是将具有某种共同属性或特征的数据归并在一起。二者区别是，聚类根据数据自身的性质分组，而分类的结果依赖于轨迹数据的标签。这种带标签的轨迹数据被称为训练数据，分类过程中需要通过训练数据建立一个分类模型，使这个模型可以用于预测标签未知的轨迹数据的类别。

轨迹分类过程如图1.5所示。图中的预处理过程与轨迹数据分析框架中的预处理技术类似，主要包括去噪、分段、去重等。轨迹特征提取的主要目的是分离出起分类作用的决策属性或特征，加速分类器的训练，时间特征、位置特征、速度特征、形状特征等都是特征提取中关注的特征。建立分类器的过程是将训练数据的特征向量作为分类器的输入，训练出分类器。常用的分类器包括支持BN、HMM、支持向量机（Support Vector Machine, SVM）、决策树（Decision Tree, DT）、朴素贝叶斯（Naive Bayes, NB）、随机森林（Random Forest, RF）、高斯混合模型（Gaussian Mixed Model, GMM）、逻辑回归（Logistic Regression, LR）、神经网络等。

轨迹分类在行为分析、服务推荐、智能交通管理、工业故障检测等诸多领域都发挥了积极的作用。但是对轨迹数据分类并非易事，轨迹分类中的数据预处理、特征提取及分类器训练的各阶段都直接影响最终的分类效果。例如，轨迹数据本身噪声、冗余较大，数据存在漂移的情况，以及采样频率不同；同时，轨迹的复杂度越来越高，单条轨迹的长度增加、同一轨迹中出现不同类型或模式的概率较大。上述因素对轨迹数据的预处理提出了更高的要求，提高预处理精度为后续分类工作提供更可靠的数据是需要重点关注的问题之一。分类模型构建中分类特征提取直接决定了后续分类的有效性，如何对不同类型轨迹提取出最有辨别能力的特征难度较大。分类是一种依赖于标签数据的方法，而轨迹大数据背景下具有标签的数据相对较少且不一定完备，尤其是在复杂运动情况下，一条轨迹包含多种运动状态，人为标注的难度很大。如何让模型在标签少、标签不完备的情况下获得理想的分类效果也是当前亟待解决的问题。

4.轨迹预测

轨迹预测也叫移动目标轨迹预测，是指通过挖掘移动目标的历史位置或其他与行为相关的信息，来预估移动目标在未来某个时刻的位置或行为状态。轨迹预测的相关研究方法大致可以归为数据驱动和行为驱动两大类，数据驱动的方法从轨迹数据本身出发，通过发现海量历史数据背后隐含的移动对象的行为特征来对移动目标的未来趋势进行预测，基于行为驱动的方法从移动对象的行为和意图出发，通过移动目标的状态和操作信号来辨识意图和预测下一时间段的行为。不同轨迹预测方法的比较如表1.3所示。

概率统计、神经网络、深度学习及混合模型是数据驱动方法中的四大类模型。概率统计模型简单高效，但是这类模型建立在历史轨迹数据与待预测轨迹存在一定相关性的基础上，常用概率统计模型涉及卡尔曼滤波器（Kalman Filter, KF）、差分自回归移动平均（Autoregressive Integrated Moving Average, ARIMA）、HMM、GMM、NB等方法及其相关变体。神经网络和深度学习模型自适应能力较强、实时性较高，但是在模型训练时间、收敛速度及可解释性上存在较大问题。反向传播（Back Propagation, BP）网络、多层感知机（Multi-Layer Perception, MLP）、长短期记忆（Long Short-Term Memory, LSTM）、极限学习机（Extreme Learning Machine, ELM）、GAN等方法在这一类模型中获得了广泛的应用。为了集合不同模型优点，出现了混合模型的轨迹预测方法，如CNN-LSTM、LSTM-RNN、LSTM-GCN（Graph Convolutional Network，图卷积网络）、ELM-MLP等。这些方法泛化能力强，精度也相对较高，但是模型训练的时间消耗也较大。基于动力学模型和意图识别模型的行为驱动方法相对于数据驱动方法具有较强的可解释性，这类方法利用了移动对象的真实运动特征和运动意图，因此，预测的准确性与预测所用假设是否和真实环境一致关系密切。动力学模型中常用的方法包括：社会力模型、注意力机制；意图识别模型中常用的方法包括生成式模型等。

轨迹预测是智能科学与技术、交通运输等多学科的交叉研究，其结果对于推动智能交通管理、异常行为识别、资源调度分配、出行决策支持、动态路径规划（导航）等领域的理论和实践研究均具有重要的价值。

5.异常检测

异常轨迹是与数据集中频繁出现的轨迹模式不一致或不符合预期的轨迹。轨迹数据的异常检测从检测范围上分为异常值检测、异常轨迹检测两种。异常值是指偏离大多数数据或不符合预期的观测值。异常轨迹检测一方面可以为后续的分析与挖掘提供更加精准的数据，另一方面在科学研究和工业应用中的实用价值也很高。

轨迹数据中的异常检测方法主要包含基于统计、基于距离、基于网格、基于密度及基于学习的方法五大类，如图1.6所示。基于统计的异常检测方法主要有参数化方法和非参数化方法两种。参数化的方法简单快速，但是参数确定和优化难度较大；除此之外，还包含基于高斯模型、回归模型、直方图、核函数的方法等。基于距离的异常检测方法由Knorr等人于2000年提出，首先用位置、方向、速度特征表示轨迹，然后利用相似性度量分离异常轨迹，其中常用的距离度量与基于距离的轨迹聚类方法类似。基于网格的方法先将轨迹路网划分成多个网格单元，然后对异常的网格单元序列进行检测。例如，利用欧氏距离、DTW、Hausdorff等距离度量计算网格轨迹的相似性，寻找异常轨迹；将网格与密度、速度、位置、方向等特征结合检测异常轨迹；在网格中开展局部异常因子（Local Outlier Factor, LOF）、DBSCAN等空间聚类检测异常；对网格建立索引，并在并行平台上开展异常检测，提升检测效率。基于密度的异常检测方法将不满足密度约束的轨迹点或轨迹作为异常轨迹，其中密度度量包含空间密度和时空密度两种，高斯概率密度、DBSCAN、密度峰快速搜索和识别聚类（Clustering by Fast Search and Find of Density Peaks, DPC）等算法及其相关变体是这一类方法中的常用方法。

随着深度学习技术在高维数据、序列数据、空间数据、图数据等类型数据上的应用，研究人员提出了大量基于学习的轨迹数据异常检测方法。这类方法的主要思想是，通过设计深度学习模型，让算法学习正常轨迹和异常轨迹之间的时空特征差异来识别异常。在实际应用中已经证明，基于学习的异常检测方法的表现明显优于其他方法。CNN、RNN、AE、GAN、LSTM等都是这类方法中的代表算法。

轨迹的异常检测研究具有重要的理论价值和实践意义，在现实中的应用也比较广泛。例如，网络入侵检测、金融和电信欺诈检测、工业故障检测、医学诊断、动物习性分析、自然气象预测等。