随着传感器和便携定位设备的广泛使用，各行各业积累了海量的时空轨迹数据。如何从轨迹数据中分析挖掘有意义的移动模式^[1-4]，是时空数据库领域的研究热点之一。时空轨迹刻画了移动对象的历史移动过程，此处特指自由移动空间下运动的物体，如船舶、飞机、动物等。移动对象在运动过程中有时会展现出不同寻常的移动模式，往往蕴含了重要行为，或者表征了异常事件。例如，轮船为避免碰撞频繁改变航向，表观呈现沿S形轨迹行进；民航飞机在等待降落之前往往在机场上空盘旋飞行；动物通过气味追踪猎物，一般遵循由四周向目标中心逐渐汇聚的特定觅食策略。从轨迹数据出发的规则发现与知识提取为行为解译、轨迹预测、城市规划、异常监测等应用提供重要技术支持。

国内外学者在轨迹移动模式挖掘方面开展了大量的研究，大致可以分为群体层面、个体层面的轨迹模式分析。从群体角度而言，轨迹模式分析侧重于群体移动对象共现模式和运动趋势的发现。共现模式寻找在一定时间内密集移动的对象，常见的共现模式有Flock^[5]、Convoy^[6]、Swarm^[7]、Crew^[8]等，常用于挖掘游行、庆祝活动和交通堵塞等群体性事件^[9]。运动趋势表征了时空规律信息，贾涛等^[10]采用微观尾气排放模型，从点、线、面3个角度研究了武汉市出租车行程轨迹的CO₂排放量的时空分布模式；He等^[11]首次单独依赖共享单车数据完成大范围的违章停车检测，为解决机动车占道停放等问题提供了新思路。

个体层面上的轨迹模式分析则可以得到单个对象的移动行为特征，可归纳为轨迹分割问题，即将轨迹分割为有特定语义的片段序列，为检测移动变化及其行为机制提供基础。Buchin等^[12]基于一系列时空相似标准，如位置、方向、速度、曲率等，提出一种通用的单轨迹分割框架；向隆刚等^[13]、吴涛等^[14]研究了基于轨迹Stop/Move模型^[15]的子轨迹划分及其语义表达问题，同时针对Stop提取问题提出了序列聚类和指数表征两种算法^[16-17]；Biljecki等^[18]对个体出行轨迹的交通方式进行划分，在交通规划应用以及用户偏好推荐系统中具有重要参考意义；任慧君等^[19]从公交车轨迹数据中提取超速、急加速、急减速、急转弯等潜在的不安全驾驶行为，用于评估驾驶员个体的驾驶行为安全性；Kajioka等^[20]根据运动和距离状态将行人移动轨迹序列化为统一描述的符号序列，采用比较序列模式挖掘男、女行人轨迹模式的差异性。

综上所述，现有的轨迹分析研究大多是面向群体轨迹的移动模式挖掘，而面向单条轨迹的研究更多是针对轨迹划分与停留提取两类问题。考虑到在单条轨迹的持续时间内，不同移动模式具有不同的方向表征，而同一模式呈现相似的方向语义表达，本文提出一种基于方向象限映射的轨迹移动模式分析方法。首先利用滑动窗口技术分析轨迹的方向信息，然后基于轨迹段的方向信息，将单条轨迹映射编码为一维的象限字符序列。在此基础上，建立特定移动模式的正则表达，据此采用有限状态自动机(finite state machine，FSM)来表达移动对象的象限时序状态及其转换^[21]，从而实现基于FSM的单轨迹移动模式探测。

本文主要通过分析单轨迹移动模式的方向表征，在象限空间中构建出轨迹的字符序列表达，从而将几何空间的移动模式探测转化为指定的字符串匹配问题，不仅可以降低移动模式探测的复杂性，而且能够提高移动模式探测的正确性和鲁棒性。实验结果表明，本文方法有效表达了移动模式的方向时序变化语义，在探测典型的“8”字盘旋单轨迹移动模式方面具有较好的表现。

1 轨迹移动模式的方向象限分析法

基于方向象限映射的轨迹移动模式分析法如图 1所示，主要包括如下步骤：基于滑动窗口的轨迹段方向分析、方向-象限映射、移动模式正则表达、象限序列FSM构造和移动模式探测。

1.1 轨迹方向计算 1.1.1 数据预处理

轨迹是将移动对象的连续运动离散化为一系列带时戳的空间散点，记录了被观察目标在给定时间段内的空间位置变化^[22]。一条全球定位系统(Global Positioning System，GPS)轨迹记录是由时空点组成的有序列表。

定义1 GPS轨迹：T={p₁=(x₁, y₁, t₁), p₂=(x₂, y₂, t₂) … p_n=(x_n, y_n, t_n)}。其中，p_i=(x_i, y_i, t_i)是构成轨迹的一个时空点，i=1, 2…n, t₁ < t₂ < t₃ < … < t_n, x_i和y_i分别表示经度、纬度，t_i是采样时刻。

在数据采集过程中，由于采集设备误差、物体遮挡等因素常产生噪声和错误信息，需要对GPS数据进行预处理，包括插值、纠正漂移点、剔除速度异常点等。插值主要基于匀速线性移动的假设，采用双线性插值技术；偏移点纠正主要采用高斯平滑技术，去除明显偏离的轨迹点；速度异常点剔除主要基于速度阈值，删除速度超出常识的轨迹点。

1.1.2 滑动窗口计算

根据GPS轨迹数据中连续采样点的信息，对预处理后的数据进一步处理可以获取移动对象的运动特征，如速度、方向及其变化等。从数据表现上来看，轨迹的移动模式主要是由方向，特别是方向的变化来承载与体现的。如图 2所示，定义轨迹点的方向为两相邻轨迹点构成的轨迹段与正北方向之间的夹角，规定正北方向为0°，方向值按顺时针变化范围为[0°, 360°)。根据北方向单位向量m₀=(0, 1)和相邻轨迹点构成的线段向量m₁=(x₂-x₁, y₂-y₁)，轨迹点p₁的方向值∂₁计算公式如下：

${\partial _1} = \left\{ \begin{array}{l} \frac{{{{\cos }^{ - 1}}({{\boldsymbol m}_1} \bullet {{\boldsymbol m}_0})}}{{\left| {{{\boldsymbol m}_1}} \right|\left| {{{\boldsymbol m}_0}} \right|}} \cdot \frac{{180}}{\pi },{x_2} \ge {x_1}\\ \left( {2\pi - \frac{{{{\cos }^{ - 1}}({{\boldsymbol m}_1} \bullet {{\boldsymbol m}_0})}}{{\left| {{{\boldsymbol m}_1}} \right|\left| {{{\boldsymbol m}_0}} \right|}}} \right) \cdot \frac{{180}}{\pi },{x_2}<{x_1} \end{array} \right.$

(1)

将移动对象的连续运动离散化为基于时间序列的轨迹点集，单个点的运动状态往往会存在局部抖动，移动特征可能不稳定，即仅考虑轨迹点的方向信息可能会忽略移动的连续性与时空关联性，从而导致重要模式信息的丢失。为了提高方向提取的鲁棒性，本文采用滑动窗口来拟合轨迹段，以窗口线段来计算和表达轨迹段的方向。本文设置长度固定的滑动窗口W以相同步长沿整条轨迹扫描，在当前窗口中，拟合线段的方向与窗口内若干个连续轨迹点的方向密切相关。考虑到方向数据的循环性，采用方向统计学^[23]中的循环量均值计算方法提取窗口线段的方向值：

$\overline \partial {\rm{ = }}\left\{ \begin{array}{l} {\tan ^{ - 1}}(\overline s /\overline c ),\overline s>0,\overline c>0\\ {\tan ^{ - 1}}(\overline s /\overline c ) + 180^\circ ,\overline c<0\\ {\tan ^{ - 1}}(\overline s /\overline c ) + 360^\circ ,\overline s<0,\overline c>0 \end{array} \right.$

(2)

式中，$\overline s = \frac{1}{K}\sum\limits_{j = 1}^K {\sin {\partial _j}} $；$\overline c = \frac{1}{K}\sum\limits_{j = 1}^K {\cos {\partial _j}} $；∂_j是轨迹点的方向；K是滑动窗口的长度，即当前窗口包含K个连续轨迹点。

1.2 方向象限映射

滑动窗口将原轨迹分割为带方向特征的轨迹段序列，连续轨迹段之间的方向差异反映了运动方向的变化趋势(如直行、左转弯或右转弯)^[24]。按照轨迹段的移动趋势变化，可将轨迹的模式特征理解为移动过程中方向相似的一组轨迹段序列，即邻近序列间的关联性及其转换规律可为不同移动模式的发现提供依据。

显然，方向角值∂∈[0°, 360°)，从而可将轨迹段的方向按照其角值范围映射到4个象限，即按图 3所示规则进行映射。首先将单条轨迹上所有窗口线段的方向值映射到相应象限，然后递归合并相邻且位于同一象限的窗口。考虑到象限边界处可能存在抖动，需要计算移动对象在象限内的逗留时间：对于那些低于时长阈值的子轨迹，则认为是其前一相邻轨迹段的延续，转化到相应象限，并与相邻轨迹进行合并。

图 4示意了一条轨迹的象限映射，箭头表示轨迹行进的方向。基于轨迹段的方向特征，按照时间序列依次记录其轨迹段的象限字符，从而将轨迹的方向序列转化为象限空间中的字符序列。

将轨迹的方向序列转换为象限字符序列，实质上可看作是一种紧凑压缩的轨迹建模方法，这种方法强调象限时序状态之间的转换，进而挖掘状态转换规律中所隐含的移动模式。象限表达的移动模式对轨迹点的空间平移和缩放是不变的，且单条轨迹的象限字符序列是基于方向特征，消除了空间参考系的限制，具有空间变换上的鲁棒性。显然，基于象限字符序列的轨迹模式挖掘一方面将有效降低问题求解的搜索空间，另一方面有助于提高问题求解的鲁棒性。

1.3 移动模式的正则式表达与处理 1.3.1 移动模式的象限序列呈现

不同的移动模式在时空上有不同的呈现，并通过方向角序列反映在轨迹的象限访问序列之中。其中，转弯行为(大于90°方向变化的)隐含着移动对象的航向变化趋势，是组成移动模式的方向语义单元，也是分析其他复杂移动模式的基础。依据轨迹的前进方向，可将转弯行为进一步区分为左转弯和右转弯，如图 5所示。转弯前后轨迹段间的方向角差异即为轨迹转角，由于转弯行为的轨迹转角大于90°，前后轨迹段将被映射到相邻象限中。在图 5中，左转弯的象限序列是Ⅲ→Ⅱ，而右转弯的象限序列为Ⅱ →Ⅲ。

以图 6给出的轨迹圆周移动模式为例，箭头表示行进方向，而黑色圆点为起/终点。在轨迹T₁、T₂和T₃的持续时间内，移动对象各自完成一次完整的圆周移动，方向角的累积变化360°。在方向-象限映射机制下，3条轨迹的象限字符序列分别为T₁→(Ⅱ Ⅰ Ⅳ Ⅲ)、T₂→(Ⅳ Ⅰ Ⅱ Ⅲ)、T₃→(Ⅲ Ⅱ Ⅰ Ⅳ)(本文均用圆括号表示字符集合)。不难得出：圆形移动模式的象限序列一定连续访问了方向象限的4个编码区域。

根据左/右转弯情况，可将圆周移动划分为顺时针和逆时针两种状态。图 6中T₂是顺时针圆，而T₁和T₃是逆时针圆。顺/逆时针圆周运动访问象限4个编码区域的顺序是有所不同的。进一步分析可知，根据起始方向的特征，圆周移动在顺时针和逆时针访问下共有8种象限时序分布，如图 7所示。其中，顺时针圆有(Ⅰ Ⅱ Ⅲ Ⅳ)、(Ⅱ Ⅲ Ⅳ Ⅰ)、(Ⅲ Ⅳ Ⅰ Ⅱ)、(Ⅳ Ⅰ Ⅱ Ⅲ)；逆时针圆有(Ⅳ Ⅲ Ⅱ Ⅰ)、(Ⅲ Ⅱ Ⅰ Ⅳ)、(Ⅱ Ⅰ Ⅳ Ⅲ)、(Ⅰ Ⅳ Ⅲ Ⅱ)。基于象限编码分布的时间循环性，面向连续发生的圆模式，本质上来说，顺逆圆周的上述象限时序分布可以分别概括为(Ⅰ Ⅱ Ⅲ Ⅳ)、(Ⅳ Ⅲ Ⅱ Ⅰ)。

1.3.2 移动模式的正则式表达

轨迹的移动模式可理解为象限字符按照特定规则排列而成的字符串，满足相同规则的字符串描述相同的移动模式。为了表示具有某种规律的字符序列，需要用一种形式化的语言来描述字符串连接的规则，以便计算机进行自动处理。正则表达式^[25]是一种针对字符串操作的逻辑公式，采用预先定义好的特定字符及其组合来组成一个规则字符串，可以用来表达对字符串的一种过滤逻辑，在自然语言处理领域应用广泛。本节基于正则表达式，讨论象限表达下移动模式的字符串规则描述，首先给出一些基本定义。

定义2 字符集Alphabet：有限的字符集，记作：Σ={ Ⅰ，Ⅱ，Ⅲ，Ⅳ }。

定义3 字符串String：由Σ中有限字符构成的字符序列，如(Ⅰ Ⅲ)、(Ⅱ Ⅲ Ⅳ Ⅲ)。

定义4 语言Language：字符串的集合，可以是有穷集合，也可以是无穷集合。

定义5 象限正则表达式：描述定义在象限字符集Σ上的语言的一种特殊表达式。

在此基础上，进一步给出象限正则表达的基本语法范式和运算规则：

1) 空串ε：长度为零的语言。

2) 串运算：表达式X、Y的串运算表示的语言是将X语言的尾部连接上Y语言(此时X、Y为一个整体)，记作XY。

3) 并运算：有一系列字符可供选择，只要匹配其中一个就可以了。所有可供选择的字符都放在方括号内，方括号表示括号内字符的并运算。比如[XYZ]表示X、Y、Z之中任选一个。

4) X*：表示将0个、1个、2个…无穷个X先取串运算然后求并，即X*=[εX XX XXX…]。

5) X+：表示将1个、2个…无穷个X先取串运算然后求并，即X+=[X XX XXX …]。

6) 象限正则表达式使用()包围，代表该规则是一个整体，优先级大于串运算。

考虑到在象限序列中，移动模式被表达为某种规则的字符串，因此，基于方向象限的移动模式探测有必要首先构造其正则表达式，以圆周移动模式为例，(Ⅳ Ⅰ Ⅱ Ⅲ)+表达的语言即为满足(Ⅳ Ⅰ Ⅱ Ⅲ)序列分布的连续顺时针转圈轨迹模式。

1.3.3 象限时序状态分析与有限状态机建模

轨迹移动模式探测就是从一条轨迹的象限字符序列中搜索所有该模式约束下的规则子字符串，这是一个字符串匹配问题。

使用正则表达式定义模式便于理解语言的规则，但并不能拿来直接解析字符串。尤其是针对复杂且移动周期长的轨迹，直接使用正则表达式进行匹配工作量大且速度缓慢。因此，借助有限状态自动机完成移动模式探测的字符串匹配。有限状态自动机是一个处理信息的简单机器，表示有限个状态以及在这些状态之间转换的数学模型。任意有限状态自动机(包括确定性的和非确定性的)所能识别的语言都是符合一定正则表达的语言。由于正则语言的良好性质，在有限状态自动机的框架下，任何相关输入的判定都能被执行。

轨迹的象限字符编码原理符合正则表达要求，可以构建相应的轨迹象限时序状态自动机。利用有限状态自动机探测轨迹模式中的状态转移，将自动机表示为如下5元组：

$M = (Q,\Sigma ,\delta ,{S_0},F)$

(3)

式中，Q是自动机的非空有限状态集，Q={S₀, S, F}，S₀是自动机的初始状态，S是自动机的中间状态，F是自动机的终止状态；字符集Σ={ Ⅰ，Ⅱ，Ⅲ，Ⅳ }；δ是状态转移函数，表示了从Q×Σ→Q的一个映射，即f = (S_i，q)=S_j，当前状态S_i在输入字符q后转到下一状态S_j。其原理是自动机逐个读入输入的字符，逐次跳转状态，直到所有字符输入完毕。图 8是针对顺时针圆周轨迹模式建立的有限状态自动机。

任意给定一条轨迹的象限字符编码，都能在自动机中生成一条与之匹配的自动机状态转移路径。所有自动机状态都起始于初始状态S₀，然后依据自动机的状态转移规则，输入轨迹编码字符进行状态跳转。

已知一条轨迹的象限字符编码：T=(Ⅱ Ⅲ Ⅰ Ⅱ Ⅲ Ⅳ Ⅲ Ⅳ Ⅱ)，顺时针圆周移动模式探测过程如下：状态转移路径中起始状态为S₀，依次输入目标轨迹编码字符，得到对应的转换路径为“S₀→S₄→S₅→S₁→S₂→S₃→F₁→S₇→S₈→S₄”；由跳转表 1可知，状态转换路径中当i=6时，达到接受状态F₁，认为完成一次匹配即检测到序列模式(Ⅰ Ⅱ Ⅲ Ⅳ)对应下的顺时针圆周移动模式。

2 “8”字盘旋模式探测

飞机在降落时，如果剩余的油料过多会有一定危险，往往通过盘旋飞行耗油来降低风险。为缓解机场降落繁忙的状况，也可能盘旋一定时间等待着陆。空中盘旋是一种缓解流量、消耗时间的举措，盘旋性能是衡量飞机机动性能和格斗能力的指标之一，也是判断飞行员飞行技能的重要参考，其中连续“8”字移动是典型的盘旋行为。

2.1 “8”字盘旋模式的象限时序分析

图 9表示两条不同的“8”字移动轨迹，箭头是行进方向。基于本文提出的方向-映射规则，得到图 9(a)、9(b)对应的象限字符串分别为：T_a=(Ⅳ Ⅰ Ⅱ Ⅲ Ⅱ Ⅰ Ⅳ)，T_b= (Ⅲ Ⅱ Ⅰ Ⅳ Ⅰ Ⅱ Ⅲ)。

单条“8”字移动轨迹直观表现为移动对象连续完成顺、逆时针方向相反的圆周运动。基于字符串分割的思想，象限串T_a=(Ⅳ Ⅰ Ⅱ Ⅲ Ⅱ Ⅰ Ⅳ)可分割得到两个子串：T_a1= (Ⅳ Ⅰ Ⅱ Ⅲ)和T_a2=(Ⅲ Ⅱ Ⅰ Ⅳ)。由图 7可知，T_a1= (Ⅳ Ⅰ Ⅱ Ⅲ)表征顺时针圆周，T_a2=(Ⅲ Ⅱ Ⅰ Ⅳ)表征逆时针圆周，这与直接观察的轨迹特征一致，即移动对象先后完成顺、逆时针转圈。同理，象限串T_b=(Ⅲ Ⅱ Ⅰ Ⅳ Ⅰ Ⅱ Ⅲ)分割得到两个子串T_b1= (Ⅲ Ⅱ Ⅰ Ⅳ)和T_b2=(Ⅳ Ⅰ Ⅱ Ⅲ)，分别表征逆时针、顺时针圆。因此，象限表达的模式信息保持了模式的直观特征。

实际飞行轨迹中的盘旋行为检测多面向连续“8”字移动模式，并且考虑到顺时针、逆时针的差异性，构造表达式(Ⅰ Ⅱ Ⅲ Ⅳ Ⅲ Ⅱ Ⅰ)+和(Ⅰ Ⅳ Ⅲ Ⅱ Ⅲ Ⅳ Ⅰ)+，描述的语言是起始象限为Ⅰ且至少完成一次连续的“8”字盘旋行为，其他起始象限类似。图 10为构建的有限自动机：

2.2 实验过程和结果分析

为了验证基于方向象限映射的轨迹移动模式分析方法的有效性，本节选用Wikiloc(https://www.wikiloc.com)的免费公开飞行轨迹和自采轨迹两组数据源，开展“8”字盘旋模式提取实验。Wikiloc支持所有用户上传并分享轨迹，提供多种类型的轨迹数据。受限于“8”字盘旋行为的特殊性，本节从中选用转向信息丰富的飞行轨迹展开模式提取实验。自采轨迹由行人按正常步行速度、手持GARMIN eTrex 20GPS设备(定位精度优于10 m，经过差分后定位精度可提高至3 m)，以时间间隔为1 s的频率采集得到，该频率是设备的最高采样频率。考虑到人的步行速度，该采样频率能确保数据分析结果的可靠性。

基于象限映射的轨迹移动模式分析方法主要依赖3个参数，即滑动窗口长度K、窗口移动步长、象限逗留时间。实验中的参数设置应与采样频率相适应。

1) 滑动窗口长度的设置考察了参与计算的轨迹点在时间上的前后联系，决定了计算当前轨迹段的方向值要参考轨迹点前后多少个邻近点的方向值。滑动窗口长度过小时，轨迹点提供的邻近方向信息不足，均值法计算得到的窗口线段方向值误差较大，过大时，轨迹点本身可能处于差异较大的角值区间，轨迹重要移动特征被忽略，轨迹段的方向值计算结果不准确。本实验在顾及行人速度及设备采样频率的前提下，针对自采轨迹设定K=12，飞行轨迹K=25。

2) 窗口移动步长：为了保证窗口线段方向值的连续性与邻接性，本文设置相邻滑动窗口之间存在重叠。

3) 象限逗留时间：单条自采轨迹持续时间为25~40 min，设置移动对象在单个象限内逗留时间至少为25 s；单条Wikiloc飞行轨迹持续时间约1.5 h，但考虑到轨迹飞行盘旋半径比较小，因此逗留时间不应设置过大。

针对2条自采轨迹和1条Wikiloc飞行轨迹的“8”字模式探测，实验结果分别如图 11和图 12所示。图 11和图 12中的红色轨迹段为探测出的“8”字模式，可以看出，本文方法能够有效探测行人轨迹和飞行轨迹中的“8”字模式，并且探测结果仍保持盘旋行为的连续性。自采轨迹中的“8”字模式是由行人模拟产生，其移动状态相对平稳、“8”字形态均匀，提取出的模式轨迹段完整。但在真实的飞行场景中，由于飞行环境、航线约束等因素，轨迹的移动特征表现多样、移动模式波动较大。如图 12所示，同一条轨迹中，移动对象的“8”字盘旋幅度差异明显，表观呈现大小相差明显的“8”字。为了保证模式提取的完整性，首先设置较长的象限逗留时间，用于提取盘旋半径较大的轨迹段；其次利用较短的时间阈值，探测盘旋幅度小的“8”字，最终获取到整条轨迹上的模式轨迹段。

从实验结果也可以看出，象限表达的模式探测是基于方向变化特征的，即使是不同移动场景，盘旋模式的象限序列与状态变换的本质特征相同，这保证了基于飞行轨迹的“8”字盘旋模式探测实验应用于行人轨迹“8”字提取的可行性。与具体应用场景相适应的参数变化并不影响本文所提方法的实践。

本文提出的轨迹模式分析方法主要优势在于：(1)象限序列保证了空间变换上的鲁棒性，能够较准确探测不同移动对象的相似特定移动模式；(2)基于状态转移函数加快了匹配速度，保证快速探测轨迹的特定移动模式；(3)对特定的轨迹移动模式只需要自定义相应的象限正则表达式，通用性和扩展性强。模式串象限序列FSM以一种离散的象限序列来拟合连续移动状态，在匹配过程中不符合表达式所约束规则下的象限序列均被视为无效。因此，在保证识别效率的前提下，该方法需要考虑特定的轨迹移动模式由于不同具体移动对象的个体运动风格差异所导致的不一致性。

3 结语

移动模式挖掘一直是轨迹大数据分析的热点和难点问题。本文面向单体轨迹数据，提出了一种基于方向象限映射的移动模式探测方法，其主要思想是将轨迹的方向序列映射为象限空间中的访问序列，并编码表达为字符串，据此构建移动模式的正则表达式，从而利用有限状态自动机来表达与解析移动模式，实现了基于字符串匹配的单轨迹移动模式探测。基于Wikiloc的飞行轨迹和自采轨迹的实验结果表明，该方法可以有效表达移动模式的方向变化语义，能够高效探测单轨迹的“8”字盘旋移动模式。基于轨迹段的方向变化来定义移动模式的正则表达，并实施基于有限状态自动机的模式匹配。本文方法对于轨迹数据的噪声和尺度是不敏感的，且具有良好的旋转不变性，是一种高效且鲁棒的移动模式探测方法。但本文的移动模式提取方法本质上只考虑了方向特征，如何综合考虑更多的移动特征信息，实现更科学合理的模式探测是下一步需要研究的内容。