基于航迹相似性的目标经典航道挖掘算法*

付 讯 薛丽惠 谢 卫

（中国西南电子技术研究所 成都 610036）

1 引言

随着传感定位设备的广泛使用，产生并积累了海量的时空轨迹数据，真实记录了目标在现实世界的活动情况，在一定程度上能够反应其活动规律及变化趋势［1～5］。以目标为中心的历史时空轨迹数据挖掘分析在商业智能、国家安全等领域有着迫切应用需求［6～9］，推动着时空数据挖掘成为近年来的研究热点问题。目标经典航道提取是时空数据挖掘的一个典型场景，它从航迹的整体相似性出发，对航迹进行相似性计算与聚类分析，挖掘目标频繁使用的轨迹序列。

目前，国内外基于历史数据进行经典航迹提取的研究主要从以下三大类进行：第一类、基于路网匹配［10～12］，这类算法首先将航迹与道路信息网进行匹配，统计路网中的道路热度，基于热度提取经典航迹；第二类、基于序列规则［13～15］，提取航迹驻留点并与现实世界具体位置关联，将航迹转为地理位置的途径序列，使用序列规则挖掘算法实现；第三类、基于轨迹聚类分析［16～20］，首先对航迹进行聚类分析，通过特定方法选择类中某一条航迹作为经典航迹。

上述方法在一定程度上实现经典航迹提取，但在面向海空目标的经典航迹提取仍然存在以下问题：第一、海空目标不存在类似陆地目标的路网信息；第二、相似性与驻留区域分析依赖经验值，可扩展性不高；第三、面向海量数据处理能力不足。对此，本文提出一种经典航道提取算法，考虑数据的实际分布特征，将经典航迹拓展为带状区域的经典航道，使得挖掘生成的知识数据有一定的容错性。算法基于MapReduce 编程，通过数据预处理、聚类分析、边界提取等步骤完成经典航道提取。

2 问题定义与描述

海量的时空航迹数据中蕴含了目标空间活动规律信息，其主要表现为目标在一段时间范围内或一定任务下，总以相同或者相似的航迹在出发地与目的地之间反复的出现。通过对这些航迹数据的挖掘分析，可辅助实现目标行为异常检测、任务意图分析、活动趋势预测。但在现实的场景下，目标规律隐藏在海量的原始航迹中，很难直观地发现与描述，因此需要设计实现经典航迹数据的提取算法，辅助分析人员进行知识发现。

2.1 问题描述

航迹是目标在三维空间中一次运动所产生的空间位置按时间顺序排列的点集合，位置点信息一般包括航迹编号、目标名称、经度、纬度、高度、速度、航向、位置时间等要素信息。本文研究对象为ADS-B获取的目标航迹数据。

经典航迹则用于描述目标在一段时间范围内或特定任务背景下经常使用的航迹，它们在空间上位置相近、形状相似；由于目标在三维空间活动时其航迹一般都分布在一定的空间范围内的带状区域，因此本文使用带航道来描述舰机目标频繁（规律）路径。

经典航道挖掘可形式化描述如下：一组待处理的原始航迹数据集T=｛t1，t2，……，tn｝，其中ti=｛p1，p2，……，pm｝（1 ≤i ≤n）表示集合中某一条航迹，航迹点pi=｛trkNum，name，lon，lat，height，speed，movdir，loctim｝（1 ≤i ≤m）。经过航迹预处理生成的航迹段集合Segs=｛L1，L2，……，Lo｝，Li（1 ≤i ≤o）表示一条航迹段；4 航迹聚类结果RS=｛C1，C2，……，Cr｝，Ci（1 ≤i ≤r）表示由若干航迹段组成的类簇，满足Ci∩Cj=Ф（i≠j）且C1∪C2∪……∪Cr=Segs。经典航道生成就是对每一个类簇Ci进行处理，提取其边界，使得类簇中大多数航迹位于航道内部。

2.2 概念定义

下面给出目标经典航道挖掘过程中的涉及到的部分名词定义。

野值点：由于传感器误差原因，导致采集到的目标空间位置点，显著偏离目标活动的正常值，从而形成航迹数据中的野值数据。图1 给出了航迹中常见的野值点分布模式。

图1 野值点示例

航迹栅格化：栅格在本文指通过使用二分法将地理空间划分为若干大小相等的网格，网格内每个经纬度点都有相同的代号，每个划分后的网格称之为一个地理栅格。本文采用GeoHash 进行航迹栅格化，从而压缩数据规模，提高处理效率，表1给出了不同编码长度下的误差信息，参考民用航道划分的标准，本文采用5位GeoHash编码。

表1 GeoHash精度

航迹相似性：是指两条航迹在位置向形状上的相近程度，假设track1 经过航迹栅格编码后的序列为｛str11，str12，……，str1m｝，track2 栅格编码序列为｛str21，str22，……，str2n｝，track1 与track2 的公共子串为comSegs=｛strc1，strc2，……，strck｝，则航迹相似度计算公式（1），其中n，m分别为两条航迹的长度。

驻留区域：指目标过航某一区域所用时间显著超过其按照正常速度过航所用时间，这样的区域称之为驻留区，这些区域一般是目标的作业区域，具有丰富的业务含义，是目标行为分析时关注的重点。图2给出了航迹驻留区域分布模式。

3 经典航道提取

本文给出的航道提取算法包括数据预处理、航迹聚类、航道生成等步骤。

3.1 数据预处理

原始航迹中的野值点、驻留区域数据会导致航迹相似性计算结果存在偏差，影响航迹聚类与经典航道结果的准确性。为提高航道提取的准确率，需要剔除野值点、分析驻留区，并基于驻留区域将原始航迹划分为若干航迹段，基于划分结果进行聚类分析及航道提取。下面给出预处理中两个关键步骤的实现逻辑。

1）野值剔除

本文采用一种启发式的航迹野值剔除算法，基本思想为：首先，基于背景知识获取每类目标的最大速度；其次，遍历每一航迹点，剔除属性为非法值的航迹点，基于航迹点间距离与时间差计算当前点与后续三个点的距离、时间差，在此基础上计算当前点到后续三个点的速度v1、v2、v3；再次，如果三个速度均为大于知识数据给定的值，则判定当前航迹点为异常点，进入下一步循环。图3给出了异常值剔除的基本流程。

图3 野值剔除算法

2）驻留区域检测与航迹分段

航迹中的驻留区域一般分为两种：单点停留与某区域内反复活动，对于海空舰机目标而言更常见的驻留区域则是后一种情况，在实际的运动过程中具体表现为在一定的区域内通过跑马环线或者八字环线往复运动。它有一个显著特征，在驻留区域每一个点附近都会反复多次经过。针对这种情况本文使用一种基于距离的驻留区检测方法，算法步骤描述如下：

步骤一：获取野值剔除后的目标航迹Trajectory并按照位置时间进行升序排列，对航迹中的每一个点采用GeoHash 5 进行编码处理，生成序列geoHashs。

步骤二：按序获取geoHashs 的值，对当前值i，如果i后连续k 个点均落在hashcodei中，第i+k+1 个点落在另一个栅格中，则将这n 个点的栅格信息简化记录为，下一次处理从i+k+1开始，从而生成序列dataLst。

步骤三：筛选出datalst 中hashcode 出现频度大于2 的栅格，合并相同编码的栅格，记录其出现频度，重新计算进入栅格时间与离开栅格时间，其中tin=min（tin1，tin2）、tout=max（tout1，tout2），生成新的数据结构放入候选停留栅格stayLst中，并按照出现频度对stayLst进行降序排列。

步骤四：分隔目标的原始航迹，遍历原始航迹中的点，如果当前点位置时间落在stayLst中的某个元组的时间区间，则将其从改点分隔，为前序点集合分配一个航迹段标识，知道Trajectory 中所有航迹点都被处理。

3.2 航迹聚类

航迹聚类是航道提取的一个重要步骤，它从空间相似性出发，将形状相似、空间相近的航迹聚成一类。本文基于一种层次聚类算我完成航迹聚类分析。算法实现思路如下：

步骤一：将预处理后的航迹数据使用GeoHash编码算法（编码长度为5）进行栅格化处理，将航迹点序列转化为GeoHash 串，降低数据维度、提升处理效率。

步骤二：基于最大公共子串思路，采用公式1计算两两航迹段之间的相似度，生成各类簇中航迹段的相似度矩阵。

步骤三：引入最小相似度阈值minScore，基于相似度矩阵求解各个航迹段的邻域组合。

步骤四：对邻域进行迭代合并，直至类簇不再发生变化且每个航迹段都被唯一划分值一个类簇中，其中合并原则为：如果两个类簇包含相同的航迹段则将其合并为一个类簇。

3.3 航道生成

目标航迹完成聚类分析后形成若干航迹簇，同一类簇中的各个航迹段在形状与空间上具有相似性，类簇的边界可大致描述目标在该区域的活动时所采用的的航道信息。因此可将目标航道提取转换为求解平面离散点集合的轮廓问题，对此，本文提出一种自适应半径的基于Delaunay 三角刨分算法的目标航道提取算法。算法步骤描述如下：

步骤一：本算法首先获取类簇中所有的航迹点，采用GeoHash 6 对航迹点进行稀疏化处理，即落在同一个栅格中的多个航迹点均使用该栅格的中心点去表征，记稀疏化后的点集为S。

步骤二：遍历S 中各个航迹点，求解每个航迹点离其最近航迹点的距离distance，选择其中最大值记录为步骤四边界判断的阈值radius。

步骤三：对集合S 中的点按照经度、纬度进行升序排列，采用Delaunay 三角刨分算法构造S 的三角刨分网格M。

步骤四：识别M 中的外部边与外部三角形，并将边长大于radius 的外部边edge 放入队列Q，其中外部边指仅在一个三角形中存在的边，外部三角形指包含外部边的三角形，采用如下方式迭代删除Q中所有的外部边：从Q 中取出一条外部边edge，找到edge 所在的外部三角形T，将edge 从Q 与T 中删除，将T 从M 中删除，此时T 中其它两条边edge1、edge2均变成外部边，将其中边长大于radius的边放入Q中。

步骤五：识别经步骤四处理后的M中所有的外部边，生成外部边列表edgeLst，作为目标的活动航道的边界信息输出。

通过上述处理步骤，算法可依据数据集分布特征，求解出一个合适的边界判断阈值radius，然后基于Delaunay算法完成目标航道边界提取。

3.4 算法并行化设计

经典航道挖掘是从海量的历史数据集中进行，以2020年1至3月为例，某ADS-B系统接收到的航迹数据近4 亿条航迹点，传统单机系统很难在短时间内处理完如此规模的数据。因此本文设计的算法基于MapReduce 编程模型在大数据计算平台上实现，图4给出了算法各个关键阶段的数据分治策略。

图4 并行化流程

其中，在预处理与聚类分析时的栅格化阶段由于处理对象是以单条航迹进行的，故以航迹编号作为分组条件；相似度计算与聚类分析是以目标为单位进行的，因此以名称进行数据分组；航道提取阶段则以类簇ID为分组条件。

4 实验评估

本文所提出的目标航道提取方法在阿里云MaxCompute V3.0大数据计算平台上采用Map-Reduce 编程模型实现并验证。实验数据集为2020年1至3月某ADS-B 系统获取的近4亿条民航航迹数据。图5 给出了算法中各主要环节中部分目标的实验效果图。

图6 中（a）图给出了野值检测的效果，在算法实现过程中根据不同目标引入不同的速度阈值，从实验结果可以看出，本文算法能够有检测出航迹中的野值数据。（b）图给出了驻留区域检测与航迹分段效果，可发现本文采用的基于距离与时间阈值的驻留区算法能够有效检测出原始航迹中的驻留区域。（c）图与（d）图给出了目标不同的航迹类簇及基于类簇生成的航道信息，根据试验结果可以看出，本文提出的目标聚类与航道边界提取算法能够较好地区分目标的航迹空间特征，形成不同的航迹簇，并且能够从航迹簇中有效提取出目标航道的边界信息，从而印证了本文提出算法的有效性。

5 结语

本文针对海量时空航迹数据分析处理需求，设计并实现了一种目标经典航道挖掘算法，通过数据去噪、驻留区域检测、航迹分段、相似性计算。实验结果表明，本文提出的算法能够有效提取目标的航道特征，在一定程度上解决基于数据驱动的知识发现问题。由于本文仅从航迹数据的空间分布特征出发，未引入业务场景语义，因此在后续工作中可考虑多元数据关联，引入目标行为意图，分析目标在不同行为意图下的航迹特征。其次可在本文的基础上，开展实侦条件下的基于经典航道的目标异常行为检测与动向预测等研究工作。