-
随着各类位置传感器、定位芯片的广泛使用，具有时空属性的数据出现在日常生产生活和经济文化活动的各个领域中。时空轨迹（记录移动对象随着时间推移而发生位置变化情况的数据）作为最为典型的时空数据类型，数据量呈爆炸式增长态势，其中蕴含的信息反映出移动对象不同的运动规律和行为模式，具有重要的挖掘价值。
轨迹相似性分析是轨迹模式挖掘的重要基础，在实际生活中的应用丰富，扩展性强，如社区人员的相似行为匹配与挖掘、基于相似出行模式的用户推荐、目标异常移动监测、船舶出航习惯聚类、基于相似历史轨迹的交通调度等。利用人员的移动、出行轨迹模式计算在预估和防治传染病传播中发挥巨大作用，如更加精准地筛查高危人群、划定传播范围，更加高效地控制病毒扩散和减缓蔓延趋势。
真实移动对象移动速度不一，移动方式多样，产生的轨迹形态及在不同的采样策略下得到的离散有序轨迹点分布也复杂多变，传统的轨迹相似性计算先采用时间翘曲或拉伸的方式匹配采样点，再基于点距离计算轨迹段间的关系。轨迹的分段会直接影响子段匹配的结果，传统做法是先遍历两条轨迹中的所有可能的子段，再采用特定的距离或相似性度量筛选出最接近的子段对。当前研究主要关注子段匹配效率和准确率的提升，如Lim等[1]和Keogh等[2]基于动态时间规整（dynamic time warping，DTW）距离提出一种使用有限时间翘曲的子轨迹匹配算法，减小了子段过滤的候选集，实现了高效的子轨迹相似查询；Buchin等[3]和Godau[4]采用弗雷歇距离寻找轨迹相似子段，证明了寻找最长相似子段是NP-complete问题，并利用自由空间图提出了近似计算方法，降低了计算复杂度；为了在非等间隔采样的轨迹中寻找相似子轨迹，Buchin等[5]设计了基于时间平均欧氏距离的相似子段查询算法，将时间复杂度从平方降低到线性，并面向有时间漂移的轨迹提出了1+ε近似算法；在其他相似性度量方法方面，Xie[6]提出了基于编辑距离的轨迹片段相似性度量（edit distance similarity，EDS），并将其应用于轨迹子段相似性查询中；Chen等[7]考虑子轨迹多维运动特征的距离度量，并以此为基础改进了只考虑运动方向变化的轨迹分段算法；Furtado等[8]通过加权归一化操作设计了一种计算多维度语义轨迹相似性的模型，并验证了该模型对轨迹不同维度出现的噪声和空隙具有更好的鲁棒性；Mao等[9]结合DTW算法提出了基于轨迹分段的动态时间翘曲距离度量，将点与点的距离替换为点和段之间的距离，同时考虑了轨迹形状和时间距离，精度更高、对噪声鲁棒性更强。
有代表性的较新研究成果是Yoo等[10]提出的基于豪斯多夫距离的时空子片段匹配算法。该算法在实现过程中先使用子段最小包围框（minimum boundary rectangular，MBR）建立的R树索引以进行快速剪枝，通过分割索引、相似计算和缝合重建3个步骤实现轨迹子片段的最长匹配，与文献[6]相比，提出的EDS度量大幅提高了准确率，同时具有较好的扩展性，可应用于不同采样条件的轨迹数据中。
可以看出，现有轨迹子段相似性匹配方法大多是经典轨迹距离或相似性度量，如最长公共子序列（longest common subsequence，LCSS）[11]、带实际惩罚函数的编辑距离（edit distance with real penalty，ERP）[12]、实际序列编辑距离（edit distance on real sequence，EDR）[13]、豪斯多夫距离和弗雷歇距离等，在轨迹分段基础上的扩展，部分考虑了轨迹点间的前后顺序特性，忽略了轨迹采样点之间的空隙，割裂了轨迹点之间的连续性，且在计算效率方面有较大的提升空间。
为解决以上不足，本文从面向轨迹点的传统视角转为面向轨迹段，提出了一种基于编码树结构的轨迹相似子段匹配方法，以相邻采样点间的片段为基本单位，设计了轨迹多层级编码树结构，充分反映轨迹段的时序特性和轨迹的多粒度性质，并在此编码树的基础上实现了基于轨迹段的编码和子段匹配方法。
HTML
-
现有关于移动对象与轨迹的索引结构是以分离的轨迹点为依据，对R树、KD树等经典索引的改进[14-16]，要在轨迹子段匹配中实现从面向点到面向段的思路转变，还需要对本文方法涉及的一些术语进行简单介绍，相关概念在图 1中进行了标识。
Figure 1. Related Concepts
原始/真实轨迹：一定时间段内，移动对象在欧几里得空间中连续运动形成的曲线，可以用连续时间函数精确描述其形态。
轨迹点序列：由传感器按固定或随机的频率记录移动对象的空间位置，作为真实轨迹数据的采样，通常用一串包含空间和时间信息的位置序列来表示。（1）轨迹片段：由相邻两个轨迹采样点构成的最小时空片段。（2）轨迹子段：将轨迹序列分割为多个分段，分段依据为轨迹形态特征或语义信息。每个分段包含多个连续轨迹采样点。
-
地理网格编码可以用一个完备的格网模型及其编码规则描述地球表面的任意一个位置，不同编码技术的区别在于格网划分方式和码元设置规范。其中，地理哈希编码具有简洁的规则、精度可控的位置描述能力和良好的体系兼容性，在地理信息网格组织、空间数据网格索引等方面具有广泛应用[17-19]。地理哈希编码通过将全球经纬度范围不断二分，将地理空间不断缩小逼近目标点，同时用0、1作为两部分空间的代码，逐步将精确的经纬度二维坐标转换为一个一维的字符串，并可以通过Base32等编码方式表示。为了提高地理哈希编码的空间局部性，使用Hilbert空间填充曲线顺序作为网格遍历和编码的依据，其前两个两层级的网格划分如图 2所示。
Figure 2. Hilbert Geohash Coding
使用分层级的自适应地理哈希编码可以描述轨迹的多粒度特性，其中编码层级是由轨迹分段的尺度大小自适应计算得到，只要使得当前层级的网格大小刚好不小于该分段的外包框范围即可，编码依据为不同粒度轨迹分段最小包围框的中心点坐标。
采用以上编码方法，即可形成定位精度与地理实体覆盖空间范围相匹配的自适应希尔伯特地理哈希空间网格编码（adaptive Hilbert-geohash，AHG）。不同层级轨迹分段的AHG编码十分适合构建上下层级具有空间从属关系的树结构，且树的父子、兄弟关系都具有明确的空间关系映射，所以可以通过多层级轨迹片段编码树结构来表达轨迹的多粒度特性。
构建多层级轨迹编码树的基本步骤如下：以整条轨迹的自适应空间网格编码为根结点，自上而下地进行多层级分段和编码，构成编码树的中间结点，最底层结点由相邻两轨迹点构成时空片段的编码组成，各结点编码根据分段的从属关系设置父子结点链接，最终形成编码长度与分段数量同步扩展的多粒度片段编码树。典型的3层级编码树结构如图 3所示，各结点字符串仅为轨迹子段编码的示例。
Figure 3. A 3-Layer Trajectory Code Tree
轨迹的分段可以根据实际数据特点和应用需求采用不同的方式，典型方法有等间隔点分段、等距离分段、拐点分段等。
-
空间编码树的结构与原轨迹具体的对应关系为：（1）根结点：整体轨迹的AHG编码；（2）枝结点（中间层级的结点）：轨迹分段/子轨迹的AHG编码；（3）叶子结点：轨迹片段的AHG编码；（4）子树：子段/子轨迹；（5）结点或子树的父子关系：轨迹片段或分段的从属关系；（6）结点或子树的左右兄弟关系：轨迹片段或分段的前后相邻关系。
根据实际应用场景和实际轨迹数据特点，也可以构建多于3层的编码树，即在轨迹根结点和最小时空片段叶子结点之间，建立两层以上的中间结点，涉及到更多粒度的轨迹分段，可以由粗到细更加精细地描述轨迹多层级的特性，适用于长度较长、形态变化较为复杂的轨迹。但更多层级轨迹编码树的存储结构更复杂，构建耗时也更高，故本文主要以3层轨迹编码树为例进行相似子段匹配的分析和探讨。
不同粒度网格的尺度间接反映轨迹多层次的不确定性，如当轨迹分段粒度较细时，自适应网格尺度也较小，网格序列可以基本反映出轨迹的形态走势，对应的编码精度也较高，基于该编码树可以直接得到较为精确的分析结果，但细粒度下构建编码树的时间与空间代价也较大；当轨迹分段粒度较粗时，自适应网格尺度较大，网格的不确定性范围也比较大，对应的编码精度较低，但该粒度下构建编码树的时间与空间代价小，后续基于编码树的分析计算也较快，可以快速得到粗略的分析结果。所以需要根据轨迹的来源、采样特点、形态特点、长度分布等因素，对分段粒度大小进行权衡选择，得到性能和效率的平衡。
1.1. 相关概念
1.2. 轨迹编码树构建方法
1.3. 轨迹编码树的特性
-
轨迹编码树的相邻结点可以反映轨迹片段时序和空间临近关系，可以把复杂的点统计或大量点距离的计算转化为简单的字符串编码前缀匹配。若两个轨迹分段的空间编码相同，代表对应轨迹段从属的网格相同，属于相似子段。而不同轨迹编码树间任意一对结点编码的相同前缀长度代表着轨迹段的相似程度，这个性质为轨迹子段相似性匹配问题带来新的思路。
-
在实际轨迹的比较中，对整条轨迹进行相似性计算可以得到一个相似值，但真实移动对象的运动轨迹往往长短不一，轨迹往往具有局部的相似性和整体的不相似性。现实的需求也常常不需要得到整体的相似度，而是需要寻找两条轨迹中相似的某一部分。
计算轨迹相似子段的步骤如下：首先，对两条轨迹分别进行分段；然后，计算两个集合中两两分段的相似性，得到相似性最高的一对或几对分段，即为两条轨迹的相似分段。分段的对应关系不必按照分段在原轨迹中的次序，故将轨迹子段相似匹配问题定义如下：（1）输入数据：两条时空轨迹（T1，T2），轨迹分段粒度（采用等间隔点分段时即为间隔点数）；（2）目标输出：两轨迹包含的相似子段；（3）约束条件：显著性检验值小于α，α通常取值为0.05。
-
利用编码树结构可以将相似子段的寻找转换为简单的字符串前缀匹配操作。具体步骤如下：
1）建树。对两条轨迹进行分段，分别建立轨迹编码树。
2）遍历子段组合。遍历不同的子段组合，通过对应的编码子树计算子段对的相似度。计算每一对子段的相似度分为初始判断和最小片段相似值计算两个步骤。
3）初始相似度判断。为减小候选子段数量，可以根据子段编码的粗粒度相似度进行预剪枝，将编码差别较大的子段排除出候选集。记当前两个子段在编码树中的编码分别为C1与C2，长度分别为L1、L2，求取两编码的相同前缀，记为Cpre，长度为Lpre，则子段初始相似度S为相同前缀长度与两子段编码平均长度的比值，即S=2Lpre/（L1+L2）。
当得到的相似度S大于设定的粗相似度阈值时，继续进行下一步的最小片段的相似度计算，否则在结果中直接排除当前子段对。
4）最小片段的相似值计算。在编码树中取出两个子段的子结点，也就是子段包含的片段集合，按顺序组合两个集合中的元素，得到一组片段对及其对应的编码对，使用相同的公式计算其相似度，并进行加和与平均计算，即得到片段粒度的相似值，作为当前子段的最终相似度。
5）排序筛选。对符合条件的子段对的相似度进行排序，获取大于阈值的子段对，并进行去重、合并等操作，得到相似子段匹配备选结果。
6）显著性检验。对备选匹配子段进行显著性检验，得到统计显著的相似子段。
得到子段匹配候选集后，采用最常见的T检验方法对结果进行显著性检验。检验的零假设H0为：轨迹子段对是不相关的。如果T检验得到的子轨迹的相关性的p值小于α，则拒绝原假设，α的取值可根据应用场景对误判和漏判的不同要求进行设定，一般可取0.05、0.01、0.005等值，α取值越小，对误判容忍程度越小，即显著性要求越高。统计子段匹配算法找出的结果中通过显著性检验的子段对数，计算与结果总数的比值，可以作为算法的准确率衡量指标。
-
代表轨迹分段编码的字符串在内存中都是以字节形式保存的，在算法具体实现过程中，可以将字符串前缀匹配操作转换为内存单元的位计算，能够大幅提高字符串匹配效率，复杂度仅为常数级。本文提出的子段匹配方法的复杂度主要在于构建轨迹编码树和遍历子段组合的过程。
在构建轨迹编码树的复杂度方面，对单个轨迹段进行自适应网格编码为常数复杂度。记单条轨迹长度，即包含的最小时空片段数为N，故当以p表示轨迹第二层级分段粒度时，建立三层级编码树的复杂度为O（1+N/p+N）。
而在遍历子段组合与筛选相似子段过程中，每对子段的相似性计算是基于字符串前缀匹配的简单操作，复杂度为O（1），故计算所有子段对相似度的复杂度为O（N/p（N/p-1）/2）=O（N2/p2-N/p）。顺序遍历单个子段对所包含的最小时空片段对，并计算其编码相似度的复杂度为O（p），最小片段粒度的匹配复杂度为O（（N2/p2-N/p）p）=O（N2/p-N）。另外，相邻子段判断、子段合并操作在轨迹编码树结构基础上仅为常数级复杂度。
将上述几个步骤复杂度进行加和，得到使用轨迹编码树寻找相似子段的总体复杂度为O（1+N/p+N+N2/p2-N/p+N2/p-N）=O（N2/p2+N2/p）。当分段粒度p为常量时，算法总体复杂度为O（N2）。
2.1. 问题定义
2.2. 相似子段计算与显著性检验
2.3. 复杂度分析
-
实验同时使用真实轨迹数据和人工合成的轨迹数据，具体描述如下：
1）真实轨迹数据。海洋地籍数据为美国海事局自动识别系统（automatic identification system，AIS）记录的船舶轨迹数据，包含了美国邻近海域上超过150 000艘船舶的航行轨迹，为典型的无约束轨迹，轨迹点的采样频率为2~10 s。
出租车轨迹数据。美国旧金山市出租车的真实行驶轨迹，仅包含采样点的位置数据，使用的数据样本包含超过20 000条出租车轨迹，每条轨迹有100~500个位置采样点，为典型的有路网约束的轨迹，轨迹点的采样频率为10~30 s。
2）人工合成数据。从真实轨迹中提取子段加入固定偏移或者随机噪声生成的具有一定相似性的轨迹，其中，固定偏移和随机噪声大小与原轨迹段的长度成正比，以达到扰动程度相对一致的目的。
为了评估所提出方法的各项性能，选取基于经典轨迹距离的相似度量方法，如弗雷歇距离方法和最长公共子序列距离方法[11]，以及文献[10]方法作为对比基准。
-
本实验采用等间隔点分段方法测试编码树的构建效率。为探究轨迹长度与建树耗时的关系，首先，固定轨迹分段参数为10，即每隔10个轨迹点进行分段；然后，分别使用AIS船舶数据和出租车轨迹数据建立三层级轨迹编码树，记录建树和在硬盘持久化的耗时。随着选取的轨迹长度的增加，建树耗时情况如图 4所示。可以看出，两种轨迹类型的建树耗时均与轨迹长度呈线性函数关系，单条轨迹的建树时间在毫秒量级。
Figure 4. Code Tree Building Time of Different Lengths
取1 000条轨迹数据，采用不同大小的分段粒度建立编码树，耗时结果如图 5所示。可以明显看出，随着分段粒度的增加，两种轨迹数据集建树的耗时呈下降趋势。这是因为分段长度越大，单个轨迹对应的分段数越少，编码树结点总数和进行空间编码和构建整树的耗时也就越少。
Figure 5. Code Tree Building Time of Different Granulates
-
构造相同的子段匹配计算任务，使用统一的标准衡量本文提出的编码树匹配方法与其他经典方法的性能，对单个测试项和准确率计算步骤设计如下：
对一条轨迹按照一定的粒度（作为实验变量）进行分段后，随机选取某一子段作为测试数据，对其包含的所有轨迹点使用固定方向的固定长度偏移或者随机方向的随机噪声扰动，生成测试子段，加入的偏移和噪声大小为原始字段长度的5%，是原始轨迹子段对应的正确匹配结果。
使用不同的相似性度量方法寻找原轨迹与该测试子段相似性最高的子段作为匹配结果。如果匹配结果恰好为噪声扰动前的子段，则该测试结果为命中。
从真实轨迹数据集中选取1 000条长度较长的轨迹，以便于使用不同粒度进行分段得到足够数量的子段进行上述测试，结果命中数量与测试轨迹数量的比值即为该子段匹配方法的准确率。
在生成测试子段过程中，使用的固定偏移方向为东北（即直接对轨迹点经纬度使用加法），偏移大小为该子段长度的2.5%；使用的随机噪声符合正态分布，其均值为0，标准差为该子段长度的5%。而候选集的大小控制了匹配过滤操作的精度，本实验中采用的候选集大小为3，即保留原轨迹中与测试子段相似度排在前3的子段，作为本文方法的粗过滤结果。在候选集中进行精确匹配计算，即可得到本文方法的精确结果。
使用不同的分段粒度，各方法匹配加入固定偏移的子段的耗时和准确率结果如图 6、图 7所示，其中图 6中蓝色与红色柱体分别表示采用本文方法的粗过滤耗时与精确匹配耗时。从图 6可以看出，在效率方面，随着分段粒度增大，最长公共子序列、弗雷歇距离方法的总耗时呈缓慢上升趋势，这是由于计算单对子段的经典距离相似性的复杂度为O（plgp），需要进行N/p对子段的相似性计算，因此总复杂度为O（Nlgp）。而文献[10]方法单个相似性测试的复杂度为O（|Q|N），其中Q为测试子段的长度，即为本实验中的分段长度p，为常量，于是总复杂度为O（N），总耗时呈水平不变趋势，实验结果符合预期。
Figure 6. Sub-trajectory Match Time with Fixed Offsets
Figure 7. Sub-trajectory Match Accuracy with Fixed Offsets
本文方法的匹配耗时相较于其他方法都有超过一个数量级的提升，且分段粒度越大，效率优势越大，这是因为本文方法只需要对结点编码进行字符串的前缀匹配操作，计算效率较高。
在准确率方面，蓝色空心三角图例标识的结果是使用轨迹编码树进行子段匹配的准确率。从图 7可以看出，在分段粒度较小时，即每隔5或10个轨迹点进行分段时，编码树的准确率落后于基于弗雷歇距离的相似性匹配方法和文献[10]方法，甚至稍低于准确率下降最快的最小公共子序列方法。这是由于3种对比方法的计算过程都使用了轨迹点间的精确欧氏距离作为度量基础。在分段较小时，可以更好地衡量子段的相似性；在分段粒度较大时，本文方法的准确率与经典距离方法持平，甚至高于经典距离方法，如分段粒度为50时就大幅领先另外3 种对比方法。这是因为轨迹编码树的中间层结点是轨迹分段的地理网格编码。在空间形态上，是用一个矩形网格代表该子段，子段粒度越大，越容易根据测试子段筛选出原始子段。
介于分段粒度较小时，本文方法的准确率并无明显优势，为了进一步说明本文方法的性能，在实验中，对基于编码树的子段匹配结果继续进行精确匹配计算，具体做法为：在子段粗过滤结果集中，使用轨迹编码树最底层的叶子结点，即轨迹最小片段的MBR端点的精确距离计算出片段距离，并进行加和计算得到子段的综合距离，筛选出距离最小的子段作为匹配结果。这种精确计算的方法可以使子段匹配结果达到100%的准确率，而粗过滤和精匹配的总耗时（如图 6中红色柱体标识结果）仍然明显低于经典距离方法，且分段粒度越大，效率优势越大。
在对轨迹子段加入随机小噪声后，使用不同的分段粒度进行子段匹配的耗时与准确率结果如图 8和图 9所示。
Figure 8. Sub-trajectory Match Time with Random Noise
Figure 9. Sub-trajectory Match Accuracy with Random Noise
从图 8可以看出，在计算效率方面，本文方法的子段匹配耗时相较于其他方法有超过一个数量级的提升。本文方法相比于仅进行粗过滤，精确匹配的耗时有所增加，但与其他方法相比仍具有显著优势，且分段粒度越小，优势越明显。从图 9可以看出，在不进行精确匹配操作时，分段粒度较小的编码树的准确率仍然低于文献[10]方法。对子段匹配粗过滤结果进行精确匹配计算，本文方法匹配准确率达到100%。
3.1. 实验数据与环境设置
3.2. 轨迹编码树构建效率
3.3. 子段匹配效率与准确率
-
本文结合轨迹的多粒度特性，从面向轨迹点转为面向轨迹段的新型视角，基于改进的自适应希尔伯特网格编码方法提出一种多层级轨迹编码树结构，在可接受的建树代价下，实现了从轨迹粗粒度到细粒度的层次化组织。并在此编码树的基础上设计了轨迹相似子段匹配算法，将复杂的空间计算转化为空间编码间的字符串匹配操作，极大地降低了轨迹相似子段匹配的计算复杂度。本文提出的方法为分析多层次精细化轨迹模式、扩展多样化轨迹相似性应用场景提供了效率保证。
由于本文提出的子段匹配方法使用了基于希尔伯特空间填充曲线的编码，具有不可避免的编码突变性，需要进行二次筛选才能得到完备、精确的结果。下一步研究将在轨迹子段编码树的基础上，结合R树、KD树等完备的空间索引结构，进一步提高算法准确率。
DownLoad:
